mdw@git.distorted.org.uk Git - sgt/library/blob - bheap.c

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