[−][src]Struct cache_2q::Cache
A 2Q Cache which maps keys to values
2Q is an enhancement over an LRU cache by tracking both recent and frequently accessed entries separately. This avoids the cache being trashed by a scan of many new items: Only the recent list will be trashed.
The cache is split into 3 sections, recent entries, frequent entries, and ghost entries.
- recent contains the most recently added entries.
- frequent is an LRU cache which contains entries which are frequently accessed
- ghost contains the keys which have been recently evicted from the recent cache.
New entries in the cache are initially placed in recent. After recent fills up, the oldest entry from recent will be removed, and its key is placed in ghost. When an entry is requested and not found, but its key is found in the ghost list, an entry is pushed to the front of frequent.
Examples
use cache_2q::Cache; // type inference lets us omit an explicit type signature (which // would be `Cache<&str, &str>` in this example). let mut book_reviews = Cache::new(1024); // review some books. book_reviews.insert("Adventures of Huckleberry Finn", "My favorite book."); book_reviews.insert("Grimms' Fairy Tales", "Masterpiece."); book_reviews.insert("Pride and Prejudice", "Very enjoyable."); book_reviews.insert("The Adventures of Sherlock Holmes", "Eye lyked it alot."); // check for a specific one. if !book_reviews.contains_key("Les Misérables") { println!("We've got {} reviews, but Les Misérables ain't one.", book_reviews.len()); } // oops, this review has a lot of spelling mistakes, let's delete it. book_reviews.remove("The Adventures of Sherlock Holmes"); // look up the values associated with some keys. let to_find = ["Pride and Prejudice", "Alice's Adventure in Wonderland"]; for book in &to_find { match book_reviews.get(book) { Some(review) => println!("{}: {}", book, review), None => println!("{} is unreviewed.", book) } } // iterate over everything. for (book, review) in &book_reviews { println!("{}: \"{}\"", book, review); }
Cache also implements an Entry API, which allows for more complex methods of getting, setting, updating and removing keys and their values:
use cache_2q::Cache; // type inference lets us omit an explicit type signature (which // would be `Cache<&str, u8>` in this example). let mut player_stats = Cache::new(32); fn random_stat_buff() -> u8 { // could actually return some random value here - let's just return // some fixed value for now 42 } // insert a key only if it doesn't already exist player_stats.entry("health").or_insert(100); // insert a key using a function that provides a new value only if it // doesn't already exist player_stats.entry("defence").or_insert_with(random_stat_buff); // update a key, guarding against the key possibly not being set let stat = player_stats.entry("attack").or_insert(100); *stat += random_stat_buff();
Implementations
impl<K: Eq + Hash, V> Cache<K, V, RandomState>
[src]
pub fn new(size: usize) -> Self
[src]
Creates an empty cache, with the specified size
The returned cache will have enough room for size
recent entries,
and size
frequent entries. In addition, up to size * 4
keys will be kept
as remembered items
Examples
use cache_2q::Cache; let mut cache: Cache<u64, Vec<u8>> = Cache::new(8); cache.insert(1, vec![1,2,3,4]); assert_eq!(*cache.get(&1).unwrap(), &[1,2,3,4]);
Panics
panics if size
is zero. A zero-sized cache isn't very useful, and breaks some apis
(like VacantEntry::insert, which returns a reference to the newly inserted item)
impl<K: Eq + Hash, V, S: BuildHasher + Clone> Cache<K, V, S>
[src]
pub fn with_hasher(size: usize, hash_builder: S) -> Self
[src]
Creates an empty Cache
with the specified capacity, using hash_builder
to hash the keys
The returned cache will have enough room for size
recent entries,
and size
frequent entries. In addition, up to size * 4
keys will be kept
as remembered items
Examples
use cache_2q::Cache; use std::collections::hash_map::DefaultHasher; use std::hash::BuildHasherDefault; let mut cache: Cache<u64, Vec<u8>, BuildHasherDefault<DefaultHasher>> = Cache::with_hasher(16, BuildHasherDefault::default()); cache.insert(1, vec![1,2,3,4]); assert_eq!(*cache.get(&1).unwrap(), &[1,2,3,4]);
Panics
panics if size
is zero. A zero-sized cache isn't very useful, and breaks some apis
(like VacantEntry::insert, which returns a reference to the newly inserted item)
impl<K: Eq + Hash, V, S: BuildHasher> Cache<K, V, S>
[src]
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
K: Borrow<Q>,
Q: Eq + Hash,
[src]
K: Borrow<Q>,
Q: Eq + Hash,
Returns true if the cache contains a value for the specified key.
The key may be any borrowed form of the cache's key type, but Eq on the borrowed form must match those for the key type.
Examples
use cache_2q::Cache; let mut cache = Cache::new(8); cache.insert(1, "a"); assert_eq!(cache.contains_key(&1), true); assert_eq!(cache.contains_key(&2), false);
pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
K: Borrow<Q>,
Q: Eq + Hash,
[src]
K: Borrow<Q>,
Q: Eq + Hash,
Returns a reference to the value corresponding to the key.
The key may be any borrowed form of the cache's key type, but Eq on the borrowed form must match those for the key type.
Unlike get(), the the cache will not be updated to reflect a new access of key
.
Because the cache is not updated, peek()
can operate without mutable access to the cache
Examples
use cache_2q::Cache; let mut cache = Cache::new(32); cache.insert(1, "a"); let cache = cache; // peek doesn't require mutable access to the cache assert_eq!(cache.peek(&1), Some(&"a")); assert_eq!(cache.peek(&2), None);
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
K: Borrow<Q>,
Q: Eq + Hash,
[src]
K: Borrow<Q>,
Q: Eq + Hash,
Returns a mutable reference to the value corresponding to the key.
The key may be any borrowed form of the cache's key type, but Eq on the borrowed form must match those for the key type.
Examples
use cache_2q::Cache; let mut cache = Cache::new(8); cache.insert(1, "a"); if let Some(x) = cache.get(&1) { *x = "b"; } assert_eq!(cache.get(&1), Some(&mut "b"));
pub fn insert(&mut self, key: K, value: V) -> Option<V>
[src]
Inserts a key-value pair into the cache.
If the cache did not have this key present, None is returned.
If the cache did have this key present, the value is updated, and the old value is returned.
Examples
use cache_2q::Cache; let mut cache = Cache::new(8); assert_eq!(cache.insert(37, "a"), None); assert_eq!(cache.is_empty(), false); cache.insert(37, "b"); assert_eq!(cache.insert(37, "c"), Some("b")); assert_eq!(*cache.get(&37).unwrap(), "c");
pub fn peek_entry(&mut self, key: K) -> Entry<K, V, S>
[src]
Gets the given key's corresponding entry in the cache for in-place manipulation. The LRU portion of the cache is not updated
Examples
use cache_2q::Cache; let mut stringified = Cache::new(8); for &i in &[1, 2, 5, 1, 2, 8, 1, 2, 102, 25, 1092, 1, 2, 82, 10, 1095] { let string = stringified.peek_entry(i).or_insert_with(|| i.to_string()); assert_eq!(string, &i.to_string()); }
pub fn entry(&mut self, key: K) -> Entry<K, V, S>
[src]
Gets the given key's corresponding entry in the cache for in-place manipulation.
Examples
use cache_2q::Cache; let mut stringified = Cache::new(8); for &i in &[1, 2, 5, 1, 2, 8, 1, 2, 102, 25, 1092, 1, 2, 82, 10, 1095] { let string = stringified.entry(i).or_insert_with(|| i.to_string()); assert_eq!(string, &i.to_string()); }
pub fn len(&self) -> usize
[src]
Returns the number of entries currently in the cache.
Examples
use cache_2q::Cache; let mut a = Cache::new(8); assert_eq!(a.len(), 0); a.insert(1, "a"); assert_eq!(a.len(), 1);
pub fn is_empty(&self) -> bool
[src]
Returns true if the cache contains no elements.
Examples
use cache_2q::Cache; let mut a = Cache::new(8); assert!(a.is_empty()); a.insert(1, "a"); assert!(!a.is_empty());
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
K: Borrow<Q>,
Q: Eq + Hash,
[src]
K: Borrow<Q>,
Q: Eq + Hash,
Removes a key from the cache, returning the value associated with the key if the key was previously in the cache.
The key may be any borrowed form of the cache's key type, but Eq on the borrowed form must match those for the key type.
Examples
use cache_2q::Cache; let mut cache = Cache::new(8); cache.insert(1, "a"); assert_eq!(cache.remove(&1), Some("a")); assert_eq!(cache.remove(&1), None);
pub fn clear(&mut self)
[src]
Clears the cache, removing all key-value pairs. Keeps the allocated memory for reuse.
Examples
use cache_2q::Cache; let mut a = Cache::new(32); a.insert(1, "a"); a.clear(); assert!(a.is_empty());
pub fn iter(&self) -> Iter<K, V>
[src]
An iterator visiting all key-value pairs in arbitrary order.
The iterator element type is (&'a K, &'a V)
.
Examples
use cache_2q::Cache; let mut cache = Cache::new(8); cache.insert("a", 1); cache.insert("b", 2); cache.insert("c", 3); for (key, val) in cache.iter() { println!("key: {} val: {}", key, val); }
Trait Implementations
impl<K: Clone + Eq + Hash, V: Clone, S: Clone + BuildHasher> Clone for Cache<K, V, S>
[src]
impl<K: Eq + Hash + Debug, V: Debug, S: BuildHasher> Debug for Cache<K, V, S>
[src]
impl<K: Eq + Hash, V: Eq, S: Eq + BuildHasher> Eq for Cache<K, V, S>
[src]
impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V>
[src]
type Item = (&'a K, &'a V)
The type of the elements being iterated over.
type IntoIter = Iter<'a, K, V>
Which kind of iterator are we turning this into?
fn into_iter(self) -> Iter<'a, K, V>
[src]
impl<K: PartialEq + Eq + Hash, V: PartialEq, S: PartialEq + BuildHasher> PartialEq<Cache<K, V, S>> for Cache<K, V, S>
[src]
impl<K: Eq + Hash, V, S: BuildHasher> StructuralEq for Cache<K, V, S>
[src]
impl<K: Eq + Hash, V, S: BuildHasher> StructuralPartialEq for Cache<K, V, S>
[src]
Auto Trait Implementations
impl<K, V, S> RefUnwindSafe for Cache<K, V, S> where
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
S: RefUnwindSafe,
V: RefUnwindSafe,
impl<K, V, S> Send for Cache<K, V, S> where
K: Send,
S: Send,
V: Send,
K: Send,
S: Send,
V: Send,
impl<K, V, S> Sync for Cache<K, V, S> where
K: Sync,
S: Sync,
V: Sync,
K: Sync,
S: Sync,
V: Sync,
impl<K, V, S> Unpin for Cache<K, V, S> where
S: Unpin,
S: Unpin,
impl<K, V, S> UnwindSafe for Cache<K, V, S> where
K: RefUnwindSafe,
S: UnwindSafe,
V: RefUnwindSafe,
K: RefUnwindSafe,
S: UnwindSafe,
V: RefUnwindSafe,
Blanket Implementations
impl<T> Any for T where
T: 'static + ?Sized,
[src]
T: 'static + ?Sized,
impl<T> Borrow<T> for T where
T: ?Sized,
[src]
T: ?Sized,
impl<T> BorrowMut<T> for T where
T: ?Sized,
[src]
T: ?Sized,
fn borrow_mut(&mut self) -> &mut T
[src]
impl<T> From<T> for T
[src]
impl<T, U> Into<U> for T where
U: From<T>,
[src]
U: From<T>,
impl<T> ToOwned for T where
T: Clone,
[src]
T: Clone,
type Owned = T
The resulting type after obtaining ownership.
fn to_owned(&self) -> T
[src]
fn clone_into(&self, target: &mut T)
[src]
impl<T, U> TryFrom<U> for T where
U: Into<T>,
[src]
U: Into<T>,
type Error = Infallible
The type returned in the event of a conversion error.
fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>
[src]
impl<T, U> TryInto<U> for T where
U: TryFrom<T>,
[src]
U: TryFrom<T>,