STL-style intrsive linked lists, single (ISList) and double (IList)

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

3 files changed, 330 insertions, 200 deletions

diff --git a/cpp/src/tests/IList.cpp b/cpp/src/tests/IList.cpp
index 392ef4823d..2e872d0e05 100644
--- a/cpp/src/tests/IList.cpp
+++ b/cpp/src/tests/IList.cpp
@@ -1,240 +1,163 @@
 /*
  *
- * Copyright (c) 2006 The Apache Software Foundation
- *
- * Licensed 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.
+ * 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.
  *
  */
-
-
+#include "qpid/IList.h"
 #include "unit_test.h"
 #include "test_tools.h"
-#include "qpid/IList.h"
 #include <boost/assign/list_of.hpp>
 #include <vector>
 
+QPID_AUTO_TEST_SUITE(IListTestSuite)
+
 using namespace qpid;
 using namespace std;
 using boost::assign::list_of;
 
-// Comparison, op== for ILists and sequences of intrusive_ptr<T>
-// in qpid namespace to satisfy template lookup rules
-namespace qpid {
-template <class T, int N, class S> bool operator==(const IList<T,N>& a, const S& b) { return seqEqual(a, b); }
-template <class T, int N> std::ostream& operator<<(std::ostream& o, const IList<T,N>& l) { return seqPrint(o, l); }
-}
-
-QPID_AUTO_TEST_SUITE(IListTestSuite)
+// Comparison, op== and << for ILists in qpid namespace for template lookup.
 
-template <class T> bool operator==(const T& v, const intrusive_ptr<T>& p) { return v==*p; }
+template <class T, class S> bool operator==(const IList<T>& a, const S& b) { return seqEqual(a, b); }
+template <class T> ostream& operator<<(std::ostream& o, const IList<T>& l) { return seqPrint(o, l); }
+template <class T>
+ostream& operator<<(ostream& o, typename IList<T>::iterator i) {
+    return i? o << "(nil)" : o << *i;
+}
 
-struct TestNode {
-    static int instances;
-    char id;
-    TestNode(char i) : id(i) { ++instances; }
-    ~TestNode() { --instances; }
-    bool operator==(const TestNode& x) const { return this == &x; }
-    bool operator==(const TestNode* x) const { return this == x; }
+struct IListFixture {
+    struct Node : public IListNode<Node*> {
+        char value;
+        Node(char c) { value=c; }
+        bool operator==(const Node& n) const { return value == n.value; }
+    };
+    typedef IList<Node> List;
+    Node a, b, c, d, e;
+    IListFixture() :a('a'),b('b'),c('c'),d('d'),e('e') {}
 };
-int TestNode::instances = 0;
-ostream& operator<<(ostream& o, const TestNode& n) { return o << n.id; }
 
-struct SingleNode : public TestNode, public IListNode<SingleNode> {
-    SingleNode(char i) : TestNode(i) {}
-};
-typedef IList<SingleNode> TestList;
-
-struct Fixture {
-    intrusive_ptr<SingleNode> a, b, c, d;
-    Fixture() : a(new SingleNode('a')),
-                b(new SingleNode('b')),
-                c(new SingleNode('c')),
-                d(new SingleNode('d'))
-    {
-        BOOST_CHECK_EQUAL(4, TestNode::instances);
-    }
-};
+ostream& operator<<(ostream& o, const IListFixture::Node& n) { return o << n.value; }
 
-BOOST_AUTO_TEST_CASE(TestFixture) {
-    { Fixture f; }
-    BOOST_CHECK_EQUAL(0, TestNode::instances);
-}
-
-BOOST_FIXTURE_TEST_CASE(TestSingleList, Fixture) {
-    TestList l;
-    BOOST_CHECK_EQUAL(0u, l.size());
+BOOST_FIXTURE_TEST_CASE(IList_default_ctor, IListFixture) {
+    List l;
     BOOST_CHECK(l.empty());
+    BOOST_CHECK(l.begin() == l.end());
+    BOOST_CHECK_EQUAL(0u, l.size());
+}
 
-    l.push_back(*a);
+BOOST_FIXTURE_TEST_CASE(IList_push_front, IListFixture) {
+    List l;
+    l.push_front(&a);
     BOOST_CHECK_EQUAL(1u, l.size());
-    BOOST_CHECK(!l.empty());
     BOOST_CHECK_EQUAL(l, list_of(a));
+    l.push_front(&b);
+    BOOST_CHECK_EQUAL(2u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(b)(a));
+}
 
-    TestList::iterator i = l.begin();
-    BOOST_CHECK_EQUAL(*i, *a);
-    
-    l.push_back(*b);
+BOOST_FIXTURE_TEST_CASE(IList_push_back, IListFixture) {
+    List l;
+    l.push_back(&a);
+    BOOST_CHECK_EQUAL(1u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    l.push_back(&b);
     BOOST_CHECK_EQUAL(2u, l.size());
     BOOST_CHECK_EQUAL(l, list_of(a)(b));
-    BOOST_CHECK_EQUAL(*i, *a);        // Iterator not invalidated
-    BOOST_CHECK_EQUAL(l.front(), *a);
-    BOOST_CHECK_EQUAL(l.back(), *b);
-
-    l.push_front(*c);
-    BOOST_CHECK_EQUAL(3u, l.size());
-    BOOST_CHECK_EQUAL(l, list_of(c)(a)(b));
-    BOOST_CHECK_EQUAL(*i, *a);        // Iterator not invalidated
-
-    l.insert(i, *d);
-    BOOST_CHECK_EQUAL(4u, l.size());
-    BOOST_CHECK_EQUAL(l, list_of(c)(d)(a)(b));
-    BOOST_CHECK_EQUAL(*i, *a);
-
-    a = 0;                      // Not deleted yet, still in list.
-    BOOST_CHECK_EQUAL(4, SingleNode::instances);
-    l.erase(i);
-    BOOST_CHECK_EQUAL(3, SingleNode::instances);
-    BOOST_CHECK_EQUAL(l, list_of(c)(d)(b));
+}
 
-    l.pop_front();
-    l.pop_back();
-    c = 0; b = 0;
-    BOOST_CHECK_EQUAL(1, SingleNode::instances);
-    BOOST_CHECK_EQUAL(l, list_of(d));
+BOOST_FIXTURE_TEST_CASE(IList_insert, IListFixture) {
+    List l;
+    List::iterator i(l.begin());
+    i = l.insert(i, &a);
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    BOOST_CHECK(i == l.begin());
 
-    l.pop_back();
-    BOOST_CHECK_EQUAL(0u, l.size());
-    BOOST_CHECK(l.empty());
+    i = l.insert(i, &b);
+    BOOST_CHECK_EQUAL(l, list_of(b)(a));
+    BOOST_CHECK(i == l.begin());
+
+    i++;
+    BOOST_CHECK_EQUAL(*i, a);    
+    i = l.insert(i, &c);
+    BOOST_CHECK_EQUAL(l, list_of(b)(c)(a));
+    BOOST_CHECK_EQUAL(*i, c);
+
+    i = l.insert(i, &d);
+    BOOST_CHECK_EQUAL(l, list_of(b)(d)(c)(a));
+    BOOST_CHECK_EQUAL(*i, d);
 }
 
-BOOST_FIXTURE_TEST_CASE(TestIterator, Fixture) {
-    {
-        TestList l;
-        l.push_back(*a);
-        BOOST_CHECK(a->getNext() == 0);
-        BOOST_CHECK(a->getPrev() == 0);
-        l.push_back(*b);
-        BOOST_CHECK(a->getNext() == b.get());
-        BOOST_CHECK(a->getPrev() == 0);
-        BOOST_CHECK(b->getNext() == 0);
-        BOOST_CHECK(b->getPrev() == a.get());
-        l.push_back(*c);
-        BOOST_CHECK(b->getNext() == c.get());
-        BOOST_CHECK(c->getPrev() == b.get());
+BOOST_FIXTURE_TEST_CASE(IList_iterator_test, IListFixture) {
+    List l;
+    l.push_back(&a);
+    l.push_back(&b);
     
-        TestList::iterator i = l.begin();
-        BOOST_CHECK_EQUAL(*i, *a);
-        i++;
-        BOOST_CHECK_EQUAL(*i, *b);
-        i++;
-        BOOST_CHECK_EQUAL(*i, *c);
-        i++;
-        BOOST_CHECK(i == l.end());
-        i--;
-        BOOST_CHECK_EQUAL(*i, *c);
-        i--;
-        BOOST_CHECK_EQUAL(*i, *b);
-        i--;
-        BOOST_CHECK_EQUAL(*i, *a);
-    }
-    a = b = c = d = 0;
-    BOOST_CHECK_EQUAL(0, TestNode::instances);
-}    
-
-
-BOOST_AUTO_TEST_CASE(testEmptyDtor) {
-    TestList l;
-}
+    List::iterator i = l.begin();
+    BOOST_CHECK_EQUAL(*i, a);
+    BOOST_CHECK_EQUAL(static_cast<Node*>(i), &a);
+    List::const_iterator ci = i;
+    BOOST_CHECK_EQUAL(static_cast<const Node*>(ci), &a);
 
-BOOST_FIXTURE_TEST_CASE(testOwnership, Fixture) {
-    { 
-        TestList l2;
-        l2.push_back(*a);
-        l2.push_back(*b);
-        l2.push_back(*c);
-        l2.push_back(*d);
-        a = b = c = d = 0;
-        BOOST_CHECK_EQUAL(4, SingleNode::instances);
-    }
-    BOOST_CHECK_EQUAL(0, SingleNode::instances);
+    i++;
+    BOOST_CHECK_EQUAL(*i, b);    
+    BOOST_CHECK_EQUAL(static_cast<Node*>(i), &b);
+    i++;
+    BOOST_CHECK(i == l.end());
 }
 
-struct MultiNode : public TestNode,
-                   public IListNode<MultiNode, 0>,
-                   public IListNode<MultiNode, 1>,
-                   public IListNode<MultiNode, 2>
-{
-    MultiNode(char c) : TestNode(c) {}
-};
+BOOST_FIXTURE_TEST_CASE(IList_pop_front, IListFixture) {
+    List l;
+    l.push_back(&a);
+    l.push_back(&b);
+    BOOST_CHECK_EQUAL(l, list_of(a)(b));
+    l.pop_front();
+    BOOST_CHECK_EQUAL(l, list_of(b));
+    l.pop_front();
+    BOOST_CHECK(l.empty());
+}
 
-struct MultiFixture {
-    IList<MultiNode, 0> l0;
-    IList<MultiNode, 1> l1;
-    IList<MultiNode, 2> l2;
-
-    intrusive_ptr<MultiNode> a, b, c;
-
-    MultiFixture() : a(new MultiNode('a')),
-                     b(new MultiNode('b')),
-                     c(new MultiNode('c'))
-    {    
-        BOOST_CHECK_EQUAL(3, MultiNode::instances);
-    }
-
-    void push_back_all(intrusive_ptr<MultiNode> p) {
-        l0.push_back(*p);
-        l1.push_back(*p);
-        l2.push_back(*p);
-    }
-};
+BOOST_FIXTURE_TEST_CASE(IList_pop_back, IListFixture) {
+    List l;
+    l.push_back(&a);
+    l.push_back(&b);
+    l.pop_back();
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    l.pop_back();
+    BOOST_CHECK(l.empty());
+}
 
-BOOST_FIXTURE_TEST_CASE(TestMultiIList, MultiFixture) {
-    BOOST_CHECK_EQUAL(a->id, 'a');
-    push_back_all(a);
-    push_back_all(b);
-    push_back_all(c);
+BOOST_FIXTURE_TEST_CASE(IList_erase, IListFixture) {
+    List l;
+    l.push_back(&a);
+    l.push_back(&b);
+    l.push_back(&c);
 
-    BOOST_CHECK_EQUAL(3, MultiNode::instances);
+    List::iterator i=l.begin();
+    i++;
+    l.erase(i);
+    BOOST_CHECK_EQUAL(l, list_of(a)(c));
 
-    l0.pop_front();
-    l1.pop_back();
-    IList<MultiNode, 2>::iterator i = l2.begin();
+    i=l.begin();
     i++;
-    l2.erase(i);
-    BOOST_CHECK_EQUAL(3, MultiNode::instances);
-    BOOST_CHECK_EQUAL(l0, list_of(b)(c));    
-    BOOST_CHECK_EQUAL(l1, list_of(a)(b));    
-    BOOST_CHECK_EQUAL(l2, list_of(a)(c));
-    
-    l1.pop_front();
-    l2.clear();
-    BOOST_CHECK_EQUAL(l0, list_of(b)(c));    
-    BOOST_CHECK_EQUAL(l1, list_of(b));    
-    BOOST_CHECK(l2.empty());
-    a = 0;
-    BOOST_CHECK_EQUAL(2, MultiNode::instances); // a gone
-
-    l0.pop_back();
-    l1.pop_front();
-    BOOST_CHECK_EQUAL(l0, list_of(b));    
-    BOOST_CHECK(l1.empty());
-    BOOST_CHECK(l2.empty());
-    BOOST_CHECK_EQUAL(2, MultiNode::instances); // c gone
-    c = 0;
-
-    l0.clear();
-    b = 0;
-    BOOST_CHECK_EQUAL(0, MultiNode::instances); // all gone
+    l.erase(i);
+    BOOST_CHECK_EQUAL(l, list_of(a));
+
+    l.erase(l.begin());
+    BOOST_CHECK(l.empty());
 }
 
 QPID_AUTO_TEST_SUITE_END()
diff --git a/cpp/src/tests/ISList.cpp b/cpp/src/tests/ISList.cpp
new file mode 100644
index 0000000000..de06f130ff
--- /dev/null
+++ b/cpp/src/tests/ISList.cpp
@@ -0,0 +1,207 @@
+/*
+ *
+ * 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.
+ *
+ */
+#include "qpid/ISList.h"
+#include "qpid/RefCounted.h"
+#include "unit_test.h"
+#include "test_tools.h"
+#include <boost/assign/list_of.hpp>
+#include <boost/shared_ptr.hpp>
+#include <vector>
+
+QPID_AUTO_TEST_SUITE(ISListTestSuite)
+
+using namespace qpid;
+using namespace std;
+using boost::assign::list_of;
+
+// Comparison, op== and << for ILists in qpid namespace for template lookup.
+
+template <class T, class S> bool operator==(const ISList<T>& a, const S& b) { return seqEqual(a, b); }
+template <class T> ostream& operator<<(std::ostream& o, const ISList<T>& l) { return seqPrint(o, l); }
+template <class T>
+ostream& operator<<(ostream& o, typename ISList<T>::iterator i) {
+    return i? o << "(nil)" : o << *i;
+}
+
+struct NodeBase {
+    static int instances;
+    char value;
+
+    NodeBase(char c) { value=c; ++instances; }
+    NodeBase(const NodeBase& n) { value=n.value; ++instances; }
+    ~NodeBase() { --instances; }
+    bool operator==(const NodeBase& n) const { return value == n.value; }
+};
+
+int NodeBase::instances = 0;
+
+ostream& operator<<(ostream& o, const NodeBase& n) { return o << n.value; }
+
+struct Fixture {
+    struct Node : public NodeBase, public ISListNode<Node*> {
+        Node(char c) : NodeBase(c) {}
+    };
+    typedef ISList<Node> List;
+    Node a, b, c, d, e;
+    List l;
+    Fixture() :a('a'),b('b'),c('c'),d('d'),e('e') {}
+};
+
+BOOST_FIXTURE_TEST_CASE(default_ctor, Fixture) {
+    BOOST_CHECK(l.empty());
+    BOOST_CHECK(l.begin() == l.end());
+    BOOST_CHECK_EQUAL(0u, l.size());
+}
+
+BOOST_FIXTURE_TEST_CASE(push_front, Fixture) {
+    l.push_front(&a);
+    BOOST_CHECK_EQUAL(1u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    l.push_front(&b);
+    BOOST_CHECK_EQUAL(2u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(b)(a));
+}
+
+BOOST_FIXTURE_TEST_CASE(push_back, Fixture) {
+    l.push_back(&a);
+    BOOST_CHECK_EQUAL(1u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    l.push_back(&b);
+    BOOST_CHECK_EQUAL(2u, l.size());
+    BOOST_CHECK_EQUAL(l, list_of(a)(b));
+}
+
+BOOST_FIXTURE_TEST_CASE(insert, Fixture) {
+    List::iterator i(l.begin());
+    i = l.insert(i, &a);
+    BOOST_CHECK_EQUAL(l, list_of(a));
+    BOOST_CHECK(i == l.begin());
+
+    i = l.insert(i, &b);
+    BOOST_CHECK_EQUAL(l, list_of(b)(a));
+    BOOST_CHECK(i == l.begin());
+
+    i++;
+    BOOST_CHECK_EQUAL(*i, a);    
+    i = l.insert(i, &c);
+    BOOST_CHECK_EQUAL(l, list_of(b)(c)(a));
+    BOOST_CHECK_EQUAL(*i, c);
+
+    i = l.insert(i, &d);
+    BOOST_CHECK_EQUAL(l, list_of(b)(d)(c)(a));
+    BOOST_CHECK_EQUAL(*i, d);
+}
+
+BOOST_FIXTURE_TEST_CASE(iterator_test, Fixture) {
+    l.push_back(&a);
+    l.push_back(&b);
+    
+    List::iterator i = l.begin();
+    BOOST_CHECK_EQUAL(*i, a);
+    BOOST_CHECK_EQUAL(static_cast<Node*>(i), &a);
+    List::const_iterator ci = i;
+    BOOST_CHECK_EQUAL(static_cast<const Node*>(ci), &a);
+
+    i++;
+    BOOST_CHECK_EQUAL(*i, b);    
+    BOOST_CHECK_EQUAL(static_cast<Node*>(i), &b);
+    i++;
+    BOOST_CHECK(i == l.end());
+}
+
+BOOST_FIXTURE_TEST_CASE(pop_front, Fixture) {
+    l.push_back(&a);
+    l.push_back(&b);
+    l.pop_front();
+    BOOST_CHECK_EQUAL(l, list_of(b));
+    l.pop_front();
+    BOOST_CHECK(l.empty());
+}
+
+BOOST_FIXTURE_TEST_CASE(erase, Fixture) {
+    l.push_back(&a);
+    l.push_back(&b);
+    l.push_back(&c);
+
+    List::iterator i=l.begin();
+    i++;
+    l.erase(i);
+    BOOST_CHECK_EQUAL(l, list_of(a)(c));
+
+    i=l.begin();
+    i++;
+    l.erase(i);
+    BOOST_CHECK_EQUAL(l, list_of(a));
+
+    l.erase(l.begin());
+    BOOST_CHECK(l.empty());
+}
+
+
+// ================ Test smart pointer  types.
+
+template <class Node> void smart_pointer_test() {
+    typedef typename Node::pointer pointer;
+    typedef ISList<Node> List;
+    List l;
+
+    BOOST_CHECK_EQUAL(0, NodeBase::instances);
+    l.push_back(pointer(new Node()));
+    l.push_back(pointer(new Node()));
+    BOOST_CHECK_EQUAL(2, NodeBase::instances); // maintains a reference.
+        
+    pointer p = l.begin();
+    l.pop_front();
+    BOOST_CHECK_EQUAL(2, NodeBase::instances); // transfers ownership.
+    p = pointer();
+    BOOST_CHECK_EQUAL(1, NodeBase::instances); 
+
+    l.clear();
+    BOOST_CHECK_EQUAL(0, NodeBase::instances);
+    {                       // Dtor cleans up
+        List ll;
+        ll.push_back(pointer(new Node()));
+        BOOST_CHECK_EQUAL(1, NodeBase::instances);        
+    }
+    BOOST_CHECK_EQUAL(0, NodeBase::instances);
+}
+
+struct IntrusiveNode : public NodeBase, public RefCounted,
+                       public ISListNode<intrusive_ptr<IntrusiveNode> >
+{
+    IntrusiveNode() : NodeBase(0) {}
+};
+
+
+BOOST_AUTO_TEST_CASE(intrusive_ptr_test) {
+    smart_pointer_test<IntrusiveNode>();
+}
+
+
+struct SharedNode : public NodeBase, public ISListNode<boost::shared_ptr<SharedNode> > {
+    SharedNode() : NodeBase(0) {}
+};
+
+BOOST_AUTO_TEST_CASE(shared_ptr_test) {
+    smart_pointer_test<SharedNode>();
+}
+
+QPID_AUTO_TEST_SUITE_END()
diff --git a/cpp/src/tests/Makefile.am b/cpp/src/tests/Makefile.am
index 5d29f3d979..0e3a7d4ff6 100644
--- a/cpp/src/tests/Makefile.am
+++ b/cpp/src/tests/Makefile.am
@@ -36,7 +36,7 @@ unit_test_SOURCES= unit_test.cpp unit_test.h \
 	Url.cpp Uuid.cpp \
 	Shlib.cpp FieldValue.cpp FieldTable.cpp Array.cpp \
 	InlineVector.cpp \
-	IList.cpp \
+	ISList.cpp IList.cpp \
 	ClientSessionTest.cpp
 
 check_LTLIBRARIES += libshlibtest.la