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
83impl<K: Eq + Hash, V, S> LruCache<K, V, S>
84where
85    S: BuildHasher,
86{
87    #[inline]
88    pub fn contains_key<Q>(&self, key: &Q) -> bool
89    where
90        K: Borrow<Q>,
91        Q: Hash + Eq + ?Sized,
92    {
93        self.map.contains_key(key)
94    }
95
96    /// Insert a new value into the `LruCache`.
97    ///
98    /// If necessary, will remove the value at the front of the LRU list to make room.
99    #[inline]
100    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
101        let old_val = self.map.insert(k, v);
102        if self.len() > self.capacity() {
103            self.remove_lru();
104        }
105        old_val
106    }
107
108    /// Get the value for the given key, *without* marking the value as recently used and moving it
109    /// to the back of the LRU list.
110    #[inline]
111    pub fn peek<Q>(&self, k: &Q) -> Option<&V>
112    where
113        K: Borrow<Q>,
114        Q: Hash + Eq + ?Sized,
115    {
116        self.map.get(k)
117    }
118
119    /// Get the value for the given key mutably, *without* marking the value as recently used and
120    /// moving it to the back of the LRU list.
121    #[inline]
122    pub fn peek_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
123    where
124        K: Borrow<Q>,
125        Q: Hash + Eq + ?Sized,
126    {
127        self.map.get_mut(k)
128    }
129
130    /// Retrieve the given key, marking it as recently used and moving it to the back of the LRU
131    /// list.
132    #[inline]
133    pub fn get<Q>(&mut self, k: &Q) -> Option<&V>
134    where
135        K: Borrow<Q>,
136        Q: Hash + Eq + ?Sized,
137    {
138        self.get_mut(k).map(|v| &*v)
139    }
140
141    /// Retrieve the given key, marking it as recently used and moving it to the back of the LRU
142    /// list.
143    #[inline]
144    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
145    where
146        K: Borrow<Q>,
147        Q: Hash + Eq + ?Sized,
148    {
149        match self.map.raw_entry_mut().from_key(k) {
150            linked_hash_map::RawEntryMut::Occupied(mut occupied) => {
151                occupied.to_back();
152                Some(occupied.into_mut())
153            }
154            linked_hash_map::RawEntryMut::Vacant(_) => None,
155        }
156    }
157
158    /// If the returned entry is vacant, it will always have room to insert a single value.  By
159    /// using the entry API, you can exceed the configured capacity by 1.
160    ///
161    /// The returned entry is not automatically moved to the back of the LRU list.  By calling
162    /// `Entry::to_back` / `Entry::to_front` you can manually control the position of this entry in
163    /// the LRU list.
164    #[inline]
165    pub fn entry(&mut self, key: K) -> Entry<'_, K, V, S> {
166        if self.len() > self.capacity() {
167            self.remove_lru();
168        }
169        self.map.entry(key)
170    }
171
172    /// The constructed raw entry is never automatically moved to the back of the LRU list.  By
173    /// calling `Entry::to_back` / `Entry::to_front` you can manually control the position of this
174    /// entry in the LRU list.
175    #[inline]
176    pub fn raw_entry(&self) -> RawEntryBuilder<'_, K, V, S> {
177        self.map.raw_entry()
178    }
179
180    /// If the constructed raw entry is vacant, it will always have room to insert a single value.
181    /// By using the raw entry API, you can exceed the configured capacity by 1.
182    ///
183    /// The constructed raw entry is never automatically moved to the back of the LRU list.  By
184    /// calling `Entry::to_back` / `Entry::to_front` you can manually control the position of this
185    /// entry in the LRU list.
186    #[inline]
187    pub fn raw_entry_mut(&mut self) -> RawEntryBuilderMut<'_, K, V, S> {
188        if self.len() > self.capacity() {
189            self.remove_lru();
190        }
191        self.map.raw_entry_mut()
192    }
193
194    #[inline]
195    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
196    where
197        K: Borrow<Q>,
198        Q: Hash + Eq + ?Sized,
199    {
200        self.map.remove(k)
201    }
202
203    #[inline]
204    pub fn remove_entry<Q>(&mut self, k: &Q) -> Option<(K, V)>
205    where
206        K: Borrow<Q>,
207        Q: Hash + Eq + ?Sized,
208    {
209        self.map.remove_entry(k)
210    }
211
212    /// Set the new cache capacity for the `LruCache`.
213    ///
214    /// If there are more entries in the `LruCache` than the new capacity will allow, they are
215    /// removed.
216    #[inline]
217    pub fn set_capacity(&mut self, capacity: usize) {
218        for _ in capacity..self.len() {
219            self.remove_lru();
220        }
221        self.max_size = capacity;
222    }
223
224    /// Remove the least recently used entry and return it.
225    ///
226    /// If the `LruCache` is empty this will return None.
227    #[inline]
228    pub fn remove_lru(&mut self) -> Option<(K, V)> {
229        self.map.pop_front()
230    }
231}
232
233impl<K: Hash + Eq + Clone, V: Clone, S: BuildHasher + Clone> Clone for LruCache<K, V, S> {
234    #[inline]
235    fn clone(&self) -> Self {
236        LruCache {
237            map: self.map.clone(),
238            max_size: self.max_size,
239        }
240    }
241}
242
243impl<K: Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for LruCache<K, V, S> {
244    #[inline]
245    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
246        for (k, v) in iter {
247            self.insert(k, v);
248        }
249    }
250}
251
252impl<K, V, S> IntoIterator for LruCache<K, V, S> {
253    type Item = (K, V);
254    type IntoIter = IntoIter<K, V>;
255
256    #[inline]
257    fn into_iter(self) -> IntoIter<K, V> {
258        self.map.into_iter()
259    }
260}
261
262impl<'a, K, V, S> IntoIterator for &'a LruCache<K, V, S> {
263    type Item = (&'a K, &'a V);
264    type IntoIter = Iter<'a, K, V>;
265
266    #[inline]
267    fn into_iter(self) -> Iter<'a, K, V> {
268        self.iter()
269    }
270}
271
272impl<'a, K, V, S> IntoIterator for &'a mut LruCache<K, V, S> {
273    type Item = (&'a K, &'a mut V);
274    type IntoIter = IterMut<'a, K, V>;
275
276    #[inline]
277    fn into_iter(self) -> IterMut<'a, K, V> {
278        self.iter_mut()
279    }
280}
281
282impl<K, V, S> fmt::Debug for LruCache<K, V, S>
283where
284    K: fmt::Debug,
285    V: fmt::Debug,
286{
287    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
288        f.debug_map().entries(self.iter().rev()).finish()
289    }
290}
hashlink/lru_cache.rs

hashlink/
lru_cache.rs
