Struct Cache

pub struct Cache<K: Eq + Hash, V, S: BuildHasher = RandomState> { /* private fields */ }

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>

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)

impl<K: Eq + Hash, V, S: BuildHasher + Clone> Cache<K, V, S>

pub fn with_hasher(size: usize, hash_builder: S) -> Self

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>

pub fn contains_key<Q>(&self, key: &Q) -> bool

where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

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>(&self, key: &Q) -> Option<&V>

where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

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>(&mut self, key: &Q) -> Option<&mut V>

where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

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>

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>

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>

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

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

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>(&mut self, key: &Q) -> Option<V>

where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

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)

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>

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>

fn clone(&self) -> Cache<K, V, S>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<K: Eq + Hash + Debug, V: Debug, S: BuildHasher> Debug for Cache<K, V, S>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'a, K: 'a + Eq + Hash, V: 'a> IntoIterator for &'a Cache<K, V>

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>

Creates an iterator from a value.

impl<K: PartialEq + Eq + Hash, V: PartialEq, S: PartialEq + BuildHasher> PartialEq for Cache<K, V, S>

fn eq(&self, other: &Cache<K, V, S>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<K: Eq + Eq + Hash, V: Eq, S: Eq + BuildHasher> Eq for Cache<K, V, S>

impl<K: Eq + Hash, V, S: BuildHasher> StructuralPartialEq for Cache<K, V, S>