1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #include <ccan/heap/heap.h>
5 * Allocating memory in chunks greater than needed does not yield measurable
6 * speedups of the test program when linking against glibc 2.15.
8 * When the data array has to be shrunk though, limiting calls to realloc
9 * does help a little bit (~7% speedup), hence the following parameter.
11 #define HEAP_MEM_HYSTERESIS 4096
13 static inline void swap(struct heap *h, size_t i, size_t j)
15 void *foo = h->data[i];
17 h->data[i] = h->data[j];
21 static void __up(struct heap *h, size_t j)
23 size_t i; /* parent */
28 if (h->less(h->data[j], h->data[i])) {
37 int heap_push(struct heap *h, void *data)
39 if (h->len == h->cap) {
40 void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
46 h->data[h->len++] = data;
51 static void __down(struct heap *h, size_t i)
53 size_t l, r, j; /* left, right, min child */
63 j = h->less(h->data[l], h->data[r]) ? l : r;
65 if (h->less(h->data[j], h->data[i])) {
74 void *heap_pop(struct heap *h)
76 void *ret = h->data[0];
82 if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
83 m = realloc(h->data, h->len * sizeof(void *));
94 struct heap *heap_init(heap_less_func_t less)
96 struct heap *heap = calloc(1, sizeof(*heap));
104 void heap_ify(struct heap *h, heap_less_func_t less)
111 for (i = h->len / 2 - 1; i >= 0; i--)
115 void heap_free(struct heap *heap)