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

7 files changed, 710 insertions, 336 deletions

diff --git a/cpp/src/Makefile.am b/cpp/src/Makefile.am
index d2242c2695..a785103b34 100644
--- a/cpp/src/Makefile.am
+++ b/cpp/src/Makefile.am
@@ -145,7 +145,9 @@ libqpidcommon_la_SOURCES = \
   qpid/log/Options.cpp \
   qpid/log/Selector.cpp \
   qpid/log/Statement.cpp \
-  qpid/IList.h
+  qpid/IList.h \
+  qpid/ISList.h \
+  qpid/pointer_to_other.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
index 4593b9a5e1..f5c78ced68 100644
--- a/cpp/src/qpid/IList.h
+++ b/cpp/src/qpid/IList.h
@@ -22,170 +22,174 @@
  *
  */
 
-#include <qpid/RefCounted.h>
-#include <boost/iterator/iterator_facade.hpp>
-#include <boost/cast.hpp>
-#include <assert.h>
+#include "ISList.h"
 
 namespace qpid {
 
-template <class T, int N> class IList;
+template <class> 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
- *
- *@param T The derived class.
- *@param N ID for multiple inheritance.
+/** Base class for values (nodes) in an IList.
+ *@param raw or smart-pointer type to use for the "next" pointer.
+ * Using a smart pointer like shared_ptr or intrusive_ptr 
+ * will automate memory management.
  */
-template<class T, int N=0> class IListNode  : public virtual RefCounted {
-    intrusive_ptr<IListNode> prev;
-    intrusive_ptr<IListNode> next;
-    void insert(IListNode*);    
-    void erase();
-    virtual T* self() const {   // Virutal so anchor can hide.
-        return boost::polymorphic_downcast<T*>(const_cast<IListNode*>(this));
-    }
-  friend class IList<T,N>;
+template <class Pointer> class IListNode {
   public:
-    typedef IList<T,N> IListType;
+    typedef Pointer pointer; 
+    typedef typename Pointee<Pointer>::type  NodeType;
+    typedef typename pointer_to_other<Pointer, const NodeType>::type const_pointer;
     
-    IListNode(IListNode* p=0) : prev(p), next(p) {}
-    T* getNext() { return next ? next->self() : 0; }
-    T* getPrev() { return prev ? prev->self() : 0; }
-    const T* getNext() const { return next ? next->self() : 0; }
-    const T* getPrev() const { return prev ? prev->self() : 0; }
+  protected:
+    IListNode() : prev() {}
+    IListNode(const IListNode&) {} // Don't copy next/prev pointers
+
+    pointer getNext() { return next; }
+    const_pointer getNext() const { return next; }
+    pointer getPrev() { return prev; }
+    const_pointer getPrev() const { return prev; }
+
+  private:
+    pointer prev, next;
+  friend class IList<NodeType>;
 };
 
+
 /**
- * Intrusive doubly linked list of reference counted nodes.
+ * Intrusive doubly-linked list.
+ * 
+ * Provides bidirectional iterator and constant time insertion
+ * at front and back.
+ *
+ * The list itself performs no memory management. Use a smart pointer
+ * as the pointer type (e.g. intrusive_ptr, shared_ptr) for automated
+ * memory management.
+ *
+ * Unlike standard containers insert(), push_front() and push_back()
+ * take const pointer& rather than const value_type&.
+ *
+ * Iterators can be converted to the pointer type.
+ *
+ * Noncopyable - intrusively linked nodes cannot be shared between
+ * lists. Does provide swap()
  * 
- *@param T must inherit from IListNode<N>
- *@param N Identifies which links to use. @see IListNode.
+ * @param Node value type for the list, must derive from ISListNode<>.
  */
-template <class T, int N=0> class IList {
-  private:
-    typedef IListNode<T,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) {}
-    };
-
+template<class Node> class IList {
+    template <class> class Iterator;
   public:
-    IList() {}
-    ~IList() { clear(); anchor.erase(); }
-    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 Node value_type;
+    typedef typename Node::pointer pointer;
+    typedef typename Node::const_pointer const_pointer;
     typedef value_type& reference;
     typedef const value_type& const_reference;
+    typedef size_t size_type;
+    typedef ptrdiff_t difference_type;
     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.Node::insert(pos.ptr); }
-    void insert(iterator pos, pointer x) { x->Node::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); }
-    void push_back(pointer 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); }
-    void push_front(pointer x) { insert(begin(), x); }
+    IList() : begin_(), last_() {}
+
+    iterator begin() { return begin_; }
+    const_iterator begin() const { return begin_; }
+    iterator end() { return 0; }
+    const_iterator end() const { return 0; }
 
     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;
+        int s = 0;
+        for (const_iterator i=begin(); i != end(); ++i)
+            ++s;
         return s;
     }
+    
+    void swap(IList &x) { swap(begin_, x.begin_); swap(last_, x.last_); }
+
+    iterator insert(iterator i, const pointer& p) {
+        if (empty()) {
+            begin_ = last_ = p;
+            insert(0, p, 0);
+        }
+        else if (i) {
+            insert(i->prev, p, i);
+            if (i == begin_) --begin_;
+        }
+        else {
+            insert(last_, p, 0) ;
+            last_ = p;
+        }
+        return p;
+    }
 
-    iterator erase(iterator from, iterator to) {
-        while(from != to) erase(from);
+    void erase(iterator i) {
+        if (begin_ == last_)
+            begin_ = last_ = 0;
+        else {
+            if (i == begin_) ++begin_;
+            else i->prev->next = i->next;
+            if (i == last_) --last_;
+            else i->next->prev = i->prev;
+        }
+        i->prev = i->next = pointer(0);
     }
 
+    void erase(iterator i, iterator j) { while(i != j) erase(i); }
+    void clear() { while (!empty()) { erase(begin()); } }
+
+    reference front() { return *begin(); }
+    const_reference front() const { return *begin(); }
+    void push_front(const pointer& p) { insert(begin(), p); }
+    void pop_front() { erase(begin()); }
+
+    /** Iterator to the last element in the list. */
+    iterator last() { return last_; }
+    const_iterator last() const { return last_; }
+
+    reference back() { return *last(); }
+    const_reference back() const { return *last(); }
+    void push_back(const pointer& p) { insert(end(), p); }
+    void pop_back() { erase(last()); }
+
   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 {}
-        // Hide anchor from public get functions.
-        T* self() const { return 0; }
-    } anchor;          
-};
+    void insert(pointer a, pointer b, pointer c) {
+        b->prev = a;
+        if (a) a->next = b;
+        b->next = c;
+        if (c) c->prev = b;
+    }
+    
+    template <class T>
+    class Iterator : public boost::iterator_facade<
+      Iterator<T>, T, boost::bidirectional_traversal_tag>
+    {
+      public:
+        Iterator() : ptr() {};
+
+        template <class U> Iterator(
+            const Iterator<U>& i,
+            typename boost::enable_if_convertible<U*, T*>::type* = 0
+        ) : ptr(i.ptr) {}
+
+        operator pointer() { return ptr; }
+        operator const_pointer() const { return ptr; }
+        
+      private:
+      friend class boost::iterator_core_access;
+
+        Iterator(const_pointer p) : ptr(const_cast<pointer>(p)) {};
 
-template <class T, int N>
-void IListNode<T,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 <class T, int N>
-void IListNode<T,N>::erase() {
-    assert(prev && next); 
-    intrusive_ptr<IListNode> save(this); // Protect till exit.
-    prev->next = next;
-    next->prev = prev;
-    prev = next = 0;
-}
+        T& dereference() const { return *ptr; }
+        void increment() { ptr = ptr->next; }
+        void decrement() { ptr = ptr->prev; }
+        bool equal(const Iterator& x) const { return ptr == x.ptr; }
+
+        pointer ptr;
+
+      friend class IList<Node>;
+    };
+
+    iterator begin_, last_;
+};
 
 } // namespace qpid
 
diff --git a/cpp/src/qpid/ISList.h b/cpp/src/qpid/ISList.h
new file mode 100644
index 0000000000..96ba3ec726
--- /dev/null
+++ b/cpp/src/qpid/ISList.h
@@ -0,0 +1,176 @@
+#ifndef QPID_ISLIST_H
+#define QPID_ISLIST_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 <boost/iterator/iterator_adaptor.hpp>
+#include <boost/noncopyable.hpp>
+#include "pointer_to_other.h"
+
+namespace qpid {
+
+template <class Pointer> struct Pointee {
+    typedef typename Pointer::element_type type;
+};
+
+template <class T> struct Pointee<T*> {
+    typedef T type;
+};
+
+template <class> class ISList;
+template <class> class IList;
+
+/** Base class for values (nodes) in an ISList.
+ *@param raw or smart-pointer type to use for the "next" pointer.
+ * Using a smart pointer like shared_ptr or intrusive_ptr 
+ * will automate memory management.
+ */
+template <class Pointer> class ISListNode {
+  public:
+    typedef Pointer pointer; 
+    typedef typename Pointee<Pointer>::type  NodeType;
+    typedef typename pointer_to_other<Pointer, const NodeType>::type const_pointer;
+    
+  protected:
+    ISListNode() : next() {}
+    ISListNode(const ISListNode&) {} // Don't copy the next pointer.
+
+    pointer getNext() { return next; }
+    const_pointer getNext() const { return next; }
+
+  private:
+    pointer next;
+  friend class ISList<NodeType>;
+};
+
+
+/**
+ * Intrusive singly-linked list.
+ * 
+ * Provides forward iterator, constant time insertion and constant
+ * time pop_front (but not pop_back) so makes a good queue
+ * implementation.
+ *
+ * Unlike standard containers insert(), push_front() and push_back()
+ * take const pointer& rather than const value_type&.
+ *
+ * Iterators can be converted to pointers.
+ *
+ * Noncopyable - intrusively linked nodes cannot be shared.
+ * 
+ * @param Node value type for the list, must derive from ISListNode<T>.
+ */
+template <class Node> class ISList : private boost::noncopyable {
+    template <class> class Iterator;
+  public:
+    typedef Node value_type;
+    typedef typename Node::pointer pointer;
+    typedef typename Node::const_pointer const_pointer;
+    typedef value_type& reference;
+    typedef const value_type& const_reference;
+    typedef size_t size_type;
+    typedef ptrdiff_t difference_type;
+    typedef Iterator<value_type> iterator;
+    typedef Iterator<const value_type> const_iterator;
+
+    ISList() : first(pointer()), end_(&first) {}
+
+    iterator begin() { return iterator(&first); }
+    const_iterator begin() const { return const_iterator(&first); }
+    iterator end() { return end_; }
+    const_iterator end() const { return end_; }
+
+    bool empty() const { return begin() == end(); }
+
+    size_type size() const {
+        int s = 0;
+        for (const_iterator i=begin(); i != end(); ++i)
+            ++s;
+        return s;
+    }
+    
+    void swap(ISList &x) { swap(first, x.first); swap(end_, x.end_); }
+
+    /** Unlike standard containers, insert takes a const pointer&, not a
+     * const value_type&. The value is not copied, only linked into the list.
+     */
+    iterator insert(iterator i, const pointer& p) {
+        p->next = *(i.pptr);
+        *(i.pptr) = p;
+        if (i==end_) ++end_;
+        return i;
+    }
+    
+    void erase(iterator i) {
+        if (&i->next == end_.pptr)
+            end_ = i;
+        *(i.pptr) = (**(i.pptr)).next;
+    }
+
+    void erase(iterator i, iterator j) { while(i != j) erase(i); }
+    void clear() { while (!empty()) { erase(begin()); } }
+
+    reference front() { return *begin(); }
+    const_reference front() const { return *begin(); }
+    void pop_front() { erase(begin()); }
+    void push_front(pointer x) { insert(begin(), x); }
+
+    void push_back(pointer x) { insert(end(), x); }
+
+  private:
+    template <class T>
+    class Iterator : public boost::iterator_facade <
+      Iterator<T>, T, boost::forward_traversal_tag>
+    {
+      public:
+        Iterator() {};
+
+        template <class U> Iterator(
+            const Iterator<U>& i,
+            typename boost::enable_if_convertible<U*, T*>::type* = 0
+        ) : pptr(i.pptr) {}
+
+        operator pointer() { return *pptr; }
+        operator const_pointer() const { return *pptr; }
+        
+      private:
+      friend class boost::iterator_core_access;
+
+        Iterator(const pointer* pp) : pptr(const_cast<pointer*>(pp)) {};
+
+        T& dereference() const { return **pptr; }
+        void increment() { pptr = &(**pptr).next; }
+        bool equal(const Iterator& x) const { return pptr == x.pptr; }
+
+        pointer* pptr;
+
+      friend class ISList<Node>;
+    };
+
+  private:
+    pointer first;
+    iterator end_;
+};
+
+} // namespace qpid
+
+#endif  /*!QPID_ISLIST_H*/
diff --git a/cpp/src/qpid/pointer_to_other.h b/cpp/src/qpid/pointer_to_other.h
new file mode 100644
index 0000000000..a99dc89658
--- /dev/null
+++ b/cpp/src/qpid/pointer_to_other.h
@@ -0,0 +1,62 @@
+#ifndef QPID_POINTERTOOTHER_H
+#define QPID_POINTERTOOTHER_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.
+ *
+ */
+
+namespace qpid {
+
+// Defines the same pointer type (raw or smart) to another pointee type
+
+template<class T, class U>
+struct pointer_to_other;
+
+template<class T, class U,
+                  template<class> class Sp>
+struct pointer_to_other< Sp<T>, U >
+                  {
+                      typedef Sp<U> type;
+                  };
+
+template<class T, class T2, class U,
+         template<class, class> class Sp>
+struct pointer_to_other< Sp<T, T2>, U >
+         {
+             typedef Sp<U, T2> type;
+         };
+
+template<class T, class T2, class T3, class U,
+         template<class, class, class> class Sp>
+struct pointer_to_other< Sp<T, T2, T3>, U >
+         {
+             typedef Sp<U, T2, T3> type;
+         };
+
+template<class T, class U>
+struct pointer_to_other< T*, U >
+{
+    typedef U* type;
+};
+
+} // namespace qpid
+
+
+
+#endif  /*!QPID_POINTERTOOTHER_H*/
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