Expand description
A space-efficient bitmap implementation with inline storage optimization.
This crate provides SmolBitmap, a bitmap that stores bits either inline
(for small bitmaps up to 127 bits) or on the heap (for larger bitmaps). The
implementation uses a clever encoding scheme where the highest bit of the
last word indicates whether the storage is inline or external.
§Features
- Zero allocation for bitmaps up to 127 bits
- Automatic promotion to heap storage when needed
- Efficient set operations (union, intersection, difference, symmetric difference)
- Iterator support for bit positions
- Serialization support via serde (optional)
no_stdsupport withallocfor embedded systems
§Examples
use smol_bitmap::SmolBitmap;
// Create a new bitmap
let mut bitmap = SmolBitmap::new();
// Set some bits
bitmap.set(10, true);
bitmap.set(42, true);
bitmap.set(127, true); // Still inline!
// Check if bits are set
assert!(bitmap.get(10));
assert!(!bitmap.get(11));
// Iterate over set bits
for bit in bitmap.iter() {
println!("Bit {} is set", bit);
}
// Set operations
let mut other = SmolBitmap::new();
other.set(10, true);
other.set(50, true);
let union = bitmap.union(&other);
let intersection = bitmap.intersection(&other);§Storage Strategy
The bitmap uses a hybrid storage strategy:
- Inline storage: Up to 127 bits stored directly in the struct (16 bytes)
- Heap storage: Automatically switches to heap allocation for larger bitmaps
The transition is completely transparent to the user.
§Performance
SmolBitmap is optimized for the common case of small bitmaps while still
supporting arbitrary sizes efficiently. Key performance characteristics:
- Setting/getting bits is O(1)
- Set operations are O(n) where n is the number of words
- No allocation overhead for bitmaps ≤ 127 bits
- Memory-efficient for sparse bitmaps
Re-exports§
pub use bitmap::SmolBitmap;pub use iter::BitIter;pub use iter::IntoIter;pub use iter::Iter;pub use iter::SelectIter;pub use storage::SmolBitmapBuilder;pub use traits::ParseBitmapError;pub use traits::TryFromBitmapError;