[glib/wip/chergert/insertbeforelink: 254/254] queue: add g_queue_insert_before_link() and g_queue_insert_after_link()

[Christian Hergert <chergert src gnome org>]

commit 2e8aea53817d4126ebbacfc07403405f91905317
Author: Christian Hergert <chergert redhat com>
Date:   Mon Jan 7 12:24:42 2019 -0800

    queue: add g_queue_insert_before_link() and g_queue_insert_after_link()
    
    This adds two new helpers that allow for inserting pre-allocated GList
    elements to the queue similar to existing helpers. This may be advantagous
    in some situations such as statically allocated GList elements.

 glib/gqueue.c      | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 glib/gqueue.h      | 10 ++++++++
 glib/tests/queue.c | 30 ++++++++++++++++++++++++
 3 files changed, 107 insertions(+)
---
diff --git a/glib/gqueue.c b/glib/gqueue.c
index 9f34790b9..3b7a7af0d 100644
--- a/glib/gqueue.c
+++ b/glib/gqueue.c
@@ -1025,6 +1025,44 @@ g_queue_insert_before (GQueue   *queue,
     }
 }
 
+/**
+ * g_queue_insert_before_link:
+ * @queue: a #GQueue
+ * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
+ *   push at the tail of the queue.
+ * @link_: a #GList link to insert which must not be part of any other list.
+ *
+ * Inserts @link_ into @queue before @sibling.
+ *
+ * @sibling must be part of @queue.
+ *
+ * Since: 2.60
+ */
+void
+g_queue_insert_before_link (GQueue   *queue,
+                            GList    *sibling,
+                            GList    *link_)
+{
+  g_return_if_fail (queue != NULL);
+  g_return_if_fail (link_ != NULL);
+  g_return_if_fail (link_->prev == NULL);
+  g_return_if_fail (link_->next == NULL);
+
+  if G_UNLIKELY (sibling == NULL)
+    {
+      /* We don't use g_list_insert_before_link() with a NULL sibling because it
+       * would be a O(n) operation and we would need to update manually the tail
+       * pointer.
+       */
+      g_queue_push_tail_link (queue, link_);
+    }
+  else
+    {
+      queue->head = g_list_insert_before_link (queue->head, sibling, link_);
+      queue->length++;
+    }
+}
+
 /**
  * g_queue_insert_after:
  * @queue: a #GQueue
@@ -1052,6 +1090,35 @@ g_queue_insert_after (GQueue   *queue,
     g_queue_insert_before (queue, sibling->next, data);
 }
 
+/**
+ * g_queue_insert_after_link:
+ * @queue: a #GQueue
+ * @sibling: (nullable): a #GList link that must be part of @queue, or %NULL to
+ *   push at the head of the queue.
+ * @link_: a #GList link to insert which must not be part of any other list.
+ *
+ * Inserts @link_ into @queue after @sibling.
+ *
+ * @sibling must be part of @queue.
+ *
+ * Since: 2.60
+ */
+void
+g_queue_insert_after_link (GQueue   *queue,
+                           GList    *sibling,
+                           GList    *link_)
+{
+  g_return_if_fail (queue != NULL);
+  g_return_if_fail (link_ != NULL);
+  g_return_if_fail (link_->prev == NULL);
+  g_return_if_fail (link_->next == NULL);
+
+  if (sibling == NULL)
+    g_queue_push_head_link (queue, link_);
+  else
+    g_queue_insert_before_link (queue, sibling->next, link_);
+}
+
 /**
  * g_queue_insert_sorted:
  * @queue: a #GQueue
diff --git a/glib/gqueue.h b/glib/gqueue.h
index f81f5fb4e..798db9894 100644
--- a/glib/gqueue.h
+++ b/glib/gqueue.h
@@ -141,10 +141,20 @@ GLIB_AVAILABLE_IN_ALL
 void     g_queue_insert_before  (GQueue           *queue,
                                  GList            *sibling,
                                  gpointer          data);
+GLIB_AVAILABLE_IN_2_60
+void     g_queue_insert_before_link
+                                (GQueue           *queue,
+                                 GList            *sibling,
+                                 GList            *link_);
 GLIB_AVAILABLE_IN_ALL
 void     g_queue_insert_after   (GQueue           *queue,
                                  GList            *sibling,
                                  gpointer          data);
+GLIB_AVAILABLE_IN_2_60
+void     g_queue_insert_after_link
+                                (GQueue           *queue,
+                                 GList            *sibling,
+                                 GList            *link_);
 GLIB_AVAILABLE_IN_ALL
 void     g_queue_insert_sorted  (GQueue           *queue,
                                  gpointer          data,
diff --git a/glib/tests/queue.c b/glib/tests/queue.c
index 9f4d3c2ca..e3f5b7dae 100644
--- a/glib/tests/queue.c
+++ b/glib/tests/queue.c
@@ -1080,6 +1080,35 @@ test_free_full (void)
   g_slice_free (QueueItem, three);
 }
 
+static void
+test_insert_sibling_link (void)
+{
+  GQueue q = G_QUEUE_INIT;
+  GList a = {0};
+  GList b = {0};
+  GList c = {0};
+  GList d = {0};
+
+  g_queue_push_head_link (&q, &a);
+  g_queue_insert_after_link (&q, &a, &d);
+  g_queue_insert_before_link (&q, &d, &b);
+  g_queue_insert_after_link (&q, &b, &c);
+
+  g_assert_true (q.head == &a);
+  g_assert_true (q.tail == &d);
+
+  g_assert_null (a.prev);
+  g_assert_true (a.next == &b);
+
+  g_assert_true (b.prev == &a);
+  g_assert_true (b.next == &c);
+
+  g_assert_true (c.prev == &b);
+  g_assert_true (c.next == &d);
+
+  g_assert_true (d.prev == &c);
+  g_assert_null (d.next);
+}
 
 int main (int argc, char *argv[])
 {
@@ -1095,6 +1124,7 @@ int main (int argc, char *argv[])
   g_test_add_func ("/queue/static", test_static);
   g_test_add_func ("/queue/clear", test_clear);
   g_test_add_func ("/queue/free-full", test_free_full);
+  g_test_add_func ("/queue/insert-sibling-link", test_insert_sibling_link);
 
   seed = g_test_rand_int_range (0, G_MAXINT);
   path = g_strdup_printf ("/queue/random/seed:%u", seed);