1 files changed, 176 insertions, 0 deletions
diff --git a/qpid/cpp/src/qpid/ISList.h b/qpid/cpp/src/qpid/ISList.h
new file mode 100644
index 0000000000..96ba3ec726
--- /dev/null
+++ b/qpid/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*/