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

   1 #include <assert.h>
   2 #include <ctype.h>
   3 #include <errno.h>
   4 #include <stdarg.h>
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <string.h>
   8
   9 #define AVL 1
  10 #define RB 2
  11 #define SPLAY 3
  12 #define TREAP 4
  13
  14 #if TREE == AVL
  15 #  include "avltree.h"
  16 #  define NODE avlnode
  17 #  define PATH avlpath
  18 #  define ITER avliter
  19 #  define TREE_CHECK avltree_check
  20 #  define TREE_HEIGHT avltree_height
  21 #  define TREE_LOOKUP avltree_lookup
  22 #  define TREE_PROBE avltree_probe
  23 #  define TREE_INITITER avltree_inititer
  24 #  define TREE_NEXT avltree_next
  25 #  define TREE_FIRSTPATH avltree_firstpath
  26 #  define TREE_LASTPATH avltree_lastpath
  27 #  define TREE_NEXTPATH avltree_nextpath
  28 #  define TREE_PREVPATH avltree_prevpath
  29 #  define TREE_INSERT avltree_insert
  30 #  define TREE_REMOVE avltree_remove
  31 #  define TREE_JOIN avltree_join
  32 #  define TREE_SPLIT avltree_split
  33 #  define TREE_SPLITAT avltree_splitat
  34 #  define TREE_UNISECT avltree_unisect
  35 #  define TREE_DIFFSECT avltree_diffsect
  36 #elif TREE == RB
  37 #  include "rbtree.h"
  38 #  define NODE rbnode
  39 #  define PATH rbpath
  40 #  define ITER rbiter
  41 #  define TREE_CHECK rbtree_check
  42 #  define TREE_HEIGHT rbtree_height
  43 #  define TREE_LOOKUP rbtree_lookup
  44 #  define TREE_PROBE rbtree_probe
  45 #  define TREE_INITITER rbtree_inititer
  46 #  define TREE_NEXT rbtree_next
  47 #  define TREE_FIRSTPATH rbtree_firstpath
  48 #  define TREE_LASTPATH rbtree_lastpath
  49 #  define TREE_NEXTPATH rbtree_nextpath
  50 #  define TREE_PREVPATH rbtree_prevpath
  51 #  define TREE_INSERT rbtree_insert
  52 #  define TREE_REMOVE rbtree_remove
  53 #  define TREE_JOIN rbtree_join
  54 #  define TREE_SPLIT rbtree_split
  55 #  define TREE_SPLITAT rbtree_splitat
  56 #  define TREE_UNISECT rbtree_unisect
  57 #  define TREE_DIFFSECT rbtree_diffsect
  58 #elif TREE == SPLAY
  59 #  include "splaytree.h"
  60 #elif TREE == TREAP
  61 #  include "treap.h"
  62 #else
  63 #  error "unknown `TREE' value"
  64 #endif
  65
  66 #ifdef __GNUC__
  67 __attribute__((used))
  68 #endif
  69 static int stop = 0;
  70
  71 struct my_node {
  72   struct NODE _n;
  73   size_t n;
  74   unsigned long seq, k;
  75 };
  76
  77 static unsigned long nodeseq = 0;
  78
  79 static int my_ordnav(struct bstree_nodecls *cls,
  80                      const struct bstnode *node, void *arg)
  81 {
  82   const struct my_node *mynode = (const struct my_node *)node;
  83   int *key = arg;
  84
  85   if (*key < mynode->k) return (-1);
  86   else if (*key > mynode->k) return (+1);
  87   else return (0);
  88 }
  89
  90 static void my_upd(struct bstree_nodecls *cls, struct bstnode *node)
  91 {
  92   struct my_node
  93     *mynode = (struct my_node *)node,
  94     *left = (struct my_node *)mynode->_n._bst.left,
  95     *right = (struct my_node *)mynode->_n._bst.right;
  96
  97   mynode->n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
  98 }
  99
 100 static const void *my_key(struct bstree_nodecls *cls,
 101                           const struct bstnode *node)
 102 {
 103   const struct my_node *mynode = (const struct my_node *)node;
 104   return (&mynode->k);
 105 }
 106
 107 static int my_check(struct bstree_nodecls *cls,
 108                     struct bstnode *const *root,
 109                     const struct bstnode *parent,
 110                     const struct bstnode *lbound,
 111                     const struct bstnode *rbound,
 112                     const struct bstnode *node, unsigned ord,
 113                     void *arg)
 114 {
 115   struct my_node *mynode, *left, *right;
 116   size_t want;
 117   int rc = 0;
 118
 119   if (ord == BSTCHK_BEFORE) {
 120     mynode = (struct my_node *)node;
 121     left = (struct my_node *)mynode->_n._bst.left;
 122     right = (struct my_node *)mynode->_n._bst.right;
 123     want = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 124     if (mynode->n != want) {
 125       fprintf(stderr, "MY_TREE %p BUG: node #%08lx %lu count %lu /= %lu\n",
 126               (void *)root, mynode->seq, mynode->k,
 127               (unsigned long)mynode->n, (unsigned long)want);
 128       rc = -1;
 129     }
 130   }
 131
 132   if (bstree_chkorder(cls, root, parent, lbound, rbound, node, ord, arg))
 133     rc = -1;
 134
 135   return (rc);
 136 }
 137
 138 static void my_ident(struct bstree_nodecls *cls,
 139                      const struct bstnode *node, FILE *fp)
 140 {
 141   const struct my_node *my_node = (const struct my_node *)node;
 142   fprintf(fp, "#0x%08lx %lu", my_node->seq, my_node->k);
 143 }
 144
 145 static const struct bstree_nodeops my_ordops =
 146   { my_ordnav, my_upd, my_key, my_check, my_ident };
 147
 148 static void bail(const char *msg, ...)
 149 {
 150   va_list ap;
 151   long pos;
 152
 153   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 154   pos = ftell(stdin);
 155   if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 156   fputc('\n', stderr);
 157   exit(2);
 158 }
 159
 160 static struct my_node *make_node(unsigned long k)
 161 {
 162   struct my_node *node;
 163
 164   node = malloc(sizeof(*node));
 165   if (!node) bail("out of memory");
 166   node->_n.f = 0; node->n = 1; node->seq = nodeseq++; node->k = k;
 167   return (node);
 168 }
 169
 170 #if TREE == AVL
 171 static const char balch[3] = { '=', '-', '+' };
 172 #endif
 173
 174 static void dump_recurse(const struct my_node *node, int indent)
 175 {
 176   if (!node) return;
 177 #if TREE == RB
 178   if (node->_n.f&RBF_RED) indent++;
 179   else indent = (indent + 2)&~1;
 180 #else
 181   indent++;
 182 #endif
 183   dump_recurse((const struct my_node *)node->_n._bst.left, indent);
 184   printf("\t#0x%08lx (n = %3lu)\t%*s",
 185          node->seq, (unsigned long)node->n, 4*indent, "");
 186 #if TREE == AVL
 187   printf("(%c)", balch[node->_n.f&AVLF_BALMASK]);
 188 #elif TREE == RB
 189   printf("(%c)", node->_n.f&RBF_RED ? ' ' : '*');
 190 #else
 191   fputs("(*)", stdout);
 192 #endif
 193   printf(" %lu\n", node->k);
 194   dump_recurse((const struct my_node *)node->_n._bst.right, indent);
 195 }
 196
 197 void dump_tree(const struct bstnode *root, int ht)
 198 {
 199   printf("tree dump, ht = %d\n", ht);
 200   if (!root) printf("\t(tree empty)\n");
 201   else dump_recurse((const struct my_node *)root, -1);
 202 }
 203
 204 static void list_recurse(const struct my_node *node)
 205 {
 206   if (!node)
 207     putchar('_');
 208   else {
 209     putchar('(');
 210     list_recurse((const struct my_node *)node->_n._bst.left);
 211     putchar(' ');
 212 #if TREE == RB
 213     if (!(node->_n.f&RBF_RED)) putchar('*');
 214 #endif
 215     printf("%lu", node->k);
 216     putchar(' ');
 217     list_recurse((const struct my_node *)node->_n._bst.right);
 218     putchar(')');
 219   }
 220 }
 221
 222 static void list_tree(struct bstnode *root)
 223   { list_recurse((struct my_node *)root); putchar('\n'); }
 224
 225 static struct bstnode *copy_tree(const struct my_node *node)
 226 {
 227   struct my_node *copy;
 228
 229   if (!node) return (0);
 230   copy = make_node(node->k);
 231 #if TREE == AVL || TREE == RB
 232   copy->_n.f = node->_n.f;
 233 #endif
 234   copy->_n._bst.left =
 235     copy_tree((const struct my_node *)node->_n._bst.left);
 236   copy->_n._bst.right =
 237     copy_tree((const struct my_node *)node->_n._bst.right);
 238   copy->n = node->n;
 239   return (&copy->_n._bst);
 240 }
 241
 242 static unsigned long read_int(void)
 243 {
 244   unsigned long k;
 245   int ch;
 246
 247   do ch = getchar(); while (isspace(ch));
 248   if (!isdigit(ch)) bail("integer expected, found `%c'", ch);
 249   ungetc(ch, stdin);
 250   if (scanf("%lu", &k) != 1) bail("integer expected, scanf failed");
 251   return (k);
 252 }
 253
 254 static struct bstnode *read_tree(int *ht_out)
 255 {
 256   struct my_node *node, *left, *right;
 257   int ch;
 258   unsigned long k;
 259   int ht, lht, rht;
 260 #if TREE == AVL
 261   unsigned f;
 262 #elif TREE == RB
 263   unsigned f = RBF_RED;
 264 #endif
 265
 266   do ch = getchar(); while (isspace(ch));
 267   if (ch == '_') { *ht_out = 0; return (0); }
 268   else if (ch != '(') bail("expected `(', found `%c'", ch);
 269   left = (struct my_node *)read_tree(&lht);
 270   for (;;) {
 271     do ch = getchar(); while (isspace(ch));
 272 #if TREE == RB
 273     if (ch == '*') f &= ~RBF_RED;
 274     else
 275 #endif
 276     break;
 277   }
 278   ungetc(ch, stdin); k = read_int();
 279   right = (struct my_node *)read_tree(&rht);
 280   do ch = getchar(); while (isspace(ch));
 281   if (ch != ')') bail("expected `)', found `%c'", ch);
 282
 283   node = make_node(k);
 284   node->_n._bst.left = left ? &left->_n._bst : 0;
 285   node->_n._bst.right = right ? &right->_n._bst : 0;
 286   node->n = (left ? left->n : 0) + (right ? right->n : 0) + 1;
 287 #if TREE == AVL
 288   switch (rht - lht) {
 289     case -1: f = AVLBAL_LBIAS; ht = lht + 1; break;
 290     case  0: f = AVLBAL_EVEN; ht = lht + 1; break;
 291     case +1: f = AVLBAL_RBIAS; ht = rht + 1; break;
 292     default: bail("tree is not AVL");
 293   }
 294   node->_n.f = f;
 295 #elif TREE == RB
 296   if (lht != rht) bail("tree is not red-black");
 297   ht = f&RBF_RED ? lht : lht + 1;
 298   node->_n.f = f;
 299 #else
 300   if (lht >= rht) ht = lht + 1;
 301   else ht = rht + 1;
 302 #endif
 303   *ht_out = ht;
 304   return (&node->_n._bst);
 305 }
 306
 307 static void free_tree(struct bstnode **root)
 308 {
 309   struct my_node *node;
 310   struct ITER it;
 311
 312   TREE_INITITER(*root, &it);
 313   for (;;) {
 314     node = TREE_NEXT(&it); if (!node) break;
 315     free(node);
 316   }
 317   *root = 0;
 318 }
 319
 320 int main(void)
 321 {
 322 #define NSTACK 16
 323
 324   struct bstree_nodecls ordcls;
 325   struct { struct bstnode *root; int ht; } cur, stack[NSTACK], u;
 326   struct my_node *node = 0, *t;
 327   struct bstnode **link;
 328   struct PATH path;
 329   struct ITER it;
 330   int ch, sp = 0;
 331   unsigned long i, j, k;
 332   unsigned f = 0;
 333 #define f_path 1u
 334 #define f_key 2u
 335 #define f_first 4u
 336 #define f_dumped 8u
 337
 338   cur.root = 0; cur.ht = 0; ordcls.ops = &my_ordops;
 339
 340   for (;;) {
 341     do ch = getchar(); while (isspace(ch));
 342     switch (ch) {
 343
 344       case EOF:
 345         goto done;
 346
 347       case ';': /* comment */
 348         do ch = getchar(); while (ch != EOF && ch != '\n');
 349         break;
 350
 351       case ':': /* print message */
 352         for (;;) {
 353           ch = getchar(); if (ch == '\n' || ch == EOF) break;
 354           putchar(ch);
 355         }
 356         putchar('\n');
 357         break;
 358
 359       case '.':
 360         stop = 1;
 361         break;
 362
 363 #ifdef TREE_INSERT
 364       case '+': /* insert */
 365         if (!(f&f_key)) bail("no key");
 366         if (!(f&f_path)) node = TREE_PROBE(&ordcls, &cur.root, &k, &path);
 367         if (node) bail("key %lu already present", k);
 368         cur.ht += TREE_INSERT(&ordcls, &path, &make_node(k)->_n);
 369         f &= ~(f_key | f_path | f_dumped);
 370         break;
 371 #endif
 372
 373 #ifdef TREE_REMOVE
 374       case '-': /* remove */
 375         if (f&f_path) {
 376           if (!node) bail("path empty");
 377         } else {
 378           if (!(f&f_key)) bail("no key or path");
 379           node = TREE_PROBE(&ordcls, &cur.root, &k, &path);
 380           if (!node) bail("key %lu not present", k);
 381         }
 382         cur.ht += TREE_REMOVE(&ordcls, &path);
 383         free(node); node = 0; f &= ~(f_key | f_path | f_dumped);
 384         break;
 385 #endif
 386
 387 #ifdef TREE_INSERT
 388       case '#': /* populate */
 389         i = read_int();
 390         do ch = getchar(); while (isspace(ch));
 391         if (ch == '-') j = read_int();
 392         else { ungetc(ch, stdin); j = i; i = 1; }
 393         for (;;) {
 394           if (!TREE_PROBE(&ordcls, &cur.root, &i, &path))
 395             cur.ht += TREE_INSERT(&ordcls, &path, &make_node(i)->_n);
 396           if (i == j) break;
 397           else if (i < j) i++;
 398           else i--;
 399         }
 400         node = 0; f &= ~(f_key | f_path | f_dumped);
 401         break;
 402 #endif
 403
 404       case '?': /* lookup */
 405         if (!(f&f_key)) bail("no key");
 406         node = TREE_LOOKUP(&ordcls, cur.root, &k); f &= ~(f_key | f_path);
 407         break;
 408
 409       case '@': /* probe */
 410         if (!(f&f_key)) bail("no key");
 411         node = TREE_PROBE(&ordcls, &cur.root, &k, &path);
 412         f |= f_key | f_path;
 413         break;
 414
 415       case '[': /* first */
 416         node = TREE_FIRSTPATH(&cur.root, &path);
 417         if (!node) f &= ~(f_key | f_path);
 418         else { k = node->k; f |= f_key | f_path; }
 419         break;
 420
 421       case ']': /* last */
 422         node = TREE_LASTPATH(&cur.root, &path);
 423         if (!node) f &= ~(f_key | f_path);
 424         else { k = node->k; f |= f_key | f_path; }
 425         break;
 426
 427       case '<': /* previous */
 428         if (!(f&f_path)) bail("no path");
 429         node = TREE_PREVPATH(&path);
 430         if (!node) f &= ~(f_key | f_path);
 431         else { k = node->k; f |= f_key | f_path; }
 432         break;
 433
 434       case '>': /* next */
 435         if (!(f&f_path)) bail("no path");
 436         node = TREE_NEXTPATH(&path);
 437         if (!node) f &= ~(f_key | f_path);
 438         else { k = node->k; f |= f_key | f_path; }
 439         break;
 440
 441       case '*': /* clear */
 442         node = 0; f &= ~(f_key | f_path);
 443         break;
 444
 445       case '(': /* push */
 446         if (sp >= NSTACK) bail("stack full");
 447         stack[sp++] = cur; cur.root = 0; cur.ht = 0;
 448         node = 0; f &= ~(f_key | f_path | f_dumped);
 449         break;
 450
 451       case '"': /* duplicate */
 452         if (sp >= NSTACK) bail("stack full");
 453         stack[sp++] = cur;
 454         cur.root = copy_tree((struct my_node *)cur.root);
 455         node = 0; f &= ~(f_key | f_path | f_dumped);
 456         break;
 457
 458       case ')': /* pop */
 459         if (!sp) bail("stack empty");
 460         free_tree(&cur.root); cur = stack[--sp];
 461         node = 0; f &= ~(f_key | f_path | f_dumped);
 462         break;
 463
 464       case '%': /* swap */
 465         if (!sp) bail("stack empty");
 466         u = stack[sp - 1]; stack[sp - 1] = cur; cur = u;
 467         node = 0; f &= ~(f_key | f_path | f_dumped);
 468         break;
 469
 470 #ifdef TREE_JOIN
 471       case '~': /* join */
 472         if (!sp) bail("stack empty");
 473         if (!(f&f_key)) t = 0;
 474         else t = make_node(k);
 475         cur.ht = TREE_JOIN(&ordcls, &cur.root,
 476                            &stack[sp - 1].root, stack[sp - 1].ht,
 477                            t ? &t->_n._bst : 0,
 478                            &cur.root, cur.ht);
 479         sp--; node = 0; f &= ~(f_key | f_path | f_dumped);
 480         break;
 481 #endif
 482
 483 #ifdef TREE_SPLIT
 484       case '/': /* split */
 485         if (sp > NSTACK - 2) bail("stack full");
 486         if (!(f&f_path)) bail("no path");
 487         node = TREE_SPLIT(&ordcls, &stack[sp].root, &stack[sp].ht,
 488                           &stack[sp + 1].ht,
 489                           &cur.root, &cur.ht,
 490                           &path);
 491         if (node) node->n = 1;
 492         stack[sp + 1].root = &node->_n._bst;
 493         sp += 2; f &= ~(f_key | f_path | f_dumped);
 494         break;
 495 #endif
 496
 497 #ifdef TREE_UNISECT
 498       case '|': /* union/intersection */
 499         if (!sp) bail("stack empty");
 500         TREE_UNISECT(&ordcls, &cur.root, &cur.ht,
 501                      &stack[sp - 1].root, &stack[sp - 1].ht,
 502                      &stack[sp - 1].root, stack[sp - 1].ht,
 503                      &cur.root, cur.ht);
 504         node = 0; f &= ~(f_key | f_path | f_dumped);
 505         break;
 506 #endif
 507
 508 #ifdef TREE_DIFFSECT
 509       case '\\': /* difference/intersection */
 510         if (!sp) bail("stack empty");
 511         if (sp >= NSTACK) bail("stack full");
 512         TREE_DIFFSECT(&ordcls,
 513                       &cur.root, &cur.ht,
 514                       &stack[sp].root, &stack[sp].ht,
 515                       &cur.root, cur.ht,
 516                       &stack[sp - 1].root);
 517         sp++; node = 0; f &= ~(f_key | f_path | f_dumped);
 518         break;
 519 #endif
 520
 521       case 'k': /* print key */
 522         if (f&f_key) printf("%lu\n", k);
 523         else fputs("(no key)\n", stdout);
 524         break;
 525
 526       case 'n': /* print node */
 527         if (!node) fputs("(nil)\n", stdout);
 528         else printf("#<node #0x%08lx %lu>\n", node->seq, node->k);
 529         break;
 530
 531       case 'p': /* print path */
 532         if (!(f&f_path))
 533           printf("(nil)\n");
 534         else {
 535           putchar('('); t = 0;
 536           for (i = 0, t = 0; i <= path.k; i++) {
 537             if (i) putchar(' ');
 538             link = path.p[i];
 539             if (!t && link == &cur.root)
 540               fputs("#<link root -> ", stdout);
 541             else if (t && link == &t->_n._bst.left)
 542               printf("#<link node #0x%08lx %lu left -> ", t->seq, t->k);
 543             else if (t && link == &t->_n._bst.right)
 544               printf("#<link node #0x%08lx %lu right -> ", t->seq, t->k);
 545             else
 546               printf("#<link address %p -> ", (void *)link);
 547             t = (struct my_node *)*link;
 548             if (!t) fputs("(nil)", stdout);
 549             else printf("node #0x%08lx %lu", t->seq, t->k);
 550             putchar('>');
 551           }
 552           putchar(')'); putchar('\n');
 553         }
 554         break;
 555
 556       case 'i': /* iterate */
 557         TREE_INITITER(cur.root, &it); f |= f_first;
 558         for (;;) {
 559           t = TREE_NEXT(&it); if (!t) break;
 560           if (f&f_first) f &= ~f_first;
 561           else putchar(' ');
 562           printf("%lu", t->k);
 563         }
 564         if (f&f_first) fputs("(empty tree)", stdout);
 565         putchar('\n');
 566         break;
 567
 568       case 'L': /* list */
 569         list_tree(cur.root);
 570         break;
 571
 572       case 'D': /* dump */
 573         dump_tree(cur.root, cur.ht); f |= f_dumped;
 574         break;
 575
 576       case '!': /* check */
 577         if (TREE_CHECK(&ordcls, &cur.root, cur.ht, 0)) {
 578           if (!(f&f_dumped)) {
 579             fputs("offending tree...\n", stdout);
 580             dump_tree(cur.root, cur.ht); fflush(stdout);
 581           }
 582           bail("check failed");
 583         }
 584         break;
 585
 586       case '=': /* assign */
 587         free_tree(&cur.root);
 588         cur.root = read_tree(&cur.ht);
 589         break;
 590
 591       default:
 592         if (isdigit(ch)) { /* set key */
 593           ungetc(ch, stdin);
 594           if (scanf("%lu", &k) != 1) bail("integer expected, scanf failed");
 595           f |= f_key;
 596         }
 597         else /* error */
 598           bail("unexpected character `%c'", ch);
 599         break;
 600     }
 601     fflush(stdout);
 602     if (ferror(stdout)) bail("stdout write failed: %s\n", strerror(errno));
 603   }
 604 done:
 605   if (sp) bail("stack not empty");
 606   free_tree(&cur.root);
 607   return (0);
 608
 609 #undef f_path
 610 #undef f_key
 611 #undef f_first
 612
 613 #undef NSTACK
 614 }