smol_bitmap/
lib.rs

1//! A space-efficient bitmap implementation with inline storage optimization.
2//!
3//! This crate provides [`SmolBitmap`], a bitmap that stores bits either inline
4//! (for small bitmaps up to 127 bits) or on the heap (for larger bitmaps). The
5//! implementation uses a clever encoding scheme where the highest bit of the
6//! last word indicates whether the storage is inline or external.
7//!
8//! # Features
9//!
10//! - **Zero allocation** for bitmaps up to 127 bits
11//! - **Automatic promotion** to heap storage when needed
12//! - **Efficient set operations** (union, intersection, difference, symmetric
13//!   difference)
14//! - **Iterator support** for bit positions
15//! - **Serialization support** via serde (optional)
16//! - **`no_std` support** with `alloc` for embedded systems
17//!
18//! # Examples
19//!
20//! ```
21//! use smol_bitmap::SmolBitmap;
22//!
23//! // Create a new bitmap
24//! let mut bitmap = SmolBitmap::new();
25//!
26//! // Set some bits
27//! bitmap.insert(10);
28//! bitmap.insert(42);
29//! bitmap.insert(127); // Still inline!
30//!
31//! // Check if bits are set
32//! assert!(bitmap.get(10));
33//! assert!(!bitmap.get(11));
34//!
35//! // Iterate over set bits
36//! for bit in bitmap.iter() {
37//!     println!("Bit {} is set", bit);
38//! }
39//!
40//! // Set operations
41//! let mut other = SmolBitmap::new();
42//! other.insert(10);
43//! other.insert(50);
44//!
45//! let union = bitmap.union(&other);
46//! let intersection = bitmap.intersection(&other);
47//! ```
48//!
49//! # Storage Strategy
50//!
51//! The bitmap uses a hybrid storage strategy:
52//!
53//! - **Inline storage**: Up to 127 bits stored directly in the struct (16
54//!   bytes)
55//! - **Heap storage**: Automatically switches to heap allocation for larger
56//!   bitmaps
57//!
58//! The transition is completely transparent to the user.
59//!
60//! # Performance
61//!
62//! `SmolBitmap` is optimized for the common case of small bitmaps while still
63//! supporting arbitrary sizes efficiently. Key performance characteristics:
64//!
65//! - Setting/getting bits is O(1)
66//! - Set operations are O(n) where n is the number of words
67//! - No allocation overhead for bitmaps ≤ 127 bits
68//! - Memory-efficient for sparse bitmaps
69
70#![cfg_attr(not(feature = "std"), no_std)]
71#![warn(missing_docs)]
72
73extern crate alloc;
74
75// Module declarations
76mod bitmap;
77mod iter;
78mod macros;
79mod ser;
80mod set_ops;
81pub mod storage;
82pub mod traits;
83
84#[cfg(feature = "rkyv")]
85pub mod rkyv;
86
87#[cfg(feature = "rkyv")]
88pub use rkyv::{ArchivedSmolBitmap, SmolBitmapResolver};
89
90#[cfg(feature = "serde")]
91pub mod serde;
92
93// Re-exports
94pub use bitmap::SmolBitmap;
95pub use iter::{BitIter, IntoIter, Iter, SelectIter};
96pub use storage::SmolBitmapBuilder;
97pub use traits::{ParseBitmapError, TryFromBitmapError};
98
99/// Creates a `SmolBitmap` from a list of bit positions.
100///
101/// This macro takes a comma-separated list of `usize` values representing
102/// bit positions to set. It automatically determines the required capacity
103/// based on the maximum bit position and creates an appropriately sized
104/// bitmap.
105///
106/// # Examples
107///
108/// ```
109/// use smol_bitmap::{SmolBitmap, bitmap};
110///
111/// // Create a bitmap with bits 1, 5, and 10 set
112/// let bmp = bitmap![1, 5, 10];
113/// assert!(bmp.get(1));
114/// assert!(bmp.get(5));
115/// assert!(bmp.get(10));
116/// assert!(!bmp.get(0));
117/// assert!(!bmp.get(3));
118///
119/// // Empty bitmap
120/// let empty = bitmap![];
121/// assert_eq!(empty.capacity(), SmolBitmap::inline_capacity());
122///
123/// // Large bit positions automatically allocate heap storage
124/// let large = bitmap![100, 200, 300];
125/// assert!(large.get(100));
126/// assert!(large.get(200));
127/// assert!(large.get(300));
128/// ```
129#[macro_export]
130macro_rules! bitmap {
131    () => {
132        $crate::SmolBitmap::new()
133    };
134    ($($bit:expr),+ $(,)?) => {{
135        let bits = [$($bit),+];
136        let capacity = bits.iter().copied().max().map(|max| max + 1).unwrap_or(0);
137        let mut bitmap = $crate::SmolBitmap::with_capacity(capacity);
138        for bit in bits {
139            bitmap.insert(bit);
140        }
141        bitmap
142    }};
143}
smol_bitmap/lib.rs

smol_bitmap/
lib.rs
