🍄 the Mycelium intrusive data structures library.
This library provides a collection of intrusive data structures originally implemented for the Mycelium operating system. Currently, it provides an intrusive doubly-linked list and an intrusive, lock-free MPSC queue.
Intrusive data structures are node-based data structures where the node data (pointers to other nodes and, potentially, any associated metadata) are stored within the values that are contained by the data structure, rather than owning those values.
- Because node data is stored inside of the elements of a collection, no additional heap allocation is required for those nodes. This means that when an element is already heap allocated, it can be added to a collection without requiring an additional allocation.
- Similarly, when elements are at fixed memory locations (such as pages in a
page allocator, or
statics), they can be added to intrusive data structures without allocating at all. This makes intrusive data structures useful in code that cannot allocate — for example, we might use intrusive lists of memory regions to implement a heap allocator.
- Intrusive data structures may offer better performance than other linked or node-based data structures, since allocator overhead is avoided.
- Intrusive data structures require the elements stored in a collection to be
aware of the collection. If a
structis to be stored in an intrusive collection, it will need to store a
Linksstruct for that structure as a field, and implement the
Linkedtrait to allow the intrusive data structure to access its
- A given instance of a
Linkedtype may not be added to multiple intrusive data structures of the same type. This can sometimes be worked around with multiple wrapper types. An object may be a member of multiple intrusive data structures of different types.
- Using intrusive data structures requires
Linkedtrait is unsafe to implement, as it requires that types implementing
Linkeduphold additional invariants. In particular, members of intrusive collections must be pinned in memory; they may not move (or be dropped) while linked into an intrusive collection.
In keeping with Mycelium’s fungal naming theme, Cordyceps is a genus of ascomycete fungi that’s (in)famous for its intrusive behavior.
The following features are available (this list is incomplete; you can help by expanding it.)
|Inhibits cache padding for the |
An intrusive doubly-linked list.