summaryrefslogtreecommitdiff
path: root/src/mtrie.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'src/mtrie.cpp')
-rw-r--r--src/mtrie.cpp36
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;
+}
+