src/qpid/broker/TopicKeyNode.h - qpid-cpp - Git at Google

 /*
  *
  * 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<std::string, typename TopicKeyNode::shared_ptr> ChildMap;
     ChildMap childTokens;
     typename TopicKeyNode::shared_ptr starChild;  // "*" subtree
     typename 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 {
                     typename 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
	/*
	*
	* 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<std::string, typename TopicKeyNode::shared_ptr> ChildMap;
	ChildMap childTokens;
	typename TopicKeyNode::shared_ptr starChild; // "*" subtree
	typename 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 {
	typename 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