heap: new module

[ccan] / ccan / heap / heap.c

diff --git a/ccan/heap/heap.c b/ccan/heap/heap.c
new file mode 100644 (file)
index 0000000..aec9016
--- /dev/null
+++ b/ccan/heap/heap.c
@@ -0,0 +1,119 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#include <ccan/heap/heap.h>
+
+/*
+ * Allocating memory in chunks greater than needed does not yield measurable
+ * speedups of the test program when linking against glibc 2.15.
+ *
+ * When the data array has to be shrunk though, limiting calls to realloc
+ * does help a little bit (~7% speedup), hence the following parameter.
+ */
+#define HEAP_MEM_HYSTERESIS    4096
+
+static inline void swap(struct heap *h, size_t i, size_t j)
+{
+       void *foo = h->data[i];
+
+       h->data[i] = h->data[j];
+       h->data[j] = foo;
+}
+
+static void __up(struct heap *h, size_t j)
+{
+       size_t i; /* parent */
+
+       while (j) {
+               i = (j - 1) / 2;
+
+               if (h->less(h->data[j], h->data[i])) {
+                       swap(h, i, j);
+                       j = i;
+               } else {
+                       break;
+               }
+       }
+}
+
+int heap_push(struct heap *h, void *data)
+{
+       if (h->len == h->cap) {
+               void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
+               if (m == NULL)
+                       return -1;
+               h->data = m;
+               h->cap++;
+       }
+       h->data[h->len++] = data;
+       __up(h, h->len - 1);
+       return 0;
+}
+
+static void __down(struct heap *h, size_t i)
+{
+       size_t l, r, j; /* left, right, min child */
+
+       while (1) {
+               l = 2 * i + 1;
+               if (l >= h->len)
+                       break;
+               r = l + 1;
+               if (r >= h->len)
+                       j = l;
+               else
+                       j = h->less(h->data[l], h->data[r]) ? l : r;
+
+               if (h->less(h->data[j], h->data[i])) {
+                       swap(h, i, j);
+                       i = j;
+               } else {
+                       break;
+               }
+       }
+}
+
+void *heap_pop(struct heap *h)
+{
+       void *ret = h->data[0];
+       void *m;
+
+       swap(h, 0, --h->len);
+       if (h->len) {
+               __down(h, 0);
+               if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
+                       m = realloc(h->data, h->len * sizeof(void *));
+                       if (m == NULL)
+                               return NULL;
+                       h->data = m;
+                       h->cap = h->len;
+               }
+       }
+
+       return ret;
+}
+
+struct heap *heap_init(heap_less_func_t less)
+{
+       struct heap *heap = calloc(1, sizeof(*heap));
+
+       if (heap == NULL)
+               return NULL;
+       heap->less = less;
+       return heap;
+}
+
+void heap_ify(struct heap *h, heap_less_func_t less)
+{
+       int i;
+
+       if (less)
+               h->less = less;
+
+       for (i = h->len / 2 - 1; i >= 0; i--)
+               __down(h, i);
+}
+
+void heap_free(struct heap *heap)
+{
+       free(heap->data);
+       free(heap);
+}