1 RCSID("$Id: a2e8f782429d35c1f40fae20ec7efced6bf6b39b $")
2
3 #include <freeradius-devel/libradius.h>
4 #include <freeradius-devel/heap.h>
5
6 /*
7 * A heap entry is made of a pointer to the object, which
8 * contains the key. The heap itself is an array of pointers.
9 *
10 * Heaps normally support only ordered insert, and extraction
11 * of the minimum element. The heap entry can contain an "int"
12 * field that holds the entries position in the heap. The offset
13 * of the field is held inside of the heap structure.
14 */
15
16 struct fr_heap_t {
17 int size;
18 int num_elements;
19 size_t offset;
20 fr_heap_cmp_t cmp;
21 void **p;
22 };
23
24 /*
25 * First node in a heap is element 0. Children of i are 2i+1 and
26 * 2i+2. These macros wrap the logic, so the code is more
27 * descriptive.
28 */
29 #define HEAP_PARENT(x) ( ( (x) - 1 ) / 2 )
30 #define HEAP_LEFT(x) ( 2*(x) + 1 )
31 /* #define HEAP_RIGHT(x) ( 2*(x) + 2 ) */
32 #define HEAP_SWAP(a, b) { void *_tmp = a; a = b; b = _tmp; }
33
34 static int fr_heap_bubble(fr_heap_t *hp, int child);
35
fr_heap_delete(fr_heap_t * hp)36 void fr_heap_delete(fr_heap_t *hp)
37 {
38 if (!hp) return;
39
40 free(hp->p);
41 free(hp);
42 }
43
fr_heap_create(fr_heap_cmp_t cmp,size_t offset)44 fr_heap_t *fr_heap_create(fr_heap_cmp_t cmp, size_t offset)
45 {
46 fr_heap_t *fh;
47
48 if (!cmp) return NULL;
49
50 fh = malloc(sizeof(*fh));
51 if (!fh) return NULL;
52
53 memset(fh, 0, sizeof(*fh));
54
55 fh->size = 2048;
56 fh->p = malloc(sizeof(*(fh->p)) * fh->size);
57 if (!fh->p) {
58 free(fh);
59 return NULL;
60 }
61
62 fh->cmp = cmp;
63 fh->offset = offset;
64
65 return fh;
66 }
67
68 /*
69 * Insert element in heap. Normally, p != NULL, we insert p in a
70 * new position and bubble up. If p == NULL, then the element is
71 * already in place, and key is the position where to start the
72 * bubble-up.
73 *
74 * Returns 1 on failure (cannot allocate new heap entry)
75 *
76 * If offset > 0 the position (index, int) of the element in the
77 * heap is also stored in the element itself at the given offset
78 * in bytes.
79 */
80 #define SET_OFFSET(heap, node) \
81 if (heap->offset) \
82 *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = node
83
84 /*
85 * RESET_OFFSET is used for sanity checks. It sets offset to an
86 * invalid value.
87 */
88 #define RESET_OFFSET(heap, node) \
89 if (heap->offset) \
90 *((int *)(((uint8_t *)heap->p[node]) + heap->offset)) = -1
91
fr_heap_insert(fr_heap_t * hp,void * data)92 int fr_heap_insert(fr_heap_t *hp, void *data)
93 {
94 int child = hp->num_elements;
95
96 /*
97 * Heap is full. Double it's size.
98 */
99 if (child == hp->size) {
100 void **p;
101
102 p = malloc(2 * hp->size * sizeof(*p));
103 if (!p) return 0;
104
105 memcpy(p, hp->p, sizeof(*p) * hp->size);
106 free(hp->p);
107 hp->p = p;
108 hp->size *= 2;
109 }
110
111 hp->p[child] = data;
112 hp->num_elements++;
113
114 return fr_heap_bubble(hp, child);
115 }
116
117
fr_heap_bubble(fr_heap_t * hp,int child)118 static int fr_heap_bubble(fr_heap_t *hp, int child)
119 {
120 /*
121 * Bubble up the element.
122 */
123 while (child > 0) {
124 int parent = HEAP_PARENT(child);
125
126 /*
127 * Parent is smaller than the child. We're done.
128 */
129 if (hp->cmp(hp->p[parent], hp->p[child]) < 0) break;
130
131 /*
132 * Child is smaller than the parent, repeat.
133 */
134 HEAP_SWAP(hp->p[child], hp->p[parent]);
135 SET_OFFSET(hp, child);
136 child = parent;
137 }
138 SET_OFFSET(hp, child);
139
140 return 1;
141 }
142
143
144 /*
145 * Remove the top element, or object.
146 */
fr_heap_extract(fr_heap_t * hp,void * data)147 int fr_heap_extract(fr_heap_t *hp, void *data)
148 {
149 int child, parent;
150 int max;
151
152 if (!hp || (hp->num_elements == 0)) return 0;
153
154 max = hp->num_elements - 1;
155
156 /*
157 * Extract element. Default is the first one.
158 */
159 if (!data) {
160 parent = 0;
161
162 } else { /* extract from the middle */
163 if (!hp->offset) return 0;
164
165 parent = *((int *)(((uint8_t *)data) + hp->offset));
166
167 /*
168 * Out of bounds.
169 */
170 if (parent < 0 || parent >= hp->num_elements) return 0;
171 }
172
173 RESET_OFFSET(hp, parent);
174 child = HEAP_LEFT(parent);
175 while (child <= max) {
176 /*
177 * Maybe take the right child.
178 */
179 if ((child != max) &&
180 (hp->cmp(hp->p[child + 1], hp->p[child]) < 0)) {
181 child = child + 1;
182 }
183 hp->p[parent] = hp->p[child];
184 SET_OFFSET(hp, parent);
185 parent = child;
186 child = HEAP_LEFT(child);
187 }
188 hp->num_elements--;
189
190 /*
191 * We didn't end up at the last element in the heap.
192 * This element has to be re-inserted.
193 */
194 if (parent != max) {
195 /*
196 * Fill hole with last entry and bubble up,
197 * reusing the insert code
198 */
199 hp->p[parent] = hp->p[max];
200 return fr_heap_bubble(hp, parent);
201 }
202
203 return 1;
204 }
205
206
fr_heap_peek(fr_heap_t * hp)207 void *fr_heap_peek(fr_heap_t *hp)
208 {
209 if (!hp || (hp->num_elements == 0)) return NULL;
210
211 /*
212 * If this is NULL, we have a problem.
213 */
214 return hp->p[0];
215 }
216
fr_heap_num_elements(fr_heap_t * hp)217 int fr_heap_num_elements(fr_heap_t *hp)
218 {
219 if (!hp) return 0;
220
221 return hp->num_elements;
222 }
223
224
225 #ifdef TESTING
fr_heap_check(fr_heap_t * hp,void * data)226 static bool fr_heap_check(fr_heap_t *hp, void *data)
227 {
228 int i;
229
230 if (!hp || (hp->num_elements == 0)) return false;
231
232 for (i = 0; i < hp->num_elements; i++) {
233 if (hp->p[i] == data) {
234 return true;
235 }
236 }
237
238 return false;
239 }
240
241 typedef struct heap_thing {
242 int data;
243 int heap; /* for the heap */
244 } heap_thing;
245
246
247 /*
248 * cc -g -DTESTING -I .. heap.c -o heap
249 *
250 * ./heap
251 */
heap_cmp(void const * one,void const * two)252 static int heap_cmp(void const *one, void const *two)
253 {
254 heap_thing const *a;
255 heap_thing const *b;
256
257 a = (heap_thing const *) one;
258 b = (heap_thing const *) two;
259
260 return a->data - b->data;
261
262 }
263
264 #define ARRAY_SIZE (1024)
265
main(int argc,char ** argv)266 int main(int argc, char **argv)
267 {
268 fr_heap_t *hp;
269 int i;
270 heap_thing array[ARRAY_SIZE];
271 int skip = 0;
272 int left;
273
274 if (argc > 1) {
275 skip = atoi(argv[1]);
276 }
277
278 hp = fr_heap_create(heap_cmp, offsetof(heap_thing, heap));
279 if (!hp) {
280 fprintf(stderr, "Failed creating heap!\n");
281 fr_exit(1);
282 }
283
284 for (i = 0; i < ARRAY_SIZE; i++) {
285 array[i].data = rand() % 65537;
286 if (!fr_heap_insert(hp, &array[i])) {
287 fprintf(stderr, "Failed inserting %d\n", i);
288 fr_exit(1);
289 }
290
291 if (!fr_heap_check(hp, &array[i])) {
292 fprintf(stderr, "Inserted but not in heap %d\n", i);
293 fr_exit(1);
294 }
295 }
296
297 #if 0
298 for (i = 0; i < ARRAY_SIZE; i++) {
299 printf("Array %d has value %d at offset %d\n",
300 i, array[i].data, array[i].heap);
301 }
302 #endif
303
304 if (skip) {
305 int entry;
306
307 printf("%d elements to remove\n", ARRAY_SIZE / skip);
308
309 for (i = 0; i < ARRAY_SIZE / skip; i++) {
310 entry = i * skip;
311
312 if (!fr_heap_extract(hp, &array[entry])) {
313 fprintf(stderr, "Failed removing %d\n", entry);
314 }
315
316 if (fr_heap_check(hp, &array[entry])) {
317 fprintf(stderr, "Deleted but still in heap %d\n", entry);
318 fr_exit(1);
319 }
320
321 if (array[entry].heap != -1) {
322 fprintf(stderr, "heap offset is wrong %d\n", entry);
323 fr_exit(1);
324 }
325 }
326 }
327
328 left = fr_heap_num_elements(hp);
329 printf("%d elements left in the heap\n", left);
330
331 for (i = 0; i < left; i++) {
332 heap_thing *t = fr_heap_peek(hp);
333
334 if (!t) {
335 fprintf(stderr, "Failed peeking %d\n", i);
336 fr_exit(1);
337 }
338
339 printf("%d\t%d\n", i, t->data);
340
341 if (!fr_heap_extract(hp, NULL)) {
342 fprintf(stderr, "Failed extracting %d\n", i);
343 fr_exit(1);
344 }
345 }
346
347 if (fr_heap_num_elements(hp) > 0) {
348 fprintf(stderr, "%d elements left at the end", fr_heap_num_elements(hp));
349 fr_exit(1);
350 }
351
352 fr_heap_delete(hp);
353
354 return 0;
355 }
356 #endif
357