From 60465a3cb0400687c5531a29c0a99991f842cb30 Mon Sep 17 00:00:00 2001 From: "Emilio G. Cota" Date: Mon, 9 Sep 2013 20:32:19 -0400 Subject: [PATCH] heap: new module Signed-off-by: Emilio G. Cota --- Makefile-ccan | 1 + ccan/heap/LICENSE | 1 + ccan/heap/_info | 67 ++++++++++++++++++++++ ccan/heap/heap.c | 119 ++++++++++++++++++++++++++++++++++++++ ccan/heap/heap.h | 114 +++++++++++++++++++++++++++++++++++++ ccan/heap/test/run.c | 133 +++++++++++++++++++++++++++++++++++++++++++ 6 files changed, 435 insertions(+) create mode 120000 ccan/heap/LICENSE create mode 100644 ccan/heap/_info create mode 100644 ccan/heap/heap.c create mode 100644 ccan/heap/heap.h create mode 100644 ccan/heap/test/run.c diff --git a/Makefile-ccan b/Makefile-ccan index 2d713a68..c4a8f455 100644 --- a/Makefile-ccan +++ b/Makefile-ccan @@ -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 index 00000000..2354d129 --- /dev/null +++ b/ccan/heap/LICENSE @@ -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 index 00000000..552b139e --- /dev/null +++ b/ccan/heap/_info @@ -0,0 +1,67 @@ +#include +#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 + * + * #include + * + * 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 + */ +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 index 00000000..aec90167 --- /dev/null +++ b/ccan/heap/heap.c @@ -0,0 +1,119 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#include + +/* + * 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 index 00000000..e7694a30 --- /dev/null +++ b/ccan/heap/heap.h @@ -0,0 +1,114 @@ +/* Licensed under BSD-MIT - see LICENSE file for details */ +#ifndef CCAN_HEAP_H +#define CCAN_HEAP_H + +#include +#include + +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 index 00000000..6972a6be --- /dev/null +++ b/ccan/heap/test/run.c @@ -0,0 +1,133 @@ +#include +#include + +#include +/* Include the C files directly. */ +#include +#include + +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(); +} -- 2.39.2