diff options
Diffstat (limited to 'src/lib.rs')
| -rw-r--r-- | src/lib.rs | 567 |
1 files changed, 567 insertions, 0 deletions
diff --git a/src/lib.rs b/src/lib.rs new file mode 100644 index 0000000..fcf9b61 --- /dev/null +++ b/src/lib.rs @@ -0,0 +1,567 @@ +// Copyright 2015 The Rust Project Developers. See the COPYRIGHT +// file at the top-level directory of this distribution and at +// http://rust-lang.org/COPYRIGHT. +// +// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or +// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license +// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your +// option. This file may not be copied, modified, or distributed +// except according to those terms. + +//! A cache that holds a limited number of key-value pairs. When the +//! capacity of the cache is exceeded, the least-recently-used +//! (where "used" means a look-up or putting the pair into the cache) +//! pair is automatically removed. +//! +//! # Examples +//! +//! ``` +//! use lru_cache::LruCache; +//! +//! let mut cache = LruCache::new(2); +//! +//! cache.insert(1, 10); +//! cache.insert(2, 20); +//! cache.insert(3, 30); +//! assert!(cache.get_mut(&1).is_none()); +//! assert_eq!(*cache.get_mut(&2).unwrap(), 20); +//! assert_eq!(*cache.get_mut(&3).unwrap(), 30); +//! +//! cache.insert(2, 22); +//! assert_eq!(*cache.get_mut(&2).unwrap(), 22); +//! +//! cache.insert(6, 60); +//! assert!(cache.get_mut(&3).is_none()); +//! +//! cache.set_capacity(1); +//! assert!(cache.get_mut(&2).is_none()); +//! ``` + +extern crate linked_hash_map; + +use std::borrow::Borrow; +use std::collections::hash_map::RandomState; +use std::fmt; +use std::hash::{Hash, BuildHasher}; + +use linked_hash_map::LinkedHashMap; + +#[cfg(feature = "heapsize_impl")] +mod heapsize; + +// FIXME(conventions): implement indexing? + +/// An LRU cache. +#[derive(Clone)] +pub struct LruCache<K: Eq + Hash, V, S: BuildHasher = RandomState> { + map: LinkedHashMap<K, V, S>, + max_size: usize, +} + +impl<K: Eq + Hash, V> LruCache<K, V> { + /// Creates an empty cache that can hold at most `capacity` items. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// let mut cache: LruCache<i32, &str> = LruCache::new(10); + /// ``` + pub fn new(capacity: usize) -> Self { + LruCache { + map: LinkedHashMap::new(), + max_size: capacity, + } + } +} + +impl<K: Eq + Hash, V, S: BuildHasher> LruCache<K, V, S> { + /// Creates an empty cache that can hold at most `capacity` items with the given hash builder. + pub fn with_hasher(capacity: usize, hash_builder: S) -> Self { + LruCache { map: LinkedHashMap::with_hasher(hash_builder), max_size: capacity } + } + + /// Checks if the map contains the given key. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(1); + /// + /// cache.insert(1, "a"); + /// assert_eq!(cache.contains_key(&1), true); + /// ``` + pub fn contains_key<Q: ?Sized>(&mut self, key: &Q) -> bool + where K: Borrow<Q>, + Q: Hash + Eq + { + self.get_mut(key).is_some() + } + + /// Inserts a key-value pair into the cache. If the key already existed, the old value is + /// returned. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, "a"); + /// cache.insert(2, "b"); + /// assert_eq!(cache.get_mut(&1), Some(&mut "a")); + /// assert_eq!(cache.get_mut(&2), Some(&mut "b")); + /// ``` + pub fn insert(&mut self, k: K, v: V) -> Option<V> { + let old_val = self.map.insert(k, v); + if self.len() > self.capacity() { + self.remove_lru(); + } + old_val + } + + /// Returns a mutable reference to the value corresponding to the given key in the cache, if + /// any. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, "a"); + /// cache.insert(2, "b"); + /// cache.insert(2, "c"); + /// cache.insert(3, "d"); + /// + /// assert_eq!(cache.get_mut(&1), None); + /// assert_eq!(cache.get_mut(&2), Some(&mut "c")); + /// ``` + pub fn get_mut<Q: ?Sized>(&mut self, k: &Q) -> Option<&mut V> + where K: Borrow<Q>, + Q: Hash + Eq + { + self.map.get_refresh(k) + } + + /// Removes the given key from the cache and returns its corresponding value. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(2, "a"); + /// + /// assert_eq!(cache.remove(&1), None); + /// assert_eq!(cache.remove(&2), Some("a")); + /// assert_eq!(cache.remove(&2), None); + /// assert_eq!(cache.len(), 0); + /// ``` + pub fn remove<Q: ?Sized>(&mut self, k: &Q) -> Option<V> + where K: Borrow<Q>, + Q: Hash + Eq + { + self.map.remove(k) + } + + /// Returns the maximum number of key-value pairs the cache can hold. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// let mut cache: LruCache<i32, &str> = LruCache::new(2); + /// assert_eq!(cache.capacity(), 2); + /// ``` + pub fn capacity(&self) -> usize { + self.max_size + } + + /// Sets the number of key-value pairs the cache can hold. Removes + /// least-recently-used key-value pairs if necessary. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, "a"); + /// cache.insert(2, "b"); + /// cache.insert(3, "c"); + /// + /// assert_eq!(cache.get_mut(&1), None); + /// assert_eq!(cache.get_mut(&2), Some(&mut "b")); + /// assert_eq!(cache.get_mut(&3), Some(&mut "c")); + /// + /// cache.set_capacity(3); + /// cache.insert(1, "a"); + /// cache.insert(2, "b"); + /// + /// assert_eq!(cache.get_mut(&1), Some(&mut "a")); + /// assert_eq!(cache.get_mut(&2), Some(&mut "b")); + /// assert_eq!(cache.get_mut(&3), Some(&mut "c")); + /// + /// cache.set_capacity(1); + /// + /// assert_eq!(cache.get_mut(&1), None); + /// assert_eq!(cache.get_mut(&2), None); + /// assert_eq!(cache.get_mut(&3), Some(&mut "c")); + /// ``` + pub fn set_capacity(&mut self, capacity: usize) { + for _ in capacity..self.len() { + self.remove_lru(); + } + self.max_size = capacity; + } + + /// Removes and returns the least recently used key-value pair as a tuple. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, "a"); + /// cache.insert(2, "b"); + /// + /// assert_eq!(cache.remove_lru(), Some((1, "a"))); + /// assert_eq!(cache.len(), 1); + /// ``` + #[inline] + pub fn remove_lru(&mut self) -> Option<(K, V)> { + self.map.pop_front() + } + + /// Returns the number of key-value pairs in the cache. + pub fn len(&self) -> usize { self.map.len() } + + /// Returns `true` if the cache contains no key-value pairs. + pub fn is_empty(&self) -> bool { self.map.is_empty() } + + /// Removes all key-value pairs from the cache. + pub fn clear(&mut self) { self.map.clear(); } + + /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order. + /// + /// Accessing the cache through the iterator does _not_ affect the cache's LRU state. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, 10); + /// cache.insert(2, 20); + /// cache.insert(3, 30); + /// + /// let kvs: Vec<_> = cache.iter().collect(); + /// assert_eq!(kvs, [(&2, &20), (&3, &30)]); + /// ``` + pub fn iter(&self) -> Iter<K, V> { Iter(self.map.iter()) } + + /// Returns an iterator over the cache's key-value pairs in least- to most-recently-used order, + /// with mutable references to the values. + /// + /// Accessing the cache through the iterator does _not_ affect the cache's LRU state. + /// + /// # Examples + /// + /// ``` + /// use lru_cache::LruCache; + /// + /// let mut cache = LruCache::new(2); + /// + /// cache.insert(1, 10); + /// cache.insert(2, 20); + /// cache.insert(3, 30); + /// + /// let mut n = 2; + /// + /// for (k, v) in cache.iter_mut() { + /// assert_eq!(*k, n); + /// assert_eq!(*v, n * 10); + /// *v *= 10; + /// n += 1; + /// } + /// + /// assert_eq!(n, 4); + /// assert_eq!(cache.get_mut(&2), Some(&mut 200)); + /// assert_eq!(cache.get_mut(&3), Some(&mut 300)); + /// ``` + pub fn iter_mut(&mut self) -> IterMut<K, V> { IterMut(self.map.iter_mut()) } +} + +impl<K: Eq + Hash, V, S: BuildHasher> Extend<(K, V)> for LruCache<K, V, S> { + fn extend<I: IntoIterator<Item=(K, V)>>(&mut self, iter: I) { + for (k, v) in iter { + self.insert(k, v); + } + } +} + +impl<K: fmt::Debug + Eq + Hash, V: fmt::Debug, S: BuildHasher> fmt::Debug for LruCache<K, V, S> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + f.debug_map().entries(self.iter().rev()).finish() + } +} + +impl<K: Eq + Hash, V, S: BuildHasher> IntoIterator for LruCache<K, V, S> { + type Item = (K, V); + type IntoIter = IntoIter<K, V>; + + fn into_iter(self) -> IntoIter<K, V> { + IntoIter(self.map.into_iter()) + } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a LruCache<K, V, S> { + type Item = (&'a K, &'a V); + type IntoIter = Iter<'a, K, V>; + fn into_iter(self) -> Iter<'a, K, V> { self.iter() } +} + +impl<'a, K: Eq + Hash, V, S: BuildHasher> IntoIterator for &'a mut LruCache<K, V, S> { + type Item = (&'a K, &'a mut V); + type IntoIter = IterMut<'a, K, V>; + fn into_iter(self) -> IterMut<'a, K, V> { self.iter_mut() } +} + +/// An iterator over a cache's key-value pairs in least- to most-recently-used order. +/// +/// # Examples +/// +/// ``` +/// use lru_cache::LruCache; +/// +/// let mut cache = LruCache::new(2); +/// +/// cache.insert(1, 10); +/// cache.insert(2, 20); +/// cache.insert(3, 30); +/// +/// let mut n = 2; +/// +/// for (k, v) in cache { +/// assert_eq!(k, n); +/// assert_eq!(v, n * 10); +/// n += 1; +/// } +/// +/// assert_eq!(n, 4); +/// ``` +#[derive(Clone)] +pub struct IntoIter<K, V>(linked_hash_map::IntoIter<K, V>); + +impl<K, V> Iterator for IntoIter<K, V> { + type Item = (K, V); + + fn next(&mut self) -> Option<(K, V)> { + self.0.next() + } + + fn size_hint(&self) -> (usize, Option<usize>) { + self.0.size_hint() + } +} + +impl<K, V> DoubleEndedIterator for IntoIter<K, V> { + fn next_back(&mut self) -> Option<(K, V)> { + self.0.next_back() + } +} + +impl<K, V> ExactSizeIterator for IntoIter<K, V> { + fn len(&self) -> usize { + self.0.len() + } +} + +/// An iterator over a cache's key-value pairs in least- to most-recently-used order. +/// +/// Accessing a cache through the iterator does _not_ affect the cache's LRU state. +pub struct Iter<'a, K: 'a, V: 'a>(linked_hash_map::Iter<'a, K, V>); + +impl<'a, K, V> Clone for Iter<'a, K, V> { + fn clone(&self) -> Iter<'a, K, V> { Iter(self.0.clone()) } +} + +impl<'a, K, V> Iterator for Iter<'a, K, V> { + type Item = (&'a K, &'a V); + fn next(&mut self) -> Option<(&'a K, &'a V)> { self.0.next() } + fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } +} + +impl<'a, K, V> DoubleEndedIterator for Iter<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a V)> { self.0.next_back() } +} + +impl<'a, K, V> ExactSizeIterator for Iter<'a, K, V> { + fn len(&self) -> usize { self.0.len() } +} + +/// An iterator over a cache's key-value pairs in least- to most-recently-used order with mutable +/// references to the values. +/// +/// Accessing a cache through the iterator does _not_ affect the cache's LRU state. +pub struct IterMut<'a, K: 'a, V: 'a>(linked_hash_map::IterMut<'a, K, V>); + +impl<'a, K, V> Iterator for IterMut<'a, K, V> { + type Item = (&'a K, &'a mut V); + fn next(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next() } + fn size_hint(&self) -> (usize, Option<usize>) { self.0.size_hint() } +} + +impl<'a, K, V> DoubleEndedIterator for IterMut<'a, K, V> { + fn next_back(&mut self) -> Option<(&'a K, &'a mut V)> { self.0.next_back() } +} + +impl<'a, K, V> ExactSizeIterator for IterMut<'a, K, V> { + fn len(&self) -> usize { self.0.len() } +} + +#[cfg(test)] +mod tests { + use super::LruCache; + + #[test] + fn test_put_and_get() { + let mut cache = LruCache::new(2); + cache.insert(1, 10); + cache.insert(2, 20); + assert_eq!(cache.get_mut(&1), Some(&mut 10)); + assert_eq!(cache.get_mut(&2), Some(&mut 20)); + assert_eq!(cache.len(), 2); + } + + #[test] + fn test_put_update() { + let mut cache = LruCache::new(1); + cache.insert("1", 10); + cache.insert("1", 19); + assert_eq!(cache.get_mut("1"), Some(&mut 19)); + assert_eq!(cache.len(), 1); + } + + #[test] + fn test_contains_key() { + let mut cache = LruCache::new(1); + cache.insert("1", 10); + assert_eq!(cache.contains_key("1"), true); + } + + #[test] + fn test_expire_lru() { + let mut cache = LruCache::new(2); + cache.insert("foo1", "bar1"); + cache.insert("foo2", "bar2"); + cache.insert("foo3", "bar3"); + assert!(cache.get_mut("foo1").is_none()); + cache.insert("foo2", "bar2update"); + cache.insert("foo4", "bar4"); + assert!(cache.get_mut("foo3").is_none()); + } + + #[test] + fn test_pop() { + let mut cache = LruCache::new(2); + cache.insert(1, 10); + cache.insert(2, 20); + assert_eq!(cache.len(), 2); + let opt1 = cache.remove(&1); + assert!(opt1.is_some()); + assert_eq!(opt1.unwrap(), 10); + assert!(cache.get_mut(&1).is_none()); + assert_eq!(cache.len(), 1); + } + + #[test] + fn test_change_capacity() { + let mut cache = LruCache::new(2); + assert_eq!(cache.capacity(), 2); + cache.insert(1, 10); + cache.insert(2, 20); + cache.set_capacity(1); + assert!(cache.get_mut(&1).is_none()); + assert_eq!(cache.capacity(), 1); + } + + #[test] + fn test_debug() { + let mut cache = LruCache::new(3); + cache.insert(1, 10); + cache.insert(2, 20); + cache.insert(3, 30); + assert_eq!(format!("{:?}", cache), "{3: 30, 2: 20, 1: 10}"); + cache.insert(2, 22); + assert_eq!(format!("{:?}", cache), "{2: 22, 3: 30, 1: 10}"); + cache.insert(6, 60); + assert_eq!(format!("{:?}", cache), "{6: 60, 2: 22, 3: 30}"); + cache.get_mut(&3); + assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60, 2: 22}"); + cache.set_capacity(2); + assert_eq!(format!("{:?}", cache), "{3: 30, 6: 60}"); + } + + #[test] + fn test_remove() { + let mut cache = LruCache::new(3); + cache.insert(1, 10); + cache.insert(2, 20); + cache.insert(3, 30); + cache.insert(4, 40); + cache.insert(5, 50); + cache.remove(&3); + cache.remove(&4); + assert!(cache.get_mut(&3).is_none()); + assert!(cache.get_mut(&4).is_none()); + cache.insert(6, 60); + cache.insert(7, 70); + cache.insert(8, 80); + assert!(cache.get_mut(&5).is_none()); + assert_eq!(cache.get_mut(&6), Some(&mut 60)); + assert_eq!(cache.get_mut(&7), Some(&mut 70)); + assert_eq!(cache.get_mut(&8), Some(&mut 80)); + } + + #[test] + fn test_clear() { + let mut cache = LruCache::new(2); + cache.insert(1, 10); + cache.insert(2, 20); + cache.clear(); + assert!(cache.get_mut(&1).is_none()); + assert!(cache.get_mut(&2).is_none()); + assert_eq!(format!("{:?}", cache), "{}"); + } + + #[test] + fn test_iter() { + let mut cache = LruCache::new(3); + cache.insert(1, 10); + cache.insert(2, 20); + cache.insert(3, 30); + cache.insert(4, 40); + cache.insert(5, 50); + assert_eq!(cache.iter().collect::<Vec<_>>(), + [(&3, &30), (&4, &40), (&5, &50)]); + assert_eq!(cache.iter_mut().collect::<Vec<_>>(), + [(&3, &mut 30), (&4, &mut 40), (&5, &mut 50)]); + assert_eq!(cache.iter().rev().collect::<Vec<_>>(), + [(&5, &50), (&4, &40), (&3, &30)]); + assert_eq!(cache.iter_mut().rev().collect::<Vec<_>>(), + [(&5, &mut 50), (&4, &mut 40), (&3, &mut 30)]); + } +} |