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)?;
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)?;
30//! assert_eq!(ys.pop(), Some(42));
31//! # Ok::<(), u8>(())
32//! ```
33//!
34//! Because they have fixed capacity `heapless` data structures don't implicitly reallocate. This
35//! means that operations like `heapless::Vec.push` are *truly* constant time rather than amortized
36//! constant time with potentially unbounded (depends on the allocator) worst case execution time
37//! (which is bad/unacceptable for hard real time applications).
38//!
39//! `heapless` data structures don't use a memory allocator which means no risk of an uncatchable
40//! Out Of Memory (OOM) condition while performing operations on them. It's certainly possible to
41//! run out of capacity while growing `heapless` data structures, but the API lets you handle this
42//! possibility by returning a `Result` on operations that may exhaust the capacity of the data
43//! structure.
44//!
45//! List of currently implemented data structures:
46#![cfg_attr(
47 any(
48 arm_llsc,
49 all(
50 target_pointer_width = "32",
51 any(target_has_atomic = "64", feature = "portable-atomic")
52 ),
53 all(
54 target_pointer_width = "64",
55 any(
56 all(target_has_atomic = "128", feature = "nightly"),
57 feature = "portable-atomic"
58 )
59 )
60 ),
61 doc = "- [`Arc`][pool::arc::Arc]: Like `std::sync::Arc` but backed by a lock-free memory pool rather than `[global_allocator]`."
62)]
63#![cfg_attr(
64 any(
65 arm_llsc,
66 all(
67 target_pointer_width = "32",
68 any(target_has_atomic = "64", feature = "portable-atomic")
69 ),
70 all(
71 target_pointer_width = "64",
72 any(
73 all(target_has_atomic = "128", feature = "nightly"),
74 feature = "portable-atomic"
75 )
76 )
77 ),
78 doc = "- [`Box`][pool::boxed::Box]: Like `std::boxed::Box` but backed by a lock-free memory pool rather than `[global_allocator]`."
79)]
80#: Objects managed by an object pool."
96)]
97//! - [`BinaryHeap`]: A priority queue.
98//! - [`Deque`]: A double-ended queue.
99//! - [`HistoryBuf`]: A “history buffer”, similar to a write-only ring buffer.
100//! - [`IndexMap`]: A hash table.
101//! - [`IndexSet`]: A hash set.
102//! - [`LinearMap`]: A linear map.
103//! - [`SortedLinkedList`](sorted_linked_list::SortedLinkedList): A sorted linked list.
104//! - [`String`]: A string.
105//! - [`Vec`]: A vector.
106//! - [`mpmc::MpMcQueue`](mpmc): A lock-free multiple-producer, multiple-consumer queue.
107//! - [`spsc::Queue`](spsc): A lock-free single-producer, single-consumer queue.
108//!
109//! # Zeroize Support
110//!
111//! The `zeroize` feature enables secure memory wiping for the data structures via the [`zeroize`](https://crates.io/crates/zeroize)
112//! crate. Sensitive data can be properly erased from memory when no longer needed.
113//!
114//! When zeroizing a container, all underlying memory (including unused portion of the containers)
115//! is overwritten with zeros, length counters are reset, and the container is left in a valid but
116//! empty state that can be reused.
117//!
118//! Check the [documentation of the zeroize crate](https://docs.rs/zeroize/) for more information.
119//! # Minimum Supported Rust Version (MSRV)
120//!
121//! This crate does *not* have a Minimum Supported Rust Version (MSRV) and may make use of language
122//! features and API in the standard library available in the latest stable Rust version.
123//!
124//! In other words, changes in the Rust version requirement of this crate are not considered semver
125//! breaking change and may occur in patch version releases.
126#![cfg_attr(docsrs, feature(doc_cfg))]
127#![cfg_attr(not(test), no_std)]
128#![deny(missing_docs)]
129#![cfg_attr(
130 all(
131 feature = "nightly",
132 target_pointer_width = "64",
133 target_has_atomic = "128"
134 ),
135 feature(integer_atomics)
136)]
137#![warn(
138 clippy::use_self,
139 clippy::too_long_first_doc_paragraph,
140 clippy::redundant_pub_crate,
141 clippy::option_if_let_else,
142 clippy::ptr_as_ptr,
143 clippy::ref_as_ptr,
144 clippy::doc_markdown,
145 clippy::semicolon_if_nothing_returned,
146 clippy::if_not_else
147)]
148
149#[cfg(feature = "alloc")]
150extern crate alloc;
151
152pub use binary_heap::BinaryHeap;
153pub use c_string::CString;
154pub use deque::Deque;
155pub use history_buf::{HistoryBuf, OldestOrdered};
156pub use index_map::IndexMap;
157pub use index_set::IndexSet;
158pub use len_type::LenType;
159pub use linear_map::LinearMap;
160pub use string::String;
161
162pub use vec::{Vec, VecView};
163
164#[macro_use]
165#[cfg(test)]
166mod test_helpers;
167
168pub mod c_string;
169pub mod deque;
170pub mod history_buf;
171pub mod index_map;
172pub mod index_set;
173mod len_type;
174pub mod linear_map;
175mod slice;
176pub mod storage;
177pub mod string;
178pub mod vec;
179
180// FIXME: Workaround a compiler ICE in rust 1.83 to 1.86
181// https://github.com/rust-lang/rust/issues/138979#issuecomment-2760839948
182#[expect(dead_code)]
183fn dead_code_ice_workaround() {}
184
185#[cfg(feature = "serde")]
186mod de;
187#[cfg(feature = "serde")]
188mod ser;
189
190pub mod binary_heap;
191#[cfg(feature = "bytes")]
192mod bytes;
193#[cfg(feature = "defmt")]
194mod defmt;
195#[cfg(any(
196 // assume we have all atomics available if we're using portable-atomic
197 feature = "portable-atomic",
198 // target has native atomic CAS (mpmc_large requires usize, otherwise just u8)
199 all(feature = "mpmc_large", target_has_atomic = "ptr"),
200 all(not(feature = "mpmc_large"), target_has_atomic = "8")
201))]
202pub mod mpmc;
203#[cfg(any(
204 arm_llsc,
205 all(
206 target_pointer_width = "32",
207 any(target_has_atomic = "64", feature = "portable-atomic")
208 ),
209 all(
210 target_pointer_width = "64",
211 any(
212 all(target_has_atomic = "128", feature = "nightly"),
213 feature = "portable-atomic"
214 )
215 )
216))]
217pub mod pool;
218pub mod sorted_linked_list;
219#[cfg(any(
220 // assume we have all atomics available if we're using portable-atomic
221 feature = "portable-atomic",
222 // target has native atomic CAS. Note this is too restrictive, spsc requires load/store only, not CAS.
223 // This should be `cfg(target_has_atomic_load_store)`, but that's not stable yet.
224 target_has_atomic = "ptr",
225 // or the current target is in a list in build.rs of targets known to have load/store but no CAS.
226 has_atomic_load_store
227))]
228pub mod spsc;
229
230#[cfg(feature = "ufmt")]
231mod ufmt;
232
233#[cfg(feature = "embedded-io-v0.7")]
234mod embedded_io;
235
236/// Implementation details for macros.
237/// Do not use. Used for macros only. Not covered by semver guarantees.
238#[doc(hidden)]
239pub mod _export {
240 pub use crate::string::format;
241}
242
243/// The error type for fallible [`Vec`] and [`String`] methods.
244#[derive(Debug, Default)]
245#[non_exhaustive]
246pub struct CapacityError;
247
248impl core::fmt::Display for CapacityError {
249 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
250 f.write_str("insufficient capacity")
251 }
252}
253
254impl core::error::Error for CapacityError {}