C macro magic

Today we’ll look at the implementation of a data structure wl_list, it belongs to the wayland library and demonstrates a very clever use of the  C preprocessor.

wl_list

It’s a simple doubly linked list. Here’s it’s definition:

Two pointers to the previous and next elements. When the list is empty, these pointers point to the list head itself. Note that it’s the complete definition of data structure.

Wait! If that’s the complete definition, where do I store the data?

You don’t store data inside this list, instead, you define a data structure which stores the data and has  wl_list as one of it’s members. This is how you’re supposed to use this list:

This creates the following doubly linked list: [e2, e3, e1], Note that foo_list points to the head of the list.

This is the implementation of wl_list_insert:

Nothing magical here, simple doubly linked list insertion. Let’s see how we’re supposed to iterate over the list:

If the length of the list is n, the loop body is executed n times, with e pointing to the corresponding data member of the list.

If you’ve been paying attention, you might have noticed something off. The foo_list is the head of the list (a wl_list), and the wl_list structure doesn’t contain any reference to the actual data (which is contained in the data structure). We’re passing only the list head to the macro, it can only iterate across the chain formed by wl_list members of the data structure, how in the world does it figure out what to assign to the e variable for each loop iteration?

avadaCadavra

Let’s assume that the memory layout of our data struct is:

The offset of link member is x bytes, i.e. it’s x bytes away away from the start of this data structure. The wl_list_for_each has the address (pointer) of the link member. It subtracts the offset of that member inside  data from it’s address, and casts the result to data *.

This is the definition of wl_list_for_each:

wl_container_of takes a pointer to the wl_list, a variable name (of the element type), and the identifier which signifies the name of wl_list element inside data, and it returns a pointer to the data containing the wl_list element given as the first identifier:

This is an example of an intrusive data structure (data structures themselves contain the references needed to maintain the container), and a very generic one at that. ASM bytecode manipulation library also uses intrusive data structures, for example, to represents the control flow of a method, but they are a domain specific solution to the needs of the project. They aren’t generic.

Note that wl_list is not a very safe data structure, in the sense that a programmer need to know exactly how to use it, because the compiler won’t do any handholding when using it.

C language provides you with a million ways to shoot yourself in the foot. And no one else will be able to figure out what you did after you do that.

See you later 

10 thoughts on “C macro magic

  1. No offense man but the font of this website kinda awful, it hurts my eyes, maybe if you make it not bold it will looks cool that way. Anyway, nice article! 🙂

  2. I’ve never heard of the wayland library, but this is identical to the list_head struct that’s used widely throughout the linux kernel. The only tangible difference is that everything is prepended with “wl_”

  3. Nice blog post!

    Only two minor comments.
    1. In the code that showcases the iteration over the list, the struct “data” should be used instead of the struct “element”.
    2. In the same piece of code, a pointer to the foo_list variable should be passed.

    Therefore, in my opinion the code should be like that
    struct data *d;
    wl_list_for_each(d, &foo_list, link) {
    do_something_with_element(d);
    }

Leave a Reply

Your email address will not be published. Required fields are marked *