Ranged Bitmap

A high-performance bitmap library with fixed-size, flexible, and small-optimized bitmap implementations.

Features

• All functions are constant
• Optimized range operations that work on multiple bits simultaneously
• Fixed-size bitmaps with compile-time size determination
• Flexible bitmaps that grow dynamically as needed
• Small-optimized bitmaps using SmallVec for stack storage with automatic heap growth
• No_std compatibility for embedded and bare-metal environments

Performance

This library is designed with performance as a primary goal:

• Range operations use precomputed lookup tables for optimal bit manipulation
• Bulk operations on full blocks use memset-like operations for maximum speed
• All functions are marked #[inline(always)] for aggressive inlining
• Constant functions enable compile-time optimizations
• Hardware-accelerated bit counting operations

Basic Usage

Fixed Bitmap (Compile-time size)

use ranged_bitmap::generate_fixed_bit_map_struct;

generate_fixed_bit_map_struct!(struct BitMap<256>); // Generates a 256-bit bitmap struct wrapper

// Create a 256-bit bitmap
let mut bitmap = BitMap::new();

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

// Gets individual bits
assert!(bitmap.get(10));
assert!(!bitmap.get(21));

// Set an entire range at once (much faster than individual operations)
bitmap.set_range(50, 100); // Set bits 50-149
bitmap.clear_range(0, 50); // Clear bits 0-49

// Check if a range is completely set or unset
assert!(bitmap.check_range_is_set(50, 100));
assert!(bitmap.check_range_is_unset(0, 50));

// Iterate over a range
for (index, value) in bitmap.iter_range(40, 20) {
    println!("Bit {}: {}", index, value);
}

// Count set bits
println!("Total set bits: {}", bitmap.count_ones());
println!("Total unset bits: {}", bitmap.count_zeros());

Flexible Bitmap (Dynamic size)

use ranged_bitmap::FlexBitMap;

// Create a flexible bitmap that grows as needed
let mut bitmap = FlexBitMap::new();

// Automatically grows when setting bits beyond current capacity
bitmap.set(1000); // Grows to accommodate bit 1000
bitmap.set_range(2000, 100); // Grows to accommodate the range

// All operations work the same as fixed bitmap
assert!(bitmap.get(1000));
assert!(bitmap.check_range_is_set(2000, 100));

// Check current capacity
println!("Current capacity: {} bits", bitmap.capacity());
println!("Number of blocks: {}", bitmap.blocks());

Small-Optimized Bitmap (Stack storage with heap growth)

use ranged_bitmap::generate_small_bit_map_struct;

// Generate a SmallBitMap wrapper with 4 blocks on the stack (256 bits)
generate_small_bit_map_struct!(struct MySmallBitmap<4>);

// Create a small-optimized bitmap
let mut bitmap = MySmallBitmap::new();

// Small bitmaps (≤256 bits) use only stack storage
bitmap.set_range(0, 64);   // Stack-only, no heap allocation
bitmap.set_range(64, 128);  // Still stack-only

// Large bitmaps automatically grow to heap when needed
bitmap.set_range(256, 1000); // Automatically spills to heap

println!("Capacity: {} bits", bitmap.capacity());

// All operations work the same as other bitmap types
assert!(bitmap.get(300));
assert!(bitmap.check_range_is_set(0, 192));

// Perfect for cases where most bitmaps are small but occasionally grow

Range Operations

The library excels at a range of operations:

use ranged_bitmap::FixedBitMap;

let mut bitmap = FixedBitMap::<2>::new(); // 128 bits

// Efficiently set large ranges
bitmap.set_range(0, 64);   // Set first block
bitmap.set_range(64, 64);  // Set second block

// Check range status
assert!(bitmap.check_range_is_set(0, 128));

// Clear ranges efficiently
bitmap.clear_range(32, 64); // Clear middle portion

Performance Characteristics

Bitmap Type Comparison

License

This project is licensed under the MIT License.