Crate sparsemap 

A sparse, compressed bitmap (bitset) over u64 indices, optimized for workloads with long runs of consecutive set bits.

sparsemap is the Rust port of the C sparsemap library. It is functionally identical: the same set semantics, the same compression behavior, and a wire-compatible serialized format, so a map written by either implementation can be read by the other.

Model

The universe is divided into fixed 2048-bit windows. Each window that contains data is stored as one of two chunk kinds:

• a run of one or more entirely-set windows, stored in O(1) space regardless of length — a run of two billion set bits is a handful of bytes; and
• a dense window of 2048 bits (32 × u64) for mixed regions, costing one bit per bit.

Empty windows are not stored at all. This makes sparsemap cheap for the two regimes that matter — long runs and sparse clusters — while degrading gracefully to a plain bitmap for random data.

Example

use sparsemap::SparseMap;

let mut m = SparseMap::new();
m.insert(42);
m.insert(1024);
assert!(m.contains(42));
assert_eq!(m.cardinality(), 2);

// Idiomatic set algebra.
let a: SparseMap = (0..100).collect();
let b: SparseMap = (50..150).collect();
assert_eq!((&a & &b).cardinality(), 50);
assert_eq!((&a | &b).cardinality(), 150);

// Ascending iteration.
let evens: SparseMap = (0..10).filter(|n| n % 2 == 0).collect();
assert_eq!(evens.iter().collect::<Vec<_>>(), vec![0, 2, 4, 6, 8]);

Thread safety

SparseMap is Send + Sync and follows the usual Rust borrowing rules: shared references allow concurrent reads, a unique reference is required to mutate. There is no interior mutability.

no_std

The crate is #![no_std] and depends only on alloc.

Structs

Iter

An iterator over the set bits of a SparseMap in ascending order.

SparseMap

A sparse, compressed, run-length-encoded bitset over u64 indices.

Enums

DecodeError

Error returned by SparseMap::from_bytes for malformed input.