1 | //! Another LRU cache implementation in rust. |
2 | //! It has two main characteristics that differentiates it from other implementation: |
3 | //! |
4 | //! 1. It is backed by a [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html): it |
5 | //! offers a O(1) time complexity (amortized average) for any operation that requires to lookup an entry from |
6 | //! a key. |
7 | //! |
8 | //! 2. It is a weighted cache: each key-value pair has a weight and the capacity serves as both as: |
9 | //! * a limit to the number of elements |
10 | //! * and as a limit to the total weight of its elements |
11 | //! |
12 | //! using the following formula: |
13 | //! |
14 | //! [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`] |
15 | //! |
16 | //! Even though most operations don't depend on the number of elements in the cache, |
17 | //! [`CLruCache::put_with_weight`] has a special behavior: because it needs to make room |
18 | //! for the new element, it will remove enough least recently used elements. In the worst |
19 | //! case, that will require to fully empty the cache. Additionally, if the weight of the |
20 | //! new element is too big, the insertion can fail. |
21 | //! |
22 | //! For the common case of an LRU cache whose elements don't have a weight, a default |
23 | //! [`ZeroWeightScale`] is provided and unlocks some useful APIs like: |
24 | //! |
25 | //! * [`CLruCache::put`]: an infallible insertion that will remove a maximum of 1 element. |
26 | //! * [`CLruCache::put_or_modify`]: a conditional insertion or modification flow similar |
27 | //! to the entry API of [`HashMap`]. |
28 | //! * [`CLruCache::try_put_or_modify`]: fallible version of [`CLruCache::put_or_modify`]. |
29 | //! * All APIs that allow to retrieve a mutable reference to a value (e.g.: [`CLruCache::get_mut`]). |
30 | //! |
31 | //! The cache requires the keys to be clonable because it will store 2 instances |
32 | //! of each key in different internal data structures. If cloning a key can be |
33 | //! expensive, you might want to consider using an [`std::rc::Rc`] or an [`std::sync::Arc`]. |
34 | //! |
35 | //! ## Examples |
36 | //! |
37 | //! ### Using the default [`ZeroWeightScale`]: |
38 | //! |
39 | //! ```rust |
40 | //! |
41 | //! use std::num::NonZeroUsize; |
42 | //! use clru::CLruCache; |
43 | //! |
44 | //! let mut cache = CLruCache::new(NonZeroUsize::new(2).unwrap()); |
45 | //! cache.put("apple" .to_string(), 3); |
46 | //! cache.put("banana" .to_string(), 2); |
47 | //! |
48 | //! assert_eq!(cache.get("apple" ), Some(&3)); |
49 | //! assert_eq!(cache.get("banana" ), Some(&2)); |
50 | //! assert!(cache.get("pear" ).is_none()); |
51 | //! |
52 | //! assert_eq!(cache.put("banana" .to_string(), 4), Some(2)); |
53 | //! assert_eq!(cache.put("pear" .to_string(), 5), None); |
54 | //! |
55 | //! assert_eq!(cache.get("pear" ), Some(&5)); |
56 | //! assert_eq!(cache.get("banana" ), Some(&4)); |
57 | //! assert!(cache.get("apple" ).is_none()); |
58 | //! |
59 | //! { |
60 | //! let v = cache.get_mut("banana" ).unwrap(); |
61 | //! *v = 6; |
62 | //! } |
63 | //! |
64 | //! assert_eq!(cache.get("banana" ), Some(&6)); |
65 | //! ``` |
66 | //! |
67 | //! ### Using a custom [`WeightScale`] implementation: |
68 | //! |
69 | //! ```rust |
70 | //! |
71 | //! use std::num::NonZeroUsize; |
72 | //! use clru::{CLruCache, CLruCacheConfig, WeightScale}; |
73 | //! |
74 | //! struct CustomScale; |
75 | //! |
76 | //! impl WeightScale<String, &str> for CustomScale { |
77 | //! fn weight(&self, _key: &String, value: &&str) -> usize { |
78 | //! value.len() |
79 | //! } |
80 | //! } |
81 | //! |
82 | //! let mut cache = CLruCache::with_config( |
83 | //! CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(CustomScale), |
84 | //! ); |
85 | //! |
86 | //! assert_eq!(cache.put_with_weight("apple" .to_string(), "red" ).unwrap(), None); |
87 | //! assert_eq!( |
88 | //! cache.put_with_weight("apple" .to_string(), "green" ).unwrap(), |
89 | //! Some("red" ) |
90 | //! ); |
91 | //! |
92 | //! assert_eq!(cache.len(), 1); |
93 | //! assert_eq!(cache.get("apple" ), Some(&"green" )); |
94 | //! ``` |
95 | |
96 | #![deny (missing_docs)] |
97 | #![deny (unsafe_code)] |
98 | #![deny (warnings)] |
99 | |
100 | mod config; |
101 | mod list; |
102 | mod weight; |
103 | |
104 | pub use crate::config::*; |
105 | use crate::list::{FixedSizeList, FixedSizeListIter, FixedSizeListIterMut}; |
106 | pub use crate::weight::*; |
107 | |
108 | use std::borrow::Borrow; |
109 | use std::collections::hash_map::Entry; |
110 | use std::collections::hash_map::RandomState; |
111 | use std::collections::HashMap; |
112 | use std::hash::{BuildHasher, Hash}; |
113 | use std::iter::FromIterator; |
114 | use std::num::NonZeroUsize; |
115 | |
116 | #[derive (Debug)] |
117 | struct CLruNode<K, V> { |
118 | key: K, |
119 | value: V, |
120 | } |
121 | |
122 | /// A weighted LRU cache with mostly¹ constant time operations. |
123 | /// |
124 | /// Each key-value pair in the cache can have a weight that is retrieved |
125 | /// using the provided [`WeightScale`] implementation. The default scale is |
126 | /// [`ZeroWeightScale`] and always return 0. The number of elements that |
127 | /// can be stored in the cache is conditioned by the sum of [`CLruCache::len`] |
128 | /// and [`CLruCache::weight`]: |
129 | /// |
130 | /// [`CLruCache::len`] + [`CLruCache::weight`] <= [`CLruCache::capacity`] |
131 | /// |
132 | /// Using the default [`ZeroWeightScale`] scale unlocks some useful APIs |
133 | /// that can currently only be implemented for this scale. The most interesting |
134 | /// ones are probably: |
135 | /// |
136 | /// * [`CLruCache::put`] |
137 | /// * [`CLruCache::put_or_modify`] |
138 | /// * [`CLruCache::try_put_or_modify`] |
139 | /// |
140 | /// But more generally, using [`ZeroWeightScale`] unlocks all methods that return |
141 | /// a mutable reference to the value of an element. |
142 | /// This is because modifying the value of an element can lead to a modification |
143 | /// of its weight and therefore would put the cache into an incoherent state. |
144 | /// For the same reason, it is a logic error for a value to change weight while |
145 | /// being stored in the cache. |
146 | /// |
147 | /// The cache requires the keys to be clonable because it will store 2 instances |
148 | /// of each key in different internal data structures. If cloning a key can be |
149 | /// expensive, you might want to consider using an `Rc` or an `Arc`. |
150 | /// |
151 | /// Note 1: See [`CLruCache::put_with_weight`] |
152 | #[derive (Debug)] |
153 | pub struct CLruCache<K, V, S = RandomState, W: WeightScale<K, V> = ZeroWeightScale> { |
154 | lookup: HashMap<K, usize, S>, |
155 | storage: FixedSizeList<CLruNode<K, V>>, |
156 | scale: W, |
157 | weight: usize, |
158 | } |
159 | |
160 | impl<K: Eq + Hash, V> CLruCache<K, V> { |
161 | /// Creates a new LRU cache that holds at most `capacity` elements. |
162 | pub fn new(capacity: NonZeroUsize) -> Self { |
163 | Self { |
164 | lookup: HashMap::new(), |
165 | storage: FixedSizeList::new(capacity.get()), |
166 | scale: ZeroWeightScale, |
167 | weight: 0, |
168 | } |
169 | } |
170 | |
171 | /// Creates a new LRU cache that holds at most `capacity` elements |
172 | /// and pre-allocates memory in order to hold at least `reserve` elements |
173 | /// without reallocating. |
174 | pub fn with_memory(capacity: NonZeroUsize, mut reserve: usize) -> Self { |
175 | if reserve > capacity.get() { |
176 | reserve = capacity.get(); |
177 | } |
178 | Self { |
179 | lookup: HashMap::with_capacity(reserve), |
180 | storage: FixedSizeList::with_memory(capacity.get(), reserve), |
181 | scale: ZeroWeightScale, |
182 | weight: 0, |
183 | } |
184 | } |
185 | } |
186 | |
187 | impl<K: Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> { |
188 | /// Creates a new LRU cache that holds at most `capacity` elements |
189 | /// and uses the provided hash builder to hash keys. |
190 | pub fn with_hasher(capacity: NonZeroUsize, hash_builder: S) -> CLruCache<K, V, S> { |
191 | Self { |
192 | lookup: HashMap::with_hasher(hash_builder), |
193 | storage: FixedSizeList::new(capacity:capacity.get()), |
194 | scale: ZeroWeightScale, |
195 | weight: 0, |
196 | } |
197 | } |
198 | } |
199 | |
200 | impl<K: Eq + Hash, V, W: WeightScale<K, V>> CLruCache<K, V, RandomState, W> { |
201 | /// Creates a new LRU cache that holds at most `capacity` elements |
202 | /// and uses the provided scale to retrieve value's weight. |
203 | pub fn with_scale(capacity: NonZeroUsize, scale: W) -> CLruCache<K, V, RandomState, W> { |
204 | Self { |
205 | lookup: HashMap::with_hasher(hash_builder:RandomState::default()), |
206 | storage: FixedSizeList::new(capacity:capacity.get()), |
207 | scale, |
208 | weight: 0, |
209 | } |
210 | } |
211 | } |
212 | |
213 | impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> CLruCache<K, V, S, W> { |
214 | /// Creates a new LRU cache using the provided configuration. |
215 | pub fn with_config(config: CLruCacheConfig<K, V, S, W>) -> Self { |
216 | let CLruCacheConfig { |
217 | capacity, |
218 | hash_builder, |
219 | reserve, |
220 | scale, |
221 | .. |
222 | } = config; |
223 | Self { |
224 | lookup: HashMap::with_hasher(hash_builder), |
225 | storage: if let Some(reserve) = reserve { |
226 | FixedSizeList::with_memory(capacity.get(), reserve) |
227 | } else { |
228 | FixedSizeList::new(capacity.get()) |
229 | }, |
230 | scale, |
231 | weight: 0, |
232 | } |
233 | } |
234 | |
235 | /// Returns the number of key-value pairs that are currently in the cache. |
236 | #[inline ] |
237 | pub fn len(&self) -> usize { |
238 | debug_assert_eq!(self.lookup.len(), self.storage.len()); |
239 | self.storage.len() |
240 | } |
241 | |
242 | /// Returns the capacity of the cache. It serves as a limit for |
243 | /// * the number of elements that the cache can hold. |
244 | /// * the total weight of the elements in the cache. |
245 | #[inline ] |
246 | pub fn capacity(&self) -> usize { |
247 | self.storage.capacity() |
248 | } |
249 | |
250 | /// Returns the total weight of the elements in the cache. |
251 | #[inline ] |
252 | pub fn weight(&self) -> usize { |
253 | self.weight |
254 | } |
255 | |
256 | /// Returns a bool indicating whether the cache is empty or not. |
257 | #[inline ] |
258 | pub fn is_empty(&self) -> bool { |
259 | debug_assert_eq!(self.lookup.is_empty(), self.storage.is_empty()); |
260 | self.storage.is_empty() |
261 | } |
262 | |
263 | /// Returns a bool indicating whether the cache is full or not. |
264 | #[inline ] |
265 | pub fn is_full(&self) -> bool { |
266 | self.len() + self.weight() == self.capacity() |
267 | } |
268 | |
269 | /// Returns the value corresponding to the most recently used item or `None` if the cache is empty. |
270 | /// Like `peek`, `front` does not update the LRU list so the item's position will be unchanged. |
271 | pub fn front(&self) -> Option<(&K, &V)> { |
272 | self.storage |
273 | .front() |
274 | .map(|CLruNode { key, value }| (key, value)) |
275 | } |
276 | |
277 | /// Returns the value corresponding to the least recently used item or `None` if the cache is empty. |
278 | /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged. |
279 | pub fn back(&self) -> Option<(&K, &V)> { |
280 | self.storage |
281 | .back() |
282 | .map(|CLruNode { key, value }| (key, value)) |
283 | } |
284 | |
285 | /// Puts a key-value pair into cache taking it's weight into account. |
286 | /// If the weight of the new element is greater than what the cache can hold, |
287 | /// it returns the provided key-value pair as an error. |
288 | /// Otherwise, it removes enough elements for the new element to be inserted, |
289 | /// thus making it a non constant time operation. |
290 | /// If the key already exists in the cache, then it updates the key's value and returns the old value. |
291 | /// Otherwise, `None` is returned. |
292 | pub fn put_with_weight(&mut self, key: K, value: V) -> Result<Option<V>, (K, V)> { |
293 | let weight = self.scale.weight(&key, &value); |
294 | if weight >= self.capacity() { |
295 | return Err((key, value)); |
296 | } |
297 | match self.lookup.entry(key) { |
298 | Entry::Occupied(mut occ) => { |
299 | // TODO: store keys in the cache itself for reuse. |
300 | let mut keys = Vec::new(); |
301 | let old = self.storage.remove(*occ.get()).unwrap(); |
302 | self.weight -= self.scale.weight(&old.key, &old.value); |
303 | while self.storage.len() + self.weight + weight >= self.storage.capacity() { |
304 | let node = self.storage.pop_back().unwrap(); |
305 | self.weight -= self.scale.weight(&node.key, &node.value); |
306 | keys.push(node.key); |
307 | } |
308 | // It's fine to unwrap here because: |
309 | // * the cache capacity is non zero |
310 | // * the cache cannot be full |
311 | let (idx, _) = self |
312 | .storage |
313 | .push_front(CLruNode { |
314 | key: occ.key().clone(), |
315 | value, |
316 | }) |
317 | .unwrap(); |
318 | occ.insert(idx); |
319 | self.weight += weight; |
320 | for key in keys.drain(..) { |
321 | self.lookup.remove(&key); |
322 | } |
323 | Ok(Some(old.value)) |
324 | } |
325 | Entry::Vacant(vac) => { |
326 | let mut keys = Vec::new(); |
327 | while self.storage.len() + self.weight + weight >= self.storage.capacity() { |
328 | let node = self.storage.pop_back().unwrap(); |
329 | self.weight -= self.scale.weight(&node.key, &node.value); |
330 | keys.push(node.key); |
331 | } |
332 | // It's fine to unwrap here because: |
333 | // * the cache capacity is non zero |
334 | // * the cache cannot be full |
335 | let (idx, _) = self |
336 | .storage |
337 | .push_front(CLruNode { |
338 | key: vac.key().clone(), |
339 | value, |
340 | }) |
341 | .unwrap(); |
342 | vac.insert(idx); |
343 | self.weight += weight; |
344 | for key in keys.drain(..) { |
345 | self.lookup.remove(&key); |
346 | } |
347 | Ok(None) |
348 | } |
349 | } |
350 | } |
351 | |
352 | /// Returns a reference to the value of the key in the cache or `None` if it is not present in the cache. |
353 | /// Moves the key to the head of the LRU list if it exists. |
354 | pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&V> |
355 | where |
356 | K: Borrow<Q>, |
357 | Q: Hash + Eq, |
358 | { |
359 | let idx = *self.lookup.get(key)?; |
360 | self.storage.move_front(idx).map(|node| &node.value) |
361 | } |
362 | |
363 | /// Removes and returns the value corresponding to the key from the cache or `None` if it does not exist. |
364 | pub fn pop<Q: ?Sized>(&mut self, key: &Q) -> Option<V> |
365 | where |
366 | K: Borrow<Q>, |
367 | Q: Hash + Eq, |
368 | { |
369 | let idx = self.lookup.remove(key)?; |
370 | self.storage.remove(idx).map(|CLruNode { key, value, .. }| { |
371 | self.weight -= self.scale.weight(&key, &value); |
372 | value |
373 | }) |
374 | } |
375 | |
376 | /// Removes and returns the key and value corresponding to the most recently used item or `None` if the cache is empty. |
377 | pub fn pop_front(&mut self) -> Option<(K, V)> { |
378 | if let Some(CLruNode { key, value }) = self.storage.pop_front() { |
379 | self.lookup.remove(&key).unwrap(); |
380 | self.weight -= self.scale.weight(&key, &value); |
381 | Some((key, value)) |
382 | } else { |
383 | None |
384 | } |
385 | } |
386 | |
387 | /// Removes and returns the key and value corresponding to the least recently used item or `None` if the cache is empty. |
388 | pub fn pop_back(&mut self) -> Option<(K, V)> { |
389 | if let Some(CLruNode { key, value }) = self.storage.pop_back() { |
390 | self.lookup.remove(&key).unwrap(); |
391 | self.weight -= self.scale.weight(&key, &value); |
392 | Some((key, value)) |
393 | } else { |
394 | None |
395 | } |
396 | } |
397 | |
398 | /// Returns a reference to the value corresponding to the key in the cache or `None` if it is not present in the cache. |
399 | /// Unlike `get`, `peek` does not update the LRU list so the key's position will be unchanged. |
400 | pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V> |
401 | where |
402 | K: Borrow<Q>, |
403 | Q: Hash + Eq, |
404 | { |
405 | let idx = *self.lookup.get(key)?; |
406 | self.storage.get(idx).map(|node| &node.value) |
407 | } |
408 | |
409 | /// Returns a bool indicating whether the given key is in the cache. |
410 | /// Does not update the LRU list. |
411 | pub fn contains<Q: ?Sized>(&mut self, key: &Q) -> bool |
412 | where |
413 | K: Borrow<Q>, |
414 | Q: Hash + Eq, |
415 | { |
416 | self.peek(key).is_some() |
417 | } |
418 | |
419 | /// Clears the contents of the cache. |
420 | #[inline ] |
421 | pub fn clear(&mut self) { |
422 | self.lookup.clear(); |
423 | self.storage.clear(); |
424 | self.weight = 0; |
425 | } |
426 | |
427 | /// Resizes the cache. |
428 | /// If the new capacity is smaller than the size of the current cache any entries past the new capacity are discarded. |
429 | pub fn resize(&mut self, capacity: NonZeroUsize) { |
430 | while capacity.get() < self.storage.len() + self.weight() { |
431 | if let Some(CLruNode { key, value }) = self.storage.pop_back() { |
432 | self.lookup.remove(&key).unwrap(); |
433 | self.weight -= self.scale.weight(&key, &value); |
434 | } |
435 | } |
436 | self.storage.resize(capacity.get()); |
437 | for i in 0..self.len() { |
438 | let data = self.storage.get(i).unwrap(); |
439 | *self.lookup.get_mut(&data.key).unwrap() = i; |
440 | } |
441 | } |
442 | |
443 | /// Retains only the elements specified by the predicate. |
444 | /// In other words, remove all pairs `(k, v)` such that `f(&k, &v)` returns `false`. |
445 | pub fn retain<F>(&mut self, mut f: F) |
446 | where |
447 | F: FnMut(&K, &V) -> bool, |
448 | { |
449 | self.storage.retain( |
450 | #[inline ] |
451 | |CLruNode { ref key, ref value }| { |
452 | if f(key, value) { |
453 | true |
454 | } else { |
455 | self.lookup.remove(key).unwrap(); |
456 | false |
457 | } |
458 | }, |
459 | ) |
460 | } |
461 | } |
462 | |
463 | impl<K, V, S, W: WeightScale<K, V>> CLruCache<K, V, S, W> { |
464 | /// Returns an iterator visiting all entries in order. |
465 | /// The iterator element type is `(&'a K, &'a V)`. |
466 | pub fn iter(&self) -> CLruCacheIter<'_, K, V> { |
467 | CLruCacheIter { |
468 | iter: self.storage.iter(), |
469 | } |
470 | } |
471 | } |
472 | |
473 | impl<K: Clone + Eq + Hash, V, S: BuildHasher> CLruCache<K, V, S> { |
474 | /// Puts a key-value pair into cache. |
475 | /// If the key already exists in the cache, then it updates the key's value and returns the old value. |
476 | /// Otherwise, `None` is returned. |
477 | pub fn put(&mut self, key: K, value: V) -> Option<V> { |
478 | match self.lookup.entry(key) { |
479 | Entry::Occupied(occ) => { |
480 | // It's fine to unwrap here because: |
481 | // * the entry already exists |
482 | let node = self.storage.move_front(*occ.get()).unwrap(); |
483 | Some(std::mem::replace(&mut node.value, value)) |
484 | } |
485 | Entry::Vacant(vac) => { |
486 | let key = vac.key().clone(); |
487 | if self.storage.is_full() { |
488 | let idx = self.storage.back_idx(); |
489 | // It's fine to unwrap here because: |
490 | // * the cache capacity is non zero |
491 | // * the cache is full |
492 | let node = self.storage.move_front(idx).unwrap(); |
493 | let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key; |
494 | vac.insert(idx); |
495 | self.lookup.remove(&obsolete_key); |
496 | } else { |
497 | // It's fine to unwrap here because: |
498 | // * the cache capacity is non zero |
499 | // * the cache is not full |
500 | let (idx, _) = self.storage.push_front(CLruNode { key, value }).unwrap(); |
501 | vac.insert(idx); |
502 | } |
503 | None |
504 | } |
505 | } |
506 | } |
507 | |
508 | /// Puts a new key-value pair or modify an already existing value. |
509 | /// If the key already exists in the cache, then `modify_op` supplied function is called. |
510 | /// Otherwise, `put_op` supplied function is called. |
511 | /// Returns a mutable reference to the value. |
512 | /// |
513 | /// The additional `data` argument can be used to pass extra information |
514 | /// to the supplied functions. This can useful when both functions need |
515 | /// to access the same variable. |
516 | pub fn put_or_modify<T, P: FnMut(&K, T) -> V, M: FnMut(&K, &mut V, T)>( |
517 | &mut self, |
518 | key: K, |
519 | mut put_op: P, |
520 | mut modify_op: M, |
521 | data: T, |
522 | ) -> &mut V { |
523 | match self.lookup.entry(key) { |
524 | Entry::Occupied(occ) => { |
525 | // It's fine to unwrap here because: |
526 | // * the entry already exists |
527 | let node = self.storage.move_front(*occ.get()).unwrap(); |
528 | modify_op(&node.key, &mut node.value, data); |
529 | &mut node.value |
530 | } |
531 | Entry::Vacant(vac) => { |
532 | let key = vac.key().clone(); |
533 | let value = put_op(&key, data); |
534 | if self.storage.is_full() { |
535 | let index = self.storage.back_idx(); |
536 | // It's fine to unwrap here because: |
537 | // * the cache capacity is non zero |
538 | // * the cache is full |
539 | let node = self.storage.move_front(index).unwrap(); |
540 | let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key; |
541 | vac.insert(index); |
542 | self.lookup.remove(&obsolete_key); |
543 | &mut node.value |
544 | } else { |
545 | // It's fine to unwrap here because: |
546 | // * the cache capacity is non zero |
547 | // * the cache cannot be full |
548 | let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap(); |
549 | vac.insert(idx); |
550 | &mut node.value |
551 | } |
552 | } |
553 | } |
554 | } |
555 | |
556 | /// Puts a new key-value pair or modify an already existing value. |
557 | /// If the key already exists in the cache, then `modify_op` supplied function is called. |
558 | /// Otherwise, `put_op` supplied function is called. |
559 | /// Returns a mutable reference to the value or an error. |
560 | /// |
561 | /// The additional `data` argument can be used to pass extra information |
562 | /// to the supplied functions. This can useful when both functions need |
563 | /// to access the same variable. |
564 | /// |
565 | /// This is the fallible version of [`CLruCache::put_or_modify`]. |
566 | pub fn try_put_or_modify< |
567 | T, |
568 | E, |
569 | P: FnMut(&K, T) -> Result<V, E>, |
570 | M: FnMut(&K, &mut V, T) -> Result<(), E>, |
571 | >( |
572 | &mut self, |
573 | key: K, |
574 | mut put_op: P, |
575 | mut modify_op: M, |
576 | data: T, |
577 | ) -> Result<&mut V, E> { |
578 | match self.lookup.entry(key) { |
579 | Entry::Occupied(occ) => { |
580 | // It's fine to unwrap here because: |
581 | // * the entry already exists |
582 | let node = self.storage.move_front(*occ.get()).unwrap(); |
583 | match modify_op(&node.key, &mut node.value, data) { |
584 | Ok(()) => Ok(&mut node.value), |
585 | Err(err) => Err(err), |
586 | } |
587 | } |
588 | Entry::Vacant(vac) => { |
589 | let value = match put_op(vac.key(), data) { |
590 | Ok(value) => value, |
591 | Err(err) => return Err(err), |
592 | }; |
593 | let key = vac.key().clone(); |
594 | if self.storage.is_full() { |
595 | let idx = self.storage.back_idx(); |
596 | // It's fine to unwrap here because: |
597 | // * the cache capacity is non zero |
598 | // * the cache is full |
599 | let node = self.storage.move_front(idx).unwrap(); |
600 | let obsolete_key = std::mem::replace(node, CLruNode { key, value }).key; |
601 | vac.insert(idx); |
602 | self.lookup.remove(&obsolete_key); |
603 | Ok(&mut node.value) |
604 | } else { |
605 | // It's fine to unwrap here because: |
606 | // * the cache capacity is non zero |
607 | // * the cache cannot be full |
608 | let (idx, node) = self.storage.push_front(CLruNode { key, value }).unwrap(); |
609 | vac.insert(idx); |
610 | Ok(&mut node.value) |
611 | } |
612 | } |
613 | } |
614 | } |
615 | |
616 | /// Returns the value corresponding to the most recently used item or `None` if the cache is empty. |
617 | /// Like `peek`, `font` does not update the LRU list so the item's position will be unchanged. |
618 | pub fn front_mut(&mut self) -> Option<(&K, &mut V)> { |
619 | self.storage |
620 | .front_mut() |
621 | .map(|CLruNode { key, value }| (&*key, value)) |
622 | } |
623 | |
624 | /// Returns the value corresponding to the least recently used item or `None` if the cache is empty. |
625 | /// Like `peek`, `back` does not update the LRU list so the item's position will be unchanged. |
626 | pub fn back_mut(&mut self) -> Option<(&K, &mut V)> { |
627 | self.storage |
628 | .back_mut() |
629 | .map(|CLruNode { key, value }| (&*key, value)) |
630 | } |
631 | |
632 | /// Returns a mutable reference to the value of the key in the cache or `None` if it is not present in the cache. |
633 | /// Moves the key to the head of the LRU list if it exists. |
634 | pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
635 | where |
636 | K: Borrow<Q>, |
637 | Q: Hash + Eq, |
638 | { |
639 | let idx = *self.lookup.get(key)?; |
640 | self.storage.move_front(idx).map(|node| &mut node.value) |
641 | } |
642 | |
643 | /// Returns a mutable reference to the value corresponding to the key in the cache or `None` if it is not present in the cache. |
644 | /// Unlike `get_mut`, `peek_mut` does not update the LRU list so the key's position will be unchanged. |
645 | pub fn peek_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> |
646 | where |
647 | K: Borrow<Q>, |
648 | Q: Hash + Eq, |
649 | { |
650 | let idx = *self.lookup.get(key)?; |
651 | self.storage.get_mut(idx).map(|node| &mut node.value) |
652 | } |
653 | |
654 | /// Retains only the elements specified by the predicate. |
655 | /// In other words, remove all pairs `(k, v)` such that `f(&k, &mut v)` returns `false`. |
656 | pub fn retain_mut<F>(&mut self, mut f: F) |
657 | where |
658 | F: FnMut(&K, &mut V) -> bool, |
659 | { |
660 | self.storage.retain_mut( |
661 | #[inline ] |
662 | |CLruNode { |
663 | ref key, |
664 | ref mut value, |
665 | }| { |
666 | if f(key, value) { |
667 | true |
668 | } else { |
669 | self.lookup.remove(key).unwrap(); |
670 | false |
671 | } |
672 | }, |
673 | ) |
674 | } |
675 | } |
676 | |
677 | impl<K, V, S> CLruCache<K, V, S> { |
678 | /// Returns an iterator visiting all entries in order, giving a mutable reference on V. |
679 | /// The iterator element type is `(&'a K, &'a mut V)`. |
680 | pub fn iter_mut(&mut self) -> CLruCacheIterMut<'_, K, V> { |
681 | CLruCacheIterMut { |
682 | iter: self.storage.iter_mut(), |
683 | } |
684 | } |
685 | } |
686 | |
687 | /// An iterator over the entries of a `CLruCache`. |
688 | /// |
689 | /// This `struct` is created by the [`iter`] method on [`CLruCache`][`CLruCache`]. |
690 | /// See its documentation for more. |
691 | /// |
692 | /// [`iter`]: struct.CLruCache.html#method.iter |
693 | /// [`CLruCache`]: struct.CLruCache.html |
694 | #[derive (Clone, Debug)] |
695 | pub struct CLruCacheIter<'a, K, V> { |
696 | iter: FixedSizeListIter<'a, CLruNode<K, V>>, |
697 | } |
698 | |
699 | impl<'a, K, V> Iterator for CLruCacheIter<'a, K, V> { |
700 | type Item = (&'a K, &'a V); |
701 | |
702 | fn next(&mut self) -> Option<Self::Item> { |
703 | self.iter |
704 | .next() |
705 | .map(|(_, CLruNode { key: &K, value: &V })| (key.borrow(), value)) |
706 | } |
707 | |
708 | fn size_hint(&self) -> (usize, Option<usize>) { |
709 | self.iter.size_hint() |
710 | } |
711 | } |
712 | |
713 | impl<'a, K, V> DoubleEndedIterator for CLruCacheIter<'a, K, V> { |
714 | fn next_back(&mut self) -> Option<Self::Item> { |
715 | self.iter |
716 | .next_back() |
717 | .map(|(_, CLruNode { key: &K, value: &V })| (key.borrow(), value)) |
718 | } |
719 | } |
720 | |
721 | impl<'a, K, V> ExactSizeIterator for CLruCacheIter<'a, K, V> { |
722 | fn len(&self) -> usize { |
723 | self.iter.len() |
724 | } |
725 | } |
726 | |
727 | impl<'a, K, V, S, W: WeightScale<K, V>> IntoIterator for &'a CLruCache<K, V, S, W> { |
728 | type Item = (&'a K, &'a V); |
729 | type IntoIter = CLruCacheIter<'a, K, V>; |
730 | |
731 | #[inline ] |
732 | fn into_iter(self) -> CLruCacheIter<'a, K, V> { |
733 | self.iter() |
734 | } |
735 | } |
736 | |
737 | /// An iterator over mutables entries of a `CLruCache`. |
738 | /// |
739 | /// This `struct` is created by the [`iter_mut`] method on [`CLruCache`][`CLruCache`]. |
740 | /// See its documentation for more. |
741 | /// |
742 | /// [`iter_mut`]: struct.CLruCache.html#method.iter_mut |
743 | /// [`CLruCache`]: struct.CLruCache.html |
744 | pub struct CLruCacheIterMut<'a, K, V> { |
745 | iter: FixedSizeListIterMut<'a, CLruNode<K, V>>, |
746 | } |
747 | |
748 | impl<'a, K, V> Iterator for CLruCacheIterMut<'a, K, V> { |
749 | type Item = (&'a K, &'a mut V); |
750 | |
751 | fn next(&mut self) -> Option<Self::Item> { |
752 | self.iter |
753 | .next() |
754 | .map(|(_, CLruNode { key: &mut K, value: &mut V })| (&*key, value)) |
755 | } |
756 | |
757 | fn size_hint(&self) -> (usize, Option<usize>) { |
758 | self.iter.size_hint() |
759 | } |
760 | } |
761 | |
762 | impl<'a, K, V> DoubleEndedIterator for CLruCacheIterMut<'a, K, V> { |
763 | fn next_back(&mut self) -> Option<Self::Item> { |
764 | self.iter |
765 | .next_back() |
766 | .map(|(_, CLruNode { key: &mut K, value: &mut V })| (&*key, value)) |
767 | } |
768 | } |
769 | |
770 | impl<'a, K, V> ExactSizeIterator for CLruCacheIterMut<'a, K, V> { |
771 | fn len(&self) -> usize { |
772 | self.iter.len() |
773 | } |
774 | } |
775 | |
776 | impl<'a, K, V, S> IntoIterator for &'a mut CLruCache<K, V, S> { |
777 | type Item = (&'a K, &'a mut V); |
778 | type IntoIter = CLruCacheIterMut<'a, K, V>; |
779 | |
780 | #[inline ] |
781 | fn into_iter(self) -> CLruCacheIterMut<'a, K, V> { |
782 | self.iter_mut() |
783 | } |
784 | } |
785 | |
786 | /// An owning iterator over the elements of a `CLruCache`. |
787 | /// |
788 | /// This `struct` is created by the [`into_iter`] method on [`CLruCache`] |
789 | /// (provided by the `IntoIterator` trait). See its documentation for more. |
790 | /// |
791 | /// [`into_iter`]: struct.CLruCache.html#method.into_iter |
792 | pub struct CLruCacheIntoIter<K, V, S, W: WeightScale<K, V>> { |
793 | cache: CLruCache<K, V, S, W>, |
794 | } |
795 | |
796 | impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> Iterator |
797 | for CLruCacheIntoIter<K, V, S, W> |
798 | { |
799 | type Item = (K, V); |
800 | |
801 | #[inline ] |
802 | fn next(&mut self) -> Option<(K, V)> { |
803 | self.cache.pop_front() |
804 | } |
805 | |
806 | #[inline ] |
807 | fn size_hint(&self) -> (usize, Option<usize>) { |
808 | (self.cache.len(), Some(self.cache.len())) |
809 | } |
810 | } |
811 | |
812 | impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> DoubleEndedIterator |
813 | for CLruCacheIntoIter<K, V, S, W> |
814 | { |
815 | fn next_back(&mut self) -> Option<Self::Item> { |
816 | self.cache.pop_back() |
817 | } |
818 | } |
819 | |
820 | impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> ExactSizeIterator |
821 | for CLruCacheIntoIter<K, V, S, W> |
822 | { |
823 | fn len(&self) -> usize { |
824 | self.size_hint().0 |
825 | } |
826 | } |
827 | |
828 | impl<K: Clone + Eq + Hash, V, S: BuildHasher, W: WeightScale<K, V>> IntoIterator |
829 | for CLruCache<K, V, S, W> |
830 | { |
831 | type Item = (K, V); |
832 | type IntoIter = CLruCacheIntoIter<K, V, S, W>; |
833 | |
834 | /// Consumes the cache into an iterator yielding elements by value. |
835 | #[inline ] |
836 | fn into_iter(self) -> CLruCacheIntoIter<K, V, S, W> { |
837 | CLruCacheIntoIter { cache: self } |
838 | } |
839 | } |
840 | |
841 | impl<K: Clone + Eq + Hash, V, S: BuildHasher + Default> FromIterator<(K, V)> |
842 | for CLruCache<K, V, S> |
843 | { |
844 | fn from_iter<I: IntoIterator<Item = (K, V)>>(iter: I) -> Self { |
845 | let cap: NonZero = NonZeroUsize::new(usize::MAX).unwrap(); |
846 | let mut cache: CLruCache = CLruCache::with_hasher(capacity:cap, S::default()); |
847 | |
848 | for (k: K, v: V) in iter { |
849 | cache.put(key:k, value:v); |
850 | } |
851 | |
852 | cache.resize( |
853 | capacity:NonZeroUsize::new(cache.len()).unwrap_or_else(|| NonZeroUsize::new(1).unwrap()), |
854 | ); |
855 | |
856 | cache |
857 | } |
858 | } |
859 | |
860 | impl<K: Clone + Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for CLruCache<K, V, S> { |
861 | fn extend<T: IntoIterator<Item = (K, V)>>(&mut self, iter: T) { |
862 | for (k: K, v: V) in iter { |
863 | self.put(key:k, value:v); |
864 | } |
865 | } |
866 | } |
867 | |
868 | #[cfg (test)] |
869 | #[allow (clippy::bool_assert_comparison)] |
870 | mod tests { |
871 | use super::*; |
872 | |
873 | #[allow (unsafe_code)] |
874 | const ONE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(1) }; |
875 | #[allow (unsafe_code)] |
876 | const TWO: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(2) }; |
877 | #[allow (unsafe_code)] |
878 | const THREE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(3) }; |
879 | #[allow (unsafe_code)] |
880 | const FOUR: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(4) }; |
881 | #[allow (unsafe_code)] |
882 | const FIVE: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(5) }; |
883 | #[allow (unsafe_code)] |
884 | const SIX: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(6) }; |
885 | #[allow (unsafe_code)] |
886 | const HEIGHT: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(8) }; |
887 | #[allow (unsafe_code)] |
888 | const MANY: NonZeroUsize = unsafe { NonZeroUsize::new_unchecked(200) }; |
889 | |
890 | #[test ] |
891 | fn test_insert_and_get() { |
892 | let mut cache = CLruCache::new(TWO); |
893 | assert!(cache.is_empty()); |
894 | |
895 | assert_eq!(cache.put("apple" , "red" ), None); |
896 | assert_eq!(cache.put("banana" , "yellow" ), None); |
897 | |
898 | assert_eq!(cache.capacity(), 2); |
899 | assert_eq!(cache.len(), 2); |
900 | assert!(!cache.is_empty()); |
901 | assert!(cache.is_full()); |
902 | assert_eq!(cache.get(&"apple" ), Some(&"red" )); |
903 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
904 | } |
905 | |
906 | #[test ] |
907 | fn test_insert_and_get_mut() { |
908 | let mut cache = CLruCache::new(TWO); |
909 | |
910 | cache.put("apple" , "red" ); |
911 | cache.put("banana" , "yellow" ); |
912 | |
913 | assert_eq!(cache.capacity(), 2); |
914 | assert_eq!(cache.len(), 2); |
915 | assert!(!cache.is_empty()); |
916 | assert!(cache.is_full()); |
917 | assert_eq!(cache.get_mut(&"apple" ), Some(&mut "red" )); |
918 | assert_eq!(cache.get_mut(&"banana" ), Some(&mut "yellow" )); |
919 | } |
920 | |
921 | #[test ] |
922 | fn test_get_mut_and_update() { |
923 | let mut cache = CLruCache::new(TWO); |
924 | |
925 | cache.put("apple" , 1); |
926 | cache.put("banana" , 3); |
927 | |
928 | { |
929 | let v = cache.get_mut(&"apple" ).unwrap(); |
930 | *v = 4; |
931 | } |
932 | |
933 | assert_eq!(cache.capacity(), 2); |
934 | assert_eq!(cache.len(), 2); |
935 | assert!(!cache.is_empty()); |
936 | assert!(cache.is_full()); |
937 | assert_eq!(cache.get_mut(&"apple" ), Some(&mut 4)); |
938 | assert_eq!(cache.get_mut(&"banana" ), Some(&mut 3)); |
939 | } |
940 | |
941 | #[test ] |
942 | fn test_insert_update() { |
943 | let mut cache = CLruCache::new(ONE); |
944 | |
945 | assert_eq!(cache.put("apple" , "red" ), None); |
946 | assert_eq!(cache.put("apple" , "green" ), Some("red" )); |
947 | |
948 | assert_eq!(cache.len(), 1); |
949 | assert_eq!(cache.get(&"apple" ), Some(&"green" )); |
950 | } |
951 | |
952 | #[test ] |
953 | fn test_insert_removes_oldest() { |
954 | let mut cache = CLruCache::new(TWO); |
955 | |
956 | assert_eq!(cache.put("apple" , "red" ), None); |
957 | assert_eq!(cache.put("banana" , "yellow" ), None); |
958 | assert_eq!(cache.put("pear" , "green" ), None); |
959 | |
960 | assert!(cache.get(&"apple" ).is_none()); |
961 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
962 | assert_eq!(cache.get(&"pear" ), Some(&"green" )); |
963 | |
964 | // Even though we inserted "apple" into the cache earlier it has since been removed from |
965 | // the cache so there is no current value for `insert` to return. |
966 | assert_eq!(cache.put("apple" , "green" ), None); |
967 | assert_eq!(cache.put("tomato" , "red" ), None); |
968 | |
969 | assert!(cache.get(&"pear" ).is_none()); |
970 | assert_eq!(cache.get(&"apple" ), Some(&"green" )); |
971 | assert_eq!(cache.get(&"tomato" ), Some(&"red" )); |
972 | } |
973 | |
974 | #[test ] |
975 | fn test_peek() { |
976 | let mut cache = CLruCache::new(TWO); |
977 | |
978 | cache.put("apple" , "red" ); |
979 | cache.put("banana" , "yellow" ); |
980 | |
981 | assert_eq!(cache.peek(&"banana" ), Some(&"yellow" )); |
982 | assert_eq!(cache.peek(&"apple" ), Some(&"red" )); |
983 | |
984 | cache.put("pear" , "green" ); |
985 | |
986 | assert!(cache.peek(&"apple" ).is_none()); |
987 | assert_eq!(cache.peek(&"banana" ), Some(&"yellow" )); |
988 | assert_eq!(cache.peek(&"pear" ), Some(&"green" )); |
989 | } |
990 | |
991 | #[test ] |
992 | fn test_peek_mut() { |
993 | let mut cache = CLruCache::new(TWO); |
994 | |
995 | cache.put("apple" , "red" ); |
996 | cache.put("banana" , "yellow" ); |
997 | |
998 | assert_eq!(cache.peek_mut(&"banana" ), Some(&mut "yellow" )); |
999 | assert_eq!(cache.peek_mut(&"apple" ), Some(&mut "red" )); |
1000 | assert!(cache.peek_mut(&"pear" ).is_none()); |
1001 | |
1002 | cache.put("pear" , "green" ); |
1003 | |
1004 | assert!(cache.peek_mut(&"apple" ).is_none()); |
1005 | assert_eq!(cache.peek_mut(&"banana" ), Some(&mut "yellow" )); |
1006 | assert_eq!(cache.peek_mut(&"pear" ), Some(&mut "green" )); |
1007 | |
1008 | { |
1009 | let v = cache.peek_mut(&"banana" ).unwrap(); |
1010 | *v = "green" ; |
1011 | } |
1012 | |
1013 | assert_eq!(cache.peek_mut(&"banana" ), Some(&mut "green" )); |
1014 | } |
1015 | |
1016 | #[test ] |
1017 | fn test_contains() { |
1018 | let mut cache = CLruCache::new(TWO); |
1019 | |
1020 | cache.put("apple" , "red" ); |
1021 | cache.put("banana" , "yellow" ); |
1022 | cache.put("pear" , "green" ); |
1023 | |
1024 | assert!(!cache.contains(&"apple" )); |
1025 | assert!(cache.contains(&"banana" )); |
1026 | assert!(cache.contains(&"pear" )); |
1027 | } |
1028 | |
1029 | #[test ] |
1030 | fn test_pop() { |
1031 | let mut cache = CLruCache::new(TWO); |
1032 | |
1033 | cache.put("apple" , "red" ); |
1034 | cache.put("banana" , "yellow" ); |
1035 | |
1036 | assert_eq!(cache.len(), 2); |
1037 | assert_eq!(cache.get(&"apple" ), Some(&"red" )); |
1038 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1039 | |
1040 | let popped = cache.pop(&"apple" ); |
1041 | assert!(popped.is_some()); |
1042 | assert_eq!(popped.unwrap(), "red" ); |
1043 | assert_eq!(cache.len(), 1); |
1044 | assert!(cache.get(&"apple" ).is_none()); |
1045 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1046 | } |
1047 | |
1048 | #[test ] |
1049 | fn test_pop_front() { |
1050 | let mut cache = CLruCache::new(MANY); |
1051 | |
1052 | for i in 0..75 { |
1053 | cache.put(i, "A" ); |
1054 | } |
1055 | for i in 0..75 { |
1056 | cache.put(i + 100, "B" ); |
1057 | } |
1058 | for i in 0..75 { |
1059 | cache.put(i + 200, "C" ); |
1060 | } |
1061 | assert_eq!(cache.len(), 200); |
1062 | |
1063 | for i in 0..75 { |
1064 | assert_eq!(cache.get(&(74 - i + 100)), Some(&"B" )); |
1065 | } |
1066 | assert_eq!(cache.get(&25), Some(&"A" )); |
1067 | |
1068 | assert_eq!(cache.pop_front(), Some((25, "A" ))); |
1069 | for i in 0..75 { |
1070 | assert_eq!(cache.pop_front(), Some((i + 100, "B" ))); |
1071 | } |
1072 | for i in 0..75 { |
1073 | assert_eq!(cache.pop_front(), Some((74 - i + 200, "C" ))); |
1074 | } |
1075 | for i in 0..49 { |
1076 | assert_eq!(cache.pop_front(), Some((74 - i, "A" ))); |
1077 | } |
1078 | for _ in 0..50 { |
1079 | assert_eq!(cache.pop_front(), None); |
1080 | } |
1081 | } |
1082 | |
1083 | #[test ] |
1084 | fn test_pop_back() { |
1085 | let mut cache = CLruCache::new(MANY); |
1086 | |
1087 | for i in 0..75 { |
1088 | cache.put(i, "A" ); |
1089 | } |
1090 | for i in 0..75 { |
1091 | cache.put(i + 100, "B" ); |
1092 | } |
1093 | for i in 0..75 { |
1094 | cache.put(i + 200, "C" ); |
1095 | } |
1096 | assert_eq!(cache.len(), 200); |
1097 | |
1098 | for i in 0..75 { |
1099 | assert_eq!(cache.get(&(74 - i + 100)), Some(&"B" )); |
1100 | } |
1101 | assert_eq!(cache.get(&25), Some(&"A" )); |
1102 | |
1103 | for i in 26..75 { |
1104 | assert_eq!(cache.pop_back(), Some((i, "A" ))); |
1105 | } |
1106 | for i in 0..75 { |
1107 | assert_eq!(cache.pop_back(), Some((i + 200, "C" ))); |
1108 | } |
1109 | for i in 0..75 { |
1110 | assert_eq!(cache.pop_back(), Some((74 - i + 100, "B" ))); |
1111 | } |
1112 | assert_eq!(cache.pop_back(), Some((25, "A" ))); |
1113 | for _ in 0..50 { |
1114 | assert_eq!(cache.pop_back(), None); |
1115 | } |
1116 | } |
1117 | |
1118 | #[test ] |
1119 | fn test_clear() { |
1120 | let mut cache = CLruCache::new(TWO); |
1121 | |
1122 | cache.put("apple" , "red" ); |
1123 | cache.put("banana" , "yellow" ); |
1124 | |
1125 | assert_eq!(cache.len(), 2); |
1126 | assert_eq!(cache.get(&"apple" ), Some(&"red" )); |
1127 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1128 | |
1129 | cache.clear(); |
1130 | assert_eq!(cache.len(), 0); |
1131 | } |
1132 | |
1133 | #[test ] |
1134 | fn test_resize_larger() { |
1135 | let mut cache = CLruCache::new(TWO); |
1136 | |
1137 | cache.put(1, "a" ); |
1138 | cache.put(2, "b" ); |
1139 | |
1140 | cache.resize(THREE); |
1141 | |
1142 | assert_eq!(cache.len(), 2); |
1143 | assert_eq!(cache.capacity(), 3); |
1144 | |
1145 | cache.resize(FOUR); |
1146 | |
1147 | assert_eq!(cache.len(), 2); |
1148 | assert_eq!(cache.capacity(), 4); |
1149 | |
1150 | cache.put(3, "c" ); |
1151 | cache.put(4, "d" ); |
1152 | |
1153 | assert_eq!(cache.len(), 4); |
1154 | assert_eq!(cache.capacity(), 4); |
1155 | assert_eq!(cache.get(&1), Some(&"a" )); |
1156 | assert_eq!(cache.get(&2), Some(&"b" )); |
1157 | assert_eq!(cache.get(&3), Some(&"c" )); |
1158 | assert_eq!(cache.get(&4), Some(&"d" )); |
1159 | } |
1160 | |
1161 | #[test ] |
1162 | fn test_resize_smaller() { |
1163 | let mut cache = CLruCache::new(FOUR); |
1164 | |
1165 | cache.put(1, "a" ); |
1166 | cache.put(2, "b" ); |
1167 | cache.put(3, "c" ); |
1168 | cache.put(4, "d" ); |
1169 | |
1170 | cache.resize(TWO); |
1171 | |
1172 | assert_eq!(cache.len(), 2); |
1173 | assert_eq!(cache.capacity(), 2); |
1174 | assert!(cache.get(&1).is_none()); |
1175 | assert!(cache.get(&2).is_none()); |
1176 | assert_eq!(cache.get(&3), Some(&"c" )); |
1177 | assert_eq!(cache.get(&4), Some(&"d" )); |
1178 | } |
1179 | |
1180 | #[test ] |
1181 | fn test_resize_equal() { |
1182 | let mut cache = CLruCache::new(FOUR); |
1183 | |
1184 | cache.put(1, "a" ); |
1185 | cache.put(2, "b" ); |
1186 | cache.put(3, "c" ); |
1187 | cache.put(4, "d" ); |
1188 | |
1189 | cache.resize(FOUR); |
1190 | |
1191 | assert_eq!(cache.len(), 4); |
1192 | assert_eq!(cache.capacity(), 4); |
1193 | assert_eq!(cache.get(&1), Some(&"a" )); |
1194 | assert_eq!(cache.get(&2), Some(&"b" )); |
1195 | assert_eq!(cache.get(&3), Some(&"c" )); |
1196 | assert_eq!(cache.get(&4), Some(&"d" )); |
1197 | } |
1198 | |
1199 | #[test ] |
1200 | fn test_iter_forwards() { |
1201 | let mut cache = CLruCache::new(THREE); |
1202 | cache.put("a" , 1); |
1203 | cache.put("b" , 2); |
1204 | cache.put("c" , 3); |
1205 | |
1206 | { |
1207 | // iter const |
1208 | let mut iter = cache.iter(); |
1209 | assert_eq!(iter.len(), 3); |
1210 | assert_eq!(iter.next(), Some((&"c" , &3))); |
1211 | |
1212 | assert_eq!(iter.len(), 2); |
1213 | assert_eq!(iter.next(), Some((&"b" , &2))); |
1214 | |
1215 | assert_eq!(iter.len(), 1); |
1216 | assert_eq!(iter.next(), Some((&"a" , &1))); |
1217 | |
1218 | assert_eq!(iter.len(), 0); |
1219 | assert_eq!(iter.next(), None); |
1220 | } |
1221 | { |
1222 | // iter mut |
1223 | let mut iter = cache.iter_mut(); |
1224 | assert_eq!(iter.len(), 3); |
1225 | assert_eq!(iter.next(), Some((&"c" , &mut 3))); |
1226 | |
1227 | assert_eq!(iter.len(), 2); |
1228 | assert_eq!(iter.next(), Some((&"b" , &mut 2))); |
1229 | |
1230 | assert_eq!(iter.len(), 1); |
1231 | assert_eq!(iter.next(), Some((&"a" , &mut 1))); |
1232 | |
1233 | assert_eq!(iter.len(), 0); |
1234 | assert_eq!(iter.next(), None); |
1235 | |
1236 | let mut vec: Vec<_> = cache.iter_mut().collect(); |
1237 | vec.iter_mut().for_each(|(_, v)| { |
1238 | **v -= 1; |
1239 | }); |
1240 | assert_eq!(vec, vec![(&"c" , &mut 2), (&"b" , &mut 1), (&"a" , &mut 0)]); |
1241 | } |
1242 | } |
1243 | |
1244 | #[test ] |
1245 | fn test_iter_backwards() { |
1246 | let mut cache = CLruCache::new(THREE); |
1247 | cache.put("a" , 1); |
1248 | cache.put("b" , 2); |
1249 | cache.put("c" , 3); |
1250 | |
1251 | { |
1252 | // iter const |
1253 | let mut iter = cache.iter(); |
1254 | assert_eq!(iter.len(), 3); |
1255 | assert_eq!(iter.next_back(), Some((&"a" , &1))); |
1256 | |
1257 | assert_eq!(iter.len(), 2); |
1258 | assert_eq!(iter.next_back(), Some((&"b" , &2))); |
1259 | |
1260 | assert_eq!(iter.len(), 1); |
1261 | assert_eq!(iter.next_back(), Some((&"c" , &3))); |
1262 | |
1263 | assert_eq!(iter.len(), 0); |
1264 | assert_eq!(iter.next_back(), None); |
1265 | } |
1266 | |
1267 | { |
1268 | // iter mut |
1269 | let mut iter = cache.iter_mut(); |
1270 | assert_eq!(iter.len(), 3); |
1271 | assert_eq!(iter.next_back(), Some((&"a" , &mut 1))); |
1272 | |
1273 | assert_eq!(iter.len(), 2); |
1274 | assert_eq!(iter.next_back(), Some((&"b" , &mut 2))); |
1275 | |
1276 | assert_eq!(iter.len(), 1); |
1277 | assert_eq!(iter.next_back(), Some((&"c" , &mut 3))); |
1278 | |
1279 | assert_eq!(iter.len(), 0); |
1280 | assert_eq!(iter.next_back(), None); |
1281 | |
1282 | let mut vec: Vec<_> = cache.iter_mut().rev().collect(); |
1283 | vec.iter_mut().for_each(|(_, v)| { |
1284 | **v -= 1; |
1285 | }); |
1286 | assert_eq!(vec, vec![(&"a" , &mut 0), (&"b" , &mut 1), (&"c" , &mut 2)]); |
1287 | } |
1288 | } |
1289 | |
1290 | #[test ] |
1291 | fn test_iter_forwards_and_backwards() { |
1292 | let mut cache = CLruCache::new(THREE); |
1293 | cache.put("a" , 1); |
1294 | cache.put("b" , 2); |
1295 | cache.put("c" , 3); |
1296 | |
1297 | { |
1298 | // iter const |
1299 | let mut iter = cache.iter(); |
1300 | assert_eq!(iter.len(), 3); |
1301 | assert_eq!(iter.next(), Some((&"c" , &3))); |
1302 | |
1303 | assert_eq!(iter.len(), 2); |
1304 | assert_eq!(iter.next_back(), Some((&"a" , &1))); |
1305 | |
1306 | assert_eq!(iter.len(), 1); |
1307 | assert_eq!(iter.next(), Some((&"b" , &2))); |
1308 | |
1309 | assert_eq!(iter.len(), 0); |
1310 | assert_eq!(iter.next_back(), None); |
1311 | } |
1312 | { |
1313 | // iter mut |
1314 | let mut iter = cache.iter_mut(); |
1315 | assert_eq!(iter.len(), 3); |
1316 | assert_eq!(iter.next(), Some((&"c" , &mut 3))); |
1317 | |
1318 | assert_eq!(iter.len(), 2); |
1319 | assert_eq!(iter.next_back(), Some((&"a" , &mut 1))); |
1320 | |
1321 | assert_eq!(iter.len(), 1); |
1322 | assert_eq!(iter.next(), Some((&"b" , &mut 2))); |
1323 | |
1324 | assert_eq!(iter.len(), 0); |
1325 | assert_eq!(iter.next_back(), None); |
1326 | } |
1327 | } |
1328 | |
1329 | #[test ] |
1330 | fn test_iter_clone() { |
1331 | let mut cache = CLruCache::new(THREE); |
1332 | cache.put("a" , 1); |
1333 | cache.put("b" , 2); |
1334 | |
1335 | let mut iter = cache.iter(); |
1336 | let mut iter_clone = iter.clone(); |
1337 | |
1338 | assert_eq!(iter.len(), 2); |
1339 | assert_eq!(iter.next(), Some((&"b" , &2))); |
1340 | assert_eq!(iter_clone.len(), 2); |
1341 | assert_eq!(iter_clone.next(), Some((&"b" , &2))); |
1342 | |
1343 | assert_eq!(iter.len(), 1); |
1344 | assert_eq!(iter.next(), Some((&"a" , &1))); |
1345 | assert_eq!(iter_clone.len(), 1); |
1346 | assert_eq!(iter_clone.next(), Some((&"a" , &1))); |
1347 | |
1348 | assert_eq!(iter.len(), 0); |
1349 | assert_eq!(iter.next(), None); |
1350 | assert_eq!(iter_clone.len(), 0); |
1351 | assert_eq!(iter_clone.next(), None); |
1352 | } |
1353 | |
1354 | #[test ] |
1355 | fn test_that_pop_actually_detaches_node() { |
1356 | let mut cache = CLruCache::new(FIVE); |
1357 | |
1358 | cache.put("a" , 1); |
1359 | cache.put("b" , 2); |
1360 | cache.put("c" , 3); |
1361 | cache.put("d" , 4); |
1362 | cache.put("e" , 5); |
1363 | |
1364 | assert_eq!(cache.pop(&"c" ), Some(3)); |
1365 | |
1366 | cache.put("f" , 6); |
1367 | |
1368 | let mut iter = cache.iter(); |
1369 | assert_eq!(iter.next(), Some((&"f" , &6))); |
1370 | assert_eq!(iter.next(), Some((&"e" , &5))); |
1371 | assert_eq!(iter.next(), Some((&"d" , &4))); |
1372 | assert_eq!(iter.next(), Some((&"b" , &2))); |
1373 | assert_eq!(iter.next(), Some((&"a" , &1))); |
1374 | assert!(iter.next().is_none()); |
1375 | } |
1376 | |
1377 | #[test ] |
1378 | fn test_get_with_borrow() { |
1379 | let mut cache = CLruCache::new(TWO); |
1380 | |
1381 | let key = String::from("apple" ); |
1382 | cache.put(key, "red" ); |
1383 | |
1384 | assert_eq!(cache.get("apple" ), Some(&"red" )); |
1385 | } |
1386 | |
1387 | #[test ] |
1388 | fn test_get_mut_with_borrow() { |
1389 | let mut cache = CLruCache::new(TWO); |
1390 | |
1391 | let key = String::from("apple" ); |
1392 | cache.put(key, "red" ); |
1393 | |
1394 | assert_eq!(cache.get_mut("apple" ), Some(&mut "red" )); |
1395 | } |
1396 | |
1397 | #[test ] |
1398 | #[cfg_attr (miri, ignore)] |
1399 | fn test_no_memory_leaks() { |
1400 | use std::sync::atomic::{AtomicUsize, Ordering}; |
1401 | |
1402 | static DROP_COUNT: AtomicUsize = AtomicUsize::new(0); |
1403 | |
1404 | struct DropCounter; |
1405 | |
1406 | impl Drop for DropCounter { |
1407 | fn drop(&mut self) { |
1408 | DROP_COUNT.fetch_add(1, Ordering::SeqCst); |
1409 | } |
1410 | } |
1411 | |
1412 | let n = 100; |
1413 | for _ in 0..n { |
1414 | let mut cache = CLruCache::new(ONE); |
1415 | for i in 0..n { |
1416 | cache.put(i, DropCounter {}); |
1417 | } |
1418 | } |
1419 | assert_eq!(DROP_COUNT.load(Ordering::SeqCst), n * n); |
1420 | } |
1421 | |
1422 | #[test ] |
1423 | fn test_retain() { |
1424 | let mut cache = CLruCache::new(FIVE); |
1425 | |
1426 | cache.put("a" , 1); |
1427 | cache.put("b" , 2); |
1428 | cache.put("c" , 3); |
1429 | cache.put("d" , 4); |
1430 | cache.put("e" , 5); |
1431 | |
1432 | assert_eq!(cache.len(), 5); |
1433 | |
1434 | cache.retain_mut(|k, v| match *k { |
1435 | "b" | "d" => false, |
1436 | _ => { |
1437 | *v += 1; |
1438 | true |
1439 | } |
1440 | }); |
1441 | |
1442 | assert_eq!(cache.len(), 3); |
1443 | |
1444 | assert_eq!(cache.get("a" ), Some(&2)); |
1445 | assert_eq!(cache.get("b" ), None); |
1446 | assert_eq!(cache.get("c" ), Some(&4)); |
1447 | assert_eq!(cache.get("d" ), None); |
1448 | assert_eq!(cache.get("e" ), Some(&6)); |
1449 | |
1450 | cache.retain(|_, _| true); |
1451 | |
1452 | assert_eq!(cache.len(), 3); |
1453 | |
1454 | assert_eq!(cache.get("a" ), Some(&2)); |
1455 | assert_eq!(cache.get("b" ), None); |
1456 | assert_eq!(cache.get("c" ), Some(&4)); |
1457 | assert_eq!(cache.get("d" ), None); |
1458 | assert_eq!(cache.get("e" ), Some(&6)); |
1459 | |
1460 | cache.retain(|_, _| false); |
1461 | |
1462 | assert_eq!(cache.len(), 0); |
1463 | |
1464 | assert_eq!(cache.get("a" ), None); |
1465 | assert_eq!(cache.get("b" ), None); |
1466 | assert_eq!(cache.get("c" ), None); |
1467 | assert_eq!(cache.get("d" ), None); |
1468 | assert_eq!(cache.get("e" ), None); |
1469 | } |
1470 | |
1471 | #[test ] |
1472 | fn test_into_iter() { |
1473 | let mut cache = CLruCache::new(FIVE); |
1474 | |
1475 | cache.put("a" , 1); |
1476 | cache.put("b" , 2); |
1477 | cache.put("c" , 3); |
1478 | cache.put("d" , 4); |
1479 | cache.put("e" , 5); |
1480 | |
1481 | let mut vec = Vec::new(); |
1482 | for (k, v) in &cache { |
1483 | vec.push((k, v)); |
1484 | } |
1485 | assert_eq!( |
1486 | vec, |
1487 | vec![(&"e" , &5), (&"d" , &4), (&"c" , &3), (&"b" , &2), (&"a" , &1)] |
1488 | ); |
1489 | |
1490 | let mut vec = Vec::new(); |
1491 | for (k, v) in &mut cache { |
1492 | *v -= 1; |
1493 | vec.push((k, v)); |
1494 | } |
1495 | assert_eq!( |
1496 | vec, |
1497 | vec![ |
1498 | (&"e" , &mut 4), |
1499 | (&"d" , &mut 3), |
1500 | (&"c" , &mut 2), |
1501 | (&"b" , &mut 1), |
1502 | (&"a" , &mut 0) |
1503 | ] |
1504 | ); |
1505 | |
1506 | assert_eq!( |
1507 | cache.into_iter().collect::<Vec<_>>(), |
1508 | vec![("e" , 4), ("d" , 3), ("c" , 2), ("b" , 1), ("a" , 0)] |
1509 | ); |
1510 | } |
1511 | |
1512 | #[test ] |
1513 | fn test_put_or_modify() { |
1514 | let mut cache = CLruCache::new(TWO); |
1515 | |
1516 | let put = |key: &&str, base: Option<usize>| base.unwrap_or(0) + key.len(); |
1517 | |
1518 | let modify = |key: &&str, value: &mut usize, base: Option<usize>| { |
1519 | if key.len() == *value { |
1520 | *value *= 2; |
1521 | } else { |
1522 | *value /= 2; |
1523 | } |
1524 | *value += base.unwrap_or(0); |
1525 | }; |
1526 | |
1527 | assert_eq!(cache.put_or_modify("a" , put, modify, None), &1); |
1528 | assert_eq!(cache.len(), 1); |
1529 | |
1530 | let mut iter = cache.iter(); |
1531 | assert_eq!(iter.next(), Some((&"a" , &1))); |
1532 | assert_eq!(iter.next(), None); |
1533 | |
1534 | assert_eq!(cache.put_or_modify("b" , put, modify, Some(3)), &4); |
1535 | assert_eq!(cache.len(), 2); |
1536 | |
1537 | let mut iter = cache.iter(); |
1538 | assert_eq!(iter.next(), Some((&"b" , &4))); |
1539 | assert_eq!(iter.next(), Some((&"a" , &1))); |
1540 | assert_eq!(iter.next(), None); |
1541 | |
1542 | assert_eq!(cache.put_or_modify("a" , put, modify, None), &2); |
1543 | assert_eq!(cache.len(), 2); |
1544 | |
1545 | let mut iter = cache.iter(); |
1546 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1547 | assert_eq!(iter.next(), Some((&"b" , &4))); |
1548 | assert_eq!(iter.next(), None); |
1549 | |
1550 | assert_eq!(cache.put_or_modify("b" , put, modify, Some(3)), &5); |
1551 | assert_eq!(cache.len(), 2); |
1552 | |
1553 | let mut iter = cache.iter(); |
1554 | assert_eq!(iter.next(), Some((&"b" , &5))); |
1555 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1556 | assert_eq!(iter.next(), None); |
1557 | } |
1558 | |
1559 | #[test ] |
1560 | fn test_panic_in_put_or_modify() { |
1561 | use std::panic::{catch_unwind, AssertUnwindSafe}; |
1562 | |
1563 | let mut cache = CLruCache::new(TWO); |
1564 | |
1565 | let put = |_: &&str, value: usize| value; |
1566 | |
1567 | let modify = |_: &&str, old: &mut usize, new: usize| { |
1568 | panic!("old value: {:?} / new value: {:?}" , old, new); |
1569 | }; |
1570 | |
1571 | assert_eq!(cache.put_or_modify("a" , put, modify, 3), &3); |
1572 | |
1573 | assert_eq!(cache.put_or_modify("b" , put, modify, 5), &5); |
1574 | |
1575 | let mut iter = cache.iter(); |
1576 | assert_eq!(iter.next(), Some((&"b" , &5))); |
1577 | assert_eq!(iter.next(), Some((&"a" , &3))); |
1578 | assert_eq!(iter.next(), None); |
1579 | |
1580 | // A panic in the modify closure will move the |
1581 | // key at the top of the cache. |
1582 | assert!(catch_unwind(AssertUnwindSafe(|| { |
1583 | cache.put_or_modify("a" , put, modify, 7); |
1584 | })) |
1585 | .is_err()); |
1586 | |
1587 | let mut iter = cache.iter(); |
1588 | assert_eq!(iter.next(), Some((&"a" , &3))); |
1589 | assert_eq!(iter.next(), Some((&"b" , &5))); |
1590 | assert_eq!(iter.next(), None); |
1591 | |
1592 | let put = |_: &&str, value: usize| panic!("value: {:?}" , value); |
1593 | |
1594 | // A panic in the put closure won't have any |
1595 | // any impact on the cache. |
1596 | assert!(catch_unwind(AssertUnwindSafe(|| { |
1597 | cache.put_or_modify("c" , put, modify, 7); |
1598 | })) |
1599 | .is_err()); |
1600 | |
1601 | let mut iter = cache.iter(); |
1602 | assert_eq!(iter.next(), Some((&"a" , &3))); |
1603 | assert_eq!(iter.next(), Some((&"b" , &5))); |
1604 | assert_eq!(iter.next(), None); |
1605 | } |
1606 | |
1607 | #[test ] |
1608 | fn test_try_put_or_modify() { |
1609 | let mut cache = CLruCache::new(TWO); |
1610 | |
1611 | let put = |_: &&str, value: usize| { |
1612 | if value % 2 == 0 { |
1613 | Ok(value) |
1614 | } else { |
1615 | Err(value) |
1616 | } |
1617 | }; |
1618 | |
1619 | let modify = |_: &&str, old: &mut usize, new: usize| { |
1620 | if new % 2 == 0 { |
1621 | *old = new; |
1622 | Ok(()) |
1623 | } else { |
1624 | Err(new) |
1625 | } |
1626 | }; |
1627 | |
1628 | assert_eq!(cache.try_put_or_modify("a" , put, modify, 2), Ok(&mut 2)); |
1629 | assert_eq!(cache.len(), 1); |
1630 | |
1631 | let mut iter = cache.iter(); |
1632 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1633 | assert_eq!(iter.next(), None); |
1634 | |
1635 | assert_eq!(cache.try_put_or_modify("b" , put, modify, 4), Ok(&mut 4)); |
1636 | assert_eq!(cache.len(), 2); |
1637 | |
1638 | let mut iter = cache.iter(); |
1639 | assert_eq!(iter.next(), Some((&"b" , &4))); |
1640 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1641 | assert_eq!(iter.next(), None); |
1642 | |
1643 | // An error in the modify closure will move the |
1644 | // key at the top of the cache. |
1645 | assert_eq!(cache.try_put_or_modify("a" , put, modify, 3), Err(3)); |
1646 | assert_eq!(cache.len(), 2); |
1647 | |
1648 | let mut iter = cache.iter(); |
1649 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1650 | assert_eq!(iter.next(), Some((&"b" , &4))); |
1651 | assert_eq!(iter.next(), None); |
1652 | |
1653 | // An error in the put closure won't have any |
1654 | // any impact on the cache. |
1655 | assert_eq!(cache.try_put_or_modify("c" , put, modify, 3), Err(3)); |
1656 | assert_eq!(cache.len(), 2); |
1657 | |
1658 | let mut iter = cache.iter(); |
1659 | assert_eq!(iter.next(), Some((&"a" , &2))); |
1660 | assert_eq!(iter.next(), Some((&"b" , &4))); |
1661 | assert_eq!(iter.next(), None); |
1662 | } |
1663 | |
1664 | #[test ] |
1665 | fn test_from_iterator() { |
1666 | let cache: CLruCache<&'static str, usize> = |
1667 | vec![("a" , 1), ("b" , 2), ("c" , 3), ("d" , 4), ("e" , 5)] |
1668 | .into_iter() |
1669 | .collect(); |
1670 | |
1671 | assert_eq!(cache.len(), 5); |
1672 | assert_eq!(cache.capacity(), 5); |
1673 | assert_eq!(cache.is_full(), true); |
1674 | |
1675 | assert_eq!( |
1676 | cache.into_iter().collect::<Vec<_>>(), |
1677 | vec![("e" , 5), ("d" , 4), ("c" , 3), ("b" , 2), ("a" , 1)] |
1678 | ); |
1679 | |
1680 | let cache: CLruCache<&'static str, usize> = vec![].into_iter().collect(); |
1681 | |
1682 | assert_eq!(cache.len(), 0); |
1683 | assert_eq!(cache.capacity(), 1); |
1684 | assert_eq!(cache.is_full(), false); |
1685 | |
1686 | assert_eq!(cache.into_iter().collect::<Vec<_>>(), vec![]); |
1687 | } |
1688 | |
1689 | #[test ] |
1690 | fn test_extend() { |
1691 | let mut cache = CLruCache::new(FIVE); |
1692 | |
1693 | cache.put("a" , 1); |
1694 | cache.put("b" , 2); |
1695 | |
1696 | assert_eq!(cache.len(), 2); |
1697 | assert_eq!(cache.capacity(), 5); |
1698 | assert_eq!(cache.is_full(), false); |
1699 | |
1700 | cache.extend(vec![("c" , 3), ("d" , 4), ("e" , 5)].into_iter()); |
1701 | |
1702 | assert_eq!(cache.len(), 5); |
1703 | assert_eq!(cache.capacity(), 5); |
1704 | assert_eq!(cache.is_full(), true); |
1705 | |
1706 | assert_eq!( |
1707 | cache.into_iter().collect::<Vec<_>>(), |
1708 | vec![("e" , 5), ("d" , 4), ("c" , 3), ("b" , 2), ("a" , 1)] |
1709 | ); |
1710 | } |
1711 | |
1712 | #[derive (Debug)] |
1713 | struct StrStrScale; |
1714 | |
1715 | impl WeightScale<&str, &str> for StrStrScale { |
1716 | fn weight(&self, _key: &&str, value: &&str) -> usize { |
1717 | value.len() |
1718 | } |
1719 | } |
1720 | |
1721 | #[test ] |
1722 | fn test_weighted_insert_and_get() { |
1723 | let mut cache = CLruCache::with_config( |
1724 | CLruCacheConfig::new(NonZeroUsize::new(11).unwrap()).with_scale(StrStrScale), |
1725 | ); |
1726 | assert!(cache.is_empty()); |
1727 | |
1728 | assert_eq!(cache.put_with_weight("apple" , "red" ).unwrap(), None); |
1729 | assert_eq!(cache.put_with_weight("banana" , "yellow" ).unwrap(), None); |
1730 | |
1731 | assert_eq!(cache.capacity(), 11); |
1732 | assert_eq!(cache.len(), 2); |
1733 | assert_eq!(cache.weight(), 9); |
1734 | assert!(!cache.is_empty()); |
1735 | assert!(cache.is_full()); // because of weight |
1736 | assert_eq!(cache.get(&"apple" ), Some(&"red" )); |
1737 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1738 | } |
1739 | |
1740 | #[test ] |
1741 | fn test_zero_weight_fails() { |
1742 | let mut cache = CLruCache::with_config( |
1743 | CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale), |
1744 | ); |
1745 | |
1746 | assert!(cache.put_with_weight("apple" , "red" ).is_err()); |
1747 | assert!(cache.put_with_weight("apple" , "red" ).is_err()); |
1748 | } |
1749 | |
1750 | #[test ] |
1751 | fn test_greater_than_max_weight_fails() { |
1752 | let mut cache = CLruCache::with_config( |
1753 | CLruCacheConfig::new(NonZeroUsize::new(3).unwrap()).with_scale(StrStrScale), |
1754 | ); |
1755 | |
1756 | assert!(cache.put_with_weight("apple" , "red" ).is_err()); |
1757 | } |
1758 | |
1759 | #[test ] |
1760 | fn test_weighted_insert_update() { |
1761 | let mut cache = CLruCache::with_config( |
1762 | CLruCacheConfig::new(NonZeroUsize::new(6).unwrap()).with_scale(StrStrScale), |
1763 | ); |
1764 | |
1765 | assert_eq!(cache.put_with_weight("apple" , "red" ).unwrap(), None); |
1766 | assert_eq!( |
1767 | cache.put_with_weight("apple" , "green" ).unwrap(), |
1768 | Some("red" ) |
1769 | ); |
1770 | |
1771 | assert_eq!(cache.len(), 1); |
1772 | assert_eq!(cache.get(&"apple" ), Some(&"green" )); |
1773 | } |
1774 | |
1775 | #[test ] |
1776 | fn test_weighted_insert_removes_oldest() { |
1777 | let mut cache = CLruCache::with_config( |
1778 | CLruCacheConfig::new(NonZeroUsize::new(16).unwrap()).with_scale(StrStrScale), |
1779 | ); |
1780 | |
1781 | assert_eq!(cache.put_with_weight("apple" , "red" ).unwrap(), None); |
1782 | assert_eq!(cache.put_with_weight("banana" , "yellow" ).unwrap(), None); |
1783 | assert_eq!(cache.put_with_weight("pear" , "green" ).unwrap(), None); |
1784 | |
1785 | assert!(cache.get(&"apple" ).is_none()); |
1786 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1787 | assert_eq!(cache.get(&"pear" ), Some(&"green" )); |
1788 | assert_eq!(cache.len(), 2); |
1789 | assert_eq!(cache.weight(), 11); |
1790 | assert_eq!(cache.capacity(), 16); |
1791 | assert!(!cache.is_full()); |
1792 | |
1793 | // Even though we inserted "apple" into the cache earlier it has since been removed from |
1794 | // the cache so there is no current value for `insert` to return. |
1795 | assert_eq!(cache.put_with_weight("apple" , "green" ).unwrap(), None); |
1796 | assert_eq!(cache.put_with_weight("tomato" , "red" ).unwrap(), None); |
1797 | |
1798 | assert_eq!(cache.len(), 3); // tomato, apple, pear |
1799 | assert_eq!(cache.weight(), 13); // 3 + 5 + 5 |
1800 | assert_eq!(cache.capacity(), 16); |
1801 | assert!(cache.is_full()); |
1802 | |
1803 | assert_eq!(cache.get(&"pear" ), Some(&"green" )); |
1804 | assert_eq!(cache.get(&"apple" ), Some(&"green" )); |
1805 | assert_eq!(cache.get(&"tomato" ), Some(&"red" )); |
1806 | } |
1807 | |
1808 | #[test ] |
1809 | fn test_weighted_clear() { |
1810 | let mut cache = CLruCache::with_config( |
1811 | CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(StrStrScale), |
1812 | ); |
1813 | |
1814 | assert_eq!(cache.put_with_weight("apple" , "red" ), Ok(None)); |
1815 | assert_eq!(cache.put_with_weight("banana" , "yellow" ), Ok(None)); |
1816 | |
1817 | assert_eq!(cache.len(), 1); |
1818 | assert_eq!(cache.weight(), 6); |
1819 | assert_eq!(cache.get(&"apple" ), None); |
1820 | assert_eq!(cache.get(&"banana" ), Some(&"yellow" )); |
1821 | |
1822 | cache.clear(); |
1823 | assert_eq!(cache.len(), 0); |
1824 | assert_eq!(cache.weight(), 0); |
1825 | } |
1826 | |
1827 | #[derive (Debug)] |
1828 | struct IntStrScale; |
1829 | |
1830 | impl WeightScale<usize, &str> for IntStrScale { |
1831 | fn weight(&self, _key: &usize, value: &&str) -> usize { |
1832 | value.len() |
1833 | } |
1834 | } |
1835 | |
1836 | #[test ] |
1837 | fn test_weighted_resize_larger() { |
1838 | let mut cache = CLruCache::with_config( |
1839 | CLruCacheConfig::new(NonZeroUsize::new(4).unwrap()).with_scale(IntStrScale), |
1840 | ); |
1841 | |
1842 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1843 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1844 | assert_eq!(cache.len(), 2); |
1845 | assert_eq!(cache.weight(), 2); |
1846 | assert_eq!(cache.capacity(), 4); |
1847 | assert!(cache.is_full()); |
1848 | |
1849 | cache.resize(SIX); |
1850 | |
1851 | assert_eq!(cache.len(), 2); |
1852 | assert_eq!(cache.weight(), 2); |
1853 | assert_eq!(cache.capacity(), 6); |
1854 | assert!(!cache.is_full()); |
1855 | |
1856 | cache.resize(HEIGHT); |
1857 | |
1858 | assert_eq!(cache.len(), 2); |
1859 | assert_eq!(cache.weight(), 2); |
1860 | assert_eq!(cache.capacity(), 8); |
1861 | assert!(!cache.is_full()); |
1862 | |
1863 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1864 | assert_eq!(cache.put_with_weight(4, "d" ), Ok(None)); |
1865 | |
1866 | assert_eq!(cache.len(), 4); |
1867 | assert_eq!(cache.weight(), 4); |
1868 | assert_eq!(cache.capacity(), 8); |
1869 | assert!(cache.is_full()); |
1870 | assert_eq!(cache.get(&1), Some(&"a" )); |
1871 | assert_eq!(cache.get(&2), Some(&"b" )); |
1872 | assert_eq!(cache.get(&3), Some(&"c" )); |
1873 | assert_eq!(cache.get(&4), Some(&"d" )); |
1874 | } |
1875 | |
1876 | #[test ] |
1877 | fn test_weighted_resize_smaller() { |
1878 | let mut cache = CLruCache::with_config( |
1879 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
1880 | ); |
1881 | |
1882 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1883 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1884 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1885 | assert_eq!(cache.put_with_weight(4, "d" ), Ok(None)); |
1886 | assert_eq!(cache.len(), 4); |
1887 | assert_eq!(cache.weight(), 4); |
1888 | assert_eq!(cache.capacity(), 8); |
1889 | assert!(cache.is_full()); |
1890 | |
1891 | cache.resize(FOUR); |
1892 | |
1893 | assert_eq!(cache.len(), 2); |
1894 | assert_eq!(cache.weight(), 2); |
1895 | assert_eq!(cache.capacity(), 4); |
1896 | assert!(cache.is_full()); |
1897 | |
1898 | assert!(cache.get(&1).is_none()); |
1899 | assert!(cache.get(&2).is_none()); |
1900 | assert_eq!(cache.get(&3), Some(&"c" )); |
1901 | assert_eq!(cache.get(&4), Some(&"d" )); |
1902 | |
1903 | cache.resize(THREE); |
1904 | |
1905 | assert_eq!(cache.len(), 1); |
1906 | assert_eq!(cache.weight(), 1); |
1907 | assert_eq!(cache.capacity(), 3); |
1908 | assert!(!cache.is_full()); |
1909 | |
1910 | assert_eq!(cache.get(&1), None); |
1911 | assert_eq!(cache.get(&2), None); |
1912 | assert_eq!(cache.get(&3), None); |
1913 | assert_eq!(cache.get(&4), Some(&"d" )); |
1914 | } |
1915 | |
1916 | #[test ] |
1917 | fn test_weighted_resize_equal() { |
1918 | let mut cache = CLruCache::with_config( |
1919 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
1920 | ); |
1921 | |
1922 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1923 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1924 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1925 | assert_eq!(cache.put_with_weight(4, "d" ), Ok(None)); |
1926 | |
1927 | assert_eq!(cache.len(), 4); |
1928 | assert_eq!(cache.weight(), 4); |
1929 | assert_eq!(cache.capacity(), 8); |
1930 | assert!(cache.is_full()); |
1931 | |
1932 | cache.resize(HEIGHT); |
1933 | |
1934 | assert_eq!(cache.len(), 4); |
1935 | assert_eq!(cache.weight(), 4); |
1936 | assert_eq!(cache.capacity(), 8); |
1937 | assert!(cache.is_full()); |
1938 | |
1939 | assert_eq!(cache.get(&1), Some(&"a" )); |
1940 | assert_eq!(cache.get(&2), Some(&"b" )); |
1941 | assert_eq!(cache.get(&3), Some(&"c" )); |
1942 | assert_eq!(cache.get(&4), Some(&"d" )); |
1943 | } |
1944 | |
1945 | #[test ] |
1946 | fn test_weighted_iter() { |
1947 | let mut cache = CLruCache::with_config( |
1948 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
1949 | ); |
1950 | |
1951 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1952 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1953 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1954 | assert_eq!(cache.put_with_weight(4, "d" ), Ok(None)); |
1955 | |
1956 | assert_eq!(cache.len(), 4); |
1957 | assert_eq!(cache.weight(), 4); |
1958 | assert_eq!(cache.capacity(), 8); |
1959 | assert!(cache.is_full()); |
1960 | } |
1961 | |
1962 | #[test ] |
1963 | fn test_weighted_iter_forwards() { |
1964 | let mut cache = CLruCache::with_config( |
1965 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
1966 | ); |
1967 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1968 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1969 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1970 | |
1971 | let mut iter = cache.iter(); |
1972 | assert_eq!(iter.len(), 3); |
1973 | assert_eq!(iter.next(), Some((&3, &"c" ))); |
1974 | |
1975 | assert_eq!(iter.len(), 2); |
1976 | assert_eq!(iter.next(), Some((&2, &"b" ))); |
1977 | |
1978 | assert_eq!(iter.len(), 1); |
1979 | assert_eq!(iter.next(), Some((&1, &"a" ))); |
1980 | |
1981 | assert_eq!(iter.len(), 0); |
1982 | assert_eq!(iter.next(), None); |
1983 | } |
1984 | |
1985 | #[test ] |
1986 | fn test_weighted_iter_backwards() { |
1987 | let mut cache = CLruCache::with_config( |
1988 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
1989 | ); |
1990 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
1991 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
1992 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
1993 | |
1994 | let mut iter = cache.iter(); |
1995 | assert_eq!(iter.len(), 3); |
1996 | assert_eq!(iter.next_back(), Some((&1, &"a" ))); |
1997 | |
1998 | assert_eq!(iter.len(), 2); |
1999 | assert_eq!(iter.next_back(), Some((&2, &"b" ))); |
2000 | |
2001 | assert_eq!(iter.len(), 1); |
2002 | assert_eq!(iter.next_back(), Some((&3, &"c" ))); |
2003 | |
2004 | assert_eq!(iter.len(), 0); |
2005 | assert_eq!(iter.next_back(), None); |
2006 | } |
2007 | |
2008 | #[test ] |
2009 | fn test_weighted_iter_forwards_and_backwards() { |
2010 | let mut cache = CLruCache::with_config( |
2011 | CLruCacheConfig::new(NonZeroUsize::new(8).unwrap()).with_scale(IntStrScale), |
2012 | ); |
2013 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
2014 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
2015 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
2016 | |
2017 | let mut iter = cache.iter(); |
2018 | assert_eq!(iter.len(), 3); |
2019 | assert_eq!(iter.next(), Some((&3, &"c" ))); |
2020 | |
2021 | assert_eq!(iter.len(), 2); |
2022 | assert_eq!(iter.next_back(), Some((&1, &"a" ))); |
2023 | |
2024 | assert_eq!(iter.len(), 1); |
2025 | assert_eq!(iter.next(), Some((&2, &"b" ))); |
2026 | |
2027 | assert_eq!(iter.len(), 0); |
2028 | assert_eq!(iter.next_back(), None); |
2029 | } |
2030 | |
2031 | #[test ] |
2032 | fn test_weighted_into_iter() { |
2033 | let mut cache = CLruCache::with_config( |
2034 | CLruCacheConfig::new(NonZeroUsize::new(10).unwrap()).with_scale(IntStrScale), |
2035 | ); |
2036 | |
2037 | assert_eq!(cache.put_with_weight(1, "a" ), Ok(None)); |
2038 | assert_eq!(cache.put_with_weight(2, "b" ), Ok(None)); |
2039 | assert_eq!(cache.put_with_weight(3, "c" ), Ok(None)); |
2040 | assert_eq!(cache.put_with_weight(4, "d" ), Ok(None)); |
2041 | assert_eq!(cache.put_with_weight(5, "e" ), Ok(None)); |
2042 | |
2043 | let mut vec = Vec::new(); |
2044 | for (k, v) in &cache { |
2045 | vec.push((k, v)); |
2046 | } |
2047 | assert_eq!( |
2048 | vec, |
2049 | vec![(&5, &"e" ), (&4, &"d" ), (&3, &"c" ), (&2, &"b" ), (&1, &"a" )] |
2050 | ); |
2051 | |
2052 | assert_eq!( |
2053 | cache.into_iter().collect::<Vec<_>>(), |
2054 | vec![(5, "e" ), (4, "d" ), (3, "c" ), (2, "b" ), (1, "a" )] |
2055 | ); |
2056 | } |
2057 | |
2058 | #[test ] |
2059 | fn test_is_send() { |
2060 | fn is_send<T: Send>() {} |
2061 | |
2062 | fn cache_is_send<K: Send, V: Send, S: Send, W: WeightScale<K, V> + Send>() { |
2063 | is_send::<K>(); |
2064 | is_send::<V>(); |
2065 | is_send::<S>(); |
2066 | is_send::<W>(); |
2067 | is_send::<CLruCache<K, V, S, W>>(); |
2068 | } |
2069 | |
2070 | cache_is_send::<String, String, RandomState, ZeroWeightScale>(); |
2071 | |
2072 | fn cache_in_mutex< |
2073 | K: Clone + Default + Eq + Hash + Send + 'static, |
2074 | V: Default + Send + 'static, |
2075 | S: BuildHasher + Send + 'static, |
2076 | W: WeightScale<K, V> + Send + 'static, |
2077 | >( |
2078 | cache: CLruCache<K, V, S, W>, |
2079 | ) where |
2080 | (K, V): std::fmt::Debug, |
2081 | { |
2082 | use std::sync::{Arc, Mutex}; |
2083 | use std::thread; |
2084 | |
2085 | let mutex: Arc<Mutex<CLruCache<K, V, S, W>>> = Arc::new(Mutex::new(cache)); |
2086 | let mutex2 = mutex.clone(); |
2087 | let t1 = thread::spawn(move || { |
2088 | mutex |
2089 | .lock() |
2090 | .unwrap() |
2091 | .put_with_weight(Default::default(), Default::default()) |
2092 | .unwrap(); |
2093 | }); |
2094 | let t2 = thread::spawn(move || { |
2095 | mutex2 |
2096 | .lock() |
2097 | .unwrap() |
2098 | .put_with_weight(Default::default(), Default::default()) |
2099 | .unwrap(); |
2100 | }); |
2101 | t1.join().unwrap(); |
2102 | t2.join().unwrap(); |
2103 | } |
2104 | |
2105 | let cache: CLruCache<String, String> = CLruCache::new(TWO); |
2106 | cache_in_mutex(cache); |
2107 | } |
2108 | |
2109 | #[test ] |
2110 | fn test_is_sync() { |
2111 | fn is_sync<T: Sync>() {} |
2112 | |
2113 | fn cache_is_sync<K: Sync, V: Sync, S: Sync, W: WeightScale<K, V> + Sync>() { |
2114 | is_sync::<K>(); |
2115 | is_sync::<V>(); |
2116 | is_sync::<S>(); |
2117 | is_sync::<W>(); |
2118 | is_sync::<CLruCache<K, V, S, W>>(); |
2119 | } |
2120 | |
2121 | cache_is_sync::<String, String, RandomState, ZeroWeightScale>(); |
2122 | |
2123 | fn cache_in_rwlock< |
2124 | K: Clone + Default + Eq + Hash + Send + Sync + 'static, |
2125 | V: Default + Send + Sync + 'static, |
2126 | S: BuildHasher + Send + Sync + 'static, |
2127 | W: WeightScale<K, V> + Send + Sync + 'static, |
2128 | >( |
2129 | cache: CLruCache<K, V, S, W>, |
2130 | ) where |
2131 | (K, V): std::fmt::Debug, |
2132 | { |
2133 | use std::sync::{Arc, RwLock}; |
2134 | use std::thread; |
2135 | |
2136 | let mutex: Arc<RwLock<CLruCache<K, V, S, W>>> = Arc::new(RwLock::new(cache)); |
2137 | let mutex2 = mutex.clone(); |
2138 | let t1 = thread::spawn(move || { |
2139 | mutex |
2140 | .write() |
2141 | .unwrap() |
2142 | .put_with_weight(Default::default(), Default::default()) |
2143 | .unwrap(); |
2144 | }); |
2145 | let t2 = thread::spawn(move || { |
2146 | mutex2 |
2147 | .write() |
2148 | .unwrap() |
2149 | .put_with_weight(Default::default(), Default::default()) |
2150 | .unwrap(); |
2151 | }); |
2152 | t1.join().unwrap(); |
2153 | t2.join().unwrap(); |
2154 | } |
2155 | |
2156 | let cache: CLruCache<String, String> = CLruCache::new(TWO); |
2157 | cache_in_rwlock(cache); |
2158 | } |
2159 | } |
2160 | |