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#![cfg_attr(
81 any(
82 arm_llsc,
83 all(
84 target_pointer_width = "32",
85 any(target_has_atomic = "64", feature = "portable-atomic")
86 ),
87 all(
88 target_pointer_width = "64",
89 any(
90 all(target_has_atomic = "128", feature = "nightly"),
91 feature = "portable-atomic"
92 )
93 )
94 ),
95 doc = "- [`Arc`][pool::arc::Arc]: Like `std::sync::Arc` but backed by a lock-free memory pool rather than `[global_allocator]`."
96)]
97#: Objects managed by an object pool."
113)]
114//! - [`BinaryHeap`]: A priority queue.
115//! - [`Deque`]: A double-ended queue.
116//! - [`HistoryBuf`]: A “history buffer”, similar to a write-only ring buffer.
117//! - [`IndexMap`]: A hash table.
118//! - [`IndexSet`]: A hash set.
119//! - [`LinearMap`]: A linear map.
120//! - [`SortedLinkedList`](sorted_linked_list::SortedLinkedList): A sorted linked list.
121//! - [`String`]: A string.
122//! - [`Vec`]: A vector.
123//! - [`mpmc::MpMcQueue`](mpmc): A lock-free multiple-producer, multiple-consumer queue.
124//! - [`spsc::Queue`](spsc): A lock-free single-producer, single-consumer queue.
125//!
126//! # Minimum Supported Rust Version (MSRV)
127//!
128//! This crate does *not* have a Minimum Supported Rust Version (MSRV) and may make use of language
129//! features and API in the standard library available in the latest stable Rust version.
130//!
131//! In other words, changes in the Rust version requirement of this crate are not considered semver
132//! breaking change and may occur in patch version releases.
133#![cfg_attr(docsrs, feature(doc_cfg), feature(doc_auto_cfg))]
134#![cfg_attr(not(test), no_std)]
135#![deny(missing_docs)]
136#![cfg_attr(
137 all(
138 feature = "nightly",
139 target_pointer_width = "64",
140 target_has_atomic = "128"
141 ),
142 feature(integer_atomics)
143)]
144#![warn(
145 clippy::use_self,
146 clippy::too_long_first_doc_paragraph,
147 clippy::redundant_pub_crate,
148 clippy::option_if_let_else,
149 clippy::ptr_as_ptr,
150 clippy::ref_as_ptr,
151 clippy::doc_markdown,
152 clippy::semicolon_if_nothing_returned,
153 clippy::if_not_else
154)]
155
156#[cfg(feature = "alloc")]
157extern crate alloc;
158
159pub use binary_heap::BinaryHeap;
160pub use c_string::CString;
161pub use deque::Deque;
162pub use history_buf::{HistoryBuf, OldestOrdered};
163pub use index_map::IndexMap;
164pub use index_set::IndexSet;
165pub use len_type::LenType;
166pub use linear_map::LinearMap;
167pub use string::String;
168
169pub use vec::{Vec, VecView};
170
171#[macro_use]
172#[cfg(test)]
173mod test_helpers;
174
175pub mod c_string;
176pub mod deque;
177pub mod history_buf;
178pub mod index_map;
179pub mod index_set;
180mod len_type;
181pub mod linear_map;
182mod slice;
183pub mod storage;
184pub mod string;
185pub mod vec;
186
187// FIXME: Workaround a compiler ICE in rust 1.83 to 1.86
188// https://github.com/rust-lang/rust/issues/138979#issuecomment-2760839948
189#[expect(dead_code)]
190fn dead_code_ice_workaround() {}
191
192#[cfg(feature = "serde")]
193mod de;
194#[cfg(feature = "serde")]
195mod ser;
196
197pub mod binary_heap;
198#[cfg(feature = "bytes")]
199mod bytes;
200#[cfg(feature = "defmt")]
201mod defmt;
202#[cfg(any(
203 // assume we have all atomics available if we're using portable-atomic
204 feature = "portable-atomic",
205 // target has native atomic CAS (mpmc_large requires usize, otherwise just u8)
206 all(feature = "mpmc_large", target_has_atomic = "ptr"),
207 all(not(feature = "mpmc_large"), target_has_atomic = "8")
208))]
209pub mod mpmc;
210#[cfg(any(
211 arm_llsc,
212 all(
213 target_pointer_width = "32",
214 any(target_has_atomic = "64", feature = "portable-atomic")
215 ),
216 all(
217 target_pointer_width = "64",
218 any(
219 all(target_has_atomic = "128", feature = "nightly"),
220 feature = "portable-atomic"
221 )
222 )
223))]
224pub mod pool;
225pub mod sorted_linked_list;
226#[cfg(any(
227 // assume we have all atomics available if we're using portable-atomic
228 feature = "portable-atomic",
229 // target has native atomic CAS. Note this is too restrictive, spsc requires load/store only, not CAS.
230 // This should be `cfg(target_has_atomic_load_store)`, but that's not stable yet.
231 target_has_atomic = "ptr",
232 // or the current target is in a list in build.rs of targets known to have load/store but no CAS.
233 has_atomic_load_store
234))]
235pub mod spsc;
236
237#[cfg(feature = "ufmt")]
238mod ufmt;
239
240/// Implementation details for macros.
241/// Do not use. Used for macros only. Not covered by semver guarantees.
242#[doc(hidden)]
243pub mod _export {
244 pub use crate::string::format;
245}
246
247/// The error type for fallible [`Vec`] and [`String`] methods.
248#[derive(Debug)]
249#[non_exhaustive]
250pub struct CapacityError;
251
252impl core::fmt::Display for CapacityError {
253 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
254 f.write_str("insufficient capacity")
255 }
256}
257
258impl core::error::Error for CapacityError {}