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 tree_valid() function is called, which ensures
 646  * all the tree properties are preserved (node->child->parent
 647  * always equals node; number of kids == number of elements + 1;
 648  * all tree nodes are distinct; ordering property between elements
 649  * of a node and elements of its children is preserved) and also
 650  * ensures the list represented by the tree is the same list it
 651  * should be. (This last check also verifies the ordering
 652  * properties, because the `same list it should be' is by
 653  * definition correctly ordered.)
 654  */
 655
 656 #include <stdarg.h>
 657
 658 /*
 659  * Error reporting function.
 660  */
 661 void error(char *fmt, ...) {
 662     va_list ap;
 663     printf("ERROR: ");
 664     va_start(ap, fmt);
 665     vfprintf(stdout, fmt, ap);
 666     va_end(ap);
 667     printf("\n");
 668 }
 669
 670 /* The array representation of the data. */
 671 void **array;
 672 int arraylen, arraysize;
 673 cmpfn234 cmp;
 674
 675 /* The tree representation of the same data. */
 676 tree234 *tree;
 677
 678 typedef struct {
 679     int treedepth;
 680     int elemcount;
 681 } chkctx;
 682
 683 void chknode(chkctx *ctx, int level, node234 *node,
 684              void *lowbound, void *highbound) {
 685     int nkids, nelems;
 686     int i;
 687
 688     /* Count the non-NULL kids. */
 689     for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
 690     /* Ensure no kids beyond the first NULL are non-NULL. */
 691     for (i = nkids; i < 4; i++)
 692         if (node->kids[i]) {
 693             error("node %p: nkids=%d but kids[%d] non-NULL",
 694                    node, nkids, i);
 695         }
 696
 697     /* Count the non-NULL elements. */
 698     for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
 699     /* Ensure no elements beyond the first NULL are non-NULL. */
 700     for (i = nelems; i < 3; i++)
 701         if (node->elems[i]) {
 702             error("node %p: nelems=%d but elems[%d] non-NULL",
 703                    node, nelems, i);
 704         }
 705
 706     if (nkids == 0) {
 707         /*
 708          * If nkids==0, this is a leaf node; verify that the tree
 709          * depth is the same everywhere.
 710          */
 711         if (ctx->treedepth < 0)
 712             ctx->treedepth = level;    /* we didn't know the depth yet */
 713         else if (ctx->treedepth != level)
 714             error("node %p: leaf at depth %d, previously seen depth %d",
 715                    node, level, ctx->treedepth);
 716     } else {
 717         /*
 718          * If nkids != 0, then it should be nelems+1, unless nelems
 719          * is 0 in which case nkids should also be 0 (and so we
 720          * shouldn't be in this condition at all).
 721          */
 722         int shouldkids = (nelems ? nelems+1 : 0);
 723         if (nkids != shouldkids) {
 724             error("node %p: %d elems should mean %d kids but has %d",
 725                    node, nelems, shouldkids, nkids);
 726         }
 727     }
 728
 729     /*
 730      * nelems should be at least 1.
 731      */
 732     if (nelems == 0) {
 733         error("node %p: no elems", node, nkids);
 734     }
 735
 736     /*
 737      * Add nelems to the running element count of the whole tree
 738      * (to ensure the enum234 routines see them all).
 739      */
 740     ctx->elemcount += nelems;
 741
 742     /*
 743      * Check ordering property: all elements should be strictly >
 744      * lowbound, strictly < highbound, and strictly < each other in
 745      * sequence. (lowbound and highbound are NULL at edges of tree
 746      * - both NULL at root node - and NULL is considered to be <
 747      * everything and > everything. IYSWIM.)
 748      */
 749     for (i = -1; i < nelems; i++) {
 750         void *lower = (i == -1 ? lowbound : node->elems[i]);
 751         void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
 752         if (lower && higher && cmp(lower, higher) >= 0) {
 753             error("node %p: kid comparison [%d=%s,%d=%s] failed",
 754                    node, i, lower, i+1, higher);
 755         }
 756     }
 757
 758     /*
 759      * Check parent pointers: all non-NULL kids should have a
 760      * parent pointer coming back to this node.
 761      */
 762     for (i = 0; i < nkids; i++)
 763         if (node->kids[i]->parent != node) {
 764             error("node %p kid %d: parent ptr is %p not %p",
 765                    node, i, node->kids[i]->parent, node);
 766         }
 767
 768
 769     /*
 770      * Now (finally!) recurse into subtrees.
 771      */
 772     for (i = 0; i < nkids; i++) {
 773         void *lower = (i == 0 ? lowbound : node->elems[i-1]);
 774         void *higher = (i >= nelems ? highbound : node->elems[i]);
 775         chknode(ctx, level+1, node->kids[i], lower, higher);
 776     }
 777 }
 778
 779 void verify(void) {
 780     chkctx ctx;
 781     enum234 e;
 782     int i;
 783     void *p;
 784
 785     ctx.treedepth = -1;                /* depth unknown yet */
 786     ctx.elemcount = 0;                 /* no elements seen yet */
 787     /*
 788      * Verify validity of tree properties.
 789      */
 790     if (tree->root)
 791         chknode(&ctx, 0, tree->root, NULL, NULL);
 792     printf("tree depth: %d\n", ctx.treedepth);
 793     /*
 794      * Enumerate the tree and ensure it matches up to the array.
 795      */
 796     for (i = 0, p = first234(tree, &e);
 797          p;
 798          i++, p = next234(&e)) {
 799         if (i >= arraylen)
 800             error("tree contains more than %d elements", arraylen);
 801         if (array[i] != p)
 802             error("enum at position %d: array says %s, tree says %s",
 803                    i, array[i], p);
 804     }
 805     if (i != ctx.elemcount) {
 806         error("tree really contains %d elements, enum gave %d",
 807                i, ctx.elemcount);
 808     }
 809     if (i < arraylen) {
 810         error("enum gave only %d elements, array has %d", i, arraylen);
 811     }
 812 }
 813
 814 void addtest(void *elem) {
 815     int i, j;
 816     void *retval, *realret;
 817
 818     if (arraysize < arraylen+1) {
 819         arraysize = arraylen+1+256;
 820         array = (array == NULL ? malloc(arraysize*sizeof(*array)) :
 821                  realloc(array, arraysize*sizeof(*array)));
 822     }
 823
 824     i = 0;
 825     while (i < arraylen && cmp(elem, array[i]) > 0)
 826         i++;
 827     /* now i points to the first element >= elem */
 828     if (i < arraylen && !cmp(elem, array[i]))
 829         retval = array[i];             /* expect that returned not elem */
 830     else {
 831         retval = elem;                  /* expect elem returned (success) */
 832         for (j = arraylen; j > i; j--)
 833             array[j] = array[j-1];
 834         array[i] = elem;                /* add elem to array */
 835         arraylen++;
 836     }
 837
 838     realret = add234(tree, elem);
 839     if (realret != retval) {
 840         error("add: retval was %p expected %p", realret, retval);
 841     }
 842
 843     verify();
 844 }
 845
 846 void deltest(void *elem) {
 847     int i;
 848
 849     i = 0;
 850     while (i < arraylen && cmp(elem, array[i]) > 0)
 851         i++;
 852     /* now i points to the first element >= elem */
 853     if (i >= arraylen || cmp(elem, array[i]) != 0)
 854         return;                        /* don't do it! */
 855     else {
 856         while (i < arraylen-1) {
 857             array[i] = array[i+1];
 858             i++;
 859         }
 860         arraylen--;                    /* delete elem from array */
 861     }
 862
 863     del234(tree, elem);
 864
 865     verify();
 866 }
 867
 868 /* A sample data set and test utility. Designed for pseudo-randomness,
 869  * and yet repeatability. */
 870
 871 /*
 872  * This random number generator uses the `portable implementation'
 873  * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
 874  * change it if not.
 875  */
 876 int randomnumber(unsigned *seed) {
 877     *seed *= 1103515245;
 878     *seed += 12345;
 879     return ((*seed) / 65536) % 32768;
 880 }
 881
 882 int mycmp(void *av, void *bv) {
 883     char const *a = (char const *)av;
 884     char const *b = (char const *)bv;
 885     return strcmp(a, b);
 886 }
 887
 888 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
 889
 890 char *strings[] = {
 891     "a", "ab", "absque", "coram", "de",
 892     "palam", "clam", "cum", "ex", "e",
 893     "sine", "tenus", "pro", "prae",
 894     "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
 895     "penguin", "blancmange", "pangolin", "whale", "hedgehog",
 896     "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
 897     "murfl", "spoo", "breen", "flarn", "octothorpe",
 898     "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
 899     "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
 900     "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
 901     "wand", "ring", "amulet"
 902 };
 903
 904 #define NSTR lenof(strings)
 905
 906 int main(void) {
 907     int in[NSTR];
 908     int i, j;
 909     unsigned seed = 0;
 910
 911     for (i = 0; i < NSTR; i++) in[i] = 0;
 912     array = NULL;
 913     arraylen = arraysize = 0;
 914     tree = newtree234(mycmp);
 915     cmp = mycmp;
 916
 917     verify();
 918     for (i = 0; i < 10000; i++) {
 919         j = randomnumber(&seed);
 920         j %= NSTR;
 921         printf("trial: %d\n", i);
 922         if (in[j]) {
 923             printf("deleting %s (%d)\n", strings[j], j);
 924             deltest(strings[j]);
 925             in[j] = 0;
 926         } else {
 927             printf("adding %s (%d)\n", strings[j], j);
 928             addtest(strings[j]);
 929             in[j] = 1;
 930         }
 931     }
 932
 933     while (arraylen > 0) {
 934         j = randomnumber(&seed);
 935         j %= arraylen;
 936         deltest(array[j]);
 937     }
 938
 939     return 0;
 940 }
 941
 942 #endif