lru_disk_cache/
lru_cache.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,ignore
19//! use lru_cache::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 key-value pairs, see
41//! [`LruCache::with_meter`][with_meter] for more information. If the `heapsize` feature is enabled,
42//! this crate provides one such alternate metric&mdash;`HeapSize`. Custom metrics can be written by
43//! implementing the [`Meter`][meter] trait.
44//!
45//! [with_meter]: struct.LruCache.html#method.with_meter
46//! [meter]: trait.Meter.html
47
48#[cfg(feature = "heapsize")]
49extern crate heapsize;
50
51use std::borrow::Borrow;
52use std::collections::hash_map::RandomState;
53use std::fmt;
54use std::hash::{BuildHasher, Hash};
55
56use linked_hash_map::LinkedHashMap;
57
58// FIXME(conventions): implement indexing?
59
60/// A trait for measuring the size of a cache entry.
61///
62/// If you implement this trait, you should use `usize` as the `Measure` type, otherwise you will
63/// also have to implement [`CountableMeter`][countablemeter].
64///
65/// [countablemeter]: trait.Meter.html
66pub trait Meter<K, V> {
67    /// The type used to store measurements.
68    type Measure: Default + Copy;
69    /// Calculate the size of `key` and `value`.
70    fn measure<Q: ?Sized>(&self, key: &Q, value: &V) -> Self::Measure
71    where
72        K: Borrow<Q>;
73}
74
75/// Size limit based on a simple count of cache items.
76pub struct Count;
77
78impl<K, V> Meter<K, V> for Count {
79    /// Don't store anything, the measurement can be derived from the map.
80    type Measure = ();
81
82    /// Don't actually count anything either.
83    fn measure<Q: ?Sized>(&self, _: &Q, _: &V)
84    where
85        K: Borrow<Q>,
86    {
87    }
88}
89
90/// A trait to allow the default `Count` measurement to not store an
91/// extraneous counter.
92pub trait CountableMeter<K, V>: Meter<K, V> {
93    /// Add `amount` to `current` and return the sum.
94    fn add(&self, current: Self::Measure, amount: Self::Measure) -> Self::Measure;
95    /// Subtract `amount` from `current` and return the difference.
96    fn sub(&self, current: Self::Measure, amount: Self::Measure) -> Self::Measure;
97    /// Return `current` as a `usize` if possible, otherwise return `None`.
98    ///
99    /// If this method returns `None` the cache will use the number of cache entries as
100    /// its size.
101    fn size(&self, current: Self::Measure) -> Option<u64>;
102}
103
104/// `Count` is all no-ops, the number of entries in the map is the size.
105impl<K, V, T: Meter<K, V>> CountableMeter<K, V> for T
106where
107    T: CountableMeterWithMeasure<K, V, <T as Meter<K, V>>::Measure>,
108{
109    fn add(&self, current: Self::Measure, amount: Self::Measure) -> Self::Measure {
110        CountableMeterWithMeasure::meter_add(self, current, amount)
111    }
112    fn sub(&self, current: Self::Measure, amount: Self::Measure) -> Self::Measure {
113        CountableMeterWithMeasure::meter_sub(self, current, amount)
114    }
115    fn size(&self, current: Self::Measure) -> Option<u64> {
116        CountableMeterWithMeasure::meter_size(self, current)
117    }
118}
119
120pub trait CountableMeterWithMeasure<K, V, M> {
121    /// Add `amount` to `current` and return the sum.
122    fn meter_add(&self, current: M, amount: M) -> M;
123    /// Subtract `amount` from `current` and return the difference.
124    fn meter_sub(&self, current: M, amount: M) -> M;
125    /// Return `current` as a `usize` if possible, otherwise return `None`.
126    ///
127    /// If this method returns `None` the cache will use the number of cache entries as
128    /// its size.
129    fn meter_size(&self, current: M) -> Option<u64>;
130}
131
132/// For any other `Meter` with `Measure=usize`, just do the simple math.
133impl<K, V, T> CountableMeterWithMeasure<K, V, usize> for T
134where
135    T: Meter<K, V>,
136{
137    fn meter_add(&self, current: usize, amount: usize) -> usize {
138        current + amount
139    }
140    fn meter_sub(&self, current: usize, amount: usize) -> usize {
141        current - amount
142    }
143    fn meter_size(&self, current: usize) -> Option<u64> {
144        Some(current as u64)
145    }
146}
147
148impl<K, V> CountableMeterWithMeasure<K, V, ()> for Count {
149    fn meter_add(&self, _current: (), _amount: ()) {}
150    fn meter_sub(&self, _current: (), _amount: ()) {}
151    fn meter_size(&self, _current: ()) -> Option<u64> {
152        None
153    }
154}
155
156#[cfg(feature = "heapsize")]
157mod heap_meter {
158    use heapsize::HeapSizeOf;
159    use std::borrow::Borrow;
160
161    /// Size limit based on the heap size of each cache item.
162    ///
163    /// Requires cache entries that implement [`HeapSizeOf`][1].
164    ///
165    /// [1]: https://doc.servo.org/heapsize/trait.HeapSizeOf.html
166    pub struct HeapSize;
167
168    impl<K, V: HeapSizeOf> super::Meter<K, V> for HeapSize {
169        type Measure = usize;
170
171        fn measure<Q: ?Sized>(&self, _: &Q, item: &V) -> usize
172        where
173            K: Borrow<Q>,
174        {
175            item.heap_size_of_children() + ::std::mem::size_of::<V>()
176        }
177    }
178}
179
180#[cfg(feature = "heapsize")]
181pub use heap_meter::*;
182
183/// An LRU cache.
184#[derive(Clone)]
185pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = RandomState, M: CountableMeter<K, V> = Count>
186{
187    map: LinkedHashMap<K, V, S>,
188    current_measure: M::Measure,
189    max_capacity: u64,
190    meter: M,
191}
192
193impl<K: Eq + Hash, V> LruCache<K, V> {
194    /// Creates an empty cache that can hold at most `capacity` items.
195    ///
196    /// # Examples
197    ///
198    /// ```rust,ignore
199    /// use lru_cache::LruCache;
200    /// let mut cache: LruCache<i32, &str> = LruCache::new(10);
201    /// ```
202    pub fn new(capacity: u64) -> Self {
203        LruCache {
204            map: LinkedHashMap::new(),
205            current_measure: (),
206            max_capacity: capacity,
207            meter: Count,
208        }
209    }
210}
211
212impl<K: Eq + Hash, V, M: CountableMeter<K, V>> LruCache<K, V, RandomState, M> {
213    /// Creates an empty cache that can hold at most `capacity` as measured by `meter`.
214    ///
215    /// You can implement the [`Meter`][meter] trait to allow custom metrics.
216    ///
217    /// [meter]: trait.Meter.html
218    ///
219    /// # Examples
220    ///
221    /// ```rust,ignore
222    /// use lru_cache::{LruCache, Meter};
223    /// use std::borrow::Borrow;
224    ///
225    /// /// Measure Vec items by their length
226    /// struct VecLen;
227    ///
228    /// impl<K, T> Meter<K, Vec<T>> for VecLen {
229    ///     // Use `Measure = usize` or implement `CountableMeter` as well.
230    ///     type Measure = usize;
231    ///     fn measure<Q: ?Sized>(&self, _: &Q, v: &Vec<T>) -> usize
232    ///         where K: Borrow<Q>
233    ///     {
234    ///         v.len()
235    ///     }
236    /// }
237    ///
238    /// let mut cache = LruCache::with_meter(5, VecLen);
239    /// cache.insert(1, vec![1, 2]);
240    /// assert_eq!(cache.size(), 2);
241    /// cache.insert(2, vec![3, 4]);
242    /// cache.insert(3, vec![5, 6]);
243    /// assert_eq!(cache.size(), 4);
244    /// assert_eq!(cache.len(), 2);
245    /// ```
246    pub fn with_meter(capacity: u64, meter: M) -> LruCache<K, V, RandomState, M> {
247        LruCache {
248            map: LinkedHashMap::new(),
249            current_measure: Default::default(),
250            max_capacity: capacity,
251            meter,
252        }
253    }
254}
255
256impl<K: Eq + Hash, V, S: BuildHasher> LruCache<K, V, S, Count> {
257    /// Creates an empty cache that can hold at most `capacity` items with the given hash builder.
258    pub fn with_hasher(capacity: u64, hash_builder: S) -> LruCache<K, V, S, Count> {
259        LruCache {
260            map: LinkedHashMap::with_hasher(hash_builder),
261            current_measure: (),
262            max_capacity: capacity,
263            meter: Count,
264        }
265    }
266
267    /// Returns a mutable reference to the value corresponding to the given key in the cache, if
268    /// any.
269    ///
270    /// Note that this method is not available for cache objects using `Meter` implementations
271    /// other than `Count`.
272    ///
273    /// # Examples
274    ///
275    /// ```rust,ignore
276    /// use lru_cache::LruCache;
277    ///
278    /// let mut cache = LruCache::new(2);
279    ///
280    /// cache.insert(1, "a");
281    /// cache.insert(2, "b");
282    /// cache.insert(2, "c");
283    /// cache.insert(3, "d");
284    ///
285    /// assert_eq!(cache.get_mut(&1), None);
286    /// assert_eq!(cache.get_mut(&2), Some(&mut "c"));
287    /// ```
288    pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V>
289    where
290        K: Borrow<Q>,
291        Q: Hash + Eq,
292    {
293        self.map.get_refresh(k)
294    }
295
296    /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order,
297    /// with mutable references to the values.
298    ///
299    /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
300    /// Note that this method is not available for cache objects using `Meter` implementations.
301    /// other than `Count`.
302    ///
303    /// # Examples
304    ///
305    /// ```rust,ignore
306    /// use lru_cache::LruCache;
307    ///
308    /// let mut cache = LruCache::new(2);
309    ///
310    /// cache.insert(1, 10);
311    /// cache.insert(2, 20);
312    /// cache.insert(3, 30);
313    ///
314    /// let mut n = 2;
315    ///
316    /// for (k, v) in cache.iter_mut() {
317    ///     assert_eq!(*k, n);
318    ///     assert_eq!(*v, n * 10);
319    ///     *v *= 10;
320    ///     n += 1;
321    /// }
322    ///
323    /// assert_eq!(n, 4);
324    /// assert_eq!(cache.get_mut(&2), Some(&mut 200));
325    /// assert_eq!(cache.get_mut(&3), Some(&mut 300));
326    /// ```
327    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
328        self.internal_iter_mut()
329    }
330}
331
332impl<K: Eq + Hash, V, S: BuildHasher, M: CountableMeter<K, V>> LruCache<K, V, S, M> {
333    /// Creates an empty cache that can hold at most `capacity` as measured by `meter` with the
334    /// given hash builder.
335    pub fn with_meter_and_hasher(capacity: u64, meter: M, hash_builder: S) -> Self {
336        LruCache {
337            map: LinkedHashMap::with_hasher(hash_builder),
338            current_measure: Default::default(),
339            max_capacity: capacity,
340            meter,
341        }
342    }
343
344    /// Returns the maximum size of the key-value pairs the cache can hold, as measured by the
345    /// `Meter` used by the cache.
346    ///
347    /// # Examples
348    ///
349    /// ```rust,ignore
350    /// use lru_cache::LruCache;
351    /// let mut cache: LruCache<i32, &str> = LruCache::new(2);
352    /// assert_eq!(cache.capacity(), 2);
353    /// ```
354    pub fn capacity(&self) -> u64 {
355        self.max_capacity
356    }
357
358    /// Checks if the map contains the given key.
359    ///
360    /// # Examples
361    ///
362    /// ```rust,ignore
363    /// use lru_cache::LruCache;
364    ///
365    /// let mut cache = LruCache::new(1);
366    ///
367    /// cache.insert(1, "a");
368    /// assert_eq!(cache.contains_key(&1), true);
369    /// ```
370    pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool
371    where
372        K: Borrow<Q>,
373        Q: Hash + Eq,
374    {
375        self.map.contains_key(key)
376    }
377
378    pub fn get<Q: ?Sized>(&mut self, k: &Q) -> Option<&V>
379    where
380        K: Borrow<Q>,
381        Q: Hash + Eq,
382    {
383        self.map.get_refresh(k).map(|v| v as &V)
384    }
385
386    /// Inserts a key-value pair into the cache. If the key already existed, the old value is
387    /// returned.
388    ///
389    /// # Examples
390    ///
391    /// ```rust,ignore
392    /// use lru_cache::LruCache;
393    ///
394    /// let mut cache = LruCache::new(2);
395    ///
396    /// cache.insert(1, "a");
397    /// cache.insert(2, "b");
398    /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
399    /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
400    /// ```
401    pub fn insert(&mut self, k: K, v: V) -> Option<V> {
402        let new_size = self.meter.measure(&k, &v);
403        self.current_measure = self.meter.add(self.current_measure, new_size);
404        if let Some(old) = self.map.get(&k) {
405            self.current_measure = self
406                .meter
407                .sub(self.current_measure, self.meter.measure(&k, old));
408        }
409        let old_val = self.map.insert(k, v);
410        while self.size() > self.capacity() {
411            self.remove_lru();
412        }
413        old_val
414    }
415
416    /// Removes the given key from the cache and returns its corresponding value.
417    ///
418    /// # Examples
419    ///
420    /// ```rust,ignore
421    /// use lru_cache::LruCache;
422    ///
423    /// let mut cache = LruCache::new(2);
424    ///
425    /// cache.insert(2, "a");
426    ///
427    /// assert_eq!(cache.remove(&1), None);
428    /// assert_eq!(cache.remove(&2), Some("a"));
429    /// assert_eq!(cache.remove(&2), None);
430    /// assert_eq!(cache.len(), 0);
431    /// ```
432    pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V>
433    where
434        K: Borrow<Q>,
435        Q: Hash + Eq,
436    {
437        self.map.remove(k).map(|v| {
438            self.current_measure = self
439                .meter
440                .sub(self.current_measure, self.meter.measure(k, &v));
441            v
442        })
443    }
444
445    /// Sets the size of the key-value pairs the cache can hold, as measured by the `Meter` used by
446    /// the cache.
447    ///
448    /// Removes least-recently-used key-value pairs if necessary.
449    ///
450    /// # Examples
451    ///
452    /// ```rust,ignore
453    /// use lru_cache::LruCache;
454    ///
455    /// let mut cache = LruCache::new(2);
456    ///
457    /// cache.insert(1, "a");
458    /// cache.insert(2, "b");
459    /// cache.insert(3, "c");
460    ///
461    /// assert_eq!(cache.get_mut(&1), None);
462    /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
463    /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
464    ///
465    /// cache.set_capacity(3);
466    /// cache.insert(1, "a");
467    /// cache.insert(2, "b");
468    ///
469    /// assert_eq!(cache.get_mut(&1), Some(&mut "a"));
470    /// assert_eq!(cache.get_mut(&2), Some(&mut "b"));
471    /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
472    ///
473    /// cache.set_capacity(1);
474    ///
475    /// assert_eq!(cache.get_mut(&1), None);
476    /// assert_eq!(cache.get_mut(&2), None);
477    /// assert_eq!(cache.get_mut(&3), Some(&mut "c"));
478    /// ```
479    pub fn set_capacity(&mut self, capacity: u64) {
480        while self.size() > capacity {
481            self.remove_lru();
482        }
483        self.max_capacity = capacity;
484    }
485
486    /// Removes and returns the least recently used key-value pair as a tuple.
487    ///
488    /// # Examples
489    ///
490    /// ```rust,ignore
491    /// use lru_cache::LruCache;
492    ///
493    /// let mut cache = LruCache::new(2);
494    ///
495    /// cache.insert(1, "a");
496    /// cache.insert(2, "b");
497    ///
498    /// assert_eq!(cache.remove_lru(), Some((1, "a")));
499    /// assert_eq!(cache.len(), 1);
500    /// ```
501    #[inline]
502    pub fn remove_lru(&mut self) -> Option<(K, V)> {
503        self.map.pop_front().map(|(k, v)| {
504            self.current_measure = self
505                .meter
506                .sub(self.current_measure, self.meter.measure(&k, &v));
507            (k, v)
508        })
509    }
510
511    /// Returns the number of key-value pairs in the cache.
512    pub fn len(&self) -> usize {
513        self.map.len()
514    }
515
516    /// Returns the size of all the key-value pairs in the cache, as measured by the `Meter` used
517    /// by the cache.
518    pub fn size(&self) -> u64 {
519        self.meter
520            .size(self.current_measure)
521            .unwrap_or_else(|| self.map.len() as u64)
522    }
523
524    /// Returns `true` if the cache contains no key-value pairs.
525    pub fn is_empty(&self) -> bool {
526        self.map.is_empty()
527    }
528
529    /// Removes all key-value pairs from the cache.
530    pub fn clear(&mut self) {
531        self.map.clear();
532        self.current_measure = Default::default();
533    }
534
535    /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order.
536    ///
537    /// Accessing the cache through the iterator does _not_ affect the cache's LRU state.
538    ///
539    /// # Examples
540    ///
541    /// ```rust,ignore
542    /// use lru_cache::LruCache;
543    ///
544    /// let mut cache = LruCache::new(2);
545    ///
546    /// cache.insert(1, 10);
547    /// cache.insert(2, 20);
548    /// cache.insert(3, 30);
549    ///
550    /// let kvs: Vec<_> = cache.iter().collect();
551    /// assert_eq!(kvs, [(&2, &20), (&3, &30)]);
552    /// ```
553    pub fn iter(&self) -> Iter<'_, K, V> {
554        Iter(self.map.iter())
555    }
556
557    fn internal_iter_mut(&mut self) -> IterMut<'_, K, V> {
558        IterMut(self.map.iter_mut())
559    }
560}
561
562impl<K: Eq + Hash, V, S: BuildHasher, M: CountableMeter<K, V>> Extend<(K, V)>
563    for LruCache<K, V, S, M>
564{
565    fn extend<I: IntoIterator<Item = (K, V)>>(&mut self, iter: I) {
566        for (k, v) in iter {
567            self.insert(k, v);
568        }
569    }
570}
571
572impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher, M: CountableMeter<K, V>> fmt::Debug
573    for LruCache<K, V, S, M>
574{
575    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
576        f.debug_map().entries(self.iter().rev()).finish()
577    }
578}
579
580impl<K: Eq + Hash, V, S: BuildHasher, M: CountableMeter<K, V>> IntoIterator
581    for LruCache<K, V, S, M>
582{
583    type Item = (K, V);
584    type IntoIter = IntoIter<K, V>;
585
586    fn into_iter(self) -> IntoIter<K, V> {
587        IntoIter(self.map.into_iter())
588    }
589}
590
591impl<'a, K: Eq + Hash, V, S: BuildHasher, M: CountableMeter<K, V>> IntoIterator
592    for &'a LruCache<K, V, S, M>
593{
594    type Item = (&'a K, &'a V);
595    type IntoIter = Iter<'a, K, V>;
596    fn into_iter(self) -> Iter<'a, K, V> {
597        self.iter()
598    }
599}
600
601impl<'a, K: Eq + Hash, V, S: BuildHasher, M: CountableMeter<K, V>> IntoIterator
602    for &'a mut LruCache<K, V, S, M>
603{
604    type Item = (&'a K, &'a mut V);
605    type IntoIter = IterMut<'a, K, V>;
606    fn into_iter(self) -> IterMut<'a, K, V> {
607        self.internal_iter_mut()
608    }
609}
610
611/// An iterator over a cache's key-value pairs in least- to most-recently-used order.
612///
613/// # Examples
614///
615/// ```rust,ignore
616/// use lru_cache::LruCache;
617///
618/// let mut cache = LruCache::new(2);
619///
620/// cache.insert(1, 10);
621/// cache.insert(2, 20);
622/// cache.insert(3, 30);
623///
624/// let mut n = 2;
625///
626/// for (k, v) in cache {
627///     assert_eq!(k, n);
628///     assert_eq!(v, n * 10);
629///     n += 1;
630/// }
631///
632/// assert_eq!(n, 4);
633/// ```
634#[derive(Clone)]
635pub struct IntoIter<K, V>(linked_hash_map::IntoIter<K, V>);
636
637impl<K, V> Iterator for IntoIter<K, V> {
638    type Item = (K, V);
639
640    fn next(&mut self) -> Option<(K, V)> {
641        self.0.next()
642    }
643
644    fn size_hint(&self) -> (usize, Option<usize>) {
645        self.0.size_hint()
646    }
647}
648
649impl<K, V> DoubleEndedIterator for IntoIter<K, V> {
650    fn next_back(&mut self) -> Option<(K, V)> {
651        self.0.next_back()
652    }
653}
654
655impl<K, V> ExactSizeIterator for IntoIter<K, V> {
656    fn len(&self) -> usize {
657        self.0.len()
658    }
659}
660
661/// An iterator over a cache's key-value pairs in least- to most-recently-used order.
662///
663/// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
664pub struct Iter<'a, K, V>(linked_hash_map::Iter<'a, K, V>);
665
666impl<'a, K, V> Clone for Iter<'a, K, V> {
667    fn clone(&self) -> Iter<'a, K, V> {
668        Iter(self.0.clone())
669    }
670}
671
672impl<'a, K, V> Iterator for Iter<'a, K, V> {
673    type Item = (&'a K, &'a V);
674    fn next(&mut self) -> Option<(&'a K, &'a V)> {
675        self.0.next()
676    }
677    fn size_hint(&self) -> (usize, Option<usize>) {
678        self.0.size_hint()
679    }
680}
681
682impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> {
683    fn next_back(&mut self) -> Option<(&'a K, &'a V)> {
684        self.0.next_back()
685    }
686}
687
688impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> {
689    fn len(&self) -> usize {
690        self.0.len()
691    }
692}
693
694/// An iterator over a cache's key-value pairs in least- to most-recently-used order with mutable
695/// references to the values.
696///
697/// Accessing a cache through the iterator does _not_ affect the cache's LRU state.
698pub struct IterMut<'a, K, V>(linked_hash_map::IterMut<'a, K, V>);
699
700impl<'a, K, V> Iterator for IterMut<'a, K, V> {
701    type Item = (&'a K, &'a mut V);
702    fn next(&mut self) -> Option<(&'a K, &'a mut V)> {
703        self.0.next()
704    }
705    fn size_hint(&self) -> (usize, Option<usize>) {
706        self.0.size_hint()
707    }
708}
709
710impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> {
711    fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> {
712        self.0.next_back()
713    }
714}
715
716impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> {
717    fn len(&self) -> usize {
718        self.0.len()
719    }
720}
721
722#[cfg(test)]
723mod tests {
724    use super::{LruCache, Meter};
725    use std::borrow::Borrow;
726
727    #[test]
728    fn test_put_and_get() {
729        let mut cache = LruCache::new(2);
730        cache.insert(1, 10);
731        cache.insert(2, 20);
732        assert_eq!(cache.get_mut(&1), Some(&mut 10));
733        assert_eq!(cache.get_mut(&2), Some(&mut 20));
734        assert_eq!(cache.len(), 2);
735        assert_eq!(cache.size(), 2);
736    }
737
738    #[test]
739    fn test_put_update() {
740        let mut cache = LruCache::new(1);
741        cache.insert("1", 10);
742        cache.insert("1", 19);
743        assert_eq!(cache.get_mut("1"), Some(&mut 19));
744        assert_eq!(cache.len(), 1);
745    }
746
747    #[test]
748    fn test_contains_key() {
749        let mut cache = LruCache::new(1);
750        cache.insert("1", 10);
751        assert_eq!(cache.contains_key("1"), true);
752    }
753
754    #[test]
755    fn test_expire_lru() {
756        let mut cache = LruCache::new(2);
757        cache.insert("foo1", "bar1");
758        cache.insert("foo2", "bar2");
759        cache.insert("foo3", "bar3");
760        assert!(cache.get_mut("foo1").is_none());
761        cache.insert("foo2", "bar2update");
762        cache.insert("foo4", "bar4");
763        assert!(cache.get_mut("foo3").is_none());
764    }
765
766    #[test]
767    fn test_pop() {
768        let mut cache = LruCache::new(2);
769        cache.insert(1, 10);
770        cache.insert(2, 20);
771        assert_eq!(cache.len(), 2);
772        let opt1 = cache.remove(&1);
773        assert!(opt1.is_some());
774        assert_eq!(opt1.unwrap(), 10);
775        assert!(cache.get_mut(&1).is_none());
776        assert_eq!(cache.len(), 1);
777    }
778
779    #[test]
780    fn test_change_capacity() {
781        let mut cache = LruCache::new(2);
782        assert_eq!(cache.capacity(), 2);
783        cache.insert(1, 10);
784        cache.insert(2, 20);
785        cache.set_capacity(1);
786        assert!(cache.get_mut(&1).is_none());
787        assert_eq!(cache.capacity(), 1);
788    }
789
790    #[test]
791    fn test_debug() {
792        let mut cache = LruCache::new(3);
793        cache.insert(1, 10);
794        cache.insert(2, 20);
795        cache.insert(3, 30);
796        assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}");
797        cache.insert(2, 22);
798        assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}");
799        cache.insert(6, 60);
800        assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}");
801        cache.get_mut(&3);
802        assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}");
803        cache.set_capacity(2);
804        assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}");
805    }
806
807    #[test]
808    fn test_remove() {
809        let mut cache = LruCache::new(3);
810        cache.insert(1, 10);
811        cache.insert(2, 20);
812        cache.insert(3, 30);
813        cache.insert(4, 40);
814        cache.insert(5, 50);
815        cache.remove(&3);
816        cache.remove(&4);
817        assert!(cache.get_mut(&3).is_none());
818        assert!(cache.get_mut(&4).is_none());
819        cache.insert(6, 60);
820        cache.insert(7, 70);
821        cache.insert(8, 80);
822        assert!(cache.get_mut(&5).is_none());
823        assert_eq!(cache.get_mut(&6), Some(&mut 60));
824        assert_eq!(cache.get_mut(&7), Some(&mut 70));
825        assert_eq!(cache.get_mut(&8), Some(&mut 80));
826    }
827
828    #[test]
829    fn test_clear() {
830        let mut cache = LruCache::new(2);
831        cache.insert(1, 10);
832        cache.insert(2, 20);
833        cache.clear();
834        assert!(cache.get_mut(&1).is_none());
835        assert!(cache.get_mut(&2).is_none());
836        assert_eq!(format!("{:?}", cache), "{}");
837    }
838
839    #[test]
840    fn test_iter() {
841        let mut cache = LruCache::new(3);
842        cache.insert(1, 10);
843        cache.insert(2, 20);
844        cache.insert(3, 30);
845        cache.insert(4, 40);
846        cache.insert(5, 50);
847        assert_eq!(
848            cache.iter().collect::<Vec<_>>(),
849            [(&3, &30), (&4, &40), (&5, &50)]
850        );
851        assert_eq!(
852            cache.iter_mut().collect::<Vec<_>>(),
853            [(&3, &mut 30), (&4, &mut 40), (&5, &mut 50)]
854        );
855        assert_eq!(
856            cache.iter().rev().collect::<Vec<_>>(),
857            [(&5, &50), (&4, &40), (&3, &30)]
858        );
859        assert_eq!(
860            cache.iter_mut().rev().collect::<Vec<_>>(),
861            [(&5, &mut 50), (&4, &mut 40), (&3, &mut 30)]
862        );
863    }
864
865    struct VecLen;
866
867    impl<K, T> Meter<K, Vec<T>> for VecLen {
868        type Measure = usize;
869        fn measure<Q: ?Sized>(&self, _: &Q, v: &Vec<T>) -> usize
870        where
871            K: Borrow<Q>,
872        {
873            v.len()
874        }
875    }
876
877    #[test]
878    fn test_metered_cache() {
879        let mut cache = LruCache::with_meter(5, VecLen);
880        cache.insert("foo1", vec![1, 2]);
881        assert_eq!(cache.size(), 2);
882        cache.insert("foo2", vec![3, 4]);
883        cache.insert("foo3", vec![5, 6]);
884        assert_eq!(cache.size(), 4);
885        assert!(!cache.contains_key("foo1"));
886        cache.insert("foo2", vec![7, 8]);
887        cache.insert("foo4", vec![9, 10]);
888        assert_eq!(cache.size(), 4);
889        assert!(!cache.contains_key("foo3"));
890        assert_eq!(cache.get("foo2"), Some(&vec![7, 8]));
891    }
892
893    #[test]
894    fn test_metered_cache_reinsert_larger() {
895        let mut cache = LruCache::with_meter(5, VecLen);
896        cache.insert("foo1", vec![1, 2]);
897        cache.insert("foo2", vec![3, 4]);
898        assert_eq!(cache.size(), 4);
899        cache.insert("foo2", vec![5, 6, 7, 8]);
900        assert_eq!(cache.size(), 4);
901        assert!(!cache.contains_key("foo1"));
902    }
903
904    #[test]
905    fn test_metered_cache_oversize() {
906        let mut cache = LruCache::with_meter(2, VecLen);
907        cache.insert("foo1", vec![1, 2]);
908        cache.insert("foo2", vec![3, 4, 5, 6]);
909        assert_eq!(cache.size(), 0);
910        assert!(!cache.contains_key("foo1"));
911        assert!(!cache.contains_key("foo2"));
912    }
913
914    #[cfg(feature = "heapsize")]
915    #[test]
916    fn test_heapsize_cache() {
917        use super::HeapSize;
918
919        let mut cache = LruCache::<&str, (u8, u8, u8), _, _>::with_meter(8, HeapSize);
920        cache.insert("foo1", (1, 2, 3));
921        cache.insert("foo2", (4, 5, 6));
922        cache.insert("foo3", (7, 8, 9));
923        assert!(!cache.contains_key("foo1"));
924        cache.insert("foo2", (10, 11, 12));
925        cache.insert("foo4", (13, 14, 15));
926        assert!(!cache.contains_key("foo3"));
927    }
928}
lru_disk_cache/lru_cache.rs

lru_disk_cache/
lru_cache.rs
