From f07e81db3e310ccc39d5d49fe525b56857804a3c Mon Sep 17 00:00:00 2001 From: Ted Ross Date: Fri, 8 Jun 2012 20:39:30 +0000 Subject: 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 --- qpid/cpp/src/Makefile.am | 1 + qpid/cpp/src/qpid/broker/TopicExchange.cpp | 369 +--------------------------- qpid/cpp/src/qpid/broker/TopicExchange.h | 126 ++-------- qpid/cpp/src/qpid/broker/TopicKeyNode.h | 371 +++++++++++++++++++++++++++++ qpid/cpp/src/tests/TopicExchangeTest.cpp | 14 +- 5 files changed, 408 insertions(+), 473 deletions(-) create mode 100644 qpid/cpp/src/qpid/broker/TopicKeyNode.h (limited to 'qpid/cpp/src') 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 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 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 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 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 bindingCache; // cache of matched routes. + class ClearCache { private: qpid::sys::RWlock* cacheLock; std::map* bindingCache; - bool cleared; + bool cleared; public: - ClearCache(qpid::sys::RWlock* l, std::map* bc): cacheLock(l), - bindingCache(bc),cleared(false) {}; + ClearCache(qpid::sys::RWlock* l, std::map* 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 +#include +#include +#include + + +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 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 QPID_BROKER_CLASS_EXTERN TopicKeyNode { + + public: + + typedef boost::shared_ptr 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 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(STAR)); + } + bKey.next(); + return starChild->add(bKey, fullPattern); + + } else if (bKey.match(HASH)) { + if (!hashChild) { + hashChild.reset(new TopicKeyNode(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(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 BindingVec; + typedef TopicKeyNode 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 -- cgit v1.2.1