summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorStaffan Gimåker <staffan@spotify.com>2012-02-27 11:51:30 +0100
committerMartin Sustrik <sustrik@250bpm.com>2012-02-28 16:00:32 +0100
commit1372c9b6f40872663201bc9d78558189a7220c36 (patch)
tree777a39c5ad1b037d0f24904b175bafd159232cb6
parent9539d1c64cfd2fb9607d39f5c051f21fa53468a3 (diff)
Fixed a bug in the mtrie table compaction logic.
Signed-off-by: Staffan Gimåker <staffan@spotify.com>
-rw-r--r--src/mtrie.cpp17
1 files changed, 12 insertions, 5 deletions
diff --git a/src/mtrie.cpp b/src/mtrie.cpp
index fd57f00..eae34c2 100644
--- a/src/mtrie.cpp
+++ b/src/mtrie.cpp
@@ -200,16 +200,16 @@ void xs::mtrie_t::rm_helper (pipe_t *pipe_, unsigned char **buff_,
// If there are multiple subnodes.
//
// New min non-null character in the node table after the removal
- unsigned char new_min = min;
+ unsigned char new_min = min + count - 1;
// New max non-null character in the node table after the removal
- unsigned char new_max = min + count - 1;
+ unsigned char new_max = min;
for (unsigned short c = 0; c != count; c++) {
(*buff_) [buffsize_] = min + c;
if (next.table [c]) {
next.table [c]->rm_helper (pipe_, buff_, buffsize_ + 1,
maxbuffsize_, func_, arg_);
- // Prune redudant nodes from the mtrie
+ // Prune redundant nodes from the mtrie
if (next.table [c]->is_redundant ()) {
delete next.table [c];
next.table [c] = 0;
@@ -218,9 +218,16 @@ void xs::mtrie_t::rm_helper (pipe_t *pipe_, unsigned char **buff_,
--live_nodes;
}
else {
- if (c + 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 + min < new_min)
new_min = c + min;
- if (c + min < new_max)
+ if (c + min > new_max)
new_max = c + min;
}
}