Struct caches::TwoQueueCache

pub struct TwoQueueCache<K: Hash + Eq, V, RH = DefaultHashBuilder, FH = DefaultHashBuilder, GH = DefaultHashBuilder> { /* private fields */ }

TwoQueueCache is a fixed size 2Q cache. 2Q is an enhancement over the standard LRU cache in that it tracks both frequently and recently used entries separately. This avoids a burst in access to new entries from evicting frequently used entries. It adds some additional tracking overhead to the RawLRU cache, and is computationally about 2x the cost, and adds some metadata over head. The AdaptiveCache is similar to the TwoQueueCache, but does not require setting any parameters.

Example

use caches::{TwoQueueCache, Cache, PutResult};

let mut cache = TwoQueueCache::new(4).unwrap();

// Add 1,2,3,4,
(1..=4).for_each(|i| {
    assert_eq!(cache.put(i, i), PutResult::Put);
});

// Add 5 -> Evict 1 to ghost LRU
assert_eq!(cache.put(5, 5), PutResult::Put);

// Pull in the recently evicted
assert_eq!(cache.put(1, 1), PutResult::Update(1));

// Add 6, should cause another recent evict
assert_eq!(cache.put(6, 6), PutResult::<i32, i32>::Put);

// Add 7, should evict an entry from ghost LRU.
assert_eq!(cache.put(7, 7), PutResult::Evicted { key: 2, value: 2 });

// Add 2, should evict an entry from ghost LRU
assert_eq!(cache.put(2, 11), PutResult::Evicted { key: 3, value: 3 });

// Add 4, should put the entry from ghost LRU to freq LRU
assert_eq!(cache.put(4, 11), PutResult::Update(4));

// move all entry in recent to freq.
assert_eq!(cache.put(2, 22), PutResult::Update(11));
assert_eq!(cache.put(7, 77), PutResult::<i32, i32>::Update(7));

// Add 6, should put the entry from ghost LRU to freq LRU, and evicted one
// entry
assert_eq!(cache.put(6, 66), PutResult::EvictedAndUpdate { evicted: (5, 5), update: 6});
assert_eq!(cache.recent_len(), 0);
assert_eq!(cache.ghost_len(), 1);
assert_eq!(cache.frequent_len(), 4);

Implementations

impl<K: Hash + Eq, V> TwoQueueCache<K, V>

pub fn new(size: usize) -> Result<Self, CacheError>

Create a TwoQueueCache with size and default configurations.

pub fn builder(size: usize) -> TwoQueueCacheBuilder

Returns a TwoQueueCacheBuilder to help build a TwoQueueCache.

Example

use caches::{TwoQueueCacheBuilder, TwoQueueCache, Cache};
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;

let mut cache = TwoQueueCache::<u64, u64>::builder(3)
    .set_recent_ratio(0.3)
    .set_ghost_ratio(0.4)
    .set_recent_hasher(BuildHasherDefault::<FxHasher>::default())
    .set_frequent_hasher(BuildHasherDefault::<FxHasher>::default())
    .set_ghost_hasher(BuildHasherDefault::<FxHasher>::default())
    .finalize::<u64, u64>()
    .unwrap();

cache.put(1, 1);

pub fn with_recent_ratio(size: usize, rr: f64) -> Result<Self, CacheError>

Create a cache with size and recent ratio.

Example

use caches::{Cache, TwoQueueCache};

let mut cache: TwoQueueCache<u64, u64>= TwoQueueCache::with_recent_ratio(5, 0.3).unwrap();

pub fn with_ghost_ratio(size: usize, gr: f64) -> Result<Self, CacheError>

Create a cache with size and ghost ratio.

Example

use caches::{Cache, TwoQueueCache};

let mut cache: TwoQueueCache<u64, u64>= TwoQueueCache::with_ghost_ratio(5, 0.6).unwrap();

pub fn with_2q_parameters(
    size: usize,
    rr: f64,
    gr: f64
) -> Result<Self, CacheError>

Create a cache with size, recent ratio and ghost ratio

Example

use caches::{Cache, TwoQueueCache};

let mut cache: TwoQueueCache<u64, u64>= TwoQueueCache::with_2q_parameters(5, 0.3, 0.6).unwrap();

impl<K: Hash + Eq, V, RH: BuildHasher, FH: BuildHasher, GH: BuildHasher> TwoQueueCache<K, V, RH, FH, GH>

pub fn from_builder(
    builder: TwoQueueCacheBuilder<RH, FH, GH>
) -> Result<Self, CacheError>

Create a TwoQueueCache from TwoQueueCacheBuilder.

Example

use caches::{TwoQueueCacheBuilder, TwoQueueCache, Cache};
use rustc_hash::FxHasher;
use std::hash::BuildHasherDefault;

let builder = TwoQueueCacheBuilder::new(5)
    .set_recent_ratio(0.3)
    .set_ghost_ratio(0.4)
    .set_recent_hasher(BuildHasherDefault::<FxHasher>::default())
    .set_frequent_hasher(BuildHasherDefault::<FxHasher>::default())
    .set_ghost_hasher(BuildHasherDefault::<FxHasher>::default());

let mut cache = TwoQueueCache::from_builder(builder).unwrap();
cache.put(1, 1);

pub fn recent_len(&self) -> usize

Returns the number of key-value pairs that are currently in the the recent LRU.

pub fn frequent_len(&self) -> usize

Returns the number of key-value pairs that are currently in the the frequent LRU.

pub fn ghost_len(&self) -> usize

Returns the number of key-value pairs that are currently in the the ghost LRU.

pub fn recent_keys(&self) -> KeysMRUIter<'_, K, V>

An iterator visiting all keys of recent LRU in most-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.recent_keys() {
    println!("key: {}", key);
}

pub fn recent_keys_lru(&self) -> KeysLRUIter<'_, K, V>

An iterator visiting all keys of recent LRU in less-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.recent_keys_lru() {
    println!("key: {}", key);
}

pub fn recent_values(&self) -> ValuesMRUIter<'_, K, V>

An iterator visiting all values of recent LRU in most-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.recent_values() {
    println!("val: {}",  val);
}

pub fn recent_values_lru(&self) -> ValuesLRUIter<'_, K, V>

An iterator visiting all values in less-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.recent_values_lru() {
    println!("val: {}", val);
}

pub fn recent_values_mut(&mut self) -> ValuesMRUIterMut<'_, K, V>

An iterator visiting all values of recent LRU in most-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.recent_values_mut() {
    println!("val: {}", val);
}

pub fn recent_values_lru_mut(&mut self) -> ValuesLRUIterMut<'_, K, V>

An iterator visiting all values of recent LRU in less-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.recent_values_lru_mut() {
    println!("val: {}", val);
}

pub fn recent_iter(&self) -> MRUIter<'_, K, V>

An iterator visiting all entries of recent LRU in most-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.recent_iter() {
    println!("key: {} val: {}", key, val);
}

pub fn recent_iter_lru(&self) -> LRUIter<'_, K, V>

An iterator visiting all entries of recent LRU in less-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.recent_iter_lru() {
    println!("key: {} val: {}", key, val);
}

pub fn recent_iter_mut(&mut self) -> MRUIterMut<'_, K, V>

An iterator visiting all entries of recent LRU in most-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 2i32;
// write dirty blocks to disk.
for (block_id, block) in cache.recent_iter_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr -= 1;
}

pub fn recent_iter_lru_mut(&mut self) -> LRUIterMut<'_, K, V>

An iterator visiting all entries of recent LRU in less-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

// upgrade to frequent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 0i32;

// write dirty blocks to disk.
for (block_id, block) in cache.frequent_iter_lru_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr += 1;
}

pub fn ghost_keys(&self) -> KeysMRUIter<'_, K, V>

An iterator visiting all keys of ghost LRU in most-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.ghost_keys() {
    println!("key: {}", key);
}

pub fn ghost_keys_lru(&self) -> KeysLRUIter<'_, K, V>

An iterator visiting all keys of ghost LRU in less-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.ghost_keys_lru() {
    println!("key: {}", key);
}

pub fn ghost_values(&self) -> ValuesMRUIter<'_, K, V>

An iterator visiting all values of ghost LRU in most-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.ghost_values() {
    println!("val: {}",  val);
}

pub fn ghost_values_lru(&self) -> ValuesLRUIter<'_, K, V>

An iterator visiting all values in less-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.ghost_values_lru() {
    println!("val: {}", val);
}

pub fn ghost_values_mut(&mut self) -> ValuesMRUIterMut<'_, K, V>

An iterator visiting all values of ghost LRU in most-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.ghost_values_mut() {
    println!("val: {}", val);
}

pub fn ghost_values_lru_mut(&mut self) -> ValuesLRUIterMut<'_, K, V>

An iterator visiting all values of ghost LRU in less-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.ghost_values_lru_mut() {
    println!("val: {}", val);
}

pub fn ghost_iter(&self) -> MRUIter<'_, K, V>

An iterator visiting all entries of ghost LRU in most-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.ghost_iter() {
    println!("key: {} val: {}", key, val);
}

pub fn ghost_iter_lru(&self) -> LRUIter<'_, K, V>

An iterator visiting all entries of ghost LRU in less-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.ghost_iter_lru() {
    println!("key: {} val: {}", key, val);
}

pub fn ghost_iter_mut(&mut self) -> MRUIterMut<'_, K, V>

An iterator visiting all entries of ghost LRU in most-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

// upgrade to frequent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 2i32;
// write dirty blocks to disk.
for (block_id, block) in cache.ghost_iter_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr -= 1;
}

pub fn ghost_iter_lru_mut(&mut self) -> LRUIterMut<'_, K, V>

An iterator visiting all entries of ghost LRU in less-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

// upgrade to frequent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 0i32;

// write dirty blocks to disk.
for (block_id, block) in cache.frequent_iter_lru_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr += 1;
}

pub fn frequent_keys(&self) -> KeysMRUIter<'_, K, V>

An iterator visiting all keys of frequent LRU in most-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.frequent_keys() {
    println!("key: {}", key);
}

pub fn frequent_keys_lru(&self) -> KeysLRUIter<'_, K, V>

An iterator visiting all keys of frequent LRU in less-recently used order. The iterator element type is &'a K.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for key in cache.frequent_keys_lru() {
    println!("key: {}", key);
}

pub fn frequent_values(&self) -> ValuesMRUIter<'_, K, V>

An iterator visiting all values of frequent LRU in most-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.frequent_values() {
    println!("val: {}",  val);
}

pub fn frequent_values_lru(&self) -> ValuesLRUIter<'_, K, V>

An iterator visiting all values of frequent LRU in less-recently used order. The iterator element type is &'a V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.frequent_values_lru() {
    println!("val: {}", val);
}

pub fn frequent_values_mut(&mut self) -> ValuesMRUIterMut<'_, K, V>

An iterator visiting all values of frequent LRU in most-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.frequent_values_mut() {
    println!("val: {}", val);
}

pub fn frequent_values_lru_mut(&mut self) -> ValuesLRUIterMut<'_, K, V>

An iterator visiting all values of frequent LRU in less-recently used order. The iterator element type is &'a mut V.

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for val in cache.frequent_values_lru_mut() {
    println!("val: {}", val);
}

pub fn frequent_iter(&self) -> MRUIter<'_, K, V>

An iterator visiting all entries of frequent LRU in most-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.frequent_iter() {
    println!("key: {} val: {}", key, val);
}

pub fn frequent_iter_lru(&self) -> LRUIter<'_, K, V>

An iterator visiting all entries of frequent LRU in less-recently used order. The iterator element type is (&'a K, &'a V).

Examples

use caches::{Cache, TwoQueueCache};

let mut cache = TwoQueueCache::new(3).unwrap();
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);

for (key, val) in cache.frequent_iter_lru() {
    println!("key: {} val: {}", key, val);
}

pub fn frequent_iter_mut(&mut self) -> MRUIterMut<'_, K, V>

An iterator visiting all entries of frequent LRU in most-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

// upgrade to frequent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 2i32;
// write dirty blocks to disk.
for (block_id, block) in cache.frequent_iter_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr -= 1;
}

pub fn frequent_iter_lru_mut(&mut self) -> LRUIterMut<'_, K, V>

An iterator visiting all entries of frequent LRU in less-recently-used order, giving a mutable reference on V. The iterator element type is (&'a K, &'a mut V).

Examples

use caches::{Cache, TwoQueueCache};

struct HddBlock {
    idx: u64,
    dirty: bool,
    data: [u8; 512]
}

let mut cache = TwoQueueCache::new(3).unwrap();

// put in recent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

// upgrade to frequent list
cache.put(0, HddBlock { idx: 0, dirty: false, data: [0x00; 512]});
cache.put(1, HddBlock { idx: 1, dirty: true,  data: [0x55; 512]});
cache.put(2, HddBlock { idx: 2, dirty: true,  data: [0x77; 512]});

let mut ctr = 0i32;

// write dirty blocks to disk.
for (block_id, block) in cache.frequent_iter_lru_mut() {
    if block.dirty {
        // write block to disk
        block.dirty = false
    }
    assert_eq!(*block_id, ctr);
    ctr += 1;
}

Trait Implementations

impl<K: Hash + Eq, V, RH: BuildHasher, FH: BuildHasher, GH: BuildHasher> Cache<K, V> for TwoQueueCache<K, V, RH, FH, GH>

fn put(&mut self, k: K, v: V) -> PutResult<K, V>

Puts a key-value pair to the cache.

Note

• TwoQueueCache guarantees that the size of the recent LRU plus the size of the freq LRU is less or equal to the TwoQueueCache’s size.
• The ghost LRU has its own size.

Example

use caches::{TwoQueueCache, Cache, PutResult};

let mut cache = TwoQueueCache::new(4).unwrap();
// Add 1,2,3,4,5 -> Evict 1
cache.put(1, 1);
cache.put(2, 2);
cache.put(3, 3);
cache.put(4, 4);
cache.put(5, 5);

// Pull in the recently evicted
assert_eq!(cache.put(1, 1), PutResult::Update(1));

// Add 6, should cause another recent evict
assert_eq!(cache.put(6, 6), PutResult::Put);

// Add 7, should evict an entry from ghost LRU.
assert_eq!(cache.put(7, 7), PutResult::Evicted { key: 2, value: 2});

// Add 2, should evict an entry from ghost LRU
assert_eq!(cache.put(2, 11), PutResult::Evicted { key: 3, value: 3});

// Add 4, should put the entry from ghost LRU to freq LRU
assert_eq!(cache.put(4, 11), PutResult::Update(4));

// move all entry in recent to freq.
assert_eq!(cache.put(2, 22), PutResult::Update(11));
assert_eq!(cache.put(7, 77), PutResult::Update(7));

// Add 6, should put the entry from ghost LRU to freq LRU, and evicted one
// entry
assert_eq!(cache.put(6, 66), PutResult::EvictedAndUpdate { evicted: (5, 5), update: 6 });

fn get<'a, Q>(&mut self, k: &'a Q) -> Option<&'a V>where
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value of the key in the cache or None if it is not present in the cache. Moves the key to the head of the LRU list if it exists.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put("apple", 8);
cache.put("banana", 4);
cache.put("banana", 6);
cache.put("pear", 2);

assert_eq!(cache.get(&"banana"), Some(&6));

fn get_mut<'a, Q>(&mut self, k: &'a Q) -> Option<&'a mut V>where
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value of the key in the cache or None if it is not present in the cache. Moves the key to the head of the LRU list if it exists.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put("apple", 8);
cache.put("banana", 4);
cache.put("banana", 6);
cache.put("pear", 2);

assert_eq!(cache.get_mut(&"apple"), None);
assert_eq!(cache.get_mut(&"banana"), Some(&mut 6));
assert_eq!(cache.get_mut(&"pear"), Some(&mut 2));

fn peek<'a, Q>(&self, k: &'a Q) -> Option<&'a V>where
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a reference to the value corresponding to the key in the cache or None if it is not present in the cache. Unlike get, peek does not update the LRU list so the key’s position will be unchanged.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put(1, "a");
cache.put(2, "b");

assert_eq!(cache.peek(&1), Some(&"a"));
assert_eq!(cache.peek(&2), Some(&"b"));

fn peek_mut<'a, Q>(&mut self, k: &'a Q) -> Option<&'a mut V>where
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a mutable reference to the value corresponding to the key in the cache or None if it is not present in the cache. Unlike get_mut, peek_mut does not update the LRU list so the key’s position will be unchanged.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put(1, "a");
cache.put(2, "b");

assert_eq!(cache.peek_mut(&1), Some(&mut "a"));
assert_eq!(cache.peek_mut(&2), Some(&mut "b"));

fn remove<Q>(&mut self, k: &Q) -> Option<V>where
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Removes and returns the value corresponding to the key from the cache or None if it does not exist.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put(2, "a");

assert_eq!(cache.remove(&1), None);
assert_eq!(cache.remove(&2), Some("a"));
assert_eq!(cache.remove(&2), None);
assert_eq!(cache.len(), 0);

fn contains<Q>(&self, k: &Q) -> boolwhere
    KeyRef<K>: Borrow<Q>,
    Q: Hash + Eq + ?Sized,

Returns a bool indicating whether the given key is in the cache. Does not update the LRU list.

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();

cache.put(1, "a");
cache.put(2, "b");
cache.put(3, "c");

assert!(!cache.contains(&1));
assert!(cache.contains(&2));
assert!(cache.contains(&3));

fn purge(&mut self)

Clears the contents of the cache.

Example

use caches::{Cache, TwoQueueCache};
let mut cache: TwoQueueCache<isize, &str> = TwoQueueCache::new(2).unwrap();
assert_eq!(cache.len(), 0);

cache.put(1, "a");
assert_eq!(cache.len(), 1);

cache.put(2, "b");
assert_eq!(cache.len(), 2);

cache.purge();
assert_eq!(cache.len(), 0);

fn len(&self) -> usize

Returns the number of key-value pairs that are currently in the the cache (excluding the length of inner ghost LRU).

Example

use caches::{Cache, TwoQueueCache};
let mut cache = TwoQueueCache::new(2).unwrap();
assert_eq!(cache.len(), 0);

cache.put(1, "a");
assert_eq!(cache.len(), 1);

cache.put(2, "b");
assert_eq!(cache.len(), 2);

cache.put(3, "c");
assert_eq!(cache.len(), 2);

fn cap(&self) -> usize

Returns the maximum number of key-value pairs the cache can hold (excluding the capacity of inner ghost LRU).

Example

use caches::{Cache, TwoQueueCache};
let mut cache: TwoQueueCache<isize, &str> = TwoQueueCache::new(2).unwrap();
assert_eq!(cache.cap(), 2);

fn is_empty(&self) -> bool

Returns a bool indicating whether the cache is empty or not.

impl<K: Hash + Eq, V, RH: BuildHasher, FH: BuildHasher, GH: BuildHasher> Debug for TwoQueueCache<K, V, RH, FH, GH>

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

Formats the value using the given formatter.