Heapless Data Structures

Recipe	Crates	Categories
Work with Heapless Data Structures with heapless

Work with Data Structures without Dynamic Memory Allocation

The heapless↗ crate provides fixed-size 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 and unpredictably re-allocate at runtime.

This can be particularly useful for systems or performance-critical applications, 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, a priority queue.
• heapless::IndexMap, like IndexMap↗.
• heapless::IndexSet and FnvIndexSet, like indexmap::set::IndexSet↗, a 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, an object managed by an object pool.
• heapless::String, a fixed capacity String↗.
• heapless::Vec, a fixed capacity Vec.
• heapless::mpmc::Q*, a fixed-capacity multiple-producer multiple-consumer lock-free queues.
• heapless::spsc::Queue, a statically allocated single-producer single-consumer lock-free queue.

Keep in mind that choosing heapless is a trade-off: gain performance and determinism, but lose the flexibility of dynamic resizing. The following example demonstrates the basic usage of heapless collections:

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

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

    vec.push(1).unwrap();
    vec.push(2).unwrap();
    vec.push(3).unwrap();
    // Because they have a fixed size, operations like `push` or `insert` can
    // fail if the collection is full. In that case, `push` returns back the
    // item.
    if let Err(err) = vec.push(4) {
        println!("Error pushing to vector: {err:?}");
    };

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

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

    // Declare a 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());

    // Returns an 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 simply `()`.
    }

    // Define a fixed-size map (using the `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();
    // If a key already exists in the map, the key remains and retains in its
    // place in the order, its corresponding value is updated with the new
    // value and the older value is returned inside `Some(_)`.
    assert_eq!(map.insert("three", 33), Ok(Some(3)));

    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:?}");
    }

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

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

Related Topics

• Binary Heaps.
• Hash Maps.
• Heap Storage.
• Other Maps.
• Stack-allocated Arrays.
• Strings.
• Vectors.