heapless/
lib.rs

1//! `static` friendly data structures that don't require dynamic memory allocation
2//!
3//! The core principle behind `heapless` is that its data structures are backed by a *static* memory
4//! allocation. For example, you can think of `heapless::Vec` as an alternative version of
5//! `std::Vec` with fixed capacity and that can't be re-allocated on the fly (e.g. via `push`).
6//!
7//! All `heapless` data structures store their memory allocation *inline* and specify their capacity
8//! via their type parameter `N`. This means that you can instantiate a `heapless` data structure on
9//! the stack, in a `static` variable, or even in the heap.
10//!
11//! ```
12//! use heapless::Vec; // fixed capacity `std::Vec`
13//!
14//! // on the stack
15//! let mut xs: Vec<u8, 8> = Vec::new(); // can hold up to 8 elements
16//! xs.push(42).unwrap();
17//! assert_eq!(xs.pop(), Some(42));
18//!
19//! // in a `static` variable
20//! static mut XS: Vec<u8, 8> = Vec::new();
21//!
22//! let xs = unsafe { &mut XS };
23//!
24//! xs.push(42);
25//! assert_eq!(xs.pop(), Some(42));
26//!
27//! // in the heap (though kind of pointless because no reallocation)
28//! let mut ys: Box<Vec<u8, 8>> = Box::new(Vec::new());
29//! ys.push(42).unwrap();
30//! assert_eq!(ys.pop(), Some(42));
31//! ```
32//!
33//! Because they have fixed capacity `heapless` data structures don't implicitly reallocate. This
34//! means that operations like `heapless::Vec.push` are *truly* constant time rather than amortized
35//! constant time with potentially unbounded (depends on the allocator) worst case execution time
36//! (which is bad / unacceptable for hard real time applications).
37//!
38//! `heapless` data structures don't use a memory allocator which means no risk of an uncatchable
39//! Out Of Memory (OOM) condition while performing operations on them. It's certainly possible to
40//! run out of capacity while growing `heapless` data structures, but the API lets you handle this
41//! possibility by returning a `Result` on operations that may exhaust the capacity of the data
42//! structure.
43//!
44//! List of currently implemented data structures:
45//!
46#![cfg_attr(
47    any(arm_llsc, target_arch = "x86"),
48    doc = "- [`Arc`](pool::arc::Arc) -- like `std::sync::Arc` but backed by a lock-free memory pool rather than `#[global_allocator]`"
49)]
50#![cfg_attr(
51    any(arm_llsc, target_arch = "x86"),
52    doc = "- [`Box`](pool::boxed::Box) -- like `std::boxed::Box` but backed by a lock-free memory pool rather than `#[global_allocator]`"
53)]
54//! - [`BinaryHeap`] -- priority queue
55//! - [`IndexMap`] -- hash table
56//! - [`IndexSet`] -- hash set
57//! - [`LinearMap`]
58#![cfg_attr(
59    any(arm_llsc, target_arch = "x86"),
60    doc = "- [`Object`](pool::object::Object) -- objects managed by an object pool"
61)]
62//! - [`String`]
63//! - [`Vec`]
64//! - [`mpmc::Q*`](mpmc) -- multiple producer multiple consumer lock-free queue
65//! - [`spsc::Queue`] -- single producer single consumer lock-free queue
66//!
67//! # Optional Features
68//!
69//! The `heapless` crate provides the following optional Cargo features:
70//!
71//! - `ufmt`: Implement [`ufmt_write::uWrite`] for `String<N>` and `Vec<u8, N>`
72//!
73//! [`ufmt_write::uWrite`]: https://docs.rs/ufmt-write/
74//!
75//! # Minimum Supported Rust Version (MSRV)
76//!
77//! This crate does *not* have a Minimum Supported Rust Version (MSRV) and may make use of language
78//! features and API in the standard library available in the latest stable Rust version.
79//!
80//! In other words, changes in the Rust version requirement of this crate are not considered semver
81//! breaking change and may occur in patch version releases.
82#![cfg_attr(docsrs, feature(doc_cfg), feature(doc_auto_cfg))]
83#![cfg_attr(not(test), no_std)]
84#![deny(missing_docs)]
85#![deny(warnings)]
86
87pub use binary_heap::BinaryHeap;
88pub use deque::Deque;
89pub use histbuf::{HistoryBuffer, OldestOrdered};
90pub use indexmap::{
91    Bucket, Entry, FnvIndexMap, IndexMap, Iter as IndexMapIter, IterMut as IndexMapIterMut,
92    Keys as IndexMapKeys, OccupiedEntry, Pos, VacantEntry, Values as IndexMapValues,
93    ValuesMut as IndexMapValuesMut,
94};
95pub use indexset::{FnvIndexSet, IndexSet, Iter as IndexSetIter};
96pub use linear_map::LinearMap;
97pub use string::String;
98pub use vec::Vec;
99
100#[macro_use]
101#[cfg(test)]
102mod test_helpers;
103
104mod deque;
105mod histbuf;
106mod indexmap;
107mod indexset;
108mod linear_map;
109mod string;
110mod vec;
111
112#[cfg(feature = "serde")]
113mod de;
114#[cfg(feature = "serde")]
115mod ser;
116
117pub mod binary_heap;
118#[cfg(feature = "defmt-03")]
119mod defmt;
120#[cfg(any(
121    // assume we have all atomics available if we're using portable-atomic
122    feature = "portable-atomic",
123    // target has native atomic CAS (mpmc_large requires usize, otherwise just u8)
124    all(feature = "mpmc_large", target_has_atomic = "ptr"),
125    all(not(feature = "mpmc_large"), target_has_atomic = "8")
126))]
127pub mod mpmc;
128#[cfg(any(arm_llsc, target_arch = "x86"))]
129pub mod pool;
130pub mod sorted_linked_list;
131#[cfg(any(
132    // assume we have all atomics available if we're using portable-atomic
133    feature = "portable-atomic",
134    // target has native atomic CAS. Note this is too restrictive, spsc requires load/store only, not CAS.
135    // This should be `cfg(target_has_atomic_load_store)`, but that's not stable yet.
136    target_has_atomic = "ptr",
137    // or the current target is in a list in build.rs of targets known to have load/store but no CAS.
138    has_atomic_load_store
139))]
140pub mod spsc;
141
142#[cfg(feature = "ufmt")]
143mod ufmt;
144
145mod sealed;