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