chiark - git - mdw - wordchain/blob - chain.c

   1 #include <assert.h>
   2 #include <stdarg.h>
   3 #include <stdio.h>
   4 #include <stdlib.h>
   5 #include <string.h>
   6
   7 #define XYLA_AVL 1
   8 #define XYLA_RB 2
   9 #define XYLA_SPLAY 3
  10 #define XYLA_TREAP 4
  11 #define QPTRIE_QP 5
  12 #define QPTRIE_FN 6
  13 #define SGT_TREE234 7
  14 #define LIBAVL_AVL 8
  15 #define LIBAVL_BST 9
  16 #define LIBAVL_RB 10
  17 #define LIBAVL_PAVL 11
  18 #define LIBAVL_PBST 12
  19 #define LIBAVL_PRB 13
  20 #define LIBAVL_RTAVL 14
  21 #define LIBAVL_RTBST 15
  22 #define LIBAVL_RTRB 16
  23 #define LIBAVL_TAVL 17
  24 #define LIBAVL_TBST 18
  25 #define LIBAVL_TRB 19
  26 #define MLIB_SYM 20
  27
  28 #define QPITER_FANF 1
  29 #define QPITER_MDW 2
  30 #define QPITER_LIST 3
  31
  32 #if !TREE
  33 #  error "`TREE' not defined or bungled constant setting"
  34 #elif TREE == XYLA_AVL
  35 #  include "avl.h"
  36 #  define USE_XYLA 1
  37 #  define WANT_HEIGHT 1
  38 #  define tree__name(name) xyla_avl_##name
  39 #elif TREE == XYLA_RB
  40 #  include "rb.h"
  41 #  define USE_XYLA 1
  42 #  define WANT_HEIGHT 1
  43 #  define tree__name(name) xyla_rb_##name
  44 #elif TREE == XYLA_SPLAY
  45 #  include "splay.h"
  46 #  define USE_XYLA 1
  47 #  define tree__name(name) xyla_splay_##name
  48 #elif TREE == XYLA_TREAP
  49 #  include "treap.h"
  50 #  define USE_XYLA 1
  51 #  define tree__name(name) xyla_treap_##name
  52 #elif TREE == QPTRIE_QP
  53 #  include <stdbool.h>
  54 #  include <stdint.h>
  55 #  include "Tbl.h"
  56 #  include "qp.h"
  57 #  define USE_QPTRIE 1
  58 #elif TREE == QPTRIE_FN
  59 #  include <stdbool.h>
  60 #  include <stdint.h>
  61 #  include "Tbl.h"
  62 #  include "fn.h"
  63 #  define USE_QPTRIE 1
  64 #elif TREE == SGT_TREE234
  65 #  include "tree234.h"
  66 #elif TREE == LIBAVL_AVL
  67 #  include "avl.h"
  68 #  define USE_LIBAVL 1
  69 #  define tree__name(name) avl_##name
  70 #elif TREE == LIBAVL_BST
  71 #  include "bst.h"
  72 #  define USE_LIBAVL 1
  73 #  define tree__name(name) bst_##name
  74 #elif TREE == LIBAVL_RB
  75 #  include "rb.h"
  76 #  define USE_LIBAVL 1
  77 #  define tree__name(name) rb_##name
  78 #elif TREE == LIBAVL_PAVL
  79 #  include "pavl.h"
  80 #  define USE_LIBAVL 1
  81 #  define tree__name(name) pavl_##name
  82 #elif TREE == LIBAVL_PBST
  83 #  include "pbst.h"
  84 #  define USE_LIBAVL 1
  85 #  define tree__name(name) pbst_##name
  86 #elif TREE == LIBAVL_PRB
  87 #  include "prb.h"
  88 #  define USE_LIBAVL 1
  89 #  define tree__name(name) prb_##name
  90 #elif TREE == LIBAVL_RTAVL
  91 #  include "rtavl.h"
  92 #  define USE_LIBAVL 1
  93 #  define tree__name(name) rtavl_##name
  94 #elif TREE == LIBAVL_RTBST
  95 #  include "rtbst.h"
  96 #  define USE_LIBAVL 1
  97 #  define tree__name(name) rtbst_##name
  98 #elif TREE == LIBAVL_RTRB
  99 #  include "rtrb.h"
 100 #  define USE_LIBAVL 1
 101 #  define tree__name(name) rtrb_##name
 102 #elif TREE == LIBAVL_TAVL
 103 #  include "tavl.h"
 104 #  define USE_LIBAVL 1
 105 #  define tree__name(name) tavl_##name
 106 #elif TREE == LIBAVL_BST
 107 #  include "tbst.h"
 108 #  define USE_LIBAVL 1
 109 #  define tree__name(name) tbst_##name
 110 #elif TREE == LIBAVL_TRB
 111 #  include "trb.h"
 112 #  define USE_LIBAVL 1
 113 #  define tree__name(name) trb_##name
 114 #elif TREE == MLIB_SYM
 115 #  include <unistd.h>
 116 #  include <mLib/sym.h>
 117 #  include <mLib/unihash.h>
 118 #else
 119 #  error "unknown `TREE' value"
 120 #endif
 121
 122 #if USE_XYLA
 123 #  define NODE tree__name(node)
 124 #  define PATH tree__name(path)
 125 #  define ITER tree__name(iter)
 126 #  define TREE_CHECK tree__name(check)
 127 #  define TREE_LOOKUP tree__name(lookup)
 128 #  define TREE_PROBE tree__name(probe)
 129 #  define TREE_INITITER tree__name(inititer)
 130 #  define TREE_NEXT tree__name(next)
 131 #  define TREE_INSERT tree__name(insert)
 132 #  if WANT_HEIGHT
 133 #    define H(x) x
 134 #    define HARG(x) , x
 135 #  else
 136 #    define H(x)
 137 #    define HARG(x)
 138 #  endif
 139 #elif USE_LIBAVL
 140 #  define TABLE tree__name(table)
 141 #  define TRAVERSER tree__name(traverser)
 142 #  define TREE_CREATE tree__name(create)
 143 #  define TREE_DESTROY tree__name(destroy)
 144 #  define TREE_PROBE tree__name(probe)
 145 #  define TREE_FIND tree__name(find)
 146 #  define TREE_T_INIT tree__name(t_init)
 147 #  define TREE_T_NEXT tree__name(t_next)
 148 #endif
 149
 150 #if USE_QPTRIE
 151 #  if !QPTRIE_ITER
 152 #    error "`QPTRIE_ITER' not defined or bungled constant setting"
 153 #  elif QPTRIE_ITER == QPITER_FANF
 154 #  elif QPTRIE_ITER == QPITER_MDW
 155 #  elif QPTRIE_ITER == QPITER_LIST
 156 #  else
 157 #    error "unknown `QPTRIE_ITER' value"
 158 #  endif
 159 #endif
 160
 161 struct word { const char *p; size_t n; } word;
 162
 163 struct node {
 164 #if USE_XYLA
 165   struct NODE _n;
 166 #elif TREE == MLIB_SYM
 167   struct sym_base _s;
 168 #endif
 169 #if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
 170   struct node *next;
 171 #endif
 172 #if TREE != MLIB_SYM
 173   struct word w;
 174 #endif
 175   struct node *down, *right, *up;
 176   int len;
 177 };
 178
 179 #define WORDMAX 64
 180
 181 static void bail(const char *msg, ...)
 182 {
 183   va_list ap;
 184   long pos;
 185
 186   va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
 187   pos = ftell(stdin);
 188   if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
 189   fputc('\n', stderr);
 190   exit(2);
 191 }
 192
 193 #if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL
 194
 195 static int compare_words(const struct word *a, const struct word *b)
 196 {
 197   size_t alen = a->n, blen = b->n;
 198   int ord;
 199
 200   ord = memcmp(a->p, b->p, alen <= blen ? alen : blen);
 201   if (!ord) ord = alen < blen ? -1 : alen > blen ? +1 : 0;
 202   return (ord);
 203 }
 204
 205 #endif
 206
 207 #if USE_XYLA
 208
 209 static int word_nav(struct xyla_bst_nodecls *cls,
 210                     const struct xyla_bst_node *nn, void *arg)
 211 {
 212   const struct word *k = arg;
 213   const struct node *node = (struct node *)nn;
 214
 215   return (compare_words(k, &node->w));
 216 }
 217
 218 #  define DECLS                                                         \
 219         struct xyla_bst_node *root = 0;                                 \
 220         struct PATH path;                                               \
 221         struct ITER it
 222
 223 #  define INIT do ; while (0)
 224
 225 #  if TREE == XYLA_TREAP
 226 #    define EXTRA_NODE_SETUP do { node->_n.wt = rand(); } while (0)
 227 #  endif
 228 #  ifndef EXTRA_NODE_SETUP
 229 #    define EXTRA_NODE_SETUP do ; while (0)
 230 #  endif
 231 #  define INSERT do {                                                   \
 232         if (TREE_PROBE(0, &root, word_nav, &word, &path)) {             \
 233           printf(";; duplicate `%s'\n", buf);                           \
 234           free(node); node = 0;                                         \
 235         } else {                                                        \
 236           EXTRA_NODE_SETUP;                                             \
 237           TREE_INSERT(0, &path, &node->_n);                             \
 238         }                                                               \
 239    } while (0)
 240
 241 #  define ITERATE                                                       \
 242         for (TREE_INITITER(&root, &it); node = TREE_NEXT(&it), node; )
 243
 244 #  if TREE == XYLA_SPLAY
 245 #    define FOCUS do { xyla_splay_splay(0, &path); } while (0)
 246 #  else
 247 #    define FOCUS do ; while (0)
 248 #  endif
 249
 250 #  define LOOKUP TREE_LOOKUP(0, &root, word_nav, &word)
 251
 252 #  define FREE do {                                                     \
 253         while (node = xyla_bst_severfirst(&root), node) free(node);     \
 254    } while (0)
 255
 256 #  ifndef WANT_CHECKS
 257 #    define CHECK do ; while (0)
 258 #  else
 259
 260 static const void *word_key(struct xyla_bst_nodecls *cls,
 261                             const struct xyla_bst_node *nn)
 262   { struct node *node = (struct node *)nn; return (&node->w); }
 263
 264 static void word_ident(struct xyla_bst_nodecls *cls,
 265                        const struct xyla_bst_node *nn, FILE *fp)
 266   { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
 267
 268 static const struct xyla_bst_ordnodeops word_ops = {
 269   { 0, xyla_bst_chkorder, sizeof(struct xyla_bst_ordinfo), word_ident },
 270   { word_nav, word_key }
 271 };
 272 struct xyla_bst_nodecls word_cls = { &word_ops.node };
 273
 274 #    define CHECK do {                                                  \
 275         if (TREE_CHECK(&word_cls, &root HARG(-1), 0))                   \
 276           bail("check failed");                                         \
 277       } while (0)
 278 #  endif
 279
 280 #elif USE_QPTRIE
 281
 282 #  if QPTRIE_ITER == QPITER_FANF
 283 #    define my_Tnextl Tnextl
 284 #    define DECL_ITER                                                   \
 285         struct word cur;                                                \
 286         void *v
 287 #    define INSERT_LIST do ; while (0)
 288 #  elif QPTRIE_ITER == QPITER_MDW
 289 #    define DECL_ITER                                                   \
 290         struct word cur;                                                \
 291         void *v
 292 #    define INSERT_LIST do ; while (0)
 293
 294 #    if TREE == QPTRIE_QP
 295
 296 static bool my_Tnextl(Tbl *tbl, const char **k_inout, size_t *sz_inout,
 297                       void **val_out)
 298 {
 299   const char *k = *k_inout;
 300   size_t sz = *sz_inout;
 301   Trie *t, *resume;
 302   unsigned off, max;
 303   Tbitmap b;
 304
 305   if (!tbl)
 306     return (false);
 307   else {
 308     t = &tbl->root;
 309     if (k) {
 310       resume = 0;
 311       while (isbranch(t)) {
 312         __builtin_prefetch(t->branch.twigs);
 313         b = twigbit(t, k, sz);
 314         TWIGOFFMAX(off, max, t, b);
 315         if (!hastwig(t, b)) return (false);
 316         t = twig(t, off);
 317         if (off + 1 < max) resume = t + 1;
 318       }
 319       /* if (strcmp(k, t->leaf.key) != 0) return (false); */
 320       t = resume; if (!t) return (false);
 321     }
 322   }
 323   while (isbranch(t)) t = twig(t, 0);
 324   *k_inout = k = t->leaf.key; *sz_inout = strlen(k); *val_out = t->leaf.val;
 325   return (true);
 326 }
 327
 328 #    elif TREE == QPTRIE_FN
 329
 330 static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 331                       void **val_out)
 332 {
 333   const char *k = *k_inout;
 334   size_t sz = *sz_inout;
 335   Trie *resume;
 336   unsigned off, max;
 337   Tbitmap b;
 338   Tindex i;
 339
 340   if (!t)
 341     return (false);
 342   else if (k) {
 343     resume = 0;
 344     while (isbranch(t)) {
 345       __builtin_prefetch(t->ptr);
 346       i = t->index; b = twigbit(i, k, sz);
 347       TWIGOFFMAX(off, max, i, b);
 348       if (!hastwig(i, b)) return (false);
 349       t = Tbranch_twigs(t) + off;
 350       if (off + 1 < max) resume = t + 1;
 351     }
 352     /* if (strcmp(k, Tleaf_key(t)) != 0) return (false); */
 353     t = resume; if (!t) return (false);
 354   }
 355   while (isbranch(t)) t = Tbranch_twigs(t);
 356   *k_inout = k = Tleaf_key(t); *sz_inout = strlen(k);
 357   *val_out = Tleaf_val(t);
 358   return (true);
 359 }
 360
 361 #    else
 362 #      error "no mdw `Tnextl' for this QP trie variant"
 363 #    endif
 364 #  elif QPTRIE_ITER == QPITER_LIST
 365 #    define DECL_ITER                                                   \
 366         struct node *list = 0, **tail = &list, *next
 367 #    define INSERT_LIST                                                 \
 368         do { node->next = 0; *tail = node; tail = &node->next; } while (0)
 369 #  endif
 370
 371 #  define DECLS                                                         \
 372         Tbl *tbl = 0;                                                   \
 373         DECL_ITER
 374
 375 #  define INIT do ; while (0)
 376
 377 #  define INSERT do {                                                   \
 378         tbl = Tsetl(tbl, node->w.p, node->w.n, node);                   \
 379         INSERT_LIST;                                                    \
 380    } while (0)
 381
 382 #  if QPTRIE_ITER == QPITER_LIST
 383 #    define ITERATE                                                     \
 384         for (next = list; node = next, node; next = next->next)
 385 #  else
 386 #    define ITERATE                                                     \
 387         for (cur.p = 0, cur.n = 0;                                      \
 388                my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; )
 389 #endif
 390
 391 #  define FOCUS do ; while (0)
 392
 393 #  define GETPREFIX do {                                                \
 394         word.n = node->w.n - 1; assert(word.n < WORDMAX);               \
 395         memcpy(buf, node->w.p, word.n); buf[word.n] = 0;                \
 396    } while (0)
 397
 398 #  define LOOKUP Tgetl(tbl, buf, word.n)
 399
 400 #  if QPTRIE_ITER == QPITER_LIST
 401 #    define FREE do {                                                   \
 402         for (node = list; node; node = next) {                          \
 403           tbl = Tsetl(tbl, node->w.p, node->w.n, 0);                    \
 404           next = node->next; free(node);                                \
 405         }                                                               \
 406         assert(!tbl);                                                   \
 407      } while (0)
 408 #  else
 409 #    define FREE do {                                                   \
 410         while (tbl) {                                                   \
 411           cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v);     \
 412           tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v);                   \
 413         }                                                               \
 414      } while (0)
 415 #  endif
 416
 417 #  define CHECK do ; while (0)
 418
 419 #elif TREE == SGT_TREE234
 420
 421 static int node_cmp(void *a, void *b)
 422   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 423
 424 #  define DECLS                                                         \
 425         tree234 *root;                                                  \
 426         int i
 427
 428 #  define INIT do { root = newtree234(node_cmp); } while (0)
 429
 430 #  define INSERT do {                                                   \
 431         if (add234(root, node) != node) {                               \
 432           printf(";; duplicate `%s'\n", buf);                           \
 433           free(node); node = 0;                                         \
 434         }                                                               \
 435    } while (0)
 436
 437 #  define ITERATE for (i = 0; node = index234(root, i), node; i++)
 438
 439 #  define FOCUS do ; while (0)
 440
 441 #  define LOOKUP find234(root, &word, 0)
 442
 443 #  define FREE do {                                                     \
 444         while (node = delpos234(root, 0), node) free(node);             \
 445         freetree234(root);                                              \
 446    } while (0)
 447
 448 #  define CHECK do ; while (0)
 449
 450 #elif USE_LIBAVL
 451
 452 static int node_cmp(const void *a, const void *b, void *arg)
 453   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 454
 455 static void free_node(void *n, void *arg) { free(n); }
 456
 457 #  define DECLS                                                         \
 458         struct TABLE *tab;                                              \
 459         struct TRAVERSER it;                                            \
 460         void **p
 461
 462 #  define INIT do {                                                     \
 463         tab = TREE_CREATE(node_cmp, 0, 0);                              \
 464         if (!tab) bail("out of memory");                                \
 465    } while (0)
 466
 467 #  define INSERT do {                                                   \
 468         p = TREE_PROBE(tab, node); if (!p) bail("out of memory");       \
 469         if (*p != node) {                                               \
 470           printf(";; duplicate `%s'\n", buf);                           \
 471           free(node); node = 0;                                         \
 472         }                                                               \
 473    } while (0)
 474
 475 #  define ITERATE                                                       \
 476         for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; )
 477
 478 #  define FOCUS do ; while (0)
 479
 480 #  define LOOKUP TREE_FIND(tab, &word)
 481
 482 #  define FREE do { TREE_DESTROY(tab, free_node); } while (0)
 483
 484 #  define CHECK do ; while (0)
 485
 486 #elif TREE == MLIB_SYM
 487
 488 #  define DECLS                                                         \
 489         sym_table tab;                                                  \
 490         struct node *list = 0, **tail = &list, *next;                   \
 491         unsigned foundp
 492
 493 #  define INIT do {                                                     \
 494         unihash_setkey(&unihash_global, /*getpid()*/ 31022);            \
 495         sym_create(&tab);                                               \
 496    } while (0)
 497
 498 #  define PREPNODE do ; while (0)
 499
 500 #  define INSERT do {                                                   \
 501         node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp);     \
 502         if (foundp) { bail(";; duplicate `%s'\n", buf); node = 0; }     \
 503         else { node->next = 0; *tail = node; tail = &node->next; }      \
 504    } while (0)
 505
 506 #  define ITERATE for (next = list; node = next, node; next = next->next)
 507
 508 #  define FOCUS do ; while (0)
 509
 510 #  define WORDPTR(node) (SYM_NAME(node))
 511 #  define WORDLEN(node) (SYM_LEN(node))
 512
 513 #  define LOOKUP sym_find(&tab, word.p, word.n, 0, 0)
 514
 515 #  define FREE do { sym_destroy(&tab); } while (0)
 516
 517 #  define CHECK do ; while (0)
 518
 519 #endif
 520
 521 #ifndef PREPNODE
 522 #  define PREPNODE do {                                                 \
 523         node = malloc(sizeof(*node) + word.n + 1);                      \
 524           if (!node) bail("out of memory");                             \
 525         node->w.p = (char *)(node + 1);                                 \
 526         memcpy(node + 1, buf, word.n + 1); node->w.n = word.n;          \
 527    } while (0)
 528 #endif
 529
 530 #ifndef WORDPTR
 531 #  define WORDPTR(node) ((node)->w.p)
 532 #endif
 533
 534 #ifndef WORDLEN
 535 #  define WORDLEN(node) ((node)->w.n)
 536 #endif
 537
 538 #ifndef GETPREFIX
 539 #  define GETPREFIX do {                                                \
 540         word.p = WORDPTR(node); word.n = WORDLEN(node) - 1;             \
 541    } while (0)
 542
 543 #endif
 544
 545 static void print_chain(struct node *node)
 546 {
 547   if (!node->right) {
 548     fputs(WORDPTR(node), stdout);
 549     if (node->down) { putchar(' '); print_chain(node->down); }
 550   } else {
 551     fputs("{ ", stdout);
 552     for (;;) {
 553       fputs(WORDPTR(node), stdout);
 554       if (node->down) { putchar(' '); print_chain(node->down); }
 555       node = node->right; if (!node) break;
 556       fputs(" | ", stdout);
 557     }
 558     fputs(" }", stdout);
 559   }
 560 }
 561
 562 int main(void)
 563 {
 564   DECLS;
 565   struct node *node, *parent;
 566   struct word word;
 567   char buf[WORDMAX];
 568   int ch, max, nlen, plen;
 569
 570   INIT;
 571   word.p = buf;
 572   for (;;) {
 573     if (!fgets(buf, WORDMAX, stdin)) break;
 574     word.n = strlen(buf); assert(word.n);
 575     if (buf[word.n - 1] == '\n') buf[--word.n] = 0;
 576     else if (word.n == WORDMAX - 1) bail("word too long");
 577     else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch);
 578
 579     PREPNODE; INSERT;
 580     if (node) { node->up = node->down = node->right = 0; node->len = 1; }
 581   }
 582
 583   CHECK;
 584
 585   max = 0;
 586
 587   ITERATE {
 588     FOCUS;
 589     /* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */
 590     if (WORDLEN(node) <= 1)
 591       parent = 0;
 592     else {
 593       GETPREFIX;
 594       /* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */
 595       parent = LOOKUP;
 596     }
 597     node->up = parent; nlen = node->len;
 598     while (parent) {
 599       plen = parent->len; nlen++;
 600       if (plen > nlen)
 601         break;
 602       else if (plen == nlen) {
 603         node->right = parent->down; parent->down = node;
 604         break;
 605       } else {
 606         parent->down = node; node->right = 0;
 607         parent->len = nlen;
 608         node = parent; parent = node->up;
 609       }
 610     }
 611     if (nlen > max) max = nlen;
 612   }
 613
 614   ITERATE if (node->len == max) { print_chain(node); putchar('\n'); }
 615   FREE;
 616   return (0);
 617 }