[PATCH 07/15] Share storage between llink and fail

[Nick Cleaton]

The last use of trie->fail now occurs before the first use of
trie->llink, so they can share storage in the trie struct.
---
 src/kwset.c |   28 ++++++++++++++++------------
 1 files changed, 16 insertions(+), 12 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index e0de003..b8736a7 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -57,7 +57,12 @@
    arranged as a balanced tree.  */
 struct trie
 {
-  struct trie *llink;          /* Left tree link (to smaller labels). */
+  union
+  {
+    struct trie *llink;         /* Left tree link (to smaller labels). */
+    struct trie *fail;          /* Aho-Corasick failure function. */
+  }
+  lf;
   struct trie *rlink;          /* Right tree link (to larger labels). */
   unsigned char label;         /* Label on the incoming edge. */
   unsigned char is_lastkid;     /* True for the last of a group of siblings. */
@@ -65,7 +70,6 @@ struct trie
   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. */
-  struct trie *fail;           /* Aho-Corasick failure function. */
   int depth;                   /* Depth of this node from the root. */
   int shift;                   /* Shift function for search failures. */
   int maxshift;                        /* Max shift of self and descendents. */
@@ -276,7 +280,7 @@ plumb_siblings (struct trie **nodes, int count)
   struct trie *t = (*nodes)++;
 
   t->rlink = plumb_siblings (nodes, rcount);
-  t->llink = plumb_siblings (nodes, lcount);
+  t->lf.llink = plumb_siblings (nodes, lcount);
 
   return t;
 }
@@ -344,7 +348,7 @@ install_suffix (kwset_t kws, struct cpsort_md *md, char 
const *text,
       link->accepting = 0;
       link->parent = trie;
       link->next = NULL;
-      link->fail = NULL;
+      link->lf.fail = NULL;
       link->depth = trie_depth;
       link->shift = 0;
       link->label = *text++;
@@ -382,7 +386,7 @@ build_trie_from_sorted_keywords (struct kwset *kwset)
   kwset->trie->links = NULL;
   kwset->trie->parent = NULL;
   kwset->trie->next = NULL;
-  kwset->trie->fail = NULL;
+  kwset->trie->lf.fail = NULL;
   kwset->trie->depth = 0;
   kwset->trie->shift = 0;
   kwset->trie->is_lastkid = 1;
@@ -432,16 +436,16 @@ triefail (struct trie *trie, struct trie const *fail, 
struct trie *recourse)
             {
               if (trie->label == link->label)
                 {
-                  trie->fail = link;
+                  trie->lf.fail = link;
                   return;
                 }
             }
           while (!link++->is_lastkid);
         }
-      fail = fail->fail;
+      fail = fail->lf.fail;
     }
 
-  trie->fail = recourse;
+  trie->lf.fail = recourse;
 }
 
 /* Return true if A has every label in B. */
@@ -536,14 +540,14 @@ kwsprep (kwset_t kws)
                     delta[child->label] = curr->depth;
 
                   /* Compute the failure function for this node. */
-                  triefail (child, curr->fail, kwset->trie);
+                  triefail (child, curr->lf.fail, kwset->trie);
                 }
               while (!child++->is_lastkid);
             }
 
           /* Update the shifts at each node in the current node's chain
              of fails back to the root. */
-          for (fail = curr->fail; fail; fail = fail->fail)
+          for (fail = curr->lf.fail; fail; fail = fail->lf.fail)
             {
               /* If the current node has some outgoing edge that the fail
                  doesn't, then the shift at the fail should be no larger
@@ -763,7 +767,7 @@ cwexec (kwset_t kws, char const *text, size_t len, struct 
kwsmatch *kwsmatch)
           trie = trie->links;
           while (trie && c != trie->label)
             if (c < trie->label)
-              trie = trie->llink;
+              trie = trie->lf.llink;
             else
               trie = trie->rlink;
           if (trie)
@@ -813,7 +817,7 @@ cwexec (kwset_t kws, char const *text, size_t len, struct 
kwsmatch *kwsmatch)
           trie = trie->links;
           while (trie && c != trie->label)
             if (c < trie->label)
-              trie = trie->llink;
+              trie = trie->lf.llink;
             else
               trie = trie->rlink;
           if (trie)
-- 
1.5.6.3