toolbox_rs/
lru.rs

1use crate::linked_list::{LinkedList, ListCursor};
2use std::{collections::HashMap, fmt::Debug, hash::Hash};
3
4/// A simple LRU implementation for a fixed size data set that avoid reallocation memory
5/// Instead of using a standard linked list with stable iterators, it us
6pub struct LRU<Key: Copy + Debug + Eq + Hash, Value> {
7    lru_list: LinkedList<(Key, Value)>,
8    access_map: HashMap<Key, ListCursor<(Key, Value)>>,
9    capacity: usize,
10}
11
12impl<Key: Copy + Debug + Eq + Hash, Value> LRU<Key, Value> {
13    pub fn new_with_capacity(capacity: usize) -> Self {
14        debug_assert!(capacity > 0);
15        let storage = LinkedList::new();
16        let indices = HashMap::with_capacity(capacity);
17        LRU {
18            lru_list: storage,
19            access_map: indices,
20            capacity,
21        }
22    }
23
24    pub fn push(&mut self, key: &Key, value: Value) {
25        debug_assert!(self.lru_list.len() <= self.capacity);
26        debug_assert!(!self.access_map.contains_key(key));
27        if self.access_map.len() == self.capacity {
28            // evict an element
29            debug_assert!(!self.access_map.is_empty());
30            let evicted = self.lru_list.pop_back();
31            let evicted_key = &evicted.unwrap().0;
32            self.access_map.remove(evicted_key);
33        }
34        let handle = self.lru_list.push_front((*key, value));
35        self.access_map.insert(*key, handle);
36    }
37
38    pub fn contains(&self, key: &Key) -> bool {
39        self.access_map.contains_key(key)
40    }
41
42    pub fn get(&mut self, key: &Key) -> Option<&Value> {
43        if let Some(handle) = self.access_map.get(key) {
44            self.lru_list.move_to_front(handle);
45            return Some(&self.lru_list.get_front().1);
46        }
47        None
48    }
49
50    pub fn capacity(&self) -> usize {
51        self.capacity
52    }
53
54    pub fn len(&self) -> usize {
55        assert_eq!(self.lru_list.len(), self.access_map.len());
56        self.lru_list.len()
57    }
58
59    pub fn is_empty(&self) -> bool {
60        self.len() == 0
61    }
62
63    pub fn clear(&mut self) {
64        self.lru_list.clear();
65        self.access_map.clear();
66    }
67}
68
69#[cfg(test)]
70mod tests {
71    use super::LRU;
72
73    struct SomeTestStruct(i32);
74
75    #[test]
76    fn construct() {
77        let mut lru = LRU::new_with_capacity(10);
78        assert_eq!(0, lru.len());
79        lru.push(&1, SomeTestStruct(1));
80        assert_eq!(1, lru.len());
81        lru.push(&2, SomeTestStruct(2));
82        assert_eq!(2, lru.len());
83        lru.push(&3, SomeTestStruct(3));
84        assert_eq!(3, lru.len());
85        lru.push(&4, SomeTestStruct(4));
86        assert_eq!(4, lru.len());
87        lru.push(&5, SomeTestStruct(5));
88        assert_eq!(5, lru.len());
89        lru.push(&6, SomeTestStruct(6));
90        assert_eq!(6, lru.len());
91        lru.push(&7, SomeTestStruct(7));
92        assert_eq!(7, lru.len());
93        lru.push(&8, SomeTestStruct(8));
94        assert_eq!(8, lru.len());
95        lru.push(&9, SomeTestStruct(9));
96        assert_eq!(9, lru.len());
97        lru.push(&10, SomeTestStruct(10));
98        assert_eq!(10, lru.len());
99        assert_eq!(10, lru.capacity());
100
101        // access 1, make 2 the oldest element now
102        let handle = lru.get(&1).unwrap();
103        assert_eq!(1, handle.0);
104        // add 11, evict 2
105        lru.push(&11, SomeTestStruct(11));
106        assert!(!lru.contains(&2));
107        assert_eq!(lru.len(), 10);
108
109        // get handle for evicted element and verify it is None
110        let handle = lru.get(&2);
111        assert!(handle.is_none());
112
113        // assert that all other elements are still cached
114        let keys = vec![1, 3, 4, 5, 6, 7, 8, 9, 10, 11];
115        keys.into_iter().for_each(|key| {
116            assert!(lru.contains(&key));
117        });
118    }
119
120    #[test]
121    fn clear_is_empty() {
122        let mut lru = LRU::new_with_capacity(10);
123        for i in [0, 1, 2, 3] {
124            lru.push(&i, 2 * i);
125        }
126        assert!(!lru.is_empty());
127        lru.clear();
128        assert!(lru.is_empty());
129    }
130}
toolbox_rs/lru.rs

toolbox_rs/
lru.rs
