Ordered set and map data structures via an arena-based scapegoat tree (memory-efficient, self-balancing binary search tree).
#![forbid(unsafe_code)].!#[no_std] by default.BTreeSet and BTreeMap.Three APIs:
SGSet) - subset of BTreeSet nightly.SGMap) - subset of BTreeMap nightly.SGTree) - backend for the previous two.Strives for two properties:
Maximal safety: strong memory safety guarantees, hence #![forbid(unsafe_code)].
unsafe (no raw pointer dereference, etc.).debug_assert! for logical invariants exercised in testing.Rc<RefCell<T>>'s runtime check).Minimal footprint: low resource use, hence !#[no_std].
Other features:
Ord trait.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
.iter()
.map(|(_, v)| *v)
.collect:: Additional examples here. The maximum number of stack-stored elements (set) or key-value pairs (map/tree) is determined at compile-time, via the environment variable Please note: If the For any system with heap memory: the first For embedded systems with only stack memory: Warning:
Although stack usage is constant (no recursion), a stack overflow can happen at runtime if For more advanced configuration options, see the documentation here. For embedded use cases prioritizing robustness (or kernelspace code), enabling the Front-end, API Tweak: 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 // This code assumes }
``` This library has three dependencies, each of which have no dependencies of their own (e.g. exactly three total dependencies). This project is an exercise in safe, portable data structure design.
It's not as mature, fast, or memory efficient as the standard library's Best-effort Compatibility: APIs are a subset of Dynamic Validation: Coverage-guided differential fuzzing is used to demonstrate that this implementation is logically equivalent and equally reliable. Licensed under the MIT license.
Contributions are welcome!Configuring a Stack Storage Limit
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
SG_MAX_STACK_ELEMS environment variable is not set, it will default to 1024.SG_MAX_STACK_ELEMS elements are stack-allocated and the remainder will be automatically heap-allocated.SG_MAX_STACK_ELEMS is a hard maximum - attempting to insert beyond this limit will cause a panic.
high_assurance to ensure error handling and avoid panic (see below).
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.The
high_assurance Featurehigh_assurance feature makes two changes:
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.cfg macros below.
// Internally, this compile-time struct packing is done with the smallnum crate:
// https://crates.io/crates/smallnumSG_MAX_STACK_ELEMS == 1024 (default)
let temp: SGMap// Without packing
#[cfg(target_pointer_width = "64")]
#[cfg(not(feature = "high_assurance"))]
{
assert_eq!(size_of::<SGMap<u64, u64>>(), 57_432);
}
// With packing
#[cfg(target_pointer_width = "64")]
#[cfg(feature = "high_assurance")]
{
assert_eq!(size_of::<SGMap<u64, u64>>(), 26_680);
}
Trusted Dependencies
smallvec - !#[no_std] compatible Vec alternative. Used in Mozilla's Servo browser engine.micromath - !#[no_std], #![forbid(unsafe_code)] floating point approximations.smallnum - !#[no_std], #![forbid(unsafe_code)] integer packing.Considerations
BTreeMap/BTreeSet (benchmarks via cargo bench).
It does, however, offer:
BTreeMap's/BTreeSet's, making it a somewhat "drop-in" replacement for !#[no_std] systems. Please open an issue if an API you need isn't yet supported!License and Contributing