Merge https://github.com/dgibson/ccan
[ccan] / ccan / heap / heap.c
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
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
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
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
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
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
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
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
115 void heap_free(struct heap *heap)
116 {
117         free(heap->data);
118         free(heap);
119 }