80aaeada |
1 | /* |
2 | * Generic reusable binary-heap maintenance code. |
749cebc3 |
3 | * |
4 | * This file is copyright 2005 Simon Tatham. |
5 | * |
6 | * Permission is hereby granted, free of charge, to any person |
7 | * obtaining a copy of this software and associated documentation |
8 | * files (the "Software"), to deal in the Software without |
9 | * restriction, including without limitation the rights to use, |
10 | * copy, modify, merge, publish, distribute, sublicense, and/or |
11 | * sell copies of the Software, and to permit persons to whom the |
12 | * Software is furnished to do so, subject to the following |
13 | * conditions: |
14 | * |
15 | * The above copyright notice and this permission notice shall be |
16 | * included in all copies or substantial portions of the Software. |
17 | * |
18 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, |
19 | * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES |
20 | * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND |
21 | * NONINFRINGEMENT. IN NO EVENT SHALL SIMON TATHAM BE LIABLE FOR |
22 | * ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF |
23 | * CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN |
24 | * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE |
25 | * SOFTWARE. |
80aaeada |
26 | */ |
27 | |
28 | #include <stdlib.h> |
29 | #include <string.h> |
30 | #include "bheap.h" |
31 | |
32 | #ifdef TESTMODE |
33 | int coverage; /* bit flags for various if clauses */ |
34 | int checked_coverage; |
35 | #define COVERAGE(x) ( coverage |= (1 << (x)) ) |
36 | #else |
37 | #define COVERAGE(x) ( (void)0 ) |
38 | #endif |
39 | |
40 | struct bheap { |
41 | int nelts, maxelts; |
42 | int eltsize; |
43 | int direction; |
44 | bheap_cmpfn_t compare; |
45 | void *compare_ctx; |
46 | char *elts; |
47 | }; |
48 | |
49 | /* |
50 | * Our array is zero-based. Therefore the children of 0 are 1 and |
51 | * 2; the children of 1 are 3 and 4; of 2 are 5 and 6, and so on. |
52 | * In other words, the children of node n are 2n+1 and 2n+2, and |
53 | * the parent of node n is floor((n-1)/2). |
54 | */ |
55 | #define PARENT(n) ( ((n)-1)/2 ) |
56 | #define LCHILD(n) ( 2*(n)+1 ) |
57 | #define RCHILD(n) ( 2*(n)+2 ) |
58 | |
59 | /* |
60 | * This macro calls the compare function, and returns TRUE if the |
61 | * two elements are the wrong way up and should be swapped. |
62 | * |
63 | * It doesn't _have_ to be called on a parent and child, but its |
64 | * return value assumes that. So you could call it on any two |
65 | * elements x,y and it would return TRUE if y ought to be the |
66 | * parent of x. |
67 | */ |
68 | #define MISORDERED(bh,parent,child) \ |
69 | ( (bh)->direction * \ |
70 | (bh)->compare((bh)->compare_ctx, \ |
71 | (bh)->elts + (parent) * (bh)->eltsize, \ |
72 | (bh)->elts + (child) * (bh)->eltsize) > 0 ) |
73 | |
74 | /* |
75 | * This macro swaps two elements of the heap. |
76 | */ |
77 | #define SWAP(bh,x,y) do { \ |
78 | memcpy((bh)->elts + (bh)->maxelts * (bh)->eltsize, \ |
79 | (bh)->elts + (x) * (bh)->eltsize, (bh)->eltsize); \ |
80 | memcpy((bh)->elts + (x) * (bh)->eltsize, \ |
81 | (bh)->elts + (y) * (bh)->eltsize, (bh)->eltsize); \ |
82 | memcpy((bh)->elts + (y) * (bh)->eltsize, \ |
83 | (bh)->elts + (bh)->maxelts * (bh)->eltsize, (bh)->eltsize); \ |
84 | } while (0) |
85 | |
86 | bheap *bheap_new(int maxelts, int eltsize, int direction, |
87 | bheap_cmpfn_t compare, void *compare_ctx) |
88 | { |
89 | bheap *bh = malloc(sizeof(bheap)); |
90 | if (!bh) |
91 | return NULL; |
92 | |
93 | /* |
94 | * Allocate one extra element of space, to use for swapping |
95 | * things. |
96 | */ |
5a2294f3 |
97 | bh->elts = malloc((maxelts + 1) * eltsize); |
80aaeada |
98 | if (!bh->elts) |
99 | return NULL; |
100 | |
101 | bh->nelts = 0; |
102 | bh->maxelts = maxelts; |
103 | bh->eltsize = eltsize; |
104 | bh->direction = direction; |
105 | bh->compare = compare; |
106 | bh->compare_ctx = compare_ctx; |
107 | |
108 | return bh; |
109 | } |
110 | |
111 | void *bheap_add(bheap *bh, void *elt) |
112 | { |
113 | int i; |
114 | |
115 | if (bh->nelts >= bh->maxelts) { |
116 | COVERAGE(0); |
117 | return NULL; |
118 | } |
119 | |
120 | COVERAGE(1); |
121 | /* |
122 | * Add the element to the end of the array. |
123 | */ |
124 | memcpy(bh->elts + bh->nelts * bh->eltsize, elt, bh->eltsize); |
125 | bh->nelts++; |
126 | |
127 | /* |
128 | * Now swap it with its parent repeatedly to preserve the heap |
129 | * property. |
130 | */ |
131 | i = bh->nelts-1; |
132 | |
133 | if (i == 0) |
134 | COVERAGE(2); |
135 | |
136 | while (i > 0) { |
137 | int p = PARENT(i); |
138 | |
139 | COVERAGE(3); |
140 | |
141 | if (MISORDERED(bh, p, i)) { |
142 | COVERAGE(4); |
143 | SWAP(bh, p, i); |
144 | i = p; |
145 | } else { |
146 | COVERAGE(5); |
147 | break; /* we're done */ |
148 | } |
149 | } |
150 | |
151 | return elt; |
152 | } |
153 | |
154 | void *bheap_topmost(bheap *bh, void *elt) |
155 | { |
156 | if (bh->nelts <= 0) { |
157 | COVERAGE(6); |
158 | return NULL; |
159 | } |
160 | |
161 | COVERAGE(7); |
162 | memcpy(elt, bh->elts, bh->eltsize); |
163 | return elt; |
164 | } |
165 | |
166 | void *bheap_remove(bheap *bh, void *elt) |
167 | { |
168 | if (bh->nelts <= 0) { |
169 | COVERAGE(8); |
170 | return NULL; |
171 | } |
172 | |
173 | if (elt) |
174 | memcpy(elt, bh->elts, bh->eltsize); |
175 | |
176 | bh->nelts--; |
177 | |
178 | if (bh->nelts > 0) { |
179 | int i; |
180 | |
181 | COVERAGE(8); |
182 | /* |
183 | * Move the highest-index element of the heap into the top |
184 | * position. |
185 | */ |
186 | SWAP(bh, bh->nelts, 0); |
187 | |
188 | /* |
189 | * Now repeatedly move it down the heap by swapping it with |
190 | * the more suitable of its children. |
191 | */ |
192 | i = 0; |
193 | while (1) { |
194 | int lc, rc; |
195 | |
196 | lc = LCHILD(i); |
197 | rc = RCHILD(i); |
198 | |
199 | COVERAGE(9); |
200 | |
201 | if (lc >= bh->nelts) { |
202 | COVERAGE(10); |
203 | break; /* we've hit bottom */ |
204 | } |
205 | |
206 | if (rc >= bh->nelts) { |
207 | /* |
208 | * Special case: there is only one child to check. |
209 | */ |
210 | COVERAGE(11); |
211 | if (MISORDERED(bh, i, lc)) { |
212 | COVERAGE(12); |
213 | SWAP(bh, i, lc); |
214 | } else { |
215 | COVERAGE(13); |
216 | } |
217 | /* _Now_ we've hit bottom. */ |
218 | break; |
219 | } else { |
220 | COVERAGE(14); |
221 | /* |
222 | * The common case: there are two children and we |
223 | * must check them both. |
224 | */ |
225 | if (MISORDERED(bh, i, lc) || MISORDERED(bh, i, rc)) { |
226 | COVERAGE(15); |
227 | /* |
228 | * Pick the more appropriate child to swap with |
229 | * (i.e. the one which would want to be the |
230 | * parent if one were above the other - as one |
231 | * is about to be). |
232 | */ |
233 | if (MISORDERED(bh, lc, rc)) { |
234 | COVERAGE(16); |
235 | SWAP(bh, i, rc); |
236 | i = rc; |
237 | } else { |
238 | COVERAGE(17); |
239 | SWAP(bh, i, lc); |
240 | i = lc; |
241 | } |
242 | } else { |
243 | /* This element is in the right place; we're done. */ |
244 | COVERAGE(18); |
245 | break; |
246 | } |
247 | } |
248 | } |
249 | } else { |
250 | COVERAGE(19); |
251 | } |
252 | |
253 | return elt; |
254 | } |
255 | |
256 | int bheap_count(bheap *bh) |
257 | { |
258 | return bh->nelts; |
259 | } |
260 | |
261 | void bheap_free(bheap *bh) |
262 | { |
263 | if (bh) { |
264 | if (bh->elts) |
265 | free(bh->elts); |
266 | free(bh); |
267 | } |
268 | } |
269 | |
270 | #ifdef TESTMODE |
271 | |
272 | #include <stdio.h> |
273 | |
274 | /* we _really_ need assertions enabled, for this test */ |
275 | #undef NDEBUG |
276 | #include <assert.h> |
277 | |
278 | #define MAX 8 |
279 | |
280 | #define CHECK_COVERAGE(c, statement) do { \ |
281 | coverage &= ~ (1 << (c)); \ |
282 | statement; \ |
283 | assert(coverage & (1 << (c))); \ |
284 | checked_coverage |= (1 << (c)); \ |
285 | } while (0) |
286 | |
287 | int intcmp_ctx; |
288 | int array[MAX]; |
289 | int n; |
290 | |
291 | bheap *bh; |
292 | |
293 | int intcmp(void *vctx, const void *av, const void *bv) |
294 | { |
295 | const int *a = (const int *)av; |
296 | const int *b = (const int *)bv; |
297 | int *ctx = (int *)vctx; |
298 | |
299 | assert(ctx == &intcmp_ctx); |
300 | |
301 | if (*a < *b) |
302 | return -1; |
303 | else if (*a > *b) |
304 | return +1; |
305 | return 0; |
306 | } |
307 | |
308 | void add(int x) |
309 | { |
310 | int *ret = bheap_add(bh, &x); |
311 | |
312 | if (n >= MAX) { |
313 | assert(ret == NULL); |
314 | } else { |
315 | assert(ret == &x); |
316 | |
317 | array[n++] = x; |
318 | } |
319 | |
320 | assert(bheap_count(bh) == n); |
321 | } |
322 | |
323 | void rem(int x) |
324 | { |
325 | int out1, *ret1, out2, *ret2; |
326 | |
327 | ret1 = bheap_topmost(bh, &out1); |
328 | ret2 = bheap_remove(bh, &out2); |
329 | |
330 | if (n == 0) { |
331 | assert(x < 0); /* test the tests! */ |
332 | assert(ret1 == NULL); |
333 | assert(ret2 == NULL); |
334 | } else { |
335 | int i; |
336 | |
337 | assert(x >= 0); /* test the tests! */ |
338 | assert(ret1 == &out1); |
339 | assert(ret2 == &out2); |
340 | assert(out1 == out2); |
341 | assert(out1 == x); |
342 | |
343 | /* Now find x in _our_ array and remove it. */ |
344 | for (i = 0; i < n; i++) { |
345 | assert(array[i] >= x); |
346 | if (array[i] == x) { |
347 | int tmp; |
348 | |
349 | tmp = array[n-1]; |
350 | array[n-1] = array[i]; |
351 | array[i] = tmp; |
352 | |
353 | break; |
354 | } |
355 | } |
356 | assert(i < n); /* we expect to have found it */ |
357 | n--; |
358 | } |
359 | |
360 | assert(bheap_count(bh) == n); |
361 | } |
362 | |
363 | int main(void) |
364 | { |
365 | coverage = checked_coverage = 0; |
366 | |
5a2294f3 |
367 | /* Regression test - this used to report access violations when run under |
368 | * valgrind. */ |
369 | bh = bheap_new(2, sizeof(int), +1, intcmp, &intcmp_ctx); |
370 | add(2); |
371 | add(1); |
372 | rem(1); |
373 | rem(2); |
374 | bheap_free(bh); |
375 | |
80aaeada |
376 | bh = bheap_new(MAX, sizeof(int), +1, intcmp, &intcmp_ctx); |
377 | |
378 | /* |
379 | * Various sets of adds and removes which test all the code |
380 | * paths marked with COVERAGE() statements. |
381 | */ |
382 | CHECK_COVERAGE(2, add(4)); |
383 | CHECK_COVERAGE(3, add(7)); |
384 | CHECK_COVERAGE(4, add(2)); |
385 | CHECK_COVERAGE(1, add(6)); |
386 | add(3); |
387 | add(1); |
388 | CHECK_COVERAGE(5, add(8)); |
389 | add(5); |
390 | CHECK_COVERAGE(0, add(9)); /* check the full-heap case */ |
391 | |
392 | CHECK_COVERAGE(7, rem(1)); |
393 | CHECK_COVERAGE(8, rem(2)); |
394 | CHECK_COVERAGE(9, rem(3)); |
395 | CHECK_COVERAGE(14, rem(4)); |
396 | rem(5); |
397 | rem(6); |
398 | rem(7); |
399 | CHECK_COVERAGE(19, rem(8)); |
400 | CHECK_COVERAGE(6, rem(-1)); /* and check the empty-heap case */ |
401 | CHECK_COVERAGE(8, rem(-1)); /* and check the empty-heap case */ |
402 | |
403 | add(1); |
404 | add(2); |
405 | add(3); |
406 | CHECK_COVERAGE(12, rem(1)); |
407 | rem(2); |
408 | rem(3); |
409 | |
410 | add(1); |
411 | add(3); |
412 | add(2); |
413 | CHECK_COVERAGE(13, rem(1)); |
414 | rem(2); |
415 | rem(3); |
416 | |
417 | add(1); |
418 | add(2); |
419 | add(3); |
420 | add(4); |
421 | CHECK_COVERAGE(17, rem(1)); |
422 | rem(2); |
423 | rem(3); |
424 | rem(4); |
425 | |
426 | add(1); |
427 | add(3); |
428 | add(2); |
429 | add(4); |
430 | CHECK_COVERAGE(16, rem(1)); |
431 | rem(2); |
432 | rem(3); |
433 | rem(4); |
434 | |
435 | add(1); |
436 | add(2); |
437 | add(3); |
438 | add(5); |
439 | add(6); |
440 | add(7); |
441 | add(4); |
442 | CHECK_COVERAGE(18, rem(1)); |
443 | CHECK_COVERAGE(15, rem(2)); |
444 | rem(3); |
445 | CHECK_COVERAGE(10, rem(4)); |
446 | CHECK_COVERAGE(11, rem(5)); |
447 | rem(6); |
448 | rem(7); |
449 | |
450 | /* |
451 | * See what happens with compare equality. |
452 | */ |
453 | add(3); |
454 | add(3); |
455 | add(3); |
456 | add(3); |
457 | add(3); |
458 | add(3); |
459 | add(3); |
460 | add(3); |
461 | rem(3); |
462 | rem(3); |
463 | rem(3); |
464 | rem(3); |
465 | rem(3); |
466 | rem(3); |
467 | rem(3); |
468 | rem(3); |
469 | |
470 | add(5); |
471 | add(4); |
472 | add(7); |
473 | add(4); |
474 | add(1); |
475 | add(4); |
476 | add(3); |
477 | rem(1); |
478 | rem(3); |
479 | rem(4); |
480 | rem(4); |
481 | rem(4); |
482 | rem(5); |
483 | rem(7); |
484 | |
485 | /* |
486 | * Interleave some adds and removes, turning the heap into a |
487 | * real priority queue rather than a glorified sorter. |
488 | * |
489 | * We add the digits of pi in order, and keep the heap size |
490 | * capped at 5 by extracting one before adding the next. |
491 | * |
492 | * Python code that generates this test sequence: |
493 | |
494 | python -c ' |
495 | list=[] |
496 | for c in "314159265358979323846264338327950288": |
497 | c = int(c) |
498 | if len(list) >= 5: |
499 | list.sort() |
500 | d = list[0] |
501 | del list[0] |
502 | print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list)) |
503 | list.append(c) |
504 | list.sort() |
505 | print (" add(%d); /"+"* %s *"+"/") % (c, repr(list)) |
506 | while len(list) > 0: |
507 | list.sort() |
508 | d = list[0] |
509 | del list[0] |
510 | print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list)) |
511 | print " rem(-1);" |
512 | ' |
513 | |
514 | */ |
515 | add(3); /* [3] */ |
516 | add(1); /* [1, 3] */ |
517 | add(4); /* [1, 3, 4] */ |
518 | add(1); /* [1, 1, 3, 4] */ |
519 | add(5); /* [1, 1, 3, 4, 5] */ |
520 | rem(1); /* [1, 3, 4, 5] */ |
521 | add(9); /* [1, 3, 4, 5, 9] */ |
522 | rem(1); /* [3, 4, 5, 9] */ |
523 | add(2); /* [2, 3, 4, 5, 9] */ |
524 | rem(2); /* [3, 4, 5, 9] */ |
525 | add(6); /* [3, 4, 5, 6, 9] */ |
526 | rem(3); /* [4, 5, 6, 9] */ |
527 | add(5); /* [4, 5, 5, 6, 9] */ |
528 | rem(4); /* [5, 5, 6, 9] */ |
529 | add(3); /* [3, 5, 5, 6, 9] */ |
530 | rem(3); /* [5, 5, 6, 9] */ |
531 | add(5); /* [5, 5, 5, 6, 9] */ |
532 | rem(5); /* [5, 5, 6, 9] */ |
533 | add(8); /* [5, 5, 6, 8, 9] */ |
534 | rem(5); /* [5, 6, 8, 9] */ |
535 | add(9); /* [5, 6, 8, 9, 9] */ |
536 | rem(5); /* [6, 8, 9, 9] */ |
537 | add(7); /* [6, 7, 8, 9, 9] */ |
538 | rem(6); /* [7, 8, 9, 9] */ |
539 | add(9); /* [7, 8, 9, 9, 9] */ |
540 | rem(7); /* [8, 9, 9, 9] */ |
541 | add(3); /* [3, 8, 9, 9, 9] */ |
542 | rem(3); /* [8, 9, 9, 9] */ |
543 | add(2); /* [2, 8, 9, 9, 9] */ |
544 | rem(2); /* [8, 9, 9, 9] */ |
545 | add(3); /* [3, 8, 9, 9, 9] */ |
546 | rem(3); /* [8, 9, 9, 9] */ |
547 | add(8); /* [8, 8, 9, 9, 9] */ |
548 | rem(8); /* [8, 9, 9, 9] */ |
549 | add(4); /* [4, 8, 9, 9, 9] */ |
550 | rem(4); /* [8, 9, 9, 9] */ |
551 | add(6); /* [6, 8, 9, 9, 9] */ |
552 | rem(6); /* [8, 9, 9, 9] */ |
553 | add(2); /* [2, 8, 9, 9, 9] */ |
554 | rem(2); /* [8, 9, 9, 9] */ |
555 | add(6); /* [6, 8, 9, 9, 9] */ |
556 | rem(6); /* [8, 9, 9, 9] */ |
557 | add(4); /* [4, 8, 9, 9, 9] */ |
558 | rem(4); /* [8, 9, 9, 9] */ |
559 | add(3); /* [3, 8, 9, 9, 9] */ |
560 | rem(3); /* [8, 9, 9, 9] */ |
561 | add(3); /* [3, 8, 9, 9, 9] */ |
562 | rem(3); /* [8, 9, 9, 9] */ |
563 | add(8); /* [8, 8, 9, 9, 9] */ |
564 | rem(8); /* [8, 9, 9, 9] */ |
565 | add(3); /* [3, 8, 9, 9, 9] */ |
566 | rem(3); /* [8, 9, 9, 9] */ |
567 | add(2); /* [2, 8, 9, 9, 9] */ |
568 | rem(2); /* [8, 9, 9, 9] */ |
569 | add(7); /* [7, 8, 9, 9, 9] */ |
570 | rem(7); /* [8, 9, 9, 9] */ |
571 | add(9); /* [8, 9, 9, 9, 9] */ |
572 | rem(8); /* [9, 9, 9, 9] */ |
573 | add(5); /* [5, 9, 9, 9, 9] */ |
574 | rem(5); /* [9, 9, 9, 9] */ |
575 | add(0); /* [0, 9, 9, 9, 9] */ |
576 | rem(0); /* [9, 9, 9, 9] */ |
577 | add(2); /* [2, 9, 9, 9, 9] */ |
578 | rem(2); /* [9, 9, 9, 9] */ |
579 | add(8); /* [8, 9, 9, 9, 9] */ |
580 | rem(8); /* [9, 9, 9, 9] */ |
581 | add(8); /* [8, 9, 9, 9, 9] */ |
582 | rem(8); /* [9, 9, 9, 9] */ |
583 | rem(9); /* [9, 9, 9] */ |
584 | rem(9); /* [9, 9] */ |
585 | rem(9); /* [9] */ |
586 | rem(9); /* [] */ |
587 | rem(-1); |
588 | |
589 | bheap_free(bh); |
590 | |
591 | { |
592 | int i; |
593 | |
594 | for (i = 0; i < 20; i++) { |
595 | if (!(coverage & (1 << i))) |
596 | printf("coverage is missing %d\n", i); |
597 | else if (!(checked_coverage & (1 << i))) |
598 | printf("checked_coverage is missing %d\n", i); |
599 | } |
600 | } |
601 | |
602 | printf("finished testing, no assertions failed\n"); |
603 | |
604 | return 0; |
605 | } |
606 | |
607 | #endif |