Intrusive list template qpid::IList and unit tests.

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

5 files changed, 433 insertions, 13 deletions

diff --git a/cpp/src/Makefile.am b/cpp/src/Makefile.am
index 99022e4e6c..a79f263c82 100644
--- a/cpp/src/Makefile.am
+++ b/cpp/src/Makefile.am
@@ -144,7 +144,8 @@ libqpidcommon_la_SOURCES = \
   qpid/Options.cpp \
   qpid/log/Options.cpp \
   qpid/log/Selector.cpp \
-  qpid/log/Statement.cpp
+  qpid/log/Statement.cpp \
+  qpid/IList.h
 
 libqpidbroker_la_LIBADD = libqpidcommon.la -lboost_iostreams
 libqpidbroker_la_SOURCES = \
diff --git a/cpp/src/qpid/IList.h b/cpp/src/qpid/IList.h
new file mode 100644
index 0000000000..5467a708d1
--- /dev/null
+++ b/cpp/src/qpid/IList.h
@@ -0,0 +1,175 @@
+#ifndef QPID_ILIST_H
+#define QPID_ILIST_H
+
+/*
+ *
+ * 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/RefCounted.h>
+#include <boost/iterator/iterator_facade.hpp>
+#include <boost/cast.hpp>
+#include <assert.h>
+
+namespace qpid {
+
+template <class T, int N> class IList;
+
+/**
+ * Base class providing links for a node in an IList.
+ * 
+ * Derived classes can inheirt multiple IListNode bases provided each
+ * has a unique value for N. This allows objects to be linked in
+ * multiple independent lists. For example:
+ *
+ * @code
+ * class Foo : public IListNode<0>, public IListNode<1> {};
+ * IList<Foo, 0> - uses the 0 links
+ * IList<Foo, 1> - uses the 1 links
+ *@endcode
+ */
+template<int N=0> class IListNode  : public virtual RefCounted {
+    intrusive_ptr<IListNode> prev;
+    intrusive_ptr<IListNode> next;
+    void insert(IListNode*);    
+    void erase();
+  template <class T, int NN> friend class IList;
+  public:
+    IListNode(IListNode* p=0) : prev(p), next(p) {}
+};
+
+/**
+ * Intrusive doubly linked list of reference counted nodes.
+ * 
+ *@param T must inherit from IListNode<N>
+ *@param N Identifies which links to use. @see IListNode.
+ */
+template <class T, int N=0> class IList {
+  private:
+    typedef IListNode<N> Node;
+
+    template <class R>
+    class Iterator :
+        public boost::iterator_facade<Iterator<R>,  R, boost::bidirectional_traversal_tag>
+    {
+        Node* ptr;                 // Iterators do not own their pointees.
+        void increment() { assert(ptr); ptr = ptr->next.get(); }
+        void decrement() { assert(ptr); ptr = ptr->prev.get(); }
+        R& dereference() const { assert(ptr); return *boost::polymorphic_downcast<R*>(ptr); }
+        bool equal(const Iterator<R>& x) const { return ptr == x.ptr; }
+
+        Node* cast(const Node* p) { return const_cast<Node*>(p); } 
+        explicit Iterator(const Node* p=0) : ptr(cast(p)) {}
+        explicit Iterator(const T* p=0) : ptr(cast(p)) {}
+
+      friend class boost::iterator_core_access;
+      friend class IList;
+
+      public:
+        template <class S> Iterator(const Iterator<S>& x) : ptr(x.ptr) {}
+    };
+
+  public:
+    IList() {}
+    ~IList() { clear(); }
+    typedef size_t size_type;
+    typedef T value_type;
+    /// pointer type is an intrusive_ptr
+    typedef intrusive_ptr<T> pointer;
+    /// pointer type is an intrusive_ptr
+    typedef intrusive_ptr<const T> const_pointer;
+    typedef value_type& reference;
+    typedef const value_type& const_reference;
+    typedef Iterator<value_type> iterator;
+    typedef Iterator<const value_type> const_iterator;
+
+    iterator begin() { return iterator(anchor.next.get()); }
+    iterator end() { return iterator(&anchor); }
+    const_iterator begin() const { return const_iterator(anchor.next.get()); }
+    const_iterator end() const { return const_iterator(&anchor); }
+    /// Iterator to the last element or end() if empty
+    iterator last() { return iterator(anchor.prev.get()); }
+    /// Iterator to the last element or end() if empty
+    const_iterator last() const { return const_iterator(anchor.prev.get()); }
+
+    /// Note: takes a non-const reference, unlike standard containers.
+    void insert(iterator pos, reference x) { x.IListNode<N>::insert(pos.ptr); }
+    void erase(iterator pos) { pos.ptr->erase(); }
+    void swap(IList &x) { anchor.swap(x.anchor); }
+
+    reference back() { assert(!empty()); return *last(); }
+    const_reference back() const { assert(!empty()); return *last(); }
+    void pop_back() { assert(!empty()); erase(last()); }
+    /// Note: takes a non-const reference, unlike standard containers.
+    void push_back(reference x) { insert(end(), x); }
+
+    reference front() { assert(!empty()); return *begin(); }
+    const_reference front() const { assert(!empty()); return *begin(); }
+    void pop_front() { assert(!empty()); erase(begin()); }
+    /// Note: takes a non-const reference, unlike standard containers.
+    void push_front(reference x) { insert(begin(), x); }
+
+    bool empty() const { return begin() == end(); }
+    void clear() { while (!empty()) { pop_front(); } }
+
+    size_type size() const {
+        size_type s=0;
+        for (const_iterator i = begin(); i != end(); ++i) ++s;
+        return s;
+    }
+
+    iterator erase(iterator from, iterator to) {
+        while(from != to) erase(from);
+    }
+
+  private:
+    // The list is circular and always contains an anchor node.
+    // end() points to the anchor, anchor.next is the first
+    // iterator, anchor.prev is the last iterator.
+
+    struct Anchor : public Node {
+        Anchor() : Node(this) {}
+        // Suppress refcounting for the anchor node.
+        void release() const {}
+    } anchor;          
+};
+
+template <int N>
+void IListNode<N>::insert(IListNode* node) {
+    assert(!next && !prev);     // Not already in a list.
+    assert(node);
+    assert(node->next && node->prev);
+    next=node;
+    prev=node->prev;
+    prev->next = this;
+    next->prev = this;
+}
+
+template <int N>
+void IListNode<N>::erase() {
+    assert(prev && next); 
+    intrusive_ptr<IListNode> self(this); // Protect till exit.
+    prev->next = next;
+    next->prev = prev;
+    prev = next = 0;
+}
+
+} // namespace qpid
+
+#endif  /*!QPID_ILIST_H*/
diff --git a/cpp/src/tests/IList.cpp b/cpp/src/tests/IList.cpp
new file mode 100644
index 0000000000..ed36228828
--- /dev/null
+++ b/cpp/src/tests/IList.cpp
@@ -0,0 +1,223 @@
+/*
+ *
+ * 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.
+ *
+ */
+
+
+#include "unit_test.h"
+#include "test_tools.h"
+#include "qpid/IList.h"
+#include <boost/assign/list_of.hpp>
+#include <vector>
+
+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)
+
+template <class T> bool operator==(const T& v, const intrusive_ptr<T>& p) { return v==*p; }
+
+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; }
+};
+int TestNode::instances = 0;
+ostream& operator<<(ostream& o, const TestNode& n) { return o << n.id; }
+
+struct SingleNode : public TestNode, public IListNode<> { 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);
+    }
+};
+
+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_CHECK(l.empty());
+
+    l.push_back(*a);
+    BOOST_CHECK_EQUAL(1u, l.size());
+    BOOST_CHECK(!l.empty());
+    BOOST_CHECK_EQUAL(l, list_of(a));
+
+    TestList::iterator i = l.begin();
+    BOOST_CHECK_EQUAL(*i, *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));
+
+    l.pop_back();
+    BOOST_CHECK_EQUAL(0u, l.size());
+    BOOST_CHECK(l.empty());
+}
+
+BOOST_FIXTURE_TEST_CASE(TestIterator, Fixture) {
+    {
+        TestList l;
+        l.push_back(*a);
+        l.push_back(*b);
+        l.push_back(*c);
+    
+        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_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);
+}
+
+struct MultiNode : public TestNode, public IListNode<0>, public IListNode<1>, public IListNode<2> {
+    MultiNode(char c) : TestNode(c) {}
+};
+
+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(TestMultiIList, MultiFixture) {
+    BOOST_CHECK_EQUAL(a->id, 'a');
+    push_back_all(a);
+    push_back_all(b);
+    push_back_all(c);
+
+    BOOST_CHECK_EQUAL(3, MultiNode::instances);
+
+    l0.pop_front();
+    l1.pop_back();
+    IList<MultiNode, 2>::iterator i = l2.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
+}
+
+QPID_AUTO_TEST_SUITE_END()
+
diff --git a/cpp/src/tests/Makefile.am b/cpp/src/tests/Makefile.am
index 87960145a4..5291891510 100644
--- a/cpp/src/tests/Makefile.am
+++ b/cpp/src/tests/Makefile.am
@@ -35,7 +35,8 @@ unit_test_SOURCES= unit_test.cpp unit_test.h \
 	SessionState.cpp Blob.cpp logging.cpp \
 	Url.cpp Uuid.cpp \
 	Shlib.cpp FieldValue.cpp FieldTable.cpp Array.cpp \
-	InlineVector.cpp
+	InlineVector.cpp \
+	IList.cpp
 
 check_LTLIBRARIES += libshlibtest.la
 libshlibtest_la_LDFLAGS = -module -rpath $(abs_builddir)
diff --git a/cpp/src/tests/test_tools.h b/cpp/src/tests/test_tools.h
index e564b9a473..2de4b6fbc1 100644
--- a/cpp/src/tests/test_tools.h
+++ b/cpp/src/tests/test_tools.h
@@ -22,21 +22,41 @@
 #include <boost/test/test_tools.hpp>
 #include <boost/assign/list_of.hpp>
 #include <boost/regex.hpp>
+#include <boost/assign/list_of.hpp>
 #include <vector>
+#include <ostream>
+
+// Print a sequence
+template <class T> std::ostream& seqPrint(std::ostream& o, const T& seq) {
+    std::copy(seq.begin(), seq.end(), std::ostream_iterator<typename T::value_type>(o, " "));
+    return o;
+}
+
+// Compare sequences 
+template <class T, class U>
+bool seqEqual(const T& a, const U& b) {
+    typename T::const_iterator i = a.begin();
+    typename U::const_iterator j = b.begin();
+    while (i != a.end() && j != b.end() && *i == *j) { ++i; ++j; }
+    return (i == a.end()) && (j == b.end());
+}
+
+// ostream and == operators so we can compare vectors and boost::assign::list_of
+// with BOOST_CHECK_EQUALS
+namespace std {                 // In namespace std so boost can find them.
+
+template <class T>
+ostream& operator<<(ostream& o, const vector<T>& v) { return seqPrint(o, v); }
+
+template <class T>
+ostream& operator<<(ostream& o, const boost::assign_detail::generic_list<T>& l) { return seqPrint(o, l); }
+
+template <class T>
+bool operator == (const vector<T>& a, const boost::assign_detail::generic_list<T>& b) { return seqEqual(a, b); }
 
-/** Stream operator so BOOST_CHECK_EQUALS works on vectors. */
-namespace std {
 template <class T>
-ostream& operator <<(ostream& o, const vector<T>& v) {
-    o << " {";
-    typename vector<T>::const_iterator i = v.begin();
-    if (i != v.end())
-        o << *i++;
-    while (i != v.end())
-        o << ", " << *i++;
-    return o << "}";
+bool operator == (const boost::assign_detail::generic_list<T>& b, const vector<T>& a) { return seqEqual(a, b); }
 }
-} // namespace std
 
 /** NB: order of parameters is regex first, in line with
  * CHECK(expected, actual) convention.