modo/cache/
lru.rs

1use std::collections::{HashMap, VecDeque};
2use std::hash::Hash;
3use std::num::NonZeroUsize;
4
5/// A fixed-capacity, in-memory least-recently-used (LRU) cache.
6///
7/// When the cache is full, inserting a new entry evicts the entry that was
8/// least recently accessed. Updating an existing key moves it to the
9/// most-recently-used position without consuming extra capacity.
10///
11/// `LruCache` is not `Sync`; wrap it in [`std::sync::RwLock`] or
12/// [`std::sync::Mutex`] when sharing across threads.
13///
14/// # Type parameters
15///
16/// - `K` — key type; must implement [`Eq`], [`Hash`], and [`Clone`].
17/// - `V` — value type; no bounds required.
18///
19/// # Examples
20///
21/// ```
22/// use std::num::NonZeroUsize;
23/// use modo::cache::LruCache;
24///
25/// let mut cache: LruCache<&str, u32> = LruCache::new(NonZeroUsize::new(2).unwrap());
26/// cache.put("a", 1);
27/// cache.put("b", 2);
28/// assert_eq!(cache.get(&"a"), Some(&1));
29///
30/// // Inserting a third entry evicts "b" (least recently used).
31/// cache.put("c", 3);
32/// assert!(cache.get(&"b").is_none());
33/// ```
34pub struct LruCache<K, V> {
35    map: HashMap<K, V>,
36    order: VecDeque<K>,
37    capacity: NonZeroUsize,
38}
39
40impl<K: Eq + Hash + Clone, V> LruCache<K, V> {
41    /// Creates a new `LruCache` with the given maximum `capacity`.
42    ///
43    /// The cache will hold at most `capacity` entries at any time. When a new
44    /// entry is inserted into a full cache, the least-recently-used entry is
45    /// evicted first.
46    pub fn new(capacity: NonZeroUsize) -> Self {
47        Self {
48            map: HashMap::with_capacity(capacity.get()),
49            order: VecDeque::with_capacity(capacity.get()),
50            capacity,
51        }
52    }
53
54    /// Returns a reference to the value associated with `key`, or `None` if
55    /// the key is not present.
56    ///
57    /// Accessing a key moves it to the most-recently-used position, making it
58    /// the last candidate for eviction.
59    pub fn get(&mut self, key: &K) -> Option<&V> {
60        if self.map.contains_key(key) {
61            // Move to back (most recently used)
62            if let Some(pos) = self.order.iter().position(|k| k == key) {
63                self.order.remove(pos);
64            }
65            self.order.push_back(key.clone());
66            self.map.get(key)
67        } else {
68            None
69        }
70    }
71
72    /// Inserts or updates the entry for `key` with the given `value`.
73    ///
74    /// - If `key` already exists, its value is replaced and it moves to the
75    ///   most-recently-used position.
76    /// - If the cache is at capacity and `key` is new, the least-recently-used
77    ///   entry is evicted before the new entry is inserted.
78    pub fn put(&mut self, key: K, value: V) {
79        if self.map.contains_key(&key) {
80            // Update existing — remove from order, will re-add at back
81            if let Some(pos) = self.order.iter().position(|k| k == &key) {
82                self.order.remove(pos);
83            }
84        } else if self.map.len() >= self.capacity.get() {
85            // Evict least recently used (front of deque)
86            if let Some(evicted) = self.order.pop_front() {
87                self.map.remove(&evicted);
88            }
89        }
90        self.map.insert(key.clone(), value);
91        self.order.push_back(key);
92    }
93}
94
95#[cfg(test)]
96mod tests {
97    use super::*;
98
99    fn cache(cap: usize) -> LruCache<String, String> {
100        LruCache::new(NonZeroUsize::new(cap).unwrap())
101    }
102
103    #[test]
104    fn get_returns_none_for_missing() {
105        let mut c = cache(2);
106        assert!(c.get(&"x".into()).is_none());
107    }
108
109    #[test]
110    fn put_and_get() {
111        let mut c = cache(2);
112        c.put("a".into(), "1".into());
113        assert_eq!(c.get(&"a".into()), Some(&"1".into()));
114    }
115
116    #[test]
117    fn evicts_lru_on_capacity() {
118        let mut c = cache(2);
119        c.put("a".into(), "1".into());
120        c.put("b".into(), "2".into());
121        c.put("c".into(), "3".into()); // evicts "a"
122        assert!(c.get(&"a".into()).is_none());
123        assert_eq!(c.get(&"b".into()), Some(&"2".into()));
124        assert_eq!(c.get(&"c".into()), Some(&"3".into()));
125    }
126
127    #[test]
128    fn get_refreshes_lru_order() {
129        let mut c = cache(2);
130        c.put("a".into(), "1".into());
131        c.put("b".into(), "2".into());
132        c.get(&"a".into()); // refresh "a"
133        c.put("c".into(), "3".into()); // evicts "b" (not "a")
134        assert_eq!(c.get(&"a".into()), Some(&"1".into()));
135        assert!(c.get(&"b".into()).is_none());
136    }
137
138    #[test]
139    fn put_updates_existing() {
140        let mut c = cache(2);
141        c.put("a".into(), "1".into());
142        c.put("a".into(), "2".into());
143        assert_eq!(c.get(&"a".into()), Some(&"2".into()));
144    }
145
146    #[test]
147    fn capacity_one() {
148        let mut c = cache(1);
149        c.put("a".into(), "1".into());
150        c.put("b".into(), "2".into());
151        assert!(c.get(&"a".into()).is_none());
152        assert_eq!(c.get(&"b".into()), Some(&"2".into()));
153    }
154}
modo/cache/lru.rs

modo/cache/
lru.rs
