Struct cache_2q::Cache [−] [src]

pub struct Cache<K, V> { /* fields omitted */ }

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, V> Cache<K, V>
[src]

Creates an empty cache, with the specified size

Notes

size defines the maximum number of entries, but there can be an additional size / 2 instances of K

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)

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);

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);

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.

Examples

use cache_2q::Cache;

let mut cache = Cache::new(32);
cache.insert(1, "a");
assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), None);

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_mut(&1) {
    *x = "b";
}
assert_eq!(cache.get(&1), Some(&"b"));

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");

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());
}

Returns the number of entries currenly 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);

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());

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);

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());

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());
}

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, V: Debug> Debug for Cache<K, V>
[src]

Formats the value using the given formatter.

impl<K: Clone, V: Clone> Clone for Cache<K, V>
[src]

Returns a copy of the value. Read more

Performs copy-assignment from source. Read more

impl<K: PartialEq, V: PartialEq> PartialEq for Cache<K, V>
[src]

This method tests for self and other values to be equal, and is used by ==. Read more

This method tests for !=.

impl<K: Eq, V: Eq> Eq for Cache<K, V>
[src]

impl<'a, K: 'a + Eq, V: 'a> IntoIterator for &'a Cache<K, V>
[src]

The type of the elements being iterated over.

Which kind of iterator are we turning this into?

Creates an iterator from a value. Read more