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