use std::collections::BTreeMap;
use std::mem::size_of;
use std::ops::Bound;
use std::sync::Arc;
use super::Slot;
use crate::limits::heap_cost;
pub(super) const STEP: u64 = 8;
pub(super) fn search_steps(n: usize) -> u64 {
n.checked_sub(1).map_or(1, |m| u64::from(m.bit_width()) + 1)
}
const ELEMENT: usize = size_of::<u64>() + size_of::<Arc<Slot>>();
const LEAF: u64 = heap_cost((16 + 11 * ELEMENT) as u64);
const INTERNAL: u64 = heap_cost((16 + 11 * ELEMENT + 12 * size_of::<usize>()) as u64);
pub(super) const SHARE: u64 = LEAF / 5 + 1 + INTERNAL / 30 + 1;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(super) enum List {
Listed,
Evicted,
}
#[derive(Debug, Default)]
pub(super) struct Pending {
listed: BTreeMap<u64, Arc<Slot>>,
evicted: BTreeMap<u64, Arc<Slot>>,
next: u64,
}
impl Pending {
fn list(&self, list: List) -> &BTreeMap<u64, Arc<Slot>> {
match list {
List::Listed => &self.listed,
List::Evicted => &self.evicted,
}
}
fn list_mut(&mut self, list: List) -> &mut BTreeMap<u64, Arc<Slot>> {
match list {
List::Listed => &mut self.listed,
List::Evicted => &mut self.evicted,
}
}
pub(super) fn push(&mut self, slot: Arc<Slot>) -> (u64, u64) {
let seq = self.next;
self.next = seq.saturating_add(1);
let steps = search_steps(self.listed.len());
self.listed.insert(seq, slot);
(seq, steps)
}
pub(super) fn after(&self, list: List, after: Option<u64>) -> (Option<(u64, Arc<Slot>)>, u64) {
let slots = self.list(list);
let lower = after.map_or(Bound::Unbounded, Bound::Excluded);
let found = slots
.range((lower, Bound::Unbounded))
.next()
.map(|(s, slot)| (*s, slot.clone()));
(found, search_steps(slots.len()))
}
pub(super) fn take(&mut self, list: List, seq: u64) -> (Option<Arc<Slot>>, u64) {
let slots = self.list_mut(list);
let steps = search_steps(slots.len());
let taken = slots.remove(&seq);
if slots.is_empty() {
*slots = BTreeMap::new();
}
(taken, steps)
}
pub(super) fn defer(&mut self, seq: u64) -> u64 {
let (taken, steps) = self.take(List::Listed, seq);
let Some(slot) = taken else {
return steps;
};
let more = search_steps(self.evicted.len());
self.evicted.insert(seq, slot);
steps.saturating_add(more)
}
pub(super) fn len(&self, list: List) -> usize {
self.list(list).len()
}
#[cfg(test)]
pub(super) fn all(&self) -> Vec<(u64, Arc<Slot>)> {
let mut all: Vec<_> = self
.listed
.iter()
.chain(&self.evicted)
.map(|(s, slot)| (*s, slot.clone()))
.collect();
all.sort_by_key(|(s, _)| *s);
all
}
}
#[cfg(test)]
mod tests {
use std::collections::BTreeMap;
use std::sync::Arc;
use super::{List, Pending, search_steps};
use crate::env::registry::Slot;
#[test]
fn the_lists_are_the_b_trees_their_steps_are_counted_for() {
let mut p = Pending::default();
let lists: [&BTreeMap<u64, Arc<Slot>>; 2] = [&p.listed, &p.evicted];
assert!(lists.iter().all(|l| l.is_empty()));
assert_eq!(p.after(List::Listed, None).1, search_steps(0));
assert_eq!(p.take(List::Listed, 0).1, search_steps(0));
assert_eq!(p.defer(0), search_steps(0));
let steps: Vec<u64> = [1, 2, 3, 4, 5, 8, 9, 1024, 1025]
.into_iter()
.map(search_steps)
.collect();
assert_eq!(steps, [1, 2, 3, 3, 4, 4, 5, 11, 12]);
}
}