Struct cache_2q::Cache [−][src]
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();
Methods
impl<K: Eq + Hash, V> Cache<K, V>
[src]
impl<K: Eq + Hash, V> Cache<K, V>
pub fn new(size: usize) -> Self
[src]
pub fn new(size: usize) -> Self
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)
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
K: Borrow<Q>,
Q: Eq + Hash,
[src]
pub fn contains_key<Q: ?Sized>(&self, key: &Q) -> bool where
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]
pub fn peek<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
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]
pub fn get<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
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]
pub fn insert(&mut self, key: K, value: V) -> Option<V>
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>
[src]
pub fn peek_entry(&mut self, key: K) -> Entry<K, V>
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>
[src]
pub fn entry(&mut self, key: K) -> Entry<K, V>
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]
pub fn len(&self) -> usize
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]
pub fn is_empty(&self) -> bool
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]
pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
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]
pub fn clear(&mut self)
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());
ⓘImportant traits for Iter<'a, K, V>pub fn iter(&self) -> Iter<K, V>
[src]
pub fn iter(&self) -> Iter<K, V>
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: Debug + Eq + Hash, V: Debug> Debug for Cache<K, V>
[src]
impl<K: Debug + Eq + Hash, V: Debug> Debug for Cache<K, V>
fn fmt(&self, f: &mut Formatter) -> Result
[src]
fn fmt(&self, f: &mut Formatter) -> Result
Formats the value using the given formatter. Read more
impl<K: Clone + Eq + Hash, V: Clone> Clone for Cache<K, V>
[src]
impl<K: Clone + Eq + Hash, V: Clone> Clone for Cache<K, V>
fn clone(&self) -> Cache<K, V>
[src]
fn clone(&self) -> Cache<K, V>
Returns a copy of the value. Read more
fn clone_from(&mut self, source: &Self)
1.0.0[src]
fn clone_from(&mut self, source: &Self)
Performs copy-assignment from source
. Read more
impl<K: PartialEq + Eq + Hash, V: PartialEq> PartialEq for Cache<K, V>
[src]
impl<K: PartialEq + Eq + Hash, V: PartialEq> PartialEq for Cache<K, V>
fn eq(&self, other: &Cache<K, V>) -> bool
[src]
fn eq(&self, other: &Cache<K, V>) -> bool
This method tests for self
and other
values to be equal, and is used by ==
. Read more
fn ne(&self, other: &Cache<K, V>) -> bool
[src]
fn ne(&self, other: &Cache<K, V>) -> bool
This method tests for !=
.
impl<K: Eq + Eq + Hash, V: Eq> Eq for Cache<K, V>
[src]
impl<K: Eq + Eq + Hash, V: Eq> Eq for Cache<K, V>
impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V>
[src]
impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V>