pub struct RoaringBitmap<M: Memory> { /* private fields */ }Expand description
Stable roaring bitmap with a heap mirror and a durable journal.
§Documentation split
crate::bitmap: on-disk layout, packed journal record format, and compatibility rules.RoaringBitmap(this type): logical length semantics (len, out-of-rangecontains), what is persisted when,Self::initas the normal entry point (canister code), checkpoint behavior, and method-level complexity.
§Storage model
Reads use a heap-backed
roaring::RoaringBitmap.
Writes append 5-byte journal records (see crate::bitmap) and update that mirror. A
serialized roaring snapshot in stable memory starts at an 8-byte aligned offset after the
journal region (with up to 7 bytes of zero padding).
§Checkpointing and amortization
The journal holds a fixed build-time number of records. To ensure a mutation that returns an error has not been journaled, the implementation checkpoints before an append would consume the final slot. A full journal from a previous build is checkpointed before any further append. That checkpoint costs Θ(S) time and I/O where S is the serialized snapshot size in bytes (and may grow stable memory). Between checkpoints, bit mutations cost O(1) amortized typical roaring work plus O(1) journal I/O per state-changing operation.
A few methods call the overflow check even when no journal append occurs, so rare Θ(S)
work can still run when opening a legacy full journal (see Self::set).
§Failure atomicity
On ICP, mutation and checkpoint writes execute synchronously within one message execution. The platform commits heap and stable-memory changes only on success and rolls them back on a trap or panic; see ICP Message Execution Property 5.
Checkpoint serialization uses multiple Memory::write calls. This type therefore does not
provide generic process-crash atomicity for a custom Memory whose individual writes persist
across an interruption. Such an implementation must supply an equivalent rollback or
transactional boundary.
§Concurrency
Interior mutability backs the heap mirror; treat this type as single-writer. Do not alias
the same Memory through another API while an instance is live.
Implementations§
Source§impl<M: Memory> RoaringBitmap<M>
impl<M: Memory> RoaringBitmap<M>
Sourcepub fn new(memory: M) -> Result<Self, BitmapError>
pub fn new(memory: M) -> Result<Self, BitmapError>
Writes an empty layout: header, zeroed journal padding up to the aligned snapshot base, and an empty heap mirror.
Canister code should call Self::init instead—that is the single supported entry
point for opening stable memory (including the first time, when memory.size() == 0, which
forwards here). Self::new remains public for tests and advanced callers that need
InitError-free bootstrap errors (BitmapError).
§Errors
Returns BitmapError when header setup or padding writes fail.
§Time complexity
O(1) with respect to bitmap contents (fixed header and journal layout).
Sourcepub fn init(memory: M) -> Result<Self, InitError>
pub fn init(memory: M) -> Result<Self, InitError>
Primary entry point: open the bitmap from stable memory on every canister entry / reload (cold start with no pages yet, upgrade with existing bytes, or steady state).
Validates the header, deserializes the roaring snapshot, and replays journal records up to
the first all-zero slot (see crate).
When memory.size() == 0, this forwards to Self::new and maps any BitmapError to
InitError::OutOfMemory (storage bootstrap failure).
§Errors
Returns InitError when magic/version/journal metadata disagree, lengths are inconsistent
with the backing memory, the snapshot deserialize fails, or a journal record fails
validation. In particular, the header journal_slots field must match
the build-time journal capacity: otherwise InitError::InvalidLayout is returned—stable
memory laid out under a different compile-time journal capacity cannot be reused without an
application-level migration.
§Time complexity
Let S be the stored snapshot length in bytes and K the number of contiguous journal
records before the first all-zero slot. Decoding the
snapshot costs Θ(S). Recovery reads journal chunks through the chunk containing that
first empty slot. Replaying K records costs Σ per-record work: typically O(1)
amortized for SetBit replay, while a shrinking SetLen applies
remove_range/remove_suffix-style work O(C) over roaring containers intersecting the
dropped suffix (C ≤ number of containers in the map).
Sourcepub fn into_memory(self) -> M
pub fn into_memory(self) -> M
Sourcepub fn len(&self) -> u64
pub fn len(&self) -> u64
Returns the exclusive logical bit length (len_bits): valid indices are 0..len().
This is not the count of set bits (cardinality).
§Time complexity
O(1).
Sourcepub fn contains(&self, index: u32) -> bool
pub fn contains(&self, index: u32) -> bool
Tests whether the bit is set using the heap mirror only (stable memory is not consulted).
Indices >= len() yield false without extending the bitmap.
§Time complexity
O(1).
Sourcepub fn contains_view(&self) -> ContainsView<'_>
pub fn contains_view(&self) -> ContainsView<'_>
Returns a borrowed view for repeated ContainsView::contains calls (see ContainsView).
§Time complexity
O(1) (one RefCell borrow).
Sourcepub fn ensure_len(&self, min_len: u64) -> Result<(), BitmapError>
pub fn ensure_len(&self, min_len: u64) -> Result<(), BitmapError>
Grows the exclusive logical length to min_len if needed, without materializing unset bits.
No-op when min_len <= len().
§Errors
Returns BitmapError::LimitsExceeded when min_len exceeds the supported logical bit length,
or other BitmapError variants when journaling or checkpointing fails. On any error, this
call has not changed the logical bitmap.
§Time complexity
O(1) on the no-op path.
When min_len is larger, this appends a SetLen journal record and may checkpoint; work is
O(1) amortized for steady mutations between checkpoints, with rare Θ(S) checkpoints
for serialized snapshot size S. Only growing the length does not enumerate unset
bits in the roaring structure.
Sourcepub fn set(&self, index: u32, value: bool) -> Result<(), BitmapError>
pub fn set(&self, index: u32, value: bool) -> Result<(), BitmapError>
Sets or clears a bit, journaling only when the logical value changes.
Idempotent: if the bit already equals value, no journal record is appended. The
value == true path still performs the journal-full overflow check and may therefore run a
Θ(S) checkpoint even when the bit was already set.
Setting true can extend Self::len to index + 1 without a separate SetLen record.
§Errors
Returns BitmapError::LimitsExceeded if index + 1 as u64 would exceed the supported logical bit length
(this is unreachable for any u32 index, but kept for API symmetry), or other BitmapError
variants when journaling or checkpointing fails. On any error, this call has not changed the
logical bitmap.
§Time complexity
O(1) to test Self::contains on the no-append paths.
When the stored bit changes, expect O(1) amortized roaring updates and journal I/O, plus Θ(S) when a checkpoint runs (S = serialized snapshot size).
Sourcepub fn insert(&self, index: u32) -> Result<(), BitmapError>
pub fn insert(&self, index: u32) -> Result<(), BitmapError>
Equivalent to self.set(index, true). See Self::set for journaling rules and complexity.
Sourcepub fn clear(&self, index: u32) -> Result<(), BitmapError>
pub fn clear(&self, index: u32) -> Result<(), BitmapError>
Equivalent to self.set(index, false). See Self::set for journaling rules and complexity.
Sourcepub fn truncate(&self, new_len: u64) -> Result<(), BitmapError>
pub fn truncate(&self, new_len: u64) -> Result<(), BitmapError>
Shrinks the exclusive logical length to new_len, clearing set bits at indices >= new_len.
No-op when new_len >= len().
§Errors
Returns BitmapError::LimitsExceeded when new_len exceeds the supported logical bit length,
or other BitmapError variants when journaling or checkpointing fails. On any error, this
call has not changed the logical bitmap.
§Time complexity
O(1) on the no-op path.
Otherwise O(C) to clear the suffix where C is the number of roaring containers overlapping the removed range, plus journal append and Θ(S) checkpoints (S = serialized snapshot size) when the journal is full.