# 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)
```rust
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)
```rust
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)
```rust
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:
```rust
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
| Individual bit get/set/clear | O(1) | Single memory access |
| Range operations (single block) | O(1) | Bitmask operations |
| Range operations (multi-block) | O(n) | n = number of affected blocks |
| Full block operations | O(n) | memset-like optimizations |
| Bit counting | O(n) | Hardware-accelerated |
### Bitmap Type Comparison
| `FixedBitMap` | Stack only | Known size at compile time | Never |
| `SmallBitMap` | Stack + SmallVec | Usually small, occasionally large | Only when needed |
| `FlexBitMap` | Heap only | Unknown size, always dynamic | Always |
## License
This project is licensed under the MIT License.