diff options
author | Christian Hergert <christian@hergert.me> | 2015-09-13 03:52:59 -0700 |
---|---|---|
committer | Christian Hergert <christian@hergert.me> | 2015-09-13 03:52:59 -0700 |
commit | 87dee43c428c20a54ad9ad7cfd46ca18ef656254 (patch) | |
tree | 4beb2cdfcd4c52755a39714c3112f0f205c7f7c1 | |
parent | 2b1e7de62878782b376afb077e41dee54edd8975 (diff) | |
download | glib-87dee43c428c20a54ad9ad7cfd46ca18ef656254.tar.gz |
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).
-rw-r--r-- | glib/garraylist.c | 79 | ||||
-rw-r--r-- | glib/garraylist.h | 4 | ||||
-rw-r--r-- | glib/tests/arraylist.c | 4 |
3 files changed, 74 insertions, 13 deletions
diff --git a/glib/garraylist.c b/glib/garraylist.c index a08462289..945666f8c 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 30fb108c1..cd2b5f6c6 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 a716dc6a6..328088d07 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); |