summaryrefslogtreecommitdiff
path: root/qpid/cpp/src/qpid/broker/TopicKeyNode.h
diff options
context:
space:
mode:
Diffstat (limited to 'qpid/cpp/src/qpid/broker/TopicKeyNode.h')
-rw-r--r--qpid/cpp/src/qpid/broker/TopicKeyNode.h371
1 files changed, 371 insertions, 0 deletions
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
View Lorry Controller Status