1 /* Licensed under BSD-MIT - see LICENSE file for details */
2 #include <ccan/heap/heap.h>
3
4 /*
5 * Allocating memory in chunks greater than needed does not yield measurable
6 * speedups of the test program when linking against glibc 2.15.
7 *
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.
10 */
11 #define HEAP_MEM_HYSTERESIS 4096
12
swap(struct heap * h,size_t i,size_t j)13 static inline void swap(struct heap *h, size_t i, size_t j)
14 {
15 void *foo = h->data[i];
16
17 h->data[i] = h->data[j];
18 h->data[j] = foo;
19 }
20
__up(struct heap * h,size_t j)21 static void __up(struct heap *h, size_t j)
22 {
23 size_t i; /* parent */
24
25 while (j) {
26 i = (j - 1) / 2;
27
28 if (h->less(h->data[j], h->data[i])) {
29 swap(h, i, j);
30 j = i;
31 } else {
32 break;
33 }
34 }
35 }
36
heap_push(struct heap * h,void * data)37 int heap_push(struct heap *h, void *data)
38 {
39 if (h->len == h->cap) {
40 void *m = realloc(h->data, (h->cap + 1) * sizeof(void *));
41 if (m == NULL)
42 return -1;
43 h->data = m;
44 h->cap++;
45 }
46 h->data[h->len++] = data;
47 __up(h, h->len - 1);
48 return 0;
49 }
50
__down(struct heap * h,size_t i)51 static void __down(struct heap *h, size_t i)
52 {
53 size_t l, r, j; /* left, right, min child */
54
55 while (1) {
56 l = 2 * i + 1;
57 if (l >= h->len)
58 break;
59 r = l + 1;
60 if (r >= h->len)
61 j = l;
62 else
63 j = h->less(h->data[l], h->data[r]) ? l : r;
64
65 if (h->less(h->data[j], h->data[i])) {
66 swap(h, i, j);
67 i = j;
68 } else {
69 break;
70 }
71 }
72 }
73
heap_pop(struct heap * h)74 void *heap_pop(struct heap *h)
75 {
76 void *ret = h->data[0];
77 void *m;
78
79 swap(h, 0, --h->len);
80 if (h->len) {
81 __down(h, 0);
82 if (h->len == h->cap - HEAP_MEM_HYSTERESIS) {
83 m = realloc(h->data, h->len * sizeof(void *));
84 if (m == NULL)
85 return NULL;
86 h->data = m;
87 h->cap = h->len;
88 }
89 }
90
91 return ret;
92 }
93
heap_init(heap_less_func_t less)94 struct heap *heap_init(heap_less_func_t less)
95 {
96 struct heap *heap = calloc(1, sizeof(*heap));
97
98 if (heap == NULL)
99 return NULL;
100 heap->less = less;
101 return heap;
102 }
103
heap_ify(struct heap * h,heap_less_func_t less)104 void heap_ify(struct heap *h, heap_less_func_t less)
105 {
106 int i;
107
108 if (less)
109 h->less = less;
110
111 for (i = h->len / 2 - 1; i >= 0; i--)
112 __down(h, i);
113 }
114
heap_free(struct heap * heap)115 void heap_free(struct heap *heap)
116 {
117 free(heap->data);
118 free(heap);
119 }
120