Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/gen_map.rs

4.4 KiB, 1 run

created by r1870400018:68813, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1//! A map swept by generation under a byte ceiling, the shape of an incremental compiler's cache.
2//!
3//! A compile calls [`GenMap::begin`], reads and inserts, then calls [`GenMap::sweep`]. A read marks an
4//! entry as touched in the generation, and the sweep drops an entry that neither of the last two
5//! generations touched, so the map holds at most the working sets of the last two compiles.
6//!
7//! An insert that would take the held bytes over the ceiling is refused, and nothing is evicted to make
8//! room: an entry the running compile may still read is never dropped under it. The caller states each
9//! entry's size, since the map cannot measure a value; a map whose entries are not worth counting states
10//! zero and is given no ceiling ([`GenMap::unbounded`]).
11
12use std::borrow::Borrow;
13use std::collections::HashMap;
14use std::hash::Hash;
15
16
17#[derive(Clone, Debug)]
18struct Slot<V> {
19 val: V,
20 size: usize,
21 last: u64, // The generation that last touched the entry.
22}
23
24#[derive(Clone, Debug)]
25pub struct GenMap<K, V> {
26 map: HashMap<K, Slot<V>>,
27 epoch: u64,
28 bytes: usize, // The sizes of the entries held.
29 ceiling: usize,
30 refused: u64, // Inserts refused at the ceiling since the map was made.
31}
32
33// An unbounded map is the default, for a holder that derives its own.
34impl<K, V> Default for GenMap<K, V> {
35 fn default() -> Self { Self::unbounded() }
36}
37
38impl<K, V> GenMap<K, V> {
39 /// A map that holds at most `ceiling` bytes of entries.
40 pub fn new(ceiling: usize) -> Self {
41 Self {
42 map: HashMap::new(),
43 epoch: 0,
44 bytes: 0,
45 ceiling,
46 refused: 0,
47 }
48 }
49
50 /// A map with no ceiling, swept by generation alone.
51 pub fn unbounded() -> Self { Self::new(usize::MAX) }
52
53 /// Opens a generation. Entries read or inserted from now on are touched in it.
54 pub fn begin(&mut self) { self.epoch = self.epoch.wrapping_add(1); }
55
56 /// Drops every entry that neither this generation nor the one before touched, and answers how many
57 /// went. Called at the end of a compile, it leaves the entries of the last two compiles.
58 pub fn sweep(&mut self) -> usize {
59 let epoch = self.epoch;
60 let before = self.map.len();
61 let mut freed = 0usize;
62 self.map.retain(|_, s| {
63 let keep = epoch.wrapping_sub(s.last) < 2;
64 if !keep {
65 freed += s.size;
66 }
67 keep
68 });
69 self.bytes -= freed;
70 before - self.map.len()
71 }
72
73 /// Drops every entry. The generation, the ceiling and the count of refusals stand.
74 pub fn clear(&mut self) {
75 self.map.clear();
76 self.bytes = 0;
77 }
78
79 pub fn len(&self) -> usize { self.map.len() }
80
81 pub fn is_empty(&self) -> bool { self.map.is_empty() }
82
83 pub fn bytes(&self) -> usize { self.bytes }
84
85 pub fn ceiling(&self) -> usize { self.ceiling }
86
87 /// Sets the ceiling. A ceiling below the bytes held evicts nothing: inserts are refused until sweeps
88 /// have brought the map under it.
89 pub fn set_ceiling(&mut self, ceiling: usize) { self.ceiling = ceiling; }
90
91 pub fn refused(&self) -> u64 { self.refused }
92
93 pub fn epoch(&self) -> u64 { self.epoch }
94}
95
96impl<K: Eq + Hash, V> GenMap<K, V> {
97 /// Reads an entry and marks it touched in this generation.
98 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
99 where
100 K: Borrow<Q>,
101 Q: Eq + Hash + ?Sized,
102 {
103 let epoch = self.epoch;
104 match self.map.get_mut(key) {
105 Some(s) => {
106 s.last = epoch;
107 Some(&s.val)
108 },
109 None => None,
110 }
111 }
112
113 /// Reads an entry without marking it, so that a look does not keep it from the sweep.
114 pub fn peek<Q>(&self, key: &Q) -> Option<&V>
115 where
116 K: Borrow<Q>,
117 Q: Eq + Hash + ?Sized,
118 {
119 self.map.get(key).map(|s| &s.val)
120 }
121
122 pub fn contains<Q>(&self, key: &Q) -> bool
123 where
124 K: Borrow<Q>,
125 Q: Eq + Hash + ?Sized,
126 {
127 self.map.contains_key(key)
128 }
129
130 /// Stores an entry of `size` bytes, touched in this generation, and answers whether it was stored. An
131 /// entry that would take the map over its ceiling is refused, and one that replaces another is refused
132 /// when the replacement would. A refused replacement leaves the old entry in place and touched.
133 pub fn insert(&mut self, key: K, val: V, size: usize) -> bool {
134 let epoch = self.epoch;
135 let held = self.map.get(&key).map_or(0, |s| s.size);
136 let next = (self.bytes - held).checked_add(size).filter(|n| *n <= self.ceiling);
137 match next {
138 Some(n) => {
139 self.map.insert(key, Slot { val, size, last: epoch });
140 self.bytes = n;
141 true
142 },
143 None => {
144 if let Some(s) = self.map.get_mut(&key) {
145 s.last = epoch;
146 }
147 self.refused += 1;
148 false
149 },
150 }
151 }
152}