c++templateslinked-listcircular-dependencyintrusive-containers

C++ circular dependency with intrusive linked list


I've implemented this intrusive linked list:

template <class Entry>
struct LinkedListNode {
    Entry *next;
    Entry *prev;
};

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry * next (Entry *e) const;
    Entry * prev (Entry *e) const;
    void prepend (Entry *e);
    void append (Entry *e);
    void insertBefore (Entry *e, Entry *target);
    void insertAfter (Entry *e, Entry *target);
    void remove (Entry *e);

public:
    Entry *m_first;
    Entry *m_last;
};

...
template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
inline Entry * LinkedList<Entry, NodeMember>::next (Entry *e) const
{
    return (e->*NodeMember).next;
}
...

It can be used like this:

struct MyEntry {
    int value;
    LinkedListNode<MyEntry> list_node;
};

LinkedList<MyEntry, &MyEntry::list_node> list;
list.init();
MyEntry entry1, entry2;
entry1.value = 3;
list.append(&entry1);
entry2.value = 5;
list.prepend(&entry2);

It works all right, until you need two objects which contain lists of one another:

struct MyEntry2;

struct MyEntry1 {
    int value;
    LinkedListNode<MyEntry1> node;
    LinkedList<MyEntry2, &MyEntry2::node> list;
};

struct MyEntry2 {
    int value;
    LinkedListNode<MyEntry2> node;
    LinkedList<MyEntry1, &MyEntry1::node> list;
};

Each MyEntry1 holds a list of MyEntry2's, and each MyEntry2 can only appear in the list of one MyEntry1; and the converse. However, this doesn't compile, because the member pointer &MyEntry2::node is taken before MyEntry2 is defined:

prog.cpp:33:27: error: incomplete type 'MyEntry2' used in nested name specifier
prog.cpp:33:41: error: template argument 2 is invalid

There isn't really any practical semantic to this problematic layout, it is only a theoretical problem I've found which may limit the usability of the generic linked list.

Is there any way around this which doesn't make the list considerably more impractical?

EDIT: the layout of all data structures here is completely defined. This is because the data members of LinkedList do not depend on the problematic NodeMember template parameter; only the functions do. The problem seems to be that the language is demanding that &MyEntry2::node be known even though it does not really need to be known at the time.

EDIT: it must be possible to use this generic list to add a structure into two or more lists; this is the purpose of the NodeMember template parameter - it specifies which LinkedListNode within the entry is to be used.


Solution

  • Here is an implementation using inheritance that does not suffer from your problem.

    template <typename Entry>
    struct LinkedListNode {
        Entry *next;
        Entry *prev;
    };
    
    template <class Entry>
    class LinkedList {
    public:
        void init ();
        bool isEmpty () const;
        Entry * first () const;
        Entry * last () const;
        Entry* next (Entry* e) const {
            return e->next;  
        }
        Entry * prev (Entry *e) const;
        void prepend (Entry *e);
        void append (Entry *e);
        void insertBefore (Entry *e, Entry *target);
        void insertAfter (Entry *e, Entry *target);
        void remove (Entry *e);
    public:
        LinkedListNode<Entry> *m_first;
        LinkedListNode<Entry> *m_last;
    };
    
    struct MyEntry2;
    
    struct MyEntry1 : public LinkedListNode<MyEntry1> {
        int value;
        LinkedList<MyEntry2> list;
    };
    
    struct MyEntry2 : public LinkedListNode<MyEntry2> {
        int value;
        LinkedList<MyEntry1> list;
    };
    

    Here is a solution where the LinkedList has a functor as second template argument. We use an accessor functor with a templated operator() to remove code duplication and to delay look-up of the name. Note: The accessor should actually be a member and treated with an empty base optimization.

    template <class Entry>
    struct LinkedListNode {
        Entry *next;
        Entry *prev;
    };
    
    template <class Entry, typename Func>
    class LinkedList {
    public:
        void init ();
        bool isEmpty () const;
        Entry * first () const;
        Entry * last () const;
        Entry * next (Entry *e) const {
          Func f;
          return f(e).next();
        }
        Entry * prev (Entry *e) const;
        void prepend (Entry *e);
        void append (Entry *e);
        void insertBefore (Entry *e, Entry *target);
        void insertAfter (Entry *e, Entry *target);
        void remove (Entry *e);
    
    public:
        Entry *m_first;
        Entry *m_last;
    };
    
    struct MyEntry2;
    
    struct node_m_access {
      template <typename T>
      LinkedListNode<T> operator()(T* t) const {
        return t->node;
      }
    };
    
    struct MyEntry1 {
        int value;
        LinkedListNode<MyEntry1> node;
        LinkedList<MyEntry2, node_m_access> list;
    };
    
    struct MyEntry2 {
        int value;
        LinkedListNode<MyEntry2> node;
        LinkedList<MyEntry1, node_m_access> list;
    };