[glib/wip/chergert/insertbeforelink: 1/3] list: add g_list_insert_before_link()

[Christian Hergert <chergert src gnome org>]

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

    list: add g_list_insert_before_link()
    
    This adds a new insertion helper using a pre-allocated link which may be
    advantagous in some situations such as statically linked GList elements.

 docs/reference/glib/glib-sections.txt |  1 +
 glib/glist.c                          | 58 ++++++++++++++++++++++++++++++
 glib/glist.h                          |  4 +++
 glib/tests/list.c                     | 67 +++++++++++++++++++++++++++++++++++
 4 files changed, 130 insertions(+)
---
diff --git a/docs/reference/glib/glib-sections.txt b/docs/reference/glib/glib-sections.txt
index d847d21e1..10ec35f75 100644
--- a/docs/reference/glib/glib-sections.txt
+++ b/docs/reference/glib/glib-sections.txt
@@ -2268,6 +2268,7 @@ g_list_append
 g_list_prepend
 g_list_insert
 g_list_insert_before
+g_list_insert_before_link
 g_list_insert_sorted
 g_list_remove
 g_list_remove_link
diff --git a/glib/glist.c b/glib/glist.c
index 51adeb058..c672e4349 100644
--- a/glib/glist.c
+++ b/glib/glist.c
@@ -367,6 +367,64 @@ g_list_insert (GList    *list,
   return list;
 }
 
+/**
+ * g_list_insert_before_link:
+ * @list: a pointer to a #GList, this must point to the top of the list
+ * @sibling: (nullable): the list element before which the new element
+ *     is inserted or %NULL to insert at the end of the list
+ * @link_: the list element to be added, which must not be part of
+ *     any other list
+ *
+ * Inserts @link_ into the list before the given position.
+ *
+ * Returns: the (possibly changed) start of the #GList
+ *
+ * Since: 2.60
+ */
+GList *
+g_list_insert_before_link (GList *list,
+                           GList *sibling,
+                           GList *link_)
+{
+  g_return_val_if_fail (link_ != NULL, list);
+  g_return_val_if_fail (link_->prev == NULL, list);
+  g_return_val_if_fail (link_->next == NULL, list);
+
+  if (list == NULL)
+    {
+      g_return_val_if_fail (sibling == NULL, list);
+      return link_;
+    }
+  else if (sibling != NULL)
+    {
+      link_->prev = sibling->prev;
+      link_->next = sibling;
+      sibling->prev = link_;
+      if (link_->prev != NULL)
+        {
+          link_->prev->next = link_;
+          return list;
+        }
+      else
+        {
+          g_return_val_if_fail (sibling == list, link_);
+          return link_;
+        }
+    }
+  else
+    {
+      GList *last;
+
+      for (last = list; last->next != NULL; 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/tests/list.c b/glib/tests/list.c
index 1b5d6cadf..0adb1bbb1 100644
--- a/glib/tests/list.c
+++ b/glib/tests/list.c
@@ -548,6 +548,72 @@ 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 e = {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);
+
+  list = g_list_insert_before_link (list, NULL, &e);
+  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_true (a.next == &e);
+  g_assert_true (e.prev == &a);
+  g_assert_null (e.next);
+  g_assert_cmpint (g_list_length (list), ==, 5);
+}
+
 int
 main (int argc, char *argv[])
 {
@@ -562,6 +628,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);