[PATCH 09/15] Share storage between rlink and depth

[Nick Cleaton]

The last use of trie->depth now occurs before the first use of
trie->rlink, so they can share storage in the trie struct.
---
 src/kwset.c |   34 +++++++++++++++++++---------------
 1 files changed, 19 insertions(+), 15 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index a408c3a..1a899e3 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -63,14 +63,18 @@ struct trie
     struct trie *fail;          /* Aho-Corasick failure function. */
   }
   lf;
-  struct trie *rlink;          /* Right tree link (to larger labels). */
+  union
+  {
+    struct trie *rlink;         /* Right tree link (to larger labels). */
+    int depth;                  /* Depth of this node from the root. */
+  }
+  rd;
   unsigned char label;         /* Label on the incoming edge. */
   unsigned char is_lastkid;     /* True for the last of a group of siblings. */
   unsigned int accepting;      /* Word index of accepted word, or zero. */
   struct trie *links;          /* Tree of edges leaving this node. */
   struct trie *parent;         /* Parent of this node. */
   struct trie *next;           /* List of all trie nodes in level order. */
-  int depth;                   /* Depth of this node from the root. */
   int shift;                   /* Shift function for search failures. */
   int maxshift;                        /* Max shift of self and descendents. */
 };
@@ -258,7 +262,7 @@ alloc_siblings (struct kwset *kwset, int count, int depth)
   struct trie *t = kwset->next_free_node++;
 
   alloc_siblings (kwset, rcount, depth);
-  t->depth = depth;
+  t->rd.depth = depth;
   t->is_lastkid = 0;
   t->links = kwset->next_prealloced;
   kwset->next_prealloced = t;
@@ -279,7 +283,7 @@ plumb_siblings (struct trie **nodes, int count)
   int rcount = count - lcount;
   struct trie *t = (*nodes)++;
 
-  t->rlink = plumb_siblings (nodes, rcount);
+  t->rd.rlink = plumb_siblings (nodes, rcount);
   t->lf.llink = plumb_siblings (nodes, lcount);
 
   return t;
@@ -311,7 +315,7 @@ allocate_and_plumb_trie_node (struct kwset *kwset, int 
index, int depth,
       kwset->bn_cursor++;
     }
 
-  if (kwset->next_prealloced && kwset->next_prealloced->depth == depth)
+  if (kwset->next_prealloced && kwset->next_prealloced->rd.depth == depth)
     {
       /* This node is part of a group of siblings for which a block of
          adjacent nodes has been allocated and plumbed in.  */
@@ -349,7 +353,7 @@ install_suffix (kwset_t kws, struct cpsort_md *md, char 
const *text,
       link->parent = trie;
       link->next = NULL;
       link->lf.fail = NULL;
-      link->depth = trie_depth;
+      link->rd.depth = trie_depth;
       link->shift = 0;
       link->label = *text++;
       kwset->prev_kw_tries[trie_depth] = link;
@@ -387,7 +391,7 @@ build_trie_from_sorted_keywords (struct kwset *kwset)
   kwset->trie->parent = NULL;
   kwset->trie->next = NULL;
   kwset->trie->lf.fail = NULL;
-  kwset->trie->depth = 0;
+  kwset->trie->rd.depth = 0;
   kwset->trie->shift = 0;
   kwset->trie->is_lastkid = 1;
 
@@ -536,8 +540,8 @@ kwsprep (kwset_t kws)
                   last = last->next = child;
 
                   /* Update the delta table. */
-                  if (curr->depth < delta[child->label])
-                    delta[child->label] = curr->depth;
+                  if (curr->rd.depth < delta[child->label])
+                    delta[child->label] = curr->rd.depth;
 
                   /* Compute the failure function for this node. */
                   triefail (child, curr->lf.fail, kwset->trie);
@@ -552,15 +556,15 @@ kwsprep (kwset_t kws)
               /* If the current node has some outgoing edge that the fail
                  doesn't, then the shift at the fail should be no larger
                  than the difference of their depths. */
-              if (curr->links && curr->depth - fail->depth < fail->shift)
+              if (curr->links && curr->rd.depth - fail->rd.depth < fail->shift)
                 if (!fail->links || !hasevery(fail->links, curr->links))
-                  fail->shift = curr->depth - fail->depth;
+                  fail->shift = curr->rd.depth - fail->rd.depth;
 
               /* If the current node is accepting then the shift at the
                  fail and its descendents should be no larger than the
                  difference of their depths. */
-              if (curr->accepting && fail->maxshift > curr->depth - 
fail->depth)
-                fail->maxshift = curr->depth - fail->depth;
+              if (curr->accepting && fail->maxshift > curr->rd.depth - 
fail->rd.depth)
+                fail->maxshift = curr->rd.depth - fail->rd.depth;
             }
         }
 
@@ -769,7 +773,7 @@ cwexec (kwset_t kws, char const *text, size_t len, struct 
kwsmatch *kwsmatch)
             if (c < trie->label)
               trie = trie->lf.llink;
             else
-              trie = trie->rlink;
+              trie = trie->rd.rlink;
           if (trie)
             {
               if (trie->accepting)
@@ -820,7 +824,7 @@ cwexec (kwset_t kws, char const *text, size_t len, struct 
kwsmatch *kwsmatch)
             if (c < trie->label)
               trie = trie->lf.llink;
             else
-              trie = trie->rlink;
+              trie = trie->rd.rlink;
           if (trie)
             {
               if (trie->accepting && beg <= mch)
-- 
1.5.6.3