cordyceps

🍄 the Mycelium intrusive data structures library.

what is it?

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

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.

when should i use intrusive data structures?

• 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.

when shouldn't i use intrusive data structures?

• Intrusive data structures require the elements stored in a collection to be aware of the collection. If a struct is to be stored in an intrusive collection, it will need to store a Links struct for that structure as a field, and implement the Linked trait to allow the intrusive data structure to access its Links.
• A given instance of a Linked type 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 unsafe code. The Linked trait is unsafe to implement, as it requires that types implementing Linked uphold 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.

about the name

In keeping with Mycelium's fungal naming theme, Cordyceps is a genus of ascomycete fungi that's (in)famous for its intrusive behavior.

features

The following features are available (this list is incomplete; you can help by expanding it.)