From 1372c9b6f40872663201bc9d78558189a7220c36 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Staffan=20Gim=C3=A5ker?= Date: Mon, 27 Feb 2012 11:51:30 +0100 Subject: Fixed a bug in the mtrie table compaction logic. MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Signed-off-by: Staffan Gimåker --- src/mtrie.cpp | 17 ++++++++++++----- 1 file changed, 12 insertions(+), 5 deletions(-) (limited to 'src') 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; } } -- cgit v1.2.3