chain.c: Optimize storage layout.

  * Remove redundant word pointers from node types that don't need
    it.  (That's Xyla, QP-tries, and SGT's `tree234'.)  It's saves an
    indirection to find the string by knowing that it's at a fixed
    offset from the node base.

  * Pack the chain length in with the word length.

diff --git a/chain.c b/chain.c
index 94dc4ae6ceedd1e9aa27d29874b92ed5ba3e1361..50a92b885c7ace00f151bb314e89ee71db2e73b0 100644 (file)
--- a/chain.c
+++ b/chain.c
@@ -180,6 +180,7 @@ struct word {
 } word;
 
 struct node {
+
 #if USE_XYLA
   TREE_NODEPFX;
 #elif TREE == MLIB_SYM
@@ -187,17 +188,38 @@ struct node {
 # define WORDPTR(node) (SYM_NAME(node))
 # define WORDLEN(node) (SYM_LEN(node))
 #endif
+
+#if TREE == MLIB_SYM
+
+  short chlen;
+# define CHLEN(node) ((node)->chlen)
+
+#elif USE_LIBAVL
+
+  union {
+    struct word w;
+    struct { const char *p; unsigned short n; short chlen; } pack;
+  } u;
+# define WORDPTR(node) ((const char *)((node) + 1))
+# define WORDLEN(node) ((node)->u.w.n)
+# define CHLEN(node) ((node)->u.pack.chlen)
+
+#else
+
+  unsigned short wlen;
+# define WORDPTR(node) ((const char *)((node) + 1))
+# define WORDLEN(node) ((node)->wlen)
+
+  short chlen;
+# define CHLEN(node) ((node)->chlen)
+
+#endif
+
 #if TREE == MLIB_SYM || (USE_QPTRIE && QPTRIE_ITER == QPITER_LIST)
   struct node *next;
 #endif
-#if TREE != MLIB_SYM
-  struct word w;
-# define WORDPTR(node) ((node)->w.p)
-# define WORDLEN(node) ((node)->w.n)
-#endif
+
   struct node *down, *right, *up;
-  short chlen;
-# define CHLEN(node) ((node)->chlen)
 };
 
 #define WORDMAX 64
@@ -285,17 +307,29 @@ static int word_nav(struct xyla_bt_nodecls *cls,
 #    define CHECK do ; while (0)
 #  else
 
-static const void *word_key(struct xyla_bt_nodecls *cls,
+static const void *node_key(struct xyla_bt_nodecls *cls,
                            const struct xyla_bt_node *nn)
-  { struct node *node = (struct node *)nn; return (&node->w); }
+  { return (nn); }
+
+static int node_nav(struct xyla_bt_nodecls *cls,
+                   const struct xyla_bt_node *nn, void *k)
+{
+  const struct node *na = k, *nb = (const struct node *)nn;
+
+  return (compare_words(WORDPTR(na), WORDLEN(na), WORDPTR(nb), WORDLEN(nb)));
+}
 
 static void word_ident(struct xyla_bt_nodecls *cls,
                       const struct xyla_bt_node *nn, FILE *fp)
-  { struct node *node = (struct node *)nn; fprintf(fp, "`%s'", node->w.p); }
+{
+  struct node *node = (struct node *)nn;
+
+  fprintf(fp, "`%s'", WORDPTR(node));
+}
 
 static const struct xyla_bt_chkops word_ops = {
   { sizeof(word_ops), 0 },
-  { word_nav, word_key },
+  { node_nav, node_key },
   { xyla_bt_chkorder, sizeof(struct xyla_bt_ordinfo), word_ident }
 };
 struct xyla_bt_nodecls word_cls = { &word_ops.node };
@@ -405,7 +439,7 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  define INIT do ; while (0)
 
 #  define INSERT do {                                                  \
-       tbl = Tsetl(tbl, node->w.p, node->w.n, node);                   \
+       tbl = Tsetl(tbl, WORDPTR(node), WORDLEN(node), node);           \
        INSERT_LIST;                                                    \
    } while (0)
 
@@ -421,8 +455,8 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  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;                \
+       word.n = WORDLEN(node) - 1; assert(word.n < WORDMAX);           \
+       memcpy(buf, WORDPTR(node), word.n); buf[word.n] = 0;            \
    } while (0)
 
 #  define LOOKUP Tgetl(tbl, buf, word.n)
@@ -430,7 +464,7 @@ static bool my_Tnextl(Tbl *t, const char **k_inout, size_t *sz_inout,
 #  if QPTRIE_ITER == QPITER_LIST
 #    define FREE do {                                                  \
        for (node = all; node; node = next) {                           \
-         tbl = Tsetl(tbl, node->w.p, node->w.n, 0);                    \
+         tbl = Tsetl(tbl, WORDPTR(node), WORDLEN(node), 0);            \
          next = node->next; free(node);                                \
        }                                                               \
        assert(!tbl);                                                   \
@@ -511,6 +545,13 @@ static void free_node(void *n, void *arg) { free(n); }
        if (!tab) bail("out of memory");                                \
    } while (0)
 
+#  define PREPNODE do {                                                        \
+       node = malloc(sizeof(*node) + word.n + 1);                      \
+         if (!node) bail("out of memory");                             \
+       memcpy(node + 1, buf, word.n + 1);                              \
+       node->u.w.p = (const char *)(node + 1); node->u.w.n = word.n;   \
+   } while (0)
+
 #  define INSERT do {                                                  \
        p = TREE_PROBE(tab, node); if (!p) bail("out of memory");       \
        if (*p != node) {                                               \
@@ -570,8 +611,7 @@ static void free_node(void *n, void *arg) { free(n); }
 #  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;          \
+       memcpy(node + 1, buf, word.n + 1); node->wlen = word.n;         \
    } while (0)
 #endif