How to implement intrusive data structures in C++11?

Question

I am porting to C++11 a C code base that makes use of a number of custom intrusive data structures.

In C, the usage patterns will typically look like this:

struct foo {
  // some members
  struct data_structure_node node;
};

// user code

struct *foo = NULL;
struct data_structure_node *result = find_in_data_structure(data_structure, some_key);
if (node) {
  foo = container_of(result, struct data_structure_node, node);
  // use foo
}

Here, container_of is implemented much like in the Linux kernel:

#define container_of(ptr, type, member) ({                      \
        const typeof( ((type *)0)->member ) *__mptr = (ptr);    \
        (type *)( (char *)__mptr - offsetof(type,member) );})

As the code moves to more idiomatic C++, structures like foo typically end up becoming classes that use different access controls, virtual functions, etc. This, in turn, makes them adopt a non standard layout and causes GCC and clang to emit the following warning when container_of is used:

error: 'offsetof' within non-standard-layout type 'foo' is conditionally-supported [-Werror=invalid-offsetof]

I have been pondering how to implement a safe alternative to the container_of macro. Using a pointers to data member is the first idea that came to my mind and I'm considering replacing uses of container_of by, essentially,

template <class Parent, class Member>
Parent* my_container_of(Member *member, Member Parent::* ptr_to_member)
{
    Parent *dummy_parent = nullptr;
    auto *offset_of_member = reinterpret_cast<char *>(&(dummy_parent->*ptr_to_member));
    auto address_of_parent = reinterpret_cast<char *>(member) - offset_of_member;

    return reinterpret_cast<Parent *>(address_of_parent);
}

to get struct foo * from a struct data_structure_node *.

In particular, the use of ptr_to_member against the null dummy_parent makes me uneasy as it seems equivalent to performing arithmetic on a null pointer, which I understand is undefined behavior (C++11 Standard 5.7.5).

[...] Unless both pointers point to elements of the same array object, or one past the last element of the array object, the behavior is undefined

Boost.Instrusive uses an approach that seems roughly equivalent to my_container_of().

I'm wondering:

• is my_container_of() safe?
• is there a cleaner way of achieving this that I'm missing?

Answer 1

You can do intrusive data structures in C++ even nicer than C. The first thing is to use inheritance. So you try this:

struct List {
    List *next{nullptr};
};

struct MyFoo : List {
    MyFoo * get_next() const { return next; }
};

But there you get an error that next is a List* and not a MyFoo *. To fix this you can introduce templates:

template <typename T>
struct List {
    T *next{nullptr};
};

struct MyFoo : List<MyFoo> {
    MyFoo * get_next() const { return next; }
};

Now your intrusive list has the right type for the next. But you are limited to one intrusive list per object. So lets extend the template a bit more:

template <typename T, typename U>
struct List {
    T *next{nullptr};
};

class Siblings;
class Children;

struct MyFoo : List<MyFoo, Siblings>, List<MyFoo, Children> {
    using Sibling = List<MyFoo, Siblings>;
    using Child = List<MyFoo, Children>;
    MyFoo * get_sibling() const { return Sibling::next; }
    MyFoo * get_child() const { return Child::next; }
};

Now you can inherit as many List as you want into a class and scoping the access to access the right List. No need of any offset() or container_of macros.

Note: The Siblings and Children classes are just declarations and purely there to give the List different types. They are never defined or instantiated.

Answer 2

Yes, You can implement intrusive data structure by CRTP. Here is an example of intrusive list.

template <typename subtype, typename tag>
struct ilist {
    ilist *prev;
    ilist *next;

    ilist() : prev{this}, next{this} {}

    subtype* self(void) noexcept { return static_cast<subtype*>(this); }
    const subtype* self(void) const noexcept { return static_cast<const subtype*>(this); }

    void link_between(ilist& prev, ilist& next) noexcept {
        this->prev = &prev;
        this->next = &next;
        prev.next = this;
        next.prev = this;
    }

    void add(ilist& node) noexcept {
        node.link_between(*this, *next);
    }
};

And then define your foo struct which contains an integer and two intrusive list.

struct plink;
struct qlink;

struct foo : ilist<foo, plink>, ilist<foo, qlink> {
    int value;

    foo(int value = 0) : value{value} {}
};

And then you can use ilist<foo, plink> and ilist<foo, qlink> to manage your intrusive lists.

foo a{0}, b{1}, c{2};
ilist<foo, plink> p;
ilist<foo, qlink> q;

p.add(a); p.add(b); p.add(c); // p contains a, b and c

q.add(a); q.add(c); // q contains a and c

for (auto it = p.next; it != &p; it = it->next) {
    foo* f = it->self();
    // do something on foo f
}

Godbolt demo: https://godbolt.org/z/o56hYob86