Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_datime/src/cache/lru.rs

6.6 KiB, 30 runs

created by r1870400018:8321, 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//! Safe LRU (Least Recently Used) cache implementation.
2//!
3//! Storage is a plain Vec, so several operations are O(n). Safety is preferred
4//! over speed here, and no unsafe code is used.
5//!
6//! [Written with AI entirely](https://need2know.ai/entirely-ai/code)\
7//! Anthropic Claude
8
9use std::hash::Hash;
10
11#[derive(Debug)]
12pub struct LruCacheInner<K, V>
13where
14 K: Hash + Eq + Clone,
15 V: Clone,
16{
17 items: Vec<(K, V)>, // most recent first
18 capacity: usize,
19 hits: u64,
20 misses: u64,
21}
22
23impl<K, V> LruCacheInner<K, V>
24where
25 K: Hash + Eq + Clone,
26 V: Clone,
27{
28 pub fn new(capacity: usize) -> Self {
29 Self {
30 items: Vec::with_capacity(capacity),
31 capacity,
32 hits: 0,
33 misses: 0,
34 }
35 }
36
37 pub fn get(&mut self, key: &K) -> Option<V> {
38 if let Some(pos) = self.find_key_position(key) {
39 self.hits += 1;
40 let (_, value) = self.items[pos].clone();
41
42 // Move to front (most recent)
43 let item = self.items.remove(pos);
44 self.items.insert(0, item);
45
46 Some(value)
47 } else {
48 self.misses += 1;
49 None
50 }
51 }
52
53 /// Evicts the least recently used entry when the insert takes the cache over capacity.
54 pub fn insert(&mut self, key: K, value: V) {
55 // Check if key already exists
56 if let Some(pos) = self.find_key_position(&key) {
57 // Update existing entry and move to front
58 self.items.remove(pos);
59 self.items.insert(0, (key, value));
60 } else {
61 // Insert new entry at front
62 self.items.insert(0, (key, value));
63
64 // Remove oldest entry if over capacity
65 if self.items.len() > self.capacity {
66 self.items.pop();
67 }
68 }
69 }
70
71 fn find_key_position(&self, key: &K) -> Option<usize> {
72 self.items.iter().position(|(k, _)| k == key)
73 }
74
75 pub fn len(&self) -> usize {
76 self.items.len()
77 }
78
79 pub fn is_empty(&self) -> bool {
80 self.items.is_empty()
81 }
82
83 pub fn clear(&mut self) {
84 self.items.clear();
85 self.hits = 0;
86 self.misses = 0;
87 }
88
89 /// Hits, misses and hit ratio, in that order.
90 pub fn stats(&self) -> (u64, u64, f64) {
91 let total = self.hits + self.misses;
92 let hit_ratio = if total > 0 {
93 self.hits as f64 / total as f64
94 } else {
95 0.0
96 };
97 (self.hits, self.misses, hit_ratio)
98 }
99
100 pub fn iter(&self) -> impl Iterator<Item = (&K, &V)> {
101 self.items.iter().map(|(k, v)| (k, v))
102 }
103
104 pub fn contains_key(&self, key: &K) -> bool {
105 self.find_key_position(key).is_some()
106 }
107
108 pub fn remove(&mut self, key: &K) -> Option<V> {
109 if let Some(pos) = self.find_key_position(key) {
110 let (_, value) = self.items.remove(pos);
111 Some(value)
112 } else {
113 None
114 }
115 }
116
117 pub fn capacity(&self) -> usize {
118 self.capacity
119 }
120
121 /// Shrinking discards the least recently used entries.
122 pub fn resize(&mut self, new_capacity: usize) {
123 self.capacity = new_capacity;
124
125 // Trim items if new capacity is smaller
126 if self.items.len() > new_capacity {
127 self.items.truncate(new_capacity);
128 }
129 }
130
131 /// Reads without promoting the entry.
132 pub fn peek(&self, key: &K) -> Option<&V> {
133 self.find_key_position(key)
134 .map(|pos| &self.items[pos].1)
135 }
136
137 pub fn peek_lru(&self) -> Option<(&K, &V)> {
138 self.items.last().map(|(k, v)| (k, v))
139 }
140
141 pub fn peek_mru(&self) -> Option<(&K, &V)> {
142 self.items.first().map(|(k, v)| (k, v))
143 }
144}
145
146impl<K, V> Clone for LruCacheInner<K, V>
147where
148 K: Hash + Eq + Clone,
149 V: Clone,
150{
151 fn clone(&self) -> Self {
152 Self {
153 items: self.items.clone(),
154 capacity: self.capacity,
155 hits: self.hits,
156 misses: self.misses,
157 }
158 }
159}
160
161#[cfg(test)]
162mod tests {
163 use super::*;
164
165 #[test]
166 fn test_lru_cache_inner_basic() {
167 let mut cache = LruCacheInner::new(2);
168
169 // Test insertion
170 cache.insert(1, "one");
171 cache.insert(2, "two");
172 assert_eq!(cache.len(), 2);
173
174 // Test retrieval
175 assert_eq!(cache.get(&1), Some("one"));
176 assert_eq!(cache.get(&2), Some("two"));
177 assert_eq!(cache.get(&3), None);
178
179 // Test LRU eviction
180 cache.insert(3, "three");
181 assert_eq!(cache.len(), 2);
182
183 // After inserting 3, and getting 1 and 2, the order should be [2, 1]
184 // So when we insert 3, it should evict the LRU item
185 assert!(cache.contains_key(&2));
186 assert!(cache.contains_key(&3));
187 }
188
189 #[test]
190 fn test_lru_cache_inner_update() {
191 let mut cache = LruCacheInner::new(2);
192
193 cache.insert(1, "one");
194 cache.insert(2, "two");
195
196 // Update existing key
197 cache.insert(1, "ONE");
198 assert_eq!(cache.get(&1), Some("ONE"));
199 assert_eq!(cache.len(), 2);
200
201 // Key 1 should now be most recent
202 cache.insert(3, "three");
203 assert!(cache.contains_key(&1)); // Should still be present
204 assert!(cache.contains_key(&3)); // Should be present
205 assert_eq!(cache.len(), 2);
206 }
207
208 #[test]
209 fn test_lru_cache_inner_stats() {
210 let mut cache = LruCacheInner::new(2);
211
212 cache.insert(1, "one");
213 cache.insert(2, "two");
214
215 // Generate some hits and misses
216 let _ = cache.get(&1); // hit
217 let _ = cache.get(&2); // hit
218 let _ = cache.get(&3); // miss
219 let _ = cache.get(&1); // hit
220
221 let (hits, misses, hit_ratio) = cache.stats();
222 assert_eq!(hits, 3);
223 assert_eq!(misses, 1);
224 assert_eq!(hit_ratio, 0.75);
225 }
226
227 #[test]
228 fn test_lru_cache_inner_clear() {
229 let mut cache = LruCacheInner::new(2);
230
231 cache.insert(1, "one");
232 cache.insert(2, "two");
233 assert_eq!(cache.len(), 2);
234
235 cache.clear();
236 assert_eq!(cache.len(), 0);
237 assert!(cache.is_empty());
238
239 let (hits, misses, hit_ratio) = cache.stats();
240 assert_eq!(hits, 0);
241 assert_eq!(misses, 0);
242 assert_eq!(hit_ratio, 0.0);
243 }
244
245 #[test]
246 fn test_lru_cache_peek_operations() {
247 let mut cache = LruCacheInner::new(3);
248
249 cache.insert(1, "one");
250 cache.insert(2, "two");
251 cache.insert(3, "three");
252
253 // Peek should not affect LRU order
254 assert_eq!(cache.peek(&2), Some(&"two"));
255
256 // MRU should be 3 (most recently inserted)
257 assert_eq!(cache.peek_mru(), Some((&3, &"three")));
258
259 // LRU should be 1 (least recently used)
260 assert_eq!(cache.peek_lru(), Some((&1, &"one")));
261 }
262
263 #[test]
264 fn test_lru_cache_resize() {
265 let mut cache = LruCacheInner::new(3);
266
267 cache.insert(1, "one");
268 cache.insert(2, "two");
269 cache.insert(3, "three");
270 assert_eq!(cache.len(), 3);
271
272 // Resize to smaller capacity
273 cache.resize(2);
274 assert_eq!(cache.capacity(), 2);
275 assert_eq!(cache.len(), 2); // Should have trimmed one item
276
277 // Resize to larger capacity
278 cache.resize(5);
279 assert_eq!(cache.capacity(), 5);
280 assert_eq!(cache.len(), 2); // Length should remain the same
281 }
282
283 #[test]
284 fn test_lru_cache_remove() {
285 let mut cache = LruCacheInner::new(3);
286
287 cache.insert(1, "one");
288 cache.insert(2, "two");
289 cache.insert(3, "three");
290
291 // Remove existing key
292 assert_eq!(cache.remove(&2), Some("two"));
293 assert_eq!(cache.len(), 2);
294 assert!(!cache.contains_key(&2));
295
296 // Remove non-existing key
297 assert_eq!(cache.remove(&4), None);
298 assert_eq!(cache.len(), 2);
299 }
300}