use std::sync::Arc;
use crate::error::Error;
use crate::limits::{Meter, MeteredVec};
const BITS: usize = u64::BITS as usize;
const MAX_LEVELS: usize = (usize::BITS as usize).div_ceil(6) + 1;
const _: () = assert!(MAX_LEVELS >= 11);
pub(super) struct Pending {
words: MeteredVec<u64>,
starts: [usize; MAX_LEVELS + 1],
levels: usize,
}
impl Pending {
pub(super) fn full(len: usize, meter: &Arc<Meter>) -> Result<Self, Error> {
let mut starts = [0; MAX_LEVELS + 1];
let mut levels = 0;
let mut total = 0_usize;
let mut n = len.div_ceil(BITS).max(1);
for end in starts.iter_mut().skip(1) {
total = total.saturating_add(n);
*end = total;
levels += 1;
if n == 1 {
break;
}
n = n.div_ceil(BITS);
}
let mut words = MeteredVec::with_capacity(meter, total)?;
let mut bits = len;
for level in starts.windows(2).take(levels) {
let &[start, end] = level else {
break;
};
for w in 0..end - start {
let left = bits.saturating_sub(w * BITS);
words.push(if left >= BITS {
u64::MAX
} else {
(1_u64 << left) - 1
})?;
}
bits = end - start;
}
Ok(Self {
words,
starts,
levels,
})
}
pub(super) fn levels(&self) -> usize {
self.levels
}
fn at(&self, level: usize, w: usize) -> Option<usize> {
let start = *self.starts.get(level)?;
let end = *self.starts.get(level.checked_add(1)?)?;
start.checked_add(w).filter(|&at| at < end)
}
fn word(&self, level: usize, w: usize) -> Option<u64> {
let at = self.at(level, w)?;
self.words.as_slice().get(at).copied()
}
fn word_mut(&mut self, level: usize, w: usize) -> Option<&mut u64> {
let at = self.at(level, w)?;
self.words.as_mut_slice().get_mut(at)
}
pub(super) fn first_from(&self, from: usize) -> Option<usize> {
let mut level = 0;
let mut at = from;
loop {
let word = self.word(level, at / BITS)?;
let rest = word & (u64::MAX << (at % BITS));
if rest != 0 {
let mut found = (at / BITS) * BITS + rest.trailing_zeros() as usize;
while level > 0 {
level -= 1;
let below = self.word(level, found)?;
found = found * BITS + below.trailing_zeros() as usize;
}
return Some(found);
}
level += 1;
if level == self.levels {
return None;
}
at = at / BITS + 1;
}
}
pub(super) fn remove(&mut self, i: usize) {
let mut at = i;
for level in 0..self.levels {
let Some(word) = self.word_mut(level, at / BITS) else {
return;
};
*word &= !(1 << (at % BITS));
if *word != 0 {
return;
}
at /= BITS;
}
}
pub(super) fn insert(&mut self, i: usize) {
let mut at = i;
for level in 0..self.levels {
let Some(word) = self.word_mut(level, at / BITS) else {
return;
};
let was = *word;
*word |= 1 << (at % BITS);
if was != 0 {
return;
}
at /= BITS;
}
}
}
#[cfg(test)]
mod tests {
use std::collections::BTreeSet;
use super::Pending;
use crate::limits::Meter;
use unityrs_testkit::rng::Rng;
fn all(p: &Pending) -> Vec<usize> {
let mut out = Vec::new();
let mut at = p.first_from(0);
while let Some(i) = at {
out.push(i);
at = p.first_from(i + 1);
}
out
}
#[test]
fn pending_is_an_ordered_set() {
let meter = Meter::unlimited();
let mut rng = Rng::new(0x0013_d0d0);
for len in [1, 2, 63, 64, 65, 4095, 4096, 4097, 300_000] {
let mut p = Pending::full(len, &meter).unwrap();
let mut model: BTreeSet<usize> = (0..len).collect();
let levels = match len {
0..=64 => 1,
65..=4096 => 2,
4097..=262_144 => 3,
_ => 4,
};
assert_eq!(p.levels(), levels, "{len}");
assert_eq!(p.first_from(len), None, "{len}");
assert_eq!(p.first_from(len + 1000), None, "{len}");
for _ in 0..4000 {
let i = rng.below(len);
match rng.below(3) {
0 => {
p.remove(i);
model.remove(&i);
}
1 => {
p.insert(i);
model.insert(i);
}
_ => {}
}
let from = rng.below(len + 2);
assert_eq!(
p.first_from(from),
model.range(from..).next().copied(),
"{len} from {from}"
);
}
if len <= 4097 {
assert_eq!(all(&p), model.iter().copied().collect::<Vec<_>>());
for i in 0..len {
p.remove(i);
}
assert_eq!(p.first_from(0), None, "{len}: emptied");
p.insert(len - 1);
assert_eq!(p.first_from(0), Some(len - 1), "{len}");
}
}
}
#[test]
fn pending_charges_its_words() {
let meter = Meter::unlimited();
let p = Pending::full(4097, &meter).unwrap();
assert_eq!(p.words.len(), 68);
assert!(meter.used() >= 68 * 8);
}
}