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