1
2 #include <stdio.h>
3 #include <stdlib.h>
4 #include <strings.h>
5 #include <string.h>
6
7 #include "heap.h"
8 #include "rmalloc.h"
9
10 #define DEFAULT_CAPACITY 13
11
12 struct heap_s {
13 /* size of array */
14 unsigned int size;
15 /* items within heap */
16 unsigned int count;
17 /** user data */
18 const void *udata;
19 int (*cmp)(const void *, const void *, const void *);
20 void *array[];
21 };
22
heap_sizeof(unsigned int size)23 size_t heap_sizeof(unsigned int size) {
24 return sizeof(heap_t) + size * sizeof(void *);
25 }
26
__child_left(const int idx)27 static int __child_left(const int idx) {
28 return idx * 2 + 1;
29 }
30
__child_right(const int idx)31 static int __child_right(const int idx) {
32 return idx * 2 + 2;
33 }
34
__parent(const int idx)35 static int __parent(const int idx) {
36 return (idx - 1) / 2;
37 }
38
heap_init(heap_t * h,int (* cmp)(const void *,const void *,const void * udata),const void * udata,unsigned int size)39 void heap_init(heap_t *h, int (*cmp)(const void *, const void *, const void *udata),
40 const void *udata, unsigned int size) {
41 h->cmp = cmp;
42 h->udata = udata;
43 h->size = size;
44 h->count = 0;
45 }
46
heap_new(int (* cmp)(const void *,const void *,const void * udata),const void * udata)47 heap_t *heap_new(int (*cmp)(const void *, const void *, const void *udata), const void *udata) {
48 heap_t *h = rm_malloc(heap_sizeof(DEFAULT_CAPACITY));
49
50 if (!h) return NULL;
51
52 heap_init(h, cmp, udata, DEFAULT_CAPACITY);
53
54 return h;
55 }
56
heap_free(heap_t * h)57 void heap_free(heap_t *h) {
58 rm_free(h);
59 }
60
61 /**
62 * @return a new heap on success; NULL otherwise */
__ensurecapacity(heap_t * h)63 static heap_t *__ensurecapacity(heap_t *h) {
64 if (h->count < h->size) return h;
65
66 h->size *= 2;
67
68 return rm_realloc(h, heap_sizeof(h->size));
69 }
70
__swap(heap_t * h,const int i1,const int i2)71 static void __swap(heap_t *h, const int i1, const int i2) {
72 void *tmp = h->array[i1];
73
74 h->array[i1] = h->array[i2];
75 h->array[i2] = tmp;
76 }
77
__pushup(heap_t * h,unsigned int idx)78 static int __pushup(heap_t *h, unsigned int idx) {
79 /* 0 is the root node */
80 while (0 != idx) {
81 int parent = __parent(idx);
82
83 /* we are smaller than the parent */
84 if (h->cmp(h->array[idx], h->array[parent], h->udata) < 0)
85 return -1;
86 else
87 __swap(h, idx, parent);
88
89 idx = parent;
90 }
91
92 return idx;
93 }
94
__pushdown(heap_t * h,unsigned int idx)95 static void __pushdown(heap_t *h, unsigned int idx) {
96 while (1) {
97 unsigned int childl, childr, child;
98
99 childl = __child_left(idx);
100 childr = __child_right(idx);
101
102 if (childr >= h->count) {
103 /* can't pushdown any further */
104 if (childl >= h->count) return;
105
106 child = childl;
107 }
108 /* find biggest child */
109 else if (h->cmp(h->array[childl], h->array[childr], h->udata) < 0)
110 child = childr;
111 else
112 child = childl;
113
114 /* idx is smaller than child */
115 if (h->cmp(h->array[idx], h->array[child], h->udata) < 0) {
116 __swap(h, idx, child);
117 idx = child;
118 /* bigger than the biggest child, we stop, we win */
119 } else
120 return;
121 }
122 }
123
__heap_offerx(heap_t * h,void * item)124 static void __heap_offerx(heap_t *h, void *item) {
125 h->array[h->count] = item;
126
127 /* ensure heap properties */
128 __pushup(h, h->count++);
129 }
130
heap_offerx(heap_t * h,void * item)131 int heap_offerx(heap_t *h, void *item) {
132 if (h->count == h->size) return -1;
133 __heap_offerx(h, item);
134 return 0;
135 }
136
heap_offer(heap_t ** h,void * item)137 int heap_offer(heap_t **h, void *item) {
138 if (NULL == (*h = __ensurecapacity(*h))) return -1;
139
140 __heap_offerx(*h, item);
141 return 0;
142 }
143
heap_poll(heap_t * h)144 void *heap_poll(heap_t *h) {
145 if (0 == heap_count(h)) return NULL;
146
147 void *item = h->array[0];
148
149 h->array[0] = h->array[h->count - 1];
150 h->count--;
151
152 if (h->count > 1) __pushdown(h, 0);
153
154 return item;
155 }
156
heap_peek(const heap_t * h)157 void *heap_peek(const heap_t *h) {
158 if (0 == heap_count(h)) return NULL;
159
160 return h->array[0];
161 }
162
heap_clear(heap_t * h)163 void heap_clear(heap_t *h) {
164 h->count = 0;
165 }
166
167 /**
168 * @return item's index on the heap's array; otherwise -1 */
__item_get_idx(const heap_t * h,const void * item)169 static int __item_get_idx(const heap_t *h, const void *item) {
170 unsigned int idx;
171
172 for (idx = 0; idx < h->count; idx++)
173 if (0 == h->cmp(h->array[idx], item, h->udata)) return idx;
174
175 return -1;
176 }
177
heap_remove_item(heap_t * h,const void * item)178 void *heap_remove_item(heap_t *h, const void *item) {
179 int idx = __item_get_idx(h, item);
180
181 if (idx == -1) return NULL;
182
183 /* swap the item we found with the last item on the heap */
184 void *ret_item = h->array[idx];
185 h->array[idx] = h->array[h->count - 1];
186 h->array[h->count - 1] = NULL;
187
188 h->count -= 1;
189
190 /* ensure heap property */
191 __pushup(h, idx);
192
193 return ret_item;
194 }
195
heap_contains_item(const heap_t * h,const void * item)196 int heap_contains_item(const heap_t *h, const void *item) {
197 return __item_get_idx(h, item) != -1;
198 }
199
heap_count(const heap_t * h)200 int heap_count(const heap_t *h) {
201 return h->count;
202 }
203
heap_size(const heap_t * h)204 int heap_size(const heap_t *h) {
205 return h->size;
206 }
207
208 /*--------------------------------------------------------------79-characters-*/
209