[glib/wip/chergert/garraylist] arraylist: add g_array_list_prepend()

[Christian Hergert <chergert src gnome org>]

commit 87dee43c428c20a54ad9ad7cfd46ca18ef656254
Author: Christian Hergert <christian hergert me>
Date:   Sun Sep 13 03:52:59 2015 -0700

    arraylist: add g_array_list_prepend()
    
    Not the most optimized way to do this, but we need it to make incremental
    porting easier. We can also look at changing directions based on the
    common access pattern (since we have O(1) access to head and tail).

 glib/garraylist.c      |   79 ++++++++++++++++++++++++++++++++++++++++--------
 glib/garraylist.h      |    4 ++
 glib/tests/arraylist.c |    4 ++
 3 files changed, 74 insertions(+), 13 deletions(-)
---
diff --git a/glib/garraylist.c b/glib/garraylist.c
index a084622..945666f 100644
--- a/glib/garraylist.c
+++ b/glib/garraylist.c
@@ -183,12 +183,31 @@ g_array_list_index (GArrayList *self,
   return items [index].data;
 }
 
+static inline void
+_g_array_list_update_pointers (GList *array,
+                               gsize  array_len)
+{
+  gsize i;
+
+  if (array_len > 0)
+    array [0].next = &array [1];
+
+  for (i = 1; i < (array_len - 1); i++)
+    {
+      array [i].prev = &array [i - 1];
+      array [i].next = &array [i + 1];
+    }
+
+  if (array_len > 1)
+    array [array_len- 1].prev = &array [array_len - 1 - 1];
+}
+
 static void
-_g_array_list_grow (GArrayList *self)
+_g_array_list_grow (GArrayList *self,
+                    gboolean    update_pointers)
 {
   GArrayListAlloc *alloc = (GArrayListAlloc *)self;
   gpointer old_items;
-  gsize i;
 
   DEBUG_ASSERT (self != NULL);
   DEBUG_ASSERT (alloc->mode == MODE_ALLOC);
@@ -203,17 +222,10 @@ _g_array_list_grow (GArrayList *self)
   if (G_LIKELY (old_items == alloc->items))
     return;
 
-  if (alloc->len > 0)
-    alloc->items [0].next = &alloc->items [1];
-
-  for (i = 1; i < (alloc->len - 1); i++)
-    {
-      alloc->items [i].prev = &alloc->items [i-1];
-      alloc->items [i].next = &alloc->items [i+1];
-    }
+  if (!update_pointers)
+    return;
 
-  if (alloc->len > 1)
-    alloc->items [alloc->len - 1].prev = &alloc->items [alloc->len - 1 - 1];
+  _g_array_list_update_pointers (alloc->items, alloc->len);
 }
 
 static void
@@ -301,7 +313,7 @@ g_array_list_add (GArrayList *self,
   DEBUG_ASSERT (any->mode == MODE_ALLOC);
 
   if (G_UNLIKELY (alloc->len == alloc->items_len))
-    _g_array_list_grow (self);
+    _g_array_list_grow (self, TRUE);
 
   item = &alloc->items [alloc->len];
   prev = (alloc->len > 0) ? &alloc->items [alloc->len - 1] : NULL;
@@ -321,6 +333,47 @@ g_array_list_add (GArrayList *self,
 }
 
 void
+g_array_list_prepend (GArrayList *self,
+                      gpointer    data)
+{
+  GArrayListAny *any = (GArrayListAny *)self;
+  GArrayListEmbed *embed = (GArrayListEmbed *)self;
+  GArrayListAlloc *alloc = (GArrayListAlloc *)self;
+
+  g_return_if_fail (self != NULL);
+
+  if (G_LIKELY (any->mode == MODE_EMBED))
+    {
+      if (G_LIKELY (embed->len < G_N_ELEMENTS (embed->items)))
+        {
+          memmove (&embed->items [1], &embed->items [0], sizeof (GList) * embed->len);
+          embed->items [0].prev = NULL;
+          embed->items [0].next = &embed->items [1];
+          embed->items [0].data = data;
+          embed->len++;
+          return;
+        }
+
+      _g_array_list_transition (self);
+    }
+
+  DEBUG_ASSERT (any->mode == MODE_ALLOC);
+
+  if (G_UNLIKELY (alloc->len == alloc->items_len))
+    _g_array_list_grow (self, FALSE);
+
+  memmove (&alloc->items [1], &alloc->items [0], sizeof (GList) * alloc->len);
+
+  alloc->items [0].data = data;
+
+  _g_array_list_update_pointers (alloc->items, alloc->len);
+
+  DEBUG_ASSERT (alloc->len <= alloc->items_len);
+  DEBUG_ASSERT (alloc->len > 0);
+  DEBUG_ASSERT (alloc->items [0].data == data);
+}
+
+void
 g_array_list_remove_index (GArrayList *self,
                            guint       index)
 {
diff --git a/glib/garraylist.h b/glib/garraylist.h
index 30fb108..cd2b5f6 100644
--- a/glib/garraylist.h
+++ b/glib/garraylist.h
@@ -74,6 +74,10 @@ void         g_array_list_destroy      (GArrayList     *list);
 GLIB_AVAILABLE_IN_2_46
 const GList *g_array_list_last_link    (GArrayList     *list);
 
+GLIB_AVAILABLE_IN_2_46
+void         g_array_list_prepend      (GArrayList     *list,
+                                        gpointer        data);
+
 #define g_array_list_first(list) (((list)->len == 0) ? NULL : g_array_list_index((list),0))
 #define g_array_list_last(list) (((list)->len == 0) ? NULL : g_array_list_index((list),(list)->len-1))
 
diff --git a/glib/tests/arraylist.c b/glib/tests/arraylist.c
index a716dc6..328088d 100644
--- a/glib/tests/arraylist.c
+++ b/glib/tests/arraylist.c
@@ -73,6 +73,10 @@ test_basic (GArrayList *al)
 
   g_assert_cmpint (al->len, ==, 500);
   g_assert_cmpint (test_basic_counter, ==, 500);
+
+  g_array_list_prepend (al, GSIZE_TO_POINTER (191919));
+  g_assert_cmpint (GPOINTER_TO_SIZE (g_array_list_index (al, 0)), ==, 191919);
+
   g_array_list_destroy (al);
   g_assert_cmpint (test_basic_counter, ==, 1000);