Navigate: Main, Up, Bottom

Intrusive Lists

Intrusive lists store the information about the list internal, not external to the listed entries. This means normally, that an entry is element of maximal one list. In the following we describe a templated implementation for single and double linked lists.

Single Linked

The following classes aid you in implementing intrusive single linked lists. SListEntry is used to store the pointer to the next element of a list, SListHead gives you access to the first element of a list and counts the number of list elements.

template< class T > class SListEntry {
private:
    SListEntry< T > *m_next;

public:
    SListEntry (void): 
        m_next (0) {}
    ~SListEntry (void) {}

    SListEntry< T > *GetNext (void) const {
        return m_next;
    }

    void Link (SListEntry< T > *next) {
        m_next = next;
    }
    void Unlink (void) {
        m_next = 0;
    }
};

template< class T > class SListHead {
private:
    unsigned m_count;
    SListEntry< T > *m_first;

public:
    SListHead (void): 
        m_count (0), m_first (0) {}
    ~SListHead (void) {}

    unsigned GetCount (void) const {
        return m_count;
    }
    SListEntry< T > *GetFirst (void) const {
        return m_first;
    }

    void Link (SListEntry< T > *that, SListEntry< T > *next = 0) {
        if (! next)
            next = m_first;
        ++ m_count;
        that->Link (next);
        if (! m_first || m_first == that->GetNext ())
            m_first = that;
    }
    void Unlink (SListEntry< T > *that) {
        if (m_first == that) 
            m_first = that->GetNext ();
        that->Unlink ();
        -- m_count;
    }
};

Double Linked

The following classes aid you in implementing intrusive double linked lists. DListEntry is used to store the pointer to the previous and next elements of a list, DListHead gives you access to the first and last element of a list and counts the number of list elements.

template< class T > class DListEntry {
private:
    DListEntry< T > *m_previous;
    DListEntry< T > *m_next;

public:
    DListEntry (void): 
        m_previous (0), m_next (0) {}
    ~DListEntry (void) {}

    DListEntry< T > *GetPrevious (void) const {
        return m_previous;
    }
    DListEntry< T > *GetNext (void) const {
        return m_next;
    }

    void Link (DListEntry< T > *previous, DListEntry< T > *next) {
        m_previous = previous;
        m_next = next;
        if (m_previous)
            m_previous->m_next = this;
        if (m_next)
            m_next->m_previous = this;
    }
    void Unlink (void) {
        if (m_previous)
            m_previous->m_next = m_next;
        if (m_next)
            m_next->m_previous = m_previous;
        m_previous = 0;
        m_next = 0;
    }
};

template< class T > class DListHead {
private:
    unsigned m_count;
    DListEntry< T > *m_first;
    DListEntry< T > *m_last;

public:
    DListHead (void): 
        m_count (0), m_first (0), m_last (0) {}
    ~DListHead (void) {}

    unsigned GetCount (void) const {
        return m_count;
    }
    DListEntry< T > *GetFirst (void) const {
        return m_first;
    }
    DListEntry< T > *GetLast (void) const {
        return m_last;
    }

    void Link (DListEntry< T > *that, DListEntry< T > *previous = 0, DListEntry< T > *next = 0) {
        if (! previous) 
            next = m_first;
        ++ m_count;
        that->Link (previous, next);
        if (! m_first || m_first == that->GetNext ())
            m_first = that;
        if (! m_last || m_last == that->GetPrevious ())
            m_last = that;
    }
    void Unlink (DListEntry< T > *that) {
        if (m_first == that) 
            m_first = that->GetNext ();
        if (m_last == that) 
            m_last = that->GetPrevious ();
        that->Unlink ();
        -- m_count;
    }
};

Navigate: Main, Up, Top