heap: new module
authorEmilio G. Cota <cota@braap.org>
Tue, 10 Sep 2013 00:32:19 +0000 (20:32 -0400)
committerRusty Russell <rusty@rustcorp.com.au>
Tue, 10 Sep 2013 04:55:06 +0000 (14:25 +0930)
Signed-off-by: Emilio G. Cota <cota@braap.org>
Makefile-ccan
ccan/heap/LICENSE [new symlink]
ccan/heap/_info [new file with mode: 0644]
ccan/heap/heap.c [new file with mode: 0644]
ccan/heap/heap.h [new file with mode: 0644]
ccan/heap/test/run.c [new file with mode: 0644]

index 2d713a6898e402e21bd45530cc586b63ca86ca4b..c4a8f455ff98683ad4721165d3eafeeef3f91b39 100644 (file)
@@ -49,6 +49,7 @@ MODS_WITH_SRC := antithread \
        foreach \
        grab_file \
        hash \
+       heap \
        htable \
        idtree \
        ilog \
diff --git a/ccan/heap/LICENSE b/ccan/heap/LICENSE
new file mode 120000 (symlink)
index 0000000..2354d12
--- /dev/null
@@ -0,0 +1 @@
+../../licenses/BSD-MIT
\ No newline at end of file
diff --git a/ccan/heap/_info b/ccan/heap/_info
new file mode 100644 (file)
index 0000000..552b139
--- /dev/null
@@ -0,0 +1,67 @@
+#include <string.h>
+#include "config.h"
+
+/**
+ * heap - a simple heap implementation
+ *
+ * Each heap entry is added as a void pointer. This means the implementation
+ * does _not_ assume you already have an array of entries. Instead, it keeps
+ * an internal array of pointers to those entries.
+ *
+ * Example:
+ *     #include <stdio.h>
+ *
+ *     #include <ccan/heap/heap.h>
+ *
+ *     static bool less(const int *i, const int *j)
+ *     {
+ *             return *i < *j;
+ *     }
+ *
+ *     static bool __less(const void *i, const void *j)
+ *     {
+ *             return less(i, j);
+ *     }
+ *
+ *     int main(int argc, char *argv[])
+ *     {
+ *             struct heap *h;
+ *             int arr[] = {1, 0, 2};
+ *             int i;
+ *
+ *             h = heap_init(__less);
+ *             if (h == NULL) {
+ *                     perror("heap alloc");
+ *                     exit(1);
+ *             }
+ *
+ *             for (i = 0; i < 3; i++) {
+ *                     if (heap_push(h, &arr[i])) {
+ *                             perror("heap push");
+ *                             exit(1);
+ *                     }
+ *             }
+ *             // should print 0, 1, 2
+ *             for (i = 0; i < 3; i++) {
+ *                     int *v = heap_pop(h);
+ *                     printf("%d\n", *v);
+ *             }
+ *             heap_free(h);
+ *             return 0;
+ *     }
+ *
+ * License: BSD-MIT
+ * Author: Emilio G. Cota <cota@braap.org>
+ */
+int main(int argc, char *argv[])
+{
+       /* Expect exactly one argument */
+       if (argc != 2)
+               return 1;
+
+       if (strcmp(argv[1], "depends") == 0) {
+               return 0;
+       }
+
+       return 1;
+}
diff --git a/ccan/heap/heap.c b/ccan/heap/heap.c
new file mode 100644 (file)
index 0000000..aec9016
--- /dev/null
@@ -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);
+}
diff --git a/ccan/heap/heap.h b/ccan/heap/heap.h
new file mode 100644 (file)
index 0000000..e7694a3
--- /dev/null
@@ -0,0 +1,114 @@
+/* Licensed under BSD-MIT - see LICENSE file for details */
+#ifndef CCAN_HEAP_H
+#define CCAN_HEAP_H
+
+#include <stdbool.h>
+#include <stdlib.h>
+
+typedef bool (*heap_less_func_t)(const void *, const void *);
+
+/**
+ * struct heap - a simple, generic heap structure
+ * @data: array of pointers to the heap's entries
+ * @less: function to compare heap entries
+ * @cap: capacity of the heap array in @data
+ * @len: number of valid elements in the heap array
+ *
+ * The @less function determines the nature of the heap. If @less is
+ * something akin to 'return a.foo < b.foo', then the heap will be
+ * a min heap. Conversely, a '>' predicate will result in a max heap.
+ *
+ * Elements in the @data array are allocated as needed, hence the need for
+ * @cap and @len.
+ */
+struct heap {
+       void **data;
+       heap_less_func_t less;
+       size_t cap;
+       size_t len;
+};
+
+/**
+ * heap_init - allocate and initialise an empty heap
+ * @less: function to be used to compare heap entries
+ *
+ * Returns a pointer to an initialised heap struct on success, NULL if
+ * the heap could not be allocated.
+ *
+ * See also: HEAP_INIT()
+ */
+struct heap *heap_init(heap_less_func_t less);
+
+/**
+ * HEAP_INIT - initialiser for an empty heap
+ * @func: comparison function to be used in the heap
+ *
+ * Explicit initialiser for a heap.
+ *
+ * See also: heap_init()
+ */
+#define HEAP_INIT(func) { NULL, func, 0, 0 }
+
+/**
+ * heap_free - free a heap allocated via heap_init()
+ * @heap: the heap to be freed
+ *
+ * Note that this only frees the heap and its internal resources, not
+ * the entries pointed to by it.
+ *
+ * See also: heap_init()
+ */
+void heap_free(struct heap *heap);
+
+/**
+ * heap_ify - enforce the heap property based on a new comparison function
+ * @h: heap to be heapified
+ * @less: new comparison function
+ *
+ * Complexity: O(n)
+ */
+void heap_ify(struct heap *h, heap_less_func_t less);
+
+/**
+ * heap_push - push a new heap entry
+ * @h: heap to receive the new entry
+ * @data: pointer to the new entry
+ *
+ * Returns 0 on success, -1 on error.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_pop()
+ */
+int heap_push(struct heap *h, void *data);
+
+/**
+ * heap_pop - pops the root heap entry
+ * @h: heap to pop the head from
+ *
+ * Returns the root entry of the heap after extracting it, or NULL on error.
+ *
+ * Note: Calling heap_pop() on an empty heap is a bug--don't do it.
+ *
+ * Complexity: O(log n)
+ *
+ * See also: heap_push(), heap_peek()
+ */
+void *heap_pop(struct heap *h);
+
+/**
+ * heap_peek - inspect the root entry of a heap
+ * @h: heap whose root entry is to be inspected
+ *
+ * Returns the root entry in the heap, without extracting it from @h.
+ *
+ * Note: Calling heap_peek() on an empty heap is a bug--don't do it.
+ *
+ * See also: heap_pop()
+ */
+static inline void *heap_peek(const struct heap *h)
+{
+       return h->data[0];
+}
+
+#endif /* CCAN_HEAP_H */
diff --git a/ccan/heap/test/run.c b/ccan/heap/test/run.c
new file mode 100644 (file)
index 0000000..6972a6b
--- /dev/null
@@ -0,0 +1,133 @@
+#include <stdlib.h>
+#include <stdio.h>
+
+#include <ccan/heap/heap.h>
+/* Include the C files directly. */
+#include <ccan/heap/heap.c>
+#include <ccan/tap/tap.h>
+
+struct item {
+       void *foobar;
+       int v;
+};
+
+static bool heap_ok(const struct heap *h, heap_less_func_t less, int i)
+{
+       int l, r;
+
+       l = 2 * i + 1;
+       r = l + 1;
+
+       if (l < h->len) {
+               if (less(h->data[l], h->data[i])) {
+                       fprintf(stderr, "heap property violation\n");
+                       return false;
+               }
+               if (!heap_ok(h, less, l))
+                       return false;
+       }
+       if (r < h->len) {
+               if (less(h->data[r], h->data[i])) {
+                       fprintf(stderr, "heap property violation\n");
+                       return false;
+               }
+               if (!heap_ok(h, less, r))
+                       return false;
+       }
+       return true;
+}
+
+static bool less(const struct item *a, const struct item *b)
+{
+       return a->v < b->v;
+}
+
+static bool __less(const void *a, const void *b)
+{
+       return less(a, b);
+}
+
+static bool more(const struct item *a, const struct item *b)
+{
+       return a->v > b->v;
+}
+
+static bool __more(const void *a, const void *b)
+{
+       return more(a, b);
+}
+
+static bool some_test(size_t n, bool is_less)
+{
+       struct item *items = calloc(n, sizeof(*items));
+       struct item *item, *prev;
+       struct heap *h;
+       int i;
+
+       if (items == NULL) {
+               perror("items");
+               exit(EXIT_FAILURE);
+       }
+
+       if (is_less)
+               h = heap_init(__less);
+       else
+               h = heap_init(__more);
+       if (h == NULL) {
+               perror("heap_init");
+               exit(EXIT_FAILURE);
+       }
+
+       for (i = 0; i < n; i++) {
+               item = &items[i];
+
+               item->v = rand();
+               printf("pushing %d\n", item->v);
+               heap_push(h, item);
+               if (!heap_ok(h, is_less ? __less : __more, 0))
+                       return false;
+       }
+       if (is_less) {
+               heap_ify(h, __more);
+               if (!heap_ok(h, __more, 0))
+                       return false;
+               heap_ify(h, __less);
+               if (!heap_ok(h, __less, 0))
+                       return false;
+       } else {
+               heap_ify(h, NULL);
+               if (!heap_ok(h, __more, 0))
+                       return false;
+       }
+
+       for (i = 0; i < n; i++) {
+               item = heap_pop(h);
+               if (!heap_ok(h, is_less ? __less : __more, 0))
+                       return false;
+               printf("popped %d\n", item->v);
+               if (i > 0) {
+                       if (is_less) {
+                               if (less(item, prev))
+                                       return false;
+                       } else {
+                               if (more(item, prev))
+                                       return false;
+                       }
+               }
+               prev = item;
+       }
+       heap_free(h);
+       free(items);
+       return true;
+}
+
+int main(void)
+{
+       plan_tests(3);
+
+       ok1(some_test(5000, true));
+       ok1(some_test(1, true));
+       ok1(some_test(33, false));
+
+       return exit_status();
+}