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

   1 /*
   2  * Generic reusable binary-heap maintenance code.
   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.
  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      */
  97     bh->elts = malloc((maxelts + 1) * eltsize);
  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
 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
 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