summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/Makefile.am4
-rw-r--r--src/sub.hpp4
-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&);
};
}