use std::collections::{HashMap, VecDeque};
#[cfg(test)]
mod tests;
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub(crate) struct Limits {
pub budget: usize,
pub ceiling: usize,
}
struct Resident<V> {
value: V,
bytes: usize,
last: u64,
}
pub(crate) struct FrameCache<V> {
entries: HashMap<u64, Resident<V>>,
order: VecDeque<(u64, u64)>,
limits: Limits,
bytes: usize,
tick: u64,
open: bool,
framed: bool,
}
impl<V> FrameCache<V> {
pub(crate) fn new(limits: Limits) -> Self {
debug_assert!(limits.budget <= limits.ceiling);
Self {
entries: HashMap::new(),
order: VecDeque::new(),
limits,
bytes: 0,
tick: 0,
open: false,
framed: false,
}
}
pub(crate) fn framed(limits: Limits) -> Self {
Self {
framed: true,
..Self::new(limits)
}
}
pub(crate) fn limits(&self) -> Limits {
self.limits
}
pub(crate) fn is_framed(&self) -> bool {
self.framed
}
pub(crate) fn bytes(&self) -> usize {
self.bytes
}
#[cfg(any(test, feature = "perf_profile"))]
pub(crate) fn len(&self) -> usize {
self.entries.len()
}
#[cfg(test)]
pub(crate) fn values(&self) -> impl Iterator<Item = &V> {
self.entries.values().map(|entry| &entry.value)
}
#[cfg(any(test, feature = "wgpu"))]
pub(crate) fn peek(&self, key: u64) -> Option<&V> {
self.entries.get(&key).map(|entry| &entry.value)
}
pub(crate) fn get(&mut self, key: u64) -> Option<&V> {
let stamp = self.stamp();
let entry = self.entries.get_mut(&key)?;
if entry.last != stamp {
entry.last = stamp;
self.order.push_back((stamp, key));
}
self.compact();
self.entries.get(&key).map(|entry| &entry.value)
}
pub(crate) fn insert(&mut self, key: u64, value: V, bytes: usize, mut evict: impl FnMut(V)) -> Result<(), V> {
let stamp = self.stamp();
if let Some(old) = self.entries.remove(&key) {
self.bytes -= old.bytes;
evict(old.value);
}
let limit = if self.framed {
self.limits.ceiling
} else {
self.limits.budget
};
if bytes > limit {
return Err(value);
}
self.evict_older_than(
self.protected_from(),
self.limits.budget.saturating_sub(bytes),
&mut evict,
);
if self.bytes + bytes > limit {
return Err(value);
}
self.bytes += bytes;
self.entries.insert(
key,
Resident {
value,
bytes,
last: stamp,
},
);
self.order.push_back((stamp, key));
self.compact();
Ok(())
}
pub(crate) fn close_frame(&mut self, mut evict: impl FnMut(V)) {
self.framed = true;
if self.open {
self.open = false;
self.evict_older_than(self.protected_from(), self.limits.budget, &mut evict);
}
}
fn protected_from(&self) -> u64 {
if self.framed {
self.tick.saturating_sub(1)
} else {
u64::MAX
}
}
fn stamp(&mut self) -> u64 {
if !self.framed || !self.open {
self.tick += 1;
self.open = true;
}
self.tick
}
fn evict_older_than(&mut self, keep: u64, target: usize, evict: &mut impl FnMut(V)) {
while self.bytes > target {
let Some(&(last, key)) = self.order.front() else {
return;
};
if self.entries.get(&key).is_some_and(|entry| entry.last == last) {
if last >= keep {
return;
}
let entry = self.entries.remove(&key).unwrap();
self.bytes -= entry.bytes;
evict(entry.value);
}
self.order.pop_front();
}
}
fn compact(&mut self) {
if self.order.len() <= 2 * self.entries.len() + 64 {
return;
}
let mut order: Vec<_> = self.entries.iter().map(|(key, entry)| (entry.last, *key)).collect();
order.sort_unstable();
self.order = order.into();
}
}