Crate cordyceps

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.

Note

This is a hobby project. I’m working on it in my spare time, for my own personal use. I’m very happy to share it with the broader Rust community, and contributions and bug reports are always welcome. However, please remember that I’m working on this library for fun, and if it stops being fun…well, you get the idea.

Anyway, feel free to use and enjoy this crate, and to contribute back as much as you want to!

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.

Compatibility

Rudimentary support for targets without CAS (Compare and Swap) atomics, such as Cortex-M0+/thumbv6m-none-eabi, is provided, however not all structures and features may be available.

CAS atomic support is automatically detected with cfg(target_has_atomic = "ptr"), which notes that a platform has support for both load/store operations as well as support for CAS atomics.

No crate-level features are necessary to enable/disable structures that require CAS atomics.

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

Feature	Default	Explanation
no-cache-pad	false	Inhibits cache padding for the CachePadded struct used for many linked list pointers. When this feature is NOT enabled, the size will be determined based on target platform.
alloc	false	Enables liballoc dependency and features that depend on liballoc.
std	false	Enables libstd dependency and features that depend on the Rust standard library. Implies alloc.

data structures

cordyceps provides implementations of the following data structures:

• List: a mutable, doubly-linked list.

  A List provides O(1) insertion and removal at both the head and tail of the list. In addition, parts of a List may be split off to form new Lists, and two Lists may be spliced together to form a single List, all in O(1) time. The list module also provides list::Cursor and list::CursorMut types, which allow traversal and modification of elements in a list. Finally, elements can remove themselves from arbitrary positions in a List, provided that they have mutable access to the List itself. This makes the List type suitable for use in cases where elements must be able to drop themselves while linked into a list.

  The List type is not a lock-free data structure, and can only be modified through &mut references.

• MpscQueue: a multi-producer, single-consumer (MPSC) lock-free last-in, first-out (LIFO) queue.

  A MpscQueue is a lock-free concurrent data structure that allows multiple producers to concurrently push elements onto the queue, and a single consumer to dequeue elements in the order that they were pushed.

  MpscQueues can be used to efficiently share data from multiple concurrent producers with a consumer.

  This structure is only available if the target supports CAS (Compare and Swap) atomics.

• SortedList: a mutable, singly-linked list, with elements stored in sorted order.

  This is a simple, singly-linked list with O(n) insertion and O(1) pop operations. The push operation performs an insertion sort, while the pop operation removes the item at the front of the list. The front/back sorting order is based on Ordering and can be min- or max-oriented, or a custom ordering function can be provided.

  The SortedList type is not a lock-free data structure, and can only be modified through &mut references.

• Stack: a mutable, singly-linked first-in, first-out (FIFO) stack.

  This is a simple, singly-linked stack with O(1) push and pop operations. The pop operation returns the last element pushed to the stack. A Stack also implements the Iterator trait; iterating over a stack pops elements from the end of the list.

  The Stack type is not a lock-free data structure, and can only be modified through &mut references.

• TransferStack: a lock-free, multi-producer FIFO stack, where all elements currently in the stack are popped in a single atomic operation.

  A TransferStack is a lock-free data structure where multiple producers can concurrently push elements to the end of the stack through immutable & references. A consumer can pop all elements currently in the TransferStack in a single atomic operation, returning a new Stack. Pushing an element, and taking all elements in the TransferStack are both O(1) operations.

  A TransferStack can be used to efficiently transfer ownership of resources from multiple producers to a consumer, such as for reuse or cleanup.

  This structure is only available if the target supports CAS (Compare and Swap) atomics.

Modules

list

An intrusive doubly-linked list.

mpsc_queuetarget_has_atomic="ptr"

A multi-producer, single-consumer (MPSC) queue, implemented using a lock-free intrusive singly-linked list.

sorted_list

Intrusive, singly-linked, sorted, linked list.

stack

Intrusive, singly-linked first-in, first-out (FIFO) stacks.

Structs

List

An intrusive doubly-linked list.

MpscQueuetarget_has_atomic="ptr"

A multi-producer, single-consumer (MPSC) queue, implemented using a lock-free intrusive singly-linked list.

SortedList

A sorted singly linked list

SortedListIter

A borrowing iterator of a SortedList

Stack

An intrusive singly-linked mutable FIFO stack.

TransferStacktarget_has_atomic="ptr"

An intrusive lock-free singly-linked FIFO stack, where all entries currently in the stack are consumed in a single atomic operation.

Traits

Linked

Trait implemented by types which can be members of an intrusive collection.