1 files changed, 319 insertions, 40 deletions

diff --git a/cpp/src/tests/TopicExchangeTest.cpp b/cpp/src/tests/TopicExchangeTest.cpp
index c103620dbf..ff8931f9c9 100644
--- a/cpp/src/tests/TopicExchangeTest.cpp
+++ b/cpp/src/tests/TopicExchangeTest.cpp
@@ -23,13 +23,121 @@
 using namespace qpid::broker;
 using namespace std;
 
+
 namespace qpid {
+namespace broker {
+
+// Class for exercising the pattern match code in the TopicExchange
+class TopicExchange::TopicExchangeTester {
+
+public:
+    typedef std::vector<std::string> BindingVec;
+
+private:
+    // binding node iterator that collects all routes that are bound
+    class TestFinder : public TopicExchange::BindingNode::TreeIterator {
+    public:
+        TestFinder(BindingVec& m) : bv(m) {};
+        ~TestFinder() {};
+        bool visit(BindingNode& node) {
+            if (!node.bindings.bindingVector.empty())
+                bv.push_back(node.routePattern);
+            return true;
+        }
+
+        BindingVec& bv;
+    };
+
+public:
+    TopicExchangeTester() {};
+    ~TopicExchangeTester() {};
+    bool addBindingKey(const std::string& bKey) {
+        string routingPattern = normalize(bKey);
+        BindingKey *bk = bindingTree.addBindingKey(routingPattern);
+        if (bk) {
+            // push a dummy binding to mark this node as "non-leaf"
+            bk->bindingVector.push_back(Binding::shared_ptr());
+            return true;
+        }
+        return false;
+    }
+
+    bool removeBindingKey(const std::string& bKey){
+        string routingPattern = normalize(bKey);
+        BindingKey *bk = bindingTree.getBindingKey(routingPattern);
+        if (bk) {
+            bk->bindingVector.pop_back();
+            if (bk->bindingVector.empty()) {
+                // no more bindings - remove this node
+                bindingTree.removeBindingKey(routingPattern);
+            }
+            return true;
+        }
+        return false;
+    }
+
+    void findMatches(const std::string& rKey, BindingVec& matches) {
+        TestFinder testFinder(matches);
+        bindingTree.iterateMatch( rKey, testFinder );
+    }
+
+    void getAll(BindingVec& bindings) {
+        TestFinder testFinder(bindings);
+        bindingTree.iterateAll( testFinder );
+    }
+
+private:
+    TopicExchange::BindingNode bindingTree;
+};
+} // namespace broker
+
+
 namespace tests {
 
 QPID_AUTO_TEST_SUITE(TopicExchangeTestSuite)
 
 #define CHECK_NORMALIZED(expect, pattern) BOOST_CHECK_EQUAL(expect, TopicExchange::normalize(pattern));
 
+namespace {
+    // return the count of bindings that match 'pattern'
+    int match(TopicExchange::TopicExchangeTester &tt,
+              const std::string& pattern)
+    {
+        TopicExchange::TopicExchangeTester::BindingVec bv;
+        tt.findMatches(pattern, bv);
+        return int(bv.size());
+    }
+
+    // return true if expected contains exactly all bindings that match
+    // against pattern.
+    bool compare(TopicExchange::TopicExchangeTester& tt,
+                 const std::string& pattern,
+                 const TopicExchange::TopicExchangeTester::BindingVec& expected)
+    {
+        TopicExchange::TopicExchangeTester::BindingVec bv;
+        tt.findMatches(pattern, bv);
+        if (expected.size() != bv.size()) {
+            // std::cout << "match failed 1 f=[" << bv << "]" << std::endl;
+            // std::cout << "match failed 1 e=[" << expected << "]" << std::endl;
+            return false;
+        }
+        TopicExchange::TopicExchangeTester::BindingVec::const_iterator i;
+        for (i = expected.begin(); i != expected.end(); i++) {
+            TopicExchange::TopicExchangeTester::BindingVec::iterator j;
+            for (j = bv.begin(); j != bv.end(); j++) {
+                // std::cout << "matched [" << *j << "]" << std::endl;
+                if (*i == *j) break;
+            }
+            if (j == bv.end()) {
+                // std::cout << "match failed 2 [" << bv << "]" << std::endl;
+                return false;
+            }
+        }
+        return true;
+    }
+}
+
+
 QPID_AUTO_TEST_CASE(testNormalize)
 {
     CHECK_NORMALIZED("", "");
@@ -45,81 +153,252 @@ QPID_AUTO_TEST_CASE(testNormalize)
 
 QPID_AUTO_TEST_CASE(testPlain)
 {
+    TopicExchange::TopicExchangeTester tt;
     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"));
+
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "ab.cd.e"));
+    BOOST_CHECK_EQUAL(0, match(tt, "abx.cd.e"));
+    BOOST_CHECK_EQUAL(0, match(tt, "ab.cd"));
+    BOOST_CHECK_EQUAL(0, match(tt, "ab.cd..e."));
+    BOOST_CHECK_EQUAL(0, match(tt, "ab.cd.e."));
+    BOOST_CHECK_EQUAL(0, match(tt, ".ab.cd.e"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = "";
-    BOOST_CHECK(TopicExchange::match(pattern, ""));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, ""));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = ".";
-    BOOST_CHECK(TopicExchange::match(pattern, "."));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "."));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 }
 
 
 QPID_AUTO_TEST_CASE(testStar)
 {
+    TopicExchange::TopicExchangeTester tt;
     string pattern("a.*.b");
-    BOOST_CHECK(TopicExchange::match(pattern, "a.xx.b"));
-    BOOST_CHECK(!TopicExchange::match(pattern, "a.b"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.xx.b"));
+    BOOST_CHECK_EQUAL(0, match(tt, "a.b"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = "*.x";
-    BOOST_CHECK(TopicExchange::match(pattern, "y.x"));
-    BOOST_CHECK(TopicExchange::match(pattern, ".x"));
-    BOOST_CHECK(!TopicExchange::match(pattern, "x"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "y.x"));
+    BOOST_CHECK_EQUAL(1, match(tt, ".x"));
+    BOOST_CHECK_EQUAL(0, match(tt, "x"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     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"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "x.x.y"));
+    BOOST_CHECK_EQUAL(1, match(tt, "x.x."));
+    BOOST_CHECK_EQUAL(0, match(tt, "x.x"));
+    BOOST_CHECK_EQUAL(0, match(tt, "q.x.y"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 }
 
 QPID_AUTO_TEST_CASE(testHash)
 {
+    TopicExchange::TopicExchangeTester tt;
     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"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.b"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.b"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a..x.y.zz.b"));
+    BOOST_CHECK_EQUAL(0, match(tt, "a.b."));
+    BOOST_CHECK_EQUAL(0, match(tt, "q.x.b"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = "a.#";
-    BOOST_CHECK(TopicExchange::match(pattern, "a"));
-    BOOST_CHECK(TopicExchange::match(pattern, "a.b"));
-    BOOST_CHECK(TopicExchange::match(pattern, "a.b.c"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.b"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.b.c"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = "#.a";
-    BOOST_CHECK(TopicExchange::match(pattern, "a"));
-    BOOST_CHECK(TopicExchange::match(pattern, "x.y.a"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a"));
+    BOOST_CHECK_EQUAL(1, match(tt, "x.y.a"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     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"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.b.c"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.b.y.c"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.x.b.y.y.c"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 }
 
 QPID_AUTO_TEST_CASE(testMixed)
 {
+    TopicExchange::TopicExchangeTester tt;
     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"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.y"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.p.qq.y"));
+    BOOST_CHECK_EQUAL(0, match(tt, "a.a.x.y"));
+    BOOST_CHECK_EQUAL(0, match(tt, "aa.x.b.c"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     pattern = "a.#.b.*";
-    BOOST_CHECK(TopicExchange::match(pattern, "a.b.x"));
-    BOOST_CHECK(TopicExchange::match(pattern, "a.x.x.x.b.x"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.b.x"));
+    BOOST_CHECK_EQUAL(1, match(tt, "a.x.x.x.b.x"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
 
     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"));
+    BOOST_CHECK(tt.addBindingKey(pattern));
+    BOOST_CHECK_EQUAL(1, match(tt, "x.y.z"));
+    BOOST_CHECK_EQUAL(1, match(tt, "x.y.z.a.b.c"));
+    BOOST_CHECK_EQUAL(0, match(tt, "x.y"));
+    BOOST_CHECK_EQUAL(0, match(tt, "x"));
+    BOOST_CHECK(tt.removeBindingKey(pattern));
+}
+
+
+QPID_AUTO_TEST_CASE(testMultiple)
+{
+    TopicExchange::TopicExchangeTester tt;
+    const std::string bindings[] =
+      { "a",        "b",
+        "a.b",      "b.c",
+        "a.b.c.d",  "b.c.d.e",
+        "a.*",      "a.#",        "a.*.#",
+        "#.b",      "*.b",        "*.#.b",
+        "a.*.b",    "a.#.b",      "a.*.#.b",
+        "*.b.*",    "#.b.#",
+      };
+    const size_t nBindings = sizeof(bindings)/sizeof(bindings[0]);
+
+    // setup bindings
+    for (size_t idx = 0; idx < nBindings; idx++) {
+        BOOST_CHECK(tt.addBindingKey(bindings[idx]));
+    }
+
+    {
+        // read all bindings, and verify all are present
+        TopicExchange::TopicExchangeTester::BindingVec b;
+        tt.getAll(b);
+        BOOST_CHECK_EQUAL(b.size(), nBindings);
+        for (size_t idx = 0; idx < nBindings; idx++) {
+            bool found = false;
+            for (TopicExchange::TopicExchangeTester::BindingVec::iterator i = b.begin();
+                 i != b.end(); i++) {
+                if (*i == bindings[idx]) {
+                    found = true;
+                    break;
+                }
+            }
+            BOOST_CHECK(found);
+        }
+    }
+
+    {   // test match on pattern "a"
+        const std::string matches[] = { "a", "a.#" };
+        const size_t nMatches = 2;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a", expected));
+    }
+
+    {   // test match on pattern "a.z"
+        const std::string matches[] = { "a.*", "a.#", "a.*.#" };
+        const size_t nMatches = 3;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a.z", expected));
+    }
+
+    {   // test match on pattern "a.b"
+        const std::string matches[] = {
+            "a.b", "a.*", "a.#", "a.*.#",
+            "#.b", "#.b.#", "*.#.b", "*.b",
+            "a.#.b"
+        };
+        const size_t nMatches = 9;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a.b", expected));
+    }
+
+    {   // test match on pattern "a.c.c.b"
+
+        const std::string matches[] = {
+            "#.b",  "#.b.#",  "*.#.b",  "a.#.b",
+            "a.#",  "a.*.#.b",  "a.*.#"
+        };
+        const size_t nMatches = 7;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a.c.c.b", expected));
+    }
+
+    {   // test match on pattern "a.b.c"
+
+        const std::string matches[] = {
+            "#.b.#",  "*.b.*",  "a.#",  "a.*.#"
+        };
+        const size_t nMatches = 4;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a.b.c", expected));
+    }
+
+    {   // test match on pattern "b"
+
+        const std::string matches[] = {
+            "#.b",  "#.b.#",  "b"
+        };
+        const size_t nMatches = 3;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "b", expected));
+    }
+
+    {   // test match on pattern "x.b"
+
+        const std::string matches[] = {
+            "#.b", "#.b.#", "*.#.b", "*.b"
+        };
+        const size_t nMatches = 4;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "x.b", expected));
+    }
+
+    {   // test match on pattern "x.y.z.b"
+
+        const std::string matches[] = {
+            "#.b", "#.b.#", "*.#.b"
+        };
+        const size_t nMatches = 3;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "x.y.z.b", expected));
+    }
+
+    {   // test match on pattern "x.y.z.b.a.b.c"
+
+        const std::string matches[] = {
+            "#.b.#", "#.b.#"
+        };
+        const size_t nMatches = 2;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "x.y.z.b.a.b.c", expected));
+    }
+
+    {   // test match on pattern "a.b.c.d"
+
+        const std::string matches[] = {
+            "#.b.#", "a.#", "a.*.#", "a.b.c.d",
+        };
+        const size_t nMatches = 4;
+        TopicExchange::TopicExchangeTester::BindingVec expected(matches, matches + nMatches);
+        BOOST_CHECK(compare(tt, "a.b.c.d", expected));
+    }
+
+    // cleanup bindings
+    for (size_t idx = 0; idx < nBindings; idx++) {
+        BOOST_CHECK(tt.removeBindingKey(bindings[idx]));
+    }
 }
 
 QPID_AUTO_TEST_SUITE_END()