tree234.c

   1 /*
   2  * tree234.c: reasonably generic counted 2-3-4 tree routines.
   3  *
   4  * This file is copyright 1999-2001 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 <stdio.h>
  29 #include <stdlib.h>
  30 #include <assert.h>
  31
  32 #include "tree234.h"
  33
  34 #define smalloc malloc
  35 #define sfree free
  36
  37 #define mknew(typ) ( (typ *) smalloc (sizeof (typ)) )
  38
  39 #ifdef TEST
  40 #define LOG(x) (printf x)
  41 #else
  42 #define LOG(x)
  43 #endif
  44
  45 typedef struct node234_Tag node234;
  46
  47 struct tree234_Tag {
  48     node234 *root;
  49     cmpfn234 cmp;
  50 };
  51
  52 struct node234_Tag {
  53     node234 *parent;
  54     node234 *kids[4];
  55     int counts[4];
  56     void *elems[3];
  57 };
  58
  59 /*
  60  * Create a 2-3-4 tree.
  61  */
  62 tree234 *newtree234(cmpfn234 cmp) {
  63     tree234 *ret = mknew(tree234);
  64     LOG(("created tree %p\n", ret));
  65     ret->root = NULL;
  66     ret->cmp = cmp;
  67     return ret;
  68 }
  69
  70 /*
  71  * Free a 2-3-4 tree (not including freeing the elements).
  72  */
  73 static void freenode234(node234 *n) {
  74     if (!n)
  75         return;
  76     freenode234(n->kids[0]);
  77     freenode234(n->kids[1]);
  78     freenode234(n->kids[2]);
  79     freenode234(n->kids[3]);
  80     sfree(n);
  81 }
  82 void freetree234(tree234 *t) {
  83     freenode234(t->root);
  84     sfree(t);
  85 }
  86
  87 /*
  88  * Internal function to count a node.
  89  */
  90 static int countnode234(node234 *n) {
  91     int count = 0;
  92     int i;
  93     if (!n)
  94         return 0;
  95     for (i = 0; i < 4; i++)
  96         count += n->counts[i];
  97     for (i = 0; i < 3; i++)
  98         if (n->elems[i])
  99             count++;
 100     return count;
 101 }
 102
 103 /*
 104  * Count the elements in a tree.
 105  */
 106 int count234(tree234 *t) {
 107     if (t->root)
 108         return countnode234(t->root);
 109     else
 110         return 0;
 111 }
 112
 113 /*
 114  * Add an element e to a 2-3-4 tree t. Returns e on success, or if
 115  * an existing element compares equal, returns that.
 116  */
 117 static void *add234_internal(tree234 *t, void *e, int index) {
 118     node234 *n, **np, *left, *right;
 119     void *orig_e = e;
 120     int c, lcount, rcount;
 121
 122     LOG(("adding node %p to tree %p\n", e, t));
 123     if (t->root == NULL) {
 124         t->root = mknew(node234);
 125         t->root->elems[1] = t->root->elems[2] = NULL;
 126         t->root->kids[0] = t->root->kids[1] = NULL;
 127         t->root->kids[2] = t->root->kids[3] = NULL;
 128         t->root->counts[0] = t->root->counts[1] = 0;
 129         t->root->counts[2] = t->root->counts[3] = 0;
 130         t->root->parent = NULL;
 131         t->root->elems[0] = e;
 132         LOG(("  created root %p\n", t->root));
 133         return orig_e;
 134     }
 135
 136     np = &t->root;
 137     while (*np) {
 138         int childnum;
 139         n = *np;
 140         LOG(("  node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
 141              n,
 142              n->kids[0], n->counts[0], n->elems[0],
 143              n->kids[1], n->counts[1], n->elems[1],
 144              n->kids[2], n->counts[2], n->elems[2],
 145              n->kids[3], n->counts[3]));
 146         if (index >= 0) {
 147             if (!n->kids[0]) {
 148                 /*
 149                  * Leaf node. We want to insert at kid position
 150                  * equal to the index:
 151                  *
 152                  *   0 A 1 B 2 C 3
 153                  */
 154                 childnum = index;
 155             } else {
 156                 /*
 157                  * Internal node. We always descend through it (add
 158                  * always starts at the bottom, never in the
 159                  * middle).
 160                  */
 161                 do { /* this is a do ... while (0) to allow `break' */
 162                     if (index <= n->counts[0]) {
 163                         childnum = 0;
 164                         break;
 165                     }
 166                     index -= n->counts[0] + 1;
 167                     if (index <= n->counts[1]) {
 168                         childnum = 1;
 169                         break;
 170                     }
 171                     index -= n->counts[1] + 1;
 172                     if (index <= n->counts[2]) {
 173                         childnum = 2;
 174                         break;
 175                     }
 176                     index -= n->counts[2] + 1;
 177                     if (index <= n->counts[3]) {
 178                         childnum = 3;
 179                         break;
 180                     }
 181                     return NULL;       /* error: index out of range */
 182                 } while (0);
 183             }
 184         } else {
 185             if ((c = t->cmp(e, n->elems[0])) < 0)
 186                 childnum = 0;
 187             else if (c == 0)
 188                 return n->elems[0];            /* already exists */
 189             else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
 190                 childnum = 1;
 191             else if (c == 0)
 192                 return n->elems[1];            /* already exists */
 193             else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
 194                 childnum = 2;
 195             else if (c == 0)
 196                 return n->elems[2];            /* already exists */
 197             else
 198                 childnum = 3;
 199         }
 200         np = &n->kids[childnum];
 201         LOG(("  moving to child %d (%p)\n", childnum, *np));
 202     }
 203
 204     /*
 205      * We need to insert the new element in n at position np.
 206      */
 207     left = NULL;  lcount = 0;
 208     right = NULL; rcount = 0;
 209     while (n) {
 210         LOG(("  at %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d\n",
 211              n,
 212              n->kids[0], n->counts[0], n->elems[0],
 213              n->kids[1], n->counts[1], n->elems[1],
 214              n->kids[2], n->counts[2], n->elems[2],
 215              n->kids[3], n->counts[3]));
 216         LOG(("  need to insert %p/%d [%p] %p/%d at position %d\n",
 217              left, lcount, e, right, rcount, np - n->kids));
 218         if (n->elems[1] == NULL) {
 219             /*
 220              * Insert in a 2-node; simple.
 221              */
 222             if (np == &n->kids[0]) {
 223                 LOG(("  inserting on left of 2-node\n"));
 224                 n->kids[2] = n->kids[1];     n->counts[2] = n->counts[1];
 225                 n->elems[1] = n->elems[0];
 226                 n->kids[1] = right;          n->counts[1] = rcount;
 227                 n->elems[0] = e;
 228                 n->kids[0] = left;           n->counts[0] = lcount;
 229             } else { /* np == &n->kids[1] */
 230                 LOG(("  inserting on right of 2-node\n"));
 231                 n->kids[2] = right;          n->counts[2] = rcount;
 232                 n->elems[1] = e;
 233                 n->kids[1] = left;           n->counts[1] = lcount;
 234             }
 235             if (n->kids[0]) n->kids[0]->parent = n;
 236             if (n->kids[1]) n->kids[1]->parent = n;
 237             if (n->kids[2]) n->kids[2]->parent = n;
 238             LOG(("  done\n"));
 239             break;
 240         } else if (n->elems[2] == NULL) {
 241             /*
 242              * Insert in a 3-node; simple.
 243              */
 244             if (np == &n->kids[0]) {
 245                 LOG(("  inserting on left of 3-node\n"));
 246                 n->kids[3] = n->kids[2];    n->counts[3] = n->counts[2];
 247                 n->elems[2] = n->elems[1];
 248                 n->kids[2] = n->kids[1];    n->counts[2] = n->counts[1];
 249                 n->elems[1] = n->elems[0];
 250                 n->kids[1] = right;         n->counts[1] = rcount;
 251                 n->elems[0] = e;
 252                 n->kids[0] = left;          n->counts[0] = lcount;
 253             } else if (np == &n->kids[1]) {
 254                 LOG(("  inserting in middle of 3-node\n"));
 255                 n->kids[3] = n->kids[2];    n->counts[3] = n->counts[2];
 256                 n->elems[2] = n->elems[1];
 257                 n->kids[2] = right;         n->counts[2] = rcount;
 258                 n->elems[1] = e;
 259                 n->kids[1] = left;          n->counts[1] = lcount;
 260             } else { /* np == &n->kids[2] */
 261                 LOG(("  inserting on right of 3-node\n"));
 262                 n->kids[3] = right;         n->counts[3] = rcount;
 263                 n->elems[2] = e;
 264                 n->kids[2] = left;          n->counts[2] = lcount;
 265             }
 266             if (n->kids[0]) n->kids[0]->parent = n;
 267             if (n->kids[1]) n->kids[1]->parent = n;
 268             if (n->kids[2]) n->kids[2]->parent = n;
 269             if (n->kids[3]) n->kids[3]->parent = n;
 270             LOG(("  done\n"));
 271             break;
 272         } else {
 273             node234 *m = mknew(node234);
 274             m->parent = n->parent;
 275             LOG(("  splitting a 4-node; created new node %p\n", m));
 276             /*
 277              * Insert in a 4-node; split into a 2-node and a
 278              * 3-node, and move focus up a level.
 279              *
 280              * I don't think it matters which way round we put the
 281              * 2 and the 3. For simplicity, we'll put the 3 first
 282              * always.
 283              */
 284             if (np == &n->kids[0]) {
 285                 m->kids[0] = left;          m->counts[0] = lcount;
 286                 m->elems[0] = e;
 287                 m->kids[1] = right;         m->counts[1] = rcount;
 288                 m->elems[1] = n->elems[0];
 289                 m->kids[2] = n->kids[1];    m->counts[2] = n->counts[1];
 290                 e = n->elems[1];
 291                 n->kids[0] = n->kids[2];    n->counts[0] = n->counts[2];
 292                 n->elems[0] = n->elems[2];
 293                 n->kids[1] = n->kids[3];    n->counts[1] = n->counts[3];
 294             } else if (np == &n->kids[1]) {
 295                 m->kids[0] = n->kids[0];    m->counts[0] = n->counts[0];
 296                 m->elems[0] = n->elems[0];
 297                 m->kids[1] = left;          m->counts[1] = lcount;
 298                 m->elems[1] = e;
 299                 m->kids[2] = right;         m->counts[2] = rcount;
 300                 e = n->elems[1];
 301                 n->kids[0] = n->kids[2];    n->counts[0] = n->counts[2];
 302                 n->elems[0] = n->elems[2];
 303                 n->kids[1] = n->kids[3];    n->counts[1] = n->counts[3];
 304             } else if (np == &n->kids[2]) {
 305                 m->kids[0] = n->kids[0];    m->counts[0] = n->counts[0];
 306                 m->elems[0] = n->elems[0];
 307                 m->kids[1] = n->kids[1];    m->counts[1] = n->counts[1];
 308                 m->elems[1] = n->elems[1];
 309                 m->kids[2] = left;          m->counts[2] = lcount;
 310                 /* e = e; */
 311                 n->kids[0] = right;         n->counts[0] = rcount;
 312                 n->elems[0] = n->elems[2];
 313                 n->kids[1] = n->kids[3];    n->counts[1] = n->counts[3];
 314             } else { /* np == &n->kids[3] */
 315                 m->kids[0] = n->kids[0];    m->counts[0] = n->counts[0];
 316                 m->elems[0] = n->elems[0];
 317                 m->kids[1] = n->kids[1];    m->counts[1] = n->counts[1];
 318                 m->elems[1] = n->elems[1];
 319                 m->kids[2] = n->kids[2];    m->counts[2] = n->counts[2];
 320                 n->kids[0] = left;          n->counts[0] = lcount;
 321                 n->elems[0] = e;
 322                 n->kids[1] = right;         n->counts[1] = rcount;
 323                 e = n->elems[2];
 324             }
 325             m->kids[3] = n->kids[3] = n->kids[2] = NULL;
 326             m->counts[3] = n->counts[3] = n->counts[2] = 0;
 327             m->elems[2] = n->elems[2] = n->elems[1] = NULL;
 328             if (m->kids[0]) m->kids[0]->parent = m;
 329             if (m->kids[1]) m->kids[1]->parent = m;
 330             if (m->kids[2]) m->kids[2]->parent = m;
 331             if (n->kids[0]) n->kids[0]->parent = n;
 332             if (n->kids[1]) n->kids[1]->parent = n;
 333             LOG(("  left (%p): %p/%d [%p] %p/%d [%p] %p/%d\n", m,
 334                  m->kids[0], m->counts[0], m->elems[0],
 335                  m->kids[1], m->counts[1], m->elems[1],
 336                  m->kids[2], m->counts[2]));
 337             LOG(("  right (%p): %p/%d [%p] %p/%d\n", n,
 338                  n->kids[0], n->counts[0], n->elems[0],
 339                  n->kids[1], n->counts[1]));
 340             left = m;  lcount = countnode234(left);
 341             right = n; rcount = countnode234(right);
 342         }
 343         if (n->parent)
 344             np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
 345                   n->parent->kids[1] == n ? &n->parent->kids[1] :
 346                   n->parent->kids[2] == n ? &n->parent->kids[2] :
 347                   &n->parent->kids[3]);
 348         n = n->parent;
 349     }
 350
 351     /*
 352      * If we've come out of here by `break', n will still be
 353      * non-NULL and all we need to do is go back up the tree
 354      * updating counts. If we've come here because n is NULL, we
 355      * need to create a new root for the tree because the old one
 356      * has just split into two. */
 357     if (n) {
 358         while (n->parent) {
 359             int count = countnode234(n);
 360             int childnum;
 361             childnum = (n->parent->kids[0] == n ? 0 :
 362                         n->parent->kids[1] == n ? 1 :
 363                         n->parent->kids[2] == n ? 2 : 3);
 364             n->parent->counts[childnum] = count;
 365             n = n->parent;
 366         }
 367     } else {
 368         LOG(("  root is overloaded, split into two\n"));
 369         t->root = mknew(node234);
 370         t->root->kids[0] = left;     t->root->counts[0] = lcount;
 371         t->root->elems[0] = e;
 372         t->root->kids[1] = right;    t->root->counts[1] = rcount;
 373         t->root->elems[1] = NULL;
 374         t->root->kids[2] = NULL;     t->root->counts[2] = 0;
 375         t->root->elems[2] = NULL;
 376         t->root->kids[3] = NULL;     t->root->counts[3] = 0;
 377         t->root->parent = NULL;
 378         if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
 379         if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
 380         LOG(("  new root is %p/%d [%p] %p/%d\n",
 381              t->root->kids[0], t->root->counts[0],
 382              t->root->elems[0],
 383              t->root->kids[1], t->root->counts[1]));
 384     }
 385
 386     return orig_e;
 387 }
 388
 389 void *add234(tree234 *t, void *e) {
 390     if (!t->cmp)                       /* tree is unsorted */
 391         return NULL;
 392
 393     return add234_internal(t, e, -1);
 394 }
 395 void *addpos234(tree234 *t, void *e, int index) {
 396     if (index < 0 ||                   /* index out of range */
 397         t->cmp)                        /* tree is sorted */
 398         return NULL;                   /* return failure */
 399
 400     return add234_internal(t, e, index);  /* this checks the upper bound */
 401 }
 402
 403 /*
 404  * Look up the element at a given numeric index in a 2-3-4 tree.
 405  * Returns NULL if the index is out of range.
 406  */
 407 void *index234(tree234 *t, int index) {
 408     node234 *n;
 409
 410     if (!t->root)
 411         return NULL;                   /* tree is empty */
 412
 413     if (index < 0 || index >= countnode234(t->root))
 414         return NULL;                   /* out of range */
 415
 416     n = t->root;
 417
 418     while (n) {
 419         if (index < n->counts[0])
 420             n = n->kids[0];
 421         else if (index -= n->counts[0] + 1, index < 0)
 422             return n->elems[0];
 423         else if (index < n->counts[1])
 424             n = n->kids[1];
 425         else if (index -= n->counts[1] + 1, index < 0)
 426             return n->elems[1];
 427         else if (index < n->counts[2])
 428             n = n->kids[2];
 429         else if (index -= n->counts[2] + 1, index < 0)
 430             return n->elems[2];
 431         else
 432             n = n->kids[3];
 433     }
 434
 435     /* We shouldn't ever get here. I wonder how we did. */
 436     return NULL;
 437 }
 438
 439 /*
 440  * Find an element e in a sorted 2-3-4 tree t. Returns NULL if not
 441  * found. e is always passed as the first argument to cmp, so cmp
 442  * can be an asymmetric function if desired. cmp can also be passed
 443  * as NULL, in which case the compare function from the tree proper
 444  * will be used.
 445  */
 446 void *findrelpos234(tree234 *t, void *e, cmpfn234 cmp,
 447                     int relation, int *index) {
 448     node234 *n;
 449     void *ret;
 450     int c;
 451     int idx, ecount, kcount, cmpret;
 452
 453     if (t->root == NULL)
 454         return NULL;
 455
 456     if (cmp == NULL)
 457         cmp = t->cmp;
 458
 459     n = t->root;
 460     /*
 461      * Attempt to find the element itself.
 462      */
 463     idx = 0;
 464     ecount = -1;
 465     /*
 466      * Prepare a fake `cmp' result if e is NULL.
 467      */
 468     cmpret = 0;
 469     if (e == NULL) {
 470         assert(relation == REL234_LT || relation == REL234_GT);
 471         if (relation == REL234_LT)
 472             cmpret = +1;               /* e is a max: always greater */
 473         else if (relation == REL234_GT)
 474             cmpret = -1;               /* e is a min: always smaller */
 475     }
 476     while (1) {
 477         for (kcount = 0; kcount < 4; kcount++) {
 478             if (kcount >= 3 || n->elems[kcount] == NULL ||
 479                 (c = cmpret ? cmpret : cmp(e, n->elems[kcount])) < 0) {
 480                 break;
 481             }
 482             if (n->kids[kcount]) idx += n->counts[kcount];
 483             if (c == 0) {
 484                 ecount = kcount;
 485                 break;
 486             }
 487             idx++;
 488         }
 489         if (ecount >= 0)
 490             break;
 491         if (n->kids[kcount])
 492             n = n->kids[kcount];
 493         else
 494             break;
 495     }
 496
 497     if (ecount >= 0) {
 498         /*
 499          * We have found the element we're looking for. It's
 500          * n->elems[ecount], at tree index idx. If our search
 501          * relation is EQ, LE or GE we can now go home.
 502          */
 503         if (relation != REL234_LT && relation != REL234_GT) {
 504             if (index) *index = idx;
 505             return n->elems[ecount];
 506         }
 507
 508         /*
 509          * Otherwise, we'll do an indexed lookup for the previous
 510          * or next element. (It would be perfectly possible to
 511          * implement these search types in a non-counted tree by
 512          * going back up from where we are, but far more fiddly.)
 513          */
 514         if (relation == REL234_LT)
 515             idx--;
 516         else
 517             idx++;
 518     } else {
 519         /*
 520          * We've found our way to the bottom of the tree and we
 521          * know where we would insert this node if we wanted to:
 522          * we'd put it in in place of the (empty) subtree
 523          * n->kids[kcount], and it would have index idx
 524          *
 525          * But the actual element isn't there. So if our search
 526          * relation is EQ, we're doomed.
 527          */
 528         if (relation == REL234_EQ)
 529             return NULL;
 530
 531         /*
 532          * Otherwise, we must do an index lookup for index idx-1
 533          * (if we're going left - LE or LT) or index idx (if we're
 534          * going right - GE or GT).
 535          */
 536         if (relation == REL234_LT || relation == REL234_LE) {
 537             idx--;
 538         }
 539     }
 540
 541     /*
 542      * We know the index of the element we want; just call index234
 543      * to do the rest. This will return NULL if the index is out of
 544      * bounds, which is exactly what we want.
 545      */
 546     ret = index234(t, idx);
 547     if (ret && index) *index = idx;
 548     return ret;
 549 }
 550 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
 551     return findrelpos234(t, e, cmp, REL234_EQ, NULL);
 552 }
 553 void *findrel234(tree234 *t, void *e, cmpfn234 cmp, int relation) {
 554     return findrelpos234(t, e, cmp, relation, NULL);
 555 }
 556 void *findpos234(tree234 *t, void *e, cmpfn234 cmp, int *index) {
 557     return findrelpos234(t, e, cmp, REL234_EQ, index);
 558 }
 559
 560 /*
 561  * Delete an element e in a 2-3-4 tree. Does not free the element,
 562  * merely removes all links to it from the tree nodes.
 563  */
 564 static void *delpos234_internal(tree234 *t, int index) {
 565     node234 *n;
 566     void *retval;
 567     int ei = -1;
 568
 569     retval = 0;
 570
 571     n = t->root;
 572     LOG(("deleting item %d from tree %p\n", index, t));
 573     while (1) {
 574         while (n) {
 575             int c;
 576             int ki;
 577             node234 *sub;
 578
 579             LOG(("  node %p: %p/%d [%p] %p/%d [%p] %p/%d [%p] %p/%d index=%d\n",
 580                  n,
 581                  n->kids[0], n->counts[0], n->elems[0],
 582                  n->kids[1], n->counts[1], n->elems[1],
 583                  n->kids[2], n->counts[2], n->elems[2],
 584                  n->kids[3], n->counts[3],
 585                  index));
 586             if (index < n->counts[0]) {
 587                 ki = 0;
 588             } else if (index -= n->counts[0]+1, index < 0) {
 589                 ei = 0; break;
 590             } else if (index < n->counts[1]) {
 591                 ki = 1;
 592             } else if (index -= n->counts[1]+1, index < 0) {
 593                 ei = 1; break;
 594             } else if (index < n->counts[2]) {
 595                 ki = 2;
 596             } else if (index -= n->counts[2]+1, index < 0) {
 597                 ei = 2; break;
 598             } else {
 599                 ki = 3;
 600             }
 601             /*
 602              * Recurse down to subtree ki. If it has only one element,
 603              * we have to do some transformation to start with.
 604              */
 605             LOG(("  moving to subtree %d\n", ki));
 606             sub = n->kids[ki];
 607             if (!sub->elems[1]) {
 608                 LOG(("  subtree has only one element!\n", ki));
 609                 if (ki > 0 && n->kids[ki-1]->elems[1]) {
 610                     /*
 611                      * Case 3a, left-handed variant. Child ki has
 612                      * only one element, but child ki-1 has two or
 613                      * more. So we need to move a subtree from ki-1
 614                      * to ki.
 615                      *
 616                      *                . C .                     . B .
 617                      *               /     \     ->            /     \
 618                      * [more] a A b B c   d D e      [more] a A b   c C d D e
 619                      */
 620                     node234 *sib = n->kids[ki-1];
 621                     int lastelem = (sib->elems[2] ? 2 :
 622                                     sib->elems[1] ? 1 : 0);
 623                     sub->kids[2] = sub->kids[1];
 624                     sub->counts[2] = sub->counts[1];
 625                     sub->elems[1] = sub->elems[0];
 626                     sub->kids[1] = sub->kids[0];
 627                     sub->counts[1] = sub->counts[0];
 628                     sub->elems[0] = n->elems[ki-1];
 629                     sub->kids[0] = sib->kids[lastelem+1];
 630                     sub->counts[0] = sib->counts[lastelem+1];
 631                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 632                     n->elems[ki-1] = sib->elems[lastelem];
 633                     sib->kids[lastelem+1] = NULL;
 634                     sib->counts[lastelem+1] = 0;
 635                     sib->elems[lastelem] = NULL;
 636                     n->counts[ki] = countnode234(sub);
 637                     LOG(("  case 3a left\n"));
 638                     LOG(("  index and left subtree count before adjustment: %d, %d\n",
 639                          index, n->counts[ki-1]));
 640                     index += n->counts[ki-1];
 641                     n->counts[ki-1] = countnode234(sib);
 642                     index -= n->counts[ki-1];
 643                     LOG(("  index and left subtree count after adjustment: %d, %d\n",
 644                          index, n->counts[ki-1]));
 645                 } else if (ki < 3 && n->kids[ki+1] &&
 646                            n->kids[ki+1]->elems[1]) {
 647                     /*
 648                      * Case 3a, right-handed variant. ki has only
 649                      * one element but ki+1 has two or more. Move a
 650                      * subtree from ki+1 to ki.
 651                      *
 652                      *      . B .                             . C .
 653                      *     /     \                ->         /     \
 654                      *  a A b   c C d D e [more]      a A b B c   d D e [more]
 655                      */
 656                     node234 *sib = n->kids[ki+1];
 657                     int j;
 658                     sub->elems[1] = n->elems[ki];
 659                     sub->kids[2] = sib->kids[0];
 660                     sub->counts[2] = sib->counts[0];
 661                     if (sub->kids[2]) sub->kids[2]->parent = sub;
 662                     n->elems[ki] = sib->elems[0];
 663                     sib->kids[0] = sib->kids[1];
 664                     sib->counts[0] = sib->counts[1];
 665                     for (j = 0; j < 2 && sib->elems[j+1]; j++) {
 666                         sib->kids[j+1] = sib->kids[j+2];
 667                         sib->counts[j+1] = sib->counts[j+2];
 668                         sib->elems[j] = sib->elems[j+1];
 669                     }
 670                     sib->kids[j+1] = NULL;
 671                     sib->counts[j+1] = 0;
 672                     sib->elems[j] = NULL;
 673                     n->counts[ki] = countnode234(sub);
 674                     n->counts[ki+1] = countnode234(sib);
 675                     LOG(("  case 3a right\n"));
 676                 } else {
 677                     /*
 678                      * Case 3b. ki has only one element, and has no
 679                      * neighbour with more than one. So pick a
 680                      * neighbour and merge it with ki, taking an
 681                      * element down from n to go in the middle.
 682                      *
 683                      *      . B .                .
 684                      *     /     \     ->        |
 685                      *  a A b   c C d      a A b B c C d
 686                      *
 687                      * (Since at all points we have avoided
 688                      * descending to a node with only one element,
 689                      * we can be sure that n is not reduced to
 690                      * nothingness by this move, _unless_ it was
 691                      * the very first node, ie the root of the
 692                      * tree. In that case we remove the now-empty
 693                      * root and replace it with its single large
 694                      * child as shown.)
 695                      */
 696                     node234 *sib;
 697                     int j;
 698
 699                     if (ki > 0) {
 700                         ki--;
 701                         index += n->counts[ki] + 1;
 702                     }
 703                     sib = n->kids[ki];
 704                     sub = n->kids[ki+1];
 705
 706                     sub->kids[3] = sub->kids[1];
 707                     sub->counts[3] = sub->counts[1];
 708                     sub->elems[2] = sub->elems[0];
 709                     sub->kids[2] = sub->kids[0];
 710                     sub->counts[2] = sub->counts[0];
 711                     sub->elems[1] = n->elems[ki];
 712                     sub->kids[1] = sib->kids[1];
 713                     sub->counts[1] = sib->counts[1];
 714                     if (sub->kids[1]) sub->kids[1]->parent = sub;
 715                     sub->elems[0] = sib->elems[0];
 716                     sub->kids[0] = sib->kids[0];
 717                     sub->counts[0] = sib->counts[0];
 718                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 719
 720                     n->counts[ki+1] = countnode234(sub);
 721
 722                     sfree(sib);
 723
 724                     /*
 725                      * That's built the big node in sub. Now we
 726                      * need to remove the reference to sib in n.
 727                      */
 728                     for (j = ki; j < 3 && n->kids[j+1]; j++) {
 729                         n->kids[j] = n->kids[j+1];
 730                         n->counts[j] = n->counts[j+1];
 731                         n->elems[j] = j<2 ? n->elems[j+1] : NULL;
 732                     }
 733                     n->kids[j] = NULL;
 734                     n->counts[j] = 0;
 735                     if (j < 3) n->elems[j] = NULL;
 736                     LOG(("  case 3b ki=%d\n", ki));
 737
 738                     if (!n->elems[0]) {
 739                         /*
 740                          * The root is empty and needs to be
 741                          * removed.
 742                          */
 743                         LOG(("  shifting root!\n"));
 744                         t->root = sub;
 745                         sub->parent = NULL;
 746                         sfree(n);
 747                     }
 748                 }
 749             }
 750             n = sub;
 751         }
 752         if (!retval)
 753             retval = n->elems[ei];
 754
 755         if (ei==-1)
 756             return NULL;               /* although this shouldn't happen */
 757
 758         /*
 759          * Treat special case: this is the one remaining item in
 760          * the tree. n is the tree root (no parent), has one
 761          * element (no elems[1]), and has no kids (no kids[0]).
 762          */
 763         if (!n->parent && !n->elems[1] && !n->kids[0]) {
 764             LOG(("  removed last element in tree\n"));
 765             sfree(n);
 766             t->root = NULL;
 767             return retval;
 768         }
 769
 770         /*
 771          * Now we have the element we want, as n->elems[ei], and we
 772          * have also arranged for that element not to be the only
 773          * one in its node. So...
 774          */
 775
 776         if (!n->kids[0] && n->elems[1]) {
 777             /*
 778              * Case 1. n is a leaf node with more than one element,
 779              * so it's _really easy_. Just delete the thing and
 780              * we're done.
 781              */
 782             int i;
 783             LOG(("  case 1\n"));
 784             for (i = ei; i < 2 && n->elems[i+1]; i++)
 785                 n->elems[i] = n->elems[i+1];
 786             n->elems[i] = NULL;
 787             /*
 788              * Having done that to the leaf node, we now go back up
 789              * the tree fixing the counts.
 790              */
 791             while (n->parent) {
 792                 int childnum;
 793                 childnum = (n->parent->kids[0] == n ? 0 :
 794                             n->parent->kids[1] == n ? 1 :
 795                             n->parent->kids[2] == n ? 2 : 3);
 796                 n->parent->counts[childnum]--;
 797                 n = n->parent;
 798             }
 799             return retval;             /* finished! */
 800         } else if (n->kids[ei]->elems[1]) {
 801             /*
 802              * Case 2a. n is an internal node, and the root of the
 803              * subtree to the left of e has more than one element.
 804              * So find the predecessor p to e (ie the largest node
 805              * in that subtree), place it where e currently is, and
 806              * then start the deletion process over again on the
 807              * subtree with p as target.
 808              */
 809             node234 *m = n->kids[ei];
 810             void *target;
 811             LOG(("  case 2a\n"));
 812             while (m->kids[0]) {
 813                 m = (m->kids[3] ? m->kids[3] :
 814                      m->kids[2] ? m->kids[2] :
 815                      m->kids[1] ? m->kids[1] : m->kids[0]);
 816             }
 817             target = (m->elems[2] ? m->elems[2] :
 818                       m->elems[1] ? m->elems[1] : m->elems[0]);
 819             n->elems[ei] = target;
 820             index = n->counts[ei]-1;
 821             n = n->kids[ei];
 822         } else if (n->kids[ei+1]->elems[1]) {
 823             /*
 824              * Case 2b, symmetric to 2a but s/left/right/ and
 825              * s/predecessor/successor/. (And s/largest/smallest/).
 826              */
 827             node234 *m = n->kids[ei+1];
 828             void *target;
 829             LOG(("  case 2b\n"));
 830             while (m->kids[0]) {
 831                 m = m->kids[0];
 832             }
 833             target = m->elems[0];
 834             n->elems[ei] = target;
 835             n = n->kids[ei+1];
 836             index = 0;
 837         } else {
 838             /*
 839              * Case 2c. n is an internal node, and the subtrees to
 840              * the left and right of e both have only one element.
 841              * So combine the two subnodes into a single big node
 842              * with their own elements on the left and right and e
 843              * in the middle, then restart the deletion process on
 844              * that subtree, with e still as target.
 845              */
 846             node234 *a = n->kids[ei], *b = n->kids[ei+1];
 847             int j;
 848
 849             LOG(("  case 2c\n"));
 850             a->elems[1] = n->elems[ei];
 851             a->kids[2] = b->kids[0];
 852             a->counts[2] = b->counts[0];
 853             if (a->kids[2]) a->kids[2]->parent = a;
 854             a->elems[2] = b->elems[0];
 855             a->kids[3] = b->kids[1];
 856             a->counts[3] = b->counts[1];
 857             if (a->kids[3]) a->kids[3]->parent = a;
 858             sfree(b);
 859             n->counts[ei] = countnode234(a);
 860             /*
 861              * That's built the big node in a, and destroyed b. Now
 862              * remove the reference to b (and e) in n.
 863              */
 864             for (j = ei; j < 2 && n->elems[j+1]; j++) {
 865                 n->elems[j] = n->elems[j+1];
 866                 n->kids[j+1] = n->kids[j+2];
 867                 n->counts[j+1] = n->counts[j+2];
 868             }
 869             n->elems[j] = NULL;
 870             n->kids[j+1] = NULL;
 871             n->counts[j+1] = 0;
 872             /*
 873              * It's possible, in this case, that we've just removed
 874              * the only element in the root of the tree. If so,
 875              * shift the root.
 876              */
 877             if (n->elems[0] == NULL) {
 878                 LOG(("  shifting root!\n"));
 879                 t->root = a;
 880                 a->parent = NULL;
 881                 sfree(n);
 882             }
 883             /*
 884              * Now go round the deletion process again, with n
 885              * pointing at the new big node and e still the same.
 886              */
 887             n = a;
 888             index = a->counts[0] + a->counts[1] + 1;
 889         }
 890     }
 891 }
 892 void *delpos234(tree234 *t, int index) {
 893     if (index < 0 || index >= countnode234(t->root))
 894         return NULL;
 895     return delpos234_internal(t, index);
 896 }
 897 void *del234(tree234 *t, void *e) {
 898     int index;
 899     if (!findrelpos234(t, e, NULL, REL234_EQ, &index))
 900         return NULL;                   /* it wasn't in there anyway */
 901     return delpos234_internal(t, index); /* it's there; delete it. */
 902 }
 903
 904 #ifdef TEST
 905
 906 /*
 907  * Test code for the 2-3-4 tree. This code maintains an alternative
 908  * representation of the data in the tree, in an array (using the
 909  * obvious and slow insert and delete functions). After each tree
 910  * operation, the verify() function is called, which ensures all
 911  * the tree properties are preserved:
 912  *  - node->child->parent always equals node
 913  *  - tree->root->parent always equals NULL
 914  *  - number of kids == 0 or number of elements + 1;
 915  *  - tree has the same depth everywhere
 916  *  - every node has at least one element
 917  *  - subtree element counts are accurate
 918  *  - any NULL kid pointer is accompanied by a zero count
 919  *  - in a sorted tree: ordering property between elements of a
 920  *    node and elements of its children is preserved
 921  * and also ensures the list represented by the tree is the same
 922  * list it should be. (This last check also doubly verifies the
 923  * ordering properties, because the `same list it should be' is by
 924  * definition correctly ordered. It also ensures all nodes are
 925  * distinct, because the enum functions would get caught in a loop
 926  * if not.)
 927  */
 928
 929 #include <stdarg.h>
 930
 931 #define srealloc realloc
 932
 933 /*
 934  * Error reporting function.
 935  */
 936 void error(char *fmt, ...) {
 937     va_list ap;
 938     printf("ERROR: ");
 939     va_start(ap, fmt);
 940     vfprintf(stdout, fmt, ap);
 941     va_end(ap);
 942     printf("\n");
 943 }
 944
 945 /* The array representation of the data. */
 946 void **array;
 947 int arraylen, arraysize;
 948 cmpfn234 cmp;
 949
 950 /* The tree representation of the same data. */
 951 tree234 *tree;
 952
 953 typedef struct {
 954     int treedepth;
 955     int elemcount;
 956 } chkctx;
 957
 958 int chknode(chkctx *ctx, int level, node234 *node,
 959              void *lowbound, void *highbound) {
 960     int nkids, nelems;
 961     int i;
 962     int count;
 963
 964     /* Count the non-NULL kids. */
 965     for (nkids = 0; nkids < 4 && node->kids[nkids]; nkids++);
 966     /* Ensure no kids beyond the first NULL are non-NULL. */
 967     for (i = nkids; i < 4; i++)
 968         if (node->kids[i]) {
 969             error("node %p: nkids=%d but kids[%d] non-NULL",
 970                    node, nkids, i);
 971         } else if (node->counts[i]) {
 972             error("node %p: kids[%d] NULL but count[%d]=%d nonzero",
 973                    node, i, i, node->counts[i]);
 974         }
 975
 976     /* Count the non-NULL elements. */
 977     for (nelems = 0; nelems < 3 && node->elems[nelems]; nelems++);
 978     /* Ensure no elements beyond the first NULL are non-NULL. */
 979     for (i = nelems; i < 3; i++)
 980         if (node->elems[i]) {
 981             error("node %p: nelems=%d but elems[%d] non-NULL",
 982                    node, nelems, i);
 983         }
 984
 985     if (nkids == 0) {
 986         /*
 987          * If nkids==0, this is a leaf node; verify that the tree
 988          * depth is the same everywhere.
 989          */
 990         if (ctx->treedepth < 0)
 991             ctx->treedepth = level;    /* we didn't know the depth yet */
 992         else if (ctx->treedepth != level)
 993             error("node %p: leaf at depth %d, previously seen depth %d",
 994                    node, level, ctx->treedepth);
 995     } else {
 996         /*
 997          * If nkids != 0, then it should be nelems+1, unless nelems
 998          * is 0 in which case nkids should also be 0 (and so we
 999          * shouldn't be in this condition at all).
1000          */
1001         int shouldkids = (nelems ? nelems+1 : 0);
1002         if (nkids != shouldkids) {
1003             error("node %p: %d elems should mean %d kids but has %d",
1004                    node, nelems, shouldkids, nkids);
1005         }
1006     }
1007
1008     /*
1009      * nelems should be at least 1.
1010      */
1011     if (nelems == 0) {
1012         error("node %p: no elems", node, nkids);
1013     }
1014
1015     /*
1016      * Add nelems to the running element count of the whole tree.
1017      */
1018     ctx->elemcount += nelems;
1019
1020     /*
1021      * Check ordering property: all elements should be strictly >
1022      * lowbound, strictly < highbound, and strictly < each other in
1023      * sequence. (lowbound and highbound are NULL at edges of tree
1024      * - both NULL at root node - and NULL is considered to be <
1025      * everything and > everything. IYSWIM.)
1026      */
1027     if (cmp) {
1028         for (i = -1; i < nelems; i++) {
1029             void *lower = (i == -1 ? lowbound : node->elems[i]);
1030             void *higher = (i+1 == nelems ? highbound : node->elems[i+1]);
1031             if (lower && higher && cmp(lower, higher) >= 0) {
1032                 error("node %p: kid comparison [%d=%s,%d=%s] failed",
1033                       node, i, lower, i+1, higher);
1034             }
1035         }
1036     }
1037
1038     /*
1039      * Check parent pointers: all non-NULL kids should have a
1040      * parent pointer coming back to this node.
1041      */
1042     for (i = 0; i < nkids; i++)
1043         if (node->kids[i]->parent != node) {
1044             error("node %p kid %d: parent ptr is %p not %p",
1045                    node, i, node->kids[i]->parent, node);
1046         }
1047
1048
1049     /*
1050      * Now (finally!) recurse into subtrees.
1051      */
1052     count = nelems;
1053
1054     for (i = 0; i < nkids; i++) {
1055         void *lower = (i == 0 ? lowbound : node->elems[i-1]);
1056         void *higher = (i >= nelems ? highbound : node->elems[i]);
1057         int subcount = chknode(ctx, level+1, node->kids[i], lower, higher);
1058         if (node->counts[i] != subcount) {
1059             error("node %p kid %d: count says %d, subtree really has %d",
1060                   node, i, node->counts[i], subcount);
1061         }
1062         count += subcount;
1063     }
1064
1065     return count;
1066 }
1067
1068 void verify(void) {
1069     chkctx ctx;
1070     int i;
1071     void *p;
1072
1073     ctx.treedepth = -1;                /* depth unknown yet */
1074     ctx.elemcount = 0;                 /* no elements seen yet */
1075     /*
1076      * Verify validity of tree properties.
1077      */
1078     if (tree->root) {
1079         if (tree->root->parent != NULL)
1080             error("root->parent is %p should be null", tree->root->parent);
1081         chknode(&ctx, 0, tree->root, NULL, NULL);
1082     }
1083     printf("tree depth: %d\n", ctx.treedepth);
1084     /*
1085      * Enumerate the tree and ensure it matches up to the array.
1086      */
1087     for (i = 0; NULL != (p = index234(tree, i)); i++) {
1088         if (i >= arraylen)
1089             error("tree contains more than %d elements", arraylen);
1090         if (array[i] != p)
1091             error("enum at position %d: array says %s, tree says %s",
1092                    i, array[i], p);
1093     }
1094     if (ctx.elemcount != i) {
1095         error("tree really contains %d elements, enum gave %d",
1096                ctx.elemcount, i);
1097     }
1098     if (i < arraylen) {
1099         error("enum gave only %d elements, array has %d", i, arraylen);
1100     }
1101     i = count234(tree);
1102     if (ctx.elemcount != i) {
1103         error("tree really contains %d elements, count234 gave %d",
1104               ctx.elemcount, i);
1105     }
1106 }
1107
1108 void internal_addtest(void *elem, int index, void *realret) {
1109     int i, j;
1110     void *retval;
1111
1112     if (arraysize < arraylen+1) {
1113         arraysize = arraylen+1+256;
1114         array = (array == NULL ? smalloc(arraysize*sizeof(*array)) :
1115                  srealloc(array, arraysize*sizeof(*array)));
1116     }
1117
1118     i = index;
1119     /* now i points to the first element >= elem */
1120     retval = elem;                  /* expect elem returned (success) */
1121     for (j = arraylen; j > i; j--)
1122         array[j] = array[j-1];
1123     array[i] = elem;                /* add elem to array */
1124     arraylen++;
1125
1126     if (realret != retval) {
1127         error("add: retval was %p expected %p", realret, retval);
1128     }
1129
1130     verify();
1131 }
1132
1133 void addtest(void *elem) {
1134     int i;
1135     void *realret;
1136
1137     realret = add234(tree, elem);
1138
1139     i = 0;
1140     while (i < arraylen && cmp(elem, array[i]) > 0)
1141         i++;
1142     if (i < arraylen && !cmp(elem, array[i])) {
1143         void *retval = array[i];       /* expect that returned not elem */
1144         if (realret != retval) {
1145             error("add: retval was %p expected %p", realret, retval);
1146         }
1147     } else
1148         internal_addtest(elem, i, realret);
1149 }
1150
1151 void addpostest(void *elem, int i) {
1152     void *realret;
1153
1154     realret = addpos234(tree, elem, i);
1155
1156     internal_addtest(elem, i, realret);
1157 }
1158
1159 void delpostest(int i) {
1160     int index = i;
1161     void *elem = array[i], *ret;
1162
1163     /* i points to the right element */
1164     while (i < arraylen-1) {
1165         array[i] = array[i+1];
1166         i++;
1167     }
1168     arraylen--;                        /* delete elem from array */
1169
1170     if (tree->cmp)
1171         ret = del234(tree, elem);
1172     else
1173         ret = delpos234(tree, index);
1174
1175     if (ret != elem) {
1176         error("del returned %p, expected %p", ret, elem);
1177     }
1178
1179     verify();
1180 }
1181
1182 void deltest(void *elem) {
1183     int i;
1184
1185     i = 0;
1186     while (i < arraylen && cmp(elem, array[i]) > 0)
1187         i++;
1188     if (i >= arraylen || cmp(elem, array[i]) != 0)
1189         return;                        /* don't do it! */
1190     delpostest(i);
1191 }
1192
1193 /* A sample data set and test utility. Designed for pseudo-randomness,
1194  * and yet repeatability. */
1195
1196 /*
1197  * This random number generator uses the `portable implementation'
1198  * given in ANSI C99 draft N869. It assumes `unsigned' is 32 bits;
1199  * change it if not.
1200  */
1201 int randomnumber(unsigned *seed) {
1202     *seed *= 1103515245;
1203     *seed += 12345;
1204     return ((*seed) / 65536) % 32768;
1205 }
1206
1207 int mycmp(void *av, void *bv) {
1208     char const *a = (char const *)av;
1209     char const *b = (char const *)bv;
1210     return strcmp(a, b);
1211 }
1212
1213 #define lenof(x) ( sizeof((x)) / sizeof(*(x)) )
1214
1215 char *strings[] = {
1216     "a", "ab", "absque", "coram", "de",
1217     "palam", "clam", "cum", "ex", "e",
1218     "sine", "tenus", "pro", "prae",
1219     "banana", "carrot", "cabbage", "broccoli", "onion", "zebra",
1220     "penguin", "blancmange", "pangolin", "whale", "hedgehog",
1221     "giraffe", "peanut", "bungee", "foo", "bar", "baz", "quux",
1222     "murfl", "spoo", "breen", "flarn", "octothorpe",
1223     "snail", "tiger", "elephant", "octopus", "warthog", "armadillo",
1224     "aardvark", "wyvern", "dragon", "elf", "dwarf", "orc", "goblin",
1225     "pixie", "basilisk", "warg", "ape", "lizard", "newt", "shopkeeper",
1226     "wand", "ring", "amulet"
1227 };
1228
1229 #define NSTR lenof(strings)
1230
1231 int findtest(void) {
1232     const static int rels[] = {
1233         REL234_EQ, REL234_GE, REL234_LE, REL234_LT, REL234_GT
1234     };
1235     const static char *const relnames[] = {
1236         "EQ", "GE", "LE", "LT", "GT"
1237     };
1238     int i, j, rel, index;
1239     char *p, *ret, *realret, *realret2;
1240     int lo, hi, mid, c;
1241
1242     for (i = 0; i < NSTR; i++) {
1243         p = strings[i];
1244         for (j = 0; j < sizeof(rels)/sizeof(*rels); j++) {
1245             rel = rels[j];
1246
1247             lo = 0; hi = arraylen-1;
1248             while (lo <= hi) {
1249                 mid = (lo + hi) / 2;
1250                 c = strcmp(p, array[mid]);
1251                 if (c < 0)
1252                     hi = mid-1;
1253                 else if (c > 0)
1254                     lo = mid+1;
1255                 else
1256                     break;
1257             }
1258
1259             if (c == 0) {
1260                 if (rel == REL234_LT)
1261                     ret = (mid > 0 ? array[--mid] : NULL);
1262                 else if (rel == REL234_GT)
1263                     ret = (mid < arraylen-1 ? array[++mid] : NULL);
1264                 else
1265                     ret = array[mid];
1266             } else {
1267                 assert(lo == hi+1);
1268                 if (rel == REL234_LT || rel == REL234_LE) {
1269                     mid = hi;
1270                     ret = (hi >= 0 ? array[hi] : NULL);
1271                 } else if (rel == REL234_GT || rel == REL234_GE) {
1272                     mid = lo;
1273                     ret = (lo < arraylen ? array[lo] : NULL);
1274                 } else
1275                     ret = NULL;
1276             }
1277
1278             realret = findrelpos234(tree, p, NULL, rel, &index);
1279             if (realret != ret) {
1280                 error("find(\"%s\",%s) gave %s should be %s",
1281                       p, relnames[j], realret, ret);
1282             }
1283             if (realret && index != mid) {
1284                 error("find(\"%s\",%s) gave %d should be %d",
1285                       p, relnames[j], index, mid);
1286             }
1287             if (realret && rel == REL234_EQ) {
1288                 realret2 = index234(tree, index);
1289                 if (realret2 != realret) {
1290                     error("find(\"%s\",%s) gave %s(%d) but %d -> %s",
1291                           p, relnames[j], realret, index, index, realret2);
1292                 }
1293             }
1294 #if 0
1295             printf("find(\"%s\",%s) gave %s(%d)\n", p, relnames[j],
1296                    realret, index);
1297 #endif
1298         }
1299     }
1300
1301     realret = findrelpos234(tree, NULL, NULL, REL234_GT, &index);
1302     if (arraylen && (realret != array[0] || index != 0)) {
1303         error("find(NULL,GT) gave %s(%d) should be %s(0)",
1304               realret, index, array[0]);
1305     } else if (!arraylen && (realret != NULL)) {
1306         error("find(NULL,GT) gave %s(%d) should be NULL",
1307               realret, index);
1308     }
1309
1310     realret = findrelpos234(tree, NULL, NULL, REL234_LT, &index);
1311     if (arraylen && (realret != array[arraylen-1] || index != arraylen-1)) {
1312         error("find(NULL,LT) gave %s(%d) should be %s(0)",
1313               realret, index, array[arraylen-1]);
1314     } else if (!arraylen && (realret != NULL)) {
1315         error("find(NULL,LT) gave %s(%d) should be NULL",
1316               realret, index);
1317     }
1318 }
1319
1320 int main(void) {
1321     int in[NSTR];
1322     int i, j, k;
1323     unsigned seed = 0;
1324
1325     for (i = 0; i < NSTR; i++) in[i] = 0;
1326     array = NULL;
1327     arraylen = arraysize = 0;
1328     tree = newtree234(mycmp);
1329     cmp = mycmp;
1330
1331     verify();
1332     for (i = 0; i < 10000; i++) {
1333         j = randomnumber(&seed);
1334         j %= NSTR;
1335         printf("trial: %d\n", i);
1336         if (in[j]) {
1337             printf("deleting %s (%d)\n", strings[j], j);
1338             deltest(strings[j]);
1339             in[j] = 0;
1340         } else {
1341             printf("adding %s (%d)\n", strings[j], j);
1342             addtest(strings[j]);
1343             in[j] = 1;
1344         }
1345         findtest();
1346     }
1347
1348     while (arraylen > 0) {
1349         j = randomnumber(&seed);
1350         j %= arraylen;
1351         deltest(array[j]);
1352     }
1353
1354     freetree234(tree);
1355
1356     /*
1357      * Now try an unsorted tree. We don't really need to test
1358      * delpos234 because we know del234 is based on it, so it's
1359      * already been tested in the above sorted-tree code; but for
1360      * completeness we'll use it to tear down our unsorted tree
1361      * once we've built it.
1362      */
1363     tree = newtree234(NULL);
1364     cmp = NULL;
1365     verify();
1366     for (i = 0; i < 1000; i++) {
1367         printf("trial: %d\n", i);
1368         j = randomnumber(&seed);
1369         j %= NSTR;
1370         k = randomnumber(&seed);
1371         k %= count234(tree)+1;
1372         printf("adding string %s at index %d\n", strings[j], k);
1373         addpostest(strings[j], k);
1374     }
1375     while (count234(tree) > 0) {
1376         printf("cleanup: tree size %d\n", count234(tree));
1377         j = randomnumber(&seed);
1378         j %= count234(tree);
1379         printf("deleting string %s from index %d\n", array[j], j);
1380         delpostest(j);
1381     }
1382
1383     return 0;
1384 }
1385
1386 #endif