[glib/wip/chergert/insertbeforelink] WIP: prototype for g_queue_insert_{before, after}_link

[Christian Hergert <chergert src gnome org>]

commit ffe1e7084e95e096b69061b4947398781d350145
Author: Christian Hergert <chergert redhat com>
Date:   Thu Nov 15 11:43:12 2018 -0800

    WIP: prototype for g_queue_insert_{before,after}_link
    
    Also includes the helper for GList to keep list mutation out of gqueue.c.

 glib/glist.c      | 44 ++++++++++++++++++++++++++++++++++++++++++++
 glib/glist.h      |  4 ++++
 glib/gqueue.c     | 37 +++++++++++++++++++++++++++++++++++++
 glib/gqueue.h     | 10 ++++++++++
 glib/tests/list.c | 51 +++++++++++++++++++++++++++++++++++++++++++++++++++
 5 files changed, 146 insertions(+)
---
diff --git a/glib/glist.c b/glib/glist.c
index 51adeb058..25a9f6b9c 100644
--- a/glib/glist.c
+++ b/glib/glist.c
@@ -367,6 +367,50 @@ g_list_insert (GList    *list,
   return list;
 }
 
+GList *
+g_list_insert_before_link (GList *list,
+                           GList *sibling,
+                           GList *link_)
+{
+  g_return_val_if_fail (link_ != NULL, list);
+
+  if (!list)
+    {
+      g_return_val_if_fail (sibling == NULL, list);
+      return link_;
+    }
+  else if (sibling)
+    {
+      link_->prev = sibling->prev;
+      link_->next = sibling;
+      sibling->prev = link_;
+      if (link_->prev)
+        {
+          link_->prev->next = link_;
+          return list;
+        }
+      else
+        {
+          g_return_val_if_fail (sibling == list, link_);
+          return link_;
+        }
+    }
+  else
+    {
+      GList *last;
+
+      last = list;
+      while (last->next)
+        last = last->next;
+
+      last->next = link_;
+      last->next->prev = last;
+      last->next->next = NULL;
+
+      return list;
+    }
+}
+
 /**
  * g_list_insert_before:
  * @list: a pointer to a #GList, this must point to the top of the list
diff --git a/glib/glist.h b/glib/glist.h
index af35cd52c..35f9cf71e 100644
--- a/glib/glist.h
+++ b/glib/glist.h
@@ -78,6 +78,10 @@ GLIB_AVAILABLE_IN_ALL
 GList*   g_list_insert_before           (GList            *list,
                                         GList            *sibling,
                                         gpointer          data) G_GNUC_WARN_UNUSED_RESULT;
+GLIB_AVAILABLE_IN_2_60
+GList*   g_list_insert_before_link      (GList            *list,
+                                        GList            *sibling,
+                                        GList            *link_) G_GNUC_WARN_UNUSED_RESULT;
 GLIB_AVAILABLE_IN_ALL
 GList*   g_list_concat                  (GList            *list1,
                                         GList            *list2) G_GNUC_WARN_UNUSED_RESULT;
diff --git a/glib/gqueue.c b/glib/gqueue.c
index 9f34790b9..4eec9ed4b 100644
--- a/glib/gqueue.c
+++ b/glib/gqueue.c
@@ -1025,6 +1025,29 @@ g_queue_insert_before (GQueue   *queue,
     }
 }
 
+void
+g_queue_insert_before_link (GQueue   *queue,
+                            GList    *sibling,
+                            GList    *link_)
+{
+  g_return_if_fail (queue != NULL);
+  g_return_if_fail (link_ != 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 +1075,20 @@ g_queue_insert_after (GQueue   *queue,
     g_queue_insert_before (queue, sibling->next, data);
 }
 
+void
+g_queue_insert_after_link (GQueue   *queue,
+                           GList    *sibling,
+                           GList    *link_)
+{
+  g_return_if_fail (queue != NULL);
+  g_return_if_fail (link_ != 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/list.c b/glib/tests/list.c
index 1b5d6cadf..4d32dc17d 100644
--- a/glib/tests/list.c
+++ b/glib/tests/list.c
@@ -548,6 +548,56 @@ test_double_free (void)
   g_test_trap_assert_stderr ("*corrupted double-linked list detected*");
 }
 
+static void
+test_list_insert_before_link (void)
+{
+  GList a = {0};
+  GList b = {0};
+  GList c = {0};
+  GList d = {0};
+  GList *list;
+
+  list = g_list_insert_before_link (NULL, NULL, &a);
+  g_assert_nonnull (list);
+  g_assert_true (list == &a);
+  g_assert_null (a.prev);
+  g_assert_null (a.next);
+  g_assert_cmpint (g_list_length (list), ==, 1);
+
+  list = g_list_insert_before_link (list, &a, &b);
+  g_assert_nonnull (list);
+  g_assert_true (list == &b);
+  g_assert_null (b.prev);
+  g_assert_true (b.next == &a);
+  g_assert_true (a.prev == &b);
+  g_assert_null (a.next);
+  g_assert_cmpint (g_list_length (list), ==, 2);
+
+  list = g_list_insert_before_link (list, &a, &c);
+  g_assert_nonnull (list);
+  g_assert_true (list == &b);
+  g_assert_null (b.prev);
+  g_assert_true (b.next == &c);
+  g_assert_true (c.next == &a);
+  g_assert_true (c.prev == &b);
+  g_assert_true (a.prev == &c);
+  g_assert_null (a.next);
+  g_assert_cmpint (g_list_length (list), ==, 3);
+
+  list = g_list_insert_before_link (list, &b, &d);
+  g_assert_nonnull (list);
+  g_assert_true (list == &d);
+  g_assert_null (d.prev);
+  g_assert_true (b.prev == &d);
+  g_assert_true (c.prev == &b);
+  g_assert_true (a.prev == &c);
+  g_assert_true (d.next == &b);
+  g_assert_true (b.next == &c);
+  g_assert_true (c.next == &a);
+  g_assert_null (a.next);
+  g_assert_cmpint (g_list_length (list), ==, 4);
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -562,6 +612,7 @@ main (int argc, char *argv[])
   g_test_add_func ("/list/sort", test_list_sort);
   g_test_add_func ("/list/sort-with-data", test_list_sort_with_data);
   g_test_add_func ("/list/sort/stable", test_list_sort_stable);
+  g_test_add_func ("/list/insert-before-link", test_list_insert_before_link);
   g_test_add_func ("/list/insert-sorted", test_list_insert_sorted);
   g_test_add_func ("/list/insert-sorted-with-data", test_list_insert_sorted_with_data);
   g_test_add_func ("/list/reverse", test_list_reverse);