Crate heapless

Crate heapless 

Source
Expand description

static friendly data structures that don’t require dynamic memory allocation

The core principle behind heapless is that its data structures are backed by a static memory allocation. For example, you can think of heapless::Vec as an alternative version of std::Vec with fixed capacity and that can’t be re-allocated on the fly (e.g. via push).

All heapless data structures store their memory allocation inline and specify their capacity via their type parameter N. This means that you can instantiate a heapless data structure on the stack, in a static variable, or even in the heap.

use heapless::Vec; // fixed capacity `std::Vec`

// on the stack
let mut xs: Vec<u8, 8> = Vec::new(); // can hold up to 8 elements
xs.push(42)?;
assert_eq!(xs.pop(), Some(42));

// in a `static` variable
static mut XS: Vec<u8, 8> = Vec::new();

let xs = unsafe { &mut XS };

xs.push(42)?;
assert_eq!(xs.pop(), Some(42));

// in the heap (though kind of pointless because no reallocation)
let mut ys: Box<Vec<u8, 8>> = Box::new(Vec::new());
ys.push(42)?;
assert_eq!(ys.pop(), Some(42));

Because they have fixed capacity heapless data structures don’t implicitly reallocate. This means that operations like heapless::Vec.push are truly constant time rather than amortized constant time with potentially unbounded (depends on the allocator) worst case execution time (which is bad/unacceptable for hard real time applications).

heapless data structures don’t use a memory allocator which means no risk of an uncatchable Out Of Memory (OOM) condition while performing operations on them. It’s certainly possible to run out of capacity while growing heapless data structures, but the API lets you handle this possibility by returning a Result on operations that may exhaust the capacity of the data structure.

List of currently implemented data structures:

  • Arc: Like std::sync::Arc but backed by a lock-free memory pool rather than [global_allocator].
  • Box: Like std::boxed::Box but backed by a lock-free memory pool rather than [global_allocator].
  • Arc: Like std::sync::Arc but backed by a lock-free memory pool rather than [global_allocator].
  • Object: Objects managed by an object pool.
  • BinaryHeap: A priority queue.
  • Deque: A double-ended queue.
  • HistoryBuf: A “history buffer”, similar to a write-only ring buffer.
  • IndexMap: A hash table.
  • IndexSet: A hash set.
  • LinearMap: A linear map.
  • SortedLinkedList: A sorted linked list.
  • String: A string.
  • Vec: A vector.
  • mpmc::MpMcQueue: A lock-free multiple-producer, multiple-consumer queue.
  • spsc::Queue: A lock-free single-producer, single-consumer queue.

§Minimum Supported Rust Version (MSRV)

This crate does not have a Minimum Supported Rust Version (MSRV) and may make use of language features and API in the standard library available in the latest stable Rust version.

In other words, changes in the Rust version requirement of this crate are not considered semver breaking change and may occur in patch version releases.

Re-exports§

pub use binary_heap::BinaryHeap;
pub use c_string::CString;
pub use deque::Deque;
pub use history_buf::HistoryBuf;
pub use history_buf::OldestOrdered;
pub use index_map::IndexMap;
pub use index_set::IndexSet;
pub use linear_map::LinearMap;
pub use string::String;
pub use vec::Vec;
pub use vec::VecView;

Modules§

binary_heap
A priority queue implemented with a binary heap.
c_string
A fixed capacity CString.
deque
A fixed capacity double-ended queue.
history_buf
A “history buffer”, similar to a write-only ring buffer of fixed length.
index_map
A fixed-capacity hash table where the iteration order is independent of the hash of the keys.
index_set
A fixed-capacity hash set where the iteration order is independent of the hash values.
linear_map
A fixed capacity map/dictionary that performs lookups via linear search.
mpmcportable-atomic, or mpmc_large and target_has_atomic="ptr", or non-mpmc_large and target_has_atomic="8"
A fixed capacity multiple-producer, multiple-consumer (MPMC) lock-free queue.
poolarm_llsc, or 32-bit and (target_has_atomic="64" or portable-atomic), or 64-bit and (target_has_atomic="128" and nightly, or portable-atomic)
Memory and object pools
sorted_linked_list
A fixed sorted priority linked list, similar to BinaryHeap but with different properties on push, pop, etc.
spscportable-atomic or target_has_atomic="ptr" or has_atomic_load_store
A fixed capacity single-producer, single-consumer (SPSC) lock-free queue.
storage
Storage trait defining how data is stored in a container.
string
A fixed capacity String.
vec
A fixed capacity Vec.

Macros§

arc_pool(portable-atomic or target_has_atomic="ptr") and (arm_llsc, or 32-bit and (target_has_atomic="64" or portable-atomic), or 64-bit and (target_has_atomic="128" and nightly, or portable-atomic))
Creates a new ArcPool singleton with the given $name that manages the specified $data_type
box_poolarm_llsc, or 32-bit and (target_has_atomic="64" or portable-atomic), or 64-bit and (target_has_atomic="128" and nightly, or portable-atomic)
Creates a new BoxPool singleton with the given $name that manages the specified $data_type
format
Macro that creates a fixed capacity String. Equivalent to format!.
object_poolarm_llsc, or 32-bit and (target_has_atomic="64" or portable-atomic), or 64-bit and (target_has_atomic="128" and nightly, or portable-atomic)
Creates a new ObjectPool singleton with the given $name that manages the specified $data_type

Structs§

CapacityError
The error type for fallible Vec and String methods.

Traits§

LenType
A sealed trait representing a valid type to use as a length for a container.