intrusive_list.hpp

#ifndef SRC_INC_INTRUSIVE_LIST_HPP
#define SRC_INC_INTRUSIVE_LIST_HPP

#include <boost/iterator/iterator_facade.hpp>
#include <boost/concept_check.hpp>

namespace std
{

template<class T>
struct LinkableConcept
{
    void constraints ()
    {
        srl->next = srl->prior;
        srl->prior = srl->next;
        srl->next = srl;
    }
    
    T* srl;
};

} // namespace std

namespace GCpp
{

template <class T>
class IntrusiveListIterator : public boost::iterator_facade
<
    IntrusiveListIterator<T>,
    T,
    boost::bidirectional_traversal_tag
>
{
    private:
        mutable T f_current;
    
        void increment ()
        {
            f_current = f_current->next;
        }

        void decrement ()
        {
            f_current = f_current->prior;
        }

        bool equal (const IntrusiveListIterator<T>& p_other) const
        {
            return this->f_current == p_other.f_current;
        }

        T& dereference () const
        {
            return f_current;
        }
        
        friend class boost::iterator_core_access;
    
    public:
        IntrusiveListIterator ()
        : f_current (0)
        {}
        
        explicit IntrusiveListIterator (T p_item)
        : f_current (p_item)
        {}
};

template <class T>
class IntrusiveList
{
    BOOST_CLASS_REQUIRE(T, std, LinkableConcept);
    
    public:
        typedef IntrusiveListIterator<T*> iterator;
        typedef IntrusiveListIterator<const T*> const_iterator;
        
    private:
        T* f_root;
        T* f_tail;
        
        void remove_node (T* p_item)
        {
            bool fin (false);
            
            if (f_root == p_item)
            {
                fin = true;
                f_root = f_root->next;
                
                if (f_root)
                    f_root->prior = 0;
            }
            
            if (f_tail == p_item)
            {
                fin = true;
                f_tail = p_item->prior;
                
                if (f_tail)
                    f_tail->next = 0;
            }
            
            if (not fin)
            {
                if (p_item->prior)
                    p_item->prior->next = p_item->next;
            
                if (p_item->next)
                    p_item->next->prior = p_item->prior;
            }
        }
    
    public:
        IntrusiveList ()
        : f_root (0),
          f_tail (0)
        {}
        
        ~IntrusiveList ()
        {
            f_root = 0;
            f_tail = 0;
        }
        
        bool empty () const
        {
            return f_root == 0;
        }
        
        void push_back (T* p_item)
        {
            if (f_root == 0)
            {
                f_root = p_item;
                f_tail = p_item;
                p_item->next = 0;
                p_item->prior = 0;
            }
            else
            {
                f_tail->next = p_item;
                p_item->prior = f_tail;
                p_item->next = 0;
                f_tail = p_item;
            }
        }
        
        iterator erase (iterator p_loc)
        {
            if (p_loc != end ())
            {
                T* cur (*p_loc);
                ++p_loc;
                remove_node (cur);
            }
            
            return p_loc;
        }
        
        void remove (T* p_item)
        {
            remove_node (p_item);
        }
        
        void insert (iterator p_loc, T* p_item)
        {
            T* cur (*p_loc);
            p_item->next = cur;
            
            if (cur)
            {
                if (cur->prior)
                    cur->prior->next = p_item;
                
                p_item->prior = cur->prior;
                cur->prior = p_item;
                
                if (cur == f_root)
                {
                    f_root = p_item;
                    f_root->prior = 0;
                }
            }
            else
            {
                p_item->prior = f_tail;
                
                if (f_tail)
                    f_tail->next = p_item;
                
                f_tail = p_item;
                
                if (f_root == 0)
                    f_root = p_item;
            }
        }
        
        void clear ()
        {
            f_root = 0;
            f_tail = 0;
        }
        
        size_t size ()
        {
            T* cur (f_root);
            size_t res (0);
            
            while (cur)
            {
                ++res;
                cur = cur->next;
            }
            
            return res;
        }
        
        iterator begin ()
        {
            return iterator (f_root);
        }
        
        const_iterator begin () const
        {
            return const_iterator (f_root);
        }
        
        iterator end ()
        {
            return iterator ();
        }
        
        const_iterator end () const
        {
            return const_iterator ();
        }

        T* root () const
        {
            return f_root;
        }
        
        T* tail () const
        {
            return f_tail;
        }
};

} // namespace GCpp

#endif /* SRC_INC_INTRUSIVE_LIST_HPP */

---