Two Queue (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;
// type inference lets us omit an explicit type signature (which
// would be `Cache<&str, &str>` in this example).
let mut book_reviews = new;
// review some books.
book_reviews.insert;
book_reviews.insert;
book_reviews.insert;
book_reviews.insert;
// check for a specific one.
if !book_reviews.contains_key
// oops, this review has a lot of spelling mistakes, let's delete it.
book_reviews.remove;
// look up the values associated with some keys.
let to_find = ;
for book in &to_find
// iterate over everything.
for in &book_reviews
Cache also implements an Entry API, which allows for more complex methods of getting, setting, updating and removing keys and their values:
use Cache;
// type inference lets us omit an explicit type signature (which
// would be `Cache<&str, u8>` in this example).
let mut player_stats = new;
// insert a key only if it doesn't already exist
player_stats.entry.or_insert;
// insert a key using a function that provides a new value only if it
// doesn't already exist
player_stats.entry.or_insert_with;
// update a key, guarding against the key possibly not being set
let stat = player_stats.entry.or_insert;
*stat += random_stat_buff;