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 | |
| 12 | use std::borrow::Borrow; |
| 13 | use std::collections::HashMap; |
| 14 | use std::hash::Hash; |
| 15 | |
| 16 | |
| 17 | #[derive(Clone, Debug)] |
| 18 | struct Slot<V> { |
| 19 | val: V, |
| 20 | size: usize, |
| 21 | last: u64, // The generation that last touched the entry. |
| 22 | } |
| 23 | |
| 24 | #[derive(Clone, Debug)] |
| 25 | pub 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. |
| 34 | impl<K, V> Default for GenMap<K, V> { |
| 35 | fn default() -> Self { Self::unbounded() } |
| 36 | } |
| 37 | |
| 38 | impl<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 | |
| 96 | impl<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 | } |