tree234.c

   1 /*
   2  * tree234.c: reasonably generic 2-3-4 tree routines. Currently
   3  * supports insert, delete, find and iterate operations.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 #include "tree234.h"
  10
  11 #define mknew(typ) ( (typ *) malloc (sizeof (typ)) )
  12 #define sfree free
  13
  14 #ifdef TEST
  15 #define LOG(x) (printf x)
  16 #else
  17 #define LOG(x)
  18 #endif
  19
  20 struct tree234_Tag {
  21     node234 *root;
  22     cmpfn234 cmp;
  23 };
  24
  25 struct node234_Tag {
  26     node234 *parent;
  27     node234 *kids[4];
  28     void *elems[3];
  29 };
  30
  31 /*
  32  * Create a 2-3-4 tree.
  33  */
  34 tree234 *newtree234(cmpfn234 cmp) {
  35     tree234 *ret = mknew(tree234);
  36     LOG(("created tree %p\n", ret));
  37     ret->root = NULL;
  38     ret->cmp = cmp;
  39     return ret;
  40 }
  41
  42 /*
  43  * Free a 2-3-4 tree (not including freeing the elements).
  44  */
  45 static void freenode234(node234 *n) {
  46     if (!n)
  47         return;
  48     freenode234(n->kids[0]);
  49     freenode234(n->kids[1]);
  50     freenode234(n->kids[2]);
  51     freenode234(n->kids[3]);
  52     sfree(n);
  53 }
  54 void freetree234(tree234 *t) {
  55     freenode234(t->root);
  56     sfree(t);
  57 }
  58
  59 /*
  60  * Add an element e to a 2-3-4 tree t. Returns e on success, or if
  61  * an existing element compares equal, returns that.
  62  */
  63 void *add234(tree234 *t, void *e) {
  64     node234 *n, **np, *left, *right;
  65     void *orig_e = e;
  66     int c;
  67
  68     LOG(("adding node %p to tree %p\n", e, t));
  69     if (t->root == NULL) {
  70         t->root = mknew(node234);
  71         t->root->elems[1] = t->root->elems[2] = NULL;
  72         t->root->kids[0] = t->root->kids[1] = NULL;
  73         t->root->kids[2] = t->root->kids[3] = NULL;
  74         t->root->parent = NULL;
  75         t->root->elems[0] = e;
  76         LOG(("  created root %p\n", t->root));
  77         return orig_e;
  78     }
  79
  80     np = &t->root;
  81     while (*np) {
  82         n = *np;
  83         LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
  84              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
  85              n->kids[2], n->elems[2], n->kids[3]));
  86         if ((c = t->cmp(e, n->elems[0])) < 0)
  87             np = &n->kids[0];
  88         else if (c == 0)
  89             return n->elems[0];        /* already exists */
  90         else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
  91             np = &n->kids[1];
  92         else if (c == 0)
  93             return n->elems[1];        /* already exists */
  94         else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
  95             np = &n->kids[2];
  96         else if (c == 0)
  97             return n->elems[2];        /* already exists */
  98         else
  99             np = &n->kids[3];
 100         LOG(("  moving to child %d (%p)\n", np - n->kids, *np));
 101     }
 102
 103     /*
 104      * We need to insert the new element in n at position np.
 105      */
 106     left = NULL;
 107     right = NULL;
 108     while (n) {
 109         LOG(("  at %p: %p [%p] %p [%p] %p [%p] %p\n",
 110              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 111              n->kids[2], n->elems[2], n->kids[3]));
 112         LOG(("  need to insert %p [%p] %p at position %d\n",
 113              left, e, right, np - n->kids));
 114         if (n->elems[1] == NULL) {
 115             /*
 116              * Insert in a 2-node; simple.
 117              */
 118             if (np == &n->kids[0]) {
 119                 LOG(("  inserting on left of 2-node\n"));
 120                 n->kids[2] = n->kids[1];
 121                 n->elems[1] = n->elems[0];
 122                 n->kids[1] = right;
 123                 n->elems[0] = e;
 124                 n->kids[0] = left;
 125             } else { /* np == &n->kids[1] */
 126                 LOG(("  inserting on right of 2-node\n"));
 127                 n->kids[2] = right;
 128                 n->elems[1] = e;
 129                 n->kids[1] = left;
 130             }
 131             if (n->kids[0]) n->kids[0]->parent = n;
 132             if (n->kids[1]) n->kids[1]->parent = n;
 133             if (n->kids[2]) n->kids[2]->parent = n;
 134             LOG(("  done\n"));
 135             break;
 136         } else if (n->elems[2] == NULL) {
 137             /*
 138              * Insert in a 3-node; simple.
 139              */
 140             if (np == &n->kids[0]) {
 141                 LOG(("  inserting on left of 3-node\n"));
 142                 n->kids[3] = n->kids[2];
 143                 n->elems[2] = n->elems[1];
 144                 n->kids[2] = n->kids[1];
 145                 n->elems[1] = n->elems[0];
 146                 n->kids[1] = right;
 147                 n->elems[0] = e;
 148                 n->kids[0] = left;
 149             } else if (np == &n->kids[1]) {
 150                 LOG(("  inserting in middle of 3-node\n"));
 151                 n->kids[3] = n->kids[2];
 152                 n->elems[2] = n->elems[1];
 153                 n->kids[2] = right;
 154                 n->elems[1] = e;
 155                 n->kids[1] = left;
 156             } else { /* np == &n->kids[2] */
 157                 LOG(("  inserting on right of 3-node\n"));
 158                 n->kids[3] = right;
 159                 n->elems[2] = e;
 160                 n->kids[2] = left;
 161             }
 162             if (n->kids[0]) n->kids[0]->parent = n;
 163             if (n->kids[1]) n->kids[1]->parent = n;
 164             if (n->kids[2]) n->kids[2]->parent = n;
 165             if (n->kids[3]) n->kids[3]->parent = n;
 166             LOG(("  done\n"));
 167             break;
 168         } else {
 169             node234 *m = mknew(node234);
 170             m->parent = n->parent;
 171             LOG(("  splitting a 4-node; created new node %p\n", m));
 172             /*
 173              * Insert in a 4-node; split into a 2-node and a
 174              * 3-node, and move focus up a level.
 175              *
 176              * I don't think it matters which way round we put the
 177              * 2 and the 3. For simplicity, we'll put the 3 first
 178              * always.
 179              */
 180             if (np == &n->kids[0]) {
 181                 m->kids[0] = left;
 182                 m->elems[0] = e;
 183                 m->kids[1] = right;
 184                 m->elems[1] = n->elems[0];
 185                 m->kids[2] = n->kids[1];
 186                 e = n->elems[1];
 187                 n->kids[0] = n->kids[2];
 188                 n->elems[0] = n->elems[2];
 189                 n->kids[1] = n->kids[3];
 190             } else if (np == &n->kids[1]) {
 191                 m->kids[0] = n->kids[0];
 192                 m->elems[0] = n->elems[0];
 193                 m->kids[1] = left;
 194                 m->elems[1] = e;
 195                 m->kids[2] = right;
 196                 e = n->elems[1];
 197                 n->kids[0] = n->kids[2];
 198                 n->elems[0] = n->elems[2];
 199                 n->kids[1] = n->kids[3];
 200             } else if (np == &n->kids[2]) {
 201                 m->kids[0] = n->kids[0];
 202                 m->elems[0] = n->elems[0];
 203                 m->kids[1] = n->kids[1];
 204                 m->elems[1] = n->elems[1];
 205                 m->kids[2] = left;
 206                 /* e = e; */
 207                 n->kids[0] = right;
 208                 n->elems[0] = n->elems[2];
 209                 n->kids[1] = n->kids[3];
 210             } else { /* np == &n->kids[3] */
 211                 m->kids[0] = n->kids[0];
 212                 m->elems[0] = n->elems[0];
 213                 m->kids[1] = n->kids[1];
 214                 m->elems[1] = n->elems[1];
 215                 m->kids[2] = n->kids[2];
 216                 n->kids[0] = left;
 217                 n->elems[0] = e;
 218                 n->kids[1] = right;
 219                 e = n->elems[2];
 220             }
 221             m->kids[3] = n->kids[3] = n->kids[2] = NULL;
 222             m->elems[2] = n->elems[2] = n->elems[1] = NULL;
 223             if (m->kids[0]) m->kids[0]->parent = m;
 224             if (m->kids[1]) m->kids[1]->parent = m;
 225             if (m->kids[2]) m->kids[2]->parent = m;
 226             if (n->kids[0]) n->kids[0]->parent = n;
 227             if (n->kids[1]) n->kids[1]->parent = n;
 228             LOG(("  left (%p): %p [%p] %p [%p] %p\n", m,
 229                  m->kids[0], m->elems[0],
 230                  m->kids[1], m->elems[1],
 231                  m->kids[2]));
 232             LOG(("  right (%p): %p [%p] %p\n", n,
 233                  n->kids[0], n->elems[0],
 234                  n->kids[1]));
 235             left = m;
 236             right = n;
 237         }
 238         if (n->parent)
 239             np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
 240                   n->parent->kids[1] == n ? &n->parent->kids[1] :
 241                   n->parent->kids[2] == n ? &n->parent->kids[2] :
 242                   &n->parent->kids[3]);
 243         n = n->parent;
 244     }
 245
 246     /*
 247      * If we've come out of here by `break', n will still be
 248      * non-NULL and we've finished. If we've come here because n is
 249      * NULL, we need to create a new root for the tree because the
 250      * old one has just split into two.
 251      */
 252     if (!n) {
 253         LOG(("  root is overloaded, split into two\n"));
 254         t->root = mknew(node234);
 255         t->root->kids[0] = left;
 256         t->root->elems[0] = e;
 257         t->root->kids[1] = right;
 258         t->root->elems[1] = NULL;
 259         t->root->kids[2] = NULL;
 260         t->root->elems[2] = NULL;
 261         t->root->kids[3] = NULL;
 262         t->root->parent = NULL;
 263         if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
 264         if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
 265         LOG(("  new root is %p [%p] %p\n",
 266              t->root->kids[0], t->root->elems[0], t->root->kids[1]));
 267     }
 268
 269     return orig_e;
 270 }
 271
 272 /*
 273  * Find an element e in a 2-3-4 tree t. Returns NULL if not found.
 274  * e is always passed as the first argument to cmp, so cmp can be
 275  * an asymmetric function if desired. cmp can also be passed as
 276  * NULL, in which case the compare function from the tree proper
 277  * will be used.
 278  */
 279 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
 280     node234 *n;
 281     int c;
 282
 283     if (t->root == NULL)
 284         return NULL;
 285
 286     if (cmp == NULL)
 287         cmp = t->cmp;
 288
 289     n = t->root;
 290     while (n) {
 291         if ( (c = cmp(e, n->elems[0])) < 0)
 292             n = n->kids[0];
 293         else if (c == 0)
 294             return n->elems[0];
 295         else if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
 296             n = n->kids[1];
 297         else if (c == 0)
 298             return n->elems[1];
 299         else if (n->elems[2] == NULL || (c = cmp(e, n->elems[2])) < 0)
 300             n = n->kids[2];
 301         else if (c == 0)
 302             return n->elems[2];
 303         else
 304             n = n->kids[3];
 305     }
 306
 307     /*
 308      * We've found our way to the bottom of the tree and we know
 309      * where we would insert this node if we wanted to. But it
 310      * isn't there.
 311      */
 312     return NULL;
 313 }
 314
 315 /*
 316  * Delete an element e in a 2-3-4 tree. Does not free the element,
 317  * merely removes all links to it from the tree nodes.
 318  */
 319 void del234(tree234 *t, void *e) {
 320     node234 *n;
 321     int ei = -1;
 322
 323     n = t->root;
 324     LOG(("deleting %p from tree %p\n", e, t));
 325     while (1) {
 326         while (n) {
 327             int c;
 328             int ki;
 329             node234 *sub;
 330
 331             LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
 332                  n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 333                  n->kids[2], n->elems[2], n->kids[3]));
 334             if ((c = t->cmp(e, n->elems[0])) < 0) {
 335                 ki = 0;
 336             } else if (c == 0) {
 337                 ei = 0; break;
 338             } else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0) {
 339                 ki = 1;
 340             } else if (c == 0) {
 341                 ei = 1; break;
 342             } else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0) {
 343                 ki = 2;
 344             } else if (c == 0) {
 345                 ei = 2; break;
 346             } else {
 347                 ki = 3;
 348             }
 349             /*
 350              * Recurse down to subtree ki. If it has only one element,
 351              * we have to do some transformation to start with.
 352              */
 353             LOG(("  moving to subtree %d\n", ki));
 354             sub = n->kids[ki];
 355             if (!sub->elems[1]) {
 356                 LOG(("  subtree has only one element!\n", ki));
 357                 if (ki > 0 && n->kids[ki-1]->elems[1]) {
 358                     /*
 359                      * Case 3a, left-handed variant. Child ki has
 360                      * only one element, but child ki-1 has two or
 361                      * more. So we need to move a subtree from ki-1
 362                      * to ki.
 363                      *
 364                      *                . C .                     . B .
 365                      *               /     \     ->            /     \
 366                      * [more] a A b B c   d D e      [more] a A b   c C d D e
 367                      */
 368                     node234 *sib = n->kids[ki-1];
 369                     int lastelem = (sib->elems[2] ? 2 :
 370                                     sib->elems[1] ? 1 : 0);
 371                     sub->kids[2] = sub->kids[1];
 372                     sub->elems[1] = sub->elems[0];
 373                     sub->kids[1] = sub->kids[0];
 374                     sub->elems[0] = n->elems[ki-1];
 375                     sub->kids[0] = sib->kids[lastelem+1];
 376                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 377                     n->elems[ki-1] = sib->elems[lastelem];
 378                     sib->kids[lastelem+1] = NULL;
 379                     sib->elems[lastelem] = NULL;
 380                     LOG(("  case 3a left\n"));
 381                 } else if (ki < 3 && n->kids[ki+1] &&
 382                            n->kids[ki+1]->elems[1]) {
 383                     /*
 384                      * Case 3a, right-handed variant. ki has only
 385                      * one element but ki+1 has two or more. Move a
 386                      * subtree from ki+1 to ki.
 387                      *
 388                      *      . B .                             . C .
 389                      *     /     \                ->         /     \
 390                      *  a A b   c C d D e [more]      a A b B c   d D e [more]
 391                      */
 392                     node234 *sib = n->kids[ki+1];
 393                     int j;
 394                     sub->elems[1] = n->elems[ki];
 395                     sub->kids[2] = sib->kids[0];
 396                     if (sub->kids[2]) sub->kids[2]->parent = sub;
 397                     n->elems[ki] = sib->elems[0];
 398                     sib->kids[0] = sib->kids[1];
 399                     for (j = 0; j < 2 && sib->elems[j+1]; j++) {
 400                         sib->kids[j+1] = sib->kids[j+2];
 401                         sib->elems[j] = sib->elems[j+1];
 402                     }
 403                     sib->kids[j+1] = NULL;
 404                     sib->elems[j] = NULL;
 405                     LOG(("  case 3a right\n"));
 406                 } else {
 407                     /*
 408                      * Case 3b. ki has only one element, and has no
 409                      * neighbour with more than one. So pick a
 410                      * neighbour and merge it with ki, taking an
 411                      * element down from n to go in the middle.
 412                      *
 413                      *      . B .                .
 414                      *     /     \     ->        |
 415                      *  a A b   c C d      a A b B c C d
 416                      *
 417                      * (Since at all points we have avoided
 418                      * descending to a node with only one element,
 419                      * we can be sure that n is not reduced to
 420                      * nothingness by this move, _unless_ it was
 421                      * the very first node, ie the root of the
 422                      * tree. In that case we remove the now-empty
 423                      * root and replace it with its single large
 424                      * child as shown.)
 425                      */
 426                     node234 *sib;
 427                     int j;
 428
 429                     if (ki > 0)
 430                         ki--;
 431                     sib = n->kids[ki];
 432                     sub = n->kids[ki+1];
 433
 434                     sub->kids[3] = sub->kids[1];
 435                     sub->elems[2] = sub->elems[0];
 436                     sub->kids[2] = sub->kids[0];
 437                     sub->elems[1] = n->elems[ki];
 438                     sub->kids[1] = sib->kids[1];
 439                     if (sub->kids[1]) sub->kids[1]->parent = sub;
 440                     sub->elems[0] = sib->elems[0];
 441                     sub->kids[0] = sib->kids[0];
 442                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 443
 444                     sfree(sib);
 445
 446                     /*
 447                      * That's built the big node in sub. Now we
 448                      * need to remove the reference to sib in n.
 449                      */
 450                     for (j = ki; j < 3 && n->kids[j+1]; j++) {
 451                         n->kids[j] = n->kids[j+1];
 452                         n->elems[j] = j<2 ? n->elems[j+1] : NULL;
 453                     }
 454                     n->kids[j] = NULL;
 455                     if (j < 3) n->elems[j] = NULL;
 456                     LOG(("  case 3b ki=%d\n", ki));
 457
 458                     if (!n->elems[0]) {
 459                         /*
 460                          * The root is empty and needs to be
 461                          * removed.
 462                          */
 463                         LOG(("  shifting root!\n"));
 464                         t->root = sub;
 465                         sub->parent = NULL;
 466                         sfree(n);
 467                     }
 468                 }
 469             }
 470             n = sub;
 471         }
 472         if (ei==-1)
 473             return;                    /* nothing to do; `already removed' */
 474
 475         /*
 476          * Treat special case: this is the one remaining item in
 477          * the tree. n is the tree root (no parent), has one
 478          * element (no elems[1]), and has no kids (no kids[0]).
 479          */
 480         if (!n->parent && !n->elems[1] && !n->kids[0]) {
 481             LOG(("  removed last element in tree\n"));
 482             sfree(n);
 483             t->root = NULL;
 484             return;
 485         }
 486
 487         /*
 488          * Now we have the element we want, as n->elems[ei], and we
 489          * have also arranged for that element not to be the only
 490          * one in its node. So...
 491          */
 492
 493         if (!n->kids[0] && n->elems[1]) {
 494             /*
 495              * Case 1. n is a leaf node with more than one element,
 496              * so it's _really easy_. Just delete the thing and
 497              * we're done.
 498              */
 499             int i;
 500             LOG(("  case 1\n"));
 501             for (i = ei; i < 2 && n->elems[i+1]; i++)
 502                 n->elems[i] = n->elems[i+1];
 503             n->elems[i] = NULL;
 504             return;                    /* finished! */
 505         } else if (n->kids[ei]->elems[1]) {
 506             /*
 507              * Case 2a. n is an internal node, and the root of the
 508              * subtree to the left of e has more than one element.
 509              * So find the predecessor p to e (ie the largest node
 510              * in that subtree), place it where e currently is, and
 511              * then start the deletion process over again on the
 512              * subtree with p as target.
 513              */
 514             node234 *m = n->kids[ei];
 515             void *target;
 516             LOG(("  case 2a\n"));
 517             while (m->kids[0]) {
 518                 m = (m->kids[3] ? m->kids[3] :
 519                      m->kids[2] ? m->kids[2] :
 520                      m->kids[1] ? m->kids[1] : m->kids[0]);
 521             }
 522             target = (m->elems[2] ? m->elems[2] :
 523                       m->elems[1] ? m->elems[1] : m->elems[0]);
 524             n->elems[ei] = target;
 525             n = n->kids[ei];
 526             e = target;
 527         } else if (n->kids[ei+1]->elems[1]) {
 528             /*
 529              * Case 2b, symmetric to 2a but s/left/right/ and
 530              * s/predecessor/successor/. (And s/largest/smallest/).
 531              */
 532             node234 *m = n->kids[ei+1];
 533             void *target;
 534             LOG(("  case 2b\n"));
 535             while (m->kids[0]) {
 536                 m = m->kids[0];
 537             }
 538             target = m->elems[0];
 539             n->elems[ei] = target;
 540             n = n->kids[ei+1];
 541             e = target;
 542         } else {
 543             /*
 544              * Case 2c. n is an internal node, and the subtrees to
 545              * the left and right of e both have only one element.
 546              * So combine the two subnodes into a single big node
 547              * with their own elements on the left and right and e
 548              * in the middle, then restart the deletion process on
 549              * that subtree, with e still as target.
 550              */
 551             node234 *a = n->kids[ei], *b = n->kids[ei+1];
 552             int j;
 553
 554             LOG(("  case 2c\n"));
 555             a->elems[1] = n->elems[ei];
 556             a->kids[2] = b->kids[0];
 557             if (a->kids[2]) a->kids[2]->parent = a;
 558             a->elems[2] = b->elems[0];
 559             a->kids[3] = b->kids[1];
 560             if (a->kids[3]) a->kids[3]->parent = a;
 561             sfree(b);
 562             /*
 563              * That's built the big node in a, and destroyed b. Now
 564              * remove the reference to b (and e) in n.
 565              */
 566             for (j = ei; j < 2 && n->elems[j+1]; j++) {
 567                 n->elems[j] = n->elems[j+1];
 568                 n->kids[j+1] = n->kids[j+2];
 569             }
 570             n->elems[j] = NULL;
 571             n->kids[j+1] = NULL;
 572             /*
 573              * It's possible, in this case, that we've just removed
 574              * the only element in the root of the tree. If so,
 575              * shift the root.
 576              */
 577             if (n->elems[0] == NULL) {
 578                 LOG(("  shifting root!\n"));
 579                 t->root = a;
 580                 a->parent = NULL;
 581                 sfree(n);
 582             }
 583             /*
 584              * Now go round the deletion process again, with n
 585              * pointing at the new big node and e still the same.
 586              */
 587             n = a;
 588         }
 589     }
 590 }
 591
 592 /*
 593  * Iterate over the elements of a tree234, in order.
 594  */
 595 void *first234(tree234 *t, enum234 *e) {
 596     node234 *n = t->root;
 597     if (!n)
 598         return NULL;
 599     while (n->kids[0])
 600         n = n->kids[0];
 601     e->node = n;
 602     e->posn = 0;
 603     return n->elems[0];
 604 }
 605
 606 void *next234(enum234 *e) {
 607     node234 *n = e->node;
 608     int pos = e->posn;
 609
 610     if (n->kids[pos+1]) {
 611         n = n->kids[pos+1];
 612         while (n->kids[0])
 613             n = n->kids[0];
 614         e->node = n;
 615         e->posn = 0;
 616         return n->elems[0];
 617     }
 618
 619     if (pos < 2 && n->elems[pos+1]) {
 620         e->posn = pos+1;
 621         return n->elems[e->posn];
 622     }
 623
 624     do {
 625         node234 *nn = n->parent;
 626         if (nn == NULL)
 627             return NULL;               /* end of tree */
 628         pos = (nn->kids[0] == n ? 0 :
 629                nn->kids[1] == n ? 1 :
 630                nn->kids[2] == n ? 2 : 3);
 631         n = nn;
 632     } while (pos == 3 || n->kids[pos+1] == NULL);
 633
 634     e->node = n;
 635     e->posn = pos;
 636     return n->elems[pos];
 637 }
 638
 639 #ifdef TEST
 640
 641 /*
 642  * Test code for the 2-3-4 tree. This code maintains an alternative
 643  * representation of the data in the tree, in an array (using the
 644  * obvious and slow insert and delete functions). After each tree
 645  * operation, the verify() function is called, which ensures all
 646  * the tree properties are preserved (node->child->parent always
 647  * equals node; number of kids == 0 or number of elements + 1;
 648  * ordering property between elements of a node and elements of its
 649  * children is preserved; tree has the same depth everywhere; every
 650  * node has at least one element) and also ensures the list
 651  * represented by the tree is the same list it should be. (This
 652  * last check also verifies the ordering properties, because the
 653  * `same list it should be' is by definition correctly ordered. It
 654  * also ensures all nodes are distinct, because the enum functions
 655  * would get caught in a loop if not.)
 656  */
 657
 658 #include <stdarg.h>
 659
 660 /*
 661  * Error reporting function.
 662  */
 663 void error(char *fmt, ...) {
 664     va_list ap;
 665     printf("ERROR: ");
 666     va_start(ap, fmt);
 667     vfprintf(stdout, fmt, ap);
 668     va_end(ap);
 669     printf("\n");
 670 }
 671
 672 /* The array representation of the data. */
 673 void **array;
 674 int arraylen, arraysize;
 675 cmpfn234 cmp;
 676
 677 /* The tree representation of the same data. */
 678 tree234 *tree;
 679
 680 typedef struct {
 681     int treedepth;
 682     int elemcount;
 683 } chkctx;
 684
 685 void chknode(chkctx *ctx, int level, node234 *node,
 686              void *lowbound, void *highbound) {
 687     int nkids, nelems;
 688     int i;
 689
 690     /* Count the non-NULL kids. */
 691     for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
 692     /* Ensure no kids beyond the first NULL are non-NULL. */
 693     for (i = nkids; i < 4; i++)
 694         if (node->kids[i]) {
 695             error("node %p: nkids=%d but kids[%d] non-NULL",
 696                    node, nkids, i);
 697         }
 698
 699     /* Count the non-NULL elements. */
 700     for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
 701     /* Ensure no elements beyond the first NULL are non-NULL. */
 702     for (i = nelems; i < 3; i++)
 703         if (node->elems[i]) {
 704             error("node %p: nelems=%d but elems[%d] non-NULL",
 705                    node, nelems, i);
 706         }
 707
 708     if (nkids == 0) {
 709         /*
 710          * If nkids==0, this is a leaf node; verify that the tree
 711          * depth is the same everywhere.
 712          */
 713         if (ctx->treedepth < 0)
 714             ctx->treedepth = level;    /* we didn't know the depth yet */
 715         else if (ctx->treedepth != level)
 716             error("node %p: leaf at depth %d, previously seen depth %d",
 717                    node, level, ctx->treedepth);
 718     } else {
 719         /*
 720          * If nkids != 0, then it should be nelems+1, unless nelems
 721          * is 0 in which case nkids should also be 0 (and so we
 722          * shouldn't be in this condition at all).
 723          */
 724         int shouldkids = (nelems ? nelems+1 : 0);
 725         if (nkids != shouldkids) {
 726             error("node %p: %d elems should mean %d kids but has %d",
 727                    node, nelems, shouldkids, nkids);
 728         }
 729     }
 730
 731     /*
 732      * nelems should be at least 1.
 733      */
 734     if (nelems == 0) {
 735         error("node %p: no elems", node, nkids);
 736     }
 737
 738     /*
 739      * Add nelems to the running element count of the whole tree
 740      * (to ensure the enum234 routines see them all).
 741      */
 742     ctx->elemcount += nelems;
 743
 744     /*
 745      * Check ordering property: all elements should be strictly >
 746      * lowbound, strictly < highbound, and strictly < each other in
 747      * sequence. (lowbound and highbound are NULL at edges of tree
 748      * - both NULL at root node - and NULL is considered to be <
 749      * everything and > everything. IYSWIM.)
 750      */
 751     for (i = -1; i < nelems; i++) {
 752         void *lower = (i == -1 ? lowbound : node->elems[i]);
 753         void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
 754         if (lower && higher && cmp(lower, higher) >= 0) {
 755             error("node %p: kid comparison [%d=%s,%d=%s] failed",
 756                    node, i, lower, i+1, higher);
 757         }
 758     }
 759
 760     /*
 761      * Check parent pointers: all non-NULL kids should have a
 762      * parent pointer coming back to this node.
 763      */
 764     for (i = 0; i < nkids; i++)
 765         if (node->kids[i]->parent != node) {
 766             error("node %p kid %d: parent ptr is %p not %p",
 767                    node, i, node->kids[i]->parent, node);
 768         }
 769
 770
 771     /*
 772      * Now (finally!) recurse into subtrees.
 773      */
 774     for (i = 0; i < nkids; i++) {
 775         void *lower = (i == 0 ? lowbound : node->elems[i-1]);
 776         void *higher = (i >= nelems ? highbound : node->elems[i]);
 777         chknode(ctx, level+1, node->kids[i], lower, higher);
 778     }
 779 }
 780
 781 void verify(void) {
 782     chkctx ctx;
 783     enum234 e;
 784     int i;
 785     void *p;
 786
 787     ctx.treedepth = -1;                /* depth unknown yet */
 788     ctx.elemcount = 0;                 /* no elements seen yet */
 789     /*
 790      * Verify validity of tree properties.
 791      */
 792     if (tree->root)
 793         chknode(&ctx, 0, tree->root, NULL, NULL);
 794     printf("tree depth: %d\n", ctx.treedepth);
 795     /*
 796      * Enumerate the tree and ensure it matches up to the array.
 797      */
 798     for (i = 0, p = first234(tree, &e);
 799          p;
 800          i++, p = next234(&e)) {
 801         if (i >= arraylen)
 802             error("tree contains more than %d elements", arraylen);
 803         if (array[i] != p)
 804             error("enum at position %d: array says %s, tree says %s",
 805                    i, array[i], p);
 806     }
 807     if (i != ctx.elemcount) {
 808         error("tree really contains %d elements, enum gave %d",
 809                i, ctx.elemcount);
 810     }
 811     if (i < arraylen) {
 812         error("enum gave only %d elements, array has %d", i, arraylen);
 813     }
 814 }
 815
 816 void addtest(void *elem) {
 817     int i, j;
 818     void *retval, *realret;
 819
 820     if (arraysize < arraylen+1) {
 821         arraysize = arraylen+1+256;
 822         array = (array == NULL ? malloc(arraysize*sizeof(*array)) :
 823                  realloc(array, arraysize*sizeof(*array)));
 824     }
 825
 826     i = 0;
 827     while (i < arraylen && cmp(elem, array[i]) > 0)
 828         i++;
 829     /* now i points to the first element >= elem */
 830     if (i < arraylen && !cmp(elem, array[i]))
 831         retval = array[i];             /* expect that returned not elem */
 832     else {
 833         retval = elem;                  /* expect elem returned (success) */
 834         for (j = arraylen; j > i; j--)
 835             array[j] = array[j-1];
 836         array[i] = elem;                /* add elem to array */
 837         arraylen++;
 838     }
 839
 840     realret = add234(tree, elem);
 841     if (realret != retval) {
 842         error("add: retval was %p expected %p", realret, retval);
 843     }
 844
 845     verify();
 846 }
 847
 848 void deltest(void *elem) {
 849     int i;
 850
 851     i = 0;
 852     while (i < arraylen && cmp(elem, array[i]) > 0)
 853         i++;
 854     /* now i points to the first element >= elem */
 855     if (i >= arraylen || cmp(elem, array[i]) != 0)
 856         return;                        /* don't do it! */
 857     else {
 858         while (i < arraylen-1) {
 859             array[i] = array[i+1];
 860             i++;
 861         }
 862         arraylen--;                    /* delete elem from array */
 863     }
 864
 865     del234(tree, elem);
 866
 867     verify();
 868 }
 869
 870 /* A sample data set and test utility. Designed for pseudo-randomness,
 871  * and yet repeatability. */
 872
 873 /*
 874  * This random number generator uses the `portable implementation'
 875  * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
 876  * change it if not.
 877  */
 878 int randomnumber(unsigned *seed) {
 879     *seed *= 1103515245;
 880     *seed += 12345;
 881     return ((*seed) / 65536) % 32768;
 882 }
 883
 884 int mycmp(void *av, void *bv) {
 885     char const *a = (char const *)av;
 886     char const *b = (char const *)bv;
 887     return strcmp(a, b);
 888 }
 889
 890 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
 891
 892 char *strings[] = {
 893     "a", "ab", "absque", "coram", "de",
 894     "palam", "clam", "cum", "ex", "e",
 895     "sine", "tenus", "pro", "prae",
 896     "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
 897     "penguin", "blancmange", "pangolin", "whale", "hedgehog",
 898     "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
 899     "murfl", "spoo", "breen", "flarn", "octothorpe",
 900     "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
 901     "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
 902     "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
 903     "wand", "ring", "amulet"
 904 };
 905
 906 #define NSTR lenof(strings)
 907
 908 int main(void) {
 909     int in[NSTR];
 910     int i, j;
 911     unsigned seed = 0;
 912
 913     for (i = 0; i < NSTR; i++) in[i] = 0;
 914     array = NULL;
 915     arraylen = arraysize = 0;
 916     tree = newtree234(mycmp);
 917     cmp = mycmp;
 918
 919     verify();
 920     for (i = 0; i < 10000; i++) {
 921         j = randomnumber(&seed);
 922         j %= NSTR;
 923         printf("trial: %d\n", i);
 924         if (in[j]) {
 925             printf("deleting %s (%d)\n", strings[j], j);
 926             deltest(strings[j]);
 927             in[j] = 0;
 928         } else {
 929             printf("adding %s (%d)\n", strings[j], j);
 930             addtest(strings[j]);
 931             in[j] = 1;
 932         }
 933     }
 934
 935     while (arraylen > 0) {
 936         j = randomnumber(&seed);
 937         j %= arraylen;
 938         deltest(array[j]);
 939     }
 940
 941     return 0;
 942 }
 943
 944 #endif