hashlink/
lru_cache.rs

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

hashlink/
lru_cache.rs
