--- /dev/null
+### -*-makefile-*-
+
+all:
+TARGETS =
+
+clean::
+CLEAN =
+
+.PHONY: all clean
+
+.SECONDEXPANSION:
+
+SRCEXT =
+
+V = 0
+v-tag = $(call v-tag.$V,$1)
+v-tag.0 = @printf " %-8s %s\n" '$1' '$@';
+V_AT = $(V_AT.$V)
+V_AT.0 = @
+
+objify = $(addsuffix $1, \
+ $(basename \
+ $(filter $(addprefix %.,$(SRCEXT)), \
+ $2)))
+DEPOBJS =
+CLEAN += *.o *.d
+
+SRCEXT += c
+CC = gcc
+CFLAGS = $(OPTIMIZE) $(WARNINGS)
+CCLD = $(CC)
+LDFLAGS =
+OPTIMIZE = -O2 -g3 -fno-omit-frame-pointer
+WARNINGS = -pedantic -Wall
+
+SRCEXT += cc
+CXX = g++
+CXXFLAGS = $(CFLAGS)
+CXXLD = $(CXX)
+
+compile-c = $(call v-tag,CC)$(CC) -c $(CFLAGS) $3 \
+ -MD -MF $(1:.o=.d) -o$1 $2
+%.o: %.c
+ $(call compile-c,$@,$<)
+
+compile-c++ = $(call v-tag,CXX)$(CXX) -c $(CFLAGS) $3 \
+ -MD -MF $(1:.o=.d) -o$1 $2
+%.o: %.cc
+ $(call compile-c++,$@,$<)
+
+SRCEXT += rs
+RUSTC = rustc
+RUSTFLAGS = --edition=2018 -L. $(OPTIMIZE_RUST)
+OPTIMIZE_RUST = -O
+RUSTLIBS =
+CARGODIR = /usr/share/cargo/registry
+compile-rust = $(call v-tag,RUSTC)$(RUSTC) $(RUSTFLAGS) $3 \
+ -o$1 $2
+
+RUSTLIBS += typed_arena
+typed_arena_DIR = $(CARGODIR)/typed-arena-2.0.0
+typed_arena_RUSTFLAGS = --cfg 'feature="std"'
+
+RUSTLIB_OBJS = $(foreach l,$(RUSTLIBS), lib$l.rlib)
+CLEAN += $(RUSTLIB_OBJS)
+$(RUSTLIB_OBJS): lib%.rlib: $$($*_DEPS)
+ $(call compile-rust,$@,$($*_DIR)/src/lib.rs, \
+ --crate-type=rlib --crate-name=$* $($*_RUSTFLAGS))
+
+TREELIBS =
+VPATH =
+
+TREELIBS += xyla
+xyla_VARIANTS = avl rb splay treap
+XYLADIR = $(HOME)/src/libxyla
+xyla_LIBS = $(XYLADIR)/build/.libs/libxyla.a
+xyla_CFLAGS = -I$(XYLADIR)
+xyla-avl_CFLAGS = -DTREE=XYLA_AVL
+xyla-rb_CFLAGS = -DTREE=XYLA_RB
+xyla-splay_CFLAGS = -DTREE=XYLA_SPLAY
+xyla-treap_CFLAGS = -DTREE=XYLA_TREAP
+
+TREELIBS += qptrie
+qptrie_VARIANTS = qp-fanf qp-mdw fn-fanf fn-mdw
+QPDIR = $(HOME)/src/ext/qp
+VPATH += $(QPDIR)
+CFLAGS += -mpopcnt
+qptrie_CFLAGS = -I$(QPDIR)
+qptrie_SRCS = Tbl.c
+qptrie-qp_SRCS = qp.c
+qptrie-fn_SRCS = fn.c
+qptrie-qp-fanf_CFLAGS = -DTREE=QPTRIE_QP -DUSE_RECURSIVE_TNEXTL
+qptrie-qp-fanf_SRCS = $(qptrie-qp_SRCS)
+qptrie-fn-fanf_CFLAGS = -DTREE=QPTRIE_FN -DUSE_RECURSIVE_TNEXTL
+qptrie-fn-fanf_SRCS = $(qptrie-fn_SRCS)
+qptrie-qp-mdw_CFLAGS = -DTREE=QPTRIE_QP
+qptrie-qp-mdw_SRCS = $(qptrie-qp_SRCS)
+qptrie-fn-mdw_CFLAGS = -DTREE=QPTRIE_FN
+qptrie-fn-mdw_SRCS = $(qptrie-fn_SRCS)
+
+TREELIBS += sgt
+sgt_VARIANTS = tree234
+SGTDIR = $(HOME)/src/sgt/puzzles
+VPATH += $(SGTDIR)
+sgt_CFLAGS = -I$(SGTDIR)
+sgt-tree234_CFLAGS = -DTREE=SGT_TREE234
+sgt-tree234_SRCS = tree234.c malloc.c nullfe.c
+
+TREELIBS += libavl
+libavl_VARIANTS =
+LIBAVLDIR = $(HOME)/src/ext/avl
+VPATH += $(LIBAVLDIR)
+libavl_CFLAGS = -I$(LIBAVLDIR)
+
+libavl_VARIANTS += avl pavl rtavl tavl
+libavl-avl_CFLAGS = -DTREE=LIBAVL_AVL
+libavl-avl_SRCS = avl.c
+libavl-pavl_CFLAGS = -DTREE=LIBAVL_PAVL
+libavl-pavl_SRCS = pavl.c
+libavl-rtavl_CFLAGS = -DTREE=LIBAVL_RTAVL
+libavl-rtavl_SRCS = rtavl.c
+libavl-tavl_CFLAGS = -DTREE=LIBAVL_TAVL
+libavl-tavl_SRCS = tavl.c
+
+libavl_VARIANTS += rb prb rtrb trb
+libavl-rb_CFLAGS = -DTREE=LIBAVL_RB
+libavl-rb_SRCS = rb.c
+libavl-prb_CFLAGS = -DTREE=LIBAVL_PRB
+libavl-prb_SRCS = prb.c
+libavl-rtrb_CFLAGS = -DTREE=LIBAVL_RTRB
+libavl-rtrb_SRCS = rtrb.c
+libavl-trb_CFLAGS = -DTREE=LIBAVL_TRB
+libavl-trb_SRCS = trb.c
+
+#libavl_VARIANTS += bst pbst rtbst tbst
+libavl-bst_CFLAGS = -DTREE=LIBAVL_BST
+libavl-bst_SRCS = bst.c
+libavl-pbst_CFLAGS = -DTREE=LIBAVL_PBST
+libavl-pbst_SRCS = pbst.c
+libavl-rtbst_CFLAGS = -DTREE=LIBAVL_RTBST
+libavl-rtbst_SRCS = rtbst.c
+libavl-tbst_CFLAGS = -DTREE=LIBAVL_TBST
+libavl-tbst_SRCS = tbst.c
+
+TREELIBS += mLib
+mLib_VARIANTS = sym
+mLib_LIBS = -lmLib
+mLib-sym_CFLAGS = -DTREE=MLIB_SYM
+
+define def-c-variant
+ALL_VARIANTS += $1-$2
+TARGETS += chain.$1-$2
+CLEAN += chain.$1-$2
+$1-$2_OBJS = chain.$1-$2.o \
+ $$(call objify,.o,$$($1_SRCS) $$($1-$2_SRCS))
+run-$1-$2 = ./chain.$1-$2 <$$1
+DEPOBJS += $$($1-$2_OBJS)
+chain.$1-$2: $$($1-$2_OBJS)
+ $$(call v-tag,CCLD)$$(CCLD) $$(LDFLAGS) -o$$@ $$+ $$($1_LIBS)
+chain.$1-$2.o: chain.c
+ $$(call compile-c,$$@,$$<,$$($1_CFLAGS) $$($1-$2_CFLAGS))
+endef
+$(foreach t,$(TREELIBS), \
+ $(foreach v,$($t_VARIANTS), \
+ $(eval $(call def-c-variant,$t,$v))))
+
+c++_VARIANTS += map
+c++-map_CXXFLAGS = -DTREE=CXX_MAP
+c++_VARIANTS += uomap
+c++-uomap_CXXFLAGS = -DTREE=CXX_UOMAP
+
+define def-c++-variant
+ALL_VARIANTS += c++-$1
+TARGETS += chain.c++-$1
+CLEAN += chain.c++-$1
+c++-$1_OBJS = chain.c++-$1.o
+run-c++-$1 = ./chain.c++-$1 <$$1
+DEPOBJS += $$(c++-$1_OBJS)
+chain.c++-$1: $$(c++-$1_OBJS)
+ $$(call v-tag,CXXLD)$$(CXXLD) $$(LDFLAGS) -o$$@ $$+
+chain.c++-$1.o: chain.cc
+ $$(call compile-c++,$$@,$$<,$$(c++-$1_CXXFLAGS))
+endef
+$(foreach v,$(c++_VARIANTS), \
+ $(eval $(call def-c++-variant,$v)))
+
+rust_VARIANTS += btree
+rust-btree_RUSTFLAGS = --cfg 'feature="btree"'
+rust_VARIANTS += hash
+rust-hash_RUSTFLAGS = --cfg 'feature="hash"'
+
+define def-rust-variant
+ALL_VARIANTS += rust-$1
+TARGETS += chain.rust-$1
+CLEAN += chain.rust-$1
+run-rust-$1 = ./chain.rust-$1 <$$1
+chain.rust-$1: chain.rs $$(RUSTLIB_OBJS)
+ $$(call compile-rust,$$@,$$<, \
+ $$(foreach l,$$(RUSTLIBS), \
+ $$(rust-$1_RUSTFLAGS) --extern=$$l))
+endef
+$(foreach v,$(rust_VARIANTS), \
+ $(eval $(call def-rust-variant,$v)))
+
+DICT = /usr/share/dict/british-english-insane
+
+MEASURES = $(foreach v,$(ALL_VARIANTS), measure/$v)
+measure: $(MEASURES)
+$(MEASURES): measure/%: chain.%
+ $TIME -f%U
+.PHONY: measure $(MEASURES)
+
+all: $(TARGETS)
+
+clean::; rm -f $(CLEAN)
+
+-include $(DEPOBJS:.o=.d)
--- /dev/null
+#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);
+}
--- /dev/null
+#include <cassert>
+#include <cstdarg>
+#include <cstdio>
+#include <cstdlib>
+#include <cstring>
+
+#include <string>
+#include <utility>
+
+#define CXX_MAP 1
+#define CXX_UOMAP 2
+
+struct Node;
+typedef std::pair<const std::string, Node> WordNode;
+struct Node {
+ WordNode *down, *right, *up;
+ int len;
+};
+
+#if !TREE
+# error "`TREE' not defined or bungled constant setting"
+#elif TREE == CXX_MAP
+# include <map>
+ typedef std::map<std::string, Node> Map;
+#elif TREE == CXX_UOMAP
+# include <unordered_map>
+ typedef std::unordered_map<std::string, Node> Map;
+#else
+# error "unknown `TREE' value"
+#endif
+
+#define WORDMAX 64
+
+static void bail(const char *msg, ...)
+{
+ va_list ap;
+ long pos;
+
+ va_start(ap, msg); std::vfprintf(stderr, msg, ap); va_end(ap);
+ pos = std::ftell(stdin);
+ if (pos >= 0) std::fprintf(stderr, " (input pos = %ld)", pos);
+ std::fputc('\n', stderr);
+ std::exit(2);
+}
+
+static void print_chain(WordNode *node)
+{
+ if (!node->second.right) {
+ std::fputs(node->first.c_str(), stdout);
+ if (node->second.down)
+ { std::putchar(' '); print_chain(node->second.down); }
+ } else {
+ std::fputs("{ ", stdout);
+ for (;;) {
+ std::fputs(node->first.c_str(), stdout);
+ if (node->second.down)
+ { std::putchar(' '); print_chain(node->second.down); }
+ node = node->second.right; if (!node) break;
+ std::fputs(" | ", stdout);
+ }
+ std::fputs(" }", stdout);
+ }
+}
+
+int main(void)
+{
+ Map map{};
+ char buf[WORDMAX]; size_t n;
+ int ch, max;
+
+ for (;;) {
+ if (!std::fgets(buf, WORDMAX, stdin)) break;
+ n = std::strlen(buf); assert(n);
+ if (buf[n - 1] == '\n') buf[--n] = 0;
+ else if (n == WORDMAX - 1) bail("word too long");
+ else if (ch = std::getchar(), ch != EOF)
+ bail("short read, found `%c'", ch);
+
+ auto r = map.insert(WordNode(std::string(buf, n), Node{}));
+ if (!r.second) printf(";; duplicate `%s'\n", buf);
+ else {
+ WordNode *w = &*r.first;
+ w->second.up = w->second.down = w->second.right = 0;
+ w->second.len = 1;
+ }
+ }
+
+ max = 0;
+
+ for (auto p = map.begin(); p != map.end(); ++p) {
+/* std::fprintf(stderr, ";; ponder `%.*s'\n",
+ p->first.length(), p->first.c_str()); */
+ WordNode *w = &*p, *parent;
+ if (w->first.length() <= 1)
+ parent = 0;
+ else {
+/* std::fprintf(stderr, ";; search `%.*s'\n",
+ w->first.length(), w->first.c_str()); */
+ std::string prefix{w->first, 0, w->first.length() - 1};
+ auto p = map.find(prefix); parent = p == map.end() ? 0 : &*p;
+ }
+ w->second.up = parent;
+ while (parent) {
+ if (parent->second.len > w->second.len + 1) break;
+ if (parent->second.len < w->second.len + 1) parent->second.down = 0;
+ if (parent->second.down != w) {
+ w->second.right = parent->second.down;
+ parent->second.down = w;
+ }
+ parent->second.len = w->second.len + 1;
+ if (parent->second.len > max) max = parent->second.len;
+ w = parent; parent = w->second.up;
+ }
+ }
+
+ for (auto p = map.begin(); p != map.end(); ++p)
+ if (p->second.len == max) { print_chain(&*p); std::putchar('\n'); }
+ return (0);
+}
--- /dev/null
+use std::cell::Cell;
+use std::io::{self, BufRead, Write};
+use std::ptr;
+
+use typed_arena;
+
+#[cfg(feature = "btree")]
+use std::collections::{btree_map::Entry as MapEntry, BTreeMap as Map};
+
+#[cfg(feature = "hash")]
+use std::collections::{hash_map::Entry as MapEntry, HashMap as Map};
+
+#[derive(Debug, Default)]
+struct Node<'a> {
+ word: &'a [u8],
+ len: Cell<u32>,
+ down: Cell<Option<&'a Node<'a>>>,
+ right: Cell<Option<&'a Node<'a>>>,
+ up: Cell<Option<&'a Node<'a>>>
+}
+
+fn print_chain<W: io::Write>(node: &Node, out: &mut W) -> io::Result<()> {
+ match node.right.get() {
+ None => {
+ out.write_all(node.word)?;
+ if let Some(down) = node.down.get()
+ { out.write_all(b" ")?; print_chain(down, out)?; }
+ }
+ Some(_) => {
+ out.write_all(b"{ ")?;
+ let mut node = node;
+ loop {
+ out.write_all(node.word)?;
+ if let Some(down) = node.down.get()
+ { out.write_all(b" ")?; print_chain(down, out)?; }
+ if let Some(right) = node.right.get()
+ { node = right; out.write_all(b" | ")?; }
+ else
+ { break; }
+ }
+ out.write_all(b" }")?;
+ }
+ }
+ Ok(())
+}
+
+fn main() -> io::Result<()> {
+ let byte_arena = typed_arena::Arena::new();
+ let node_arena = typed_arena::Arena::new();
+ let mut buf: Vec<u8> = Vec::with_capacity(64);
+ let global_stdin = io::stdin(); let mut stdin = global_stdin.lock();
+ let global_stdout = io::stdout(); let mut stdout = global_stdout.lock();
+ let global_stderr = io::stderr(); let mut stderr = global_stderr.lock();
+ let mut map = Map::new();
+
+ loop {
+ buf.clear();
+ let n = stdin.read_until(b'\n', &mut buf)?;
+ let mut line = &buf[0 .. n];
+ let n = line.len();
+ if n == 0 { break; }
+ if line[n - 1] == b'\n' { line = &line[0 .. n - 1]; }
+//stdout.write_all(b";; read `")?;
+//stdout.write_all(line)?;
+//stdout.write_all(b"'\n")?;
+ let word: &[u8] = byte_arena.alloc_extend(line.iter().map(|p| *p));
+ if let MapEntry::Vacant(e) = map.entry(word) {
+ e.insert(node_arena.alloc(Node { word: word, .. Node::default() }));
+ } else {
+ stderr.write_all(b";; duplicate `")?;
+ stderr.write_all(word)?;
+ stderr.write_all(b"'\n")?;
+ }
+ }
+
+ let mut max = 0;
+ for node in map.values() {
+//stdout.write_all(b";; ponder `")?;
+//stdout.write_all(node.word)?;
+//stdout.write_all(b"'\n")?;
+ let mut node: &Node = node;
+ let mut parent;
+ let n = node.word.len();
+ if n <= 1 { parent = None; }
+ else { parent = map.get(&node.word[0 .. n - 1]).map(|n| &**n); }
+ node.up.set(parent);
+ while let Some(parent_node) = parent {
+ let plen = parent_node.len.get();
+ let nlen = node.len.get() + 1;
+ if plen > nlen { break; }
+ if plen < nlen { parent_node.down.set(None); }
+ match parent_node.down.get() {
+ Some(link) if ptr::eq(link, node) => (),
+ _ => {
+ node.right.set(parent_node.down.get());
+ parent_node.down.set(Some(node));
+ }
+ }
+ parent_node.len.set(nlen);
+ if nlen > max { max = nlen; }
+ node = parent_node; parent = node.up.get()
+ }
+ }
+
+ for node in map.values() {
+ if node.len.get() == max
+ { print_chain(node, &mut stdout)?; stdout.write(b"\n")?; }
+ }
+
+ Ok(())
+}
~mdw / wordchain / commitdiff