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
