3 ms·
Nobody's mentioned what is IMO the main benefit of an intrusive data-structure: items within the data-structure can belong to multiple containers. This allows
by Diggsey 5y ago
Nobody's mentioned what is IMO the main benefit of an intrusive data-structure: items within the data-structure can belong to multiple containers.
This allows you to locate an item using more than one criteria: for example, you could store blocks of free memory in two intrusive lists, one sorted by size and one by location. This would allow you to first locate eg. the largest memory block, and then quickly locate blocks adjacent to that one in memory.
With non-intrusive data-structures this is not possible, because while you can go from an iterator -> the item pointed to by the iterator, there is no way to efficiently do the reverse. This is possible in an intrusive data-structure because the iterator and the item itself are the same thing.
- loeg 5y agoYes, a very important point. In the kernel, it is pretty common for objects to need to be on multiple different lists.
- shadowofneptune 5y agoSo when you remove an element from the list, how do you make sure both lists are updated? Are elements even likely to be removed in this use-case?
- jjnoakes 5y agoThis is one of the purposes of doubly-linking the nodes. Say your struct is in two lists. To remove it from both, first follow the next/prev pointers of the first list embedded struct to remove it from the first list, and then do the same thing with the second list embedded struct to remove it from the second list.
- adwn 5y ago> So when you remove an element from the list, how do you make sure both lists are updated? The remove_from_list() function has to be either payload-specific, or it needs a function pointer parameter which is called to handle the payload-specific unlinking. Assuming the lists are doubly-linked, which they typically are in the Linux kernel.