[gnome-builder] egg-heap: add a min heap to use in various sources
- From: Christian Hergert <chergert src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [gnome-builder] egg-heap: add a min heap to use in various sources
- Date: Wed, 13 May 2015 00:13:52 +0000 (UTC)
commit b160c5d29b5e98f99ff21c984e69a266de1482d8
Author: Christian Hergert <christian hergert me>
Date: Tue May 12 17:12:12 2015 -0700
egg-heap: add a min heap to use in various sources
Going to use this for EggTaskCache. I'd rather manage the minheap than
deal with the memmoves on a GPtrArray once we get larger data caching.
Might change later though depending on how I feel about
g_source_set_ready_time() and maintaining our eviction timeouts in a
gptrarray.
contrib/egg/Makefile.am | 2 +
contrib/egg/egg-heap.c | 361 +++++++++++++++++++++++++++++++++++++++++++++++
contrib/egg/egg-heap.h | 53 +++++++
tests/Makefile.am | 7 +
tests/test-egg-heap.c | 173 ++++++++++++++++++++++
5 files changed, 596 insertions(+), 0 deletions(-)
---
diff --git a/contrib/egg/Makefile.am b/contrib/egg/Makefile.am
index a9839d5..562c65e 100644
--- a/contrib/egg/Makefile.am
+++ b/contrib/egg/Makefile.am
@@ -5,6 +5,8 @@ libegg_la_SOURCES = \
egg-binding-set.h \
egg-counter.c \
egg-counter.h \
+ egg-heap.c \
+ egg-heap.h \
egg-search-bar.c \
egg-search-bar.h \
egg-settings-sandwich.c \
diff --git a/contrib/egg/egg-heap.c b/contrib/egg/egg-heap.c
new file mode 100644
index 0000000..0dde013
--- /dev/null
+++ b/contrib/egg/egg-heap.c
@@ -0,0 +1,361 @@
+/* egg-heap.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/>.
+ */
+
+#define G_LOG_DOMAIN "egg-heap"
+
+#include <string.h>
+
+#include "egg-heap.h"
+
+/**
+ * SECTION:egg-heap
+ * @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 egg_heap_new().
+ *
+ * To add items to the heap, use egg_heap_insert_val() or
+ * egg_heap_insert_vals() to insert in bulk.
+ *
+ * To access an item in the heap, use egg_heap_index().
+ *
+ * To remove an arbitrary item from the heap, use egg_heap_extract_index().
+ *
+ * To remove the highest priority item in the heap, use egg_heap_extract().
+ *
+ * To free a heap, use egg_heap_unref().
+ *
+ * Here is an example that stores integers in a #EggHeap:
+ * |[<!-- language="C" -->
+ * static int
+ * cmpint (gconstpointer a,
+ * gconstpointer b)
+ * {
+ * return *(const gint *)a - *(const gint *)b;
+ * }
+ *
+ * int
+ * main (gint argc,
+ * gchar *argv[])
+ * {
+ * EggHeap *heap;
+ * gint i;
+ * gint v;
+ *
+ * heap = egg_heap_new (sizeof (gint), cmpint);
+ *
+ * for (i = 0; i < 10000; i++)
+ * egg_heap_insert_val (heap, i);
+ * for (i = 0; i < 10000; i++)
+ * egg_heap_extract (heap, &v);
+ *
+ * egg_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 _EggHeapReal EggHeapReal;
+
+struct _EggHeapReal
+{
+ 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
+
+EggHeap *
+egg_heap_new (guint element_size,
+ GCompareFunc compare_func)
+{
+ EggHeapReal *real;
+
+ g_return_val_if_fail (element_size, NULL);
+ g_return_val_if_fail (compare_func, NULL);
+
+ real = g_malloc_n (1, sizeof (EggHeapReal) + 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 (EggHeap *)real;
+}
+
+EggHeap *
+egg_heap_ref (EggHeap *heap)
+{
+ EggHeapReal *real = (EggHeapReal *)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
+egg_heap_real_free (EggHeapReal *real)
+{
+ g_assert (real);
+ g_assert_cmpint (real->ref_count, ==, 0);
+
+ g_free (real->data);
+ g_free (real);
+}
+
+void
+egg_heap_unref (EggHeap *heap)
+{
+ EggHeapReal *real = (EggHeapReal *)heap;
+
+ g_return_if_fail (heap);
+ g_return_if_fail (real->ref_count);
+
+ if (g_atomic_int_dec_and_test (&real->ref_count))
+ egg_heap_real_free (real);
+}
+
+static void
+egg_heap_real_grow (EggHeapReal *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
+egg_heap_real_shrink (EggHeapReal *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
+egg_heap_real_insert_val (EggHeapReal *real,
+ gconstpointer data)
+{
+ gint ipos;
+ gint ppos;
+
+ g_assert (real);
+ g_assert (data);
+
+ if (G_UNLIKELY (real->len == real->allocated_len))
+ egg_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
+egg_heap_insert_vals (EggHeap *heap,
+ gconstpointer data,
+ guint len)
+{
+ EggHeapReal *real = (EggHeapReal *)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)
+ egg_heap_real_insert_val (real, ptr);
+}
+
+gboolean
+egg_heap_extract (EggHeap *heap,
+ gpointer result)
+{
+ EggHeapReal *real = (EggHeapReal *)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;
+
+ while (TRUE)
+ {
+ 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)
+ egg_heap_real_shrink (real);
+
+ return ret;
+}
+
+gboolean
+egg_heap_extract_index (EggHeap *heap,
+ guint index_,
+ gpointer result)
+{
+ EggHeapReal *real = (EggHeapReal *)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_)
+ {
+ while (TRUE)
+ {
+ 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)
+ egg_heap_real_shrink (real);
+
+ return ret;
+}
diff --git a/contrib/egg/egg-heap.h b/contrib/egg/egg-heap.h
new file mode 100644
index 0000000..d9ae3b6
--- /dev/null
+++ b/contrib/egg/egg-heap.h
@@ -0,0 +1,53 @@
+/* egg-heap.h
+ *
+ * Copyright (C) 2014-2015 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 EGG_HEAP_H
+#define EGG_HEAP_H
+
+#include <glib.h>
+
+G_BEGIN_DECLS
+
+#define egg_heap_insert_val(h,v) egg_heap_insert_vals(h,&(v),1)
+#define egg_heap_index(h,t,i) (((t*)(h)->data)[i])
+#define egg_heap_peek(h,t) egg_heap_index(h,t,0)
+
+typedef struct _EggHeap EggHeap;
+
+struct _EggHeap
+{
+ gchar *data;
+ guint len;
+};
+
+EggHeap *egg_heap_new (guint element_size,
+ GCompareFunc compare_func);
+EggHeap *egg_heap_ref (EggHeap *heap);
+void egg_heap_unref (EggHeap *heap);
+void egg_heap_insert_vals (EggHeap *heap,
+ gconstpointer data,
+ guint len);
+gboolean egg_heap_extract (EggHeap *heap,
+ gpointer result);
+gboolean egg_heap_extract_index (EggHeap *heap,
+ guint index_,
+ gpointer result);
+
+G_END_DECLS
+
+#endif /* EGG_HEAP_H */
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 5be26eb..8ced8ca 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -105,6 +105,13 @@ test_egg_state_machine_SOURCES = test-egg-state-machine.c
test_egg_state_machine_CFLAGS = $(tests_cflags) -I$(top_srcdir)/contrib/egg
test_egg_state_machine_LDADD = $(tests_libs) $(top_builddir)/contrib/egg/libegg.la
+
+TESTS += test-egg-heap
+test_egg_heap_SOURCES = test-egg-heap.c
+test_egg_heap_CFLAGS = $(tests_cflags) -I$(top_srcdir)/contrib/egg
+test_egg_heap_LDADD = $(tests_libs) $(top_builddir)/contrib/egg/libegg.la
+
+
if ENABLE_TESTS
noinst_PROGRAMS = $(TESTS) $(misc_programs)
endif
diff --git a/tests/test-egg-heap.c b/tests/test-egg-heap.c
new file mode 100644
index 0000000..a136eb3
--- /dev/null
+++ b/tests/test-egg-heap.c
@@ -0,0 +1,173 @@
+/* test-egg-heap.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 "egg-heap.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_EggHeap_insert_val_int (void)
+{
+ EggHeap *heap;
+ gint i;
+
+ heap = egg_heap_new (sizeof (gint), cmpint_rev);
+
+ for (i = 0; i < 100000; i++) {
+ egg_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 (egg_heap_peek (heap, gint), ==, i);
+ egg_heap_extract (heap, NULL);
+ }
+
+ egg_heap_unref (heap);
+}
+
+static void
+test_EggHeap_insert_val_ptr (void)
+{
+ gconstpointer ptr;
+ EggHeap *heap;
+ gint i;
+
+ heap = egg_heap_new (sizeof (gpointer), cmpptr_rev);
+
+ for (i = 0; i < 100000; i++) {
+ ptr = GINT_TO_POINTER (i);
+ egg_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 (egg_heap_peek (heap, gpointer) == GINT_TO_POINTER (i));
+ egg_heap_extract (heap, NULL);
+ }
+
+ egg_heap_unref (heap);
+}
+
+static void
+test_EggHeap_insert_val_tuple (void)
+{
+ Tuple t;
+ EggHeap *heap;
+ gint i;
+
+ heap = egg_heap_new (sizeof (Tuple), cmptuple_rev);
+
+ for (i = 0; i < 100000; i++) {
+ t.pointer = GINT_TO_POINTER (i);
+ t.size = i;
+ egg_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 (egg_heap_peek (heap, Tuple).size == i);
+ g_assert (egg_heap_peek (heap, Tuple).pointer == GINT_TO_POINTER (i));
+ egg_heap_extract (heap, NULL);
+ }
+
+ egg_heap_unref (heap);
+}
+
+static void
+test_EggHeap_extract_int (void)
+{
+ EggHeap *heap;
+ gint removed[5];
+ gint i;
+ gint v;
+
+ heap = egg_heap_new (sizeof (gint), cmpint_rev);
+
+ for (i = 0; i < 100000; i++) {
+ egg_heap_insert_val (heap, i);
+ }
+
+ removed [0] = egg_heap_index (heap, gint, 1578); egg_heap_extract_index (heap, 1578, NULL);
+ removed [1] = egg_heap_index (heap, gint, 2289); egg_heap_extract_index (heap, 2289, NULL);
+ removed [2] = egg_heap_index (heap, gint, 3312); egg_heap_extract_index (heap, 3312, NULL);
+ removed [3] = egg_heap_index (heap, gint, 78901); egg_heap_extract_index (heap, 78901, NULL);
+ removed [4] = egg_heap_index (heap, gint, 99000); egg_heap_extract_index (heap, 99000, NULL);
+
+ for (i = 0; i < 100000; i++) {
+ if (egg_heap_peek (heap, gint) != i) {
+ g_assert ((i == removed[0]) ||
+ (i == removed[1]) ||
+ (i == removed[2]) ||
+ (i == removed[3]) ||
+ (i == removed[4]));
+ } else {
+ egg_heap_extract (heap, &v);
+ g_assert_cmpint (v, ==, i);
+ }
+ }
+
+ g_assert_cmpint (heap->len, ==, 0);
+
+ egg_heap_unref (heap);
+}
+
+int
+main (gint argc,
+ gchar *argv[])
+{
+ g_test_init (&argc, &argv, NULL);
+
+ g_test_add_func ("/EggHeap/insert_and_extract<gint>", test_EggHeap_insert_val_int);
+ g_test_add_func ("/EggHeap/insert_and_extract<gpointer>", test_EggHeap_insert_val_ptr);
+ g_test_add_func ("/EggHeap/insert_and_extract<Tuple>", test_EggHeap_insert_val_tuple);
+ g_test_add_func ("/EggHeap/extract_index<int>", test_EggHeap_extract_int);
+
+ return g_test_run ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
