[PATCH 10/15] Eliminate the trie->parent field

[Nick Cleaton]

The last remaining use of trie->parent occurs in the maxshift prep
pass; it can be eliminated by applying the maxshift correction to the
children of the current node rather than to the current node itself.
---
 src/kwset.c |   27 ++++++++++++++-------------
 1 files changed, 14 insertions(+), 13 deletions(-)

diff --git a/src/kwset.c b/src/kwset.c
index 1a899e3..c30e951 100644
--- a/src/kwset.c
+++ b/src/kwset.c
@@ -73,7 +73,6 @@ struct trie
   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 shift;                   /* Shift function for search failures. */
   int maxshift;                        /* Max shift of self and descendents. */
@@ -350,7 +349,6 @@ install_suffix (kwset_t kws, struct cpsort_md *md, char 
const *text,
     {
       link = allocate_and_plumb_trie_node (kwset, index, ++trie_depth, trie);
       link->accepting = 0;
-      link->parent = trie;
       link->next = NULL;
       link->lf.fail = NULL;
       link->rd.depth = trie_depth;
@@ -388,7 +386,6 @@ build_trie_from_sorted_keywords (struct kwset *kwset)
   kwset->trie = kwset->next_free_node++;
   kwset->trie->accepting = 0;
   kwset->trie->links = NULL;
-  kwset->trie->parent = NULL;
   kwset->trie->next = NULL;
   kwset->trie->lf.fail = NULL;
   kwset->trie->rd.depth = 0;
@@ -573,18 +570,22 @@ kwsprep (kwset_t kws)
          and llink fields. */
       for (curr = kwset->trie; curr; curr = curr->next)
         {
-          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)
+          if (!(child = curr->links))
+            continue;
+
+          do
             {
-              struct trie *links = curr->links;
-              struct trie *links_end = links;
-              while (!links_end++->is_lastkid)
-                ;
-              plumb_siblings (&links, links_end - links);
+              if (curr->maxshift < child->maxshift)
+                child->maxshift = curr->maxshift;
+              if (child->maxshift < child->shift)
+                child->shift = child->maxshift;
             }
+          while (!child++->is_lastkid);
+
+          {
+            struct trie *links = curr->links;
+            plumb_siblings (&links, child - links);
+          }
         }
 
       /* Create a vector, indexed by character code, of the outgoing links
-- 
1.5.6.3