Intrusive list templates

LinkedList.h

/*
 *  LinkedList.h
 */

#include <assert.h>

template <class C, int N=0>
class Linked
{
    Linked* m_next;
    
public:
    Linked() : m_next(0) {}
    
    class List
    {
        Linked* m_head;
        
    public:
        List() : m_head(0) {}
        class Range {
            Linked* m_item;
        public:
            Range(const List& list) : m_item(list.m_head) {}
            C* front() const { return static_cast<C*>(m_item); }
            bool empty() const { return m_item == 0; }
            void popFront() { m_item = m_item->m_next; }
        };
        
        List& addFront(C *item_) {
            Linked *item = item_;
            assert(item->m_next == 0);
            item->m_next = m_head;
            m_head = item;
            return *this;
        }
        
        C* removeFront() {
            if (m_head == 0)
                return 0;
            Linked *item = m_head;
            m_head = item->m_next;
            return static_cast<C*>(item);
        }
        
        void remove(C *item_) {
            Linked* item = item_;
            
            for (Linked** p = &m_head; *p; p = &((*p)->m_next)) {
                if (*p == item) {
                    *p = item->m_next;
                    item->m_next = 0;
                    return;
                }
            }
            assert(!"item not in list");
        }
    };
};

template <class C, int N=0>
class DblLinked
{
    DblLinked* m_next;
    DblLinked* m_prev;
    
public:
    DblLinked() : m_next(0), m_prev(0) {}
    
    class List
    {
        DblLinked* m_head;
        DblLinked* m_tail;
        
    public:
        List() : m_head(0), m_tail(0) {}

        class Range
        {
            DblLinked* m_front;
            DblLinked* m_back;
            
        public:
            Range(const List& list) : m_front(list.m_head), m_back(list.m_tail) {}
            bool empty() const { return m_front == 0; }
            C* front() const { return static_cast<C*>(m_front); }
            void popFront() { m_front = m_front->m_next; if (!m_front) m_back = 0; }
            C* back() const { return static_cast<C*>(m_back); }
            void popBack() { m_back = m_back->m_prev; if (!m_back) m_front = 0; }
        };
        
        List& addFront(C *item_) {
            DblLinked *item = item_;
            assert(item->m_next == 0 && item->m_prev == 0);
            item->m_next = m_head;
            if (m_head)
                m_head->m_prev = item;
            else
                m_tail = item;
            m_head = item;
            return *this;
        }
        
        C* removeFront() {
            if (m_head == 0)
                return 0;
            DblLinked *item = m_head;
            m_head = item->m_next;
            if (m_head)
                m_head->m_prev = 0;
            else 
                m_tail = 0;
            return static_cast<C*>(item);
        }
        
        List& addBack(C *item_) {
            DblLinked *item = item_;
            assert(item->m_next == 0 && item->m_prev == 0);
            item->m_prev = m_tail;
            if (m_tail)
                m_tail->m_next = item;
            else
                m_head = item;
            m_tail = item;
            return *this;
        }
        
        C* removeBack() {
            if (m_tail == 0)
                return 0;
            DblLinked *item = m_tail;
            m_tail = item->m_prev;
            if (m_tail)
                m_tail->m_next = 0;
            else 
                m_head = 0;
            return static_cast<C*>(item);
        }
        
        void remove(C *item_) {
            DblLinked *item = item_;
            assert((item->m_prev == 0) == (m_head == item));
            assert((item->m_next == 0) == (m_tail == item));
            if (item == m_head) {
                m_head = item->m_next;
                if (m_head)
                    m_head->m_prev = 0;
                else 
                    m_tail = 0;
            }
            else if (item == m_tail) {
                m_tail = item->m_prev;
                if (m_tail)
                    m_tail->m_next = 0;
                else 
                    m_head = 0;
            }
            else {
                item->m_next->m_prev = item->m_prev;
                item->m_prev->m_next = item->m_next;
            }
            item->m_next = item->m_prev = 0;
        }
    };
};

main.cpp

#include <iostream>
#include "LinkedList.h"

using namespace std;

struct Foo: public Linked<Foo>, public Linked<Foo,1>, public DblLinked<Foo>, public DblLinked<Foo,1>
{
public:
    Foo(const char *s) : s(s) {}
    const char * const s;
};

int main (int argc, char * const argv[]) {
    Foo a("a"), b("b"), c("c"), d("d");
    Linked<Foo>::List list1;
    Linked<Foo,1>::List list2;
    DblLinked<Foo>::List list3;
    DblLinked<Foo,1>::List list4;
    
    list1.addFront(&a).addFront(&b).addFront(&c).addFront(&d);
    list2.addFront(&a).addFront(&c).addFront(&b).addFront(&d);
    list3.addFront(&a).addBack(&b).addFront(&c).addBack(&d);
    list4.addFront(&a).addBack(&c).addFront(&b).addBack(&d);
    
    cout << "list1:";
    for (Linked<Foo>::List::Range r(list1); !r.empty(); r.popFront())
        cout << " " << r.front()->s;
    cout << endl;
    
    cout << "removing \"c\"" << endl;
    list1.remove(&c);
    
    cout << "removing list1:";
    while (Foo* item = list1.removeFront())
        cout << " " << item->s;
    cout << endl;
    
    cout << "list2:";
    for (Linked<Foo,1>::List::Range r(list2); !r.empty(); r.popFront())
        cout << " " << r.front()->s;
    cout << endl;
    
    cout << "removing \"c\"" << endl;
    list2.remove(&c);
    cout << "removing list2:";
    while (Foo* item = list2.removeFront())
        cout << " " << item->s;
    cout << endl;
    
    cout << "list3:";
    for (DblLinked<Foo>::List::Range r(list3); !r.empty(); r.popFront())
        cout << " " << r.front()->s;
    cout << endl;
    
    cout << "list3 backward:";
    for (DblLinked<Foo>::List::Range r(list3); !r.empty(); r.popBack())
        cout << " " << r.back()->s;
    cout << endl;
    
    cout << "removing \"c\"" << endl;
    list3.remove(&c);
    
    cout << "removing list3:";
    while (Foo* item = list3.removeFront())
        cout << " " << item->s;
    cout << endl;
    
    cout << "list4:";
    for (DblLinked<Foo,1>::List::Range r(list4); !r.empty(); r.popFront())
        cout << " " << r.front()->s;
    cout << endl;
    
    cout << "list4 backward:";
    for (DblLinked<Foo,1>::List::Range r(list4); !r.empty(); r.popBack())
        cout << " " << r.back()->s;
    cout << endl;
    
    cout << "removing \"c\"" << endl;
    list4.remove(&c);
    
    cout << "removing list4 backward:";
    while (Foo* item = list4.removeBack())
        cout << " " << item->s;
    cout << endl;
    
    return 0;
}

Jiri Soukup wrote a whole book on how to implement intrusive lists in C++. In the end he resorted to writing a preprocessor to massage an augmented syntax into C++ because he didn't know about the CRTP.

This little doodle shows how to do it using plain old C++.