use super::{LoadError, OrderedTable, Transient, UseDecl, admitted, search_units};
const DENSE_RATIO: usize = 64;
pub(super) enum Marks {
Sparse {
rows: OrderedTable<usize, u8>,
live: usize,
},
Dense(Vec<u8>),
}
impl Default for Marks {
fn default() -> Self {
Self::Sparse {
rows: OrderedTable::default(),
live: 0,
}
}
}
impl Marks {
pub(super) fn get(
&self,
module: usize,
charge: &dyn Fn(usize) -> Result<(), LoadError>,
) -> Result<Option<u8>, LoadError> {
Ok(match self {
Self::Sparse { rows, .. } => {
charge(2 * search_units(rows.len()))?;
rows.get(&module).copied()
}
Self::Dense(rows) => {
charge(1)?;
rows.get(module).copied()
}
})
}
pub(super) fn mark(
&mut self,
module: usize,
modules: usize,
returning: bool,
memory: &Transient<'_>,
decl: &UseDecl,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<bool, LoadError> {
let value = if returning { 2 } else { 1 };
match self {
Self::Dense(rows) => {
step(1)?;
if rows[module] != 0 {
return Ok(false);
}
rows[module] = value;
}
Self::Sparse { rows, live } => {
step(4 * search_units(rows.len()))?;
if rows.get(&module).is_some() {
return Ok(false);
}
admitted(memory, decl, live, |native| {
rows.insert(module, value, native)
})?;
if rows.len() >= modules.div_ceil(DENSE_RATIO) {
self.promote(modules, memory, decl, step)?;
}
}
}
Ok(true)
}
fn promote(
&mut self,
modules: usize,
memory: &Transient<'_>,
decl: &UseDecl,
step: &mut dyn FnMut(usize) -> Result<(), LoadError>,
) -> Result<(), LoadError> {
let Self::Sparse { rows, .. } = self else {
unreachable!("only sparse membership promotes")
};
step(modules.saturating_add(rows.len()))?;
let mut dense = Vec::new();
admitted(memory, decl, &mut 0, |native| {
native.reserve(&mut dense, modules)
})?;
dense.resize(modules, 0);
for (&module, &mark) in rows.ordered() {
dense[module] = mark;
}
let previous = std::mem::replace(self, Self::Dense(dense));
let Self::Sparse { rows, mut live } = previous else {
unreachable!("the original sparse account remains exclusive")
};
admitted(memory, decl, &mut live, |native| rows.release(native))
}
}