jeudi 9 juin 2022

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

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?

Aucun commentaire:

Enregistrer un commentaire