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

1 files changed, 175 insertions, 0 deletions

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*/