Heapless Data Structures

Recipe	Crates	Categories
Heapless

Heapless

The heapless↗ crate provides data structures that don't require dynamic memory allocation. This means they are backed by static memory allocation (on the stack, in a static variable, or even in the heap, despite the name) and have fixed capacities determined at compile time. They don't implicitly re-allocate at runtime.

This can be particularly useful for systems or other environments where dynamic memory allocation is not feasible or desirable: operations on heapless↗ data structures do not involve a memory allocator, reducing the risk of memory allocation failures. In addition, operations like push and pop are truly constant time, as there is no dynamic resizing involved.

heapless↗ includes:

• heapless::pool::arc::Arc - like std::sync::Arc↗ but backed by a lock-free memory pool rather than #[global_allocator].
• heapless::pool::boxed::Box - like std::boxed::Box↗ but backed by a lock-free memory pool rather than #[global_allocator].
• heapless::binary_heap::BinaryHeap - priority queue.
• heapless::IndexMap - like IndexMap↗.
• heapless::IndexSet and FnvIndexSet - like indexmap::set::IndexSet↗, hash set where the iteration order of the values is independent of their hash values.
• heapless::LinearMap - a fixed capacity map / dictionary that performs lookups via linear search.
• heapless::pool::object::Object - objects managed by an object pool.
• heapless::String - a fixed capacity String↗.
• heapless::Vec - a fixed capacity Vec.
• heapless::mpmc::Q* - fixed-capacity multiple-producer multiple-consumer lock-free queues.
• heapless::spsc::Queue - a statically allocated single-producer single-consumer lock-free queue.

//! This example demonstrates the usage of `heapless` collections in Rust.
//!
//! `heapless` provides fixed-size, stack-allocated data structures, which are
//! useful when you know the maximum size of your data at compile time and need
//! to avoid dynamic memory allocation (and potential capacity errors). This is
//! particularly beneficial in embedded systems or performance-critical
//! applications where dynamic allocation can be unpredictable or undesirable.
//!
//! Choosing `heapless` is a trade-off: you gain performance and determinism but
//! lose the flexibility of dynamic resizing.

use heapless::FnvIndexMap;
use heapless::String;
use heapless::Vec;

fn main() -> anyhow::Result<()> {
    // `heapless`` collections have a fixed, compile-time determined capacity.
    // Here we define a fixed-size vector with capacity of 5.
    let mut vec: Vec<u32, 5> = Vec::new();

    // Because they have a fixed size, operations like `push` or `insert` can
    // fail if the collection is full.
    vec.push(1).unwrap();
    vec.push(2).unwrap();
    vec.push(3).unwrap();

    println!("Vector: {vec:?}");
    println!("Vector length: {}", vec.len());
    println!("Vector capacity: {}", vec.capacity());

    if let Some(last) = vec.pop() {
        println!("Popped: {last}");
    }

    // Fixed-size string with capacity of 16:
    let mut string: String<16> = String::from("Hello");

    assert!(string.push_str(", world!").is_ok());

    println!("String: {string}");
    println!("String length: {}", string.len());
    println!("String capacity: {}", string.capacity());

    // Error if we exceed the capacity:
    let result = string.push_str(" It is too much!");
    if let Err(err) = result {
        println!("Error pushing to string: {err:?}"); // err is ()
    }

    // Fixed-size map (using Fnv hash for performance)
    let mut map: FnvIndexMap<&str, u32, 4> = FnvIndexMap::new();

    map.insert("one", 1).unwrap();
    map.insert("two", 2).unwrap();
    map.insert("three", 3).unwrap();
    map.insert("four", 4).unwrap();

    println!("Map: {map:?}");

    if let Some(value) = map.get("two") {
        println!("Value for 'two': {value}");
    }

    let result = map.insert("five", 5);
    if let Err(err) = result {
        println!("Error inserting to map: {err:?}");
    }

    // Iterating over the map:
    for (key, value) in &map {
        println!("Key: {key}, Value: {value}");
    }

    // Clearing the map:
    map.clear();
    println!("Map is empty: {}", map.is_empty());

    Ok(())
}