use std::collections::HashMap;
use std::hash::Hash;
pub const RENDERING_ENTRIES: usize = 8;
pub const RENDERING_BYTES: usize = 64 * 1024 * 1024;
pub const MACRO_ENVIRONMENT_ENTRIES: usize = 16;
pub const MACRO_ENVIRONMENT_NAMES: usize = 64 * 1024;
pub const EFFECT_ENTRIES: usize = 4096;
pub const VIEW_ENTRIES: usize = 8;
pub const RENDERING_VIEW_ENTRIES: usize = 4;
pub const RENDERING_VIEW_BYTES: usize = 256 * 1024 * 1024;
pub const VIEW_BYTES: usize = 64 * 1024 * 1024;
pub struct Cache<K, V> {
entries: HashMap<K, (V, u64, usize)>,
clock: u64,
weight: usize,
max_entries: usize,
max_weight: usize,
}
impl<K: Hash + Eq + Clone, V> Cache<K, V> {
pub fn new(max_entries: usize, max_weight: usize) -> Self {
Self {
entries: HashMap::new(),
clock: 0,
weight: 0,
max_entries,
max_weight,
}
}
pub fn renderings() -> Self {
Self::new(RENDERING_ENTRIES, RENDERING_BYTES)
}
pub fn views() -> Self {
Self::new(VIEW_ENTRIES, VIEW_BYTES)
}
pub fn rendering_views() -> Self {
Self::new(RENDERING_VIEW_ENTRIES, RENDERING_VIEW_BYTES)
}
pub fn macro_environments() -> Self {
Self::new(MACRO_ENVIRONMENT_ENTRIES, MACRO_ENVIRONMENT_NAMES)
}
pub fn effects() -> Self {
Self::new(EFFECT_ENTRIES, usize::MAX)
}
pub fn get(&mut self, key: &K) -> Option<&V> {
self.clock += 1;
let clock = self.clock;
let (value, used, _) = self.entries.get_mut(key)?;
*used = clock;
Some(value)
}
pub fn contains(&self, key: &K) -> bool {
self.entries.contains_key(key)
}
pub fn insert(&mut self, key: K, value: V, weight: usize) {
self.clock += 1;
let clock = self.clock;
if let Some((_, _, previous)) = self.entries.remove(&key) {
self.weight = self.weight.saturating_sub(previous);
}
self.entries.insert(key, (value, clock, weight));
self.weight = self.weight.saturating_add(weight);
self.evict();
}
fn evict(&mut self) {
while self.entries.len() > self.max_entries || self.weight > self.max_weight {
if self.entries.len() <= 1 {
break;
}
let oldest = self
.entries
.iter()
.min_by_key(|(_, (_, used, _))| *used)
.map(|(key, _)| key.clone());
let Some(oldest) = oldest else {
break;
};
if let Some((_, _, weight)) = self.entries.remove(&oldest) {
self.weight = self.weight.saturating_sub(weight);
}
}
}
pub fn len(&self) -> usize {
self.entries.len()
}
pub fn is_empty(&self) -> bool {
self.entries.is_empty()
}
pub fn weight(&self) -> usize {
self.weight
}
pub fn values(&self) -> impl Iterator<Item = &V> {
self.entries.values().map(|(value, _, _)| value)
}
pub fn keys(&self) -> impl Iterator<Item = &K> {
self.entries.keys()
}
pub fn remove(&mut self, key: &K) -> Option<V> {
let (value, _, weight) = self.entries.remove(key)?;
self.weight = self.weight.saturating_sub(weight);
Some(value)
}
pub fn retain(&mut self, mut keep: impl FnMut(&K) -> bool) {
let dropped: Vec<K> = self
.entries
.iter()
.filter(|(key, _)| !keep(key))
.map(|(key, _)| key.clone())
.collect();
for key in dropped {
self.remove(&key);
}
}
pub fn clear(&mut self) {
self.entries.clear();
self.weight = 0;
}
}
#[cfg(test)]
mod tests {
use super::*;
#[test]
fn an_entry_is_evicted_when_the_count_is_exceeded() {
let mut cache: Cache<u32, &str> = Cache::new(2, usize::MAX);
cache.insert(1, "one", 1);
cache.insert(2, "two", 1);
cache.insert(3, "three", 1);
assert_eq!(cache.len(), 2, "the cache holds two");
assert!(!cache.contains(&1), "the oldest went");
assert!(cache.contains(&2) && cache.contains(&3));
}
#[test]
fn a_used_entry_survives_the_eviction() {
let mut cache: Cache<u32, &str> = Cache::new(2, usize::MAX);
cache.insert(1, "one", 1);
cache.insert(2, "two", 1);
assert_eq!(cache.get(&1), Some(&"one"), "this marks 1 as used");
cache.insert(3, "three", 1);
assert!(cache.contains(&1), "the entry a query just read stays");
assert!(!cache.contains(&2), "the untouched one goes");
}
#[test]
fn the_weight_budget_evicts_before_the_count_does() {
let mut cache: Cache<u32, &str> = Cache::new(100, 10);
cache.insert(1, "one", 6);
cache.insert(2, "two", 6);
assert_eq!(cache.len(), 1, "12 units do not fit in 10");
assert!(cache.contains(&2), "the newer entry is the one kept");
}
#[test]
fn one_entry_over_the_budget_is_kept() {
let mut cache: Cache<u32, &str> = Cache::new(100, 4);
cache.insert(1, "huge", 1_000);
assert_eq!(cache.len(), 1, "a single oversized entry stays");
}
#[test]
fn retain_drops_what_the_predicate_rejects() {
let mut cache: Cache<u32, &str> = Cache::new(100, usize::MAX);
cache.insert(1, "one", 1);
cache.insert(2, "two", 1);
cache.retain(|key| *key != 1);
assert_eq!(cache.len(), 1);
assert!(cache.contains(&2));
assert_eq!(cache.weight(), 1, "the weight follows the entries");
}
}