pub struct TombstoneMap {
bits: Vec<u64>,
}
impl TombstoneMap {
pub fn new() -> Self {
Self { bits: Vec::new() }
}
pub fn mark_deleted(&mut self, vec_id: u32) {
let word = vec_id as usize / 64;
let bit = vec_id as usize % 64;
if word >= self.bits.len() {
self.bits.resize(word + 1, 0);
}
self.bits[word] |= 1u64 << bit;
}
pub fn restore(&mut self, vec_id: u32) {
if let Some(word) = self.bits.get_mut(vec_id as usize / 64) {
*word &= !(1u64 << (vec_id as usize % 64));
}
}
pub fn is_deleted(&self, vec_id: u32) -> bool {
let word = vec_id as usize / 64;
let bit = vec_id as usize % 64;
if word >= self.bits.len() {
return false;
}
(self.bits[word] >> bit) & 1 == 1
}
pub fn count(&self) -> usize {
self.bits.iter().map(|w| w.count_ones() as usize).sum()
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn marks_only_the_deleted_slots_across_word_boundaries() {
let mut t = TombstoneMap::new();
assert!(!t.is_deleted(0));
assert!(!t.is_deleted(1000));
t.mark_deleted(0);
t.mark_deleted(63);
t.mark_deleted(64);
t.mark_deleted(1000);
assert_eq!(t.count(), 4);
assert!(t.is_deleted(0));
assert!(t.is_deleted(63));
assert!(t.is_deleted(64));
assert!(t.is_deleted(1000));
assert!(!t.is_deleted(1));
}
}