Struct SmallBitMap

Source

pub struct SmallBitMap<const BLOCKS_ON_STACK: usize> { /* private fields */ }

Expand description

A bitmap that uses SmallVec for efficient storage with configurable inline capacity.

This bitmap type combines the benefits of stack allocation for small bitmaps with the ability to grow to heap allocation when needed. It’s ideal for cases where most bitmaps are small but occasionally need to grow larger.

The BLOCKS_ON_STACK parameter determines how many usize blocks are stored inline on the stack before spilling to heap allocation.

§Performance

Small bitmaps (≤ BLOCKS_ON_STACK * usize::BITS bits): No heap allocation, stack-only storage
Large bitmaps: Automatically grows to heap when needed
Uses the same high-performance range operations as other bitmap types

§Examples

use ranged_bitmap::SmallBitMap;

// Create a bitmap with 2 inline blocks (128 bits on 64-bit systems)
let mut bitmap = SmallBitMap::<2>::new();

// Set individual bits
bitmap.set(10);
bitmap.set(20);

// Set ranges - automatically grows if needed
bitmap.set_range(100, 50);

// Check bits
assert!(bitmap.get(10));
assert!(bitmap.get(125));
assert!(!bitmap.get(200));

// Count bits
assert_eq!(bitmap.count_ones(), 52);

Implementations§

Source §

impl<const BLOCKS_ON_STACK: usize> SmallBitMap<BLOCKS_ON_STACK>

Source

pub const fn new() -> Self

Creates a new empty bitmap.

The bitmap starts empty and will grow as needed when bits are set. For small bitmaps, this avoids heap allocation entirely.

§Examples

use ranged_bitmap::SmallBitMap;

let bitmap = SmallBitMap::<4>::new();
assert_eq!(bitmap.count_ones(), 0);

Source

pub fn set(&mut self, bit: usize)

Sets a bit to 1.

Automatically grows the bitmap if the bit is beyond current capacity. For small bitmaps, this operation is completely stack-based.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set(42);

assert!(bitmap.get(42));

Source

pub fn clear(&mut self, bit: usize)

Clears a bit to 0.

If the bit is beyond current capacity, this operation does nothing.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set(42);
bitmap.clear(42);

assert!(!bitmap.get(42));

Source

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

Gets the value of a bit.

Returns false for bits beyond current capacity.

§Examples

use ranged_bitmap::SmallBitMap;

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

assert!(!bitmap.get(100)); // Beyond capacity, returns false

bitmap.set(100);

assert!(bitmap.get(100));

Source

pub fn count_ones(&self) -> usize

Counts the number of set bits in the bitmap.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set(10);
bitmap.set(20);

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

Source

pub fn count_zeros(&self) -> usize

Counts the number of clear bits in the bitmap

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set_range(0, 10);

// count_zeros counts all zeros in the allocated blocks, not just the set range
assert_eq!(bitmap.count_zeros(), bitmap.capacity() - 10);

Source

pub fn iter_range( &self, start: usize, len: usize, ) -> impl Iterator<Item = (usize, bool)> + '_

Iterates over a range of bits, returning (position, value) pairs.

For bits beyond current capacity, the value is always false.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set(5);
bitmap.set(7);

let bits: Vec<_> = bitmap.iter_range(4, 4).collect();

assert_eq!(bits, vec![(4, false), (5, true), (6, false), (7, true)]);

Source §

impl<const BLOCKS_ON_STACK: usize> SmallBitMap<BLOCKS_ON_STACK>

Source

pub fn set_range(&mut self, start: usize, len: usize)

Sets all bits in a range to 1.

Automatically grows the bitmap if the range extends beyond current capacity. For small ranges, this avoids heap allocation.

§Examples

use ranged_bitmap::SmallBitMap;

let mut bitmap = SmallBitMap::<4>::new();
bitmap.set_range(100, 50); // Automatically grows

for i in 100..150 {
    assert!(bitmap.get(i));
}

Source

pub fn clear_range(&mut self, start: usize, len: usize)

Clears all bits in a range to 0.

For bits beyond current capacity, this operation does nothing.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set_range(0, 100);
bitmap.clear_range(50, 25);

// Bits 50-74 should be clear, others set
assert!(!bitmap.get(60));
assert!(bitmap.get(40));
assert!(bitmap.get(80));

Source

pub fn check_range_is_set(&self, start: usize, len: usize) -> bool

Checks if all bits in a range are set to 1.

For bits beyond current capacity, they are considered unset.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set_range(10, 5);

assert!(bitmap.check_range_is_set(10, 5));
assert!(!bitmap.check_range_is_set(10, 6)); // Bit 15 is not set

Source

pub fn check_range_is_unset(&self, start: usize, len: usize) -> bool

Checks if all bits in a range are clear to 0.

For bits beyond current capacity, they are considered clear.

§Examples

use ranged_bitmap::SmallBitMap;

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

bitmap.set_range(10, 5);

assert!(bitmap.check_range_is_unset(0, 10));
assert!(!bitmap.check_range_is_unset(10, 5));

Source

pub fn capacity(&self) -> usize

Returns the current capacity in bits.

This is the highest bit position that can be accessed without growing.

§Examples

use ranged_bitmap::SmallBitMap;

let mut bitmap = SmallBitMap::<4>::new();
assert_eq!(bitmap.capacity(), 0);

bitmap.set(100);
assert!(bitmap.capacity() >= 100);

Source