supa_mdx_lint/utils/
lru.rs

Help
1use std::{
2    borrow::Borrow,
3    collections::{HashMap, VecDeque},
4    hash::Hash,
5};
6
7pub(crate) struct LruCache<K, V>
8where
9    K: Eq + Hash + Clone,
10{
11    capacity: usize,
12    inner: HashMap<K, V>,
13    usage_queue: VecDeque<K>,
14}
15
16impl<K, V> std::fmt::Debug for LruCache<K, V>
17where
18    K: std::fmt::Debug + Eq + Hash + Clone,
19    V: std::fmt::Debug,
20{
21    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
22        f.debug_struct("LruCache")
23            .field("capacity", &self.capacity)
24            .field("inner", &self.inner)
25            .field("usage_queue", &self.usage_queue)
26            .finish()
27    }
28}
29
30impl<K, V> Default for LruCache<K, V>
31where
32    K: Eq + Hash + Clone,
33{
34    fn default() -> Self {
35        Self {
36            capacity: 10,
37            inner: HashMap::default(),
38            usage_queue: VecDeque::default(),
39        }
40    }
41}
42
43impl<K, V> LruCache<K, V>
44where
45    K: Eq + Hash + Clone,
46{
47    pub(crate) fn contains_key<Q>(&self, key: &Q) -> bool
48    where
49        K: Borrow<Q>,
50        Q: Hash + Eq + ?Sized,
51    {
52        self.inner.contains_key(key)
53    }
54
55    pub(crate) fn insert(&mut self, key: K, value: V) -> Option<V> {
56        if self.inner.contains_key(&key) {
57            self.usage_queue.retain(|k| k != &key);
58        } else if self.inner.len().saturating_add(1) > self.capacity {
59            if let Some(lru_key) = self.usage_queue.pop_front() {
60                self.inner.remove(&lru_key);
61            }
62        }
63
64        self.usage_queue.push_back(key.clone());
65        self.inner.insert(key, value)
66    }
67
68    pub(crate) fn get(&mut self, key: &K) -> Option<&V> {
69        if self.inner.contains_key(key) {
70            self.usage_queue.retain(|k| k != key);
71            self.usage_queue.push_back(key.clone());
72        }
73        self.inner.get(key)
74    }
75}
76
77#[cfg(test)]
78mod tests {
79    use super::*;
80
81    #[test]
82    fn test_lru_cache_basic() {
83        let mut cache = LruCache::<String, i32>::default();
84
85        // Insert some items
86        assert_eq!(cache.insert("a".to_string(), 1), None);
87        assert_eq!(cache.insert("b".to_string(), 2), None);
88        assert_eq!(cache.insert("c".to_string(), 3), None);
89
90        // Check if keys exist
91        assert!(cache.contains_key("a"));
92        assert!(cache.contains_key("b"));
93        assert!(cache.contains_key("c"));
94
95        // Overwrite existing key
96        assert_eq!(cache.insert("b".to_string(), 22), Some(2));
97        assert!(cache.contains_key("b"));
98        assert_eq!(cache.get(&"b".to_string()), Some(&22));
99    }
100
101    #[test]
102    fn test_lru_cache_eviction() {
103        let mut cache = LruCache::<String, i32>::default();
104        cache.capacity = 3;
105
106        // Fill the cache
107        cache.insert("a".to_string(), 1);
108        cache.insert("b".to_string(), 2);
109        cache.insert("c".to_string(), 3);
110
111        // All three items should be in the cache
112        assert!(cache.contains_key("a"));
113        assert!(cache.contains_key("b"));
114        assert!(cache.contains_key("c"));
115
116        // Adding a new item should evict the least recently used item (a)
117        cache.insert("d".to_string(), 4);
118        assert!(!cache.contains_key("a"));
119        assert!(cache.contains_key("b"));
120        assert!(cache.contains_key("c"));
121        assert!(cache.contains_key("d"));
122
123        // Using an item moves it to the back of the queue
124        // Access b (now b is most recently used)
125        cache.insert("b".to_string(), 22);
126
127        // Adding another item should evict c now
128        cache.insert("e".to_string(), 5);
129        assert!(!cache.contains_key("a"));
130        assert!(cache.contains_key("b"));
131        assert!(!cache.contains_key("c"));
132        assert!(cache.contains_key("d"));
133        assert!(cache.contains_key("e"));
134    }
135}
supa_mdx_lint/utils/lru.rs

supa_mdx_lint/utils/
lru.rs
