Struct BitMap 

pub struct BitMap<const N: usize, S: State = Clean> { /* private fields */ }

A historical bitmap that maintains one actual bitmap plus diffs for history.

Uses a type-state pattern to track whether the bitmap is clean (no pending mutations) or dirty (has pending mutations).

Commit numbers must be strictly monotonically increasing and < u64::MAX.

Implementations

impl<const N: usize> BitMap<N>

pub const fn new() -> Self

Create a new empty historical bitmap.

pub fn new_with_pruned_chunks(pruned_chunks: usize) -> Result<Self, Error>

Create a new historical bitmap with the given number of pruned chunks.

pub fn into_dirty(self) -> DirtyBitMap<N>

Transition to dirty state to begin making mutations.

All mutations are applied to a diff layer and do not affect the current bitmap until commit.

Examples

let bitmap: BitMap<4> = BitMap::new();

let mut dirty = bitmap.into_dirty();
dirty.push(true);
dirty.push(false);
let bitmap = dirty.commit(1).unwrap();

assert_eq!(bitmap.len(), 2);

pub fn apply_batch<F>(self, commit_number: u64, f: F) -> Result<Self, Error>

where F: FnOnce(&mut DirtyBitMap<N>),

Execute a closure with a dirty bitmap and commit it at the given commit number.

Errors

Returns Error::NonMonotonicCommit if the commit number is not greater than the previous commit.

Returns Error::ReservedCommitNumber if the commit number is u64::MAX.

Examples

let mut bitmap: BitMap<4> = BitMap::new();

bitmap = bitmap.apply_batch(1, |dirty| {
    dirty.push(true).push(false);
}).unwrap();

assert_eq!(bitmap.len(), 2);

pub fn get_at_commit(&self, commit_number: u64) -> Option<Prunable<N>>

Get the bitmap state as it existed at a specific commit.

Returns None if the commit does not exist or if commit_number is u64::MAX (which is reserved and cannot be used as a commit number).

This reconstructs the historical state by applying reverse diffs backward from the current state. Each commit’s reverse diff describes the state before that commit, so we “undo” commits one by one until we reach the target.

Examples

let mut bitmap: BitMap<4> = BitMap::new();

bitmap = bitmap.apply_batch(1, |dirty| {
    dirty.push(true);
    dirty.push(false);
}).unwrap();

bitmap = bitmap.apply_batch(2, |dirty| {
    dirty.set_bit(0, false);
    dirty.push(true);
}).unwrap();

// Get state as it was at commit 1
let state_at_1 = bitmap.get_at_commit(1).unwrap();
assert_eq!(state_at_1.len(), 2);
assert!(state_at_1.get_bit(0));
assert!(!state_at_1.get_bit(1));

// Current state is different
assert_eq!(bitmap.len(), 3);
assert!(!bitmap.get_bit(0));

pub fn commit_exists(&self, commit_number: u64) -> bool

Check if a commit exists.

pub fn commits(&self) -> impl Iterator<Item = u64> + '_

Get an iterator over all commit numbers in ascending order.

pub fn latest_commit(&self) -> Option<u64>

Get the latest commit number, if any commits exist.

pub fn earliest_commit(&self) -> Option<u64>

Get the earliest commit number, if any commits exist.

pub const fn current(&self) -> &Prunable<N>

Get a reference to the current bitmap state.

pub const fn len(&self) -> u64

Number of bits in the current bitmap.

pub const fn is_empty(&self) -> bool

Returns true if the current bitmap is empty.

pub fn get_bit(&self, bit: u64) -> bool

Get the value of a bit in the current bitmap.

pub fn get_chunk_containing(&self, bit: u64) -> &[u8; N]

Get the chunk containing a bit in the current bitmap.

pub const fn pruned_chunks(&self) -> usize

Number of pruned chunks in the current bitmap.

pub fn prune_commits_before(&mut self, commit_number: u64) -> usize

Remove all commits with numbers below the commit number.

Returns the number of commits removed.

pub fn clear_history(&mut self)

Clear all historical commits.

impl<const N: usize> BitMap<N, Dirty<N>>

pub const fn len(&self) -> u64

Get the length of the bitmap as it would be after committing.

pub const fn is_empty(&self) -> bool

Returns true if the bitmap would be empty after committing.

pub const fn pruned_chunks(&self) -> usize

Get the number of pruned chunks after committing.

pub fn get_bit(&self, bit: u64) -> bool

Get a bit value with read-through semantics.

Returns the bit’s value as it would be after committing. Priority: appended bits > modified bits > original bitmap.

Panics

Panics if the bit offset is out of bounds or if the bit has been pruned.

pub fn get_chunk(&self, bit: u64) -> [u8; N]

Get a chunk value with read-through semantics.

Reconstructs the chunk if it has modifications, otherwise returns from current.

Panics

Panics if the bit offset is out of bounds or if the chunk has been pruned.

pub fn set_bit(&mut self, bit: u64, value: bool) -> &mut Self

Set a bit value.

Panics

Panics if the bit offset is out of bounds or if the bit has been pruned.

pub fn push(&mut self, bit: bool) -> &mut Self

Push a bit to the end of the bitmap.

pub fn push_byte(&mut self, byte: u8) -> &mut Self

Push a byte to the end of the bitmap.

pub fn push_chunk(&mut self, chunk: &[u8; N]) -> &mut Self

Push a full chunk to the end of the bitmap.

pub fn pop(&mut self) -> bool

Pop the last bit from the bitmap.

Returns the value of the popped bit, accounting for any modifications.

Panics

Panics if the bitmap is empty.

pub fn prune_to_bit(&mut self, bit: u64) -> &mut Self

Prune chunks up to the chunk containing the given bit offset.

Note: bit can equal projected_len when pruning at a chunk boundary.

Panics

Panics if bit is > the projected length.

pub fn commit(self, commit_number: u64) -> Result<CleanBitMap<N>, Error>

Commit the changes and return a clean bitmap with a historical snapshot.

Errors

Returns Error::NonMonotonicCommit if the commit number is not greater than the previous commit.

Returns Error::ReservedCommitNumber if the commit number is u64::MAX.

pub fn abort(self) -> CleanBitMap<N>

Abort the changes and return to clean state.

All pending mutations are discarded.

Trait Implementations

impl<const N: usize, S: Clone + State> Clone for BitMap<N, S>

fn clone(&self) -> BitMap<N, S>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<const N: usize, S: Debug + State> Debug for BitMap<N, S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.