hashlink/
lru_cache.rs

1use core::{
2    borrow::Borrow,
3    fmt,
4    hash::{BuildHasher, Hash},
5};
6
7use crate::linked_hash_map::{self, LinkedHashMap};
8use crate::DefaultHashBuilder;
9
10pub use crate::linked_hash_map::{
11    Drain, Entry, IntoIter, Iter, IterMut, OccupiedEntry, RawEntryBuilder, RawEntryBuilderMut,
12    RawOccupiedEntryMut, RawVacantEntryMut, VacantEntry,
13};
14
15pub struct LruCache<K, V, S = DefaultHashBuilder> {
16    map: LinkedHashMap<K, V, S>,
17    max_size: usize,
18}
19
20impl<K: Eq + Hash, V> LruCache<K, V> {
21    #[inline]
22    pub fn new(capacity: usize) -> Self {
23        LruCache {
24            map: LinkedHashMap::new(),
25            max_size: capacity,
26        }
27    }
28
29    /// Create a new unbounded `LruCache` that does not automatically evict entries.
30    ///
31    /// A simple convenience method that is equivalent to `LruCache::new(usize::MAX)`
32    #[inline]
33    pub fn new_unbounded() -> Self {
34        LruCache::new(usize::MAX)
35    }
36}
37
38impl<K, V, S> LruCache<K, V, S> {
39    #[inline]
40    pub fn with_hasher(capacity: usize, hash_builder: S) -> Self {
41        LruCache {
42            map: LinkedHashMap::with_hasher(hash_builder),
43            max_size: capacity,
44        }
45    }
46
47    #[inline]
48    pub fn capacity(&self) -> usize {
49        self.max_size
50    }
51
52    #[inline]
53    pub fn len(&self) -> usize {
54        self.map.len()
55    }
56
57    #[inline]
58    pub fn is_empty(&self) -> bool {
59        self.map.is_empty()
60    }
61
62    #[inline]
63    pub fn clear(&mut self) {
64        self.map.clear();
65    }
66
67    #[inline]
68    pub fn iter(&self) -> Iter<'_, K, V> {
69        self.map.iter()
70    }
71
72    #[inline]
73    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
74        self.map.iter_mut()
75    }
76
77    #[inline]
78    pub fn drain(&mut self) -> Drain<'_, K, V> {
79        self.map.drain()
80    }
81
82    #[inline]
83    pub fn retain<F>(&mut self, f: F)
84    where
85        F: FnMut(&K, &mut V) -> bool,
86    {
87        self.map.retain(f);
88    }
89}
90
91impl<K: Eq + Hash, V, S> LruCache<K, V, S>
92where
93    S: BuildHasher,
94{
95    #[inline]
96    pub fn contains_key<Q>(&self, key: &Q) -> bool
97    where
98        K: Borrow<Q>,
99        Q: Hash + Eq + ?Sized,
100    {
101        self.map.contains_key(key)
102    }
103
104    /// Insert a new value into the `LruCache`.
105    ///
106    /// If necessary, will remove the value at the front of the LRU list to make room.
107    #[inline]
108    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
109        let old_val = self.map.insert(k, v);
110        if self.len() > self.capacity() {
111            self.remove_lru();
112        }
113        old_val
114    }
115
116    /// Get the value for the given key, *without* marking the value as recently used and moving it
117    /// to the back of the LRU list.
118    #[inline]
119    pub fn peek<Q>(&self, k: &Q) -> Option<&V>
120    where
121        K: Borrow<Q>,
122        Q: Hash + Eq + ?Sized,
123    {
124        self.map.get(k)
125    }
126
127    /// Get the value for the given key mutably, *without* marking the value as recently used and
128    /// moving it to the back of the LRU list.
129    #[inline]
130    pub fn peek_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
131    where
132        K: Borrow<Q>,
133        Q: Hash + Eq + ?Sized,
134    {
135        self.map.get_mut(k)
136    }
137
138    /// Retrieve the given key, marking it as recently used and moving it to the back of the LRU
139    /// list.
140    #[inline]
141    pub fn get<Q>(&mut self, k: &Q) -> Option<&V>
142    where
143        K: Borrow<Q>,
144        Q: Hash + Eq + ?Sized,
145    {
146        self.get_mut(k).map(|v| &*v)
147    }
148
149    /// Retrieve the given key, marking it as recently used and moving it to the back of the LRU
150    /// list.
151    #[inline]
152    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
153    where
154        K: Borrow<Q>,
155        Q: Hash + Eq + ?Sized,
156    {
157        match self.map.raw_entry_mut().from_key(k) {
158            linked_hash_map::RawEntryMut::Occupied(mut occupied) => {
159                occupied.to_back();
160                Some(occupied.into_mut())
161            }
162            linked_hash_map::RawEntryMut::Vacant(_) => None,
163        }
164    }
165
166    /// If the returned entry is vacant, it will always have room to insert a single value.  By
167    /// using the entry API, you can exceed the configured capacity by 1.
168    ///
169    /// The returned entry is not automatically moved to the back of the LRU list.  By calling
170    /// `Entry::to_back` / `Entry::to_front` you can manually control the position of this entry in
171    /// the LRU list.
172    #[inline]
173    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
174        if self.len() > self.capacity() {
175            self.remove_lru();
176        }
177        self.map.entry(key)
178    }
179
180    /// The constructed raw entry is never automatically moved to the back of the LRU list.  By
181    /// calling `Entry::to_back` / `Entry::to_front` you can manually control the position of this
182    /// entry in the LRU list.
183    #[inline]
184    pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
185        self.map.raw_entry()
186    }
187
188    /// If the constructed raw entry is vacant, it will always have room to insert a single value.
189    /// By using the raw entry API, you can exceed the configured capacity by 1.
190    ///
191    /// The constructed raw entry is never automatically moved to the back of the LRU list.  By
192    /// calling `Entry::to_back` / `Entry::to_front` you can manually control the position of this
193    /// entry in the LRU list.
194    #[inline]
195    pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
196        if self.len() > self.capacity() {
197            self.remove_lru();
198        }
199        self.map.raw_entry_mut()
200    }
201
202    #[inline]
203    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
204    where
205        K: Borrow<Q>,
206        Q: Hash + Eq + ?Sized,
207    {
208        self.map.remove(k)
209    }
210
211    #[inline]
212    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
213    where
214        K: Borrow<Q>,
215        Q: Hash + Eq + ?Sized,
216    {
217        self.map.remove_entry(k)
218    }
219
220    /// Set the new cache capacity for the `LruCache`.
221    ///
222    /// If there are more entries in the `LruCache` than the new capacity will allow, they are
223    /// removed.
224    #[inline]
225    pub fn set_capacity(&mut self, capacity: usize) {
226        for _ in capacity..self.len() {
227            self.remove_lru();
228        }
229        self.max_size = capacity;
230    }
231
232    /// Remove the least recently used entry and return it.
233    ///
234    /// If the `LruCache` is empty this will return None.
235    #[inline]
236    pub fn remove_lru(&mut self) -> Option<(K, V)> {
237        self.map.pop_front()
238    }
239}
240
241impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LruCache<K, V, S> {
242    #[inline]
243    fn clone(&self) -> Self {
244        LruCache {
245            map: self.map.clone(),
246            max_size: self.max_size,
247        }
248    }
249}
250
251impl<K: Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for LruCache<K, V, S> {
252    #[inline]
253    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
254        for (k, v) in iter {
255            self.insert(k, v);
256        }
257    }
258}
259
260impl<K, V, S> IntoIterator for LruCache<K, V, S> {
261    type Item = (K, V);
262    type IntoIter = IntoIter<K, V>;
263
264    #[inline]
265    fn into_iter(self) -> IntoIter<K, V> {
266        self.map.into_iter()
267    }
268}
269
270impl<'a, K, V, S> IntoIterator for &'a LruCache<K, V, S> {
271    type Item = (&'a K, &'a V);
272    type IntoIter = Iter<'a, K, V>;
273
274    #[inline]
275    fn into_iter(self) -> Iter<'a, K, V> {
276        self.iter()
277    }
278}
279
280impl<'a, K, V, S> IntoIterator for &'a mut LruCache<K, V, S> {
281    type Item = (&'a K, &'a mut V);
282    type IntoIter = IterMut<'a, K, V>;
283
284    #[inline]
285    fn into_iter(self) -> IterMut<'a, K, V> {
286        self.iter_mut()
287    }
288}
289
290impl<K, V, S> fmt::Debug for LruCache<K, V, S>
291where
292    K: fmt::Debug,
293    V: fmt::Debug,
294{
295    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
296        f.debug_map().entries(self.iter().rev()).finish()
297    }
298}
hashlink/lru_cache.rs

hashlink/
lru_cache.rs
