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 EMPTY_CHUNK: [u8; N]

A chunk of all 0s.

pub const FULL_CHUNK: [u8; N]

A chunk of all 1s.

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 max_encode_size(bits: u64) -> usize

Returns the largest encoded size of a bitmap of at most bits bits.

Panics

Panics if the number of chunks does not fit in a usize.

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 extend_from_bitmap<const M: usize>(&mut self, other: &BitMap<M>)

Append every bit of other (of any chunk size), in order.

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) -> Self

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 fixed working buffer for inline writes, so it must not be less than the bytes written inline. Override alongside Write::write_bufs for types where large byte fields go via push, or the working buffer will over-allocate.

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

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: &Self) -> bool

Equality operator ==.

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

Inequality operator !=.

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

type Cfg = RangeCfg<u64>

Accepted range for the decoded length in bits.

fn read_cfg(buf: &mut impl Buf, range: &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.

fn ones_iter_range(&self, range: Range<u64>) -> OnesIter<'_, Self, N>

where Self: Sized,

Returns an iterator over the indices of set bits in range.

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

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 byte chunks to be appended via BufsMut::push instead of written inline. Must encode to the same format as Write::write. Defaults to Write::write.