generational_cache/cache/
lru_cache.rs

1//! Module providing abstractions to represent an LRUCache.
2//!
3//! ## Usage
4//!
5//! ```rust
6//! use generational_cache::prelude::*;
7//!
8//! const CAPACITY: usize = 3;
9//!
10//! let mut cache = LRUCache::<_, i32, u64, AllocBTreeMap<_, _>>::with_backing_vector(Array::<_, CAPACITY>::new());
11//!
12//! cache.insert(-1, 1).unwrap();
13//! cache.insert(-2, 2).unwrap();
14//! cache.insert(-3, 3).unwrap();
15//!
16//! assert_eq!(cache.least_recent().unwrap(), (&-1, &1));
17//! assert_eq!(cache.most_recent().unwrap(), (&-3, &3));
18//!
19//! assert_eq!(cache.insert(-4, 4).unwrap(), Eviction::Block { key: -1, value: 1});
20//!
21//! assert_eq!(cache.least_recent().unwrap(), (&-2, &2));
22//! assert_eq!(cache.most_recent().unwrap(), (&-4, &4));
23//!
24//! assert_eq!(cache.insert(-2, 42).unwrap(), Eviction::Value(2));
25//!
26//! assert_eq!(cache.least_recent().unwrap(), (&-3, &3));
27//! assert_eq!(cache.most_recent().unwrap(), (&-2, &42));
28//!
29//! assert_eq!(cache.remove(&-42).unwrap(), Lookup::Miss);
30//! assert_eq!(cache.query(&-42).unwrap(), Lookup::Miss);
31//!
32//! assert_eq!(cache.query(&-3).unwrap(), Lookup::Hit(&3));
33//!
34//! assert_eq!(cache.least_recent().unwrap(), (&-4, &4));
35//! assert_eq!(cache.most_recent().unwrap(), (&-3, &3));
36//!
37//! assert_eq!(cache.remove(&-2).unwrap(), Lookup::Hit(42));
38//!
39//! assert_eq!(cache.query(&-2).unwrap(), Lookup::Miss);
40//!
41//! // zero capacity LRUCache is unusable
42//! let mut cache = LRUCache::<_, i32, u64, AllocBTreeMap<_, _>>::with_backing_vector(Array::<_, 0_usize>::new());
43//!
44//! match cache.insert(0, 0) {
45//!     Err(LRUCacheError::ListUnderflow) => {}
46//!     _ => unreachable!("Wrong error on list underflow."),
47//! };
48//!
49//! ```
50
51use crate::{
52    cache::{Cache, Eviction},
53    collections::list::{Link, LinkedList, LinkedListArenaEntry, ListError},
54    map::Map,
55    vector::Vector,
56};
57use core::{
58    fmt::{Debug, Display},
59    mem,
60};
61
62use super::Lookup;
63
64extern crate alloc;
65
66/// A cache block containing a key value pair.
67#[derive(Clone, Copy)]
68pub struct Block<K, T> {
69    pub key: K,
70    pub value: T,
71}
72
73/// Alias representing block entries for storage in a generational arena.
74pub type LRUCacheBlockArenaEntry<K, T> = LinkedListArenaEntry<Block<K, T>>;
75
76/// A generational [`Arena`](crate::arena::Arena) backed LRU cache implementation.
77///
78/// This [`Cache`] implementation always evicts the least-recently-used (LRU) key/value pair. It
79/// uses a [`LinkedList`] for storing the underlying cache block entries to maintain the order
80/// in which they were inserted into the cache.
81///
82/// It uses a generational [`Arena`](crate::arena::Arena) for allocating the underlying
83/// [`LinkedList`] which stores the cache blocks. It uses a [`Map`] for maintaining the mapping
84/// from keys to the nodes storing the respective cache blocks in the [`LinkedList`].
85///
86/// ### Type parameters
87/// - `V: Vector<LRUCacheBlockArenaEntry<K, T>>`
88///     Used as the backing vector for the underlying [`Arena`](crate::arena::Arena).
89/// - `K`
90///     The Key type.
91/// - `V`
92///     The Value type.
93/// - `M: Map<K, Link>`
94///     Used to store a mapping from the keys to links in the linked list.
95///
96pub struct LRUCache<V, K, T, M> {
97    block_list: LinkedList<V, Block<K, T>>,
98    block_refs: M,
99
100    capacity: usize,
101}
102
103impl<V, K, T, M> LRUCache<V, K, T, M>
104where
105    V: Vector<LRUCacheBlockArenaEntry<K, T>>,
106    M: Map<K, Link>,
107{
108    /// Returns the least recently used key/value pair.
109    pub fn least_recent(&self) -> Option<(&K, &T)> {
110        let block = self.block_list.peek_front()?;
111        Some((&block.key, &block.value))
112    }
113
114    /// Returns the most recently used key/value pair.
115    pub fn most_recent(&self) -> Option<(&K, &T)> {
116        let block = self.block_list.peek_back()?;
117        Some((&block.key, &block.value))
118    }
119}
120
121impl<V, K, T, M> LRUCache<V, K, T, M>
122where
123    V: Vector<LRUCacheBlockArenaEntry<K, T>>,
124    M: Map<K, Link>,
125{
126    /// Creates an [`LRUCache`] instance with the given the backing [`Vector`] and [`Map`]
127    /// implementation instances.
128    pub fn with_backing_vector_and_map(vector: V, map: M) -> Self {
129        let block_list = LinkedList::with_backing_vector(vector);
130        let capacity = block_list.capacity();
131
132        Self {
133            block_list,
134            block_refs: map,
135            capacity,
136        }
137    }
138}
139
140impl<V, K, T, M> LRUCache<V, K, T, M>
141where
142    V: Vector<LRUCacheBlockArenaEntry<K, T>>,
143    M: Map<K, Link> + Default,
144{
145    /// Creates an [`LRUCache`] instance with the given [`Vector`] implementation instance
146    /// and the default [`Map`] implementation value.
147    pub fn with_backing_vector(vector: V) -> Self {
148        Self::with_backing_vector_and_map(vector, M::default())
149    }
150}
151
152impl<V, K, T, M> Default for LRUCache<V, K, T, M>
153where
154    V: Vector<LRUCacheBlockArenaEntry<K, T>> + Default,
155    M: Map<K, Link> + Default,
156{
157    fn default() -> Self {
158        Self::with_backing_vector(V::default())
159    }
160}
161
162/// Error type associated with [`LRUCache`] operations.
163#[derive(Debug)]
164pub enum LRUCacheError<VE, ME> {
165    /// Used when there is an error on an operation in the underlying list.
166    ListError(ListError<VE>),
167
168    /// Used when attempting to remove elements from the underlying list when its empty.
169    ListUnderflow,
170
171    /// Used when the underlying map and list instances contain an inconsistent view
172    /// of the entries allocated in the LRUCache
173    MapListInconsistent,
174
175    /// Used when there is an error on an operation in the underlying map..
176    MapError(ME),
177}
178
179impl<VE, ME> Display for LRUCacheError<VE, ME>
180where
181    VE: Debug,
182    ME: Debug,
183{
184    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
185        write!(f, "{self:?}")
186    }
187}
188
189#[allow(unused)]
190impl<V, K, T, M> Cache<K, T> for LRUCache<V, K, T, M>
191where
192    V: Vector<LRUCacheBlockArenaEntry<K, T>>,
193    M: Map<K, Link>,
194    K: Copy,
195{
196    type Error = LRUCacheError<V::Error, M::Error>;
197
198    fn insert(&mut self, key: K, value: T) -> Result<Eviction<K, T>, Self::Error> {
199        if let Some(link) = self.block_refs.get(&key) {
200            self.block_list
201                .shift_push_back(link)
202                .ok_or(Self::Error::MapListInconsistent)?;
203
204            let block = self
205                .block_list
206                .get_mut(link)
207                .ok_or(Self::Error::MapListInconsistent)?;
208
209            return Ok(Eviction::Value(mem::replace(&mut block.value, value)));
210        }
211
212        let eviction = if self.is_maxed() {
213            let Block { key, value } = self
214                .block_list
215                .pop_front()
216                .ok_or(Self::Error::ListUnderflow)?;
217
218            self.block_refs.remove(&key);
219
220            Eviction::Block { key, value }
221        } else {
222            Eviction::None
223        };
224
225        let link = self
226            .block_list
227            .push_back(Block { key, value })
228            .map_err(Self::Error::ListError)?;
229
230        self.block_refs
231            .insert(key, link)
232            .map_err(Self::Error::MapError)?;
233
234        Ok(eviction)
235    }
236
237    fn remove(&mut self, key: &K) -> Result<Lookup<T>, Self::Error> {
238        match self.block_refs.remove(key) {
239            Some(link) => self
240                .block_list
241                .remove(&link)
242                .map(|x| Lookup::Hit(x.value))
243                .ok_or(Self::Error::MapListInconsistent),
244            _ => Ok(Lookup::Miss),
245        }
246    }
247
248    fn shrink(&mut self, new_capacity: usize) -> Result<(), Self::Error> {
249        if new_capacity >= self.capacity() {
250            return Ok(());
251        }
252
253        while self.len() > new_capacity {
254            let Block { key, value } = self
255                .block_list
256                .pop_front()
257                .ok_or(Self::Error::ListUnderflow)?;
258
259            self.block_refs.remove(&key);
260        }
261
262        self.capacity = new_capacity;
263
264        Ok(())
265    }
266
267    fn reserve(&mut self, additional: usize) -> Result<(), Self::Error> {
268        self.block_list
269            .reserve(additional)
270            .map_err(Self::Error::ListError)?;
271
272        self.capacity += additional;
273
274        Ok(())
275    }
276
277    fn query(&mut self, key: &K) -> Result<Lookup<&T>, Self::Error> {
278        match self.block_refs.get(key) {
279            Some(link) => {
280                self.block_list
281                    .shift_push_back(link)
282                    .ok_or(Self::Error::MapListInconsistent)?;
283
284                self.block_list
285                    .get(link)
286                    .map(|x| Lookup::Hit(&x.value))
287                    .ok_or(Self::Error::MapListInconsistent)
288            }
289            _ => Ok(Lookup::Miss),
290        }
291    }
292
293    fn capacity(&self) -> usize {
294        self.capacity
295    }
296
297    fn len(&self) -> usize {
298        self.block_list.len()
299    }
300
301    fn is_empty(&self) -> bool {
302        self.block_list.is_empty()
303    }
304
305    fn clear(&mut self) -> Result<(), Self::Error> {
306        self.block_list.clear().map_err(Self::Error::ListError)?;
307        self.block_refs.clear().map_err(Self::Error::MapError)?;
308
309        Ok(())
310    }
311}
312
313#[doc(hidden)]
314pub mod tests {
315
316    use super::{
317        Cache, Eviction, LRUCache, LRUCacheBlockArenaEntry, LRUCacheError, Link, Lookup, Map,
318        Vector,
319    };
320
321    pub fn _test_cache_correctness<VX, VY, M>(zero_capacity_vec: VX, test_vec: VY)
322    where
323        VX: Vector<LRUCacheBlockArenaEntry<usize, usize>>,
324        VY: Vector<LRUCacheBlockArenaEntry<usize, usize>>,
325        M: Map<usize, Link> + Default,
326    {
327        assert_eq!(
328            zero_capacity_vec.capacity(),
329            0,
330            "Zero capacity vector provider yielded vector of non zero capacity."
331        );
332
333        let mut cache = LRUCache::<_, _, _, M>::with_backing_vector(zero_capacity_vec);
334
335        assert!(cache.is_empty());
336
337        match cache.insert(0, 0) {
338            Err(LRUCacheError::ListUnderflow) => {}
339            _ => unreachable!("Wrong error on list underflow."),
340        };
341
342        let mut cache = LRUCache::<_, _, _, M>::with_backing_vector(test_vec);
343
344        let capacity = cache.capacity();
345
346        assert!(
347            capacity > 3,
348            "Too small capacity: {} to run meaningful tests.",
349            capacity
350        );
351
352        assert!(cache.is_empty());
353
354        for i in 0..cache.capacity() {
355            assert_eq!(cache.insert(i, i).unwrap(), Eviction::None);
356        }
357
358        assert_eq!(cache.least_recent().unwrap(), (&0, &0));
359
360        assert_eq!(
361            cache.insert(capacity, capacity).unwrap(),
362            Eviction::Block { key: 0, value: 0 }
363        );
364
365        assert_eq!(cache.query(&1).unwrap(), Lookup::Hit(&1));
366
367        assert_eq!(cache.least_recent().unwrap(), (&2, &2));
368        assert_eq!(cache.most_recent().unwrap(), (&1, &1));
369
370        assert_eq!(cache.remove(&(capacity + 1)).unwrap(), Lookup::Miss);
371        assert_eq!(cache.query(&(capacity + 1)).unwrap(), Lookup::Miss);
372
373        assert_eq!(
374            cache.insert(capacity + 1, capacity + 1).unwrap(),
375            Eviction::Block { key: 2, value: 2 }
376        );
377
378        assert_eq!(
379            cache.remove(&(capacity + 1)).unwrap(),
380            Lookup::Hit(capacity + 1)
381        );
382
383        assert_eq!(cache.remove(&(capacity + 1)).unwrap(), Lookup::Miss);
384        assert_eq!(cache.query(&(capacity + 1)).unwrap(), Lookup::Miss);
385
386        assert_eq!(
387            cache.insert(capacity, capacity + 2).unwrap(),
388            Eviction::Value(capacity)
389        );
390
391        assert_eq!(cache.most_recent().unwrap(), (&capacity, &(capacity + 2)));
392
393        cache.clear().unwrap();
394
395        assert!(cache.is_empty());
396
397        for i in 0..cache.capacity() {
398            assert_eq!(cache.insert(i, i).unwrap(), Eviction::None);
399        }
400
401        assert_eq!(cache.least_recent().unwrap(), (&0, &0));
402
403        const ADDITIONAL: usize = 5;
404
405        let result = cache.reserve(ADDITIONAL);
406
407        if result.is_ok() {
408            let old_len = cache.len();
409            for i in 0..ADDITIONAL {
410                assert_eq!(cache.insert(i + old_len, i).unwrap(), Eviction::None);
411            }
412        }
413
414        let old_capacity = cache.capacity();
415
416        cache.shrink(0).unwrap();
417
418        assert!(cache.is_maxed());
419
420        match cache.insert(0, 0) {
421            Err(LRUCacheError::ListUnderflow) => {}
422            _ => unreachable!("Wrong error on list underflow."),
423        };
424
425        assert!(cache.is_empty());
426
427        cache.reserve(old_capacity).unwrap();
428        cache.shrink(old_capacity).unwrap();
429
430        assert_eq!(cache.capacity(), old_capacity);
431
432        for i in 0..cache.capacity() {
433            assert_eq!(cache.insert(i, i).unwrap(), Eviction::None);
434        }
435
436        cache.clear().unwrap();
437
438        assert!(cache.is_empty());
439    }
440}
generational_cache/cache/lru_cache.rs

generational_cache/cache/
lru_cache.rs
