tree234.c

   1 /*
   2  * tree234.c: reasonably generic 2-3-4 tree routines. Currently
   3  * supports insert, delete, find and iterate operations.
   4  */
   5
   6 #include <stdio.h>
   7 #include <stdlib.h>
   8
   9 #include "tree234.h"
  10
  11 #define mknew(typ) ( (typ *) malloc (sizeof (typ)) )
  12 #define sfree free
  13
  14 #ifdef TEST
  15 #define LOG(x) (printf x)
  16 #else
  17 #define LOG(x)
  18 #endif
  19
  20 struct tree234_Tag {
  21     node234 *root;
  22     cmpfn234 cmp;
  23 };
  24
  25 struct node234_Tag {
  26     node234 *parent;
  27     node234 *kids[4];
  28     void *elems[3];
  29 };
  30
  31 /*
  32  * Create a 2-3-4 tree.
  33  */
  34 tree234 *newtree234(cmpfn234 cmp) {
  35     tree234 *ret = mknew(tree234);
  36     LOG(("created tree %p\n", ret));
  37     ret->root = NULL;
  38     ret->cmp = cmp;
  39     return ret;
  40 }
  41
  42 /*
  43  * Free a 2-3-4 tree (not including freeing the elements).
  44  */
  45 static void freenode234(node234 *n) {
  46     if (!n)
  47         return;
  48     freenode234(n->kids[0]);
  49     freenode234(n->kids[1]);
  50     freenode234(n->kids[2]);
  51     freenode234(n->kids[3]);
  52     sfree(n);
  53 }
  54 void freetree234(tree234 *t) {
  55     freenode234(t->root);
  56     sfree(t);
  57 }
  58
  59 /*
  60  * Add an element e to a 2-3-4 tree t. Returns e on success, or if
  61  * an existing element compares equal, returns that.
  62  */
  63 void *add234(tree234 *t, void *e) {
  64     node234 *n, **np, *left, *right;
  65     void *orig_e = e;
  66     int c;
  67
  68     LOG(("adding node %p to tree %p\n", e, t));
  69     if (t->root == NULL) {
  70         t->root = mknew(node234);
  71         t->root->elems[1] = t->root->elems[2] = NULL;
  72         t->root->kids[0] = t->root->kids[1] = NULL;
  73         t->root->kids[2] = t->root->kids[3] = NULL;
  74         t->root->parent = NULL;
  75         t->root->elems[0] = e;
  76         LOG(("  created root %p\n", t->root));
  77         return orig_e;
  78     }
  79
  80     np = &t->root;
  81     while (*np) {
  82         n = *np;
  83         LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
  84              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
  85              n->kids[2], n->elems[2], n->kids[3]));
  86         if ((c = t->cmp(e, n->elems[0])) < 0)
  87             np = &n->kids[0];
  88         else if (c == 0)
  89             return n->elems[0];        /* already exists */
  90         else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0)
  91             np = &n->kids[1];
  92         else if (c == 0)
  93             return n->elems[1];        /* already exists */
  94         else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0)
  95             np = &n->kids[2];
  96         else if (c == 0)
  97             return n->elems[2];        /* already exists */
  98         else
  99             np = &n->kids[3];
 100         LOG(("  moving to child %d (%p)\n", np - n->kids, *np));
 101     }
 102
 103     /*
 104      * We need to insert the new element in n at position np.
 105      */
 106     left = NULL;
 107     right = NULL;
 108     while (n) {
 109         LOG(("  at %p: %p [%p] %p [%p] %p [%p] %p\n",
 110              n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 111              n->kids[2], n->elems[2], n->kids[3]));
 112         LOG(("  need to insert %p [%p] %p at position %d\n",
 113              left, e, right, np - n->kids));
 114         if (n->elems[1] == NULL) {
 115             /*
 116              * Insert in a 2-node; simple.
 117              */
 118             if (np == &n->kids[0]) {
 119                 LOG(("  inserting on left of 2-node\n"));
 120                 n->kids[2] = n->kids[1];
 121                 n->elems[1] = n->elems[0];
 122                 n->kids[1] = right;
 123                 n->elems[0] = e;
 124                 n->kids[0] = left;
 125             } else { /* np == &n->kids[1] */
 126                 LOG(("  inserting on right of 2-node\n"));
 127                 n->kids[2] = right;
 128                 n->elems[1] = e;
 129                 n->kids[1] = left;
 130             }
 131             if (n->kids[0]) n->kids[0]->parent = n;
 132             if (n->kids[1]) n->kids[1]->parent = n;
 133             if (n->kids[2]) n->kids[2]->parent = n;
 134             LOG(("  done\n"));
 135             break;
 136         } else if (n->elems[2] == NULL) {
 137             /*
 138              * Insert in a 3-node; simple.
 139              */
 140             if (np == &n->kids[0]) {
 141                 LOG(("  inserting on left of 3-node\n"));
 142                 n->kids[3] = n->kids[2];
 143                 n->elems[2] = n->elems[1];
 144                 n->kids[2] = n->kids[1];
 145                 n->elems[1] = n->elems[0];
 146                 n->kids[1] = right;
 147                 n->elems[0] = e;
 148                 n->kids[0] = left;
 149             } else if (np == &n->kids[1]) {
 150                 LOG(("  inserting in middle of 3-node\n"));
 151                 n->kids[3] = n->kids[2];
 152                 n->elems[2] = n->elems[1];
 153                 n->kids[2] = right;
 154                 n->elems[1] = e;
 155                 n->kids[1] = left;
 156             } else { /* np == &n->kids[2] */
 157                 LOG(("  inserting on right of 3-node\n"));
 158                 n->kids[3] = right;
 159                 n->elems[2] = e;
 160                 n->kids[2] = left;
 161             }
 162             if (n->kids[0]) n->kids[0]->parent = n;
 163             if (n->kids[1]) n->kids[1]->parent = n;
 164             if (n->kids[2]) n->kids[2]->parent = n;
 165             if (n->kids[3]) n->kids[3]->parent = n;
 166             LOG(("  done\n"));
 167             break;
 168         } else {
 169             node234 *m = mknew(node234);
 170             m->parent = n->parent;
 171             LOG(("  splitting a 4-node; created new node %p\n", m));
 172             /*
 173              * Insert in a 4-node; split into a 2-node and a
 174              * 3-node, and move focus up a level.
 175              *
 176              * I don't think it matters which way round we put the
 177              * 2 and the 3. For simplicity, we'll put the 3 first
 178              * always.
 179              */
 180             if (np == &n->kids[0]) {
 181                 m->kids[0] = left;
 182                 m->elems[0] = e;
 183                 m->kids[1] = right;
 184                 m->elems[1] = n->elems[0];
 185                 m->kids[2] = n->kids[1];
 186                 e = n->elems[1];
 187                 n->kids[0] = n->kids[2];
 188                 n->elems[0] = n->elems[2];
 189                 n->kids[1] = n->kids[3];
 190             } else if (np == &n->kids[1]) {
 191                 m->kids[0] = n->kids[0];
 192                 m->elems[0] = n->elems[0];
 193                 m->kids[1] = left;
 194                 m->elems[1] = e;
 195                 m->kids[2] = right;
 196                 e = n->elems[1];
 197                 n->kids[0] = n->kids[2];
 198                 n->elems[0] = n->elems[2];
 199                 n->kids[1] = n->kids[3];
 200             } else if (np == &n->kids[2]) {
 201                 m->kids[0] = n->kids[0];
 202                 m->elems[0] = n->elems[0];
 203                 m->kids[1] = n->kids[1];
 204                 m->elems[1] = n->elems[1];
 205                 m->kids[2] = left;
 206                 /* e = e; */
 207                 n->kids[0] = right;
 208                 n->elems[0] = n->elems[2];
 209                 n->kids[1] = n->kids[3];
 210             } else { /* np == &n->kids[3] */
 211                 m->kids[0] = n->kids[0];
 212                 m->elems[0] = n->elems[0];
 213                 m->kids[1] = n->kids[1];
 214                 m->elems[1] = n->elems[1];
 215                 m->kids[2] = n->kids[2];
 216                 n->kids[0] = left;
 217                 n->elems[0] = e;
 218                 n->kids[1] = right;
 219                 e = n->elems[2];
 220             }
 221             m->kids[3] = n->kids[3] = n->kids[2] = NULL;
 222             m->elems[2] = n->elems[2] = n->elems[1] = NULL;
 223             if (m->kids[0]) m->kids[0]->parent = m;
 224             if (m->kids[1]) m->kids[1]->parent = m;
 225             if (m->kids[2]) m->kids[2]->parent = m;
 226             if (n->kids[0]) n->kids[0]->parent = n;
 227             if (n->kids[1]) n->kids[1]->parent = n;
 228             LOG(("  left (%p): %p [%p] %p [%p] %p\n", m,
 229                  m->kids[0], m->elems[0],
 230                  m->kids[1], m->elems[1],
 231                  m->kids[2]));
 232             LOG(("  right (%p): %p [%p] %p\n", n,
 233                  n->kids[0], n->elems[0],
 234                  n->kids[1]));
 235             left = m;
 236             right = n;
 237         }
 238         if (n->parent)
 239             np = (n->parent->kids[0] == n ? &n->parent->kids[0] :
 240                   n->parent->kids[1] == n ? &n->parent->kids[1] :
 241                   n->parent->kids[2] == n ? &n->parent->kids[2] :
 242                   &n->parent->kids[3]);
 243         n = n->parent;
 244     }
 245
 246     /*
 247      * If we've come out of here by `break', n will still be
 248      * non-NULL and we've finished. If we've come here because n is
 249      * NULL, we need to create a new root for the tree because the
 250      * old one has just split into two.
 251      */
 252     if (!n) {
 253         LOG(("  root is overloaded, split into two\n"));
 254         t->root = mknew(node234);
 255         t->root->kids[0] = left;
 256         t->root->elems[0] = e;
 257         t->root->kids[1] = right;
 258         t->root->elems[1] = NULL;
 259         t->root->kids[2] = NULL;
 260         t->root->elems[2] = NULL;
 261         t->root->kids[3] = NULL;
 262         t->root->parent = NULL;
 263         if (t->root->kids[0]) t->root->kids[0]->parent = t->root;
 264         if (t->root->kids[1]) t->root->kids[1]->parent = t->root;
 265         LOG(("  new root is %p [%p] %p\n",
 266              t->root->kids[0], t->root->elems[0], t->root->kids[1]));
 267     }
 268
 269     return orig_e;
 270 }
 271
 272 /*
 273  * Find an element e in a 2-3-4 tree t. Returns NULL if not found.
 274  * e is always passed as the first argument to cmp, so cmp can be
 275  * an asymmetric function if desired. cmp can also be passed as
 276  * NULL, in which case the compare function from the tree proper
 277  * will be used.
 278  */
 279 void *find234(tree234 *t, void *e, cmpfn234 cmp) {
 280     node234 *n;
 281     int c;
 282
 283     if (t->root == NULL)
 284         return NULL;
 285
 286     if (cmp == NULL)
 287         cmp = t->cmp;
 288
 289     n = t->root;
 290     while (n) {
 291         if ( (c = cmp(e, n->elems[0])) < 0)
 292             n = n->kids[0];
 293         else if (c == 0)
 294             return n->elems[0];
 295         else if (n->elems[1] == NULL || (c = cmp(e, n->elems[1])) < 0)
 296             n = n->kids[1];
 297         else if (c == 0)
 298             return n->elems[1];
 299         else if (n->elems[2] == NULL || (c = cmp(e, n->elems[2])) < 0)
 300             n = n->kids[2];
 301         else if (c == 0)
 302             return n->elems[2];
 303         else
 304             n = n->kids[3];
 305     }
 306
 307     /*
 308      * We've found our way to the bottom of the tree and we know
 309      * where we would insert this node if we wanted to. But it
 310      * isn't there.
 311      */
 312     return NULL;
 313 }
 314
 315 /*
 316  * Delete an element e in a 2-3-4 tree. Does not free the element,
 317  * merely removes all links to it from the tree nodes.
 318  */
 319 void del234(tree234 *t, void *e) {
 320     node234 *n;
 321     int ei = -1;
 322
 323     n = t->root;
 324     LOG(("deleting %p from tree %p\n", e, t));
 325     while (1) {
 326         while (n) {
 327             int c;
 328             int ki;
 329             node234 *sub;
 330
 331             LOG(("  node %p: %p [%p] %p [%p] %p [%p] %p\n",
 332                  n, n->kids[0], n->elems[0], n->kids[1], n->elems[1],
 333                  n->kids[2], n->elems[2], n->kids[3]));
 334             if ((c = t->cmp(e, n->elems[0])) < 0) {
 335                 ki = 0;
 336             } else if (c == 0) {
 337                 ei = 0; break;
 338             } else if (n->elems[1] == NULL || (c = t->cmp(e, n->elems[1])) < 0) {
 339                 ki = 1;
 340             } else if (c == 0) {
 341                 ei = 1; break;
 342             } else if (n->elems[2] == NULL || (c = t->cmp(e, n->elems[2])) < 0) {
 343                 ki = 2;
 344             } else if (c == 0) {
 345                 ei = 2; break;
 346             } else {
 347                 ki = 3;
 348             }
 349             /*
 350              * Recurse down to subtree ki. If it has only one element,
 351              * we have to do some transformation to start with.
 352              */
 353             LOG(("  moving to subtree %d\n", ki));
 354             sub = n->kids[ki];
 355             if (!sub->elems[1]) {
 356                 LOG(("  subtree has only one element!\n", ki));
 357                 if (ki > 0 && n->kids[ki-1]->elems[1]) {
 358                     /*
 359                      * Case 3a, left-handed variant. Child ki has
 360                      * only one element, but child ki-1 has two or
 361                      * more. So we need to move a subtree from ki-1
 362                      * to ki.
 363                      *
 364                      *                . C .                     . B .
 365                      *               /     \     ->            /     \
 366                      * [more] a A b B c   d D e      [more] a A b   c C d D e
 367                      */
 368                     node234 *sib = n->kids[ki-1];
 369                     int lastelem = (sib->elems[2] ? 2 :
 370                                     sib->elems[1] ? 1 : 0);
 371                     sub->kids[2] = sub->kids[1];
 372                     sub->elems[1] = sub->elems[0];
 373                     sub->kids[1] = sub->kids[0];
 374                     sub->elems[0] = n->elems[ki-1];
 375                     sub->kids[0] = sib->kids[lastelem+1];
 376                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 377                     n->elems[ki-1] = sib->elems[lastelem];
 378                     sib->kids[lastelem+1] = NULL;
 379                     sib->elems[lastelem] = NULL;
 380                     LOG(("  case 3a left\n"));
 381                 } else if (ki < 3 && n->kids[ki+1] &&
 382                            n->kids[ki+1]->elems[1]) {
 383                     /*
 384                      * Case 3a, right-handed variant. ki has only
 385                      * one element but ki+1 has two or more. Move a
 386                      * subtree from ki+1 to ki.
 387                      *
 388                      *      . B .                             . C .
 389                      *     /     \                ->         /     \
 390                      *  a A b   c C d D e [more]      a A b B c   d D e [more]
 391                      */
 392                     node234 *sib = n->kids[ki+1];
 393                     int j;
 394                     sub->elems[1] = n->elems[ki];
 395                     sub->kids[2] = sib->kids[0];
 396                     if (sub->kids[2]) sub->kids[2]->parent = sub;
 397                     n->elems[ki] = sib->elems[0];
 398                     sib->kids[0] = sib->kids[1];
 399                     for (j = 0; j < 2 && sib->elems[j+1]; j++) {
 400                         sib->kids[j+1] = sib->kids[j+2];
 401                         sib->elems[j] = sib->elems[j+1];
 402                     }
 403                     sib->kids[j+1] = NULL;
 404                     sib->elems[j] = NULL;
 405                     LOG(("  case 3a right\n"));
 406                 } else {
 407                     /*
 408                      * Case 3b. ki has only one element, and has no
 409                      * neighbour with more than one. So pick a
 410                      * neighbour and merge it with ki, taking an
 411                      * element down from n to go in the middle.
 412                      *
 413                      *      . B .                .
 414                      *     /     \     ->        |
 415                      *  a A b   c C d      a A b B c C d
 416                      *
 417                      * (Since at all points we have avoided
 418                      * descending to a node with only one element,
 419                      * we can be sure that n is not reduced to
 420                      * nothingness by this move, _unless_ it was
 421                      * the very first node, ie the root of the
 422                      * tree. In that case we remove the now-empty
 423                      * root and replace it with its single large
 424                      * child as shown.)
 425                      */
 426                     node234 *sib;
 427                     int j;
 428
 429                     if (ki > 0)
 430                         ki--;
 431                     sib = n->kids[ki];
 432                     sub = n->kids[ki+1];
 433
 434                     sub->kids[3] = sub->kids[1];
 435                     sub->elems[2] = sub->elems[0];
 436                     sub->kids[2] = sub->kids[0];
 437                     sub->elems[1] = n->elems[ki];
 438                     sub->kids[1] = sib->kids[1];
 439                     if (sub->kids[1]) sub->kids[1]->parent = sub;
 440                     sub->elems[0] = sib->elems[0];
 441                     sub->kids[0] = sib->kids[0];
 442                     if (sub->kids[0]) sub->kids[0]->parent = sub;
 443
 444                     sfree(sib);
 445
 446                     /*
 447                      * That's built the big node in sub. Now we
 448                      * need to remove the reference to sib in n.
 449                      */
 450                     for (j = ki; j < 3 && n->kids[j+1]; j++) {
 451                         n->kids[j] = n->kids[j+1];
 452                         n->elems[j] = j<2 ? n->elems[j+1] : NULL;
 453                     }
 454                     n->kids[j] = NULL;
 455                     if (j < 3) n->elems[j] = NULL;
 456                     LOG(("  case 3b\n"));
 457
 458                     if (!n->elems[0]) {
 459                         /*
 460                          * The root is empty and needs to be
 461                          * removed.
 462                          */
 463                         LOG(("  shifting root!\n"));
 464                         t->root = sub;
 465                         sub->parent = NULL;
 466                         sfree(n);
 467                     }
 468                 }
 469             }
 470             n = sub;
 471         }
 472         if (ei==-1)
 473             return;                    /* nothing to do; `already removed' */
 474
 475         /*
 476          * Treat special case: this is the one remaining item in
 477          * the tree. n is the tree root (no parent), has one
 478          * element (no elems[1]), and has no kids (no kids[0]).
 479          */
 480         if (!n->parent && !n->elems[1] && !n->kids[0]) {
 481             LOG(("  removed last element in tree\n"));
 482             sfree(n);
 483             t->root = NULL;
 484             return;
 485         }
 486
 487         /*
 488          * Now we have the element we want, as n->elems[ei], and we
 489          * have also arranged for that element not to be the only
 490          * one in its node. So...
 491          */
 492
 493         if (!n->kids[0] && n->elems[1]) {
 494             /*
 495              * Case 1. n is a leaf node with more than one element,
 496              * so it's _really easy_. Just delete the thing and
 497              * we're done.
 498              */
 499             int i;
 500             LOG(("  case 1\n"));
 501             for (i = ei; i < 2 && n->elems[i+1]; i++)
 502                 n->elems[i] = n->elems[i+1];
 503             n->elems[i] = NULL;
 504             return;                    /* finished! */
 505         } else if (n->kids[ei]->elems[1]) {
 506             /*
 507              * Case 2a. n is an internal node, and the root of the
 508              * subtree to the left of e has more than one element.
 509              * So find the predecessor p to e (ie the largest node
 510              * in that subtree), place it where e currently is, and
 511              * then start the deletion process over again on the
 512              * subtree with p as target.
 513              */
 514             node234 *m = n->kids[ei];
 515             void *target;
 516             LOG(("  case 2a\n"));
 517             while (m->kids[0]) {
 518                 m = (m->kids[3] ? m->kids[3] :
 519                      m->kids[2] ? m->kids[2] :
 520                      m->kids[1] ? m->kids[1] : m->kids[0]);
 521             }
 522             target = (m->elems[2] ? m->elems[2] :
 523                       m->elems[1] ? m->elems[1] : m->elems[0]);
 524             n->elems[ei] = target;
 525             n = n->kids[ei];
 526             e = target;
 527         } else if (n->kids[ei+1]->elems[1]) {
 528             /*
 529              * Case 2b, symmetric to 2a but s/left/right/ and
 530              * s/predecessor/successor/. (And s/largest/smallest/).
 531              */
 532             node234 *m = n->kids[ei+1];
 533             void *target;
 534             LOG(("  case 2b\n"));
 535             while (m->kids[0]) {
 536                 m = m->kids[0];
 537             }
 538             target = m->elems[0];
 539             n->elems[ei] = target;
 540             n = n->kids[ei+1];
 541             e = target;
 542         } else {
 543             /*
 544              * Case 2c. n is an internal node, and the subtrees to
 545              * the left and right of e both have only one element.
 546              * So combine the two subnodes into a single big node
 547              * with their own elements on the left and right and e
 548              * in the middle, then restart the deletion process on
 549              * that subtree, with e still as target.
 550              */
 551             node234 *a = n->kids[ei], *b = n->kids[ei+1];
 552             int j;
 553
 554             LOG(("  case 2c\n"));
 555             a->elems[1] = n->elems[ei];
 556             a->kids[2] = b->kids[0];
 557             if (a->kids[2]) a->kids[2]->parent = a;
 558             a->elems[2] = b->elems[0];
 559             a->kids[3] = b->kids[1];
 560             if (a->kids[3]) a->kids[3]->parent = a;
 561             sfree(b);
 562             /*
 563              * That's built the big node in a, and destroyed b. Now
 564              * remove the reference to b (and e) in n.
 565              */
 566             for (j = ei; j < 2 && n->elems[j+1]; j++) {
 567                 n->elems[j] = n->elems[j+1];
 568                 n->kids[j+1] = n->kids[j+2];
 569             }
 570             n->elems[j] = NULL;
 571             n->kids[j+1] = NULL;
 572             /*
 573              * Now go round the deletion process again, with n
 574              * pointing at the new big node and e still the same.
 575              */
 576             n = a;
 577         }
 578     }
 579 }
 580
 581 /*
 582  * Iterate over the elements of a tree234, in order.
 583  */
 584 void *first234(tree234 *t, enum234 *e) {
 585     node234 *n = t->root;
 586     if (!n)
 587         return NULL;
 588     while (n->kids[0])
 589         n = n->kids[0];
 590     e->node = n;
 591     e->posn = 0;
 592     return n->elems[0];
 593 }
 594
 595 void *next234(enum234 *e) {
 596     node234 *n = e->node;
 597     int pos = e->posn;
 598
 599     if (n->kids[pos+1]) {
 600         n = n->kids[pos+1];
 601         while (n->kids[0])
 602             n = n->kids[0];
 603         e->node = n;
 604         e->posn = 0;
 605         return n->elems[0];
 606     }
 607
 608     if (pos < 2 && n->elems[pos+1]) {
 609         e->posn = pos+1;
 610         return n->elems[e->posn];
 611     }
 612
 613     do {
 614         node234 *nn = n->parent;
 615         if (nn == NULL)
 616             return NULL;               /* end of tree */
 617         pos = (nn->kids[0] == n ? 0 :
 618                nn->kids[1] == n ? 1 :
 619                nn->kids[2] == n ? 2 : 3);
 620         n = nn;
 621     } while (pos == 3 || n->kids[pos+1] == NULL);
 622
 623     e->node = n;
 624     e->posn = pos;
 625     return n->elems[pos];
 626 }
 627
 628 #ifdef TEST
 629
 630 int pnode(node234 *n, int level) {
 631     printf("%*s%p\n", level*4, "", n);
 632     if (n->kids[0]) pnode(n->kids[0], level+1);
 633     if (n->elems[0]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[0]);
 634     if (n->kids[1]) pnode(n->kids[1], level+1);
 635     if (n->elems[1]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[1]);
 636     if (n->kids[2]) pnode(n->kids[2], level+1);
 637     if (n->elems[2]) printf("%*s\"%s\"\n", level*4+4, "", n->elems[2]);
 638     if (n->kids[3]) pnode(n->kids[3], level+1);
 639 }
 640 int ptree(tree234 *t) {
 641     if (t->root)
 642         pnode(t->root, 0);
 643     else
 644         printf("empty tree\n");
 645 }
 646
 647 int cmp(void *av, void *bv) {
 648     char *a = (char *)av;
 649     char *b = (char *)bv;
 650     return strcmp(a, b);
 651 }
 652
 653 int main(void) {
 654     tree234 *t = newtree234(cmp);
 655
 656     add234(t, "Richard");
 657     add234(t, "Of");
 658     add234(t, "York");
 659     add234(t, "Gave");
 660     add234(t, "Battle");
 661     add234(t, "In");
 662     add234(t, "Vain");
 663     add234(t, "Rabbits");
 664     add234(t, "On");
 665     add234(t, "Your");
 666     add234(t, "Garden");
 667     add234(t, "Bring");
 668     add234(t, "Invisible");
 669     add234(t, "Vegetables");
 670
 671     ptree(t);
 672     del234(t, find234(t, "Richard", NULL));
 673     ptree(t);
 674     del234(t, find234(t, "Of", NULL));
 675     ptree(t);
 676     del234(t, find234(t, "York", NULL));
 677     ptree(t);
 678     del234(t, find234(t, "Gave", NULL));
 679     ptree(t);
 680     del234(t, find234(t, "Battle", NULL));
 681     ptree(t);
 682     del234(t, find234(t, "In", NULL));
 683     ptree(t);
 684     del234(t, find234(t, "Vain", NULL));
 685     ptree(t);
 686     del234(t, find234(t, "Rabbits", NULL));
 687     ptree(t);
 688     del234(t, find234(t, "On", NULL));
 689     ptree(t);
 690     del234(t, find234(t, "Your", NULL));
 691     ptree(t);
 692     del234(t, find234(t, "Garden", NULL));
 693     ptree(t);
 694     del234(t, find234(t, "Bring", NULL));
 695     ptree(t);
 696     del234(t, find234(t, "Invisible", NULL));
 697     ptree(t);
 698     del234(t, find234(t, "Vegetables", NULL));
 699     ptree(t);
 700 }
 701 #endif