summaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
authorAdam Guthrie <asguthrie@gmail.com>2012-04-29 07:24:11 +0200
committerMartin Sustrik <sustrik@250bpm.com>2012-04-29 07:24:11 +0200
commit4cd65e7c488379f4f4a719a6400c839b61c61f7c (patch)
tree8cdd66b8d0e89ef57a0063e5db65480001e720fd /src
parent5b468252036fdbadfab00df743c35a415fbb2adb (diff)
Fix a bug in prefix filter compaction logic
Diffstat (limited to 'src')
-rw-r--r--src/prefix_filter.cpp17
1 files changed, 12 insertions, 5 deletions
diff --git a/src/prefix_filter.cpp b/src/prefix_filter.cpp
index 1a9b8ac..5f1a72a 100644
--- a/src/prefix_filter.cpp
+++ b/src/prefix_filter.cpp
@@ -226,17 +226,17 @@ static void pfx_rm_all (pfx_node_t *node_, void *subscribers_,
// If there are multiple subnodes.
// New min non-null character in the node table after the removal.
- unsigned char new_min = node_->min;
+ unsigned char new_min = node_->min + node_->count - 1;
// New max non-null character in the node table after the removal.
- unsigned char new_max = node_->min + node_->count - 1;
+ unsigned char new_max = node_->min;
for (unsigned short c = 0; c != node_->count; c++) {
(*buff_) [buffsize_] = node_->min + c;
if (node_->next.table [c]) {
pfx_rm_all (node_->next.table [c], subscribers_, buff_,
buffsize_ + 1, maxbuffsize_, arg_);
- // Prune redudant nodes from the the trie.
+ // Prune redundant nodes from the the trie.
if (pfx_is_redundant (node_->next.table [c])) {
pfx_close (node_->next.table [c]);
free (node_->next.table [c]);
@@ -246,9 +246,16 @@ static void pfx_rm_all (pfx_node_t *node_, void *subscribers_,
--node_->live_nodes;
}
else {
- if (c + node_->min > new_min)
+ // The node is not redundant, so it's a candidate for being
+ // the new min/max node.
+ //
+ // We loop through the node array from left to right, so the
+ // first non-null, non-redundant node encountered is the new
+ // minimum index. Conversely, the last non-redundant, non-null
+ // node encountered is the new maximum index.
+ if (c + node_->min < new_min)
new_min = c + node_->min;
- if (c + node_->min < new_max)
+ if (c + node_->min > new_max)
new_max = c + node_->min;
}
}