use crate::layout::BLOCK_SIZE;
pub const BITS_PER_BLOCK: usize = BLOCK_SIZE * 8;
#[derive(Clone, Debug)]
pub struct Bitmap {
start_index: u32,
bit_count: usize,
blocks: Vec<[u8; BLOCK_SIZE]>,
}
impl Bitmap {
pub fn empty(start_index: u32, bit_count: usize) -> Self {
let block_count = bit_count.max(1).div_ceil(BITS_PER_BLOCK);
Self {
start_index,
bit_count,
blocks: vec![[0_u8; BLOCK_SIZE]; block_count],
}
}
pub fn from_blocks(start_index: u32, bit_count: usize, blocks: Vec<[u8; BLOCK_SIZE]>) -> Self {
Self {
start_index,
bit_count,
blocks,
}
}
pub fn start_index(&self) -> u32 {
self.start_index
}
pub fn bit_count(&self) -> usize {
self.bit_count
}
pub fn block_count(&self) -> usize {
self.blocks.len()
}
pub fn blocks(&self) -> &[[u8; BLOCK_SIZE]] {
&self.blocks
}
pub fn is_set(&self, value: u32) -> bool {
let Some(relative) = value.checked_sub(self.start_index) else {
return false;
};
let relative = relative as usize;
if relative >= self.bit_count {
return false;
}
let (byte_index, bit_mask) = Self::bit_position(relative);
let block = byte_index / BLOCK_SIZE;
let byte = byte_index % BLOCK_SIZE;
self.blocks[block][byte] & bit_mask != 0
}
pub fn set(&mut self, value: u32) {
let relative = (value - self.start_index) as usize;
let (byte_index, bit_mask) = Self::bit_position(relative);
let block = byte_index / BLOCK_SIZE;
let byte = byte_index % BLOCK_SIZE;
self.blocks[block][byte] |= bit_mask;
}
pub fn clear(&mut self, value: u32) {
let relative = (value - self.start_index) as usize;
let (byte_index, bit_mask) = Self::bit_position(relative);
let block = byte_index / BLOCK_SIZE;
let byte = byte_index % BLOCK_SIZE;
self.blocks[block][byte] &= !bit_mask;
}
pub fn alloc(&mut self) -> Option<u32> {
for relative in 0..self.bit_count {
let value = self.start_index + relative as u32;
if !self.is_set(value) {
self.set(value);
return Some(value);
}
}
None
}
pub fn count_free(&self) -> usize {
(0..self.bit_count)
.map(|relative| self.start_index + relative as u32)
.filter(|value| !self.is_set(*value))
.count()
}
fn bit_position(relative: usize) -> (usize, u8) {
let byte_index = relative / 8;
let bit_mask = 1_u8 << (relative % 8);
(byte_index, bit_mask)
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn allocation_returns_the_first_free_value() {
let mut bitmap = Bitmap::empty(5, 4);
bitmap.set(5);
bitmap.set(6);
assert_eq!(bitmap.alloc(), Some(7));
assert_eq!(bitmap.alloc(), Some(8));
assert_eq!(bitmap.alloc(), None);
}
}