lru_cache_map/lib.rs
1// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
2// file at the top-level directory of this distribution and at
3// http://rust-lang.org/COPYRIGHT.
4//
5// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8// option. This file may not be copied, modified, or distributed
9// except according to those terms.
10
11//! A cache that holds a limited number of key-value pairs. When the
12//! capacity of the cache is exceeded, the least-recently-used
13//! (where "used" means a look-up or putting the pair into the cache)
14//! pair is automatically removed.
15//!
16//! # Examples
17//!
18//! ```rust
19//! # use lru_cache_map::LruCache;
20//! #
21//! let mut cache = LruCache::new(2);
22//!
23//! cache.insert(1, 10);
24//! cache.insert(2, 20);
25//! cache.insert(3, 30);
26//! assert!(cache.get_mut(&1).is_none());
27//! assert_eq!(*cache.get_mut(&2).unwrap(), 20);
28//! assert_eq!(*cache.get_mut(&3).unwrap(), 30);
29//!
30//! cache.insert(2, 22);
31//! assert_eq!(*cache.get_mut(&2).unwrap(), 22);
32//!
33//! cache.insert(6, 60);
34//! assert!(cache.get_mut(&3).is_none());
35//!
36//! cache.set_capacity(1);
37//! assert!(cache.get_mut(&2).is_none());
38//! ```
39//!
40//! The cache can also be limited by an arbitrary metric calculated from its
41//! key-value pairs, see [`LruCache::with_meter`] for more information. Custom metrics can be
42//! written by implementing the [`Meter`] trait.
43
44use std::borrow::Borrow;
45use std::fmt;
46use std::hash::BuildHasher;
47use std::hash::Hash;
48
49pub use hashbrown;
50use hashbrown::hash_map::DefaultHashBuilder;
51use hashlink::linked_hash_map;
52use hashlink::linked_hash_map::RawEntryMut;
53use linked_hash_map::LinkedHashMap;
54
55use crate::cache_iter::IntoIter;
56use crate::cache_iter::Iter;
57use crate::cache_iter::IterMut;
58use crate::meter::Count;
59use crate::meter::Meter;
60use crate::peek_mut::PeekMut;
61
62mod cache_iter;
63pub mod meter;
64mod peek_mut;
65
66/// An LRU cache.
67#[derive(Clone)]
68pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = DefaultHashBuilder, M: Meter<K, V> = Count> {
69 map: LinkedHashMap<K, V, S>,
70
71 /// The maximum number of items this cache can hold.
72 max_items: usize,
73
74 meter: M,
75 current_measure: M::Measure,
76 max_capacity: M::Measure,
77}
78
79impl<K: Eq + Hash, V> LruCache<K, V> {
80 /// Creates an empty cache that can hold at most `max_items` items.
81 ///
82 /// # Examples
83 ///
84 /// ```rust
85 /// # use lru_cache_map::LruCache;
86 /// let mut cache: LruCache<i32, &str> = LruCache::new(10);
87 /// ```
88 pub fn new(max_items: usize) -> Self {
89 LruCache {
90 map: LinkedHashMap::new(),
91 // By default Meter is `Count` so that max_item is the same as capacity;
92 max_items,
93 current_measure: 0,
94 max_capacity: max_items,
95 meter: Count,
96 }
97 }
98}
99
100impl<K: Eq + Hash, V, M: Meter<K, V>> LruCache<K, V, DefaultHashBuilder, M> {
101 /// Creates an empty cache that can hold at most `capacity` as measured by
102 /// [`Meter`].
103 ///
104 /// You can implement the [`Meter`] trait to allow custom metrics.
105 ///
106 /// # Examples
107 ///
108 /// ```rust
109 /// # use lru_cache_map::{LruCache, meter::Meter};
110 /// # use std::borrow::Borrow;
111 /// #
112 /// /// Measure Vec items by their length
113 /// struct VecLen;
114 ///
115 /// impl<K, T> Meter<K, Vec<T>> for VecLen {
116 /// type Measure = usize;
117 /// fn measure<Q: ?Sized>(&self, _: &Q, v: &Vec<T>) -> usize
118 /// where K: Borrow<Q>
119 /// {
120 /// v.len()
121 /// }
122 /// }
123 ///
124 /// let mut cache = LruCache::with_meter(100, 5, VecLen);
125 ///
126 /// cache.insert(1, vec![1, 2]);
127 /// assert_eq!(cache.size(), 2);
128 ///
129 /// cache.insert(2, vec![3, 4]);
130 /// cache.insert(3, vec![5, 6]);
131 /// assert_eq!(cache.size(), 4);
132 /// assert_eq!(cache.len(), 2);
133 /// ```
134 pub fn with_meter(
135 max_items: usize,
136 capacity: M::Measure,
137 meter: M,
138 ) -> LruCache<K, V, DefaultHashBuilder, M> {
139 LruCache {
140 map: LinkedHashMap::new(),
141 max_items,
142 current_measure: Default::default(),
143 max_capacity: capacity,
144 meter,
145 }
146 }
147}
148
149impl<K: Eq + Hash, V, S: BuildHasher> LruCache<K, V, S, Count> {
150 /// Creates an empty cache that can hold at most `capacity` items with the
151 /// given hash builder.
152 pub fn with_hasher(capacity: usize, hash_builder: S) -> LruCache<K, V, S, Count> {
153 LruCache {
154 map: LinkedHashMap::with_hasher(hash_builder),
155 max_items: capacity,
156 current_measure: 0,
157 max_capacity: capacity,
158 meter: Count,
159 }
160 }
161}
162
163impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> LruCache<K, V, S, M> {
164 /// Creates an empty cache that can hold at most `capacity` as measured by
165 /// [`Meter`] with the given hash builder.
166 pub fn with_meter_and_hasher(
167 max_items: usize,
168 capacity: M::Measure,
169 meter: M,
170 hash_builder: S,
171 ) -> Self {
172 LruCache {
173 map: LinkedHashMap::with_hasher(hash_builder),
174 max_items,
175 current_measure: Default::default(),
176 max_capacity: capacity,
177 meter,
178 }
179 }
180
181 /// Returns `true` if the cache contains no key-value pairs.
182 pub fn is_empty(&self) -> bool {
183 self.map.is_empty()
184 }
185
186 /// Returns the number of key-value pairs in the cache.
187 pub fn len(&self) -> usize {
188 self.map.len()
189 }
190
191 pub fn max_items(&self) -> usize {
192 self.max_items
193 }
194
195 /// Sets the max number of items the cache can hold.
196 ///
197 /// Removes least-recently-used key-value pairs if necessary.
198 ///
199 /// # Examples
200 ///
201 /// ```rust
202 /// # use lru_cache_map::LruCache;
203 /// #
204 /// let mut cache = LruCache::new(2);
205 /// cache.set_capacity(100);
206 ///
207 /// cache.insert(1, "a");
208 /// cache.insert(2, "b");
209 /// cache.insert(3, "c");
210 ///
211 /// assert_eq!(cache.get(&1), None);
212 /// assert_eq!(cache.get(&2), Some(&"b"));
213 /// assert_eq!(cache.get(&3), Some(&"c"));
214 ///
215 /// cache.set_max_items(3);
216 /// cache.insert(1, "a");
217 /// cache.insert(2, "b");
218 ///
219 /// assert_eq!(cache.get(&1), Some(&"a"));
220 /// assert_eq!(cache.get(&2), Some(&"b"));
221 /// assert_eq!(cache.get(&3), Some(&"c"));
222 ///
223 /// cache.set_max_items(1);
224 ///
225 /// assert_eq!(cache.get(&1), None);
226 /// assert_eq!(cache.get(&2), None);
227 /// assert_eq!(cache.get(&3), Some(&"c"));
228 /// ```
229 pub fn set_max_items(&mut self, max_items: usize) {
230 self.max_items = max_items;
231 self.evict_by_policy();
232 }
233
234 /// Returns the size in `Meter::Measure` of all the key-value pairs in the cache.
235 pub fn size(&self) -> M::Measure {
236 self.current_measure
237 }
238
239 /// Returns the maximum size of the key-value pairs the cache can hold, as
240 /// measured by the [`Meter`] used by the cache.
241 ///
242 /// # Examples
243 ///
244 /// ```rust
245 /// # use lru_cache_map::LruCache;
246 /// let mut cache: LruCache<i32, &str> = LruCache::new(2);
247 /// assert_eq!(cache.capacity(), 2);
248 /// ```
249 pub fn capacity(&self) -> M::Measure {
250 self.max_capacity
251 }
252
253 /// Sets the size of the key-value pairs the cache can hold, as measured by
254 /// the [`Meter`] used by the cache.
255 ///
256 /// Removes least-recently-used key-value pairs if necessary.
257 ///
258 /// # Examples
259 ///
260 /// ```rust
261 /// # use lru_cache_map::LruCache;
262 /// #
263 /// let mut cache = LruCache::new(2);
264 /// cache.set_max_items(100);
265 ///
266 /// cache.insert(1, "a");
267 /// cache.insert(2, "b");
268 /// cache.insert(3, "c");
269 ///
270 /// assert_eq!(cache.get(&1), None);
271 /// assert_eq!(cache.get(&2), Some(&"b"));
272 /// assert_eq!(cache.get(&3), Some(&"c"));
273 ///
274 /// cache.set_capacity(3);
275 /// cache.insert(1, "a");
276 /// cache.insert(2, "b");
277 ///
278 /// assert_eq!(cache.get(&1), Some(&"a"));
279 /// assert_eq!(cache.get(&2), Some(&"b"));
280 /// assert_eq!(cache.get(&3), Some(&"c"));
281 ///
282 /// cache.set_capacity(1);
283 ///
284 /// assert_eq!(cache.get(&1), None);
285 /// assert_eq!(cache.get(&2), None);
286 /// assert_eq!(cache.get(&3), Some(&"c"));
287 /// ```
288 pub fn set_capacity(&mut self, capacity: M::Measure) {
289 self.max_capacity = capacity;
290 self.evict_by_policy();
291 }
292
293 /// Checks if the map contains the given key.
294 ///
295 /// # Examples
296 ///
297 /// ```rust
298 /// # use lru_cache_map::LruCache;
299 /// #
300 /// let mut cache = LruCache::new(1);
301 ///
302 /// cache.insert(1, "a");
303 /// assert!(cache.contains_key(&1));
304 /// ```
305 pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
306 where
307 K: Borrow<Q>,
308 Q: Hash + Eq,
309 {
310 self.map.contains_key(key)
311 }
312
313 /// Returns a reference to the value corresponding to the given key
314 /// in the cache, if any. **Do not** put the accessed item to the back.
315 ///
316 /// # Examples
317 ///
318 /// ```rust
319 /// # use lru_cache_map::LruCache;
320 /// #
321 /// let mut cache = LruCache::new(2);
322 ///
323 /// cache.insert(1, "a");
324 /// cache.insert(2, "b");
325 /// cache.insert(2, "c");
326 /// cache.insert(3, "d");
327 ///
328 /// assert_eq!(cache.peek(&1), None);
329 /// assert_eq!(cache.peek(&2), Some(&"c"));
330 /// ```
331 pub fn peek<Q: ?Sized>(&mut self, k: &Q) -> Option<&V>
332 where
333 K: Borrow<Q>,
334 Q: Hash + Eq,
335 {
336 match self.map.raw_entry_mut().from_key(k) {
337 RawEntryMut::Occupied(occupied) => Some(occupied.into_mut()),
338 RawEntryMut::Vacant(_) => None,
339 }
340 }
341
342 /// Returns a mutable reference to the value corresponding to the given key
343 /// in the cache, if any. **Do** put the accessed item to the back.
344 ///
345 /// When the mutable reference is dropped, the cache will be evicted by policy if the `measure`
346 /// of the updated value changes.
347 ///
348 /// # Examples
349 ///
350 /// ```rust
351 /// # use lru_cache_map::LruCache;
352 /// # use std::ops::DerefMut;
353 /// #
354 /// let mut cache = LruCache::new(2);
355 ///
356 /// cache.insert(1, "a");
357 /// cache.insert(2, "b");
358 ///
359 /// {
360 /// let mut a = cache.peek_mut(&1).unwrap();
361 /// *a = "c";
362 /// }
363 ///
364 /// assert_eq!(cache.get(&1).unwrap(), &"c");
365 /// assert_eq!(cache.get(&2).unwrap(), &"b");
366 /// ```
367 pub fn peek_mut<'a, Q: ?Sized>(&'a mut self, k: &'a Q) -> Option<PeekMut<'a, K, V, S, M>>
368 where
369 K: Borrow<Q>,
370 Q: Hash + Eq,
371 {
372 let me = self as *mut Self;
373
374 match self.map.raw_entry_mut().from_key(k) {
375 RawEntryMut::Occupied(occupied) => {
376 let p = PeekMut::new(occupied, me);
377 Some(p)
378 }
379 RawEntryMut::Vacant(_) => None,
380 }
381 }
382
383 /// Returns a reference to the value corresponding to the given key
384 /// in the cache, if any. And put the accessed item to the back.
385 ///
386 /// # Examples
387 ///
388 /// ```rust
389 /// # use lru_cache_map::LruCache;
390 /// #
391 /// let mut cache = LruCache::new(2);
392 ///
393 /// cache.insert(1, "a");
394 /// cache.insert(2, "b");
395 /// cache.insert(2, "c");
396 /// cache.insert(3, "d");
397 ///
398 /// assert_eq!(cache.get(&1), None);
399 /// assert_eq!(cache.get(&2), Some(&"c"));
400 /// ```
401 pub fn get<Q: ?Sized>(&mut self, k: &Q) -> Option<&V>
402 where
403 K: Borrow<Q>,
404 Q: Hash + Eq,
405 {
406 match self.map.raw_entry_mut().from_key(k) {
407 RawEntryMut::Occupied(mut occupied) => {
408 occupied.to_back();
409 Some(occupied.into_mut())
410 }
411 RawEntryMut::Vacant(_) => None,
412 }
413 }
414
415 /// Returns a mutable reference to the value corresponding to the given key
416 /// in the cache, if any.
417 ///
418 /// # Examples
419 ///
420 /// ```rust
421 /// # use lru_cache_map::LruCache;
422 /// # use std::ops::DerefMut;
423 /// #
424 /// let mut cache = LruCache::new(2);
425 ///
426 /// cache.insert(1, "a");
427 /// cache.insert(2, "b");
428 ///
429 /// {
430 /// let mut a = cache.get_mut(&1).unwrap();
431 /// *a = "c";
432 /// }
433 ///
434 /// assert_eq!(cache.get(&1).unwrap(), &"c");
435 /// assert_eq!(cache.get(&2).unwrap(), &"b");
436 /// ```
437 pub fn get_mut<'a, Q: ?Sized>(&'a mut self, k: &'a Q) -> Option<PeekMut<'a, K, V, S, M>>
438 where
439 K: Borrow<Q>,
440 Q: Hash + Eq,
441 {
442 let me = self as *mut Self;
443
444 match self.map.raw_entry_mut().from_key(k) {
445 RawEntryMut::Occupied(mut occupied) => {
446 occupied.to_back();
447 let p = PeekMut::new(occupied, me);
448 Some(p)
449 }
450 RawEntryMut::Vacant(_) => None,
451 }
452 }
453
454 /// Inserts a key-value pair into the cache and put it to the back. If the key already existed,
455 /// the old value is returned.
456 ///
457 /// # Examples
458 ///
459 /// ```rust
460 /// # use lru_cache_map::LruCache;
461 /// #
462 /// let mut cache = LruCache::new(2);
463 ///
464 /// cache.insert(1, "a");
465 /// cache.insert(2, "b");
466 /// assert_eq!(cache.get(&1), Some(&"a"));
467 /// assert_eq!(cache.get(&2), Some(&"b"));
468 ///
469 /// let evicted = cache.insert(2, "c");
470 /// assert_eq!(evicted, Some("b"));
471 /// assert_eq!(cache.get(&2), Some(&"c"));
472 /// ```
473 pub fn insert(&mut self, k: K, v: V) -> Option<V> {
474 self.measure_add(&k, &v);
475
476 let old_val = match self.map.raw_entry_mut().from_key(&k) {
477 RawEntryMut::Occupied(mut occupied) => {
478 occupied.to_back();
479 let old_val = occupied.replace_value(v);
480
481 self.measure_remove(&k, &old_val);
482 Some(old_val)
483 }
484 RawEntryMut::Vacant(vacant) => {
485 vacant.insert(k, v);
486 None
487 }
488 };
489
490 self.evict_by_policy();
491
492 old_val
493 }
494
495 /// Removes the given key from the cache and returns its corresponding
496 /// value.
497 ///
498 /// # Examples
499 ///
500 /// ```rust
501 /// # use lru_cache_map::LruCache;
502 /// #
503 /// let mut cache = LruCache::new(2);
504 ///
505 /// cache.insert(2, "a");
506 ///
507 /// assert_eq!(cache.remove(&1), None);
508 /// assert_eq!(cache.remove(&2), Some("a"));
509 /// assert_eq!(cache.remove(&2), None);
510 /// assert_eq!(cache.len(), 0);
511 /// ```
512 pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
513 where
514 K: Borrow<Q>,
515 Q: Hash + Eq,
516 {
517 self.map.remove(k).map(|v| {
518 self.measure_remove(k, &v);
519 v
520 })
521 }
522
523 /// Removes and returns the least recently used key-value pair as a tuple.
524 ///
525 /// # Examples
526 ///
527 /// ```rust
528 /// # use lru_cache_map::LruCache;
529 /// #
530 /// let mut cache = LruCache::new(2);
531 ///
532 /// cache.insert(1, "a");
533 /// cache.insert(2, "b");
534 ///
535 /// assert_eq!(cache.remove_lru(), Some((1, "a")));
536 /// assert_eq!(cache.len(), 1);
537 /// ```
538 #[inline]
539 pub fn remove_lru(&mut self) -> Option<(K, V)> {
540 self.map.pop_front().map(|(k, v)| {
541 self.measure_remove(&k, &v);
542 (k, v)
543 })
544 }
545
546 /// Removes all key-value pairs from the cache.
547 pub fn clear(&mut self) {
548 self.map.clear();
549 self.current_measure = Default::default();
550 }
551
552 /// Returns an iterator over the cache's key-value pairs in least- to
553 /// most-recently-used order.
554 ///
555 /// Accessing the cache through the iterator does _not_ affect the cache's
556 /// LRU state.
557 ///
558 /// # Examples
559 ///
560 /// ```rust
561 /// # use lru_cache_map::LruCache;
562 /// #
563 /// let mut cache = LruCache::new(2);
564 ///
565 /// cache.insert(1, 10);
566 /// cache.insert(2, 20);
567 /// cache.insert(3, 30);
568 ///
569 /// let kvs: Vec<_> = cache.iter().collect();
570 /// assert_eq!(kvs, [(&2, &20), (&3, &30)]);
571 /// ```
572 pub fn iter(&self) -> Iter<'_, K, V> {
573 Iter(self.map.iter())
574 }
575
576 /// Returns an iterator over the cache's key-value pairs in least- to
577 /// most-recently-used order, with mutable references to the values.
578 ///
579 /// Accessing the cache through the iterator does _not_ affect the cache's
580 /// LRU state. Note that this method is not available for cache objects
581 /// using `Meter` implementations. other than `Count`.
582 ///
583 /// # Examples
584 ///
585 /// ```rust
586 /// # use lru_cache_map::LruCache;
587 /// #
588 /// let mut cache = LruCache::new(2);
589 ///
590 /// cache.insert(1, 10);
591 /// cache.insert(2, 20);
592 /// cache.insert(3, 30);
593 ///
594 /// let mut n = 2;
595 ///
596 /// for (k, v) in cache.iter_mut() {
597 /// assert_eq!(*k, n);
598 /// assert_eq!(*v, n * 10);
599 /// *v *= 10;
600 /// n += 1;
601 /// }
602 ///
603 /// assert_eq!(n, 4);
604 /// assert_eq!(cache.get(&2), Some(&200));
605 /// assert_eq!(cache.get(&3), Some(&300));
606 /// ```
607 // TODO: validate against `Meter` when the updated value is given back
608 pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
609 self.internal_iter_mut()
610 }
611
612 fn internal_iter_mut(&mut self) -> IterMut<'_, K, V> {
613 IterMut(self.map.iter_mut())
614 }
615
616 /// Evict least recent used items until both count and size are below their limit.
617 pub(crate) fn evict_by_policy(&mut self) {
618 while self.len() > self.max_items() {
619 self.remove_lru();
620 }
621 while self.size() > self.capacity() {
622 self.remove_lru();
623 }
624 }
625
626 pub(crate) fn measure_add<Q: ?Sized>(&mut self, k: &Q, v: &V) -> M::Measure
627 where
628 K: Borrow<Q>,
629 {
630 self.current_measure = self.current_measure + self.meter.measure(k, v);
631 self.current_measure
632 }
633
634 pub(crate) fn measure_remove<Q: ?Sized>(&mut self, k: &Q, v: &V) -> M::Measure
635 where
636 K: Borrow<Q>,
637 {
638 self.current_measure = self.current_measure - self.meter.measure(k, v);
639 self.current_measure
640 }
641}
642
643impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> Extend<(K, V)> for LruCache<K, V, S, M> {
644 fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
645 for (k, v) in iter {
646 self.insert(k, v);
647 }
648 }
649}
650
651impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher, M: Meter<K, V>> fmt::Debug
652 for LruCache<K, V, S, M>
653{
654 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
655 f.debug_map().entries(self.iter().rev()).finish()
656 }
657}
658
659impl<K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator for LruCache<K, V, S, M> {
660 type Item = (K, V);
661 type IntoIter = IntoIter<K, V>;
662
663 fn into_iter(self) -> IntoIter<K, V> {
664 IntoIter(self.map.into_iter())
665 }
666}
667
668impl<'a, K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator
669 for &'a LruCache<K, V, S, M>
670{
671 type Item = (&'a K, &'a V);
672 type IntoIter = Iter<'a, K, V>;
673 fn into_iter(self) -> Iter<'a, K, V> {
674 self.iter()
675 }
676}
677
678impl<'a, K: Eq + Hash, V, S: BuildHasher, M: Meter<K, V>> IntoIterator
679 for &'a mut LruCache<K, V, S, M>
680{
681 type Item = (&'a K, &'a mut V);
682 type IntoIter = IterMut<'a, K, V>;
683 fn into_iter(self) -> IterMut<'a, K, V> {
684 self.internal_iter_mut()
685 }
686}
687
688#[cfg(test)]
689mod tests {
690 use std::borrow::Borrow;
691 use std::ops::Deref;
692
693 use super::LruCache;
694 use crate::meter::Meter;
695
696 #[test]
697 fn test_put_and_get() {
698 let mut cache = LruCache::new(2);
699 cache.insert(1, 10);
700 cache.insert(2, 20);
701 assert_eq!(cache.get_mut(&1).unwrap().deref(), &mut 10);
702 assert_eq!(cache.get_mut(&2).unwrap().deref(), &mut 20);
703 assert_eq!(cache.len(), 2);
704 assert_eq!(cache.size(), 2);
705 }
706
707 #[test]
708 fn test_put_update() {
709 let mut cache = LruCache::new(1);
710 cache.insert("1", 10);
711 cache.insert("1", 19);
712 assert_eq!(cache.get_mut("1").unwrap().deref(), &mut 19);
713 assert_eq!(cache.len(), 1);
714 }
715
716 #[test]
717 fn test_contains_key() {
718 let mut cache = LruCache::new(1);
719 cache.insert("1", 10);
720 assert!(cache.contains_key("1"));
721 }
722
723 #[test]
724 fn test_expire_lru() {
725 let mut cache = LruCache::new(2);
726 cache.insert("foo1", "bar1");
727 cache.insert("foo2", "bar2");
728 cache.insert("foo3", "bar3");
729 assert!(cache.get_mut("foo1").is_none());
730 cache.insert("foo2", "bar2update");
731 cache.insert("foo4", "bar4");
732 assert!(cache.get_mut("foo3").is_none());
733 }
734
735 #[test]
736 fn test_pop() {
737 let mut cache = LruCache::new(2);
738 cache.insert(1, 10);
739 cache.insert(2, 20);
740 assert_eq!(cache.len(), 2);
741 let opt1 = cache.remove(&1);
742 assert!(opt1.is_some());
743 assert_eq!(opt1.unwrap(), 10);
744 assert!(cache.get_mut(&1).is_none());
745 assert_eq!(cache.len(), 1);
746 }
747
748 #[test]
749 fn test_change_capacity() {
750 let mut cache = LruCache::new(2);
751 assert_eq!(cache.capacity(), 2);
752 cache.insert(1, 10);
753 cache.insert(2, 20);
754 cache.set_capacity(1);
755 assert!(cache.get_mut(&1).is_none());
756 assert_eq!(cache.capacity(), 1);
757 }
758
759 #[test]
760 fn test_debug() {
761 let mut cache = LruCache::new(3);
762 cache.insert(1, 10);
763 cache.insert(2, 20);
764 cache.insert(3, 30);
765 assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}");
766 cache.insert(2, 22);
767 assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}");
768 cache.insert(6, 60);
769 assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}");
770 cache.get_mut(&3);
771 assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}");
772 cache.set_capacity(2);
773 assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}");
774 }
775
776 #[test]
777 fn test_remove() {
778 let mut cache = LruCache::new(3);
779 cache.insert(1, 10);
780 cache.insert(2, 20);
781 cache.insert(3, 30);
782 cache.insert(4, 40);
783 cache.insert(5, 50);
784 cache.remove(&3);
785 cache.remove(&4);
786 assert!(cache.get_mut(&3).is_none());
787 assert!(cache.get_mut(&4).is_none());
788 cache.insert(6, 60);
789 cache.insert(7, 70);
790 cache.insert(8, 80);
791 assert!(cache.get_mut(&5).is_none());
792 assert_eq!(cache.get_mut(&6).unwrap().deref(), &mut 60);
793 assert_eq!(cache.get_mut(&7).unwrap().deref(), &mut 70);
794 assert_eq!(cache.get_mut(&8).unwrap().deref(), &mut 80);
795 }
796
797 #[test]
798 fn test_get_mut_debug() {
799 let mut cache = LruCache::new(2);
800 cache.insert(1, 10);
801 let a = cache.get_mut(&1).unwrap();
802
803 assert_eq!("PeekMut(10)", format!("{:?}", a))
804 }
805
806 #[test]
807 fn test_get_mut_evict() {
808 // When a value is updated via `get_mut()` and given back to the cache,
809 // the cache should evict items according to the meter changes.
810
811 let mut cache = LruCache::with_meter(2, 5, VecLen);
812 cache.insert(1, b"12".to_vec());
813 cache.insert(2, b"34".to_vec());
814
815 assert_eq!(cache.len(), 2);
816
817 {
818 let mut a = cache.get_mut(&1).unwrap();
819 *a = b"1234".to_vec();
820 }
821
822 assert_eq!(cache.len(), 1);
823 assert_eq!(cache.get(&1).unwrap(), &b"1234".to_vec());
824
825 {
826 let mut a = cache.get_mut(&1).unwrap();
827 *a = b"123456".to_vec();
828 }
829
830 assert_eq!(cache.len(), 0);
831 }
832
833 #[test]
834 fn test_peek() {
835 let mut cache = LruCache::with_meter(2, 5, VecLen);
836 cache.insert(1, b"12".to_vec());
837 cache.insert(2, b"34".to_vec());
838
839 // peek() does not update the recency of `1`.
840 assert_eq!(cache.peek(&1).unwrap(), &b"12".to_vec());
841
842 // still evict `1`, because peek() does not update its recency
843 cache.insert(3, b"33".to_vec());
844 assert_eq!(cache.peek(&1), None);
845 }
846
847 #[test]
848 fn test_peek_mut() {
849 let mut cache = LruCache::with_meter(2, 5, VecLen);
850 cache.insert(1, b"12".to_vec());
851 cache.insert(2, b"34".to_vec());
852
853 {
854 let mut a = cache.peek_mut(&1).unwrap();
855 *a = b"56".to_vec();
856 }
857 // `1` is updated
858 assert_eq!(cache.peek(&1).unwrap(), &b"56".to_vec());
859
860 // still evict `1`, because peek() does not update its recency
861 cache.insert(3, b"33".to_vec());
862 assert_eq!(cache.peek(&1), None);
863 }
864
865 #[test]
866 fn test_peek_mut_evict() {
867 // When a value is updated via `peek_mut()` and given back to the cache,
868 // the cache should evict items according to the meter changes.
869
870 let mut cache = LruCache::with_meter(2, 5, VecLen);
871 cache.insert(1, b"12".to_vec());
872 cache.insert(2, b"34".to_vec());
873
874 assert_eq!(cache.len(), 2);
875
876 {
877 let mut a = cache.peek_mut(&1).unwrap();
878 *a = b"1234".to_vec();
879 }
880
881 assert_eq!(cache.len(), 1);
882 // Because peek does not update the recency, `1` is evicted
883 assert_eq!(cache.get(&1), None);
884 assert_eq!(cache.get(&2).unwrap(), &b"34".to_vec());
885 }
886
887 #[test]
888 fn test_clear() {
889 let mut cache = LruCache::new(2);
890 cache.insert(1, 10);
891 cache.insert(2, 20);
892 cache.clear();
893
894 assert!(cache.get_mut(&1).is_none());
895 assert!(cache.get_mut(&2).is_none());
896 assert_eq!(format!("{:?}", cache), "{}");
897 }
898
899 #[test]
900 fn test_iter() {
901 let mut cache = LruCache::new(3);
902 cache.insert(1, 10);
903 cache.insert(2, 20);
904 cache.insert(3, 30);
905 cache.insert(4, 40);
906 cache.insert(5, 50);
907 assert_eq!(cache.iter().collect::<Vec<_>>(), [
908 (&3, &30),
909 (&4, &40),
910 (&5, &50)
911 ]);
912 assert_eq!(cache.iter_mut().collect::<Vec<_>>(), [
913 (&3, &mut 30),
914 (&4, &mut 40),
915 (&5, &mut 50)
916 ]);
917 assert_eq!(cache.iter().rev().collect::<Vec<_>>(), [
918 (&5, &50),
919 (&4, &40),
920 (&3, &30)
921 ]);
922 assert_eq!(cache.iter_mut().rev().collect::<Vec<_>>(), [
923 (&5, &mut 50),
924 (&4, &mut 40),
925 (&3, &mut 30)
926 ]);
927 }
928
929 struct VecLen;
930
931 impl<K, T> Meter<K, Vec<T>> for VecLen {
932 type Measure = usize;
933 fn measure<Q: ?Sized>(&self, _: &Q, v: &Vec<T>) -> usize
934 where
935 K: Borrow<Q>,
936 {
937 v.len()
938 }
939 }
940
941 #[test]
942 fn test_metered_cache() {
943 let mut cache = LruCache::with_meter(100, 5, VecLen);
944 cache.insert("foo1", vec![1, 2]);
945 assert_eq!(cache.size(), 2);
946 cache.insert("foo2", vec![3, 4]);
947 cache.insert("foo3", vec![5, 6]);
948 assert_eq!(cache.size(), 4);
949 assert!(!cache.contains_key("foo1"));
950 cache.insert("foo2", vec![7, 8]);
951 cache.insert("foo4", vec![9, 10]);
952 assert_eq!(cache.size(), 4);
953 assert!(!cache.contains_key("foo3"));
954 assert_eq!(cache.get("foo2"), Some(&vec![7, 8]));
955 }
956
957 #[test]
958 fn test_metered_cache_reinsert_larger_capacity() {
959 let mut cache = LruCache::with_meter(100, 5, VecLen);
960 cache.insert("foo1", vec![1, 2]);
961 cache.insert("foo2", vec![3, 4]);
962 assert_eq!(cache.size(), 4);
963 cache.insert("foo2", vec![5, 6, 7, 8]);
964 assert_eq!(cache.size(), 4);
965 assert!(!cache.contains_key("foo1"));
966 }
967
968 #[test]
969 fn test_metered_cache_reinsert_larger_max_items() {
970 let mut cache = LruCache::with_meter(2, 100, VecLen);
971
972 cache.insert("foo1", vec![1, 2]);
973 cache.insert("foo2", vec![3, 4]);
974 assert_eq!(cache.len(), 2);
975
976 cache.insert("foo2", vec![5, 6, 7, 8]);
977 assert_eq!(cache.len(), 2);
978 assert!(cache.contains_key("foo1"));
979
980 cache.insert("foo3", vec![9, 10]);
981 assert_eq!(cache.len(), 2);
982 assert!(!cache.contains_key("foo1"));
983 }
984
985 #[test]
986 fn test_metered_cache_oversize() {
987 let mut cache = LruCache::with_meter(100, 2, VecLen);
988 cache.insert("foo1", vec![1, 2]);
989 cache.insert("foo2", vec![3, 4, 5, 6]);
990 assert_eq!(cache.size(), 0);
991 assert!(!cache.contains_key("foo1"));
992 assert!(!cache.contains_key("foo2"));
993 }
994
995 #[test]
996 fn test_metered_cache_over_max_items() {
997 let mut cache = LruCache::with_meter(1, 100, VecLen);
998 cache.insert("foo1", vec![1, 2]);
999 cache.insert("foo2", vec![3, 4, 5, 6]);
1000 assert_eq!(cache.len(), 1);
1001 assert!(!cache.contains_key("foo1"));
1002 assert!(cache.contains_key("foo2"));
1003 }
1004}