Skip to main content

ahrightos_fs/
lru_cache.rs

1use alloc::vec::Vec;
2use core::marker::PhantomData;
3
4pub trait Cacheable<K> {
5    fn key(&self) -> K;
6}
7
8#[derive(Debug)]
9pub struct LruCache<K, V>
10where
11    K: PartialEq,
12    V: Cacheable<K>,
13{
14    entries: Vec<V>,
15    capacity: usize,
16    _phantom: PhantomData<K>,
17}
18
19impl<K: PartialEq, V: Cacheable<K>> LruCache<K, V> {
20    pub fn new(capacity: usize) -> Self {
21        Self {
22            entries: Vec::with_capacity(capacity),
23            capacity,
24            _phantom: PhantomData,
25        }
26    }
27
28    pub fn get(&mut self, key: &K) -> Option<&V> {
29        for i in 0..self.entries.len() {
30            if self.entries[i].key() == *key {
31                if i + 1 == self.entries.len() {
32                    return self.entries.last();
33                }
34                let entry = self.entries.remove(i);
35                self.entries.push(entry);
36                return self.entries.last();
37            }
38        }
39        None
40    }
41
42    pub fn insert(&mut self, value: V) {
43        if self.capacity == 0 {
44            return;
45        }
46        let key = value.key();
47        if let Some(pos) = self.entries.iter().position(|entry| entry.key() == key) {
48            self.entries.remove(pos);
49        }
50        if self.entries.len() >= self.capacity {
51            self.entries.remove(0);
52        }
53        self.entries.push(value);
54    }
55
56    pub fn len(&self) -> usize {
57        self.entries.len()
58    }
59
60    pub fn is_empty(&self) -> bool {
61        self.entries.is_empty()
62    }
63
64    pub fn capacity(&self) -> usize {
65        self.capacity
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[derive(Debug, PartialEq, Eq)]
74    struct Entry {
75        key: usize,
76        value: usize,
77    }
78
79    impl Cacheable<usize> for Entry {
80        fn key(&self) -> usize {
81            self.key
82        }
83    }
84
85    #[test]
86    fn get_promotes_entry_to_mru() {
87        let mut cache = LruCache::<usize, Entry>::new(2);
88        cache.insert(Entry { key: 1, value: 10 });
89        cache.insert(Entry { key: 2, value: 20 });
90        assert_eq!(cache.get(&1).map(|entry| entry.value), Some(10));
91        cache.insert(Entry { key: 3, value: 30 });
92        assert_eq!(cache.get(&2).map(|entry| entry.value), None);
93        assert_eq!(cache.get(&1).map(|entry| entry.value), Some(10));
94    }
95}