summaryrefslogtreecommitdiff
path: root/src/trie.cpp
diff options
context:
space:
mode:
authorMartin Sustrik <sustrik@250bpm.com>2012-04-05 07:32:58 +0200
committerMartin Sustrik <sustrik@250bpm.com>2012-04-05 07:32:58 +0200
commitd82cbb3a81f116cd22e9895ecac36ac3d7b38929 (patch)
tree03c923311b937f550bec325d131476513a02bebf /src/trie.cpp
parent52b8a917deb2990e7197b82e81e0258ebe30f424 (diff)
XS_PLUGIN and XS_FILTER implementation
This patch introduces following features: - XS_PLUGIN context option to add plugins to libxs - XS_FILTER option to switch between different filter types - Automatic loading of plug-ins is *not* implemented. From the implementation point of view: - standard prefix filter is implemented as a pluggable filter - trie_t and mtrie_t are joined into a single class - the code for 0MQ/3.1 compatibility is left in in the form of comments - new test for testing re-subscriptions is added Signed-off-by: Martin Sustrik <sustrik@250bpm.com>
Diffstat (limited to 'src/trie.cpp')
-rw-r--r--src/trie.cpp338
1 files changed, 0 insertions, 338 deletions
diff --git a/src/trie.cpp b/src/trie.cpp
deleted file mode 100644
index af6cdd9..0000000
--- a/src/trie.cpp
+++ /dev/null
@@ -1,338 +0,0 @@
-/*
- 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 I/O project.
-
- Crossroads I/O is free software; you can redistribute it and/or modify it
- under the terms of the GNU Lesser General Public License as published by
- the Free Software Foundation; either version 3 of the License, or
- (at your option) any later version.
-
- Crossroads is distributed in the hope that it will be useful,
- but WITHOUT ANY WARRANTY; without even the implied warranty of
- MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
- GNU Lesser General Public License for more details.
-
- You should have received a copy of the GNU Lesser General Public License
- along with this program. If not, see <http://www.gnu.org/licenses/>.
-*/
-
-#include <stdlib.h>
-
-#include <new>
-#include <algorithm>
-
-#include "platform.hpp"
-#if defined XS_HAVE_WINDOWS
-#include "windows.hpp"
-#endif
-
-#include "err.hpp"
-#include "trie.hpp"
-
-xs::trie_t::trie_t () :
- refcnt (0),
- min (0),
- count (0),
- live_nodes (0)
-{
-}
-
-xs::trie_t::~trie_t ()
-{
- if (count == 1) {
- xs_assert (next.node);
- delete next.node;
- next.node = 0;
- }
- else if (count > 1) {
- for (unsigned short i = 0; i != count; ++i)
- if (next.table [i])
- delete next.table [i];
- free (next.table);
- }
-}
-
-bool xs::trie_t::add (unsigned char *prefix_, size_t size_)
-{
- // We are at the node corresponding to the prefix. We are done.
- if (!size_) {
- ++refcnt;
- return refcnt == 1;
- }
-
- unsigned char c = *prefix_;
- if (c < min || c >= min + count) {
-
- // The character is out of range of currently handled
- // charcters. We have to extend the table.
- if (!count) {
- min = c;
- count = 1;
- next.node = NULL;
- }
- else if (count == 1) {
- unsigned char oldc = min;
- trie_t *oldp = next.node;
- count = (min < c ? c - min : min - c) + 1;
- next.table = (trie_t**)
- malloc (sizeof (trie_t*) * count);
- xs_assert (next.table);
- for (unsigned short i = 0; i != count; ++i)
- next.table [i] = 0;
- min = std::min (min, c);
- next.table [oldc - min] = oldp;
- }
- else if (min < c) {
-
- // The new character is above the current character range.
- unsigned short old_count = count;
- count = c - min + 1;
- next.table = (trie_t**) realloc ((void*) next.table,
- sizeof (trie_t*) * count);
- xs_assert (next.table);
- for (unsigned short i = old_count; i != count; i++)
- next.table [i] = NULL;
- }
- else {
-
- // The new character is below the current character range.
- unsigned short old_count = count;
- count = (min + old_count) - c;
- next.table = (trie_t**) realloc ((void*) next.table,
- sizeof (trie_t*) * count);
- xs_assert (next.table);
- memmove (next.table + min - c, next.table,
- old_count * sizeof (trie_t*));
- for (unsigned short i = 0; i != min - c; i++)
- next.table [i] = NULL;
- min = c;
- }
- }
-
- // If next node does not exist, create one.
- if (count == 1) {
- if (!next.node) {
- next.node = new (std::nothrow) trie_t;
- xs_assert (next.node);
- ++live_nodes;
- xs_assert (live_nodes == 1);
- }
- return next.node->add (prefix_ + 1, size_ - 1);
- }
- else {
- if (!next.table [c - min]) {
- next.table [c - min] = new (std::nothrow) trie_t;
- xs_assert (next.table [c - min]);
- ++live_nodes;
- xs_assert (live_nodes > 1);
- }
- return next.table [c - min]->add (prefix_ + 1, size_ - 1);
- }
-}
-
-bool xs::trie_t::rm (unsigned char *prefix_, size_t size_)
-{
- // TODO: Shouldn't an error be reported if the key does not exist?
-
- if (!size_) {
- if (!refcnt)
- return false;
- refcnt--;
- return refcnt == 0;
- }
-
- unsigned char c = *prefix_;
- if (!count || c < min || c >= min + count)
- return false;
-
- trie_t *next_node =
- count == 1 ? next.node : next.table [c - min];
-
- if (!next_node)
- return false;
-
- bool ret = next_node->rm (prefix_ + 1, size_ - 1);
-
- // Prune redundant nodes
- if (next_node->is_redundant ()) {
- delete next_node;
- xs_assert (count > 0);
-
- if (count == 1) {
- // The just pruned node is was the only live node
- next.node = 0;
- count = 0;
- --live_nodes;
- xs_assert (live_nodes == 0);
- }
- else {
- next.table [c - min] = 0;
- xs_assert (live_nodes > 1);
- --live_nodes;
-
- // Compact the table if possible
- if (live_nodes == 1) {
- // We can switch to using the more compact single-node
- // representation since the table only contains one live node
- trie_t *node = 0;
- // Since we always compact the table the pruned node must
- // either be the left-most or right-most ptr in the node
- // table
- if (c == min) {
- // The pruned node is the left-most node ptr in the
- // node table => keep the right-most node
- node = next.table [count - 1];
- min += count - 1;
- }
- else if (c == min + count - 1) {
- // The pruned node is the right-most node ptr in the
- // node table => keep the left-most node
- node = next.table [0];
- }
-
- xs_assert (node);
- free (next.table);
- next.node = node;
- count = 1;
- }
- else if (c == min) {
- // We can compact the table "from the left".
- // Find the left-most non-null node ptr, which we'll use as
- // our new min
- unsigned char new_min = min;
- for (unsigned short i = 1; i < count; ++i) {
- if (next.table [i]) {
- new_min = i + min;
- break;
- }
- }
- xs_assert (new_min != min);
-
- trie_t **old_table = next.table;
- xs_assert (new_min > min);
- xs_assert (count > new_min - min);
-
- count = count - (new_min - min);
- next.table = (trie_t**) malloc (sizeof (trie_t*) * count);
- xs_assert (next.table);
-
- memmove (next.table, old_table + (new_min - min),
- sizeof (trie_t*) * count);
- free (old_table);
-
- min = new_min;
- }
- else if (c == min + count - 1) {
- // We can compact the table "from the right".
- // Find the right-most non-null node ptr, which we'll use to
- // determine the new table size
- unsigned short new_count = count;
- for (unsigned short i = 1; i < count; ++i) {
- if (next.table [count - 1 - i]) {
- new_count = count - i;
- break;
- }
- }
- xs_assert (new_count != count);
- count = new_count;
-
- trie_t **old_table = next.table;
- next.table = (trie_t**) malloc (sizeof (trie_t*) * count);
- xs_assert (next.table);
-
- memmove (next.table, old_table, sizeof (trie_t*) * count);
- free (old_table);
- }
- }
- }
-
- return ret;
-}
-
-bool xs::trie_t::check (unsigned char *data_, size_t size_)
-{
- // This function is on critical path. It deliberately doesn't use
- // recursion to get a bit better performance.
- trie_t *current = this;
- while (true) {
-
- // We've found a corresponding subscription!
- if (current->refcnt)
- return true;
-
- // We've checked all the data and haven't found matching subscription.
- if (!size_)
- return false;
-
- // If there's no corresponding slot for the first character
- // of the prefix, the message does not match.
- unsigned char c = *data_;
- if (c < current->min || c >= current->min + current->count)
- return false;
-
- // Move to the next character.
- if (current->count == 1)
- current = current->next.node;
- else {
- current = current->next.table [c - current->min];
- if (!current)
- return false;
- }
- data_++;
- size_--;
- }
-}
-
-void xs::trie_t::apply (void (*func_) (unsigned char *data_, size_t size_,
- void *arg_), void *arg_)
-{
- unsigned char *buff = NULL;
- apply_helper (&buff, 0, 0, func_, arg_);
- free (buff);
-}
-
-void xs::trie_t::apply_helper (
- unsigned char **buff_, size_t buffsize_, size_t maxbuffsize_,
- void (*func_) (unsigned char *data_, size_t size_, void *arg_), void *arg_)
-{
- // If this node is a subscription, apply the function.
- if (refcnt)
- func_ (*buff_, buffsize_, arg_);
-
- // Adjust the buffer.
- if (buffsize_ >= maxbuffsize_) {
- maxbuffsize_ = buffsize_ + 256;
- *buff_ = (unsigned char*) realloc (*buff_, maxbuffsize_);
- xs_assert (*buff_);
- }
-
- // If there are no subnodes in the trie, return.
- if (count == 0)
- return;
-
- // If there's one subnode (optimisation).
- if (count == 1) {
- (*buff_) [buffsize_] = min;
- buffsize_++;
- next.node->apply_helper (buff_, buffsize_, maxbuffsize_, func_, arg_);
- return;
- }
-
- // If there are multiple subnodes.
- for (unsigned short c = 0; c != count; c++) {
- (*buff_) [buffsize_] = min + c;
- 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;
-}
-