QPID-4048 - Rafactor of TopicExchange to isolate the binding-key data structure.

git-svn-id: https://svn.apache.org/repos/asf/qpid/trunk@1348233 13f79535-47bb-0310-9956-ffa450edef68

5 files changed, 408 insertions, 473 deletions

diff --git a/qpid/cpp/src/Makefile.am b/qpid/cpp/src/Makefile.am
index d021843f16..c17dc8227b 100644
--- a/qpid/cpp/src/Makefile.am
+++ b/qpid/cpp/src/Makefile.am
@@ -683,6 +683,7 @@ libqpidbroker_la_SOURCES = \
   qpid/broker/ThresholdAlerts.h \
   qpid/broker/TopicExchange.cpp \
   qpid/broker/TopicExchange.h \
+  qpid/broker/TopicKeyNode.h \
   qpid/broker/TransactionalStore.h \
   qpid/broker/TxAccept.cpp \
   qpid/broker/TxAccept.h \
diff --git a/qpid/cpp/src/qpid/broker/TopicExchange.cpp b/qpid/cpp/src/qpid/broker/TopicExchange.cpp
index dd3ec13019..c11389bb17 100644
--- a/qpid/cpp/src/qpid/broker/TopicExchange.cpp
+++ b/qpid/cpp/src/qpid/broker/TopicExchange.cpp
@@ -32,20 +32,8 @@ using namespace qpid::sys;
 using namespace std;
 namespace _qmf = qmf::org::apache::qpid::broker;
 
-
-// TODO aconway 2006-09-20: More efficient matching algorithm.
-// Areas for improvement:
-// - excessive string copying: should be 0 copy, match from original buffer.
-// - match/lookup: use descision tree or other more efficient structure.
-
-namespace 
-{
-const std::string STAR("*");
-const std::string HASH("#");
-}
-
 // iterator for federation ReOrigin bind operation
-class TopicExchange::ReOriginIter : public TopicExchange::BindingNode::TreeIterator {
+class TopicExchange::ReOriginIter : public BindingNode::TreeIterator {
 public:
     ReOriginIter() {};
     ~ReOriginIter() {};
@@ -61,7 +49,7 @@ public:
 
 // match iterator used by route(): builds BindingList of all unique queues
 // that match the routing key.
-class TopicExchange::BindingsFinderIter : public TopicExchange::BindingNode::TreeIterator {
+class TopicExchange::BindingsFinderIter : public BindingNode::TreeIterator {
 public:
     BindingsFinderIter(BindingList &bl) : b(bl) {};
     ~BindingsFinderIter() {};
@@ -85,7 +73,7 @@ public:
 
 
 // Iterator to visit all bindings until a given queue is found
-class TopicExchange::QueueFinderIter : public TopicExchange::BindingNode::TreeIterator {
+class TopicExchange::QueueFinderIter : public BindingNode::TreeIterator {
 public:
     QueueFinderIter(Queue::shared_ptr queue) : queue(queue), found(false) {};
     ~QueueFinderIter() {};
@@ -107,58 +95,7 @@ public:
 };
 
 
-// Iterate over a string of '.'-separated tokens.
-struct TopicExchange::TokenIterator {
-    typedef pair<const char*,const char*> Token;
-    
-    TokenIterator(const char* b, const char* e) : end(e), token(make_pair(b, find(b,e,'.'))) {}
-
-    TokenIterator(const string& key) : end(&key[0]+key.size()), token(make_pair(&key[0], find(&key[0],end,'.'))) {}
-
-    bool finished() const { return !token.first; }
-
-    void next() {
-        if (token.second == end)
-            token.first = token.second = 0;
-        else {
-            token.first=token.second+1;
-            token.second=(find(token.first, end, '.'));
-        }
-    }
-
-    void pop(string &top) {
-        ptrdiff_t l = len();
-        if (l) {
-            top.assign(token.first, l);
-        } else top.clear();
-        next();
-    }
-
-    bool match1(char c) const {
-        return token.second==token.first+1 && *token.first == c;
-    }
-
-    bool match(const Token& token2) const {
-        ptrdiff_t l=len();
-        return l == token2.second-token2.first &&
-            strncmp(token.first, token2.first, l) == 0;
-    }
-
-    bool match(const string& str) const {
-        ptrdiff_t l=len();
-        return l == ptrdiff_t(str.size()) &&
-          str.compare(0, l, token.first, l) == 0;
-    }
-
-    ptrdiff_t len() const { return token.second - token.first; }
-
-
-    const char* end;
-    Token token;
-};
-
-
-class TopicExchange::Normalizer : public TopicExchange::TokenIterator {
+class TopicExchange::Normalizer : public TokenIterator {
   public:
     Normalizer(string& p)
         : TokenIterator(&p[0], &p[0]+p.size()), pattern(p)
@@ -230,7 +167,7 @@ bool TopicExchange::bind(Queue::shared_ptr queue, const string& routingKey, cons
 
     if (args == 0 || fedOp.empty() || fedOp == fedOpBind) {
         RWlock::ScopedWlock l(lock);
-        BindingKey *bk = bindingTree.addBindingKey(routingPattern);
+        BindingKey *bk = bindingTree.add(routingPattern);
         if (bk) {
             Binding::vector& qv(bk->bindingVector);
             Binding::vector::iterator q;
@@ -324,7 +261,7 @@ bool TopicExchange::deleteBinding(Queue::shared_ptr queue,
     nBindings--;
 
     if(qv.empty()) {
-        bindingTree.removeBindingKey(routingKey);
+        bindingTree.remove(routingKey);
     }
     if (mgmtExchange != 0) {
         mgmtExchange->dec_bindingCount();
@@ -340,7 +277,7 @@ bool TopicExchange::deleteBinding(Queue::shared_ptr queue,
 TopicExchange::BindingKey *TopicExchange::getQueueBinding(Queue::shared_ptr queue, const string& pattern)
 {
     // Note well: lock held by caller....
-    BindingKey *bk = bindingTree.getBindingKey(pattern);  // Exact match against binding pattern
+    BindingKey *bk = bindingTree.get(pattern);  // Exact match against binding pattern
     if (!bk) return 0;
     Binding::vector& qv(bk->bindingVector);
     Binding::vector::iterator q;
@@ -385,7 +322,7 @@ bool TopicExchange::isBound(Queue::shared_ptr queue, const string* const routing
     } else if (!routingKey && !queue) {
         return nBindings > 0;
     } else if (routingKey) {
-        if (bindingTree.getBindingKey(*routingKey)) {
+        if (bindingTree.get(*routingKey)) {
             return true;
         }
     } else {
@@ -400,294 +337,4 @@ TopicExchange::~TopicExchange() {}
 
 const std::string TopicExchange::typeName("topic");
 
-//
-// class BindingNode
-//
-
-TopicExchange::BindingNode::~BindingNode()
-{
-    childTokens.clear();
-}
-
-
-// Add a binding pattern to the tree.  Return a pointer to the binding key
-// of the node that matches the binding pattern.
-TopicExchange::BindingKey*
-TopicExchange::BindingNode::addBindingKey(const std::string& normalizedRoute)
-{
-    TokenIterator bKey(normalizedRoute);
-    return addBindingKey(bKey, normalizedRoute);
-}
-
-
-// Return a pointer to the binding key of the leaf node that matches the binding pattern.
-TopicExchange::BindingKey*
-TopicExchange::BindingNode::getBindingKey(const std::string& normalizedRoute)
-{
-    TokenIterator bKey(normalizedRoute);
-    return getBindingKey(bKey);
-}
-
-
-// Delete the binding associated with the given route.
-void TopicExchange::BindingNode::removeBindingKey(const std::string& normalizedRoute)
-{
-    TokenIterator bKey2(normalizedRoute);
-    removeBindingKey(bKey2, normalizedRoute);
-}
-
-// visit each node in the tree.  Note: all nodes are visited,
-// even non-leaf nodes (i.e. nodes without any bindings)
-bool TopicExchange::BindingNode::iterateAll(TopicExchange::BindingNode::TreeIterator& iter)
-{
-    if (!iter.visit(*this)) return false;
-
-    if (starChild && !starChild->iterateAll(iter)) return false;
-
-    if (hashChild && !hashChild->iterateAll(iter)) return false;
-
-    for (ChildMap::iterator ptr = childTokens.begin();
-         ptr != childTokens.end(); ptr++) {
-
-        if (!ptr->second->iterateAll(iter)) return false;
-    }
-
-    return true;
-}
-
-// applies iter against only matching nodes until iter returns false
-// Note Well: the iter may match against the same node more than once
-// if # wildcards are present!
-bool TopicExchange::BindingNode::iterateMatch(const std::string& routingKey, TreeIterator& iter)
-{
-    TopicExchange::TokenIterator rKey(routingKey);
-    return iterateMatch( rKey, iter );
-}
-
-
-// recurse over binding using token iterator.
-// Note well: bkey is modified!
-TopicExchange::BindingKey*
-TopicExchange::BindingNode::addBindingKey(TokenIterator &bKey,
-                                          const string& fullPattern)
-{
-    if (bKey.finished()) {
-        // this node's binding
-        if (routePattern.empty()) {
-            routePattern = fullPattern;
-        } else assert(routePattern == fullPattern);
-
-        return &bindings;
-
-    } else {
-        // pop the topmost token & recurse...
-
-        if (bKey.match(STAR)) {
-            if (!starChild) {
-                starChild.reset(new StarNode());
-            }
-            bKey.next();
-            return starChild->addBindingKey(bKey, fullPattern);
-
-        } else if (bKey.match(HASH)) {
-            if (!hashChild) {
-                hashChild.reset(new HashNode());
-            }
-            bKey.next();
-            return hashChild->addBindingKey(bKey, fullPattern);
-
-        } else {
-            ChildMap::iterator ptr;
-            std::string next_token;
-            bKey.pop(next_token);
-            ptr = childTokens.find(next_token);
-            if (ptr != childTokens.end()) {
-                return ptr->second->addBindingKey(bKey, fullPattern);
-            } else {
-                BindingNode::shared_ptr child(new BindingNode(next_token));
-                childTokens[next_token] = child;
-                return child->addBindingKey(bKey, fullPattern);
-            }
-        }
-    }
-}
-
-
-// Remove a binding pattern from the tree.  Return true if the current
-// node becomes a leaf without any bindings (therefore can be deleted).
-// Note Well: modifies parameter bKey's value!
-bool
-TopicExchange::BindingNode::removeBindingKey(TokenIterator &bKey,
-                                             const string& fullPattern)
-{
-    bool remove;
-
-    if (!bKey.finished()) {
-
-        if (bKey.match(STAR)) {
-            bKey.next();
-            if (starChild) {
-                remove = starChild->removeBindingKey(bKey, fullPattern);
-                if (remove) {
-                    starChild.reset();
-                }
-            }
-        } else if (bKey.match(HASH)) {
-            bKey.next();
-            if (hashChild) {
-                remove = hashChild->removeBindingKey(bKey, fullPattern);
-                if (remove) {
-                    hashChild.reset();
-                }
-            }
-        } else {
-            ChildMap::iterator ptr;
-            std::string next_token;
-            bKey.pop(next_token);
-            ptr = childTokens.find(next_token);
-            if (ptr != childTokens.end()) {
-                remove = ptr->second->removeBindingKey(bKey, fullPattern);
-                if (remove) {
-                    childTokens.erase(ptr);
-                }
-            }
-        }
-    }
-
-    // no bindings and no children == parent can delete this node.
-    return getChildCount() == 0 && bindings.bindingVector.empty();
-}
-
-
-// find the binding key that matches the given binding pattern.
-// Note Well: modifies key parameter!
-TopicExchange::BindingKey*
-TopicExchange::BindingNode::getBindingKey(TokenIterator &key)
-{
-    if (key.finished()) {
-        return &bindings;
-    }
-
-    string next_token;
-
-    key.pop(next_token);
-
-    if (next_token == STAR) {
-        if (starChild)
-            return starChild->getBindingKey(key);
-    } else if (next_token == HASH) {
-        if (hashChild)
-            return hashChild->getBindingKey(key);
-    } else {
-        ChildMap::iterator ptr;
-        ptr = childTokens.find(next_token);
-        if (ptr != childTokens.end()) {
-            return ptr->second->getBindingKey(key);
-        }
-    }
-
-    return 0;
-}
-
-
-
-// iterate over all nodes that match the given key.  Note well: the set of nodes
-// that are visited includes matching non-leaf nodes.
-// Note well: parameter key is modified!
-bool TopicExchange::BindingNode::iterateMatch(TokenIterator& key, TreeIterator& iter)
-{
-    // invariant: key has matched all previous tokens up to this node.
-    if (key.finished()) {
-        // exact match this node:  visit if bound
-        if (!bindings.bindingVector.empty())
-            if (!iter.visit(*this)) return false;
-    }
-
-    // check remaining key against children, even if empty.
-    return iterateMatchChildren(key, iter);
-}
-
-
-TopicExchange::StarNode::StarNode()
-    : BindingNode(STAR) {}
-
-
-// See iterateMatch() above.
-// Special case: this node must verify a token is available (match exactly one).
-bool TopicExchange::StarNode::iterateMatch(TokenIterator& key, TreeIterator& iter)
-{
-    // must match one token:
-    if (key.finished())
-        return true;    // match failed, but continue iteration on siblings
-
-    // pop the topmost token
-    key.next();
-
-    if (key.finished()) {
-        // exact match this node:  visit if bound
-        if (!bindings.bindingVector.empty())
-            if (!iter.visit(*this)) return false;
-    }
-
-    return iterateMatchChildren(key, iter);
-}
-
-
-TopicExchange::HashNode::HashNode()
-    : BindingNode(HASH) {}
-
-
-// See iterateMatch() above.
-// Special case: can match zero or more tokens at the head of the key.
-bool TopicExchange::HashNode::iterateMatch(TokenIterator& key, TreeIterator& iter)
-{
-    // consume each token and look for a match on the
-    // remaining key.
-    while (!key.finished()) {
-        if (!iterateMatchChildren(key, iter)) return false;
-        key.next();
-    }
-
-    if (!bindings.bindingVector.empty())
-        return iter.visit(*this);
-
-    return true;
-}
-
-
-// helper: iterate over current node's matching children
-bool
-TopicExchange::BindingNode::iterateMatchChildren(const TopicExchange::TokenIterator& key,
-                                                 TopicExchange::BindingNode::TreeIterator& iter)
-{
-    // always try glob - it can match empty keys
-    if (hashChild) {
-        TokenIterator tmp(key);
-        if (!hashChild->iterateMatch(tmp, iter))
-            return false;
-    }
-
-    if (!key.finished()) {
-
-        if (starChild) {
-            TokenIterator tmp(key);
-            if (!starChild->iterateMatch(tmp, iter))
-                return false;
-        }
-
-        if (!childTokens.empty()) {
-            TokenIterator newKey(key);
-            std::string next_token;
-            newKey.pop(next_token);
-
-            ChildMap::iterator ptr = childTokens.find(next_token);
-            if (ptr != childTokens.end()) {
-                return ptr->second->iterateMatch(newKey, iter);
-            }
-        }
-    }
-
-    return true;
-}
-
 }} // namespace qpid::broker
diff --git a/qpid/cpp/src/qpid/broker/TopicExchange.h b/qpid/cpp/src/qpid/broker/TopicExchange.h
index cc24e1411e..46871a1c6b 100644
--- a/qpid/cpp/src/qpid/broker/TopicExchange.h
+++ b/qpid/cpp/src/qpid/broker/TopicExchange.h
@@ -28,6 +28,7 @@
 #include "qpid/framing/FieldTable.h"
 #include "qpid/sys/Monitor.h"
 #include "qpid/broker/Queue.h"
+#include "qpid/broker/TopicKeyNode.h"
 
 
 namespace qpid {
@@ -35,7 +36,6 @@ namespace broker {
 
 class TopicExchange : public virtual Exchange {
 
-    struct TokenIterator;
     class Normalizer;
 
     struct BindingKey {        // binding for this node
@@ -43,129 +43,44 @@ class TopicExchange : public virtual Exchange {
         FedBinding fedBinding;
     };
 
-    // Binding database:
-    // The dotted form of a binding key is broken up and stored in a directed tree graph.
-    // Common binding prefix are merged.  This allows the route match alogrithm to quickly
-    // isolate those sub-trees that match a given routingKey.
-    // For example, given the routes:
-    //     a.b.c.<...>
-    //     a.b.d.<...>
-    //     a.x.y.<...>
-    // The resulting tree would be:
-    //    a-->b-->c-->...
-    //    |   +-->d-->...
-    //    +-->x-->y-->...
-    //
-    class QPID_BROKER_CLASS_EXTERN BindingNode {
-    public:
-
-        typedef boost::shared_ptr<BindingNode> shared_ptr;
-
-        // for database transversal (visit a node).
-        class TreeIterator {
-        public:
-            TreeIterator() {};
-            virtual ~TreeIterator() {};
-            virtual bool visit(BindingNode& node) = 0;
-        };
-
-        BindingNode() {};
-        BindingNode(const std::string& token) : token(token) {};
-        QPID_BROKER_EXTERN virtual ~BindingNode();
-
-        // add normalizedRoute to tree, return associated BindingKey
-        QPID_BROKER_EXTERN BindingKey* addBindingKey(const std::string& normalizedRoute);
-
-        // return BindingKey associated with normalizedRoute
-        QPID_BROKER_EXTERN BindingKey* getBindingKey(const std::string& normalizedRoute);
-
-        // remove BindingKey associated with normalizedRoute
-        QPID_BROKER_EXTERN void removeBindingKey(const std::string& normalizedRoute);
-
-        // applies iter against each node in tree until iter returns false
-        QPID_BROKER_EXTERN bool iterateAll(TreeIterator& iter);
-
-        // applies iter against only matching nodes until iter returns false
-        QPID_BROKER_EXTERN bool iterateMatch(const std::string& routingKey, TreeIterator& iter);
-
-        std::string routePattern;  // normalized binding that matches this node
-        BindingKey bindings;  // for matches against this node
-
-  protected:
-
-        std::string token;         // portion of pattern represented by this node
-
-        // children
-        typedef std::map<const std::string, BindingNode::shared_ptr> ChildMap;
-        ChildMap childTokens;
-        BindingNode::shared_ptr starChild;  // "*" subtree
-        BindingNode::shared_ptr hashChild;  // "#" subtree
-
-        unsigned int getChildCount() { return childTokens.size() +
-              (starChild ? 1 : 0) + (hashChild ? 1 : 0); }
-        BindingKey* addBindingKey(TokenIterator& bKey,
-                                  const std::string& fullPattern);
-        bool removeBindingKey(TokenIterator& bKey,
-                              const std::string& fullPattern);
-        BindingKey* getBindingKey(TokenIterator& bKey);
-        QPID_BROKER_EXTERN virtual bool iterateMatch(TokenIterator& rKey, TreeIterator& iter);
-        bool iterateMatchChildren(const TokenIterator& key, TreeIterator& iter);
-    };
-
-    // Special case: ("*" token) Node in the tree for a match exactly one wildcard
-    class StarNode : public BindingNode {
-    public:
-        StarNode();
-        ~StarNode() {};
-
-    protected:
-        virtual bool iterateMatch(TokenIterator& key, TreeIterator& iter);
-    };
+    typedef TopicKeyNode<BindingKey> BindingNode;
 
-    // Special case: ("#" token) Node in the tree for a match zero or more
-    class HashNode : public BindingNode {
-    public:
-        HashNode();
-        ~HashNode() {};
+    BindingKey *getQueueBinding(Queue::shared_ptr queue, const std::string& pattern);
+    bool deleteBinding(Queue::shared_ptr queue,
+                       const std::string& routingKey,
+                       BindingKey *bk);
 
-    protected:
-        virtual bool iterateMatch(TokenIterator& key, TreeIterator& iter);
-    };
+    class ReOriginIter;
+    class BindingsFinderIter;
+    class QueueFinderIter;
 
     BindingNode bindingTree;
     unsigned long nBindings;
     qpid::sys::RWlock lock;     // protects bindingTree and nBindings
     qpid::sys::RWlock cacheLock;     // protects cache
     std::map<std::string, BindingList> bindingCache; // cache of matched routes.
+
     class ClearCache {
     private:
         qpid::sys::RWlock* cacheLock;
         std::map<std::string, BindingList>* bindingCache;
-	bool cleared; 
+        bool cleared; 
     public:
-        ClearCache(qpid::sys::RWlock* l, std::map<std::string, BindingList>* bc): cacheLock(l),
-             bindingCache(bc),cleared(false) {};
+        ClearCache(qpid::sys::RWlock* l, std::map<std::string, BindingList>* bc) :
+            cacheLock(l), bindingCache(bc),cleared(false) {};
         void clearCache() {
-             qpid::sys::RWlock::ScopedWlock l(*cacheLock);
-             if (!cleared) {
-                 bindingCache->clear();
-                 cleared =true;
-             }
+            qpid::sys::RWlock::ScopedWlock l(*cacheLock);
+            if (!cleared) {
+                bindingCache->clear();
+                cleared =true;
+            }
         };
         ~ClearCache(){ 
-	     clearCache();
+            clearCache();
         };
     };
-    BindingKey *getQueueBinding(Queue::shared_ptr queue, const std::string& pattern);
-    bool deleteBinding(Queue::shared_ptr queue,
-                       const std::string& routingKey,
-                       BindingKey *bk);
 
-    class ReOriginIter;
-    class BindingsFinderIter;
-    class QueueFinderIter;
-
-  public:
+public:
     static const std::string typeName;
 
     static QPID_BROKER_EXTERN std::string normalize(const std::string& pattern);
@@ -199,7 +114,6 @@ class TopicExchange : public virtual Exchange {
 };
 
 
-
 }
 }
 
diff --git a/qpid/cpp/src/qpid/broker/TopicKeyNode.h b/qpid/cpp/src/qpid/broker/TopicKeyNode.h
new file mode 100644
index 0000000000..de54e2d636
--- /dev/null
+++ b/qpid/cpp/src/qpid/broker/TopicKeyNode.h
@@ -0,0 +1,371 @@
+/*
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ *
+ */
+#ifndef _QPID_BROKER_TOPIC_KEY_NODE_
+#define _QPID_BROKER_TOPIC_KEY_NODE_
+
+#include "qpid/broker/BrokerImportExport.h"
+#include <boost/shared_ptr.hpp>
+#include <map>
+#include <string>
+#include <string.h>
+
+
+namespace qpid {
+namespace broker {
+
+static const std::string STAR("*");
+static const std::string HASH("#");
+
+
+// Iterate over a string of '.'-separated tokens.
+struct TokenIterator {
+    typedef std::pair<const char*,const char*> Token;
+    
+    TokenIterator(const char* b, const char* e) : end(e), token(std::make_pair(b, std::find(b,e,'.'))) {}
+
+    TokenIterator(const std::string& key) : end(&key[0]+key.size()), token(std::make_pair(&key[0], std::find(&key[0],end,'.'))) {}
+
+    bool finished() const { return !token.first; }
+
+    void next() {
+        if (token.second == end)
+            token.first = token.second = 0;
+        else {
+            token.first=token.second+1;
+            token.second=(std::find(token.first, end, '.'));
+        }
+    }
+
+    void pop(std::string &top) {
+        ptrdiff_t l = len();
+        if (l) {
+            top.assign(token.first, l);
+        } else top.clear();
+        next();
+    }
+
+    bool match1(char c) const {
+        return token.second==token.first+1 && *token.first == c;
+    }
+
+    bool match(const Token& token2) const {
+        ptrdiff_t l=len();
+        return l == token2.second-token2.first &&
+            strncmp(token.first, token2.first, l) == 0;
+    }
+
+    bool match(const std::string& str) const {
+        ptrdiff_t l=len();
+        return l == ptrdiff_t(str.size()) &&
+          str.compare(0, l, token.first, l) == 0;
+    }
+
+    ptrdiff_t len() const { return token.second - token.first; }
+
+
+    const char* end;
+    Token token;
+};
+
+    
+// Binding database:
+// The dotted form of a binding key is broken up and stored in a directed tree graph.
+// Common binding prefix are merged.  This allows the route match alogrithm to quickly
+// isolate those sub-trees that match a given routingKey.
+// For example, given the routes:
+//     a.b.c.<...>
+//     a.b.d.<...>
+//     a.x.y.<...>
+// The resulting tree would be:
+//    a-->b-->c-->...
+//    |   +-->d-->...
+//    +-->x-->y-->...
+//
+template <class T>
+class QPID_BROKER_CLASS_EXTERN TopicKeyNode {
+
+ public:
+
+    typedef boost::shared_ptr<TopicKeyNode> shared_ptr;
+
+    // for database transversal (visit a node).
+    class TreeIterator {
+    public:
+        TreeIterator() {};
+        virtual ~TreeIterator() {};
+        virtual bool visit(TopicKeyNode& node) = 0;
+    };
+
+    TopicKeyNode() : isStar(false), isHash(false) {}
+    TopicKeyNode(const std::string& _t) : token(_t), isStar(_t == STAR), isHash(_t == HASH) {}
+    QPID_BROKER_EXTERN virtual ~TopicKeyNode() {
+        childTokens.clear();
+    }
+
+    // add normalizedRoute to tree, return associated T
+    QPID_BROKER_EXTERN T* add(const std::string& normalizedRoute) {
+        TokenIterator bKey(normalizedRoute);
+        return add(bKey, normalizedRoute);
+    }
+
+    // return T associated with normalizedRoute
+    QPID_BROKER_EXTERN T* get(const std::string& normalizedRoute) {
+        TokenIterator bKey(normalizedRoute);
+        return get(bKey);
+    }
+
+    // remove T associated with normalizedRoute
+    QPID_BROKER_EXTERN void remove(const std::string& normalizedRoute) {
+        TokenIterator bKey2(normalizedRoute);
+        remove(bKey2, normalizedRoute);
+    }
+
+    // applies iter against each node in tree until iter returns false
+    QPID_BROKER_EXTERN bool iterateAll(TreeIterator& iter) {
+        if (!iter.visit(*this)) return false;
+        if (starChild && !starChild->iterateAll(iter)) return false;
+        if (hashChild && !hashChild->iterateAll(iter)) return false;
+        for (typename ChildMap::iterator ptr = childTokens.begin();
+             ptr != childTokens.end(); ptr++) {
+            if (!ptr->second->iterateAll(iter)) return false;
+        }
+        return true;
+    }
+
+    // applies iter against only matching nodes until iter returns false
+    QPID_BROKER_EXTERN bool iterateMatch(const std::string& routingKey, TreeIterator& iter) {
+        TokenIterator rKey(routingKey);
+        return iterateMatch( rKey, iter );
+    }
+
+    std::string routePattern;  // normalized binding that matches this node
+    T bindings;  // for matches against this node
+
+ private:
+
+    std::string token;         // portion of pattern represented by this node
+    bool isStar;
+    bool isHash;
+
+    // children
+    typedef std::map<const std::string, TopicKeyNode::shared_ptr> ChildMap;
+    ChildMap childTokens;
+    TopicKeyNode::shared_ptr starChild;  // "*" subtree
+    TopicKeyNode::shared_ptr hashChild;  // "#" subtree
+
+    unsigned int getChildCount() { return childTokens.size() +
+            (starChild ? 1 : 0) + (hashChild ? 1 : 0); }
+
+    T* add(TokenIterator& bKey, const std::string& fullPattern){
+        if (bKey.finished()) {
+            // this node's binding
+            if (routePattern.empty()) {
+                routePattern = fullPattern;
+            } else assert(routePattern == fullPattern);
+
+            return &bindings;
+
+        } else {
+            // pop the topmost token & recurse...
+
+            if (bKey.match(STAR)) {
+                if (!starChild) {
+                    starChild.reset(new TopicKeyNode<T>(STAR));
+                }
+                bKey.next();
+                return starChild->add(bKey, fullPattern);
+
+            } else if (bKey.match(HASH)) {
+                if (!hashChild) {
+                    hashChild.reset(new TopicKeyNode<T>(HASH));
+                }
+                bKey.next();
+                return hashChild->add(bKey, fullPattern);
+
+            } else {
+                typename ChildMap::iterator ptr;
+                std::string next_token;
+                bKey.pop(next_token);
+                ptr = childTokens.find(next_token);
+                if (ptr != childTokens.end()) {
+                    return ptr->second->add(bKey, fullPattern);
+                } else {
+                    TopicKeyNode::shared_ptr child(new TopicKeyNode<T>(next_token));
+                    childTokens[next_token] = child;
+                    return child->add(bKey, fullPattern);
+                }
+            }
+        }
+    }
+
+
+    bool remove(TokenIterator& bKey, const std::string& fullPattern) {
+        bool remove;
+        if (!bKey.finished()) {
+            if (bKey.match(STAR)) {
+                bKey.next();
+                if (starChild) {
+                    remove = starChild->remove(bKey, fullPattern);
+                    if (remove) {
+                        starChild.reset();
+                    }
+                }
+            } else if (bKey.match(HASH)) {
+                bKey.next();
+                if (hashChild) {
+                    remove = hashChild->remove(bKey, fullPattern);
+                    if (remove) {
+                        hashChild.reset();
+                    }
+                }
+            } else {
+                typename ChildMap::iterator ptr;
+                std::string next_token;
+                bKey.pop(next_token);
+                ptr = childTokens.find(next_token);
+                if (ptr != childTokens.end()) {
+                    remove = ptr->second->remove(bKey, fullPattern);
+                    if (remove) {
+                        childTokens.erase(ptr);
+                    }
+                }
+            }
+        }
+
+        // no bindings and no children == parent can delete this node.
+        return getChildCount() == 0 && bindings.bindingVector.empty();
+    }
+
+
+    T* get(TokenIterator& bKey) {
+        if (bKey.finished()) {
+            return &bindings;
+        }
+
+        std::string next_token;
+        bKey.pop(next_token);
+
+        if (next_token == STAR) {
+            if (starChild)
+                return starChild->get(bKey);
+        } else if (next_token == HASH) {
+            if (hashChild)
+                return hashChild->get(bKey);
+        } else {
+            typename ChildMap::iterator ptr;
+            ptr = childTokens.find(next_token);
+            if (ptr != childTokens.end()) {
+                return ptr->second->get(bKey);
+            }
+        }
+
+        return 0;
+    }
+
+
+    bool iterateMatch(TokenIterator& rKey, TreeIterator& iter) {
+        if (isStar) return iterateMatchStar(rKey, iter);
+        if (isHash) return iterateMatchHash(rKey, iter);
+        return iterateMatchString(rKey, iter);
+    }
+
+
+    bool iterateMatchString(TokenIterator& rKey, TreeIterator& iter){
+        // invariant: key has matched all previous tokens up to this node.
+        if (rKey.finished()) {
+            // exact match this node:  visit if bound
+            if (!bindings.bindingVector.empty())
+                if (!iter.visit(*this)) return false;
+        }
+
+        // check remaining key against children, even if empty.
+        return iterateMatchChildren(rKey, iter);
+    }
+
+
+    bool iterateMatchStar(TokenIterator& rKey, TreeIterator& iter) {
+        // must match one token:
+        if (rKey.finished())
+            return true;    // match failed, but continue iteration on siblings
+
+        // pop the topmost token
+        rKey.next();
+
+        if (rKey.finished()) {
+            // exact match this node:  visit if bound
+            if (!bindings.bindingVector.empty())
+                if (!iter.visit(*this)) return false;
+        }
+
+        return iterateMatchChildren(rKey, iter);
+    }
+
+
+    bool iterateMatchHash(TokenIterator& rKey, TreeIterator& iter) {
+        // consume each token and look for a match on the
+        // remaining key.
+        while (!rKey.finished()) {
+            if (!iterateMatchChildren(rKey, iter)) return false;
+            rKey.next();
+        }
+
+        if (!bindings.bindingVector.empty())
+            return iter.visit(*this);
+
+        return true;
+    }
+
+
+    bool iterateMatchChildren(const TokenIterator& key, TreeIterator& iter) {
+        // always try glob - it can match empty keys
+        if (hashChild) {
+            TokenIterator tmp(key);
+            if (!hashChild->iterateMatch(tmp, iter))
+                return false;
+        }
+
+        if (!key.finished()) {
+            if (starChild) {
+                TokenIterator tmp(key);
+                if (!starChild->iterateMatch(tmp, iter))
+                    return false;
+            }
+
+            if (!childTokens.empty()) {
+                TokenIterator newKey(key);
+                std::string next_token;
+                newKey.pop(next_token);
+
+                typename ChildMap::iterator ptr = childTokens.find(next_token);
+                if (ptr != childTokens.end()) {
+                    return ptr->second->iterateMatch(newKey, iter);
+                }
+            }
+        }
+
+        return true;
+    }
+};
+
+}
+}
+
+#endif
diff --git a/qpid/cpp/src/tests/TopicExchangeTest.cpp b/qpid/cpp/src/tests/TopicExchangeTest.cpp
index ff8931f9c9..d57951ea3f 100644
--- a/qpid/cpp/src/tests/TopicExchangeTest.cpp
+++ b/qpid/cpp/src/tests/TopicExchangeTest.cpp
@@ -16,6 +16,7 @@
  * specific language governing permissions and limitations
  * under the License.
  */
+#include "qpid/broker/TopicKeyNode.h"
 #include "qpid/broker/TopicExchange.h"
 #include "unit_test.h"
 #include "test_tools.h"
@@ -32,14 +33,15 @@ class TopicExchange::TopicExchangeTester {
 
 public:
     typedef std::vector<std::string> BindingVec;
+    typedef TopicKeyNode<TopicExchange::BindingKey> TestBindingNode;
 
 private:
     // binding node iterator that collects all routes that are bound
-    class TestFinder : public TopicExchange::BindingNode::TreeIterator {
+    class TestFinder : public TestBindingNode::TreeIterator {
     public:
         TestFinder(BindingVec& m) : bv(m) {};
         ~TestFinder() {};
-        bool visit(BindingNode& node) {
+        bool visit(TestBindingNode& node) {
             if (!node.bindings.bindingVector.empty())
                 bv.push_back(node.routePattern);
             return true;
@@ -53,7 +55,7 @@ public:
     ~TopicExchangeTester() {};
     bool addBindingKey(const std::string& bKey) {
         string routingPattern = normalize(bKey);
-        BindingKey *bk = bindingTree.addBindingKey(routingPattern);
+        BindingKey *bk = bindingTree.add(routingPattern);
         if (bk) {
             // push a dummy binding to mark this node as "non-leaf"
             bk->bindingVector.push_back(Binding::shared_ptr());
@@ -64,12 +66,12 @@ public:
 
     bool removeBindingKey(const std::string& bKey){
         string routingPattern = normalize(bKey);
-        BindingKey *bk = bindingTree.getBindingKey(routingPattern);
+        BindingKey *bk = bindingTree.get(routingPattern);
         if (bk) {
             bk->bindingVector.pop_back();
             if (bk->bindingVector.empty()) {
                 // no more bindings - remove this node
-                bindingTree.removeBindingKey(routingPattern);
+                bindingTree.remove(routingPattern);
             }
             return true;
         }
@@ -87,7 +89,7 @@ public:
     }
 
 private:
-    TopicExchange::BindingNode bindingTree;
+    TestBindingNode bindingTree;
 };
 } // namespace broker