gheap: add GHeap for min heap based priority queues.wip/gheap

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.

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 ();
+}