Struct BitMap 

pub struct BitMap<const N: usize = DEFAULT_CHUNK_SIZE> { /* private fields */ }

A bitmap that stores data in chunks of N bytes.

Panics

Operations panic if bit / CHUNK_SIZE_BITS > usize::MAX. On 32-bit systems with N=32, this occurs at bit >= 1,099,511,627,776.

Implementations

impl<const N: usize> BitMap<N>

pub const CHUNK_SIZE_BITS: u64

The size of a chunk in bits.

pub const fn new() -> Self

Create a new empty bitmap.

pub fn with_capacity(size: u64) -> Self

pub fn zeroes(size: u64) -> Self

Create a new bitmap with size bits, with all bits set to 0.

pub fn ones(size: u64) -> Self

Create a new bitmap with size bits, with all bits set to 1.

pub const fn len(&self) -> u64

Return the number of bits currently stored in the bitmap.

pub const fn is_empty(&self) -> bool

Returns true if the bitmap is empty.

pub const fn is_chunk_aligned(&self) -> bool

Returns true if the bitmap length is aligned to a chunk boundary.

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

Get the value of the bit at the given index.

Warning

Panics if the bit doesn’t exist.

pub const fn get_bit_from_chunk(chunk: &[u8; N], bit: u64) -> bool

Get the value at the given bit from the chunk. bit is an index into the entire bitmap, not just the chunk.

pub fn extend_to(&mut self, new_len: u64)

Extend the bitmap to new_len bits, filling new positions with zero. No-op if new_len <= self.len.

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

Add a single bit to the bitmap.

pub fn pop(&mut self) -> bool

Remove and return the last bit from the bitmap.

Warning

Panics if the bitmap is empty.

pub fn truncate(&mut self, new_len: u64)

Shrink the bitmap to new_len bits, discarding trailing bits.

Panics

Panics if new_len > self.len().

pub fn flip(&mut self, bit: u64)

Flips the given bit.

Panics

Panics if bit is out of bounds.

pub fn flip_all(&mut self)

Flips all bits (1s become 0s and vice versa).

pub fn set(&mut self, bit: u64, value: bool)

Set the value of the referenced bit.

Warning

Panics if the bit doesn’t exist.

pub fn set_all(&mut self, bit: bool)

Sets all bits to the specified value.

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

Add a chunk of bits to the bitmap.

Warning

Panics if self.len is not chunk aligned.

pub fn count_ones(&self) -> u64

Returns the number of bits set to 1.

pub fn count_zeros(&self) -> u64

Returns the number of bits set to 0.

pub const fn iter(&self) -> Iterator<'_, N>

Creates an iterator over the bits.

pub fn ones_iter(&self) -> OnesIter<'_, Self, N>

Returns an iterator over the indices of set bits.

pub fn and(&mut self, other: &Self)

Performs a bitwise AND with another BitMap.

Panics

Panics if the lengths don’t match.

pub fn or(&mut self, other: &Self)

Performs a bitwise OR with another BitMap.

Panics

Panics if the lengths don’t match.

pub fn xor(&mut self, other: &Self)

Performs a bitwise XOR with another BitMap.

Panics

Panics if the lengths don’t match.

pub fn is_unset(&self, range: Range<u64>) -> bool

Check if all the bits in a given range are 0.

Returns true if every index in the range is unset (i.e. Self::get returns false). Returns true if the range is empty.

Panics

Panics if range.end exceeds the length of the bitmap.

Examples

use commonware_utils::bitmap::BitMap;

let mut bitmap = BitMap::<8>::zeroes(128);
assert!(bitmap.is_unset(0..128));

bitmap.set(64, true);
assert!(bitmap.is_unset(0..64));
assert!(!bitmap.is_unset(0..65));

Trait Implementations

impl<const N: usize> BitAnd for &BitMap<N>

type Output = BitMap<N>

The resulting type after applying the & operator.

fn bitand(self, rhs: Self) -> Self::Output

Performs the & operation.

impl<const N: usize> BitOr for &BitMap<N>

type Output = BitMap<N>

The resulting type after applying the | operator.

fn bitor(self, rhs: Self) -> Self::Output

Performs the | operation.

impl<const N: usize> BitXor for &BitMap<N>

type Output = BitMap<N>

The resulting type after applying the ^ operator.

fn bitxor(self, rhs: Self) -> Self::Output

Performs the ^ operation.

impl<const N: usize> Clone for BitMap<N>

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

Returns a duplicate of the value.

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

Performs copy-assignment from source.

impl<const N: usize> Debug for BitMap<N>

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

Formats the value using the given formatter.

impl<const N: usize> Default for BitMap<N>

fn default() -> Self

Returns the “default value” for a type.

impl<const N: usize> EncodeSize for BitMap<N>

fn encode_size(&self) -> usize

Returns the encoded size of this value (in bytes).

fn encode_inline_size(&self) -> usize

Returns the encoded size excluding bytes passed to BufsMut::push during Write::write_bufs. Used to size the working buffer for inline writes. Override alongside Write::write_bufs for types where large Bytes fields go via push; failing to do so will over-allocate.

impl<const N: usize> From<BitMap<N>> for Vec<bool>

fn from(bv: BitMap<N>) -> Self

Converts to this type from the input type.

impl<T: AsRef<[bool]>, const N: usize> From<T> for BitMap<N>

fn from(t: T) -> Self

Converts to this type from the input type.

impl<const N: usize> Hash for BitMap<N>

fn hash<__H: Hasher>(&self, state: &mut __H)

Feeds this value into the given Hasher.

fn hash_slice<H>(data: &[Self], state: &mut H)

where H: Hasher, Self: Sized,

Feeds a slice of this type into the given Hasher.

impl<const N: usize> Index<u64> for BitMap<N>

fn index(&self, bit: u64) -> &Self::Output

Allows accessing bits using the [] operator.

Panics if out of bounds.

type Output = bool

The returned type after indexing.

impl<const N: usize> PartialEq for BitMap<N>

fn eq(&self, other: &BitMap<N>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<const N: usize> Read for BitMap<N>

type Cfg = u64

The Cfg type parameter allows passing configuration during the read process. This is crucial for safely decoding untrusted data, for example, by providing size limits for collections or strings.

fn read_cfg(buf: &mut impl Buf, max_len: &Self::Cfg) -> Result<Self, CodecError>

Reads a value from the buffer using the provided configuration cfg.

impl<const N: usize> Readable<N> for BitMap<N>

fn complete_chunks(&self) -> usize

Return the number of complete (fully filled) chunks.

fn get_chunk(&self, chunk: usize) -> [u8; N]

Return the chunk data at the given absolute chunk index.

fn last_chunk(&self) -> ([u8; N], u64)

Return the last chunk and its size in bits.

fn pruned_chunks(&self) -> usize

Return the number of pruned chunks.

fn len(&self) -> u64

Return the total number of bits.

fn is_empty(&self) -> bool

Returns true if the bitmap is empty.

fn pruned_bits(&self) -> u64

Return the number of pruned bits (i.e. pruned chunks * bits per chunk).

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

Return the value of a single bit.

fn ones_iter_from(&self, pos: u64) -> OnesIter<'_, Self, N>

where Self: Sized,

Returns an iterator over the indices of set bits starting from pos.

impl<const N: usize> Write for BitMap<N>

fn write(&self, buf: &mut impl BufMut)

Writes the binary representation of self to the provided buffer buf.

fn write_bufs(&self, buf: &mut impl BufsMut)

Writes to a BufsMut, allowing existing Bytes chunks to be appended via BufsMut::push instead of written inline. Must encode to the same format as Write::write. Defaults to Write::write.

impl<const N: usize> Eq for BitMap<N>

impl<const N: usize> StructuralPartialEq for BitMap<N>