devpage_design/tiles/
cache.rs

1//! The tile cache: tiles by key, capped by a cost, least recently used
2//! dropped first; damage marks the tiles it overlaps stale, and a stale tile
3//! is still returned, as stale, until it is replaced. Generic over what a
4//! tile holds — the server's pixels, the module's GPU textures.
5
6use std::collections::{BTreeMap, HashMap};
7
8use kurbo::Rect as KRect;
9
10use crate::scene::Theme;
11
12use super::*;
13
14/// A cached tile: what it holds, what it costs, whether damage made it
15/// stale, and when it was last used.
16struct Entry<T> {
17    value: T,
18    cost: usize,
19    stale: bool,
20    used: u64,
21}
22
23/// Painted tiles, keyed by theme, level, column and row, holding at most
24/// `cap` of cost — bytes of pixels, or a count — the least recently used
25/// dropped first. Damage marks the tiles it overlaps stale; a stale tile is
26/// still there, and says so, until it is painted again. What a tile holds is
27/// the cache's user's: pixels in the server, a texture on the GPU.
28pub struct Cache<T, K: Tiled = Key> {
29    cap: usize,
30    cost: usize,
31    clock: u64,
32    entries: HashMap<K, Entry<T>>,
33    by_use: BTreeMap<u64, K>,
34}
35
36impl<T, K: Tiled> Cache<T, K> {
37    pub fn new(cap: usize) -> Cache<T, K> {
38        Cache {
39            cap,
40            cost: 0,
41            clock: 0,
42            entries: HashMap::new(),
43            by_use: BTreeMap::new(),
44        }
45    }
46
47    /// The tile at `key`, and whether it is stale; it counts as used.
48    pub fn get(&mut self, key: &K) -> Option<(&T, bool)> {
49        self.clock += 1;
50        let e = self.entries.get_mut(key)?;
51        self.by_use.remove(&e.used);
52        e.used = self.clock;
53        self.by_use.insert(self.clock, *key);
54        Some((&e.value, e.stale))
55    }
56
57    /// The tile at `key` and whether it is stale, without counting a use.
58    pub fn peek(&self, key: &K) -> Option<(&T, bool)> {
59        self.entries.get(key).map(|e| (&e.value, e.stale))
60    }
61
62    /// Keeps `value` as the current tile at `key`, costing `cost`, and drops
63    /// the least recently used others until the cache is within its cap.
64    /// Returns what was dropped.
65    pub fn insert(&mut self, key: K, value: T, cost: usize) -> Vec<(K, T)> {
66        // The tile it replaces isn't dropped: it is the same tile, painted again.
67        self.remove(&key);
68        let mut dropped = Vec::new();
69        self.clock += 1;
70        self.entries.insert(
71            key,
72            Entry {
73                value,
74                cost,
75                stale: false,
76                used: self.clock,
77            },
78        );
79        self.by_use.insert(self.clock, key);
80        self.cost += cost;
81        while self.cost > self.cap {
82            let Some((_, oldest)) = self.by_use.iter().next().map(|(u, k)| (*u, *k)) else {
83                break;
84            };
85            if oldest == key {
86                break;
87            }
88            if let Some(v) = self.remove(&oldest) {
89                dropped.push((oldest, v));
90            }
91        }
92        dropped
93    }
94
95    /// Takes the tile at `key` out.
96    pub fn remove(&mut self, key: &K) -> Option<T> {
97        let e = self.entries.remove(key)?;
98        self.by_use.remove(&e.used);
99        self.cost -= e.cost;
100        Some(e.value)
101    }
102
103    /// Marks stale every tile of `theme` that overlaps one of `rects` — in
104    /// the design's coordinates, the drawing's top-left at `origin` — at
105    /// every level.
106    pub fn damage(&mut self, theme: Theme, origin: (f64, f64), rects: &[KRect]) {
107        self.damage_where(|k| k.key().theme == theme, origin, rects);
108    }
109
110    /// Marks stale every tile `which` picks that overlaps one of `rects`, as
111    /// [`Cache::damage`] does.
112    pub fn damage_where(
113        &mut self,
114        which: impl Fn(&K) -> bool,
115        origin: (f64, f64),
116        rects: &[KRect],
117    ) {
118        for (k, e) in &mut self.entries {
119            if !e.stale && which(k) && k.key().overlaps(origin, rects) {
120                e.stale = true;
121            }
122        }
123    }
124
125    /// Marks every tile of `theme` stale.
126    pub fn damage_all(&mut self, theme: Theme) {
127        self.damage_all_where(|k| k.key().theme == theme);
128    }
129
130    /// Marks every tile `which` picks stale.
131    pub fn damage_all_where(&mut self, which: impl Fn(&K) -> bool) {
132        for (k, e) in &mut self.entries {
133            if which(k) {
134                e.stale = true;
135            }
136        }
137    }
138
139    /// Drops every tile `which` picks.
140    pub fn forget(&mut self, which: impl Fn(&K) -> bool) {
141        let gone: Vec<K> = self.entries.keys().filter(|k| which(k)).copied().collect();
142        for k in gone {
143            self.remove(&k);
144        }
145    }
146
147    /// Every tile, with whether it is stale.
148    pub fn iter(&self) -> impl Iterator<Item = (&K, &T, bool)> {
149        self.entries.iter().map(|(k, e)| (k, &e.value, e.stale))
150    }
151
152    /// Drops every tile.
153    pub fn clear(&mut self) -> Vec<T> {
154        self.by_use.clear();
155        self.cost = 0;
156        self.entries.drain().map(|(_, e)| e.value).collect()
157    }
158
159    pub fn len(&self) -> usize {
160        self.entries.len()
161    }
162
163    pub fn is_empty(&self) -> bool {
164        self.entries.is_empty()
165    }
166
167    /// What the tiles held cost together.
168    pub fn cost(&self) -> usize {
169        self.cost
170    }
171}
172
173#[cfg(test)]
174mod tests;
devpage_design/tiles/cache.rs

devpage_design/tiles/
cache.rs
