scapegoat


scapegoat

crates.io docs.rs GitHub Actions License: MIT Unsafe-Zero-Percent

Ordered set and map data structures via an arena-based scapegoat tree (memory-efficient, self-balancing binary search tree).

About

Three APIs:

Strives for two properties:

Other features:

Usage

SGMap non-exhaustive, !#[no_std] API example (would work identically for std::collections::BTreeMap):

```rust use scapegoat::SGMap; use smallvec::{smallvec, SmallVec};

const REFBUFLEN: usize = 5;

let mut example = SGMap::new(); let mut stack_str = "your friend the";

// Insert "dynamically" (as if heap) example.insert(3, "the"); example.insert(2, "don't blame"); example.insert(1, "Please"); example.insert(4, "borrow checker");

// Ordered reference iterator assert!(example .iter() .map(|(_, v)| *v) .collect::

// Container indexing assert_eq!(example[&3], "the");

// Fast (no search) head removal let pleasetuple = example.popfirst().unwrap(); asserteq!(pleasetuple, (1, "Please"));

// By-predicate removal (iterates all entries) example.retain(|_, v| !v.contains("a"));

// Extension let iterable: SmallVec<[(isize, &str); REFBUFLEN]> = smallvec![(1337, "safety!"), (0, "Leverage"), (100, "for")]; example.extend(iterable.into_iter());

// Value mutation if let Some(threeval) = example.getmut(&3) { *threeval = &mut stackstr; }

// New message :) assert!(example .into_values() .collect::

Additional examples here.

Configuring a Stack Storage Limit

The maximum number of stack-stored elements (set) or key-value pairs (map/tree) is determined at compile-time, via the environment variable SG_MAX_STACK_ELEMS. Valid values include the range [0, 32] and powers of 2 up to 1,048,576. For example, to store up to 2048 items on the stack:

bash export SG_MAX_STACK_ELEMS=2048 cargo build --release

Please note:

Warning: Although stack usage is constant (no recursion), a stack overflow can happen at runtime if SG_MAX_STACK_ELEMS (configurable) and/or the stored item type (generic) is too large. Note stack overflow is distinct from buffer overflow (which safe Rust prevents). Regardless, you must test to ensure you don't exceed the stack frame(s) size limit of your target platform. Rust only supports stack probes on x86/x64, although creative linking solutions have been suggested for other architectures.

For more advanced configuration options, see the documentation here.

The high_assurance Feature

For embedded use cases prioritizing robustness (or kernelspace code), the high_assurance feature can be enabled with the standard Cargo.toml declaration:

rust [dependencies] scapegoat = { version = "^1.7", features = ["high_assurance"] }

Enabling this feature makes two changes:

  1. Front-end, API Tweak: insert and append APIs now return Result. Err indicates stack storage is already at maximum capacity, so caller must handle. No heap use, no panic potential on insert.

  2. Back-end, Integer Packing: Because the fixed/max size of the stack arena is known, indexing integers (metadata stored at every node!) can be size-optimized. This memory micro-optimization honors the original design goals of the scapegoat data structure.

That second change is a subtle but interesting one. Example of packing saving 53% (31 KB) of RAM usage:

```rust use core::mem::size_of; use scapegoat::SGMap;

// If you're on a 64-bit system, you can compile-time check the below numbers yourself! // Just do: // // $ cargo test --doc // $ cargo test --doc --features="high_assurance" // // One command per set of cfg macros below. // Internally, this compile-time struct packing is done with the smallnum crate: // https://crates.io/crates/smallnum

// This code assumes SG_MAX_STACK_ELEMS == 1024 (default) let temp: SGMap = SGMap::new(); let otherfeaturesenabled = cfg!(any(feature = "fastrebalance", feature = "lowmeminsert")); if temp.capacity() == 1024 && (!otherfeatures_enabled) {

// Without packing
#[cfg(target_pointer_width = "64")]
#[cfg(not(feature = "high_assurance"))] // Disabled
{
    assert_eq!(size_of::<SGMap<u64, u64>>(), 57_440);
}

// With packing
#[cfg(target_pointer_width = "64")]
#[cfg(feature = "high_assurance")]  // Enabled
{
    assert_eq!(size_of::<SGMap<u64, u64>>(), 26_688);
}

} ```

Considerations

General Goals

This project is an exercise in safe, portable data structure design. The goal is to offer embedded developers familiar, ergonomic APIs on resource constrained systems that otherwise don't get the luxury of dynamic collections. Without sacrificing safety.

scapegoat is not as fast or mature as the standard library's BTreeMap/BTreeSet (benchmarks via cargo bench). The standard library has been heavily optimized for cache performance. This library is optimized for low, stack-only memory footprint. It offers:

Algorithmic Complexity

Space complexity is always O(n).

| Operation | Average Case | Worst Case | | --- | --- | --- | | get | O(log n) | O(log n) | | insert | O(log n) | Amortized O(log n) | | remove | O(log n) | Amortized O(log n) |

The low_mem_insert and fast_rebalance features can be used to fine-tune tradeoffs of memory usage and speed.

Memory Footprint Demos

Trusted Dependencies

This library has three dependencies, each of which have no dependencies of their own (e.g. exactly three total dependencies).

License and Contributing

Licensed under the MIT license. Contributions are welcome!