cranpose_core/collections/
pass_aged.rs

1//! Caches that forget what layout stopped asking for.
2
3use std::{borrow::Borrow, hash::Hash};
4
5use super::bounded_lru::BoundedLruCache;
6
7/// Layout passes an entry may go without a lookup before it leaves. Text on
8/// screen is measured again only when its layout changes, so this is how long
9/// a list may keep an item scrolled out before measuring it anew costs a miss.
10pub const IDLE_PASSES: u64 = 120;
11
12/// A value and the layout pass that last looked it up.
13struct Used<V> {
14    value: V,
15    pass: u64,
16}
17
18/// A bounded LRU cache whose entries also leave once [`IDLE_PASSES`] layout
19/// passes go by without a lookup of them. A scrolling list then keeps the
20/// measurements of the texts it shows, not of every text it has shown up to
21/// the bound.
22pub struct PassAgedCache<K, V> {
23    entries: BoundedLruCache<K, Used<V>>,
24    pass: u64,
25}
26
27impl<K, V> PassAgedCache<K, V>
28where
29    K: Eq + Hash,
30{
31    pub fn with_capacity_at_least_one(capacity: usize) -> Self {
32        Self {
33            entries: BoundedLruCache::with_capacity_at_least_one(capacity),
34            pass: 0,
35        }
36    }
37
38    pub fn len(&self) -> usize {
39        self.entries.len()
40    }
41
42    pub fn is_empty(&self) -> bool {
43        self.entries.is_empty()
44    }
45
46    /// Drops every entry and gives back the storage they took.
47    pub fn clear(&mut self) {
48        self.entries.clear();
49    }
50
51    /// The value under `key`, marked used in the current pass.
52    pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
53    where
54        K: Borrow<Q>,
55        Q: Hash + Eq + ?Sized,
56    {
57        let pass = self.pass;
58        let used = self.entries.get_mut(key)?;
59        used.pass = pass;
60        Some(&used.value)
61    }
62
63    /// Stores `value` under `key`, returning the entry it replaced or the
64    /// least recently used one it pushed out.
65    pub fn push(&mut self, key: K, value: V) -> Option<(K, V)> {
66        let pass = self.pass;
67        self.entries
68            .push(key, Used { value, pass })
69            .map(|(key, used)| (key, used.value))
70    }
71
72    pub fn pop_lru(&mut self) -> Option<(K, V)> {
73        self.entries.pop_lru().map(|(key, used)| (key, used.value))
74    }
75
76    /// Starts a layout pass: drops the entries no lookup asked for in the
77    /// last [`IDLE_PASSES`] passes, least recently used first, handing each
78    /// dropped value to `dropped`. It stops at the first entry still in use,
79    /// so it costs one comparison when nothing has gone idle.
80    pub fn begin_pass(&mut self, mut dropped: impl FnMut(V)) {
81        self.pass += 1;
82        let pass = self.pass;
83        while self
84            .entries
85            .peek_lru()
86            .is_some_and(|(_, used)| pass - used.pass > IDLE_PASSES)
87        {
88            let Some((_, used)) = self.entries.pop_lru() else {
89                break;
90            };
91            dropped(used.value);
92        }
93    }
94}
95
96#[cfg(test)]
97#[path = "tests/pass_aged_tests.rs"]
98mod tests;
cranpose_core/collections/pass_aged.rs

cranpose_core/collections/
pass_aged.rs
