use std::ops::Range;
use int::BinaryInteger;
use bitmaputils::*;
#[derive(Debug, Clone)]
pub struct BitmapAlloc {
bitmap: Vec<usize>,
size: usize,
next: usize,
}
#[derive(Debug, PartialEq, Eq, Hash)]
pub struct BitmapAllocRegion {
range: Range<usize>,
}
impl BitmapAlloc {
pub fn new(size: usize) -> Self {
let width = <usize>::max_digits() as usize;
Self {
bitmap: vec![0; (size + width - 1) / width],
size,
next: 0,
}
}
pub fn alloc(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
self.alloc_next(size)
}
pub fn alloc_next(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
let next = self.next;
self.alloc_inner(size, next).or_else(
|| self.alloc_first(size),
)
}
pub fn alloc_first(&mut self, size: usize) -> Option<(BitmapAllocRegion, usize)> {
self.alloc_inner(size, 0)
}
fn alloc_inner(&mut self, size: usize, start: usize) -> Option<(BitmapAllocRegion, usize)> {
assert!(size != 0);
if start + size > self.size {
return None;
}
find_zeros(&self.bitmap, start, size).and_then(|offs| {
let range = offs..offs + size;
if range.end <= self.size {
set_bits_ranged(&mut self.bitmap, range.clone());
if range.end == self.size {
self.next = 0;
} else {
self.next = range.end;
}
Some((BitmapAllocRegion { range }, offs))
} else {
None
}
})
}
pub fn dealloc_relaxed(&mut self, r: BitmapAllocRegion) {
if self.next == r.range.end {
self.next = r.range.start;
}
clear_bits_ranged(&mut self.bitmap, r.range);
}
}