From 80aaeadadee69b7b1104e044ab619f65d09b3847 Mon Sep 17 00:00:00 2001 From: simon Date: Wed, 5 Jan 2005 18:08:07 +0000 Subject: [PATCH] There's a possibility I may need a binary heap in the near future, and they're always handy things to have around. So here's a brand new, but decently tested and apparently robust, generic binary heap implementation just in case it comes in handy. git-svn-id: svn://svn.tartarus.org/sgt/library@5065 cda61777-01e9-0310-a592-d414129be87e --- bheap.c | 575 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ bheap.h | 59 +++++++ 2 files changed, 634 insertions(+) create mode 100644 bheap.c create mode 100644 bheap.h diff --git a/bheap.c b/bheap.c new file mode 100644 index 0000000..e0157cd --- /dev/null +++ b/bheap.c @@ -0,0 +1,575 @@ +/* + * Generic reusable binary-heap maintenance code. + */ + +#include +#include +#include "bheap.h" + +#ifdef TESTMODE +int coverage; /* bit flags for various if clauses */ +int checked_coverage; +#define COVERAGE(x) ( coverage |= (1 << (x)) ) +#else +#define COVERAGE(x) ( (void)0 ) +#endif + +struct bheap { + int nelts, maxelts; + int eltsize; + int direction; + bheap_cmpfn_t compare; + void *compare_ctx; + char *elts; +}; + +/* + * Our array is zero-based. Therefore the children of 0 are 1 and + * 2; the children of 1 are 3 and 4; of 2 are 5 and 6, and so on. + * In other words, the children of node n are 2n+1 and 2n+2, and + * the parent of node n is floor((n-1)/2). + */ +#define PARENT(n) ( ((n)-1)/2 ) +#define LCHILD(n) ( 2*(n)+1 ) +#define RCHILD(n) ( 2*(n)+2 ) + +/* + * This macro calls the compare function, and returns TRUE if the + * two elements are the wrong way up and should be swapped. + * + * It doesn't _have_ to be called on a parent and child, but its + * return value assumes that. So you could call it on any two + * elements x,y and it would return TRUE if y ought to be the + * parent of x. + */ +#define MISORDERED(bh,parent,child) \ + ( (bh)->direction * \ + (bh)->compare((bh)->compare_ctx, \ + (bh)->elts + (parent) * (bh)->eltsize, \ + (bh)->elts + (child) * (bh)->eltsize) > 0 ) + +/* + * This macro swaps two elements of the heap. + */ +#define SWAP(bh,x,y) do { \ + memcpy((bh)->elts + (bh)->maxelts * (bh)->eltsize, \ + (bh)->elts + (x) * (bh)->eltsize, (bh)->eltsize); \ + memcpy((bh)->elts + (x) * (bh)->eltsize, \ + (bh)->elts + (y) * (bh)->eltsize, (bh)->eltsize); \ + memcpy((bh)->elts + (y) * (bh)->eltsize, \ + (bh)->elts + (bh)->maxelts * (bh)->eltsize, (bh)->eltsize); \ +} while (0) + +bheap *bheap_new(int maxelts, int eltsize, int direction, + bheap_cmpfn_t compare, void *compare_ctx) +{ + bheap *bh = malloc(sizeof(bheap)); + if (!bh) + return NULL; + + /* + * Allocate one extra element of space, to use for swapping + * things. + */ + bh->elts = malloc(maxelts * (eltsize+1)); + if (!bh->elts) + return NULL; + + bh->nelts = 0; + bh->maxelts = maxelts; + bh->eltsize = eltsize; + bh->direction = direction; + bh->compare = compare; + bh->compare_ctx = compare_ctx; + + return bh; +} + +void *bheap_add(bheap *bh, void *elt) +{ + int i; + + if (bh->nelts >= bh->maxelts) { + COVERAGE(0); + return NULL; + } + + COVERAGE(1); + /* + * Add the element to the end of the array. + */ + memcpy(bh->elts + bh->nelts * bh->eltsize, elt, bh->eltsize); + bh->nelts++; + + /* + * Now swap it with its parent repeatedly to preserve the heap + * property. + */ + i = bh->nelts-1; + + if (i == 0) + COVERAGE(2); + + while (i > 0) { + int p = PARENT(i); + + COVERAGE(3); + + if (MISORDERED(bh, p, i)) { + COVERAGE(4); + SWAP(bh, p, i); + i = p; + } else { + COVERAGE(5); + break; /* we're done */ + } + } + + return elt; +} + +void *bheap_topmost(bheap *bh, void *elt) +{ + if (bh->nelts <= 0) { + COVERAGE(6); + return NULL; + } + + COVERAGE(7); + memcpy(elt, bh->elts, bh->eltsize); + return elt; +} + +void *bheap_remove(bheap *bh, void *elt) +{ + if (bh->nelts <= 0) { + COVERAGE(8); + return NULL; + } + + if (elt) + memcpy(elt, bh->elts, bh->eltsize); + + bh->nelts--; + + if (bh->nelts > 0) { + int i; + + COVERAGE(8); + /* + * Move the highest-index element of the heap into the top + * position. + */ + SWAP(bh, bh->nelts, 0); + + /* + * Now repeatedly move it down the heap by swapping it with + * the more suitable of its children. + */ + i = 0; + while (1) { + int lc, rc; + + lc = LCHILD(i); + rc = RCHILD(i); + + COVERAGE(9); + + if (lc >= bh->nelts) { + COVERAGE(10); + break; /* we've hit bottom */ + } + + if (rc >= bh->nelts) { + /* + * Special case: there is only one child to check. + */ + COVERAGE(11); + if (MISORDERED(bh, i, lc)) { + COVERAGE(12); + SWAP(bh, i, lc); + } else { + COVERAGE(13); + } + /* _Now_ we've hit bottom. */ + break; + } else { + COVERAGE(14); + /* + * The common case: there are two children and we + * must check them both. + */ + if (MISORDERED(bh, i, lc) || MISORDERED(bh, i, rc)) { + COVERAGE(15); + /* + * Pick the more appropriate child to swap with + * (i.e. the one which would want to be the + * parent if one were above the other - as one + * is about to be). + */ + if (MISORDERED(bh, lc, rc)) { + COVERAGE(16); + SWAP(bh, i, rc); + i = rc; + } else { + COVERAGE(17); + SWAP(bh, i, lc); + i = lc; + } + } else { + /* This element is in the right place; we're done. */ + COVERAGE(18); + break; + } + } + } + } else { + COVERAGE(19); + } + + return elt; +} + +int bheap_count(bheap *bh) +{ + return bh->nelts; +} + +void bheap_free(bheap *bh) +{ + if (bh) { + if (bh->elts) + free(bh->elts); + free(bh); + } +} + +#ifdef TESTMODE + +#include + +/* we _really_ need assertions enabled, for this test */ +#undef NDEBUG +#include + +#define MAX 8 + +#define CHECK_COVERAGE(c, statement) do { \ + coverage &= ~ (1 << (c)); \ + statement; \ + assert(coverage & (1 << (c))); \ + checked_coverage |= (1 << (c)); \ +} while (0) + +int intcmp_ctx; +int array[MAX]; +int n; + +bheap *bh; + +int intcmp(void *vctx, const void *av, const void *bv) +{ + const int *a = (const int *)av; + const int *b = (const int *)bv; + int *ctx = (int *)vctx; + + assert(ctx == &intcmp_ctx); + + if (*a < *b) + return -1; + else if (*a > *b) + return +1; + return 0; +} + +void add(int x) +{ + int *ret = bheap_add(bh, &x); + + if (n >= MAX) { + assert(ret == NULL); + } else { + assert(ret == &x); + + array[n++] = x; + } + + assert(bheap_count(bh) == n); +} + +void rem(int x) +{ + int out1, *ret1, out2, *ret2; + + ret1 = bheap_topmost(bh, &out1); + ret2 = bheap_remove(bh, &out2); + + if (n == 0) { + assert(x < 0); /* test the tests! */ + assert(ret1 == NULL); + assert(ret2 == NULL); + } else { + int i; + + assert(x >= 0); /* test the tests! */ + assert(ret1 == &out1); + assert(ret2 == &out2); + assert(out1 == out2); + assert(out1 == x); + + /* Now find x in _our_ array and remove it. */ + for (i = 0; i < n; i++) { + assert(array[i] >= x); + if (array[i] == x) { + int tmp; + + tmp = array[n-1]; + array[n-1] = array[i]; + array[i] = tmp; + + break; + } + } + assert(i < n); /* we expect to have found it */ + n--; + } + + assert(bheap_count(bh) == n); +} + +int main(void) +{ + coverage = checked_coverage = 0; + + bh = bheap_new(MAX, sizeof(int), +1, intcmp, &intcmp_ctx); + + /* + * Various sets of adds and removes which test all the code + * paths marked with COVERAGE() statements. + */ + CHECK_COVERAGE(2, add(4)); + CHECK_COVERAGE(3, add(7)); + CHECK_COVERAGE(4, add(2)); + CHECK_COVERAGE(1, add(6)); + add(3); + add(1); + CHECK_COVERAGE(5, add(8)); + add(5); + CHECK_COVERAGE(0, add(9)); /* check the full-heap case */ + + CHECK_COVERAGE(7, rem(1)); + CHECK_COVERAGE(8, rem(2)); + CHECK_COVERAGE(9, rem(3)); + CHECK_COVERAGE(14, rem(4)); + rem(5); + rem(6); + rem(7); + CHECK_COVERAGE(19, rem(8)); + CHECK_COVERAGE(6, rem(-1)); /* and check the empty-heap case */ + CHECK_COVERAGE(8, rem(-1)); /* and check the empty-heap case */ + + add(1); + add(2); + add(3); + CHECK_COVERAGE(12, rem(1)); + rem(2); + rem(3); + + add(1); + add(3); + add(2); + CHECK_COVERAGE(13, rem(1)); + rem(2); + rem(3); + + add(1); + add(2); + add(3); + add(4); + CHECK_COVERAGE(17, rem(1)); + rem(2); + rem(3); + rem(4); + + add(1); + add(3); + add(2); + add(4); + CHECK_COVERAGE(16, rem(1)); + rem(2); + rem(3); + rem(4); + + add(1); + add(2); + add(3); + add(5); + add(6); + add(7); + add(4); + CHECK_COVERAGE(18, rem(1)); + CHECK_COVERAGE(15, rem(2)); + rem(3); + CHECK_COVERAGE(10, rem(4)); + CHECK_COVERAGE(11, rem(5)); + rem(6); + rem(7); + + /* + * See what happens with compare equality. + */ + add(3); + add(3); + add(3); + add(3); + add(3); + add(3); + add(3); + add(3); + rem(3); + rem(3); + rem(3); + rem(3); + rem(3); + rem(3); + rem(3); + rem(3); + + add(5); + add(4); + add(7); + add(4); + add(1); + add(4); + add(3); + rem(1); + rem(3); + rem(4); + rem(4); + rem(4); + rem(5); + rem(7); + + /* + * Interleave some adds and removes, turning the heap into a + * real priority queue rather than a glorified sorter. + * + * We add the digits of pi in order, and keep the heap size + * capped at 5 by extracting one before adding the next. + * + * Python code that generates this test sequence: + +python -c ' +list=[] +for c in "314159265358979323846264338327950288": + c = int(c) + if len(list) >= 5: + list.sort() + d = list[0] + del list[0] + print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list)) + list.append(c) + list.sort() + print (" add(%d); /"+"* %s *"+"/") % (c, repr(list)) +while len(list) > 0: + list.sort() + d = list[0] + del list[0] + print (" rem(%d); /"+"* %s *"+"/") % (d, repr(list)) +print " rem(-1);" +' + + */ + add(3); /* [3] */ + add(1); /* [1, 3] */ + add(4); /* [1, 3, 4] */ + add(1); /* [1, 1, 3, 4] */ + add(5); /* [1, 1, 3, 4, 5] */ + rem(1); /* [1, 3, 4, 5] */ + add(9); /* [1, 3, 4, 5, 9] */ + rem(1); /* [3, 4, 5, 9] */ + add(2); /* [2, 3, 4, 5, 9] */ + rem(2); /* [3, 4, 5, 9] */ + add(6); /* [3, 4, 5, 6, 9] */ + rem(3); /* [4, 5, 6, 9] */ + add(5); /* [4, 5, 5, 6, 9] */ + rem(4); /* [5, 5, 6, 9] */ + add(3); /* [3, 5, 5, 6, 9] */ + rem(3); /* [5, 5, 6, 9] */ + add(5); /* [5, 5, 5, 6, 9] */ + rem(5); /* [5, 5, 6, 9] */ + add(8); /* [5, 5, 6, 8, 9] */ + rem(5); /* [5, 6, 8, 9] */ + add(9); /* [5, 6, 8, 9, 9] */ + rem(5); /* [6, 8, 9, 9] */ + add(7); /* [6, 7, 8, 9, 9] */ + rem(6); /* [7, 8, 9, 9] */ + add(9); /* [7, 8, 9, 9, 9] */ + rem(7); /* [8, 9, 9, 9] */ + add(3); /* [3, 8, 9, 9, 9] */ + rem(3); /* [8, 9, 9, 9] */ + add(2); /* [2, 8, 9, 9, 9] */ + rem(2); /* [8, 9, 9, 9] */ + add(3); /* [3, 8, 9, 9, 9] */ + rem(3); /* [8, 9, 9, 9] */ + add(8); /* [8, 8, 9, 9, 9] */ + rem(8); /* [8, 9, 9, 9] */ + add(4); /* [4, 8, 9, 9, 9] */ + rem(4); /* [8, 9, 9, 9] */ + add(6); /* [6, 8, 9, 9, 9] */ + rem(6); /* [8, 9, 9, 9] */ + add(2); /* [2, 8, 9, 9, 9] */ + rem(2); /* [8, 9, 9, 9] */ + add(6); /* [6, 8, 9, 9, 9] */ + rem(6); /* [8, 9, 9, 9] */ + add(4); /* [4, 8, 9, 9, 9] */ + rem(4); /* [8, 9, 9, 9] */ + add(3); /* [3, 8, 9, 9, 9] */ + rem(3); /* [8, 9, 9, 9] */ + add(3); /* [3, 8, 9, 9, 9] */ + rem(3); /* [8, 9, 9, 9] */ + add(8); /* [8, 8, 9, 9, 9] */ + rem(8); /* [8, 9, 9, 9] */ + add(3); /* [3, 8, 9, 9, 9] */ + rem(3); /* [8, 9, 9, 9] */ + add(2); /* [2, 8, 9, 9, 9] */ + rem(2); /* [8, 9, 9, 9] */ + add(7); /* [7, 8, 9, 9, 9] */ + rem(7); /* [8, 9, 9, 9] */ + add(9); /* [8, 9, 9, 9, 9] */ + rem(8); /* [9, 9, 9, 9] */ + add(5); /* [5, 9, 9, 9, 9] */ + rem(5); /* [9, 9, 9, 9] */ + add(0); /* [0, 9, 9, 9, 9] */ + rem(0); /* [9, 9, 9, 9] */ + add(2); /* [2, 9, 9, 9, 9] */ + rem(2); /* [9, 9, 9, 9] */ + add(8); /* [8, 9, 9, 9, 9] */ + rem(8); /* [9, 9, 9, 9] */ + add(8); /* [8, 9, 9, 9, 9] */ + rem(8); /* [9, 9, 9, 9] */ + rem(9); /* [9, 9, 9] */ + rem(9); /* [9, 9] */ + rem(9); /* [9] */ + rem(9); /* [] */ + rem(-1); + + bheap_free(bh); + + { + int i; + + for (i = 0; i < 20; i++) { + if (!(coverage & (1 << i))) + printf("coverage is missing %d\n", i); + else if (!(checked_coverage & (1 << i))) + printf("checked_coverage is missing %d\n", i); + } + } + + printf("finished testing, no assertions failed\n"); + + return 0; +} + +#endif diff --git a/bheap.h b/bheap.h new file mode 100644 index 0000000..8e3d92c --- /dev/null +++ b/bheap.h @@ -0,0 +1,59 @@ +/* + * Header file for bheap.c. + */ + +#ifndef BHEAP_H +#define BHEAP_H + +typedef struct bheap bheap; + +typedef int (*bheap_cmpfn_t)(void *ctx, const void *x, const void *y); + +/* + * Create a new binary heap, of maximum size `maxelts'. `eltsize' + * is the size of each element (use `sizeof'). `compare' is the + * function that determines the ordering between elements; + * `compare_ctx' is passed as its first argument. + * + * If `direction' is +1, the heap sorts the largest things to the + * top, so it can return the largest element easily. If it's -1, + * the heap sorts the smallest things to the top. + */ +bheap *bheap_new(int maxelts, int eltsize, int direction, + bheap_cmpfn_t compare, void *compare_ctx); + +/* + * Add an element to the heap. Returns `elt', or NULL if the heap + * is full. + */ +void *bheap_add(bheap *bh, void *elt); + +/* + * Non-destructively read the topmost element in the heap and store + * it at `elt'. Returns `elt', or NULL if the heap is empty. + */ +void *bheap_topmost(bheap *bh, void *elt); + +/* + * Remove, and optionally also read, the topmost element in the + * heap. Stores it at `elt' if `elt' is not itself NULL. + * + * Returns `elt', or NULL if the heap is empty. Note that if you + * pass elt==NULL the two cases can therefore not be distinguished! + */ +void *bheap_remove(bheap *bh, void *elt); + +/* + * Count the number of elements currently in the heap. + */ +int bheap_count(bheap *bh); + +/* + * Destroy a heap. If the elements in the heap need freeing, you'd + * better make sure there aren't any left before calling this + * function, because the heap code won't know about it and won't do + * anything. + */ +void bheap_free(bheap *bh); + +#endif /* BHEAP_H */ -- 2.11.0