alpha2_geometry/raster/
cache.rs

1//! Coverage kept between frames: a path that does not change is not
2//! rasterized again.
3
4use super::TileCoverage;
5use crate::{IRect, StableHash};
6use alpha2_model::FillRule;
7use kurbo::BezPath;
8use std::collections::HashMap;
9use std::sync::Arc;
10
11/// The key of `path`'s coverage under `rule` in `clip`: its bits, so only
12/// the same path in the same place shares it.
13#[must_use]
14pub fn coverage_key(path: &BezPath, rule: FillRule, clip: IRect) -> u128 {
15    let mut hash = StableHash::new();
16    hash.bytes(b"coverage");
17    hash.path(path);
18    hash.u32(match rule {
19        FillRule::Nonzero => 0,
20        FillRule::Evenodd => 1,
21    });
22    for edge in [clip.x0, clip.y0, clip.x1, clip.y1] {
23        hash.u32(edge.cast_unsigned());
24    }
25    hash.finish()
26}
27
28/// Coverage by key, least recently used first out, within a byte budget.
29#[derive(Debug)]
30pub struct CoverageCache {
31    budget: usize,
32    bytes: usize,
33    clock: u64,
34    entries: HashMap<u128, (Arc<TileCoverage>, u64)>,
35    hits: u64,
36    misses: u64,
37}
38
39/// The default budget: 64 MiB of tiles.
40pub const DEFAULT_COVERAGE_BUDGET: usize = 64 * 1024 * 1024;
41
42impl Default for CoverageCache {
43    fn default() -> Self {
44        Self::new(DEFAULT_COVERAGE_BUDGET)
45    }
46}
47
48impl CoverageCache {
49    /// An empty cache holding at most `budget` bytes.
50    #[must_use]
51    pub fn new(budget: usize) -> Self {
52        Self {
53            budget,
54            bytes: 0,
55            clock: 0,
56            entries: HashMap::new(),
57            hits: 0,
58            misses: 0,
59        }
60    }
61
62    /// The coverage kept under `key`, now the most recently used.
63    pub fn get(&mut self, key: u128) -> Option<Arc<TileCoverage>> {
64        self.clock += 1;
65        let clock = self.clock;
66        if let Some((coverage, used)) = self.entries.get_mut(&key) {
67            *used = clock;
68            self.hits += 1;
69            Some(Arc::clone(coverage))
70        } else {
71            self.misses += 1;
72            None
73        }
74    }
75
76    /// Keeps `coverage` under `key`, dropping the least recently used until
77    /// it fits. Coverage larger than the whole budget is not kept.
78    pub fn insert(&mut self, key: u128, coverage: Arc<TileCoverage>) {
79        let size = coverage.heap_bytes() + size_of::<TileCoverage>();
80        if size > self.budget {
81            return;
82        }
83        self.clock += 1;
84        if let Some((old, _)) = self.entries.insert(key, (coverage, self.clock)) {
85            self.bytes -= old.heap_bytes() + size_of::<TileCoverage>();
86        }
87        self.bytes += size;
88        while self.bytes > self.budget {
89            let Some(oldest) = self
90                .entries
91                .iter()
92                .min_by_key(|(_, (_, used))| *used)
93                .map(|(key, _)| *key)
94            else {
95                break;
96            };
97            if let Some((evicted, _)) = self.entries.remove(&oldest) {
98                self.bytes -= evicted.heap_bytes() + size_of::<TileCoverage>();
99            }
100        }
101    }
102
103    /// Drops everything kept.
104    pub fn clear(&mut self) {
105        self.entries.clear();
106        self.bytes = 0;
107    }
108
109    /// Bytes kept.
110    #[must_use]
111    pub const fn bytes(&self) -> usize {
112        self.bytes
113    }
114
115    /// Entries kept.
116    #[must_use]
117    pub fn len(&self) -> usize {
118        self.entries.len()
119    }
120
121    /// Whether nothing is kept.
122    #[must_use]
123    pub fn is_empty(&self) -> bool {
124        self.entries.is_empty()
125    }
126
127    /// Lookups that found coverage, and ones that did not.
128    #[must_use]
129    pub const fn hit_counts(&self) -> (u64, u64) {
130        (self.hits, self.misses)
131    }
132}
alpha2_geometry/raster/cache.rs

alpha2_geometry/raster/
cache.rs
