4 ms·
BAH! 4. The "intrusive" containers, but of course. The one true way to do it in C. For one, you can keep items in multiple containers, all being on equal foo
by abcd_f 11y ago
BAH!
4. The "intrusive" containers, but of course.
The one true way to do it in C.
For one, you can keep items in multiple containers, all being on equal footing. None of that typical C++ mess, when this list is a primary storage for items, and those maps are secondary indexes, all sprinkled evenly with iterators. Intrusive containers don't own items, they merely organize them, which is exactly the right way to go about it.
For two, the actual code for container operations is as abstract and on-point as it gets as it focuses solely on "weaving" items into and out of a container rather than on other things, like de/allocating supporting structures.
For three, you get no heap activity when adding/removing items to/from a container. This means that if you already have the items, you can always arrange them into a collection. This also eliminates a lot of error handling code, leading to a simpler code.
Obviously, this is not limited to just linked lists.
[1] http://www.makelinux.net/ldd3/chp-11-sect-5 http://www.makelinux.net/ldd3/chp-11-sect-5 (
- notalaser 11y agoYes yes! Yes! It saddens me that this extremely useful idiom is not more widely taught. It's a beautiful, simple concept that works for so many things.
- zodiac 11y agoWhat is an intrusive container?
- exDM69 11y agoA technique commonly used in C, for example in the Linux kernel. You embed "links" to other nodes in your structs, and find the struct from the link based on offsetof. Linux kernel uses linked lists and red-black trees this way. Probably other data structures too. Intrusive containers are cache friendly and typically require no dynamic allocations (in addition to allocating the data itself). See the link in the post above for more about linked lists in the linux kernel.
- charlieflowers 11y agoInteresting. At first I thought you were claiming this technique made linked lists cache friendly. After looking at it, I have concluded you meant merely that the next and prev pointers are near your data. Am I understanding you correctly?
- krakensden 11y agoThat's my understanding too. Instead of going to your data structure, and then dereferencing a pointer to your data, after going to your data structure, you're already there.
- exDM69 11y agoYes, there's one pointer chase less when you don't have a pointer from the link node to the data, but you can get it with offsetof. This can save a significant number of cache misses in some algorithms.
- stonemetal 11y agoIt is a container that intrudes on your data structure. For example in a linked list the next pointer is inside your structure instead of your data structure being wrapped in a node type.
- deleted 11y ago[deleted]
- dividuum 11y agoThe two other responses already described what intrusive containers are. Have a look at https://troydhanson.github.io/uthash/ https://troydhanson.github.io/uthash/ to see an implementation of them that I personally like and use in my C projects. It's really simple to have a struct that is indexed by multiple keys by basically just adding two UT_hash_handle values to your struct and then using the uthash functions. On top of that, it's a really nice implementation that is completely self-contained in a single C header file.
- gpderetta 11y agoAre you aware of Boost intrusive containers?
- joveian 11y agoI use this method but never heard that name before. Many uses are unfortunately not type safe, although it is possible to use a combination of macros and inline functions to get type safety with this method.
- aleden 11y agoOne can implement linked lists as you describe in a C++ fashion using multiple inheritance. The LLVM project has many examples of this using the ilist_node class [1], e.g. [2]. Between using preprocessor directives in C and multiple inheritance in C++ (comes with associated complexity in the resulting client code), I'd always pick the latter. [1] https://github.com/llvm-mirror/llvm/blob/release_37/include/llvm/ADT/ilist_node.h#L43 https://github.com/llvm-mirror/llvm/blob/release_37/include/... [2] https://github.com/llvm-mirror/llvm/blob/release_37/include/llvm/IR/BasicBlock.h#L66 https://github.com/llvm-mirror/llvm/blob/release_37/include/...
- fanf2 11y agoHow do you put an object on multiple different lists with this technique? E.g. in FreeBSD an mbuf can be on two lists at once: http://svnweb.freebsd.org/base/head/sys/sys/mbuf.h?revision=293439&view=markup#l178 http://svnweb.freebsd.org/base/head/sys/sys/mbuf.h?revision=...