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

cache_mod/
lru.rs
