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           fprintf(stderr, ";; 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 *all = 0, **all_tail = &all
 367 #    define INSERT_LIST do {                                            \
 368         node->next = 0; *all_tail = node; all_tail = &node->next;       \
 369      } while (0)
 370 #  endif
 371
 372 #  define DECLS                                                         \
 373         Tbl *tbl = 0;                                                   \
 374         DECL_ITER
 375
 376 #  define INIT do ; while (0)
 377
 378 #  define INSERT do {                                                   \
 379         tbl = Tsetl(tbl, node->w.p, node->w.n, node);                   \
 380         INSERT_LIST;                                                    \
 381    } while (0)
 382
 383 #  if QPTRIE_ITER == QPITER_LIST
 384 #    define ITERATE                                                     \
 385         for (next = all; node = next, node; next = next->next)
 386 #  else
 387 #    define ITERATE                                                     \
 388         for (cur.p = 0, cur.n = 0;                                      \
 389                my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; )
 390 #endif
 391
 392 #  define FOCUS do ; while (0)
 393
 394 #  define GETPREFIX do {                                                \
 395         word.n = node->w.n - 1; assert(word.n < WORDMAX);               \
 396         memcpy(buf, node->w.p, word.n); buf[word.n] = 0;                \
 397    } while (0)
 398
 399 #  define LOOKUP Tgetl(tbl, buf, word.n)
 400
 401 #  if QPTRIE_ITER == QPITER_LIST
 402 #    define FREE do {                                                   \
 403         for (node = all; node; node = next) {                           \
 404           tbl = Tsetl(tbl, node->w.p, node->w.n, 0);                    \
 405           next = node->next; free(node);                                \
 406         }                                                               \
 407         assert(!tbl);                                                   \
 408      } while (0)
 409 #  else
 410 #    define FREE do {                                                   \
 411         while (tbl) {                                                   \
 412           cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v);     \
 413           tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v);                   \
 414         }                                                               \
 415      } while (0)
 416 #  endif
 417
 418 #  define CHECK do ; while (0)
 419
 420 #elif TREE == SGT_TREE234
 421
 422 static int node_cmp(void *a, void *b)
 423   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 424
 425 #  define DECLS                                                         \
 426         tree234 *root;                                                  \
 427         int i
 428
 429 #  define INIT do { root = newtree234(node_cmp); } while (0)
 430
 431 #  define INSERT do {                                                   \
 432         if (add234(root, node) != node) {                               \
 433           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 434           free(node); node = 0;                                         \
 435         }                                                               \
 436    } while (0)
 437
 438 #  define ITERATE for (i = 0; node = index234(root, i), node; i++)
 439
 440 #  define FOCUS do ; while (0)
 441
 442 #  define LOOKUP find234(root, &word, 0)
 443
 444 #  define FREE do {                                                     \
 445         while (node = delpos234(root, 0), node) free(node);             \
 446         freetree234(root);                                              \
 447    } while (0)
 448
 449 #  define CHECK do ; while (0)
 450
 451 #elif USE_LIBAVL
 452
 453 static int node_cmp(const void *a, const void *b, void *arg)
 454   { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
 455
 456 static void free_node(void *n, void *arg) { free(n); }
 457
 458 #  define DECLS                                                         \
 459         struct TABLE *tab;                                              \
 460         struct TRAVERSER it;                                            \
 461         void **p
 462
 463 #  define INIT do {                                                     \
 464         tab = TREE_CREATE(node_cmp, 0, 0);                              \
 465         if (!tab) bail("out of memory");                                \
 466    } while (0)
 467
 468 #  define INSERT do {                                                   \
 469         p = TREE_PROBE(tab, node); if (!p) bail("out of memory");       \
 470         if (*p != node) {                                               \
 471           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 472           free(node); node = 0;                                         \
 473         }                                                               \
 474    } while (0)
 475
 476 #  define ITERATE                                                       \
 477         for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; )
 478
 479 #  define FOCUS do ; while (0)
 480
 481 #  define LOOKUP TREE_FIND(tab, &word)
 482
 483 #  define FREE do { TREE_DESTROY(tab, free_node); } while (0)
 484
 485 #  define CHECK do ; while (0)
 486
 487 #elif TREE == MLIB_SYM
 488
 489 #  define DECLS                                                         \
 490         sym_table tab;                                                  \
 491         struct node *all = 0, **all_tail = &all;                        \
 492         unsigned foundp
 493
 494 #  define INIT do {                                                     \
 495         unihash_setkey(&unihash_global, getpid());                      \
 496         sym_create(&tab);                                               \
 497    } while (0)
 498
 499 #  define PREPNODE do ; while (0)
 500
 501 #  define INSERT do {                                                   \
 502         node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp);     \
 503         if (!foundp) {                                                  \
 504           node->next = 0; *all_tail = node; all_tail = &node->next;     \
 505         } else {                                                        \
 506           fprintf(stderr, ";; duplicate `%s'\n", buf);                  \
 507           free(node); node = 0;                                         \
 508         }                                                               \
 509    } while (0)
 510
 511 #  define ITERATE for (next = all; node = next, node; next = next->next)
 512
 513 #  define FOCUS do ; while (0)
 514
 515 #  define WORDPTR(node) (SYM_NAME(node))
 516 #  define WORDLEN(node) (SYM_LEN(node))
 517
 518 #  define LOOKUP sym_find(&tab, word.p, word.n, 0, 0)
 519
 520 #  define FREE do { sym_destroy(&tab); } while (0)
 521
 522 #  define CHECK do ; while (0)
 523
 524 #endif
 525
 526 #ifndef PREPNODE
 527 #  define PREPNODE do {                                                 \
 528         node = malloc(sizeof(*node) + word.n + 1);                      \
 529           if (!node) bail("out of memory");                             \
 530         node->w.p = (char *)(node + 1);                                 \
 531         memcpy(node + 1, buf, word.n + 1); node->w.n = word.n;          \
 532    } while (0)
 533 #endif
 534
 535 #ifndef WORDPTR
 536 #  define WORDPTR(node) ((node)->w.p)
 537 #endif
 538
 539 #ifndef WORDLEN
 540 #  define WORDLEN(node) ((node)->w.n)
 541 #endif
 542
 543 #ifndef GETPREFIX
 544 #  define GETPREFIX do {                                                \
 545         word.p = WORDPTR(node); word.n = WORDLEN(node) - 1;             \
 546    } while (0)
 547
 548 #endif
 549
 550 static void print_chain(struct node *node)
 551 {
 552   if (!node->right) {
 553     fputs(WORDPTR(node), stdout);
 554     if (node->down) { putchar(' '); print_chain(node->down); }
 555   } else {
 556     fputs("{ ", stdout);
 557     for (;;) {
 558       fputs(WORDPTR(node), stdout);
 559       if (node->down) { putchar(' '); print_chain(node->down); }
 560       node = node->right; if (!node) break;
 561       fputs(" | ", stdout);
 562     }
 563     fputs(" }", stdout);
 564   }
 565 }
 566
 567 int main(void)
 568 {
 569   DECLS;
 570   struct node *node, *parent, *winners, **winners_tail, *next;
 571   struct word word;
 572   char buf[WORDMAX];
 573   int ch, max, nlen, plen;
 574
 575   INIT;
 576   word.p = buf;
 577   for (;;) {
 578     if (!fgets(buf, WORDMAX, stdin)) break;
 579     word.n = strlen(buf); assert(word.n);
 580     if (buf[word.n - 1] == '\n') buf[--word.n] = 0;
 581     else if (word.n == WORDMAX - 1) bail("word too long");
 582     else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch);
 583
 584     PREPNODE; INSERT;
 585     if (node) { node->up = node->down = node->right = 0; node->len = 1; }
 586   }
 587
 588   CHECK;
 589
 590   max = 0; winners_tail = &winners;
 591
 592   ITERATE {
 593     FOCUS;
 594     /* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */
 595     if (WORDLEN(node) <= 1)
 596       continue;
 597     else {
 598       GETPREFIX;
 599       /* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */
 600       parent = LOOKUP; if (!parent) continue;
 601     }
 602     node->up = parent; nlen = node->len;
 603     for (;;) {
 604       if (!parent) {
 605         if (nlen >= max) {
 606           if (nlen > max)
 607             { max = nlen; *winners_tail = 0; winners_tail = &winners; }
 608           *winners_tail = node; winners_tail = &node->right;
 609         }
 610         break;
 611       }
 612       plen = parent->len; nlen++;
 613       if (plen > nlen)
 614         break;
 615       else if (plen == nlen) {
 616         node->right = parent->down; parent->down = node;
 617         break;
 618       } else {
 619         parent->down = node; node->right = 0;
 620         parent->len = nlen;
 621         node = parent; parent = node->up;
 622       }
 623     }
 624   }
 625
 626   for (*winners_tail = 0, node = winners; node; node = next) {
 627     next = node->right; node->right = 0;
 628     print_chain(node); putchar('\n');
 629   }
 630   FREE;
 631   return (0);
 632 }