diff options
Diffstat (limited to 'cpp/src')
-rw-r--r-- | cpp/src/qpid/broker/TopicExchange.cpp | 221 | ||||
-rw-r--r-- | cpp/src/qpid/broker/TopicExchange.h | 48 | ||||
-rw-r--r-- | cpp/src/tests/TopicExchangeTest.cpp | 192 |
3 files changed, 209 insertions, 252 deletions
diff --git a/cpp/src/qpid/broker/TopicExchange.cpp b/cpp/src/qpid/broker/TopicExchange.cpp index a465c35790..85c7a6a28e 100644 --- a/cpp/src/qpid/broker/TopicExchange.cpp +++ b/cpp/src/qpid/broker/TopicExchange.cpp @@ -21,11 +21,16 @@ #include "TopicExchange.h" #include <algorithm> -using namespace qpid::broker; + +namespace qpid { +namespace broker { + using namespace qpid::framing; 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. @@ -43,98 +48,134 @@ const std::string fedOpReorigin("R"); const std::string fedOpHello("H"); } -Tokens& Tokens::operator=(const std::string& s) { - clear(); - if (s.empty()) return *this; - std::string::const_iterator i = s.begin(); - while (true) { - // Invariant: i is at the beginning of the next untokenized word. - std::string::const_iterator j = std::find(i, s.end(), '.'); - push_back(std::string(i, j)); - if (j == s.end()) return *this; - i = j + 1; + +namespace { +// Iterate over a string of '.'-separated tokens. +struct TokenIterator { + typedef pair<const char*,const char*> Token; + + TokenIterator(const char* b, const char* e) : token(make_pair(b, find(b,e,'.'))), end(e) {} + + 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, '.')); + } } - return *this; -} -TopicPattern& TopicPattern::operator=(const Tokens& tokens) { - Tokens::operator=(tokens); - normalize(); - return *this; -} + bool match1(char c) const { + return token.second==token.first+1 && *token.first == c; + } -void Tokens::key(string& keytext) const -{ - for (std::vector<string>::const_iterator iter = begin(); iter != end(); iter++) { - if (iter != begin()) - keytext += "."; - keytext += *iter; + bool match(const Token& token2) { + ptrdiff_t l=len(); + return l == token2.second-token2.first && + strncmp(token.first, token2.first, l) == 0; } -} -namespace { -const std::string hashmark("#"); -const std::string star("*"); -} + ptrdiff_t len() const { return token.second - token.first; } + + Token token; + const char* end; +}; -void TopicPattern::normalize() { - std::string word; - Tokens::iterator i = begin(); - while (i != end()) { - if (*i == hashmark) { - ++i; - while (i != end()) { - // Invariant: *(i-1)==#, [begin()..i-1] is normalized. - if (*i == star) { // Move * before #. - std::swap(*i, *(i-1)); - ++i; - } else if (*i == hashmark) { - erase(i); // Remove extra # - } else { - break; +class Normalizer : public TokenIterator { + public: + Normalizer(string& p) + : TokenIterator(&p[0], &p[0]+p.size()), pattern(p) + { normalize(); } + + private: + // Apply 2 transformations: #.* -> *.# and #.# -> # + void normalize() { + while (!finished()) { + if (match1('#')) { + const char* hash1=token.first; + next(); + if (!finished()) { + if (match1('#')) { // Erase #.# -> # + pattern.erase(hash1-pattern.data(), 2); + token.first -= 2; + token.second -= 2; + end -= 2; + } + else if (match1('*')) { // Swap #.* -> *.# + swap(*const_cast<char*>(hash1), + *const_cast<char*>(token.first)); + } } } - } else { - i ++; + else + next(); } } -} + string& pattern; +}; -namespace { -// TODO aconway 2006-09-20: Inefficient to convert every routingKey to a string. -// Need StringRef class that operates on a string in place witout copy. -// Should be applied everywhere strings are extracted from frames. -// -bool do_match(Tokens::const_iterator pattern_begin, Tokens::const_iterator pattern_end, Tokens::const_iterator target_begin, Tokens::const_iterator target_end) -{ - // Invariant: [pattern_begin..p) matches [target_begin..t) - Tokens::const_iterator p = pattern_begin; - Tokens::const_iterator t = target_begin; - while (p != pattern_end && t != target_end) - { - if (*p == star || *p == *t) { - ++p, ++t; - } else if (*p == hashmark) { - ++p; - if (do_match(p, pattern_end, t, target_end)) return true; - while (t != target_end) { - ++t; - if (do_match(p, pattern_end, t, target_end)) return true; +class Matcher { + public: + Matcher(const string& p, const string& k) + : matched(), pattern(&p[0], &p[0]+p.size()), key(&k[0], &k[0]+k.size()) + { matched = match(); } + + operator bool() const { return matched; } + + private: + Matcher(const char* bp, const char* ep, const char* bk, const char* ek) + : matched(), pattern(bp,ep), key(bk,ek) { matched = match(); } + + bool match() { + // Invariant: pattern and key match up to but excluding + // pattern.token and key.token + while (!pattern.finished() && !key.finished()) { + if (pattern.match1('*') && !key.finished()) { + pattern.next(); + key.next(); } - return false; - } else { - return false; + else if (pattern.match1('#')) { + pattern.next(); + if (pattern.finished()) return true; // Trailing # matches anything. + while (!key.finished()) { + if (Matcher(pattern.token.first, pattern.end, + key.token.first, key.end)) + return true; + key.next(); + } + return false; + } + else if (pattern.len() == key.len() && + equal(pattern.token.first,pattern.token.second,key.token.first)) { + pattern.next(); + key.next(); + } + else + return false; } + if (!pattern.finished() && pattern.match1('#')) + pattern.next(); // Trailing # matches empty. + return pattern.finished() && key.finished(); } - while (p != pattern_end && *p == hashmark) ++p; // Ignore trailing # - return t == target_end && p == pattern_end; + + bool matched; + TokenIterator pattern, key; +}; } + +// Convert sequences of * and # to a sequence of * followed by a single # +string TopicExchange::normalize(const string& pattern) { + string normal(pattern); + Normalizer n(normal); + return normal; } -bool TopicPattern::match(const Tokens& target) const +bool TopicExchange::match(const string& pattern, const string& key) { - return do_match(begin(), end(), target.begin(), target.end()); + return Matcher(pattern, key); } TopicExchange::TopicExchange(const string& _name, Manageable* _parent, Broker* b) : Exchange(_name, _parent, b) @@ -158,14 +199,14 @@ bool TopicExchange::bind(Queue::shared_ptr queue, const string& routingKey, cons string fedOrigin(args ? args->getAsString(qpidFedOrigin) : ""); bool propagate = false; bool reallyUnbind; - TopicPattern routingPattern(routingKey); + string routingPattern = normalize(routingKey); if (args == 0 || fedOp.empty() || fedOp == fedOpBind) { RWlock::ScopedWlock l(lock); if (isBound(queue, routingPattern)) { return false; } else { - Binding::shared_ptr binding (new Binding (routingKey, queue, this, FieldTable(), fedOrigin)); + Binding::shared_ptr binding (new Binding (routingPattern, queue, this, FieldTable(), fedOrigin)); BoundKey& bk = bindings[routingPattern]; bk.bindingVector.push_back(binding); propagate = bk.fedBinding.addOrigin(fedOrigin); @@ -182,15 +223,13 @@ bool TopicExchange::bind(Queue::shared_ptr queue, const string& routingKey, cons reallyUnbind = bk.fedBinding.count() == 0; } if (reallyUnbind) - unbind(queue, routingKey, 0); + unbind(queue, routingPattern, 0); } else if (fedOp == fedOpReorigin) { - for (std::map<TopicPattern, BoundKey>::iterator iter = bindings.begin(); + for (BindingMap::iterator iter = bindings.begin(); iter != bindings.end(); iter++) { const BoundKey& bk = iter->second; if (bk.fedBinding.hasLocal()) { - string propKey; - iter->first.key(propKey); - propagateFedOp(propKey, string(), fedOpBind, string()); + propagateFedOp(iter->first, string(), fedOpBind, string()); } } } @@ -201,9 +240,11 @@ bool TopicExchange::bind(Queue::shared_ptr queue, const string& routingKey, cons return true; } -bool TopicExchange::unbind(Queue::shared_ptr queue, const string& routingKey, const FieldTable* /*args*/){ +bool TopicExchange::unbind(Queue::shared_ptr queue, const string& constRoutingKey, const FieldTable* /*args*/){ RWlock::ScopedWlock l(lock); - BindingMap::iterator bi = bindings.find(TopicPattern(routingKey)); + string routingKey = normalize(constRoutingKey); + + BindingMap::iterator bi = bindings.find(routingKey); if (bi == bindings.end()) return false; BoundKey& bk = bi->second; Binding::vector& qv(bk.bindingVector); @@ -227,7 +268,7 @@ bool TopicExchange::unbind(Queue::shared_ptr queue, const string& routingKey, co return true; } -bool TopicExchange::isBound(Queue::shared_ptr queue, TopicPattern& pattern) +bool TopicExchange::isBound(Queue::shared_ptr queue, const string& pattern) { BindingMap::iterator bi = bindings.find(pattern); if (bi == bindings.end()) return false; @@ -246,10 +287,8 @@ void TopicExchange::route(Deliverable& msg, const string& routingKey, const Fiel { RWlock::ScopedRlock l(lock); - Tokens tokens(routingKey); - for (BindingMap::iterator i = bindings.begin(); i != bindings.end(); ++i) { - if (i->first.match(tokens)) { + if (match(i->first, routingKey)) { Binding::vector& qv(i->second.bindingVector); for(Binding::vector::iterator j = qv.begin(); j != qv.end(); j++, count++){ mb.push_back(*j); @@ -284,16 +323,15 @@ void TopicExchange::route(Deliverable& msg, const string& routingKey, const Fiel bool TopicExchange::isBound(Queue::shared_ptr queue, const string* const routingKey, const FieldTable* const) { if (routingKey && queue) { - TopicPattern key(*routingKey); + string key(normalize(*routingKey)); return isBound(queue, key); } else if (!routingKey && !queue) { return bindings.size() > 0; } else if (routingKey) { for (BindingMap::iterator i = bindings.begin(); i != bindings.end(); ++i) { - if (i->first.match(*routingKey)) { + if (match(i->first, *routingKey)) return true; } - } } else { for (BindingMap::iterator i = bindings.begin(); i != bindings.end(); ++i) { Binding::vector& qv(i->second.bindingVector); @@ -304,10 +342,11 @@ bool TopicExchange::isBound(Queue::shared_ptr queue, const string* const routing } } return false; + return queue && routingKey; } TopicExchange::~TopicExchange() {} const std::string TopicExchange::typeName("topic"); - +}} // namespace qpid::broker diff --git a/cpp/src/qpid/broker/TopicExchange.h b/cpp/src/qpid/broker/TopicExchange.h index b3ee1ea66d..02d4809c4c 100644 --- a/cpp/src/qpid/broker/TopicExchange.h +++ b/cpp/src/qpid/broker/TopicExchange.h @@ -32,59 +32,23 @@ namespace qpid { namespace broker { -/** A vector of string tokens */ -class Tokens : public std::vector<std::string> { - public: - Tokens() {}; - // Default copy, assign, dtor are sufficient. - - /** Tokenize s, provides automatic conversion of string to Tokens */ - Tokens(const std::string& s) { operator=(s); } - /** Tokenizing assignment operator s */ - QPID_BROKER_EXTERN Tokens & operator=(const std::string& s); - void key(std::string& key) const; - - private: - size_t hash; -}; - - -/** - * Tokens that have been normalized as a pattern and can be matched - * with topic Tokens. Normalized meands all sequences of mixed * and - * # are reduced to a series of * followed by at most one #. - */ -class TopicPattern : public Tokens -{ - public: - TopicPattern() {} - // Default copy, assign, dtor are sufficient. - TopicPattern(const Tokens& tokens) { operator=(tokens); } - TopicPattern(const std::string& str) { operator=(str); } - QPID_BROKER_EXTERN TopicPattern& operator=(const Tokens&); - TopicPattern& operator=(const std::string& str) { return operator=(Tokens(str)); } - - /** Match a topic */ - bool match(const std::string& topic) { return match(Tokens(topic)); } - QPID_BROKER_EXTERN bool match(const Tokens& topic) const; - - private: - void normalize(); -}; - class TopicExchange : public virtual Exchange { struct BoundKey { Binding::vector bindingVector; FedBinding fedBinding; }; - typedef std::map<TopicPattern, BoundKey> BindingMap; + typedef std::map<std::string, BoundKey> BindingMap; BindingMap bindings; qpid::sys::RWlock lock; - bool isBound(Queue::shared_ptr queue, TopicPattern& pattern); + bool isBound(Queue::shared_ptr queue, const string& pattern); + public: static const std::string typeName; + static bool match(const std::string& pattern, const std::string& topic); + static std::string normalize(const std::string& pattern); + QPID_BROKER_EXTERN TopicExchange(const string& name, management::Manageable* parent = 0, Broker* broker = 0); QPID_BROKER_EXTERN TopicExchange(const string& _name, diff --git a/cpp/src/tests/TopicExchangeTest.cpp b/cpp/src/tests/TopicExchangeTest.cpp index af4263de34..d707066534 100644 --- a/cpp/src/tests/TopicExchangeTest.cpp +++ b/cpp/src/tests/TopicExchangeTest.cpp @@ -21,147 +21,101 @@ #include "test_tools.h" using namespace qpid::broker; - -Tokens makeTokens(const char** begin, const char** end) -{ - Tokens t; - t.insert(t.end(), begin, end); - return t; -} - -// Calculate size of an array. -#define LEN(a) (sizeof(a)/sizeof(a[0])) - -// Convert array to token vector -#define TOKENS(a) makeTokens(a, a + LEN(a)) - -#define ASSERT_NORMALIZED(expect, pattern) \ - BOOST_CHECK_EQUAL(Tokens(expect), static_cast<Tokens>(TopicPattern(pattern))) - - +using namespace std; QPID_AUTO_TEST_SUITE(TopicExchangeTestSuite) -QPID_AUTO_TEST_CASE(testTokens) -{ - Tokens tokens("hello.world"); - const char* expect[] = {"hello", "world"}; - BOOST_CHECK_EQUAL(TOKENS(expect), tokens); - - tokens = "a.b.c"; - const char* expect2[] = { "a", "b", "c" }; - BOOST_CHECK_EQUAL(TOKENS(expect2), tokens); - - tokens = ""; - BOOST_CHECK(tokens.empty()); - - tokens = "x"; - const char* expect3[] = { "x" }; - BOOST_CHECK_EQUAL(TOKENS(expect3), tokens); - - tokens = (".x"); - const char* expect4[] = { "", "x" }; - BOOST_CHECK_EQUAL(TOKENS(expect4), tokens); - - tokens = ("x."); - const char* expect5[] = { "x", "" }; - BOOST_CHECK_EQUAL(TOKENS(expect5), tokens); - - tokens = ("."); - const char* expect6[] = { "", "" }; - BOOST_CHECK_EQUAL(TOKENS(expect6), tokens); - - tokens = (".."); - const char* expect7[] = { "", "", "" }; - BOOST_CHECK_EQUAL(TOKENS(expect7), tokens); -} +#define CHECK_NORMALIZED(expect, pattern) BOOST_CHECK_EQUAL(expect, TopicExchange::normalize(pattern)); QPID_AUTO_TEST_CASE(testNormalize) { - BOOST_CHECK(TopicPattern("").empty()); - ASSERT_NORMALIZED("a.b.c", "a.b.c"); - ASSERT_NORMALIZED("a.*.c", "a.*.c"); - ASSERT_NORMALIZED("#", "#"); - ASSERT_NORMALIZED("#", "#.#.#.#"); - ASSERT_NORMALIZED("*.*.*.#", "#.*.#.*.#.#.*"); - ASSERT_NORMALIZED("a.*.*.*.#", "a.*.#.*.#.*.#"); - ASSERT_NORMALIZED("a.*.*.*.#", "a.*.#.*.#.*"); + CHECK_NORMALIZED("", ""); + CHECK_NORMALIZED("a.b.c", "a.b.c"); + CHECK_NORMALIZED("a.*.c", "a.*.c"); + CHECK_NORMALIZED("#", "#"); + CHECK_NORMALIZED("#", "#.#.#.#"); + CHECK_NORMALIZED("*.*.*.#", "#.*.#.*.#.#.*"); + CHECK_NORMALIZED("a.*.*.*.#", "a.*.#.*.#.*.#"); + CHECK_NORMALIZED("a.*.*.*.#", "a.*.#.*.#.*"); + CHECK_NORMALIZED("*.*.*.#", "*.#.#.*.*.#"); } QPID_AUTO_TEST_CASE(testPlain) { - TopicPattern p("ab.cd.e"); - BOOST_CHECK(p.match("ab.cd.e")); - BOOST_CHECK(!p.match("abx.cd.e")); - BOOST_CHECK(!p.match("ab.cd")); - BOOST_CHECK(!p.match("ab.cd..e.")); - BOOST_CHECK(!p.match("ab.cd.e.")); - BOOST_CHECK(!p.match(".ab.cd.e")); - - p = ""; - BOOST_CHECK(p.match("")); - - p = "."; - BOOST_CHECK(p.match(".")); + string pattern("ab.cd.e"); + BOOST_CHECK(TopicExchange::match(pattern, "ab.cd.e")); + BOOST_CHECK(!TopicExchange::match(pattern, "abx.cd.e")); + BOOST_CHECK(!TopicExchange::match(pattern, "ab.cd")); + BOOST_CHECK(!TopicExchange::match(pattern, "ab.cd..e.")); + BOOST_CHECK(!TopicExchange::match(pattern, "ab.cd.e.")); + BOOST_CHECK(!TopicExchange::match(pattern, ".ab.cd.e")); + + pattern = ""; + BOOST_CHECK(TopicExchange::match(pattern, "")); + + pattern = "."; + BOOST_CHECK(TopicExchange::match(pattern, ".")); } QPID_AUTO_TEST_CASE(testStar) { - TopicPattern p("a.*.b"); - BOOST_CHECK(p.match("a.xx.b")); - BOOST_CHECK(!p.match("a.b")); - - p = "*.x"; - BOOST_CHECK(p.match("y.x")); - BOOST_CHECK(p.match(".x")); - BOOST_CHECK(!p.match("x")); - - p = "x.x.*"; - BOOST_CHECK(p.match("x.x.y")); - BOOST_CHECK(p.match("x.x.")); - BOOST_CHECK(!p.match("x.x")); - BOOST_CHECK(!p.match("q.x.y")); + string pattern("a.*.b"); + BOOST_CHECK(TopicExchange::match(pattern, "a.xx.b")); + BOOST_CHECK(!TopicExchange::match(pattern, "a.b")); + + pattern = "*.x"; + BOOST_CHECK(TopicExchange::match(pattern, "y.x")); + BOOST_CHECK(TopicExchange::match(pattern, ".x")); + BOOST_CHECK(!TopicExchange::match(pattern, "x")); + + pattern = "x.x.*"; + BOOST_CHECK(TopicExchange::match(pattern, "x.x.y")); + BOOST_CHECK(TopicExchange::match(pattern, "x.x.")); + BOOST_CHECK(!TopicExchange::match(pattern, "x.x")); + BOOST_CHECK(!TopicExchange::match(pattern, "q.x.y")); } QPID_AUTO_TEST_CASE(testHash) { - TopicPattern p("a.#.b"); - BOOST_CHECK(p.match("a.b")); - BOOST_CHECK(p.match("a.x.b")); - BOOST_CHECK(p.match("a..x.y.zz.b")); - BOOST_CHECK(!p.match("a.b.")); - BOOST_CHECK(!p.match("q.x.b")); - - p = "a.#"; - BOOST_CHECK(p.match("a")); - BOOST_CHECK(p.match("a.b")); - BOOST_CHECK(p.match("a.b.c")); - - p = "#.a"; - BOOST_CHECK(p.match("a")); - BOOST_CHECK(p.match("x.y.a")); + string pattern("a.#.b"); + BOOST_CHECK(TopicExchange::match(pattern, "a.b")); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.b")); + BOOST_CHECK(TopicExchange::match(pattern, "a..x.y.zz.b")); + BOOST_CHECK(!TopicExchange::match(pattern, "a.b.")); + BOOST_CHECK(!TopicExchange::match(pattern, "q.x.b")); + + pattern = "a.#"; + BOOST_CHECK(TopicExchange::match(pattern, "a")); + BOOST_CHECK(TopicExchange::match(pattern, "a.b")); + BOOST_CHECK(TopicExchange::match(pattern, "a.b.c")); + + pattern = "#.a"; + BOOST_CHECK(TopicExchange::match(pattern, "a")); + BOOST_CHECK(TopicExchange::match(pattern, "x.y.a")); + + pattern = "a.#.b.#.c"; + BOOST_CHECK(TopicExchange::match(pattern, "a.b.c")); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.b.y.c")); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.x.b.y.y.c")); } QPID_AUTO_TEST_CASE(testMixed) { - TopicPattern p("*.x.#.y"); - BOOST_CHECK(p.match("a.x.y")); - BOOST_CHECK(p.match("a.x.p.qq.y")); - BOOST_CHECK(!p.match("a.a.x.y")); - BOOST_CHECK(!p.match("aa.x.b.c")); - - p = "a.#.b.*"; - BOOST_CHECK(p.match("a.b.x")); - BOOST_CHECK(p.match("a.x.x.x.b.x")); -} - -QPID_AUTO_TEST_CASE(testCombo) -{ - TopicPattern p("*.#.#.*.*.#"); - BOOST_CHECK(p.match("x.y.z")); - BOOST_CHECK(p.match("x.y.z.a.b.c")); - BOOST_CHECK(!p.match("x.y")); - BOOST_CHECK(!p.match("x")); + string pattern("*.x.#.y"); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.y")); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.p.qq.y")); + BOOST_CHECK(!TopicExchange::match(pattern, "a.a.x.y")); + BOOST_CHECK(!TopicExchange::match(pattern, "aa.x.b.c")); + + pattern = "a.#.b.*"; + BOOST_CHECK(TopicExchange::match(pattern, "a.b.x")); + BOOST_CHECK(TopicExchange::match(pattern, "a.x.x.x.b.x")); + + pattern = "*.*.*.#"; + BOOST_CHECK(TopicExchange::match(pattern, "x.y.z")); + BOOST_CHECK(TopicExchange::match(pattern, "x.y.z.a.b.c")); + BOOST_CHECK(!TopicExchange::match(pattern, "x.y")); + BOOST_CHECK(!TopicExchange::match(pattern, "x")); } QPID_AUTO_TEST_SUITE_END() |