small_collections/
lib.rs

1#![doc = include_str!("../README.md")]
2//! # Small Collections
3//!
4//! A collection of data structures optimized for small-buffer scenarios.
5//!
6//! ## Overview
7//! This crate provides a variety of collections that are designed to reside on the stack
8//! up to a specific capacity `N`. If the collection exceeds this capacity, it automatically
9//! "spills" its contents to a corresponding heap-allocated collection from the standard library
10//! or specialized crates (like `hashbrown` or `bitvec`).
11//!
12//! This approach balances the performance benefits of zero-allocation stack storage for small workloads
13//! with the flexibility of heap storage for larger or unpredictable workloads.
14//!
15//! ## Key Features
16//! - **Zero-Allocation Initial State:** All collections start on the stack.
17//! - **Automatic Spill:** Seamless transition to heap storage when needed.
18//! - **Efficient Spills:** Items are moved (bitwise copy/ownership transfer), never cloned during a spill.
19//! - **Safety:** Extensively verified with Miri to ensure zero memory leaks and no Undefined Behavior (UB).
20//!
21//! ## Documentation Examples
22//!
23//! ### SmallVec
24//! ```rust
25//! use small_collections::{SmallVec, AnyVec};
26//! let mut v: SmallVec<i32, 4> = SmallVec::new();
27//! v.push(1);
28//! v.push(2);
29//! assert!(v.is_on_stack()); // Stays on stack
30//!
31//! v.extend(vec![3, 4, 5]);   // Exceeds capacity of 4
32//! assert!(!v.is_on_stack()); // Spilled to heap
33//! assert_eq!(v.pop(), Some(5));
34//!
35//! // Dynamic trait usage via AnyVec
36//! fn print_len<T>(v: &impl AnyVec<T>) {
37//!     assert_eq!(v.len(), 4);
38//! }
39//! print_len(&v);
40//! ```
41//!
42//! ### SmallDeque
43//! ```rust
44//! use small_collections::{SmallDeque, AnyDeque};
45//! let mut d: SmallDeque<i32, 4> = SmallDeque::new();
46//! d.push_back(1);
47//! d.push_front(2);
48//! assert_eq!(d.pop_back(), Some(1));
49//! assert!(d.is_on_stack());
50//!
51//! d.extend(vec![3, 4, 5, 6]);
52//! assert!(!d.is_on_stack());
53//! ```
54//!
55//! ### SmallString
56//! ```rust
57//! use small_collections::{SmallString, AnyString};
58//! let mut s: SmallString<16> = SmallString::new();
59//! s.push_str("Hello");
60//! assert!(s.is_on_stack());
61//!
62//! s.push_str(", World! This is a long string that will spill.");
63//! assert!(!s.is_on_stack());
64//! assert_eq!(s.len(), 52);
65//! ```
66//!
67//! ### SmallMap & SmallSet
68//! ```rust
69//! use small_collections::{SmallMap, SmallSet, AnyMap, AnySet};
70//! let mut map: SmallMap<&str, i32, 4> = SmallMap::new();
71//! map.insert("key", 10);
72//! assert!(map.is_on_stack());
73//!
74//! let mut set: SmallSet<i32, 4> = SmallSet::new();
75//! set.insert(1);
76//! assert!(set.is_on_stack());
77//! ```
78//!
79//! ### SmallBTreeMap & SmallBTreeSet
80//! ```rust
81//! use small_collections::{SmallBTreeMap, SmallBTreeSet};
82//! let mut bmap: SmallBTreeMap<i32, i32, 4> = SmallBTreeMap::new();
83//! bmap.insert(1, 10);
84//!
85//! let mut bset: SmallBTreeSet<i32, 4> = SmallBTreeSet::new();
86//! bset.insert(1);
87//! bset.insert(2);
88//! bset.insert(3);
89//! bset.insert(4);
90//! bset.insert(5); // Spills to heap
91//! assert!(!bset.is_on_stack());
92//! ```
93//!
94//! ### SmallOrderedMap & SmallOrderedSet
95//! ```rust
96//! use small_collections::{SmallOrderedMap, SmallOrderedSet};
97//! let mut omap: SmallOrderedMap<i32, i32, 4> = SmallOrderedMap::new();
98//! omap.insert(1, 10); // Maintains insertion order
99//!
100//! let mut oset: SmallOrderedSet<i32, 4> = SmallOrderedSet::new();
101//! oset.insert(1);
102//! ```
103//!
104//! ### SmallBinaryHeap
105//! ```rust
106//! use small_collections::{SmallBinaryHeap, AnyHeap};
107//! let mut heap: SmallBinaryHeap<i32, 4> = SmallBinaryHeap::new();
108//! heap.push(10);
109//! heap.push(20);
110//! assert_eq!(heap.pop(), Some(20));
111//! assert!(heap.is_on_stack());
112//!
113//! heap.extend(vec![30, 40, 50, 60]);
114//! assert!(!heap.is_on_stack()); // Spills logic seamlessly
115//! ```
116//!
117//! ### SmallLruCache
118//! ```rust
119//! use small_collections::{SmallLruCache, AnyLruCache};
120//! use std::num::NonZeroUsize;
121//! let mut cache: SmallLruCache<i32, i32, 4> = SmallLruCache::new(NonZeroUsize::new(2).unwrap());
122//! cache.put(1, 10);
123//! cache.put(2, 20);
124//! cache.put(3, 30); // Evicts key 1 based on LRU
125//! assert_eq!(cache.get(&1), None);
126//! assert_eq!(cache.get(&2), Some(&20));
127//! ```
128//!
129//! ### SmallBitVec
130//! ```rust
131//! use small_collections::{SmallBitVec, AnyBitVec};
132//! let mut bv: SmallBitVec<4> = SmallBitVec::new(); // 4 bytes = 32 bits
133//! bv.push(true);
134//! assert!(bv.get(0).unwrap());
135//! assert!(bv.is_on_stack());
136//!
137//! for _ in 0..40 {
138//!     bv.push(false);
139//! }
140//! assert!(!bv.is_on_stack()); // Automatically spilled to a heap allocated BitVec
141//! ```
142//!
143//! ### Pure Heapless Collections
144//! ```rust
145//! use small_collections::{HeaplessBTreeMap, HeaplessBitVec};
146//! // Use these if you want strict stack-only collections without heap-spill overhead.
147//! let mut bmap: HeaplessBTreeMap<i32, i32, 4> = HeaplessBTreeMap::new();
148//! assert_eq!(bmap.insert(1, 10), Ok(None));
149//!
150//! let mut bv: HeaplessBitVec<4> = HeaplessBitVec::new();
151//! let _ = bv.push(true);
152//! ```
153//!
154//! ## Capacity Constraints
155//! Many collections using the `heapless` backend require `N` to be a power of two and greater than 1.
156//! These constraints are enforced at compile time.
157
158// --- Module Declarations ---
159
160/// Exposes cache collection module.
161pub mod cache;
162/// Exposes maps collection module.
163pub mod maps;
164/// Exposes sets collection module.
165pub mod sets;
166/// Exposes utils collection module.
167pub mod utils;
168/// Exposes vecs collection module.
169pub mod vecs;
170
171pub mod heap;
172pub mod string;
173
174#[cfg(feature = "lru")]
175pub use cache::heapless_btree_lru_cache::HeaplessBTreeLruCache;
176#[cfg(feature = "lru")]
177pub use cache::heapless_linear_lru_cache::HeaplessLinearLruCache;
178#[cfg(feature = "lru")]
179pub use cache::heapless_lru_cache::HeaplessLruCache;
180#[cfg(feature = "lru")]
181pub use cache::lru_cache::{AnyLruCache, SmallLruCache};
182pub use heap::{AnyHeap, SmallBinaryHeap};
183pub use maps::btree_map::{AnyBTreeMap, SmallBTreeMap};
184pub use maps::heapless_btree_map::{Entry as BTreeEntry, HeaplessBTreeMap};
185#[cfg(feature = "ordered")]
186pub use maps::heapless_ordered_map::HeaplessOrderedMap;
187pub use maps::map::{AnyMap, SmallMap, SmallMapIntoIter, SmallMapIter};
188#[cfg(feature = "ordered")]
189pub use maps::ordered_map::SmallOrderedMap;
190pub use sets::btree_set::SmallBTreeSet;
191#[cfg(feature = "ordered")]
192pub use sets::ordered_set::SmallOrderedSet;
193pub use sets::set::{AnySet, SetRefIter, SmallSet, SmallSetIntoIter};
194pub use string::{AnyString, SmallString};
195#[cfg(feature = "lru")]
196pub use utils::index_type::IndexType;
197#[cfg(feature = "bitvec")]
198pub use vecs::bitvec::{AnyBitVec, SmallBitVec};
199pub use vecs::deque::{AnyDeque, SmallDeque};
200#[cfg(feature = "bitvec")]
201pub use vecs::heapless_bitvec::HeaplessBitVec;
202pub use vecs::vec::{AnyVec, SmallVec};
small_collections/lib.rs

small_collections/
lib.rs
