Struct SmolBitmap

Source

pub struct SmolBitmap { /* private fields */ }

Expand description

A compact bitmap that stores bits either inline or on the heap.

§Overview

SmolBitmap provides efficient storage for bit flags with automatic promotion from inline storage to heap allocation when needed. It’s designed for scenarios where you frequently need small bitmaps but occasionally require larger ones.

§Storage Strategy

Inline: Up to SmolBitmap::inline_capacity() bits stored directly in the struct
Heap: Automatically switches to heap allocation for larger bitmaps
The highest bit of the last word indicates storage mode (0 = inline, 1 = heap)

§Capacity Model

Unlike typical collections, SmolBitmap unifies length and capacity. All bits up to the capacity are accessible, with unset bits returning false.

§Internal Representation

The array field has dual purpose:

Inline mode: Contains the actual bit data
External mode: Contains [pointer, -length] where length is negative to set MSB

§Examples

use smol_bitmap::SmolBitmap;
let mut bitmap = SmolBitmap::new();

// Set some bits
bitmap.insert(10);
bitmap.insert(100);

// Check bits
assert!(bitmap.get(10));
assert!(bitmap.get(100));
assert!(!bitmap.get(50)); // Unset bits are false

// Force heap allocation
bitmap.insert(200);
assert!(bitmap.is_spilled()); // Now using heap storage

Implementations§

Source §

impl SmolBitmap

Source

pub const fn new() -> Self

Creates a new empty bitmap with inline storage.

The bitmap starts with inline storage capacity (127 bits) and will automatically promote to heap storage if needed.

§Examples

let bitmap = SmolBitmap::new();
assert_eq!(bitmap.capacity(), SmolBitmap::inline_capacity());
assert!(!bitmap.is_spilled());

Source

pub const fn inline_capacity() -> usize

Returns the maximum number of bits that can be stored in inline storage.

This is 127 bits (2 × 64 - 1), as the highest bit is reserved for storage mode indication.

§Examples

assert_eq!(SmolBitmap::inline_capacity(), 127);

Source

pub fn retain<F>(&mut self, f: F)
where F: FnMut(usize) -> bool,

Retains only the elements specified by the predicate.

Removes all bits bit such that f(bit) returns false. This operation is performed in-place and efficiently processes bits word by word.

§Arguments

f - A predicate function that takes a bit index and returns true if the bit should be retained

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(1);
bitmap.insert(2);
bitmap.insert(5);
bitmap.insert(8);

// Retain only even indices
bitmap.retain(|bit| bit % 2 == 0);

assert!(!bitmap.get(1));
assert!(bitmap.get(2));
assert!(!bitmap.get(5));
assert!(bitmap.get(8));

Source

pub fn with_capacity(bits: usize) -> Self

Creates a new bitmap with at least the specified bit capacity.

If the capacity is within the inline limit (inline_capacity), the bitmap will use inline storage. Otherwise, it will allocate heap storage.

§Examples

// Small capacity uses inline storage
let bitmap = SmolBitmap::with_capacity(100);
assert!(!bitmap.is_spilled());

// Large capacity uses heap storage
let bitmap = SmolBitmap::with_capacity(1000);
assert!(bitmap.is_spilled());

Source

pub const fn is_spilled(&self) -> bool

Returns true if the bitmap is using heap storage.

§Examples

let mut bitmap = SmolBitmap::new();
assert!(!bitmap.is_spilled());

bitmap.insert(200); // Beyond inline capacity
assert!(bitmap.is_spilled());

Source

pub const fn as_ptr(&self) -> *const u64

Get a const pointer to the storage

Source

pub const fn as_mut_ptr(&mut self) -> *mut u64

Get a mutable pointer to the storage

Source

pub const fn as_slice(&self) -> &[u64]

Get the storage as a slice

Source

pub const unsafe fn as_mut_slice(&mut self) -> &mut [u64]

Get the storage as a mutable slice

§Safety

The caller must ensure that:

If the storage is inline, the MSB of the last word must not be set
Modifications must maintain the storage invariants
The slice must not be extended beyond its capacity

Source

pub const fn capacity(&self) -> usize

Returns the total number of bits that can be stored without reallocation.

For inline storage, this is always inline_capacity. For heap storage, this is the number of allocated bits.

§Examples

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.capacity(), SmolBitmap::inline_capacity());

Source

pub fn reserve(&mut self, additional: usize)

Reserves capacity for at least additional more bits.

This method ensures that the bitmap can store at least additional more bits beyond its current capacity. It may reserve more space to avoid frequent reallocations.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.reserve(300);
assert!(bitmap.capacity() >= 300);
assert!(bitmap.is_spilled());

Source

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

Returns the value of the bit at the given index.

Returns false if the index is out of bounds.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(42);

assert!(bitmap.get(42));
assert!(!bitmap.get(43));
assert!(!bitmap.get(1000)); // Out of bounds returns false

Source

pub fn replace(&mut self, i: usize, v: bool) -> bool

Sets the bit at the given index to the specified value and returns the previous value.

If the index is beyond the current capacity and the value is true, the bitmap will be resized to accommodate it. If the value is false and the index is out of bounds, no resize occurs and false is returned.

§Examples

let mut bitmap = SmolBitmap::new();

assert_eq!(bitmap.replace(10, true), false);
assert_eq!(bitmap.replace(10, false), true);
assert_eq!(bitmap.replace(10, true), false);

Source

pub fn set(&mut self, i: usize, v: bool)

Sets the bit at the given index to the specified value.

If the index is beyond the current capacity and the value is true, the bitmap will be resized to accommodate it.

§Performance

O(1) for bits within current capacity
O(n) if reallocation is needed (when index > capacity)

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(10);
bitmap.insert(20);

assert!(bitmap.get(10));
assert!(bitmap.get(20));

Source

pub fn insert(&mut self, i: usize) -> bool

Inserts a bit at the given index, setting it to true.

Returns true if the bit was previously unset (insertion occurred), or false if it was already set.

§Examples

let mut bitmap = SmolBitmap::new();

assert!(bitmap.insert(10)); // First insertion
assert!(!bitmap.insert(10)); // Already set

Source

pub fn remove(&mut self, i: usize) -> bool

Removes a bit at the given index, setting it to false.

Returns true if the bit was previously set (removal occurred), or false if it was already unset.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(10);

assert!(bitmap.remove(10)); // Bit was set
assert!(!bitmap.remove(10)); // Already unset

Source

pub fn clear(&mut self)

Clears all bits in the bitmap.

This is equivalent to creating a new empty bitmap but it keeps the existing allocation if possible.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(100);
bitmap.insert(200);

bitmap.clear();
assert!(!bitmap.get(100));
assert!(bitmap.is_spilled());

Source

pub fn shrink_to_fit(&mut self)

Shrinks the capacity of the bitmap as much as possible.

This will remove trailing zero words and potentially move the data back to inline storage if it fits.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(300);
bitmap.remove(300); // Clear the bit

bitmap.shrink_to_fit();
// May move back to inline storage if all set bits fit

Source

pub const fn as_slice_rtrim(&self) -> &[u64]

Returns a trimmed slice of the bitmap, removing any trailing zero words.

This method provides a view of the bitmap’s underlying storage without trailing zeros, which can be useful for operations that require a compact representation of the set bits.

§Returns

A slice of type &[u64] representing the bitmap’s storage without trailing zeros.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(64);

let trimmed_slice = bitmap.as_slice_rtrim();
assert_eq!(trimmed_slice.len(), 2); // Only two words are needed

Source

pub fn eq_rtrim(&self, b: &[u64]) -> bool

Compares two slices for equivalency, ignoring trailing zero words.

This function checks if two slices are equivalent by comparing their elements, ignoring any trailing zero words. This is useful for comparing bitmaps where trailing zeros do not affect the logical equivalence of the data.

§Arguments

a - The first slice to compare.
b - The second slice to compare.

§Returns

true if the slices are equivalent when trailing zeros are ignored, false otherwise.

§Examples

use smol_bitmap::SmolBitmap;

let a = SmolBitmap::from(&[1u64, 2, 0, 0]);
let b = &[1u64, 2];
assert!(a.eq_rtrim(b));

let c = &[1u64, 2, 3];
assert!(!a.eq_rtrim(c));

Source

pub fn cmp_rtrim(&self, b: &[u64]) -> Ordering

Compares two slices for ordering, ignoring trailing zero words.

This function compares two slices by their elements, ignoring any trailing zero words. This is useful for comparing bitmaps where trailing zeros do not affect the logical ordering of the data.

§Arguments

a - The first slice to compare.
b - The second slice to compare.

§Returns

An Ordering value that indicates whether a is less than, equal to, or greater than b when trailing zeros are ignored.

§Examples

use smol_bitmap::SmolBitmap;

let a = SmolBitmap::from(&[1u64, 2, 0, 0]);
let b = &[1u64, 2];
assert_eq!(a.cmp_rtrim(b), core::cmp::Ordering::Equal);

let c = &[1u64, 2, 3];
assert_eq!(a.cmp_rtrim(c), core::cmp::Ordering::Less);

Source

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

Removes a prefix of consecutive bits with the specified value.

Efficiently removes all consecutive bits of the given value from the beginning of the bitmap by shifting the remaining bits left. This is useful for maintaining compact bitmap representations.

§Algorithm

Skip whole words that match the pattern (all 0s or all 1s)
Find consecutive bits in the first non-matching word
Shift all remaining bits left by the total skip amount

§Arguments

bit - The bit value to remove from the prefix (true for 1s, false for 0s)

§Returns

The number of bits removed from the prefix.

§Examples

let mut bitmap = SmolBitmap::new();
// Set bits: 111100101
bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(2);
bitmap.insert(3);
bitmap.insert(5);
bitmap.insert(7);

// Remove prefix of 1s
let removed = bitmap.remove_prefix(true);
assert_eq!(removed, 4); // Removed four leading 1s
// Bitmap is now: 0101 (shifted left)

Source

pub const fn iter(&self) -> Iter<'_>

Returns an iterator over the set bits.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(10);
bitmap.insert(20);

let mut iter = bitmap.iter();
assert_eq!(iter.next(), Some(10));
assert_eq!(iter.next(), Some(20));
assert_eq!(iter.next(), None);

Source

pub fn select<I: IntoIterator>(&self, iter: I) -> SelectIter<'_, I::IntoIter> ⓘ

Creates an iterator that selects elements from the provided iterator based on set bits.

This method returns a SelectIter that filters the input iterator, yielding only elements at positions corresponding to set bits in the bitmap. This is useful for creating a subset of a collection based on a bitmap mask.

§Arguments

iter - An iterator whose elements will be selected based on set bits

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(2);
bitmap.insert(4);

let items = vec!["a", "b", "c", "d", "e"];
let selected: Vec<_> = bitmap.select(items.iter().copied()).collect();
assert_eq!(selected, vec!["a", "c", "e"]);

Source

pub fn len(&self) -> usize

Returns the number of set bits in the bitmap.

Time complexity: O(n) where n is the number of words.

§Examples

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.len(), 0);

bitmap.insert(10);
bitmap.insert(20);
assert_eq!(bitmap.len(), 2);

Source

pub fn rank(&self, i: usize) -> usize

Returns the number of set bits below the given index.

Counts all set bits at positions less than idx. This is useful for determining the position of an element in a compressed representation.

Time complexity: O(w) where w is the number of words up to the target index.

§Arguments

idx - The index to count below (exclusive upper bound)

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);
bitmap.insert(15);
bitmap.insert(20);

assert_eq!(bitmap.rank(0), 0); // No bits below index 0
assert_eq!(bitmap.rank(6), 1); // Bit at index 5
assert_eq!(bitmap.rank(12), 2); // Bits at indices 5, 10
assert_eq!(bitmap.rank(25), 4); // All bits below index 25

Source

pub fn is_empty(&self) -> bool

Returns true if the bitmap contains no set bits.

Time complexity: O(n) where n is the number of words.

§Examples

let mut bitmap = SmolBitmap::new();
assert!(bitmap.is_empty());

bitmap.insert(10);
assert!(!bitmap.is_empty());

Source

pub fn first(&self) -> Option<usize>

Returns the minimum (first) set bit in the bitmap, or None if the bitmap is empty.

Time complexity: O(n) where n is the number of words.

§Examples

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.first(), None);

bitmap.insert(10);
bitmap.insert(5);
bitmap.insert(20);
assert_eq!(bitmap.first(), Some(5));

Source

pub fn last(&self) -> Option<usize>

Returns the maximum (last) set bit in the bitmap, or None if the bitmap is empty.

Returns None if the bitmap is empty.

Time complexity: O(n) where n is the number of words.

§Examples

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.last(), None);

bitmap.insert(10);
bitmap.insert(5);
bitmap.insert(20);
assert_eq!(bitmap.last(), Some(20));

Source

pub fn count_ones(&self) -> usize

Counts the number of set bits in the bitmap.

This method efficiently counts all set bits using the built-in count_ones method on each word.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);
bitmap.insert(15);
assert_eq!(bitmap.count_ones(), 3);

Source

pub fn count_zeros(&self) -> usize

Counts the number of unset bits up to the capacity of the bitmap.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);
let zeros = bitmap.count_zeros();
assert_eq!(zeros, bitmap.capacity() - 2);

Source

pub fn complement(&mut self, i: usize) -> bool

Complements the bit at the specified index.

If the bit was set, it becomes unset. If it was unset, it becomes set.

§Examples

let mut bitmap = SmolBitmap::new();
assert!(!bitmap.get(5));

bitmap.complement(5);
assert!(bitmap.get(5));

bitmap.complement(5);
assert!(!bitmap.get(5));

Source

pub fn next_set_bit(&self, beg: usize) -> Option<usize>

Returns the index of the next set bit at or after the given index.

If no set bit is found at or after the given index, returns None.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);
bitmap.insert(15);

assert_eq!(bitmap.next_set_bit(0), Some(5));
assert_eq!(bitmap.next_set_bit(6), Some(10));
assert_eq!(bitmap.next_set_bit(11), Some(15));
assert_eq!(bitmap.next_set_bit(16), None);

Source

pub fn prev_set_bit(&self, from: usize) -> Option<usize>

Returns the index of the previous set bit at or before the given index.

If no set bit is found at or before the given index, returns None.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);
bitmap.insert(15);

assert_eq!(bitmap.prev_set_bit(20), Some(15));
assert_eq!(bitmap.prev_set_bit(14), Some(10));
assert_eq!(bitmap.prev_set_bit(9), Some(5));
assert_eq!(bitmap.prev_set_bit(4), None);

Source

pub fn shl(&self, n: usize) -> Self

Shifts all bits left by n positions.

Bits that would be shifted beyond the capacity are lost.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(2);

let shifted = bitmap.shl(2);
assert!(!shifted.get(0));
assert!(!shifted.get(1));
assert!(shifted.get(2));
assert!(shifted.get(3));
assert!(shifted.get(4));

Source

pub fn shr(&self, n: usize) -> Self

Shifts all bits right by n positions.

Bits that would be shifted below 0 are lost.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(2);
bitmap.insert(3);
bitmap.insert(4);

let shifted = bitmap.shr(2);
assert!(shifted.get(0));
assert!(shifted.get(1));
assert!(shifted.get(2));
assert!(!shifted.get(3));
assert!(!shifted.get(4));

Source

pub fn leading_zeros(&self) -> Option<usize>

Counts the number of leading zero bits (from bit 0 upward).

Returns None if the bitmap is empty.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.leading_zeros(), None);

bitmap.insert(3);
assert_eq!(bitmap.leading_zeros(), Some(3));

bitmap.insert(0);
assert_eq!(bitmap.leading_zeros(), Some(0));

Source

pub fn trailing_zeros(&self) -> Option<usize>

Counts the number of trailing zero bits (from the highest set bit downward).

Returns None if the bitmap is empty.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(3);
bitmap.insert(5);
bitmap.insert(10);

// 4 trailing zeros from bit 10 down to bit 6 (bit 5 is set)
assert_eq!(bitmap.trailing_zeros(), Some(4));

Source

pub fn leading_ones(&self) -> usize

Counts the number of leading one bits (consecutive ones from bit 0).

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(2);
bitmap.insert(4);

assert_eq!(bitmap.leading_ones(), 3);

Source

pub fn trailing_ones(&self) -> usize

Counts the number of trailing one bits (consecutive ones from the highest set bit).

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(2);
bitmap.insert(4);
bitmap.insert(5);
bitmap.insert(6);

assert_eq!(bitmap.trailing_ones(), 3);

Source

pub fn find_first_zero(&self) -> Option<usize>

Finds the first unset bit in the bitmap.

Returns None if all bits up to capacity are set.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
assert_eq!(bitmap.find_first_zero(), Some(0));

bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(3);
assert_eq!(bitmap.find_first_zero(), Some(2));

Source

pub fn find_last_zero(&self) -> Option<usize>

Finds the last unset bit in the bitmap.

Returns None if all bits are set or the bitmap is empty.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(2);
bitmap.insert(5);

// The last unset bit before bit 5
assert_eq!(bitmap.find_last_zero(), Some(4));

Source

pub fn find_next_zero(&self, beg: usize) -> Option<usize>

Finds the next unset bit at or after the given position.

Returns None if no unset bit is found within capacity.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(3);

assert_eq!(bitmap.find_next_zero(0), Some(2));
assert_eq!(bitmap.find_next_zero(2), Some(2));
assert_eq!(bitmap.find_next_zero(3), Some(4));

Source

pub fn find_prev_zero(&self, from: usize) -> Option<usize>

Finds the previous unset bit at or before the given position.

Returns None if no unset bit is found.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(1);
bitmap.insert(3);
bitmap.insert(5);

assert_eq!(bitmap.find_prev_zero(5), Some(4));
assert_eq!(bitmap.find_prev_zero(3), Some(2));
assert_eq!(bitmap.find_prev_zero(1), Some(0));

Source

pub fn count_ones_range(&self, beg: usize, end: usize) -> usize

Counts the number of set bits in the range [beg, end).

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(1);
bitmap.insert(3);
bitmap.insert(5);
bitmap.insert(7);

assert_eq!(bitmap.count_ones_range(0, 4), 2); // bits 1 and 3
assert_eq!(bitmap.count_ones_range(2, 8), 3); // bits 3, 5, and 7

Source

pub fn count_zeros_range(&self, beg: usize, end: usize) -> usize

Counts the number of unset bits in the range [beg, end).

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(1);
bitmap.insert(3);

assert_eq!(bitmap.count_zeros_range(0, 4), 2); // bits 0 and 2
assert_eq!(bitmap.count_zeros_range(0, 8), 6); // 8 - 2 set bits

Source

pub fn set_all(&mut self)

Sets all bits up to the current highest set bit to true.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(5);

bitmap.set_all();
assert!(bitmap.get(0));
assert!(bitmap.get(1));
assert!(bitmap.get(2));
assert!(bitmap.get(3));
assert!(bitmap.get(4));
assert!(bitmap.get(5));

Source

pub fn clear_range(&mut self, beg: usize, end: usize)

Clears bits in the range [beg, end).

§Panics

Panics if beg > end.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
for i in 0..10 {
    bitmap.insert(i);
}

bitmap.clear_range(3, 7);
assert!(bitmap.get(2));
assert!(!bitmap.get(3));
assert!(!bitmap.get(6));
assert!(bitmap.get(7));

Source

pub fn complement_range(&mut self, beg: usize, end: usize)

Complements all bits in the range [beg, end).

§Panics

Panics if beg > end.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(2);
bitmap.insert(4);

bitmap.complement_range(1, 6);

assert!(bitmap.get(1));
assert!(!bitmap.get(2));
assert!(bitmap.get(3));
assert!(!bitmap.get(4));
assert!(bitmap.get(5));

Source

pub fn set_range(&mut self, beg: usize, end: usize)

Sets all bits bits in the range [beg, end).

§Panics

Panics if beg > end.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.set_range(2, 6);

assert!(!bitmap.get(1));
assert!(bitmap.get(2));
assert!(bitmap.get(4));
assert!(bitmap.get(5));
assert!(!bitmap.get(6));

Source

pub fn set_range_value(&mut self, beg: usize, end: usize, value: bool)

Sets all bits in the range [beg, end) to the specified value.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();

bitmap.set_range_value(5, 10, true);
assert!(!bitmap.get(4));
assert!(bitmap.get(5));
assert!(bitmap.get(9));
assert!(!bitmap.get(10));

bitmap.set_range_value(7, 9, false);
assert!(bitmap.get(6));
assert!(!bitmap.get(7));
assert!(!bitmap.get(8));
assert!(bitmap.get(9));

Source

pub fn fill(&mut self, value: bool)

Sets all bits up to capacity to the specified value.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(10); // This determines a capacity

bitmap.fill(true);
// All bits from 0 to 10 are now true
for i in 0..=10 {
    assert!(bitmap.get(i));
}

Source

pub fn get_range(&self, beg: usize, end: usize) -> u64

Extracts bits in the range [beg, end) as a u64 value.

Returns up to 64 bits. If the range is larger than 64 bits, only the first 64 bits are returned.

§Panics

Panics if beg > end.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(2);
bitmap.insert(3);

// Extract bits 0-4: 1101 in binary = 13 in decimal
assert_eq!(bitmap.get_range(0, 4), 0b1101);

Source

pub fn extract_word(&self, word_idx: usize) -> u64

Extracts a 64-bit word at the given word index.

This method returns the word at the specified index. For inline storage, if reading the last word (index 1), bit 127 (the MSB) is cleared to hide the storage mode indicator.

§Arguments

word_idx - The word index to extract (0-based)

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(63);
bitmap.insert(64);
bitmap.insert(126);

assert_eq!(bitmap.extract_word(0), (1u64 << 63) | 1);
assert_eq!(bitmap.extract_word(1), (1u64 << 62) | 1); // bit 127 is masked

Source

pub fn put_word(&mut self, word_idx: usize, word: u64)

Inserts a 64-bit word at the given word index.

This method sets the word at the specified index. If the bitmap is using inline storage and bit 127 would be set (MSB of the last word), the bitmap is automatically promoted to heap storage.

§Arguments

word_idx - The word index to write to (0-based)
word - The 64-bit word to insert

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();

// Set word 0
bitmap.put_word(0, 0xFFFF_FFFF_FFFF_FFFF);
assert!(!bitmap.is_spilled());

// Setting MSB of word 1 causes promotion to heap
bitmap.put_word(1, 0x8000_0000_0000_0000);
assert!(bitmap.is_spilled());

Source

pub fn resize(&mut self, new_bits: usize)

Resizes the bitmap to contain exactly new_bits bits.

If new_bits is greater than the current capacity, the bitmap is extended with zeros. If new_bits is less than the current capacity, the bitmap is truncated.

§Arguments

new_bits - The new size in bits

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(50);
bitmap.insert(100);

// Resize to 75 bits - bit 100 will be removed
bitmap.resize(75);
assert!(bitmap.get(50));
assert!(!bitmap.get(100));

// Resize to 200 bits - expands with zeros
bitmap.resize(200);
assert!(bitmap.is_spilled()); // Beyond inline capacity

Source

pub fn truncate(&mut self, max_bits: usize)

Truncates the bitmap to contain at most max_bits bits.

If max_bits is greater than or equal to the current highest set bit, this has no effect. Otherwise, all bits at positions >= max_bits are cleared.

This method may also shrink the storage if the truncation allows the bitmap to fit back into inline storage.

§Arguments

max_bits - The maximum number of bits to keep

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(50);
bitmap.insert(100);
bitmap.insert(150);

// Truncate to 120 bits - bit 150 will be removed
bitmap.truncate(120);
assert!(bitmap.get(50));
assert!(bitmap.get(100));
assert!(!bitmap.get(150));

// Further truncation
bitmap.truncate(60);
assert!(bitmap.get(50));
assert!(!bitmap.get(100));

Source

pub fn bitslice(&self, beg: usize, end: usize) -> Self

Extracts a range of bits as a new bitmap.

The bits in the range [start, end) are copied to a new bitmap, with bit start becoming bit 0 in the new bitmap.

§Panics

This function will not panic under normal circumstances. The unwrap call in the implementation is safe because the function returns early when the slice would be empty, ensuring there’s always at least one element when we access the last element.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(2);
bitmap.insert(3);
bitmap.insert(5);

let sub = bitmap.bitslice(2, 6);
assert!(sub.get(0)); // bit 2 -> 0
assert!(sub.get(1)); // bit 3 -> 1
assert!(!sub.get(2)); // bit 4 -> 2
assert!(sub.get(3)); // bit 5 -> 3

Source

pub fn skip(&self, beg: usize) -> Self

Extracts bits from the given position to the end as a new bitmap.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(2);
bitmap.insert(3);
bitmap.insert(5);

let sub = bitmap.skip(2);
assert!(sub.get(0)); // bit 2 -> 0
assert!(sub.get(1)); // bit 3 -> 1
assert!(sub.get(3)); // bit 5 -> 3

Source

pub fn take(&self, end: usize) -> Self

Extracts bits from the beginning up to (but not including) the given position.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(1);
bitmap.insert(3);
bitmap.insert(5);

let sub = bitmap.take(4);
assert!(sub.get(1));
assert!(sub.get(3));
assert!(!sub.get(5)); // Not included

Source §

impl SmolBitmap

Source

pub const fn to_ne_bytes(&self) -> &[u8] ⓘ

Converts the bitmap to a byte slice in native-endian order.

This method provides a view of the bitmap’s internal representation as a slice of bytes. The byte order is native-endian, meaning it matches the endianness of the host system.

§Safety

The returned slice is valid as long as the bitmap is not modified. Modifying the bitmap while holding a reference to this slice may lead to undefined behavior.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
let bytes = bitmap.to_ne_bytes();
assert_eq!(bytes[0], 0b00000001);

Source

pub fn from_ne_bytes(bytes: &[u8]) -> (Self, &[u8])

Constructs a bitmap from a byte slice in native-endian order.

This method reads bytes in native-endian order and constructs a SmolBitmap from them. Any remaining bytes that do not form a complete word are returned as a separate slice.

§Safety

The input byte slice must be properly aligned and sized to match the internal representation of the bitmap. Misalignment or incorrect sizing may lead to undefined behavior.

Source §

impl SmolBitmap

Source

pub const fn to_le_bytes(&self) -> Cow<'_, [u8]>

Converts the bitmap to little-endian bytes.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(7);
bitmap.insert(8);

let bytes = bitmap.to_le_bytes();
assert_eq!(bytes[0], 0b10000001); // bits 0 and 7
assert_eq!(bytes[1], 0b00000001); // bit 8

Source

pub fn from_le_bytes(bytes: &[u8]) -> (Self, &[u8])

Constructs a bitmap from little-endian bytes.

§Examples

use smol_bitmap::SmolBitmap;

let bytes = [0b10000001, 0b00000001, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00];
let (bitmap, _rest) = SmolBitmap::from_le_bytes(&bytes);

assert!(bitmap.get(0)); // bit 0 from byte 0
assert!(bitmap.get(7)); // bit 7 from byte 0
assert!(bitmap.get(8)); // bit 0 from byte 1

Source

pub fn to_be_bytes(&self) -> Cow<'_, [u8]>

Converts the bitmap to big-endian bytes.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(7);

let bytes = bitmap.to_be_bytes();
// Big-endian representation

Source

pub fn from_be_bytes(bytes: &[u8]) -> (Self, &[u8])

Constructs a bitmap from big-endian bytes.

§Examples

use smol_bitmap::SmolBitmap;

let bytes = vec![0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x01, 0x00]; // Big-endian representation
let (bitmap, _rest) = SmolBitmap::from_be_bytes(&bytes);

assert!(bitmap.get(8)); // The high bit of the first byte

Source §

impl SmolBitmap

Source

pub fn contains(&self, index: usize) -> bool

Checks if the bit at the specified index is set.

This is an alias for the SmolBitmap::get method.

§Arguments

index - The index of the bit to check.

§Returns

Returns true if the bit at the specified index is set, otherwise false.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(10);
assert!(bitmap.contains(10));
assert!(!bitmap.contains(5));

Source

pub fn pop_first(&mut self) -> Option<usize>

Removes and returns the index of the first set bit in the bitmap, or None if the bitmap is empty.

This operation modifies the bitmap by clearing the first set bit.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);

assert_eq!(bitmap.pop_first(), Some(5));
assert_eq!(bitmap.pop_first(), Some(10));
assert_eq!(bitmap.pop_first(), None);

Source

pub fn pop_last(&mut self) -> Option<usize>

Removes and returns the index of the last set bit in the bitmap, or None if the bitmap is empty.

This operation modifies the bitmap by clearing the last set bit.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(5);
bitmap.insert(10);

assert_eq!(bitmap.pop_last(), Some(10));
assert_eq!(bitmap.pop_last(), Some(5));
assert_eq!(bitmap.pop_last(), None);

Source

pub fn cardinality(&self) -> usize

Returns the number of set bits in the bitmap.

This is an alias for the SmolBitmap::count_ones method.

§Examples

let mut bitmap = SmolBitmap::new();
bitmap.insert(10);
bitmap.insert(20);
assert_eq!(bitmap.cardinality(), 2);

Source

pub fn add(&mut self, index: usize) -> bool

Inserts a bit at the given index, setting it to true.

Returns true if the bit was previously unset (insertion occurred), or false if it was already set.

This is an alias for the SmolBitmap::insert method.

§Examples

let mut bitmap = SmolBitmap::new();

assert!(bitmap.insert(10)); // First insertion
assert!(!bitmap.insert(10)); // Already set

Source

pub fn union_with(&mut self, other: impl AsRef<[u64]>)

Performs a bitwise OR operation with another bitmap.

This sets each bit in self to self[i] | other[i]. If other is larger, the bitmap is extended to accommodate all bits.

§Examples

let mut a = SmolBitmap::new();
let mut b = SmolBitmap::new();

a.insert(10);
b.insert(20);

a.union_with(&b);
assert!(a.get(10));
assert!(a.get(20));

Source

pub fn union(&self, other: impl AsRef<[u64]>) -> Self

Creates a new set that is the union of this set and another set.

The union contains elements present in either this set or the other set.

Time complexity: O(n) where n is the max number of bytes in either set.

Source

pub fn intersection_with(&mut self, other: impl AsRef<[u64]>)

Performs a bitwise AND operation with another bitmap.

This sets each bit in self to self[i] & other[i]. The result is truncated to the length of the shorter bitmap. Trailing zeros are removed.

§Examples

let mut a = SmolBitmap::new();
let mut b = SmolBitmap::new();

a.insert(10);
a.insert(20);
b.insert(10);

a.intersection_with(&b);
assert!(a.get(10));
assert!(!a.get(20));

Source

pub fn intersection(&self, other: impl AsRef<[u64]>) -> Self

Creates a new set that is the intersection of this set and another set.

The intersection contains only elements present in both sets.

Time complexity: O(n) where n is the min number of bytes in either set.

Source

pub fn difference(&self, other: impl AsRef<[u64]>) -> Self

Creates a new set that is the difference of this set and another set.

The difference contains elements present in this set but not in the other set.

Time complexity: O(n) where n is the number of bytes in self.

Source

pub fn difference_with(&mut self, other: impl AsRef<[u64]>)

Updates this set to be the difference of itself and another set.

Time complexity: O(n) where n is the min number of bytes in either set.

Source

pub fn symmetric_difference(&self, other: impl AsRef<[u64]>) -> Self

Creates a new set that is the symmetric difference of this set and another set.

The symmetric difference contains elements present in either this set or the other set, but not in both.

Time complexity: O(n) where n is the max number of words in either set.

Source

pub fn symmetric_difference_with(&mut self, other: impl AsRef<[u64]>)

Updates this set to be the symmetric difference of itself and another set.

Time complexity: O(n) where n is the max number of words in either set.

Source

pub fn is_subset(&self, other: impl AsRef<[u64]>) -> bool

Checks if this set is a subset of another set.

A set is a subset if all its elements are contained in the other set.

Time complexity: O(n) where n is the number of words in self.

Source

pub fn is_superset(&self, other: impl AsRef<[u64]>) -> bool

Checks if this set is a superset of another set.

A set is a superset if it contains all elements of the other set.

Time complexity: O(n) where n is the number of words in other.

Source

pub fn is_disjoint(&self, other: impl AsRef<[u64]>) -> bool

Checks if this set is disjoint from another set.

Two sets are disjoint if they have no elements in common.

Time complexity: O(n) where n is the min number of words in either set.

Source

pub fn all(&self) -> bool

Returns true if all bits up to the maximum set bit are set.

Returns true for an empty bitmap.

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
assert!(bitmap.all()); // Empty bitmap

bitmap.insert(0);
bitmap.insert(1);
bitmap.insert(2);
assert!(bitmap.all()); // All bits 0-2 are set

bitmap.insert(4);
assert!(!bitmap.all()); // Bit 3 is not set

Source

pub fn any(&self) -> bool

Returns true if any bit is set.

This is equivalent to !self.is_empty().

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
assert!(!bitmap.any());

bitmap.insert(42);
assert!(bitmap.any());

Source

pub fn none(&self) -> bool

Returns true if no bits are set.

This is equivalent to self.is_empty().

§Examples

use smol_bitmap::SmolBitmap;

let mut bitmap = SmolBitmap::new();
assert!(bitmap.none());

bitmap.insert(42);
assert!(!bitmap.none());

Trait Implementations§

Source §

impl Archive for SmolBitmap

Source §

type Archived = ArchivedVec<<u64 as Archive>::Archived>

The archived representation of this type. Read more

Source §

type Resolver = VecResolver

The resolver for this type. It must contain all the additional information from serializing needed to make the archived type from the normal type.

Source §

fn resolve(&self, resolver: Self::Resolver, out: Place<Self::Archived>)

Creates the archived version of this value at the given position and writes it to the given output. Read more

Source §

const COPY_OPTIMIZATION: CopyOptimization<Self> = _

An optimization flag that allows the bytes of this type to be copied directly to a writer instead of calling serialize. Read more

Source §

impl AsRef<[u64]> for SmolBitmap

Source §

fn as_ref(&self) -> &[u64]

Converts this type into a shared reference of the (usually inferred) input type.

Source §

impl Binary for SmolBitmap

Source §

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

Formats the bitmap as a binary string representation.

The binary representation shows bits from least significant (rightmost) to most significant (leftmost), with the 0b prefix. Trailing zeros are omitted for compact representation.

§Examples

use smol_bitmap::SmolBitmap;
let mut bitmap = SmolBitmap::new();
bitmap.insert(0);
bitmap.insert(2);
bitmap.insert(65);

// Shows compact binary representation
println!("{:#b}", bitmap); // 0b10000000000000000000000000000000000000000000000000000000000000000101

Source §

impl BitAnd for &SmolBitmap

Source §

type Output = SmolBitmap

The resulting type after applying the & operator.

Source §

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

Performs the & operation. Read more

Source §

impl BitAnd for SmolBitmap

Source §

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

Performs bitwise AND operation between two bitmaps.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);
a.insert(1);

let mut b = SmolBitmap::new();
b.insert(1);
b.insert(2);

let c = a & b;
assert!(c.get(1)); // Only bit 1 is set in both
assert!(!c.get(0));
assert!(!c.get(2));

Source §

type Output = SmolBitmap

The resulting type after applying the & operator.

Source §

impl BitAndAssign<&SmolBitmap> for SmolBitmap

Source §

fn bitand_assign(&mut self, rhs: &Self)

Performs the &= operation. Read more

Source §

impl BitAndAssign for SmolBitmap

Source §

fn bitand_assign(&mut self, rhs: Self)

Performs in-place bitwise AND operation.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);
a.insert(1);

let mut b = SmolBitmap::new();
b.insert(1);
b.insert(2);

a &= b;
assert!(a.get(1)); // Only bit 1 is set in both
assert!(!a.get(0));

Source §

impl BitOr for &SmolBitmap

Source §

type Output = SmolBitmap

The resulting type after applying the | operator.

Source §

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

Performs the | operation. Read more

Source §

impl BitOr for SmolBitmap

Source §

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

Performs bitwise OR operation between two bitmaps.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);
a.insert(1);

let mut b = SmolBitmap::new();
b.insert(1);
b.insert(2);

let c = a | b;
assert!(c.get(0));
assert!(c.get(1));
assert!(c.get(2));

Source §

type Output = SmolBitmap

The resulting type after applying the | operator.

Source §

impl BitOrAssign<&SmolBitmap> for SmolBitmap

Source §

fn bitor_assign(&mut self, rhs: &Self)

Performs the |= operation. Read more

Source §

impl BitOrAssign for SmolBitmap

Source §

fn bitor_assign(&mut self, rhs: Self)

Performs in-place bitwise OR operation.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);

let mut b = SmolBitmap::new();
b.insert(1);

a |= b;
assert!(a.get(0));
assert!(a.get(1));

Source §

impl BitXor for &SmolBitmap

Source §

type Output = SmolBitmap

The resulting type after applying the ^ operator.

Source §

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

Performs the ^ operation. Read more

Source §

impl BitXor for SmolBitmap

Source §

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

Performs bitwise XOR operation between two bitmaps.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);
a.insert(1);

let mut b = SmolBitmap::new();
b.insert(1);
b.insert(2);

let c = a ^ b;
assert!(c.get(0)); // Only in a
assert!(!c.get(1)); // In both, so not in XOR
assert!(c.get(2)); // Only in b

Source §

type Output = SmolBitmap

The resulting type after applying the ^ operator.

Source §

impl BitXorAssign<&SmolBitmap> for SmolBitmap

Source §

fn bitxor_assign(&mut self, rhs: &Self)

Performs the ^= operation. Read more

Source §

impl BitXorAssign for SmolBitmap

Source §

fn bitxor_assign(&mut self, rhs: Self)

Performs in-place bitwise XOR operation.

§Examples

use smol_bitmap::SmolBitmap;

let mut a = SmolBitmap::new();
a.insert(0);
a.insert(1);

let mut b = SmolBitmap::new();
b.insert(1);
b.insert(2);

a ^= b;
assert!(a.get(0)); // Only in original a
assert!(!a.get(1)); // In both, so removed
assert!(a.get(2)); // Only in b

Source §

impl Borrow<[u64]> for SmolBitmap

Source §

fn borrow(&self) -> &[u64]

Immutably borrows from an owned value. Read more

Source §

impl Clone for SmolBitmap

Source §

fn clone(&self) -> Self

Returns a duplicate of the value. Read more

1.0.0 · Source§

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

Performs copy-assignment from source. Read more

Source §

impl Debug for SmolBitmap

Source §

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

Formats the value using the given formatter. Read more

Source §

impl Default for SmolBitmap

Source §

fn default() -> Self

Returns the “default value” for a type. Read more

Source §

impl<'de> Deserialize<'de> for SmolBitmap

Source §

fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
where D: Deserializer<'de>,

Deserialize a SmolBitmap using little-endian byte order.

§Errors

Returns an error if deserialization fails.

Source §

impl<D: Fallible + ?Sized> Deserialize<SmolBitmap, D> for ArchivedSmolBitmap

Source §

fn deserialize(&self, _deserializer: &mut D) -> Result<SmolBitmap, D::Error>

Deserializes using the given deserializer

Source §

impl Display for SmolBitmap

Source §

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

Formats the value using the given formatter. Read more

Source §

impl Drop for SmolBitmap

Source §

fn drop(&mut self)

Executes the destructor for this type. Read more

Source §

impl Extend<usize> for SmolBitmap

Source §

fn extend<I: IntoIterator<Item = usize>>(&mut self, iter: I)

Extends a collection with the contents of an iterator. Read more

Source §

fn extend_one(&mut self, item: A)

🔬This is a nightly-only experimental API. (extend_one)

Extends a collection with exactly one element.

Source §

fn extend_reserve(&mut self, additional: usize)

🔬This is a nightly-only experimental API. (extend_one)

Reserves capacity in a collection for the given number of additional elements. Read more

Source §