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

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