Crate smol_bitmap 

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_std support with alloc for embedded systems

Examples

use smol_bitmap::SmolBitmap;

// Create a new bitmap
let mut bitmap = SmolBitmap::new();

// Set some bits
bitmap.insert(10);
bitmap.insert(42);
bitmap.insert(127); // 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.insert(10);
other.insert(50);

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 rkyv::ArchivedSmolBitmap;

pub use rkyv::SmolBitmapResolver;

pub use storage::SmolBitmapBuilder;

pub use traits::ParseBitmapError;

pub use traits::TryFromBitmapError;

Modules

rkyv

Rkyv implementation for SmolBitmap.

serde

Serde implementations for SmolBitmap.

storage

Internal storage representation and management for the bitmap.

traits

Trait implementations for SmolBitmap.

Macros

bitmap

Creates a SmolBitmap from a list of bit positions.

Structs

BitIter

An iterator over the indices of set bits in a bitmap.

SelectIter

An iterator that selects elements from another iterator based on set bits in a bitmap.

SmolBitmap

A compact bitmap that stores bits either inline or on the heap.

Type Aliases

IntoIter

An owning iterator over the indices of set bits in a SmolBitmap.

Iter

An iterator over the indices of set bits in a SmolBitmap.