Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_data/src/lru.rs

3.6 KiB, 1 run

created by r1870400018:72224, 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 least-recently-used map under a byte ceiling.
2//!
3//! Where [`GenMap`](crate::gen_map::GenMap) refuses an insert at its ceiling, so that a running
4//! compile never loses an entry it may still read, this map makes room: an insert evicts the entries
5//! read or written longest ago until the new one fits. It suits a read cache of decoded values in
6//! front of a store, where any entry can be decoded again at a cost and the bound is on memory.
7//!
8//! The caller states each entry's size, since the map cannot measure a value. An entry larger than
9//! the whole ceiling is not stored, and evicts nothing.
10
11use std::borrow::Borrow;
12use std::collections::{
13 BTreeMap,
14 HashMap,
15};
16use std::hash::Hash;
17
18
19#[derive(Clone, Debug)]
20struct Slot<V> {
21 val: V,
22 size: usize,
23 tick: u64, // when it was last read or written
24}
25
26#[derive(Clone, Debug)]
27pub struct SizedLru<K, V> {
28 map: HashMap<K, Slot<V>>,
29 order: BTreeMap<u64, K>, // tick to key, oldest first
30 tick: u64,
31 bytes: usize, // the sizes of the entries held
32 ceiling: usize,
33 evicted: u64, // entries evicted since the map was made
34}
35
36impl<K, V> SizedLru<K, V> {
37 /// A map that holds at most `ceiling` bytes of entries.
38 pub fn new(ceiling: usize) -> Self {
39 Self {
40 map: HashMap::new(),
41 order: BTreeMap::new(),
42 tick: 0,
43 bytes: 0,
44 ceiling,
45 evicted: 0,
46 }
47 }
48
49 pub fn len(&self) -> usize { self.map.len() }
50
51 pub fn is_empty(&self) -> bool { self.map.is_empty() }
52
53 pub fn bytes(&self) -> usize { self.bytes }
54
55 pub fn ceiling(&self) -> usize { self.ceiling }
56
57 pub fn evicted(&self) -> u64 { self.evicted }
58
59 /// Drops every entry. The ceiling and the count of evictions stand.
60 pub fn clear(&mut self) {
61 self.map.clear();
62 self.order.clear();
63 self.bytes = 0;
64 }
65}
66
67impl<K: Eq + Hash + Clone, V> SizedLru<K, V> {
68 /// Reads an entry and makes it the most recently used.
69 pub fn get<Q>(&mut self, key: &Q) -> Option<&V>
70 where
71 K: Borrow<Q>,
72 Q: Eq + Hash + ?Sized,
73 {
74 self.tick = self.tick.wrapping_add(1);
75 let tick = self.tick;
76 match self.map.get_mut(key) {
77 Some(s) => {
78 if let Some(k) = self.order.remove(&s.tick) {
79 self.order.insert(tick, k);
80 }
81 s.tick = tick;
82 Some(&s.val)
83 },
84 None => None,
85 }
86 }
87
88 /// Reads an entry without making it recent.
89 pub fn peek<Q>(&self, key: &Q) -> Option<&V>
90 where
91 K: Borrow<Q>,
92 Q: Eq + Hash + ?Sized,
93 {
94 self.map.get(key).map(|s| &s.val)
95 }
96
97 pub fn contains<Q>(&self, key: &Q) -> bool
98 where
99 K: Borrow<Q>,
100 Q: Eq + Hash + ?Sized,
101 {
102 self.map.contains_key(key)
103 }
104
105 pub fn remove<Q>(&mut self, key: &Q) -> Option<V>
106 where
107 K: Borrow<Q>,
108 Q: Eq + Hash + ?Sized,
109 {
110 match self.map.remove(key) {
111 Some(s) => {
112 self.order.remove(&s.tick);
113 self.bytes -= s.size;
114 Some(s.val)
115 },
116 None => None,
117 }
118 }
119
120 /// Stores an entry of `size` bytes as the most recently used, evicting the least recently used
121 /// until it fits, and answers whether it was stored. One larger than the ceiling is not stored
122 /// and evicts nothing, though it still replaces, by removal, an entry under the same key.
123 pub fn insert(&mut self, key: K, val: V, size: usize) -> bool {
124 self.remove(&key);
125 if size > self.ceiling {
126 return false;
127 }
128 while self.bytes.saturating_add(size) > self.ceiling {
129 let oldest = match self.order.pop_first() {
130 Some((_, k)) => k,
131 None => break, // unreachable while bytes count only held entries
132 };
133 if let Some(s) = self.map.remove(&oldest) {
134 self.bytes -= s.size;
135 self.evicted += 1;
136 }
137 }
138 self.tick = self.tick.wrapping_add(1);
139 self.order.insert(self.tick, key.clone());
140 self.map.insert(key, Slot { val, size, tick: self.tick });
141 self.bytes += size;
142 true
143 }
144}