[PATCH 06/15] Defer llink/rlink plumbing to the end of prep

[Nick Cleaton]

More groundwork for storage sharing between prep time and match time
fields: Wait until the final pass of trie preparation to set up the
trie->llink and trie->rlink fields.
---
 src/kwset.c |   71 +++++++++++++++++++++++++++++++++++++++-------------------
 1 files changed, 48 insertions(+), 23 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index f36f036..e0de003 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -241,32 +241,50 @@ compute_brood_notes (struct kwset *kwset, struct 
cpsort_dump *keywords,
   return brood_dest + 1;
 }
 
-/* Pre-allocate and plumb in a tree of 'count' trie nodes.  Push the nodes
-   onto the prealloced node list in right to left order. */
-static struct trie *
-alloc_and_plumb_siblings (struct kwset *kwset, int count, int depth)
+/* Pre-allocate a tree of 'count' trie nodes.  Push the nodes onto the
+   prealloced node list in right to left order. */
+static void
+alloc_siblings (struct kwset *kwset, int count, int depth)
 {
   if (count == 0)
-    return NULL;
+    return;
 
   int lcount = --count / 2;
   int rcount = count - lcount;
   struct trie *t = kwset->next_free_node++;
 
-  t->rlink = alloc_and_plumb_siblings (kwset, rcount, depth);
+  alloc_siblings (kwset, rcount, depth);
   t->depth = depth;
   t->is_lastkid = 0;
   t->links = kwset->next_prealloced;
   kwset->next_prealloced = t;
-  t->llink = alloc_and_plumb_siblings (kwset, lcount, depth);
+  alloc_siblings (kwset, lcount, depth);
+}
+
+/* Plumb in the rlink and llink pointers for a block of sibling trie nodes.
+   Must visit the nodes in the same order as alloc_siblings() above, so that
+   both functions use the same mapping between position in the node block
+   and position in the link tree. */
+static struct trie *
+plumb_siblings (struct trie **nodes, int count)
+{
+  if (count == 0)
+    return NULL;
+
+  int lcount = --count / 2;
+  int rcount = count - lcount;
+  struct trie *t = (*nodes)++;
+
+  t->rlink = plumb_siblings (nodes, rcount);
+  t->llink = plumb_siblings (nodes, lcount);
 
   return t;
 }
 
 /* Used to allocate each trie node from the node vector when building the
    trie from the sorted reversed keyword list, and to plumb the new node
-   into the trie.  Responsible for setting 'llink', 'rlink' and 'is_lastkid',
-   and for updating 'links' in the parent node.  */
+   into the trie.  Responsible for setting 'is_lastkid' and for updating
+   'links' in the parent node.  */
 static struct trie *
 allocate_and_plumb_trie_node (struct kwset *kwset, int index, int depth,
                               struct trie *parent)
@@ -279,13 +297,12 @@ allocate_and_plumb_trie_node (struct kwset *kwset, int 
index, int depth,
          a linked list (using 'links' as the list pointer) and tagged with
          the depth at which they are to be used.
 
-         Plumb in llink and rlink for the pre-allocated node block now.
-         This requires that they be pushed onto the pre-alloced list in right
-         to left order, so that they will come off the list in left to right
-         order, matching the order in which keywords are being added. */
-      parent->links = alloc_and_plumb_siblings (kwset,
-                                                kwset->bn_cursor->count,
-                                                depth);
+         To get the correct tree layout, the nodes must be pushed onto the
+         pre-alloced list in right to left order, so that they will come off
+         the list in left to right order, matching the order in which
+         keywords are being added. */
+      parent->links = kwset->next_free_node;
+      alloc_siblings (kwset, kwset->bn_cursor->count, depth);
       kwset->next_free_node[-1].is_lastkid = 1;
       kwset->bn_cursor++;
     }
@@ -301,7 +318,6 @@ allocate_and_plumb_trie_node (struct kwset *kwset, int 
index, int depth,
 
   /* This node is an only child. */
   parent->links = kwset->next_free_node++;
-  parent->links->llink = parent->links->rlink = NULL;
   parent->links->is_lastkid = 1;
   return parent->links;
 }
@@ -545,23 +561,32 @@ kwsprep (kwset_t kws)
         }
 
       /* Traverse the trie in level order again, fixing up all nodes whose
-         shift exceeds their inherited maxshift. */
-      for (curr = kwset->trie->next; curr; curr = curr->next)
+         shift exceeds their inherited maxshift and plumbing in the rlink
+         and llink fields. */
+      for (curr = kwset->trie; curr; curr = curr->next)
         {
-          if (curr->maxshift > curr->parent->maxshift)
+          if (curr->parent && curr->maxshift > curr->parent->maxshift)
             curr->maxshift = curr->parent->maxshift;
           if (curr->shift > curr->maxshift)
             curr->shift = curr->maxshift;
+          if (curr->links)
+            {
+              struct trie *links = curr->links;
+              struct trie *links_end = links;
+              while (!links_end++->is_lastkid)
+                ;
+              plumb_siblings (&links, links_end - links);
+            }
         }
 
       /* Create a vector, indexed by character code, of the outgoing links
          from the root node. */
       for (i = 0; i < NCHAR; ++i)
         next[i] = NULL;
-      if ((curr = kwset->trie->links))
+      if ((child = kwset->trie->links))
         do
-          next[curr->label] = curr;
-        while (!curr++->is_lastkid);
+          next[child->label] = child;
+        while (!child++->is_lastkid);
 
       if ((trans = kwset->trans) != NULL)
         for (i = 0; i < NCHAR; ++i)
-- 
1.5.6.3