cache_mod/
lru.rs

1//! Least-Recently-Used (LRU) cache — the reference implementation of
2//! [`Cache`](crate::Cache).
3
4use core::hash::Hash;
5use std::collections::{HashMap, VecDeque};
6use std::num::NonZeroUsize;
7use std::sync::Mutex;
8
9use crate::cache::Cache;
10use crate::error::CacheError;
11use crate::util::MutexExt;
12
13/// A bounded, thread-safe LRU cache.
14///
15/// On insert overflow the least-recently-accessed entry is evicted. Both
16/// [`get`](Cache::get) and [`insert`](Cache::insert) count as accesses and
17/// promote the affected entry to most-recently-used.
18///
19/// This is the reference implementation: correct, `&self`-everywhere,
20/// `Mutex`-guarded. A lock-free, arena-backed implementation lands in a
21/// later minor without changing this public surface.
22///
23/// # Example
24///
25/// ```
26/// use cache_mod::{Cache, LruCache};
27///
28/// let cache: LruCache<u32, &'static str> = LruCache::new(2).expect("capacity > 0");
29///
30/// cache.insert(1, "one");
31/// cache.insert(2, "two");
32/// assert_eq!(cache.get(&1), Some("one")); // 1 is now MRU, 2 is LRU
33///
34/// cache.insert(3, "three"); // evicts 2
35/// assert_eq!(cache.get(&2), None);
36/// assert_eq!(cache.get(&1), Some("one"));
37/// assert_eq!(cache.get(&3), Some("three"));
38/// ```
39pub struct LruCache<K, V> {
40    capacity: NonZeroUsize,
41    inner: Mutex<Inner<K, V>>,
42}
43
44struct Inner<K, V> {
45    /// Storage of live entries.
46    map: HashMap<K, V>,
47    /// Access order. Front = most-recently-used, back = least-recently-used.
48    order: VecDeque<K>,
49}
50
51impl<K, V> LruCache<K, V>
52where
53    K: Eq + Hash + Clone,
54    V: Clone,
55{
56    /// Creates a cache with the given capacity.
57    ///
58    /// Returns [`CacheError::InvalidCapacity`] if `capacity == 0`.
59    ///
60    /// # Example
61    ///
62    /// ```
63    /// use cache_mod::LruCache;
64    ///
65    /// let cache: LruCache<String, u32> = LruCache::new(128).expect("capacity > 0");
66    /// ```
67    pub fn new(capacity: usize) -> Result<Self, CacheError> {
68        let cap = NonZeroUsize::new(capacity).ok_or(CacheError::InvalidCapacity)?;
69        Ok(Self::with_capacity(cap))
70    }
71
72    /// Creates a cache with the given non-zero capacity. Infallible.
73    ///
74    /// # Example
75    ///
76    /// ```
77    /// use std::num::NonZeroUsize;
78    /// use cache_mod::LruCache;
79    ///
80    /// let cap = NonZeroUsize::new(64).expect("64 != 0");
81    /// let cache: LruCache<String, u32> = LruCache::with_capacity(cap);
82    /// ```
83    pub fn with_capacity(capacity: NonZeroUsize) -> Self {
84        let cap = capacity.get();
85        Self {
86            capacity,
87            inner: Mutex::new(Inner {
88                map: HashMap::with_capacity(cap),
89                order: VecDeque::with_capacity(cap),
90            }),
91        }
92    }
93}
94
95impl<K, V> Cache<K, V> for LruCache<K, V>
96where
97    K: Eq + Hash + Clone,
98    V: Clone,
99{
100    fn get(&self, key: &K) -> Option<V> {
101        let mut inner = self.inner.lock_recover();
102        let value = inner.map.get(key)?.clone();
103        promote(&mut inner.order, key);
104        Some(value)
105    }
106
107    fn insert(&self, key: K, value: V) -> Option<V> {
108        let mut inner = self.inner.lock_recover();
109        let old = inner.map.insert(key.clone(), value);
110        if old.is_some() {
111            promote(&mut inner.order, &key);
112        } else {
113            inner.order.push_front(key);
114            while inner.order.len() > self.capacity.get() {
115                if let Some(evicted) = inner.order.pop_back() {
116                    let _ = inner.map.remove(&evicted);
117                }
118            }
119        }
120        old
121    }
122
123    fn remove(&self, key: &K) -> Option<V> {
124        let mut inner = self.inner.lock_recover();
125        let value = inner.map.remove(key)?;
126        if let Some(pos) = inner.order.iter().position(|k| k == key) {
127            let _ = inner.order.remove(pos);
128        }
129        Some(value)
130    }
131
132    fn contains_key(&self, key: &K) -> bool {
133        self.inner.lock_recover().map.contains_key(key)
134    }
135
136    fn len(&self) -> usize {
137        self.inner.lock_recover().map.len()
138    }
139
140    fn clear(&self) {
141        let mut inner = self.inner.lock_recover();
142        inner.map.clear();
143        inner.order.clear();
144    }
145
146    fn capacity(&self) -> usize {
147        self.capacity.get()
148    }
149}
150
151/// Moves `key` to the front of `order` if it is present. No-op otherwise.
152fn promote<K: Eq>(order: &mut VecDeque<K>, key: &K) {
153    if let Some(pos) = order.iter().position(|k| k == key) {
154        if let Some(k) = order.remove(pos) {
155            order.push_front(k);
156        }
157    }
158}
cache_mod/lru.rs

cache_mod/
lru.rs
