putty/TREE234.C

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