chiark - git - mdw - xyla/blob - t/treetest.c

   1 /* -*-c-*-
   2  *
   3  * Test driver
   4  *
   5  * (c) 2024 Straylight/Edgeware
   6  */
   7
   8 /*----- Licensing notice --------------------------------------------------*
   9  *
  10  * This file is part of Xyla, a library of binary trees.
  11  *
  12  * Xyla is free software: you can redistribute it and/or modify it under
  13  * the terms of the GNU Lesser General Public License as published by the
  14  * Free Software Foundation; either version 3 of the License, or (at your
  15  * option) any later version.
  16  *
  17  * Xyla is distributed in the hope that it will be useful, but WITHOUT
  18  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  19  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  20  * License for more details.
  21  *
  22  * You should have received a copy of the GNU Lesser General Public
  23  * License along with Xyla.  If not, see <https://www.gnu.org/licenses/>.
  24  */
  25
  26 /*----- Header files ------------------------------------------------------*/
  27
  28 #include <assert.h>
  29 #include <ctype.h>
  30 #include <errno.h>
  31 #include <stdarg.h>
  32 #include <stdio.h>
  33 #include <stdlib.h>
  34 #include <string.h>
  35
  36 /*----- Primary switch ----------------------------------------------------*/
  37
  38 #define AVL 1
  39 #define RB 2
  40 #define SPLAY 3
  41 #define TREAP 4
  42
  43 #include "lib.h"
  44 #if TREE == AVL
  45 #  include "avl.h"
  46 #  define T avl
  47 #  define TREE__NAME(name) XYLA_AVL_##name
  48 #  define tree__name(name) xyla_avl_##name
  49 #  define HAVE_HEIGHT 1
  50 #  define FLAGMASK (~XYLA_AVLF_BALMASK)
  51 #elif TREE == RB
  52 #  include "rb.h"
  53 #  define T rb
  54 #  define TREE__NAME(name) XYLA_RB_##name
  55 #  define tree__name(name) xyla_rb_##name
  56 #  define HAVE_HEIGHT 1
  57 #  define FLAGMASK (~XYLA_RBF_RED)
  58 #elif TREE == SPLAY
  59 #  include "splay.h"
  60 #  define T spl
  61 #  define TREE__NAME(name) XYLA_SPLAY_##name
  62 #  define tree__name(name) xyla_splay_##name
  63 #  undef HAVE_HEIGHT
  64 #  undef FLAGMASK
  65 #elif TREE == TREAP
  66 #  include "treap.h"
  67 #  define T trp
  68 #  define TREE__NAME(name) XYLA_TREAP_##name
  69 #  define tree__name(name) xyla_treap_##name
  70 #  undef HAVE_HEIGHT
  71 #  undef FLAGMASK
  72 #else
  73 #  error "unknown `TREE' value"
  74 #endif
  75
  76 #define NODE tree__name(node)
  77 #define ITER tree__name(iter)
  78 #define RITER tree__name(riter)
  79 #define PATH tree__name(path)
  80 #define TREE_NODEPFX TREE__NAME(NODEPFX)
  81 #define TREE_NODEUSFX TREE__NAME(NODEUSFX)
  82 #define TREE_CHECK tree__name(check)
  83 #define TREE_HEIGHT tree__name(height)
  84 #define TREE_LOOKUP tree__name(lookup)
  85 #define TREE_PROBE tree__name(probe)
  86 #define TREE_INITITER tree__name(inititer)
  87 #define TREE_NEXT tree__name(next)
  88 #define TREE_INITRITER tree__name(initriter)
  89 #define TREE_PREV tree__name(prev)
  90 #define TREE_CURRENT tree__name(current)
  91 #define TREE_ROOTPATH tree__name(rootpath)
  92 #define TREE_UPPATH tree__name(uppath)
  93 #define TREE_LEFTPATH tree__name(leftpath)
  94 #define TREE_RIGHTPATH tree__name(rightpath)
  95 #define TREE_FIRSTPATH tree__name(firstpath)
  96 #define TREE_LASTPATH tree__name(lastpath)
  97 #define TREE_NEXTPATH tree__name(nextpath)
  98 #define TREE_PREVPATH tree__name(prevpath)
  99 #define TREE_BEFOREPATH tree__name(beforepath)
 100 #define TREE_AFTERPATH tree__name(afterpath)
 101 #define TREE_ASCEND tree__name(ascend)
 102 #define TREE_INSERT tree__name(insert)
 103 #define TREE_REMOVE tree__name(remove)
 104 #define TREE_JOIN tree__name(join)
 105 #define TREE_SPLIT tree__name(split)
 106 #define TREE_SPLITAT tree__name(splitat)
 107 #define TREE_UNISECT tree__name(unisect)
 108 #define TREE_DIFFSECT tree__name(diffsect)
 109
 110 #ifdef HAVE_HEIGHT
 111 #  define H(x) x
 112 #  define HELSE(x, y) x
 113 #  define HARG(x) , x
 114 #else
 115 #  define H(x)
 116 #  define HELSE(x, y) y
 117 #  define HARG(x)
 118 #endif
 119
 120 /*----- Preliminaries -----------------------------------------------------*/
 121
 122 static FILE *in, *out;
 123 int stop = 0;
 124
 125 #define BCAT_FAIL 1u
 126 #define BCAT_ERR 2u
 127 #define BCAT_BUG 3u
 128 static NORETURN PRINTF_LIKE(2, 3)
 129   void bail(unsigned cat, const char *msg, ...)
 130 {
 131   /* Write a`printf'-formatted message MSG to standard error and quit the
 132    * program.  CAT is a constant which indicates the reason: `BCAT_FAIL'
 133    * indicates an environmental problem (e.g., insufficient memory);
 134    * `BCAT_ERR' indicates a user error; `BCAT_BUG' indicates a bug detected
 135    * in the tree implementation.  The category determines the token printed
 136    * before the message.  Also, if this is a fuzzing build, `BCAT_BUG'
 137    * results in a call to `abort' rather than `exit' to let the fuzzer know
 138    * that it should claim a win.
 139    */
 140
 141   va_list ap;
 142   long pos;
 143
 144   switch (cat) {
 145     case BCAT_FAIL: fputs("failure: ", stderr); break;
 146     case BCAT_ERR: fputs("error: ", stderr); break;
 147     case BCAT_BUG: fputs("BUG: ", stderr); break;
 148     default:
 149       fprintf(stderr, "(unknown bail code %u): ", cat);
 150       cat = BCAT_BUG;
 151       break;
 152   }
 153   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 154   if (in) {
 155     pos = ftell(in);
 156     if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 157   }
 158   fputc('\n', stderr);
 159 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 160   if (cat == BCAT_BUG) abort();
 161 #endif
 162   exit(2);
 163 }
 164
 165 enum { DIR_IN, DIR_OUT };
 166   /* Direction codes for `check_file', `open_file', and `close_file'. */
 167
 168 static void check_file(unsigned dir)
 169 {
 170   /* Check that the file indicated by DIR is free of errors.  If DIR is
 171    * `DIR_OUT' then buffered output is flushed.
 172    */
 173
 174   FILE *fp;
 175   const char *act;
 176   unsigned f = 0;
 177 #define f_flush 1u
 178
 179   switch (dir) {
 180     case DIR_IN: fp = in; act = "read"; break;
 181     case DIR_OUT: fp = out; act = "write"; f |= f_flush; break;
 182     default: assert(0);
 183   }
 184   if (fp) {
 185     if (((f&f_flush) && fflush(fp)) || ferror(fp))
 186       bail(BCAT_ERR, "%s error: %s", act, strerror(errno));
 187   }
 188
 189 #undef f_flush
 190 }
 191
 192 static void close_file(unsigned dir)
 193 {
 194   /* Close the file indicated by DIR.  Check that it was in a good state
 195    * beforehand.
 196    */
 197
 198   FILE **fp_inout, *fp, *stdfp;
 199
 200   switch (dir) {
 201     case DIR_IN: fp_inout = &in; stdfp = stdin; break;
 202     case DIR_OUT: fp_inout = &out; stdfp = stdout; break;
 203     default: assert(0);
 204   }
 205   fp = *fp_inout;
 206   if (fp) {
 207     check_file(dir);
 208     if (fp != stdfp) fclose(fp);
 209     *fp_inout = 0;
 210   }
 211 }
 212
 213 static void open_file(const char *file, unsigned dir)
 214 {
 215   /* Open FILE as the current input or output file, as indicated by DIR. */
 216
 217   FILE **fp_inout, *fp, *stdfp;
 218   const char *mode, *what;
 219   unsigned f = 0;
 220 #define f_chkeof 1u
 221
 222   switch (dir) {
 223     case DIR_IN:
 224       fp_inout = &in; stdfp = stdin; mode = "r"; what = "input";
 225       f |= f_chkeof;
 226       break;
 227     case DIR_OUT:
 228       fp_inout = &out; stdfp = stdout; mode = "w"; what = "output";
 229       break;
 230     default: assert(0);
 231   }
 232   close_file(dir);
 233   if (file[0] == '-' && !file[1]) {
 234     if (((f&f_chkeof) && feof(stdfp)) || ferror(stdfp))
 235       bail(BCAT_ERR, "already consumed standard %s", what);
 236     *fp_inout = stdfp;
 237   } else {
 238     fp = fopen(file, mode);
 239     if (!fp)
 240       bail(BCAT_ERR, "failed to open %s file `%s': %s",
 241            what, file, strerror(errno));
 242     *fp_inout = fp;
 243   }
 244
 245 #undef f_chkeof
 246 }
 247
 248 static unsigned long read_int(void)
 249 {
 250   /* Read and return an integer from the intput file.
 251    *
 252    * These are used as a search keys, indices, or weights.
 253    */
 254
 255   unsigned long k;
 256   int ch;
 257
 258   /* For some stupid reason, there isn't a `scanf' format which just reads
 259    * an unsigned integer with an arbitrary radix prefix.  The `%d' format
 260    * does the right thing for a signed value, but not unsigned.  So we have
 261    * this.
 262    */
 263   do ch = getc(in); while (isspace(ch));
 264   if (!isdigit(ch)) bail(BCAT_ERR, "integer expected, found `%c'", ch);
 265   if (ch != '0') {
 266     ungetc(ch, in);
 267     if (fscanf(in, "%lu", &k) != 1)
 268       bail(BCAT_ERR, "integer expected, scanf failed");
 269   } else {
 270     ch = getc(in);
 271     if (ch == 'x' || ch == 'X') {
 272       if (fscanf(in, "%lx", &k) != 1)
 273         bail(BCAT_ERR, "integer expected, scanf failed");
 274     } else if ('0' <= ch && ch <= '7') {
 275       ungetc(ch, in);
 276       if (fscanf(in, "%lo", &k) != 1)
 277         bail(BCAT_ERR, "integer expected, scanf failed");
 278     } else
 279       { ungetc(ch, in); k = 0; }
 280   }
 281   return (k);
 282 }
 283
 284 static unsigned long seed = 0xacd1051a;
 285   /* Seed for random number generator.  Don't set this to zero. */
 286
 287 #if TREE == TREAP || defined(FLAGMASK)
 288 static unsigned long randwt(void)
 289 {
 290   /* Return a pseudo-random integer.
 291    *
 292    * We have our own -- currently a rather simple LFSR -- so that the test
 293    * results are reproducible on all targets.
 294    */
 295
 296   unsigned long x = seed, m;
 297   unsigned i;
 298 #define RANDPOLY 0x915717d7
 299
 300   for (i = 0; i < 32; i++) {
 301     m = ((seed >> 31)&1) - 1;
 302     seed = (seed << 1) ^ (m&RANDPOLY);
 303   }
 304   seed &= 0xffffffff; return (x);
 305
 306 #undef RANDPOLY
 307 }
 308 #endif
 309
 310 static const char *rctag(int rc)
 311 {
 312   /* Return the name of return code RC as a string. */
 313
 314   static const char *const tagtab[] = {
 315 #define TAG(tag, msg) #tag,
 316     XYLA_RC_DOLOSE(TAG)
 317     XYLA_RC_DOWIN(TAG)
 318 #undef TAG
 319   };
 320
 321   if (XYLA_RC_LOSELIMIT <= rc && rc < XYLA_RC_WINLIMIT)
 322     return (tagtab[rc - XYLA_RC_LOSELIMIT]);
 323   else
 324     return ("#<unknown libxyla error code>");
 325 }
 326
 327 /*----- Node definition ---------------------------------------------------*/
 328
 329 struct my_node {
 330   /* Our test node structure. */
 331
 332   TREE_NODEPFX;                         /* tree node control data */
 333 #ifdef FLAGMASK
 334   unsigned fref;                        /* reference value for user flags */
 335 #endif
 336   struct my_node *next, *prev;          /* links in active nodes list */
 337   size_t n;                             /* number of nodes in this subtree */
 338   unsigned long seq, k;                 /* sequence number and key */
 339 };
 340 union my_nodeu { struct my_node my; TREE_NODEUSFX; };
 341
 342 /* Conversions. */
 343 #define MY_NODE(node)                                                   \
 344         CONVERT_CAREFULLY(struct my_node *, struct xyla_bt_node *, node)
 345 #define MY_NODEU(node)                                                  \
 346         CONVERT_CAREFULLY(union my_nodeu *, struct xyla_bt_node *, node)
 347 #define CONST_MY_NODE(node)                                             \
 348         CONVERT_CAREFULLY(const struct my_node *,                       \
 349                           const struct xyla_bt_node *,                  \
 350                           node)
 351 #define CONST_MY_NODEU(node)                                            \
 352         CONVERT_CAREFULLY(const union my_nodeu *,                       \
 353                           const struct xyla_bt_node *,                  \
 354                           node)
 355
 356 #define MY_SPLAY_NODE(node)                                             \
 357         CONVERT_CAREFULLY(struct my_node *, struct xyla_splay_node *, node)
 358
 359 #define TREE_NODE(node)                                                 \
 360         CONVERT_CAREFULLY(struct NODE *, struct xyla_bt_node *, node)
 361 #define CONST_TREE_NODE(node)                                           \
 362         CONVERT_CAREFULLY(const struct NODE *,                          \
 363                           const struct xyla_bt_node *,                  \
 364                           node)
 365
 366 static unsigned long nodeseq = 0;       /* next node sequence number */
 367 static struct my_node *nodes = 0;       /* list of active nodes */
 368
 369 static int my_ordnav(struct xyla_bt_nodecls *cls,
 370                      const struct xyla_bt_node *node, void *arg)
 371 {
 372   /* Navigation function to search by key. */
 373
 374   const struct my_node *mynode = CONST_MY_NODE(node);
 375   unsigned long *key = arg;
 376
 377   if (*key < mynode->k) return (-1);
 378   else if (*key > mynode->k) return (+1);
 379   else return (0);
 380 }
 381
 382 static int my_idxnav(struct xyla_bt_nodecls *cls,
 383                      const struct xyla_bt_node *node, void *arg)
 384 {
 385   /* Navigation function to search by index. */
 386
 387   const struct my_node *myleft = CONST_MY_NODE(node->left);
 388   unsigned long *i_inout = arg, i = *i_inout, n;
 389
 390   if (myleft) {
 391     n = myleft->n;
 392     if (i < n) return (-1);
 393     else i -= n;
 394   }
 395   if (!i) return (0);
 396   *i_inout = i - 1; return (+1);
 397 }
 398
 399 static void my_upd(struct xyla_bt_nodecls *cls, struct xyla_bt_node *node)
 400 {
 401   /* Update function to maintain node count. */
 402
 403   struct my_node
 404     *mynode = MY_NODE(node),
 405     *left = MY_NODE(mynode->bt.left), *right = MY_NODE(mynode->bt.right);
 406
 407   mynode->n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 408 }
 409
 410 static const void *my_key(struct xyla_bt_nodecls *cls,
 411                           const struct xyla_bt_node *node)
 412 {
 413   /* Return search key for node. */
 414
 415   return (&CONST_MY_NODE(node)->k);
 416 }
 417
 418 #define CHKF_OUTMASK 0x3000u            /* check flags: output mode mask */
 419 #define CHKOUT_NONE 0x0000u             /*   no output */
 420 #define CHKOUT_LIST 0x1000u             /*   structure list */
 421 #define CHKOUT_KEYS 0x2000u             /*   plain list of keys */
 422 #define CHKOUT_DUMP 0x3000u             /*   full multiline dump */
 423 #define CHKF_SANITY 0x0800u             /* checking user input */
 424
 425 struct my_checkstate {
 426   /* Checking state. */
 427
 428   unsigned f;                           /* flags */
 429 #define CF_SPC 1u                       /*   put space before next output */
 430 };
 431
 432 struct my_nodeinfo {
 433   /* Per-node tracking information */
 434
 435   struct xyla_bt_ordinfo _ord;          /* order checking state */
 436   int lv;                               /* indentation level */
 437 };
 438
 439 static int my_check(unsigned op, const struct xyla_bt_check *chk)
 440 {
 441   /* Main checking and walking function. */
 442
 443   const struct my_node *node = CONST_MY_NODE(chk->node), *left, *right;
 444   struct my_checkstate *st = chk->state;
 445   struct my_nodeinfo
 446     *node_info = chk->node_info,
 447     *parent_info = chk->parent_info;
 448   size_t want;
 449   int rc = XYLA_RC_OK, subrc;
 450
 451   switch (op) {
 452     case XYLA_CHKOP_NIL:
 453       /* Reached a null link.  Some dump types print something distinctive
 454        * if the entire tree is empty, which we can determine easily enough.
 455        * The `CHKOUT_LIST' format needs to indicate all null links
 456        * explicitly.
 457        */
 458
 459       switch (chk->f&CHKF_OUTMASK) {
 460         case CHKOUT_NONE:
 461           break;
 462         case CHKOUT_LIST:
 463           putc('_', out);
 464           break;
 465         case CHKOUT_KEYS:
 466           if (chk->pos == XYLA_BTPOS_ROOT) fputs("(empty tree)", out);
 467           break;
 468         case CHKOUT_DUMP:
 469           if (chk->pos == XYLA_BTPOS_ROOT)
 470             fputs("\t(tree empty)\n", out);
 471           break;
 472       }
 473       break;
 474
 475     case XYLA_CHKOP_BEFORE:
 476       /* Called before the children.  Set up our indentation level, which
 477        * is a little tricky for red-black trees, because we align black
 478        * nodes.
 479        */
 480
 481       if (!parent_info)
 482         node_info->lv = 0;
 483       else
 484 #if TREE == RB
 485       if (!(node->rb.f&XYLA_RBF_RED))
 486         node_info->lv = (parent_info->lv + 2)&~1;
 487       else
 488 #endif
 489         node_info->lv = parent_info->lv + 1;
 490       if ((chk->f&CHKF_OUTMASK) == CHKOUT_LIST) putc('(', out);
 491       break;
 492
 493     case XYLA_CHKOP_MID:
 494       /* Called after the left subtree.  This is where the main printing
 495        * happens.
 496        */
 497
 498       switch (chk->f&CHKF_OUTMASK) {
 499         case CHKOUT_NONE:
 500           break;
 501         case CHKOUT_LIST:
 502           putc(' ', out);
 503 #if TREE == RB
 504           if (!(node->rb.f&XYLA_RBF_RED)) putc('*', out);
 505 #elif TREE == TREAP
 506           fprintf(out, "0x%08lx$ ", (unsigned long)node->trp.wt);
 507 #endif
 508           fprintf(out, "%lu", node->k);
 509           putc(' ', out);
 510           break;
 511         case CHKOUT_KEYS:
 512           if (!(st->f&CF_SPC)) st->f |= CF_SPC;
 513           else putc(' ', out);
 514           fprintf(out, "%lu", node->k);
 515           break;
 516         case CHKOUT_DUMP:
 517           fprintf(out, "\t#0x%08lx (n = %3lu)\t%*s",
 518                  node->seq, (unsigned long)node->n, 4*node_info->lv, "");
 519 #if TREE == AVL
 520           fprintf(out, "(%c)", AVL_BALCH(node));
 521 #elif TREE == RB
 522           fprintf(out, "(%c)", node->rb.f&XYLA_RBF_RED ? ' ' : '*');
 523 #else
 524           fputs("(*)", out);
 525 #endif
 526 #if TREE == TREAP
 527           fprintf(out, " 0x%08lx$", (unsigned long)node->trp.wt);
 528 #endif
 529           fprintf(out, " %lu\n", node->k);
 530           break;
 531       }
 532       break;
 533
 534     case XYLA_CHKOP_AFTER:
 535       /* Called after the right subtree.  This is where we check that the
 536        * node count is correct and that the user flags are faithfully
 537        * preserved.
 538        */
 539
 540       left = CONST_MY_NODE(chk->left);
 541       right = CONST_MY_NODE(chk->right);
 542       want = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 543       if (node->n != want) {
 544         if (chk->fp) {
 545           xyla_bt_bughdr("MY_TREE", chk->root, chk->fp);
 546           xyla_bt_printnode(chk->cls, &node->bt, chk->fp);
 547           fprintf(chk->fp, " count %lu /= %lu\n",
 548                   (unsigned long)node->n, (unsigned long)want);
 549         }
 550         rc = XYLA_RC_BAD;
 551       }
 552 #ifdef FLAGMASK
 553       if ((node->T.f&FLAGMASK) != node->fref) {
 554         if (chk->fp) {
 555           xyla_bt_bughdr("MY_TREE", chk->root, chk->fp);
 556           xyla_bt_printnode(chk->cls, &node->bt, chk->fp);
 557           fprintf(chk->fp, " flags %x /= %x\n",
 558                   node->T.f&FLAGMASK, node->fref);
 559         }
 560         rc = XYLA_RC_BAD;
 561       }
 562 #endif
 563       if ((chk->f&CHKF_OUTMASK) == CHKOUT_LIST) putc(')', out);
 564       break;
 565   }
 566
 567   /* Check that the ordering is respected. */
 568   subrc = xyla_bt_chkorder(op, chk);
 569     if (subrc) { rc = subrc; if (subrc != XYLA_RC_BAD) goto end; }
 570
 571   /* Done. */
 572 end:
 573   return (rc);
 574 }
 575
 576 static void my_ident(struct xyla_bt_nodecls *cls,
 577                      const struct xyla_bt_node *node, FILE *fp)
 578 {
 579   /* Node identification function. */
 580
 581   const struct my_node *my_node = CONST_MY_NODE(node);
 582
 583   fprintf(fp, "#<node #0x%08lx ", my_node->seq);
 584 #if TREE == TREAP
 585   fprintf(fp, "0x%08lx$ ", (unsigned long)my_node->trp.wt);
 586 #endif
 587   fprintf(fp, "%lu>", my_node->k);
 588 }
 589
 590 static const struct xyla_bt_chkops my_ops = {
 591   /* Node class operations table. */
 592
 593   { sizeof(my_ops), my_upd },
 594   { my_ordnav, my_key },
 595   { my_check, sizeof(struct my_nodeinfo), my_ident },
 596 };
 597
 598 /*----- Node utilities ----------------------------------------------------*/
 599
 600 static union my_nodeu *make_node(unsigned long k)
 601 {
 602   /* Return a fresh node with key K. */
 603
 604   union my_nodeu *node;
 605
 606   node = malloc(sizeof(*node));
 607   if (!node) bail(BCAT_FAIL, "out of memory");
 608 #ifdef FLAGMASK
 609   node->my.fref = node->my.T.f = randwt()&FLAGMASK;
 610 #endif
 611   node->my.n = 99; node->my.seq = nodeseq++; node->my.k = k;
 612   if (nodes) nodes->prev = &node->my;
 613   node->my.next = nodes; node->my.prev = 0; nodes = &node->my;
 614   return (node);
 615 }
 616
 617 static void free_node(struct my_node *node)
 618 {
 619   /* Free a node which we don't want any more. */
 620
 621   struct my_node *next = node->next, *prev = node->prev;
 622
 623   if (next) next->prev = prev;
 624   if (prev) prev->next = next;
 625   else nodes = next;
 626   free(node);
 627 }
 628
 629 static void free_tree(struct xyla_bt_node **root)
 630 {
 631   /* Free the tree rooted at ROOT. */
 632
 633   while (*root) free_node(xyla_bt_severfirst(root));
 634 }
 635
 636 static void check_dump(struct xyla_bt_nodecls *cls,
 637                        struct xyla_bt_node *const *root HARG(int expht),
 638                        unsigned f)
 639 {
 640   /* Run a check or dump of the tree at ROOT.
 641    *
 642    * If output is requested, then suppress checking output.  If there were
 643    * problems them report them afterwards.  If we didn't have a full dump
 644    * and problems were found, then print a dump afterwards.
 645    */
 646
 647   struct my_checkstate st;
 648   int rc;
 649   H( int ht; )
 650
 651   st.f = 0;
 652   if ((f&CHKF_OUTMASK) == CHKOUT_DUMP) {
 653     fputs("tree dump", out);
 654     H( if (expht != -1) fprintf(out, ", ht = %d", expht); )
 655     putc('\n', out);
 656   }
 657   rc = TREE_CHECK(cls, root,
 658                   (f&CHKF_OUTMASK) == CHKOUT_NONE ? stderr : 0, f
 659                   HARG(expht), &st);
 660 #ifdef HAVE_HEIGHT
 661   if ((f&CHKF_OUTMASK) == CHKOUT_NONE) {
 662     ht = TREE_HEIGHT(CONST_TREE_NODE(*root));
 663     if (ht != expht) {
 664       xyla_bt_bughdr("MY_TREE", root, stderr);
 665       fprintf(stderr, "expected height %d /= %d\n", expht, ht);
 666       if (!rc) rc = XYLA_RC_BAD;
 667     }
 668   }
 669 #endif
 670   if ((f&CHKF_OUTMASK) == CHKOUT_LIST || (f&CHKF_OUTMASK) == CHKOUT_KEYS)
 671     putc('\n', out);
 672   if (rc) {
 673     if ((f&CHKF_OUTMASK) != CHKOUT_NONE)
 674       TREE_CHECK(cls, root, stderr, CHKOUT_NONE HARG(expht), &st);
 675     if ((f&CHKF_OUTMASK) != CHKOUT_DUMP) {
 676       fputs("offending tree...\n", out);
 677       TREE_CHECK(cls, root, 0, CHKOUT_DUMP HARG(expht), &st);
 678     }
 679     if (f&CHKF_SANITY) bail(BCAT_ERR, "invalid tree: %s", xyla_strerror(rc));
 680     else bail(BCAT_BUG, "check failed: %s", xyla_strerror(rc));
 681   }
 682 }
 683
 684 static union my_nodeu *copy_tree(const union my_nodeu *node)
 685 {
 686   /* Make a copy of a tree.
 687    *
 688    * The nodes have new sequence numbers, but should otherwise be identical.
 689    */
 690
 691   union my_nodeu *copy, *left, *right;
 692
 693   if (!node) return (0);
 694   left = copy_tree(CONST_MY_NODEU(node->bt.left));
 695   right = copy_tree(CONST_MY_NODEU(node->bt.right));
 696   copy = make_node(node->my.k);
 697 #ifdef FLAGMASK
 698   copy->my.T.f = node->my.T.f;
 699   copy->my.fref = node->my.fref;
 700 #elif TREE == SPLAY
 701   copy->my.spl.parent = 0;
 702   if (left) left->my.spl.parent = &copy->spl;
 703   if (right) right->my.spl.parent = &copy->spl;
 704 #elif TREE == TREAP
 705   copy->my.trp.wt = node->my.trp.wt;
 706 #endif
 707   copy->my.bt.left = left ? &left->bt : 0;
 708   copy->my.bt.right = right ? &right->bt : 0;
 709   copy->my.n = node->my.n;
 710   return (copy);
 711 }
 712
 713 static int ascend_index(struct xyla_bt_node *node,
 714                         struct xyla_bt_node *parent,
 715                         struct xyla_bt_node *sibling,
 716                         unsigned pos, void *arg)
 717 {
 718   /* Ascension function to determine a node's index. */
 719
 720   struct my_node *mysib = MY_NODE(sibling);
 721   size_t *i_inout = arg;
 722
 723   if (pos == XYLA_BTPOS_RIGHT)
 724     *i_inout += 1 + (mysib ? mysib->n : 0);
 725   return (0);
 726 }
 727
 728 static size_t path_index(struct PATH *path)
 729 {
 730   /* Return the index of a node given a full path to it. */
 731
 732   struct my_node *mynode, *myleft;
 733   size_t i = 0;
 734
 735   mynode = TREE_CURRENT(path);
 736   if (mynode) {
 737     myleft = MY_NODE(mynode->bt.left);
 738     if (myleft) i += myleft->n;
 739   }
 740
 741   TREE_ASCEND(ascend_index, path, &i);
 742   return (i);
 743 }
 744
 745 static int full_path_p(struct PATH *path)
 746 {
 747   /* Return wehther PATH is full. */
 748
 749   return (!!TREE_CURRENT(path));
 750 }
 751
 752 static struct xyla_bt_node *read_tree(HELSE(int *ht_out, void))
 753 {
 754   /* Read a tree structure description from the input file and return
 755    * a pointer to the root.
 756    *
 757    * If the tree has a notion of height, then return the height in *HT_OUT.
 758    */
 759
 760   union my_nodeu *node;
 761   struct my_node *left, *right;
 762   int ch;
 763   unsigned long k;
 764   H( int ht; int lht; int rht; )
 765 #if TREE == AVL
 766   unsigned f = 3;
 767 #elif TREE == RB
 768   unsigned f = XYLA_RBF_RED;
 769 #elif TREE == TREAP
 770   size_t wt = 0, lwt, rwt;
 771   unsigned f = 0;
 772 #  define f_weight 1u
 773 #endif
 774
 775   /* Check for a `_' indicating a nil subtree, or the open paren. */
 776   do ch = getc(in); while (isspace(ch));
 777   if (ch == '_') { H( *ht_out = 0; ) return (0); }
 778   else if (ch != '(') bail(BCAT_ERR, "expected `(', found `%c'", ch);
 779
 780   /* Read the left subtree. */
 781   left = MY_NODE(read_tree(H(&lht)));
 782
 783   /* Read flags before the node proper. */
 784   for (;;) {
 785     do ch = getc(in); while (isspace(ch));
 786 #if TREE == AVL
 787     if (f == 3 && ch == '-') f = XYLA_AVLBAL_LBIAS;
 788     else if (f == 3 && ch == '=') f = XYLA_AVLBAL_EVEN;
 789     else if (f == 3 && ch == '+') f = XYLA_AVLBAL_RBIAS;
 790     else
 791 #elif TREE == RB
 792     if (ch == '*') f &= ~XYLA_RBF_RED;
 793     else
 794 #endif
 795     break;
 796   }
 797
 798   /* Read the node key. */
 799   ungetc(ch, in); k = read_int();
 800   do ch = getc(in); while (isspace(ch));
 801
 802   /* If this is a treap, then maybe that was actually the node weight.
 803    * If so, stash it and read the real key.
 804    */
 805 #if TREE == TREAP
 806   if (ch == '$') { wt = k; f |= f_weight; k = read_int(); }
 807   else
 808 #endif
 809   ungetc(ch, in);
 810
 811   /* Read the right subtree. */
 812   right = MY_NODE(read_tree(H(&rht)));
 813
 814   /* Expect the closing paren. */
 815   do ch = getc(in); while (isspace(ch));
 816   if (ch != ')') bail(BCAT_ERR, "expected `)', found `%c'", ch);
 817
 818   /* Make the node. */
 819   node = make_node(k);
 820   node->my.bt.left = left ? &left->bt : 0;
 821   node->my.bt.right = right ? &right->bt : 0;
 822   node->my.n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 823
 824   /* Fill in the tree-specific bits. */
 825 #if TREE == AVL
 826   if (f != 3)
 827     ht = -1;
 828   else {
 829     if (lht == -1 || rht == -1)
 830       bail(BCAT_ERR, "missing balance annotation");
 831     switch (rht - lht) {
 832       case -1: f = XYLA_AVLBAL_LBIAS; ht = lht + 1; break;
 833       case  0: f = XYLA_AVLBAL_EVEN; ht = lht + 1; break;
 834       case +1: f = XYLA_AVLBAL_RBIAS; ht = rht + 1; break;
 835       default: bail(BCAT_ERR, "tree is not AVL");
 836     }
 837   }
 838   node->my.avl.f = (node->my.avl.f&FLAGMASK) | f;
 839 #elif TREE == RB
 840   ht = f&XYLA_RBF_RED ? lht : lht + 1;
 841   node->my.rb.f = (node->my.rb.f&FLAGMASK) | f;
 842 #elif TREE == SPLAY
 843   if (left) left->spl.parent = &node->spl;
 844   if (right) right->spl.parent = &node->spl;
 845   node->my.spl.parent = 0;
 846 #elif TREE == TREAP
 847   lwt = left ? left->trp.wt : 0xffffffff;
 848   rwt = right ? right->trp.wt : 0xffffffff;
 849   if (f&f_weight)
 850     node->my.trp.wt = wt;
 851   else {
 852     wt = (((rwt < lwt ? rwt : lwt)&0xfff00000) - (1ul << 20)) | node->my.seq;
 853     if (wt > lwt || wt > rwt) bail(BCAT_ERR, "tree is not a treap");
 854     node->my.trp.wt = wt;
 855   }
 856 #endif
 857
 858   /* Save the subtree height. */
 859   H( *ht_out = ht; )
 860
 861   /* All done. */
 862   return (&node->bt);
 863
 864 #if TREE == TREAP
 865 #  undef f_weight
 866 #endif
 867 }
 868
 869 /*----- Main program ------------------------------------------------------*/
 870
 871 int main(int argc, char *argv[])
 872 {
 873 #define NSTACK 16
 874
 875   struct xyla_bt_nodecls mycls;
 876   struct { struct xyla_bt_node *root; H( int ht; ) } cur, stack[NSTACK], u;
 877   struct my_node *node = 0, *t;
 878   union my_nodeu *nodeu;
 879 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 880   struct my_node *x, *y;
 881 #endif
 882 #if TREE != SPLAY
 883   struct xyla_bt_node **link;
 884 #endif
 885   struct xyla_bt_node *btnode;
 886   struct ITER it;
 887   struct RITER rit;
 888   struct PATH path;
 889   unsigned pos;
 890   const char *p;
 891   int opt, ch, rc, sp = 0;
 892   unsigned long i, j, k;
 893 #if TREE == TREAP
 894   size_t wt = 0;
 895 #endif
 896   V( unsigned v; )
 897   unsigned f = 0;
 898 #define f_path 1u
 899 #define f_key 2u
 900 #define f_first 4u
 901 #define f_weight 8u
 902
 903   /* Parse command-line options. */
 904   opt = 1;
 905   for (;;) {
 906     if (opt >= argc) break;
 907     p = argv[opt];
 908     if (*p != '-') break;
 909     p++; if (!*p) break;
 910     if (*p == '-' && !p[1]) { opt++; break; }
 911     for (;;) {
 912 #define GETARG do {                                                     \
 913   if (!*p) {                                                            \
 914     if (opt >= argc) bail(BCAT_ERR, "missing argument");                \
 915     p = argv[++opt];                                                    \
 916   }                                                                     \
 917 } while (0)
 918       switch (*p++) {
 919         case 'o': GETARG; open_file(p, DIR_OUT); goto next_arg;
 920         default: bail(BCAT_ERR, "unknown option `-%c'", p[-1]);
 921       }
 922 #undef GETARG
 923     }
 924   next_arg:
 925     opt++;
 926   }
 927
 928   /* Initialize my node class. */
 929   mycls.ops = &my_ops.node;
 930
 931   /* Initialize the current tree. */
 932   cur.root = 0; H( cur.ht = 0; )
 933
 934   /* Set up the input and output streams. */
 935   if (!out) out = stdout;
 936   if (opt >= argc) in = stdin;
 937   else open_file(argv[opt++], DIR_IN);
 938   V( xyla__verbout = out; )
 939
 940   for (;;) {
 941     do ch = getc(in); while (isspace(ch));
 942     switch (ch) {
 943
 944       case EOF:
 945         if (opt < argc) open_file(argv[opt++], DIR_IN);
 946         else goto done;
 947         break;
 948
 949       case ';': /* comment */
 950         do ch = getc(in); while (ch != EOF && ch != '\n');
 951         break;
 952
 953       case ':': /* print message */
 954         for (;;) {
 955           ch = getc(in); if (ch == '\n' || ch == EOF) break;
 956           putc(ch, out);
 957         }
 958         putc('\n', out);
 959         break;
 960
 961       case '.':
 962         stop = 1;
 963         break;
 964
 965       case '+': /* insert */
 966         if (!(f&f_key)) bail(BCAT_ERR, "no key");
 967         if (!(f&f_path))
 968           node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
 969         else {
 970 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
 971           bail(BCAT_ERR, "placed insertion is out-of-bounds for fuzzers");
 972 #else
 973           if (full_path_p(&path)) bail(BCAT_ERR, "path full");
 974 #endif
 975         }
 976         if (node) bail(BCAT_ERR, "key %lu already present", k);
 977         nodeu = make_node(k);
 978 #if TREE == TREAP
 979         if (f&f_weight) nodeu->my.trp.wt = wt;
 980         else nodeu->my.trp.wt = randwt();
 981 #endif
 982         rc = TREE_INSERT(&mycls, &path, &nodeu->T);
 983           H( if (rc == XYLA_RC_HTCHG) cur.ht++; else )
 984           if (rc)
 985             bail(BCAT_BUG, "insert returned #%s: %s",
 986                  rctag(rc), xyla_strerror(rc));
 987         node = &nodeu->my;
 988         f &= ~(f_key | f_path | f_weight);
 989         break;
 990
 991       case '-': /* remove */
 992         if (f&f_path) {
 993           if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
 994         } else {
 995           if (!(f&f_key)) bail(BCAT_ERR, "no key or path");
 996           node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
 997           if (!node) bail(BCAT_ERR, "key %lu not present", k);
 998         }
 999         rc = TREE_REMOVE(&mycls, &path);
1000           H( if (rc == XYLA_RC_HTCHG) cur.ht--; else )
1001           if (rc)
1002             bail(BCAT_BUG, "remove returned #%s: %s",
1003                  rctag(rc), xyla_strerror(rc));
1004         free_node(node); node = 0; f &= ~(f_key | f_path);
1005         break;
1006
1007       case '#': /* populate */
1008         i = read_int();
1009         do ch = getc(in); while (isspace(ch));
1010         if (ch == '-') j = read_int();
1011         else { ungetc(ch, in); j = i; i = 1; }
1012         for (;;) {
1013           if (!TREE_PROBE(&mycls, &cur.root, my_ordnav, &i, &path)) {
1014             nodeu = make_node(i);
1015 #if TREE == TREAP
1016             nodeu->my.trp.wt = randwt();
1017 #endif
1018             rc = TREE_INSERT(&mycls, &path, &nodeu->T);
1019               H( if (rc == XYLA_RC_HTCHG) cur.ht++; else )
1020               if (rc)
1021                 bail(BCAT_BUG, "insert returned #%s: %s",
1022                      rctag(rc), xyla_strerror(rc));
1023           }
1024           if (i == j) break;
1025           else if (i < j) i++;
1026           else i--;
1027         }
1028         node = 0; f &= ~(f_key | f_path | f_weight);
1029         break;
1030
1031       case '?': /* lookup */
1032         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1033         node = TREE_LOOKUP(&mycls, &cur.root, my_ordnav, &k);
1034         f &= ~(f_key | f_path);
1035         break;
1036
1037       case '@': /* probe */
1038         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1039         node = TREE_PROBE(&mycls, &cur.root, my_ordnav, &k, &path);
1040         f = (f&~f_key) | f_path;
1041         break;
1042
1043       case ',': /* lookup/probe by index */
1044         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1045         ch = getc(in);
1046         switch (ch) {
1047           case '?':
1048             node = TREE_LOOKUP(&mycls, &cur.root, my_idxnav, &k);
1049             f &= ~(f_key | f_path);
1050             break;
1051           case '@':
1052             node = TREE_PROBE(&mycls, &cur.root, my_idxnav, &k, &path);
1053             f = (f&~f_key) | f_path;
1054             break;
1055           default:
1056             bail(BCAT_ERR, "expected `?' or `@', found `%c'", ch);
1057             break;
1058         }
1059         break;
1060
1061       case 't': /* root (`top') */
1062         node = TREE_ROOTPATH(&cur.root, &path);
1063         if (!node) f &= ~f_key;
1064         else { k = node->k; f |= f_key; }
1065         f |= f_path;
1066         break;
1067
1068       case 'u': /* up */
1069         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1070         node = TREE_UPPATH(&pos, &path);
1071         switch (pos) {
1072           case XYLA_BTPOS_ROOT: fputs("root\n", out); break;
1073           case XYLA_BTPOS_LEFT: fputs("left\n", out); break;
1074           case XYLA_BTPOS_RIGHT: fputs("right\n", out); break;
1075           default: bail(BCAT_BUG, "unexpected position code %u\n", pos);
1076         }
1077         break;
1078
1079       case 'l': /* left */
1080         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1081         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1082         node = TREE_LEFTPATH(&path);
1083         if (!node) f &= ~f_key;
1084         else { k = node->k; f |= f_key; }
1085         break;
1086
1087       case 'r': /* right */
1088         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1089         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1090         node = TREE_RIGHTPATH(&path);
1091         if (!node) f &= ~f_key;
1092         else { k = node->k; f |= f_key; }
1093         break;
1094
1095       case '[': /* first */
1096         node = TREE_FIRSTPATH(&cur.root, &path);
1097         if (!node) f &= ~f_key;
1098         else { k = node->k; f |= f_key; }
1099         f |= f_path;
1100         break;
1101
1102       case ']': /* last */
1103         node = TREE_LASTPATH(&cur.root, &path);
1104         if (!node) f &= ~f_key;
1105         else { k = node->k; f |= f_key; }
1106         f |= f_path;
1107         break;
1108
1109       case 'c': /* current */
1110         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1111         node = TREE_CURRENT(&path);
1112         if (!node) f &= ~f_key;
1113         else { k = node->k; f |= f_key; }
1114         break;
1115
1116       case '<': /* previous */
1117         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1118         node = TREE_PREVPATH(&path);
1119         if (!node) f &= ~f_key;
1120         else { k = node->k; f |= f_key; }
1121         break;
1122
1123       case '>': /* next */
1124         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1125         node = TREE_NEXTPATH(&path);
1126         if (!node) f &= ~f_key;
1127         else { k = node->k; f |= f_key; }
1128         break;
1129
1130       case '{': /* before */
1131         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1132         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1133         TREE_BEFOREPATH(&path); f &= ~f_key;
1134         break;
1135
1136       case '}': /* after */
1137         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1138         else if (!full_path_p(&path)) bail(BCAT_ERR, "path empty");
1139         TREE_AFTERPATH(&path); f &= ~f_key;
1140         break;
1141
1142       case '*': /* clear */
1143         node = 0; f &= ~(f_key | f_path);
1144         break;
1145
1146       case '(': /* push */
1147         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1148         stack[sp++] = cur; cur.root = 0; H( cur.ht = 0; )
1149         node = 0; f &= ~(f_key | f_path | f_weight);
1150         break;
1151
1152       case '"': /* duplicate */
1153         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1154         stack[sp++] = cur;
1155         cur.root = (struct xyla_bt_node *)copy_tree(MY_NODEU(cur.root));
1156         node = 0; f &= ~(f_key | f_path | f_weight);
1157         break;
1158
1159       case ')': /* pop */
1160         if (!sp) bail(BCAT_ERR, "stack empty");
1161         free_tree(&cur.root); cur = stack[--sp];
1162         node = 0; f &= ~(f_key | f_path | f_weight);
1163         break;
1164
1165       case '%': /* swap */
1166         if (!sp) bail(BCAT_ERR, "stack empty");
1167         u = stack[sp - 1]; stack[sp - 1] = cur; cur = u;
1168         node = 0; f &= ~(f_key | f_path | f_weight);
1169         break;
1170
1171       case '~': /* join */
1172         if (!sp) bail(BCAT_ERR, "stack empty");
1173         if (!(f&f_key)) t = 0;
1174         else {
1175           t = &make_node(k)->my;
1176 #  if TREE == TREAP
1177           if (f&f_weight) t->trp.wt = wt;
1178           else t->trp.wt = randwt();
1179 #  endif
1180         }
1181 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1182         x = TREE_LASTPATH(&stack[sp - 1].root, &path);
1183         y = TREE_FIRSTPATH(&cur.root, &path);
1184         if (!t ? x && y && x->k >= y->k
1185                : (x && x->k >= t->k) || (y && t->k >= y->k))
1186           bail(BCAT_ERR, "invalid ordering");
1187 #endif
1188         rc = TREE_JOIN(&mycls, &cur.root HARG(&cur.ht),
1189                        &stack[sp - 1].root HARG(stack[sp - 1].ht),
1190                        t ? &t->bt : 0,
1191                        &cur.root HARG(cur.ht));
1192           if (rc)
1193             bail(BCAT_BUG, "join returned #%s: %s",
1194                  rctag(rc), xyla_strerror(rc));
1195         sp--; node = 0; f &= ~(f_key | f_path | f_weight);
1196         break;
1197
1198       case '/': /* split */
1199         if (sp > NSTACK - 2) bail(BCAT_ERR, "stack full");
1200         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1201         rc = TREE_SPLIT(&mycls, &stack[sp].root HARG(&stack[sp].ht),
1202                         &btnode,
1203                         &cur.root HARG(&cur.ht),
1204                         &path);
1205           if (rc)
1206             bail(BCAT_BUG, "split returned #%s: %s",
1207                  rctag(rc), xyla_strerror(rc));
1208         node = MY_NODE(btnode);
1209         if (node) node->n = 1;
1210         stack[sp + 1].root = node ? &node->bt : 0;
1211         H( stack[sp + 1].ht = node ? 1 : 0; )
1212         sp += 2; f &= ~(f_key | f_path | f_weight);
1213         break;
1214
1215       case '|': /* union/intersection */
1216         if (!sp) bail(BCAT_ERR, "stack empty");
1217         rc = TREE_UNISECT(&mycls, &cur.root HARG(&cur.ht),
1218                           &stack[sp - 1].root HARG(&stack[sp - 1].ht),
1219                           &stack[sp - 1].root HARG(stack[sp - 1].ht),
1220                           &cur.root HARG(cur.ht));
1221           if (rc)
1222             bail(BCAT_BUG, "unisect returned #%s: %s",
1223                  rctag(rc), xyla_strerror(rc));
1224         node = 0; f &= ~(f_key | f_path | f_weight);
1225         break;
1226
1227       case '\\': /* difference/intersection */
1228         if (!sp) bail(BCAT_ERR, "stack empty");
1229         if (sp >= NSTACK) bail(BCAT_ERR, "stack full");
1230         rc = TREE_DIFFSECT(&mycls, &cur.root HARG(&cur.ht),
1231                            &stack[sp].root HARG(&stack[sp].ht),
1232                            &cur.root HARG(cur.ht),
1233                            &stack[sp - 1].root);
1234           if (rc)
1235             bail(BCAT_BUG, "diffsect returned #%s: %s",
1236                  rctag(rc), xyla_strerror(rc));
1237         sp++; node = 0; f &= ~(f_key | f_path | f_weight);
1238         break;
1239
1240       case '^': /* ascend */
1241         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1242         fprintf(out, "%lu\n", (unsigned long)path_index(&path));
1243         break;
1244
1245       case 'k': /* print key */
1246         if (f&f_key) {
1247 #if TREE == TREAP
1248           if (f&f_weight) fprintf(out, "0x%08lx$ ", (unsigned long)wt);
1249 #endif
1250           fprintf(out, "%lu\n", k);
1251         }
1252         else fputs("(no key)\n", out);
1253         break;
1254
1255       case 'n': /* print node */
1256         if (!node) fputs("(nil)\n", out);
1257         else fprintf(out, "#<node #0x%08lx %lu>\n", node->seq, node->k);
1258         break;
1259
1260       case 'p': /* print path */
1261         if (!(f&f_path))
1262           fprintf(out, "(nil)\n");
1263         else {
1264           putc('(', out);
1265 #if TREE == SPLAY
1266           if (path.root == &cur.root) fputs("#<link root -> ", out);
1267           else fprintf(out, "#<link address %p -> ... ", (void *)path.root);
1268           t = MY_SPLAY_NODE(path.node);
1269           if (!t)
1270             fputs("(nil)>", out);
1271           else {
1272             fprintf(out, "node #0x%08lx %lu>", t->seq, t->k);
1273             if (path.f)
1274               fprintf(out, " #<node #0x%08lx %lu %s> -> (nil)",
1275                      t->seq, t->k,
1276                      path.f == XYLA_SPF_LEFT ? "left" : "right");
1277           }
1278 #else
1279           t = 0;
1280           for (i = 0, t = 0; i <= path.k; i++) {
1281             if (i) putc(' ', out);
1282             link = path.p[i];
1283             if (!t && link == &cur.root)
1284               fputs("#<link root -> ", out);
1285             else if (t && link == &t->bt.left)
1286               fprintf(out, "#<link node #0x%08lx %lu left -> ",
1287                       t->seq, t->k);
1288             else if (t && link == &t->bt.right)
1289               fprintf(out, "#<link node #0x%08lx %lu right -> ",
1290                       t->seq, t->k);
1291             else
1292               fprintf(out, "#<link address %p -> ", (void *)link);
1293             t = MY_NODE(*link);
1294             if (!t) fputs("(nil)", out);
1295             else fprintf(out, "node #0x%08lx %lu", t->seq, t->k);
1296             putc('>', out);
1297           }
1298 #endif
1299           putc(')', out); putc('\n', out);
1300         }
1301         break;
1302
1303       case 'i': /* iterate */
1304         TREE_INITITER(cur.root, &it); f |= f_first;
1305         for (;;) {
1306           t = TREE_NEXT(&it); if (!t) break;
1307           if (f&f_first) f &= ~f_first;
1308           else putc(' ', out);
1309           fprintf(out, "%lu", t->k);
1310         }
1311         if (f&f_first) fputs("(empty tree)", out);
1312         putc('\n', out);
1313         break;
1314
1315       case 'j': /* reverse iterate */
1316         TREE_INITRITER(cur.root, &rit); f |= f_first;
1317         for (;;) {
1318           t = TREE_PREV(&rit); if (!t) break;
1319           if (f&f_first) f &= ~f_first;
1320           else putc(' ', out);
1321           fprintf(out, "%lu", t->k);
1322         }
1323         if (f&f_first) fputs("(empty tree)", out);
1324         putc('\n', out);
1325         break;
1326
1327       case 'K': /* list keys */
1328         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_KEYS);
1329         break;
1330
1331       case 'L': /* list */
1332         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_LIST);
1333         break;
1334
1335       case 'D': /* dump */
1336         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_DUMP);
1337         break;
1338
1339       case '!': /* check */
1340         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_NONE);
1341         break;
1342
1343       case '=': /* assign */
1344         free_tree(&cur.root);
1345         cur.root = read_tree(H(&cur.ht));
1346 #if TREE == AVL
1347         if (cur.ht == -1) cur.ht = xyla_avl_height(AVL_NODE(cur.root));
1348 #endif
1349 #ifdef FUZZING_BUILD_MODE_UNSAFE_FOR_PRODUCTION
1350         check_dump(&mycls, &cur.root HARG(cur.ht), CHKOUT_NONE | CF_SANITY);
1351 #endif
1352         node = 0; f &= ~(f_key | f_path | f_weight);
1353         break;
1354
1355       case 'S': /* seed */
1356         seed = read_int();
1357         break;
1358
1359       case 'V': /* verbose */
1360         V( v = 0; )
1361         for (;;) {
1362           ch = getc(in);
1363           if (ch == EOF || isspace(ch)) break;
1364           switch (ch) {
1365             case ':':
1366               for (;;) {
1367                 ch = getc(in); if (ch == '\n' || ch == EOF) break;
1368                 NV( putc(ch, out); )
1369               }
1370               NV( putc('\n', out); )
1371               goto skip;
1372             case 'i': V( v |= XYLA__VF_ITER; ) break;
1373             case 'p': V( v |= XYLA__VF_PATH; ) break;
1374             case '@': V( v |= XYLA__VF_PROBE; ) break;
1375             case '+': V( v |= XYLA__VF_INSERT; ) break;
1376             case '-': V( v |= XYLA__VF_REMOVE; ) break;
1377             case '/': V( v |= XYLA__VF_SPLIT; ) break;
1378             case '~': V( v |= XYLA__VF_JOIN; ) break;
1379             case '|': V( v |= XYLA__VF_UNISECT; ) break;
1380             case '\\': V( v |= XYLA__VF_DIFFSECT; ) break;
1381 #if TREE == SPLAY
1382             case 'Z': V( v |= XYLA__VF_SPLAY; ) break;
1383 #endif
1384             default: bail(BCAT_ERR, "unexpected category `%c'", ch);
1385           }
1386         }
1387         V( xyla__verbose = v; )
1388         break;
1389
1390       case 'B': /* rebalance */
1391 #if TREE == SPLAY
1392         xyla_splay_rebalance(&mycls, &cur.root);
1393 #endif
1394         break;
1395
1396       case 'Z': /* splay */
1397         if (!(f&f_path)) bail(BCAT_ERR, "no path");
1398 #if TREE == SPLAY
1399         xyla_splay_splay(&mycls, &path);
1400 #endif
1401         break;
1402
1403 #if TREE == TREAP
1404       case '$': /* weight */
1405         if (!(f&f_key)) bail(BCAT_ERR, "no key");
1406         wt = k; f = (f&~f_key) | f_weight;
1407         break;
1408 #endif
1409
1410       default:
1411         if (isdigit(ch)) /* set key */
1412           { ungetc(ch, in); k = read_int(); f |= f_key; }
1413         else /* error */
1414           bail(BCAT_ERR, "unexpected character `%c'", ch);
1415         break;
1416     }
1417
1418   skip:
1419     check_file(DIR_OUT);
1420   }
1421
1422 done:
1423   /* Free the current tree and all of the stacked trees. */
1424   free_tree(&cur.root);
1425   for (i = 0; i < sp; i++) free_tree(&stack[i].root);
1426
1427   /* Work through the list.  Anything here has mysteriously gone missing
1428    * from all of the trees we've been tracking.
1429    */
1430   if (nodes) {
1431     fputs("leaked nodes...", out);
1432     for (node = nodes; node; node = node->next)
1433       fprintf(out, "\t#0x%08lx %lu\n", node->seq, node->k);
1434     bail(BCAT_BUG, "leaked nodes");
1435   }
1436
1437   /* The user is expected to clear the stack. */
1438   if (sp) bail(BCAT_ERR, "stack not empty");
1439
1440   /* Close the files and make sure all the output actually got out. */
1441   close_file(DIR_IN); close_file(DIR_OUT);
1442
1443   /* It's all over. */
1444   return (0);
1445
1446 #undef f_path
1447 #undef f_key
1448 #undef f_first
1449 #undef f_weight
1450
1451 #undef NSTACK
1452 }
1453
1454 /*----- That's all, folks -------------------------------------------------*/