diff options
| -rw-r--r-- | glib/Makefile.am | 2 | ||||
| -rw-r--r-- | glib/gheap.c | 364 | ||||
| -rw-r--r-- | glib/gheap.h | 59 | ||||
| -rw-r--r-- | glib/glib.h | 1 | ||||
| -rw-r--r-- | glib/tests/.gitignore | 1 | ||||
| -rw-r--r-- | glib/tests/Makefile.am | 1 | ||||
| -rw-r--r-- | glib/tests/gheap.c | 176 |
7 files changed, 604 insertions, 0 deletions
diff --git a/glib/Makefile.am b/glib/Makefile.am index d9892f6c0..f8c9dd1f7 100644 --- a/glib/Makefile.am +++ b/glib/Makefile.am @@ -127,6 +127,7 @@ libglib_2_0_la_SOURCES = \ gfileutils.c \ ggettext.c \ ghash.c \ + gheap.c \ ghmac.c \ ghook.c \ ghostutils.c \ @@ -263,6 +264,7 @@ glibsubinclude_HEADERS = \ gfileutils.h \ ggettext.h \ ghash.h \ + gheap.h \ ghmac.h \ ghook.h \ ghostutils.h \ diff --git a/glib/gheap.c b/glib/gheap.c new file mode 100644 index 000000000..852dd4497 --- /dev/null +++ b/glib/gheap.c @@ -0,0 +1,364 @@ +/* gheap.c + * + * Copyright (C) 2014 Christian Hergert <christian@hergert.me> + * + * This file is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This file is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <string.h> + +#include "gheap.h" + +/** + * SECTION:gheap + * @title: Heaps + * @short_description: efficient priority queues using min/max heaps + * + * Heaps are similar to a partially sorted tree but implemented as an + * array. They allow for efficient O(1) lookup of the highest priority + * item as it will always be the first item of the array. + * + * To create a new heap use g_heap_new(). + * + * To add items to the heap, use g_heap_insert_val() or + * g_heap_insert_vals() to insert in bulk. + * + * To access an item in the heap, use g_heap_index(). + * + * To remove an arbitrary item from the heap, use g_heap_extract_index(). + * + * To remove the highest priority item in the heap, use g_heap_extract(). + * + * To free a heap, use g_heap_unref(). + * + * Here is an example that stores integers in a #GHeap: + * |[<!-- language="C" --> + * static int + * cmpint (gconstpointer a, + * gconstpointer b) + * { + * return *(const gint *)a - *(const gint *)b; + * } + * + * int + * main (gint argc, + * gchar *argv[]) + * { + * GHeap *heap; + * gint i; + * gint v; + * + * heap = g_heap_new (sizeof (gint), cmpint); + * + * for (i = 0; i < 10000; i++) + * g_heap_insert_val (heap, i); + * for (i = 0; i < 10000; i++) + * g_heap_extract (heap, &v); + * + * g_heap_unref (heap); + * } + * ]| + */ + +#define MIN_HEAP_SIZE 16 + +/* + * Based upon Mastering Algorithms in C by Kyle Loudon. + * Section 10 - Heaps and Priority Queues. + */ + +typedef struct _GHeapReal GHeapReal; + +struct _GHeapReal +{ + gchar *data; + gsize len; + volatile gint ref_count; + guint element_size; + gsize allocated_len; + GCompareFunc compare; + gchar tmp[0]; +}; + +#define heap_parent(npos) (((npos)-1)/2) +#define heap_left(npos) (((npos)*2)+1) +#define heap_right(npos) (((npos)*2)+2) +#define heap_index(h,i) ((h)->data + (i * (h)->element_size)) +#define heap_compare(h,a,b) ((h)->compare(heap_index(h,a), heap_index(h,b))) +#define heap_swap(h,a,b) \ + G_STMT_START { \ + memcpy ((h)->tmp, heap_index (h, a), (h)->element_size); \ + memcpy (heap_index (h, a), heap_index (h, b), (h)->element_size); \ + memcpy (heap_index (h, b), (h)->tmp, (h)->element_size); \ + } G_STMT_END + +GHeap * +g_heap_new (guint element_size, + GCompareFunc compare_func) +{ + GHeapReal *real; + + g_return_val_if_fail (element_size, NULL); + g_return_val_if_fail (compare_func, NULL); + + real = g_malloc_n (1, sizeof (GHeapReal) + element_size); + real->data = NULL; + real->len = 0; + real->ref_count = 1; + real->element_size = element_size; + real->allocated_len = 0; + real->compare = compare_func; + + return (GHeap *)real; +} + +GHeap * +g_heap_ref (GHeap *heap) +{ + GHeapReal *real = (GHeapReal *)heap; + + g_return_val_if_fail (heap, NULL); + g_return_val_if_fail (real->ref_count, NULL); + + g_atomic_int_inc (&real->ref_count); + + return heap; +} + +static void +g_heap_real_free (GHeapReal *real) +{ + g_assert (real); + g_assert_cmpint (real->ref_count, ==, 0); + + g_free (real->data); + g_free (real); +} + +void +g_heap_unref (GHeap *heap) +{ + GHeapReal *real = (GHeapReal *)heap; + + g_return_if_fail (heap); + g_return_if_fail (real->ref_count); + + if (g_atomic_int_dec_and_test (&real->ref_count)) { + g_heap_real_free (real); + } +} + +static void +g_heap_real_grow (GHeapReal *real) +{ + g_assert (real); + g_assert_cmpint (real->allocated_len, <, G_MAXSIZE / 2); + + real->allocated_len = MAX (MIN_HEAP_SIZE, (real->allocated_len * 2)); + real->data = g_realloc_n (real->data, + real->allocated_len, + real->element_size); +} + +static void +g_heap_real_shrink (GHeapReal *real) +{ + g_assert (real); + g_assert ((real->allocated_len / 2) >= real->len); + + real->allocated_len = MAX (MIN_HEAP_SIZE, real->allocated_len / 2); + real->data = g_realloc_n (real->data, + real->allocated_len, + real->element_size); +} + +static void +g_heap_real_insert_val (GHeapReal *real, + gconstpointer data) +{ + gint ipos; + gint ppos; + + g_assert (real); + g_assert (data); + + if (G_UNLIKELY (real->len == real->allocated_len)) { + g_heap_real_grow (real); + } + + memcpy (real->data + (real->element_size * real->len), data, + real->element_size); + + ipos = real->len; + ppos = heap_parent (ipos); + + while ((ipos > 0) && (heap_compare (real, ppos, ipos) < 0)) { + heap_swap (real, ppos, ipos); + ipos = ppos; + ppos = heap_parent (ipos); + } + + real->len++; +} + +void +g_heap_insert_vals (GHeap *heap, + gconstpointer data, + guint len) +{ + GHeapReal *real = (GHeapReal *)heap; + const gchar *ptr = data; + guint i; + + g_return_if_fail (heap); + g_return_if_fail (data); + g_return_if_fail (len); + + for (i = 0; i < len; i++, ptr += real->element_size) { + g_heap_real_insert_val (real, ptr); + } +} + +gboolean +g_heap_extract (GHeap *heap, + gpointer result) +{ + GHeapReal *real = (GHeapReal *)heap; + gboolean ret; + gint ipos; + gint lpos; + gint rpos; + gint mpos; + + g_return_val_if_fail (heap, FALSE); + + ret = (real->len > 0); + + if (ret) { + if (result) { + memcpy (result, heap_index (real, 0), real->element_size); + } + + if (real->len && --real->len) { + memmove (real->data, heap_index (real, real->len), real->element_size); + + ipos = 0; + + for (;;) { + lpos = heap_left (ipos); + rpos = heap_right (ipos); + + if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0)) { + mpos = lpos; + } else { + mpos = ipos; + } + + if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0)) { + mpos = rpos; + } + + if (mpos == ipos) { + break; + } + + heap_swap (real, mpos, ipos); + + ipos = mpos; + } + } + } + + if ((real->len >= MIN_HEAP_SIZE) && + (real->allocated_len / 2) >= real->len) { + g_heap_real_shrink (real); + } + + return ret; +} + +gboolean +g_heap_extract_index (GHeap *heap, + guint index_, + gpointer result) +{ + GHeapReal *real = (GHeapReal *)heap; + gboolean ret; + gint ipos; + gint lpos; + gint mpos; + gint ppos; + gint rpos; + + g_return_val_if_fail (heap, FALSE); + + ret = (real->len > 0); + + if (real->len) { + if (result) { + memcpy (result, heap_index (real, 0), real->element_size); + } + + real->len--; + + if (real->len && index_ != real->len) { + memcpy (heap_index (real, index_), + heap_index (real, real->len), + real->element_size); + + ipos = index_; + ppos = heap_parent (ipos); + + while (heap_compare (real, ipos, ppos) > 0) { + heap_swap (real, ipos, ppos); + ipos = ppos; + ppos = heap_parent (ppos); + } + + if (ipos == index_) { + for (;;) { + lpos = heap_left (ipos); + rpos = heap_right (ipos); + + if ((lpos < real->len) && (heap_compare (real, lpos, ipos) > 0)) { + mpos = lpos; + } else { + mpos = ipos; + } + + if ((rpos < real->len) && (heap_compare (real, rpos, mpos) > 0)) { + mpos = rpos; + } + + if (mpos == ipos) { + break; + } + + heap_swap (real, mpos, ipos); + + ipos = mpos; + } + } + } + } + + if ((real->len >= MIN_HEAP_SIZE) && + (real->allocated_len / 2) >= real->len) { + g_heap_real_shrink (real); + } + + return ret; +} diff --git a/glib/gheap.h b/glib/gheap.h new file mode 100644 index 000000000..b964d68c4 --- /dev/null +++ b/glib/gheap.h @@ -0,0 +1,59 @@ +/* gheap.h + * + * Copyright (C) 2014 Christian Hergert <christian@hergert.me> + * + * This file is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This file is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#ifndef G_HEAP_H +#define G_HEAP_H + +#include <glib.h> + +G_BEGIN_DECLS + +#define g_heap_insert_val(h,v) g_heap_insert_vals(h,&(v),1) +#define g_heap_index(h,t,i) (((t*)(h)->data)[i]) +#define g_heap_peek(h,t) g_heap_index(h,t,0) + +typedef struct _GHeap GHeap; + +struct _GHeap +{ + gchar *data; + guint len; +}; + +GLIB_AVAILABLE_IN_2_42 +GHeap *g_heap_new (guint element_size, + GCompareFunc compare_func); +GLIB_AVAILABLE_IN_2_42 +GHeap *g_heap_ref (GHeap *heap); +GLIB_AVAILABLE_IN_2_42 +void g_heap_unref (GHeap *heap); +GLIB_AVAILABLE_IN_2_42 +void g_heap_insert_vals (GHeap *heap, + gconstpointer data, + guint len); +GLIB_AVAILABLE_IN_2_42 +gboolean g_heap_extract (GHeap *heap, + gpointer result); +GLIB_AVAILABLE_IN_2_42 +gboolean g_heap_extract_index (GHeap *heap, + guint index_, + gpointer result); + +G_END_DECLS + +#endif /* G_HEAP_H */ diff --git a/glib/glib.h b/glib/glib.h index c7fc999b2..a5d5eb6d5 100644 --- a/glib/glib.h +++ b/glib/glib.h @@ -48,6 +48,7 @@ #include <glib/gfileutils.h> #include <glib/ggettext.h> #include <glib/ghash.h> +#include <glib/gheap.h> #include <glib/ghmac.h> #include <glib/ghook.h> #include <glib/ghostutils.h> diff --git a/glib/tests/.gitignore b/glib/tests/.gitignore index 33ef15eed..20ca63c23 100644 --- a/glib/tests/.gitignore +++ b/glib/tests/.gitignore @@ -25,6 +25,7 @@ gvariant gwakeup gwakeup-fallback hash +gheap hmac hook hostutils diff --git a/glib/tests/Makefile.am b/glib/tests/Makefile.am index 445040ade..2311d346b 100644 --- a/glib/tests/Makefile.am +++ b/glib/tests/Makefile.am @@ -48,6 +48,7 @@ test_programs = \ error \ fileutils \ gdatetime \ + gheap \ gvariant \ hash \ hmac \ diff --git a/glib/tests/gheap.c b/glib/tests/gheap.c new file mode 100644 index 000000000..9b4833909 --- /dev/null +++ b/glib/tests/gheap.c @@ -0,0 +1,176 @@ +/* gheap.c + * + * Copyright (C) 2014 Christian Hergert <christian@hergert.me> + * + * This file is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This file is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include "config.h" + +#include <glib.h> + +typedef struct +{ + gint64 size; + gpointer pointer; +} Tuple; + +static int +cmpint_rev (gconstpointer a, + gconstpointer b) +{ + return *(const gint *)b - *(const gint *)a; +} + +static int +cmpptr_rev (gconstpointer a, + gconstpointer b) +{ + return GPOINTER_TO_SIZE(*(gpointer *)b) - GPOINTER_TO_SIZE (*(gpointer *)a); +} + +static int +cmptuple_rev (gconstpointer a, + gconstpointer b) +{ + Tuple *at = (Tuple *)a; + Tuple *bt = (Tuple *)b; + + return bt->size - at->size; +} + +static void +test_GHeap_insert_val_int (void) +{ + GHeap *heap; + gint i; + + heap = g_heap_new (sizeof (gint), cmpint_rev); + + for (i = 0; i < 100000; i++) { + g_heap_insert_val (heap, i); + g_assert_cmpint (heap->len, ==, i + 1); + } + + for (i = 0; i < 100000; i++) { + g_assert_cmpint (heap->len, ==, 100000 - i); + g_assert_cmpint (g_heap_peek (heap, gint), ==, i); + g_heap_extract (heap, NULL); + } + + g_heap_unref (heap); +} + +static void +test_GHeap_insert_val_ptr (void) +{ + gconstpointer ptr; + GHeap *heap; + gint i; + + heap = g_heap_new (sizeof (gpointer), cmpptr_rev); + + for (i = 0; i < 100000; i++) { + ptr = GINT_TO_POINTER (i); + g_heap_insert_val (heap, ptr); + g_assert_cmpint (heap->len, ==, i + 1); + } + + for (i = 0; i < 100000; i++) { + g_assert_cmpint (heap->len, ==, 100000 - i); + g_assert (g_heap_peek (heap, gpointer) == GINT_TO_POINTER (i)); + g_heap_extract (heap, NULL); + } + + g_heap_unref (heap); +} + +static void +test_GHeap_insert_val_tuple (void) +{ + Tuple t; + GHeap *heap; + gint i; + + heap = g_heap_new (sizeof (Tuple), cmptuple_rev); + + for (i = 0; i < 100000; i++) { + t.pointer = GINT_TO_POINTER (i); + t.size = i; + g_heap_insert_val (heap, t); + g_assert_cmpint (heap->len, ==, i + 1); + } + + for (i = 0; i < 100000; i++) { + g_assert_cmpint (heap->len, ==, 100000 - i); + g_assert (g_heap_peek (heap, Tuple).size == i); + g_assert (g_heap_peek (heap, Tuple).pointer == GINT_TO_POINTER (i)); + g_heap_extract (heap, NULL); + } + + g_heap_unref (heap); +} + +static void +test_GHeap_extract_int (void) +{ + GHeap *heap; + gint removed[5]; + gint i; + gint v; + + heap = g_heap_new (sizeof (gint), cmpint_rev); + + for (i = 0; i < 100000; i++) { + g_heap_insert_val (heap, i); + } + + removed [0] = g_heap_index (heap, gint, 1578); g_heap_extract_index (heap, 1578, NULL); + removed [1] = g_heap_index (heap, gint, 2289); g_heap_extract_index (heap, 2289, NULL); + removed [2] = g_heap_index (heap, gint, 3312); g_heap_extract_index (heap, 3312, NULL); + removed [3] = g_heap_index (heap, gint, 78901); g_heap_extract_index (heap, 78901, NULL); + removed [4] = g_heap_index (heap, gint, 99000); g_heap_extract_index (heap, 99000, NULL); + + for (i = 0; i < 100000; i++) { + if (g_heap_peek (heap, gint) != i) { + g_assert ((i == removed[0]) || + (i == removed[1]) || + (i == removed[2]) || + (i == removed[3]) || + (i == removed[4])); + } else { + g_heap_extract (heap, &v); + g_assert_cmpint (v, ==, i); + } + } + + g_assert_cmpint (heap->len, ==, 0); + + g_heap_unref (heap); +} + +int +main (gint argc, + gchar *argv[]) +{ + g_test_init (&argc, &argv, NULL); + g_test_bug_base ("http://bugzilla.gnome.org/"); + + g_test_add_func ("/GHeap/insert_and_extract<gint>", test_GHeap_insert_val_int); + g_test_add_func ("/GHeap/insert_and_extract<gpointer>", test_GHeap_insert_val_ptr); + g_test_add_func ("/GHeap/insert_and_extract<Tuple>", test_GHeap_insert_val_tuple); + g_test_add_func ("/GHeap/extract_index<int>", test_GHeap_extract_int); + + return g_test_run (); +} |