[glib/wip/gheap] gheap: add GHeap for min heap based priority queues.
- From: Christian Hergert <chergert src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [glib/wip/gheap] gheap: add GHeap for min heap based priority queues.
- Date: Mon, 5 May 2014 01:35:26 +0000 (UTC)
commit bd25317ebe041d88e7ed67d0b99d2fa3b29e9e25
Author: Christian Hergert <christian hergert me>
Date: Sun May 4 19:44:26 2014 +0200
gheap: add GHeap for min heap based priority queues.
This data structure allows for O(1) lookup time for one of min or max item
(depending on a given compare function) in a priority queue. Insertion
into the heap is O(log n) and removal from the heap is O(log n). It allows
for removal from any index within the heap.
Since the heap is implemented as an array, it can often have good cache
locality properties.
glib/Makefile.am | 2 +
glib/gheap.c | 364 ++++++++++++++++++++++++++++++++++++++++++++++++
glib/gheap.h | 59 ++++++++
glib/glib.h | 1 +
glib/tests/.gitignore | 1 +
glib/tests/Makefile.am | 1 +
glib/tests/gheap.c | 176 +++++++++++++++++++++++
7 files changed, 604 insertions(+), 0 deletions(-)
---
diff --git a/glib/Makefile.am b/glib/Makefile.am
index d9892f6..f8c9dd1 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 0000000..852dd44
--- /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 0000000..b964d68
--- /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 c7fc999..a5d5eb6 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 33ef15e..20ca63c 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 445040a..2311d34 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 0000000..9b48339
--- /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 ();
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
