+#include <assert.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#define XYLA_AVL 1
+#define XYLA_RB 2
+#define XYLA_SPLAY 3
+#define XYLA_TREAP 4
+#define QPTRIE_QP 5
+#define QPTRIE_FN 6
+#define SGT_TREE234 7
+#define LIBAVL_AVL 8
+#define LIBAVL_BST 9
+#define LIBAVL_RB 10
+#define LIBAVL_PAVL 11
+#define LIBAVL_PBST 12
+#define LIBAVL_PRB 13
+#define LIBAVL_RTAVL 14
+#define LIBAVL_RTBST 15
+#define LIBAVL_RTRB 16
+#define LIBAVL_TAVL 17
+#define LIBAVL_TBST 18
+#define LIBAVL_TRB 19
+#define MLIB_SYM 20
+
+#if !TREE
+# error "`TREE' not defined or bungled constant setting"
+#elif TREE == XYLA_AVL
+# include "avl.h"
+# define USE_XYLA 1
+# define WANT_HEIGHT 1
+# define tree__name(name) xyla_avl_##name
+#elif TREE == XYLA_RB
+# include "rb.h"
+# define USE_XYLA 1
+# define WANT_HEIGHT 1
+# define tree__name(name) xyla_rb_##name
+#elif TREE == XYLA_SPLAY
+# include "splay.h"
+# define USE_XYLA 1
+# define tree__name(name) xyla_splay_##name
+#elif TREE == XYLA_TREAP
+# include "treap.h"
+# define USE_XYLA 1
+# define tree__name(name) xyla_treap_##name
+#elif TREE == QPTRIE_QP
+# include <stdbool.h>
+# include <stdint.h>
+# include "Tbl.h"
+# include "qp.h"
+# define USE_QPTRIE 1
+#elif TREE == QPTRIE_FN
+# include <stdbool.h>
+# include <stdint.h>
+# include "Tbl.h"
+# include "fn.h"
+# define USE_QPTRIE 1
+#elif TREE == SGT_TREE234
+# include "tree234.h"
+#elif TREE == LIBAVL_AVL
+# include "avl.h"
+# define USE_LIBAVL 1
+# define tree__name(name) avl_##name
+#elif TREE == LIBAVL_BST
+# include "bst.h"
+# define USE_LIBAVL 1
+# define tree__name(name) bst_##name
+#elif TREE == LIBAVL_RB
+# include "rb.h"
+# define USE_LIBAVL 1
+# define tree__name(name) rb_##name
+#elif TREE == LIBAVL_PAVL
+# include "pavl.h"
+# define USE_LIBAVL 1
+# define tree__name(name) pavl_##name
+#elif TREE == LIBAVL_PBST
+# include "pbst.h"
+# define USE_LIBAVL 1
+# define tree__name(name) pbst_##name
+#elif TREE == LIBAVL_PRB
+# include "prb.h"
+# define USE_LIBAVL 1
+# define tree__name(name) prb_##name
+#elif TREE == LIBAVL_RTAVL
+# include "rtavl.h"
+# define USE_LIBAVL 1
+# define tree__name(name) rtavl_##name
+#elif TREE == LIBAVL_RTBST
+# include "rtbst.h"
+# define USE_LIBAVL 1
+# define tree__name(name) rtbst_##name
+#elif TREE == LIBAVL_RTRB
+# include "rtrb.h"
+# define USE_LIBAVL 1
+# define tree__name(name) rtrb_##name
+#elif TREE == LIBAVL_TAVL
+# include "tavl.h"
+# define USE_LIBAVL 1
+# define tree__name(name) tavl_##name
+#elif TREE == LIBAVL_BST
+# include "tbst.h"
+# define USE_LIBAVL 1
+# define tree__name(name) tbst_##name
+#elif TREE == LIBAVL_TRB
+# include "trb.h"
+# define USE_LIBAVL 1
+# define tree__name(name) trb_##name
+#elif TREE == MLIB_SYM
+# include <mLib/sym.h>
+#else
+# error "unknown `TREE' value"
+#endif
+
+#if USE_XYLA
+# define NODE tree__name(node)
+# define PATH tree__name(path)
+# define ITER tree__name(iter)
+# define TREE_CHECK tree__name(check)
+# define TREE_LOOKUP tree__name(lookup)
+# define TREE_PROBE tree__name(probe)
+# define TREE_INITITER tree__name(inititer)
+# define TREE_NEXT tree__name(next)
+# define TREE_INSERT tree__name(insert)
+# if WANT_HEIGHT
+# define H(x) x
+# define HARG(x) , x
+# else
+# define H(x)
+# define HARG(x)
+# endif
+#elif USE_LIBAVL
+# define TABLE tree__name(table)
+# define TRAVERSER tree__name(traverser)
+# define TREE_CREATE tree__name(create)
+# define TREE_DESTROY tree__name(destroy)
+# define TREE_PROBE tree__name(probe)
+# define TREE_FIND tree__name(find)
+# define TREE_T_INIT tree__name(t_init)
+# define TREE_T_NEXT tree__name(t_next)
+#endif
+
+struct word { const char *p; size_t n; } word;
+
+struct node {
+#if USE_XYLA
+ struct NODE _n;
+#elif TREE == MLIB_SYM
+ struct sym_base _s;
+#endif
+#if TREE != MLIB_SYM
+ struct word w;
+#endif
+ struct node *down, *right, *up;
+ int len;
+};
+
+#define WORDMAX 64
+
+static void bail(const char *msg, ...)
+{
+ va_list ap;
+ long pos;
+
+ va_start(ap, msg); vfprintf(stderr, msg, ap); va_end(ap);
+ pos = ftell(stdin);
+ if (pos >= 0) fprintf(stderr, " (input pos = %ld)", pos);
+ fputc('\n', stderr);
+ exit(2);
+}
+
+#if USE_XYLA || TREE == SGT_TREE234 || USE_LIBAVL
+
+static int compare_words(const struct word *a, const struct word *b)
+{
+ size_t alen = a->n, blen = b->n;
+ int ord;
+
+ ord = memcmp(a->p, b->p, alen <= blen ? alen : blen);
+ if (!ord) ord = alen < blen ? -1 : alen > blen ? +1 : 0;
+ return (ord);
+}
+
+#endif
+
+#if USE_XYLA
+
+static int word_nav(struct xyla_bst_nodecls *cls,
+ const struct xyla_bst_node *nn, void *arg)
+{
+ const struct word *k = arg;
+ const struct node *node = (struct node *)nn;
+
+ return (compare_words(k, &node->w));
+}
+
+# define DECLS \
+ struct xyla_bst_node *root = 0; \
+ struct PATH path; \
+ struct ITER it
+
+# define INIT do ; while (0)
+
+# if TREE == XYLA_TREAP
+# define EXTRA_NODE_SETUP do { node->_n.wt = rand(); } while (0)
+# endif
+# ifndef EXTRA_NODE_SETUP
+# define EXTRA_NODE_SETUP do ; while (0)
+# endif
+# define INSERT do { \
+ if (TREE_PROBE(0, &root, word_nav, &word, &path)) { \
+ printf(";; duplicate `%s'\n", buf); \
+ free(node); node = 0; \
+ } else { \
+ EXTRA_NODE_SETUP; \
+ TREE_INSERT(0, &path, &node->_n); \
+ } \
+ } while (0)
+
+# define ITERATE \
+ for (TREE_INITITER(&root, &it); node = TREE_NEXT(&it), node; )
+
+# if TREE == XYLA_SPLAY
+# define FOCUS do { xyla_splay_splay(0, &path); } while (0)
+# else
+# define FOCUS do ; while (0)
+# endif
+
+# define LOOKUP TREE_LOOKUP(0, &root, word_nav, &word)
+
+# define FREE do { \
+ while (node = xyla_bst_severfirst(&root), node) free(node); \
+ } while (0)
+
+# ifndef WANT_CHECKS
+# define CHECK do ; while (0)
+# else
+
+static const void *word_key(struct xyla_bst_nodecls *cls,
+ const struct xyla_bst_node *nn)
+ { struct node *node = (struct node *)nn; return (&node->w); }
+
+static void word_ident(struct xyla_bst_nodecls *cls,
+ const struct xyla_bst_node *nn, FILE *fp)
+ { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
+
+static const struct xyla_bst_ordnodeops word_ops = {
+ { 0, xyla_bst_chkorder, sizeof(struct xyla_bst_ordinfo), word_ident },
+ { word_nav, word_key }
+};
+struct xyla_bst_nodecls word_cls = { &word_ops.node };
+
+# define CHECK do { \
+ if (TREE_CHECK(&word_cls, &root HARG(-1), 0)) \
+ bail("check failed"); \
+ } while (0)
+# endif
+
+#elif USE_QPTRIE
+# ifdef USE_RECURSIVE_TNEXTL
+# define my_Tnextl Tnextl
+# elif TREE == QPTRIE_QP
+
+static bool my_Tnextl(Tbl *tbl, const char **k_inout, size_t *sz_inout,
+ void **val_out)
+{
+ const char *k = *k_inout;
+ size_t sz = *sz_inout;
+ Trie *t, *resume;
+ unsigned off, max;
+ Tbitmap b;
+
+ if (!tbl)
+ return (false);
+ else {
+ t = &tbl->root;
+ if (k) {
+ resume = 0;
+ while (isbranch(t)) {
+ __builtin_prefetch(t->branch.twigs);
+ b = twigbit(t, k, sz);
+ TWIGOFFMAX(off, max, t, b);
+ if (!hastwig(t, b)) return (false);
+ t = twig(t, off);
+ if (off + 1 < max) resume = t + 1;
+ }
+ if (strcmp(k, t->leaf.key) != 0) return (false);
+ t = resume; if (!t) return (false);
+ }
+ }
+ while (isbranch(t)) t = twig(t, 0);
+ *k_inout = k = t->leaf.key; *sz_inout = strlen(k); *val_out = t->leaf.val;
+ return (true);
+}
+
+# elif TREE == QPTRIE_FN
+
+static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
+ void **val_out)
+{
+ const char *k = *k_inout;
+ size_t sz = *sz_inout;
+ Trie *resume;
+ unsigned off, max;
+ Tbitmap b;
+ Tindex i;
+
+ if (!t)
+ return (false);
+ else if (k) {
+ resume = 0;
+ while (isbranch(t)) {
+ __builtin_prefetch(t->ptr);
+ i = t->index; b = twigbit(i, k, sz);
+ TWIGOFFMAX(off, max, i, b);
+ if (!hastwig(i, b)) return (false);
+ t = Tbranch_twigs(t) + off;
+ if (off + 1 < max) resume = t + 1;
+ }
+ if (strcmp(k, Tleaf_key(t)) != 0) return (false);
+ t = resume; if (!t) return (false);
+ }
+ while (isbranch(t)) t = Tbranch_twigs(t);
+ *k_inout = k = Tleaf_key(t); *sz_inout = strlen(k);
+ *val_out = Tleaf_val(t);
+ return (true);
+}
+
+# endif
+
+# define DECLS \
+ Tbl *tbl = 0; \
+ struct word cur; \
+ void *v
+
+# define INIT do ; while (0)
+
+# define INSERT do { \
+ tbl = Tsetl(tbl, node->w.p, node->w.n, node); \
+ } while (0)
+
+# define ITERATE \
+ for (cur.p = 0, cur.n = 0; \
+ my_Tnextl(tbl, &cur.p, &cur.n, &v) ? node = v, 1 : 0; )
+
+# define FOCUS do ; while (0)
+
+# define GETPREFIX do { \
+ word.n = node->w.n - 1; assert(word.n < WORDMAX); \
+ memcpy(buf, node->w.p, word.n); buf[word.n] = 0; \
+ } while (0)
+
+# define LOOKUP Tgetl(tbl, buf, word.n)
+
+# define FREE do { \
+ while (tbl) { \
+ cur.p = 0; cur.n = 0; my_Tnextl(tbl, &cur.p, &cur.n, &v); \
+ tbl = Tsetl(tbl, cur.p, cur.n, 0); free(v); \
+ } \
+ } while (0)
+
+# define CHECK do ; while (0)
+
+#elif TREE == SGT_TREE234
+
+static int node_cmp(void *a, void *b)
+ { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
+
+# define DECLS \
+ tree234 *root; \
+ int i
+
+# define INIT do { root = newtree234(node_cmp); } while (0)
+
+# define INSERT do { \
+ if (add234(root, node) != node) { \
+ printf(";; duplicate `%s'\n", buf); \
+ free(node); node = 0; \
+ } \
+ } while (0)
+
+# define ITERATE for (i = 0; node = index234(root, i), node; i++)
+
+# define FOCUS do ; while (0)
+
+# define LOOKUP find234(root, &word, 0)
+
+# define FREE do { \
+ while (node = delpos234(root, 0), node) free(node); \
+ freetree234(root); \
+ } while (0)
+
+# define CHECK do ; while (0)
+
+#elif USE_LIBAVL
+
+static int node_cmp(const void *a, const void *b, void *arg)
+ { const struct word *wa = a, *wb = b; return (compare_words(wa, wb)); }
+
+static void free_node(void *n, void *arg) { free(n); }
+
+# define DECLS \
+ struct TABLE *tab; \
+ struct TRAVERSER it; \
+ void **p
+
+# define INIT do { \
+ tab = TREE_CREATE(node_cmp, 0, 0); \
+ if (!tab) bail("out of memory"); \
+ } while (0)
+
+# define INSERT do { \
+ p = TREE_PROBE(tab, node); if (!p) bail("out of memory"); \
+ if (*p != node) { \
+ printf(";; duplicate `%s'\n", buf); \
+ free(node); node = 0; \
+ } \
+ } while (0)
+
+# define ITERATE \
+ for (TREE_T_INIT(&it, tab); node = TREE_T_NEXT(&it), node; )
+
+# define FOCUS do ; while (0)
+
+# define LOOKUP TREE_FIND(tab, &word)
+
+# define FREE do { TREE_DESTROY(tab, free_node); } while (0)
+
+# define CHECK do ; while (0)
+
+#elif TREE == MLIB_SYM
+
+# define DECLS \
+ sym_table tab; \
+ sym_iter it; \
+ unsigned foundp
+
+# define INIT do { sym_create(&tab); } while (0)
+
+# define PREPNODE do ; while (0)
+
+# define INSERT do { \
+ node = sym_find(&tab, buf, word.n, sizeof(*node), &foundp); \
+ if (foundp) { bail(";; duplicate `%s'\n", buf); node = 0; } \
+ } while (0)
+
+# define ITERATE for (sym_mkiter(&it, &tab); node = sym_next(&it), node; )
+
+# define FOCUS do ; while (0)
+
+# define WORDPTR(node) (SYM_NAME(node))
+# define WORDLEN(node) (SYM_LEN(node))
+
+# define LOOKUP sym_find(&tab, word.p, word.n, 0, 0)
+
+# define FREE do { sym_destroy(&tab); } while (0)
+
+# define CHECK do ; while (0)
+
+#endif
+
+#ifndef PREPNODE
+# define PREPNODE do { \
+ node = malloc(sizeof(*node) + word.n + 1); \
+ if (!node) bail("out of memory"); \
+ node->w.p = (char *)(node + 1); \
+ memcpy(node + 1, buf, word.n + 1); node->w.n = word.n; \
+ } while (0)
+#endif
+
+#ifndef WORDPTR
+# define WORDPTR(node) ((node)->w.p)
+#endif
+
+#ifndef WORDLEN
+# define WORDLEN(node) ((node)->w.n)
+#endif
+
+#ifndef GETPREFIX
+# define GETPREFIX do { \
+ word.p = WORDPTR(node); word.n = WORDLEN(node) - 1; \
+ } while (0)
+
+#endif
+
+static void print_chain(struct node *node)
+{
+ if (!node->right) {
+ fputs(WORDPTR(node), stdout);
+ if (node->down) { putchar(' '); print_chain(node->down); }
+ } else {
+ fputs("{ ", stdout);
+ for (;;) {
+ fputs(WORDPTR(node), stdout);
+ if (node->down) { putchar(' '); print_chain(node->down); }
+ node = node->right; if (!node) break;
+ fputs(" | ", stdout);
+ }
+ fputs(" }", stdout);
+ }
+}
+
+int main(void)
+{
+ DECLS;
+ struct node *node, *parent;
+ struct word word;
+ char buf[WORDMAX];
+ int ch, max;
+
+ INIT;
+ word.p = buf;
+ for (;;) {
+ if (!fgets(buf, WORDMAX, stdin)) break;
+ word.n = strlen(buf); assert(word.n);
+ if (buf[word.n - 1] == '\n') buf[--word.n] = 0;
+ else if (word.n == WORDMAX - 1) bail("word too long");
+ else if (ch = getchar(), ch != EOF) bail("short read, found `%c'", ch);
+
+ PREPNODE; INSERT;
+ if (node) { node->up = node->down = node->right = 0; node->len = 1; }
+ }
+
+ CHECK;
+
+ max = 0;
+
+ ITERATE {
+ FOCUS;
+/* fprintf(stderr, ";; ponder `%.*s'\n", WORDLEN(node), WORDPTR(node)); */
+ if (WORDLEN(node) <= 1)
+ parent = 0;
+ else {
+ GETPREFIX;
+/* fprintf(stderr, ";; search `%.*s'\n", word.n, word.p); */
+ parent = LOOKUP;
+ }
+ node->up = parent;
+ while (parent) {
+ if (parent->len > node->len + 1) break;
+ if (parent->len < node->len + 1) parent->down = 0;
+ if (parent->down != node)
+ { node->right = parent->down; parent->down = node; }
+ parent->len = node->len + 1;
+ if (parent->len > max) max = parent->len;
+ node = parent; parent = node->up;
+ }
+ }
+
+ ITERATE if (node->len == max) { print_chain(node); putchar('\n'); }
+ FREE;
+ return (0);
+}
~mdw / wordchain / commitdiff