C++ circular dependency with intrusive linked list

Question

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.

Answer 1

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;
};

Answer 2

This problem is equivalent to trying to do:

struct MyEntry2;

struct MyEntry1 {
    MyEntry2 a;
};

struct MyEntry2 {
    MyEntry1 b;
};

In the above case, the compiler needs to know the size of the MyEntry2 struct when generating MyEntry1. In your case, the compiler needs to know the offset of node in MyEntry2 while generating MyEntry1.

I'm not experienced in template-foo but I would guess that instead of making Entry a class, you want to use a pointer to a class.

Answer 3

Here's a small modification of pmr's accessor solution to reduce the amount of boilerplate. The trick is to first provide an incomplete "struct" declaration of the accessors, instantiate the LinkedList's with these, and later complete the accessors by inheriting from a template accessor class.

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

template <class Entry, class Accessor>
class LinkedList {
public:
    void init ();
    bool isEmpty () const;
    Entry * first () const;
    Entry * last () const;
    Entry * next (Entry *e) const {
        return Accessor::access(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;
};

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
struct LinkedListAccessor {
    static LinkedListNode<Entry> & access (Entry *e)
    {
        return e->*NodeMember;
    }
};

struct MyEntry2;
struct Accessor1;
struct Accessor2;

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

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

struct Accessor1 : LinkedListAccessor<MyEntry1, &MyEntry1::node> {};
struct Accessor2 : LinkedListAccessor<MyEntry2, &MyEntry2::node> {};

With this, a convenience class can even be made for when there is no problem with the circular dependency:

template <class Entry, LinkedListNode<Entry> Entry::*NodeMember>
class SimpleLinkedList
: public LinkedList<Entry, LinkedListAccessor<Entry, NodeMember> >
{};