ahrightos_fs/
lru_cache.rs1use 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}