diff options
Diffstat (limited to 'src/mtrie.cpp')
| -rw-r--r-- | src/mtrie.cpp | 36 |
1 files changed, 33 insertions, 3 deletions
diff --git a/src/mtrie.cpp b/src/mtrie.cpp index 3a0a339..ad4978c 100644 --- a/src/mtrie.cpp +++ b/src/mtrie.cpp @@ -1,5 +1,6 @@ /* Copyright (c) 2011-2012 250bpm s.r.o. + Copyright (c) 2011-2012 Spotify AB Copyright (c) 2011 Other contributors as noted in the AUTHORS file This file is part of Crossroads project. @@ -34,7 +35,8 @@ xs::mtrie_t::mtrie_t () : min (0), - count (0) + count (0), + live_nodes (0) { } @@ -118,6 +120,7 @@ bool xs::mtrie_t::add_helper (unsigned char *prefix_, size_t size_, if (count == 1) { if (!next.node) { next.node = new (std::nothrow) mtrie_t; + ++live_nodes; xs_assert (next.node); } return next.node->add_helper (prefix_ + 1, size_ - 1, pipe_); @@ -125,6 +128,7 @@ bool xs::mtrie_t::add_helper (unsigned char *prefix_, size_t size_, else { if (!next.table [c - min]) { next.table [c - min] = new (std::nothrow) mtrie_t; + ++live_nodes; xs_assert (next.table [c - min]); } return next.table [c - min]->add_helper (prefix_ + 1, size_ - 1, pipe_); @@ -167,6 +171,11 @@ void xs::mtrie_t::rm_helper (pipe_t *pipe_, unsigned char **buff_, buffsize_++; next.node->rm_helper (pipe_, buff_, buffsize_, maxbuffsize_, func_, arg_); + if (next.node->is_redundant ()) { + delete next.node; + next.node = 0; + --live_nodes; + } return; } @@ -176,7 +185,12 @@ void xs::mtrie_t::rm_helper (pipe_t *pipe_, unsigned char **buff_, if (next.table [c]) next.table [c]->rm_helper (pipe_, buff_, buffsize_ + 1, maxbuffsize_, func_, arg_); - } + if (next.table [c]->is_redundant ()) { + delete next.table [c]; + next.table [c] = 0; + --live_nodes; + } + } } bool xs::mtrie_t::rm (unsigned char *prefix_, size_t size_, pipe_t *pipe_) @@ -203,7 +217,18 @@ bool xs::mtrie_t::rm_helper (unsigned char *prefix_, size_t size_, if (!next_node) return false; - return next_node->rm_helper (prefix_ + 1, size_ - 1, pipe_); + bool ret = next_node->rm_helper (prefix_ + 1, size_ - 1, pipe_); + + if (next_node->is_redundant ()) { + delete next_node; + if (count == 1) + next.node = 0; + else + next.table [c - min] = 0; + --live_nodes; + } + + return ret; } void xs::mtrie_t::match (unsigned char *data_, size_t size_, @@ -247,3 +272,8 @@ void xs::mtrie_t::match (unsigned char *data_, size_t size_, } } +bool xs::mtrie_t::is_redundant() const +{ + return pipes.empty () && live_nodes == 0; +} + |