repository·main·Indexed 24 days ago
https://github.com/rust-embedded/heaplessA collection of fixed-capacity, stack-allocated (or static) data structures that do not require a dynamic memory allocator. Designed for embedded systems and environments where deterministic memory usage is required, heapless provides implementations of BinaryHeap, CString, and Deque.
heapless provides static friendly data structures that do not require dynamic memory allocation. It is designed for environments where a heap is unavailable or where deterministic memory usage is required, such as embedded systems.You can run the test suite using cargo test. If you need to test with serde support enabled, include the --features serde flag. To run tests specifically for the histbuf example, provide the module name.
# run all
$ cargo test --features serde
# run only for example histbuf tests
$ cargo test histbuf --features serdeSince heapless::String is UTF-8 encoded, operations like insert, remove, and pop operate on character boundaries.
Warning: Providing an index that is not a valid UTF-8 character boundary to insert or insert_str will cause a panic.
pop() and remove() correctly handle multi-byte Unicode characters (e.g., combining marks or emojis) by treating them as single characters where possible, but they operate on the underlying byte structure. If you use pop() on a string containing a combining character (like an acute accent), it will return the combining character itself.
A BinaryHeap is a priority queue implemented with a binary heap. It can be configured as either a Max heap (where the largest element is at the top) or a Min heap (where the smallest element is at the top).
Complexity:
push): O(log n)pop): O(log n)peek): O(1)Warning: It is a logic error to modify an item in a way that changes its Ord relationship with other items while it is in the heap. This can happen via Cell, RefCell, or unsafe code, and will corrupt the heap structure.
use heapless::binary_heap::{BinaryHeap, Max};
let mut heap: BinaryHeap<_, Max, 8> = BinaryHeap::new();
heap.push(1).unwrap();
heap.push(5).unwrap();
heap.push(2).unwrap();
// Peek shows the most important item (5)
assert_eq!(heap.peek(), Some(&5));
// Pop items in order of priority
assert_eq!(heap.pop(), Some(5));
assert_eq!(heap.pop(), Some(2));
assert_eq!(heap.pop(), Some(1));
assert_eq!(heap.pop(), None);A LinearMap<K, V, N> (owned storage) can be converted into a LinearMapView<K, V> (view/unsized storage) to erase the capacity N. This is useful for passing maps to functions that don't need to know the specific compile-time capacity.
You can perform this conversion via:
&mut LinearMap -> &mut LinearMapView).as_view() or .as_mut_view()heapless provides data structures that are backed by static memory allocation. Unlike std::Vec, which reallocates on the heap, heapless structures store their memory inline.
N. They cannot grow beyond this limit.push are truly constant time ($O(1)$), making them suitable for hard real-time applications.Result (e.g., CapacityError).static variable, or even on the heap (though heap usage is rare as they won't reallocate).use heapless::Vec;
// on the stack
let mut xs: Vec<u8, 8> = Vec::new(); // can hold up to 8 elements
xs.push(42).unwrap();
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).unwrap();
assert_eq!(xs.pop(), Some(42));LinearMap is a fixed-capacity dictionary that performs lookups via linear search. Because it does not use hashing, most operations (like get, insert, and remove) have a time complexity of $O(n)$ rather than $O(1)$. It is ideal for small collections where the overhead of a hashing algorithm is undesirable.
You can allocate a LinearMap on the stack or in a static variable by specifying its capacity as a const generic N.
use heapless::LinearMap;
// allocate the map on the stack with capacity 8
let mut map: LinearMap<&str, isize, 8> = LinearMap::new();
// allocate the map in a static variable
static mut MAP: LinearMap<&str, isize, 8> = LinearMap::new();When instantiating a BinaryHeap, you must specify the heap kind using one of the following marker types:
Max: The largest element (according to Ord) is treated as the highest priority.Min: The smallest element is treated as the highest priority.An IndexSet is a fixed-capacity hash set that maintains insertion order. Unlike a standard HashSet, iterating over an IndexSet yields elements in the order they were added.
Because IndexSet is generic over the hashing algorithm (S), you cannot use it directly without specifying a hasher. Instead, use a concrete instantiation like FnvIndexSet or define your own using IndexSet<T, S, N>.
Key Constraints:
N must be a power of 2.A Deque is a fixed-capacity, double-ended queue (FIFO or LIFO) that allocates its storage on the stack. It allows pushing and popping from both the front and the back.
Key characteristics:
N is defined at compile time via a const generic.push_front, push_back, pop_front, and pop_back.static variable), making it suitable for embedded environments without a heap.Common operations include checking len(), is_empty(), and is_full(), or iterating over elements from front to back.
use heapless::Deque;
// A deque with a fixed capacity of 8 elements allocated on the stack
let mut deque = Deque::<_, 8>::new();
// FIFO operations
deque.push_back(1);
deque.push_back(2);
assert_eq!(deque.len(), 2);
assert_eq!(deque.pop_front(), Some(1));
assert_eq!(deque.pop_front(), Some(2));
// Double-ended operations
deque.push_back(1);
deque.push_front(2);
deque.push_back(3);
deque.push_front(4);
assert_eq!(deque.pop_front(), Some(4));
assert_eq!(deque.pop_front(), Some(2));
// Iteration
for x in &deque {
println!("{}", x);
}A StringView<LenT> is an unsized version of String that stores data in a slice rather than a fixed-size array. You can convert a String<N> to a StringView to erase the specific capacity N from the type, which is useful for writing generic functions that accept any heapless string.
Conversion can be done via:
.as_view().as_mut_view()&String<N> -> &StringView or &mut String<N> -> &mut StringView)The CString<const N: usize, LenT: LenType> type provides a fixed-capacity, C-compatible string that always includes a trailing nul terminator. It stores up to N - 1 non-nul characters. This is useful for interfacing with C APIs in embedded environments where heap allocation is unavailable.
Key characteristics:
N bytes, including the mandatory nul terminator.AsRef<CStr>, Borrow<CStr>, and Deref<Target = CStr>, allowing it to be used wherever a &CStr is expected.use heapless::CString;
// A fixed-size `CString` that can store up to 10 characters
// including the nul terminator.
let empty = CString::<10>::new();
assert_eq!(empty.as_c_str(), c"");