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