Optimized TopicExchange matching.

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

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()