summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorStaffan Gimåker <staffan@spotify.com>2012-02-16 10:02:27 +0900
committerMartin Sustrik <sustrik@250bpm.com>2012-02-16 10:02:27 +0900
commitc1fc7c4a0ef0faf941a57e8eb6ffdc247ffb7129 (patch)
tree49fe59a482d418d9292da06c9653df2edadd3684
parent024e8b2d73237cf2a8e7e463b9b7c72764c00458 (diff)
Prune redundant nodes in the trie.
Signed-off-by: Staffan Gimåker <staffan@spotify.com>
-rw-r--r--src/trie.cpp26
-rw-r--r--src/trie.hpp3
2 files changed, 26 insertions, 3 deletions
diff --git a/src/trie.cpp b/src/trie.cpp
index 5656efb..2a21a5f 100644
--- a/src/trie.cpp
+++ b/src/trie.cpp
@@ -1,6 +1,7 @@
/*
Copyright (c) 2009-2012 250bpm s.r.o.
Copyright (c) 2007-2009 iMatix Corporation
+ Copyright (c) 2011-2012 Spotify AB
Copyright (c) 2007-2011 Other contributors as noted in the AUTHORS file
This file is part of Crossroads project.
@@ -35,7 +36,8 @@
xs::trie_t::trie_t () :
refcnt (0),
min (0),
- count (0)
+ count (0),
+ live_nodes (0)
{
}
@@ -112,6 +114,7 @@ bool xs::trie_t::add (unsigned char *prefix_, size_t size_)
if (count == 1) {
if (!next.node) {
next.node = new (std::nothrow) trie_t;
+ ++live_nodes;
xs_assert (next.node);
}
return next.node->add (prefix_ + 1, size_ - 1);
@@ -119,6 +122,7 @@ bool xs::trie_t::add (unsigned char *prefix_, size_t size_)
else {
if (!next.table [c - min]) {
next.table [c - min] = new (std::nothrow) trie_t;
+ ++live_nodes;
xs_assert (next.table [c - min]);
}
return next.table [c - min]->add (prefix_ + 1, size_ - 1);
@@ -146,7 +150,18 @@ bool xs::trie_t::rm (unsigned char *prefix_, size_t size_)
if (!next_node)
return false;
- return next_node->rm (prefix_ + 1, size_ - 1);
+ bool ret = next_node->rm (prefix_ + 1, size_ - 1);
+
+ if (next_node->is_redundant ()) {
+ delete next_node;
+ if (count == 1)
+ next.node = 0;
+ else
+ next.table [c - min] = 0;
+ --live_nodes;
+ }
+
+ return ret;
}
bool xs::trie_t::check (unsigned char *data_, size_t size_)
@@ -224,6 +239,11 @@ void xs::trie_t::apply_helper (
if (next.table [c])
next.table [c]->apply_helper (buff_, buffsize_ + 1, maxbuffsize_,
func_, arg_);
- }
+ }
+}
+
+bool xs::trie_t::is_redundant() const
+{
+ return refcnt == 0 && live_nodes == 0;
}
diff --git a/src/trie.hpp b/src/trie.hpp
index 19aaa26..ba7e3d2 100644
--- a/src/trie.hpp
+++ b/src/trie.hpp
@@ -1,6 +1,7 @@
/*
Copyright (c) 2009-2012 250bpm s.r.o.
Copyright (c) 2007-2009 iMatix Corporation
+ Copyright (c) 2011-2012 Spotify AB
Copyright (c) 2007-2011 Other contributors as noted in the AUTHORS file
This file is part of Crossroads project.
@@ -57,10 +58,12 @@ namespace xs
unsigned char **buff_, size_t buffsize_, size_t maxbuffsize_,
void (*func_) (unsigned char *data_, size_t size_, void *arg_),
void *arg_);
+ bool is_redundant () const;
uint32_t refcnt;
unsigned char min;
unsigned short count;
+ unsigned short live_nodes;
union {
class trie_t *node;
class trie_t **table;