diff options
| -rw-r--r-- | src/Makefile.am | 4 | ||||
| -rw-r--r-- | src/sub.hpp | 4 | ||||
| -rw-r--r-- | src/trie.cpp (renamed from src/prefix_tree.cpp) | 36 | ||||
| -rw-r--r-- | src/trie.hpp (renamed from src/prefix_tree.hpp) | 17 |
4 files changed, 32 insertions, 29 deletions
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/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/prefix_tree.cpp b/src/trie.cpp index 51225d6..369f72c 100644 --- a/src/prefix_tree.cpp +++ b/src/trie.cpp @@ -28,16 +28,16 @@ #endif #include "err.hpp" -#include "prefix_tree.hpp" +#include "trie.hpp" -zmq::prefix_tree_t::prefix_tree_t () : +zmq::trie_t::trie_t () : refcnt (0), min (0), count (0) { } -zmq::prefix_tree_t::~prefix_tree_t () +zmq::trie_t::~trie_t () { if (count == 1) delete next.node; @@ -49,7 +49,7 @@ zmq::prefix_tree_t::~prefix_tree_t () } } -void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) +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_) { @@ -69,10 +69,10 @@ void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) } else if (count == 1) { unsigned char oldc = min; - prefix_tree_t *oldp = next.node; + trie_t *oldp = next.node; count = (min < c ? c - min : min - c) + 1; - next.table = (prefix_tree_t**) - malloc (sizeof (prefix_tree_t*) * count); + 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; @@ -84,8 +84,8 @@ void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) // 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); + 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; @@ -95,11 +95,11 @@ void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) // 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); + 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 (prefix_tree_t*)); + old_count * sizeof (trie_t*)); for (unsigned char i = 0; i != min - c; i++) next.table [i] = NULL; min = c; @@ -109,21 +109,21 @@ void zmq::prefix_tree_t::add (unsigned char *prefix_, size_t size_) // If next node does not exist, create one. if (count == 1) { if (!next.node) { - next.node = new (std::nothrow) prefix_tree_t; + 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) prefix_tree_t; + 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::prefix_tree_t::rm (unsigned char *prefix_, size_t size_) +bool zmq::trie_t::rm (unsigned char *prefix_, size_t size_) { if (!size_) { if (!refcnt) @@ -136,7 +136,7 @@ bool zmq::prefix_tree_t::rm (unsigned char *prefix_, size_t size_) if (!count || c < min || c >= min + count) return false; - prefix_tree_t *next_node = + trie_t *next_node = count == 1 ? next.node : next.table [c - min]; if (!next_node) @@ -145,11 +145,11 @@ bool zmq::prefix_tree_t::rm (unsigned char *prefix_, size_t size_) return next_node->rm (prefix_ + 1, size_ - 1); } -bool zmq::prefix_tree_t::check (unsigned char *data_, size_t size_) +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. - prefix_tree_t *current = this; + trie_t *current = this; while (true) { // We've found a corresponding subscription! diff --git a/src/prefix_tree.hpp b/src/trie.hpp index 53c7c18..c085a41 100644 --- a/src/prefix_tree.hpp +++ b/src/trie.hpp @@ -17,8 +17,8 @@ along with this program. If not, see <http://www.gnu.org/licenses/>. */ -#ifndef __ZMQ_PREFIX_TREE_HPP_INCLUDED__ -#define __ZMQ_PREFIX_TREE_HPP_INCLUDED__ +#ifndef __ZMQ_TRIE_HPP_INCLUDED__ +#define __ZMQ_TRIE_HPP_INCLUDED__ #include <stddef.h> @@ -27,12 +27,12 @@ namespace zmq { - class prefix_tree_t + class trie_t { public: - prefix_tree_t (); - ~prefix_tree_t (); + trie_t (); + ~trie_t (); void add (unsigned char *prefix_, size_t size_); bool rm (unsigned char *prefix_, size_t size_); @@ -44,9 +44,12 @@ namespace zmq unsigned char min; unsigned char count; union { - class prefix_tree_t *node; - class prefix_tree_t **table; + class trie_t *node; + class trie_t **table; } next; + + trie_t (const trie_t&); + void operator = (const trie_t&); }; } |