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

[Christian Hergert <chergert src gnome org>]

commit f91234227b2319cb6237f18212971e964d379ad9
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.

 docs/reference/glib/glib-sections.txt |  2 ++
 glib/gqueue.c                         | 67 +++++++++++++++++++++++++++++++++++
 glib/gqueue.h                         | 10 ++++++
 glib/tests/queue.c                    | 35 ++++++++++++++++++
 4 files changed, 114 insertions(+)
---
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index 10ec35f75..82512fe8c 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -2390,7 +2390,9 @@ g_queue_index
 g_queue_remove
 g_queue_remove_all
 g_queue_insert_before
+g_queue_insert_before_link
 g_queue_insert_after
+g_queue_insert_after_link
 g_queue_insert_sorted
 g_queue_push_head_link
 g_queue_push_tail_link
diff --git a/glib/gqueue.c b/glib/gqueue.c
index 76541f493..349dcfee3 100644
--- a/glib/gqueue.c
+++ b/glib/gqueue.c
@@ -1047,6 +1047,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
@@ -1074,6 +1112,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 2c836553b..83102fdb1 100644
--- a/glib/gqueue.h
+++ b/glib/gqueue.h
@@ -144,10 +144,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 46839790f..b2faeb14a 100644
--- a/glib/tests/queue.c
+++ b/glib/tests/queue.c
@@ -1117,6 +1117,40 @@ 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};
+  GList e = {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_queue_insert_after_link (&q, NULL, &e);
+
+  g_assert_true (q.head == &e);
+  g_assert_true (q.tail == &d);
+
+  g_assert_null (e.prev);
+  g_assert_true (e.next == &a);
+
+  g_assert_true (a.prev == &e);
+  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[])
 {
@@ -1133,6 +1167,7 @@ int main (int argc, char *argv[])
   g_test_add_func ("/queue/clear", test_clear);
   g_test_add_func ("/queue/free-full", test_free_full);
   g_test_add_func ("/queue/clear-full", test_clear_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);