From e170136a2e00eec2e786441cdc090c3b00a8fbd4 Mon Sep 17 00:00:00 2001 From: Martin Sustrik Date: Fri, 16 Sep 2011 16:34:28 +0200 Subject: More bugs in mtrie fixed Aside of fixing couple of corner cases this patch turns the 'match' function in mtrie from recursive to iterative. Signed-off-by: Martin Sustrik --- src/mtrie.cpp | 57 ++++++++++++++++++++++++++++++--------------------------- 1 file changed, 30 insertions(+), 27 deletions(-) (limited to 'src/mtrie.cpp') diff --git a/src/mtrie.cpp b/src/mtrie.cpp index bb20df8..edff336 100644 --- a/src/mtrie.cpp +++ b/src/mtrie.cpp @@ -209,33 +209,36 @@ bool zmq::mtrie_t::rm_helper (unsigned char *prefix_, size_t size_, void zmq::mtrie_t::match (unsigned char *data_, size_t size_, void (*func_) (pipe_t *pipe_, void *arg_), void *arg_) { - match_helper (data_, size_, func_, arg_); -} - -void zmq::mtrie_t::match_helper (unsigned char *data_, size_t size_, - void (*func_) (pipe_t *pipe_, void *arg_), void *arg_) -{ - // TODO: This function is on critical path. Rewrite it as iteration - // rather than recursion. - - // Signal the pipes attached to this node. - for (pipes_t::iterator it = pipes.begin (); it != pipes.end (); ++it) - func_ (*it, arg_); - - // If there are no subnodes in the trie, return. - if (count == 0) - return; - - // If there's one subnode (optimisation). - if (count == 1) { - if (min == data_ [0]) - next.node->match_helper (data_ + 1, size_ - 1, func_, arg_); - return; + mtrie_t *current = this; + while (size_) { + + // Signal the pipes attached to this node. + for (pipes_t::iterator it = current->pipes.begin (); + it != current->pipes.end (); ++it) + func_ (*it, arg_); + + // If there are no subnodes in the trie, return. + if (current->count == 0) + break; + + // If there's one subnode (optimisation). + if (current->count == 1) { + if (data_ [0] != current->min) + break; + current = current->next.node; + data_++; + size_--; + continue; + } + + // If there are multiple subnodes. + if (data_ [0] < min || data_ [0] >= min + count) + break; + if (!current->next.table [data_ [0] - min]) + break; + current = current->next.table [data_ [0] - min]; + data_++; + size_--; } - - // If there are multiple subnodes. - if (next.table [data_ [0] - min]) - next.table [data_ [0] - min]->match_helper (data_ + 1, size_ - 1, - func_, arg_); } -- cgit v1.2.3