It is awkward in C, where the implementation has to be macro-generated
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
One other advantage of intrusive data structures is the ability to link a payload into several parallel collections without indirections
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
the defining property of intrusive data structures is that they leave the responsibility of allocating elements to the user.
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
Ah yes if all collections are explicitly listed in the list node type, that makes sense. I thought the suggestion was that you could somehow link any given payload entry into multiple independent lists each with their own list node type.
struct thread {
// Entry in the list of threads of the containing process
list_node process_entry;
// Entry in this thread's scheduling queue
list_node sched_entry;
// ...
};
Each struct thread is linked in two lists. When we need to get from a list_node * to the enclosing struct thread, we know from the context which list is being inspected, so we know which one of process_entry or sched_entry to consider for offsetting the pointer.
Comments
I assume this is why they are putting the list pointer and payload in separate structs and doing pointer math to access the payload, so that it’s easy to build a set of macros that act like a generic list class for building lists out of any payload, right?
Wait - how does this work? If I do address math on the pointer in order to find a payload, then isn’t the payload tied into exactly one next pointer, and thus exactly one list? For a minute I thought maybe this is why they put the pointer after the payload, but now I don’t see how to use a payload in more than one list, nor why they use subtract on the list pointer to find the payload instead of putting the list in front of the payload and adding (or using a type-cast pointer for direct access).
Indeed! This is why you see them in OS’s, in memory managers, and in embedded systems. We used to use them all the time in console video games before dynamic memory and heap allocations were common (or even allowed). Use of STL wasn’t allowed. Often the memory needed would be pre-allocated, and lists would be created and managed at run time without allocation, just by wiring up the pointers. Similar to what a memory manager has to do.
This was in C++, but back when (and before) EASTL was popular. EASTL was EA’s version of the STL without built-in heap allocation for container classes. We usually built payload classes with the list next pointer placed directly in the payload, and essentially did the list management as a one-off separately for each payload, because it was typically only a few lines of code and there weren’t enough list types for it to be a problem. This is the kind of intrusive list I’ve seen the most of, hence the questions about the particular C flavor shown here.
The container_of macro takes the type and member - so for a different member it can subtract a different offset.
Going more basic, you could imagine creating something like:
The normal, 10ths, and 100ths lists are distinct collections, this is the basic idea. The macros just help generalise it and make it more usable.Ah yes if all collections are explicitly listed in the list node type, that makes sense. I thought the suggestion was that you could somehow link any given payload entry into multiple independent lists each with their own list node type.
Like this:
Each struct thread is linked in two lists. When we need to get from a list_node * to the enclosing struct thread, we know from the context which list is being inspected, so we know which one of process_entry or sched_entry to consider for offsetting the pointer.