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