From 6ec783e7023b4c4d4d10a3870b4c560684ae7069 Mon Sep 17 00:00:00 2001 From: Martin Sustrik Date: Sat, 28 Aug 2010 13:26:19 +0200 Subject: prefix_tree_t renamed to trie_t --- src/Makefile.am | 4 +- src/prefix_tree.cpp | 180 ---------------------------------------------------- src/prefix_tree.hpp | 55 ---------------- src/sub.hpp | 4 +- src/trie.cpp | 180 ++++++++++++++++++++++++++++++++++++++++++++++++++++ src/trie.hpp | 58 +++++++++++++++++ 6 files changed, 242 insertions(+), 239 deletions(-) delete mode 100644 src/prefix_tree.cpp delete mode 100644 src/prefix_tree.hpp create mode 100644 src/trie.cpp create mode 100644 src/trie.hpp (limited to 'src') diff --git a/src/Makefile.am b/src/Makefile.am index f15814f..60c2584 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -89,7 +89,6 @@ libzmq_la_SOURCES = \ poll.hpp \ poller.hpp \ pair.hpp \ - prefix_tree.hpp \ pub.hpp \ pull.hpp \ push.hpp \ @@ -110,6 +109,7 @@ libzmq_la_SOURCES = \ tcp_socket.hpp \ thread.hpp \ transient_session.hpp \ + trie.hpp \ uuid.hpp \ windows.hpp \ wire.hpp \ @@ -146,7 +146,6 @@ libzmq_la_SOURCES = \ pgm_receiver.cpp \ pgm_sender.cpp \ pgm_socket.cpp \ - prefix_tree.cpp \ pipe.cpp \ poll.cpp \ pull.cpp \ @@ -167,6 +166,7 @@ libzmq_la_SOURCES = \ tcp_socket.cpp \ thread.cpp \ transient_session.cpp \ + trie.cpp \ uuid.cpp \ xrep.cpp \ xreq.cpp \ diff --git a/src/prefix_tree.cpp b/src/prefix_tree.cpp deleted file mode 100644 index 51225d6..0000000 --- a/src/prefix_tree.cpp +++ /dev/null @@ -1,180 +0,0 @@ -/* - Copyright (c) 2007-2010 iMatix Corporation - - This file is part of 0MQ. - - 0MQ is free software; you can redistribute it and/or modify it under - the terms of the Lesser GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - 0MQ 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 - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with this program. If not, see . -*/ - -#include - -#include -#include - -#include "platform.hpp" -#if defined ZMQ_HAVE_WINDOWS -#include "windows.hpp" -#endif - -#include "err.hpp" -#include "prefix_tree.hpp" - -zmq::prefix_tree_t::prefix_tree_t () : - refcnt (0), - min (0), - count (0) -{ -} - -zmq::prefix_tree_t::~prefix_tree_t () -{ - if (count == 1) - delete next.node; - else if (count > 1) { - for (unsigned char i = 0; i != count; ++i) - if (next.table [i]) - delete next.table [i]; - free (next.table); - } -} - -void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) -{ - // We are at the node corresponding to the prefix. We are done. - if (!size_) { - ++refcnt; - return; - } - - 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; - prefix_tree_t *oldp = next.node; - count = (min < c ? c - min : min - c) + 1; - next.table = (prefix_tree_t**) - malloc (sizeof (prefix_tree_t*) * count); - zmq_assert (next.table); - for (unsigned char 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 char old_count = count; - count = c - min + 1; - next.table = (prefix_tree_t**) realloc ((void*) next.table, - sizeof (prefix_tree_t*) * count); - zmq_assert (next.table); - for (unsigned char i = old_count; i != count; i++) - next.table [i] = NULL; - } - else { - - // The new character is below the current character range. - unsigned char old_count = count; - count = (min + old_count) - c; - next.table = (prefix_tree_t**) realloc ((void*) next.table, - sizeof (prefix_tree_t*) * count); - zmq_assert (next.table); - memmove (next.table + min - c, next.table, - old_count * sizeof (prefix_tree_t*)); - for (unsigned char 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) prefix_tree_t; - zmq_assert (next.node); - } - next.node->add (prefix_ + 1, size_ - 1); - } - else { - if (!next.table [c - min]) { - next.table [c - min] = new (std::nothrow) prefix_tree_t; - zmq_assert (next.table [c - min]); - } - next.table [c - min]->add (prefix_ + 1, size_ - 1); - } -} - -bool zmq::prefix_tree_t::rm (unsigned char *prefix_, size_t size_) -{ - if (!size_) { - if (!refcnt) - return false; - refcnt--; - return true; - } - - unsigned char c = *prefix_; - if (!count || c < min || c >= min + count) - return false; - - prefix_tree_t *next_node = - count == 1 ? next.node : next.table [c - min]; - - if (!next_node) - return false; - - return next_node->rm (prefix_ + 1, size_ - 1); -} - -bool zmq::prefix_tree_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. - prefix_tree_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_--; - } -} diff --git a/src/prefix_tree.hpp b/src/prefix_tree.hpp deleted file mode 100644 index 53c7c18..0000000 --- a/src/prefix_tree.hpp +++ /dev/null @@ -1,55 +0,0 @@ -/* - Copyright (c) 2007-2010 iMatix Corporation - - This file is part of 0MQ. - - 0MQ is free software; you can redistribute it and/or modify it under - the terms of the Lesser GNU General Public License as published by - the Free Software Foundation; either version 3 of the License, or - (at your option) any later version. - - 0MQ 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 - Lesser GNU General Public License for more details. - - You should have received a copy of the Lesser GNU General Public License - along with this program. If not, see . -*/ - -#ifndef __ZMQ_PREFIX_TREE_HPP_INCLUDED__ -#define __ZMQ_PREFIX_TREE_HPP_INCLUDED__ - -#include - -#include "stdint.hpp" - -namespace zmq -{ - - class prefix_tree_t - { - public: - - prefix_tree_t (); - ~prefix_tree_t (); - - void add (unsigned char *prefix_, size_t size_); - bool rm (unsigned char *prefix_, size_t size_); - bool check (unsigned char *data_, size_t size_); - - private: - - uint32_t refcnt; - unsigned char min; - unsigned char count; - union { - class prefix_tree_t *node; - class prefix_tree_t **table; - } next; - }; - -} - -#endif - diff --git a/src/sub.hpp b/src/sub.hpp index a832c48..659e04b 100644 --- a/src/sub.hpp +++ b/src/sub.hpp @@ -22,7 +22,7 @@ #include "../include/zmq.h" -#include "prefix_tree.hpp" +#include "trie.hpp" #include "socket_base.hpp" #include "i_terminate_events.hpp" #include "fq.hpp" @@ -61,7 +61,7 @@ namespace zmq fq_t fq; // The repository of subscriptions. - prefix_tree_t subscriptions; + trie_t subscriptions; // If true, 'message' contains a matching message to return on the // next recv call. diff --git a/src/trie.cpp b/src/trie.cpp new file mode 100644 index 0000000..369f72c --- /dev/null +++ b/src/trie.cpp @@ -0,0 +1,180 @@ +/* + Copyright (c) 2007-2010 iMatix Corporation + + This file is part of 0MQ. + + 0MQ is free software; you can redistribute it and/or modify it under + the terms of the Lesser GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 0MQ 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 + Lesser GNU General Public License for more details. + + You should have received a copy of the Lesser GNU General Public License + along with this program. If not, see . +*/ + +#include + +#include +#include + +#include "platform.hpp" +#if defined ZMQ_HAVE_WINDOWS +#include "windows.hpp" +#endif + +#include "err.hpp" +#include "trie.hpp" + +zmq::trie_t::trie_t () : + refcnt (0), + min (0), + count (0) +{ +} + +zmq::trie_t::~trie_t () +{ + if (count == 1) + delete next.node; + else if (count > 1) { + for (unsigned char i = 0; i != count; ++i) + if (next.table [i]) + delete next.table [i]; + free (next.table); + } +} + +void zmq::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; + } + + 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); + zmq_assert (next.table); + for (unsigned char 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 char old_count = count; + count = c - min + 1; + next.table = (trie_t**) realloc ((void*) next.table, + sizeof (trie_t*) * count); + zmq_assert (next.table); + for (unsigned char i = old_count; i != count; i++) + next.table [i] = NULL; + } + else { + + // The new character is below the current character range. + unsigned char old_count = count; + count = (min + old_count) - c; + next.table = (trie_t**) realloc ((void*) next.table, + sizeof (trie_t*) * count); + zmq_assert (next.table); + memmove (next.table + min - c, next.table, + old_count * sizeof (trie_t*)); + for (unsigned char 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; + zmq_assert (next.node); + } + next.node->add (prefix_ + 1, size_ - 1); + } + else { + if (!next.table [c - min]) { + next.table [c - min] = new (std::nothrow) trie_t; + zmq_assert (next.table [c - min]); + } + next.table [c - min]->add (prefix_ + 1, size_ - 1); + } +} + +bool zmq::trie_t::rm (unsigned char *prefix_, size_t size_) +{ + if (!size_) { + if (!refcnt) + return false; + refcnt--; + return true; + } + + 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; + + return next_node->rm (prefix_ + 1, size_ - 1); +} + +bool zmq::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_--; + } +} diff --git a/src/trie.hpp b/src/trie.hpp new file mode 100644 index 0000000..c085a41 --- /dev/null +++ b/src/trie.hpp @@ -0,0 +1,58 @@ +/* + Copyright (c) 2007-2010 iMatix Corporation + + This file is part of 0MQ. + + 0MQ is free software; you can redistribute it and/or modify it under + the terms of the Lesser GNU General Public License as published by + the Free Software Foundation; either version 3 of the License, or + (at your option) any later version. + + 0MQ 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 + Lesser GNU General Public License for more details. + + You should have received a copy of the Lesser GNU General Public License + along with this program. If not, see . +*/ + +#ifndef __ZMQ_TRIE_HPP_INCLUDED__ +#define __ZMQ_TRIE_HPP_INCLUDED__ + +#include + +#include "stdint.hpp" + +namespace zmq +{ + + class trie_t + { + public: + + trie_t (); + ~trie_t (); + + void add (unsigned char *prefix_, size_t size_); + bool rm (unsigned char *prefix_, size_t size_); + bool check (unsigned char *data_, size_t size_); + + private: + + uint32_t refcnt; + unsigned char min; + unsigned char count; + union { + class trie_t *node; + class trie_t **table; + } next; + + trie_t (const trie_t&); + void operator = (const trie_t&); + }; + +} + +#endif + -- cgit v1.2.3