TwoQueueCache

caches::lru

Struct TwoQueueCache 

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

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§

Source§

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

Source

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

Create a TwoQueueCache with size and default configurations.

Source

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

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

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

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

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

Source

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

pub fn recent_len(&self) -> usize

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

Source

pub fn frequent_len(&self) -> usize

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

Source

pub fn ghost_len(&self) -> usize

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

Source

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

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

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

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

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

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

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

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

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;
}
Source

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;
}
Source

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

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

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

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

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

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

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

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

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;
}
Source

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;
}
Source

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

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

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

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

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

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

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

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

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;
}
Source

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§

Source§

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

Source§

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 });
Source§

fn get<Q>(&mut self, k: &Q) -> Option<&V>
where 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));
Source§

fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
where 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));
Source§

fn peek<Q>(&self, k: &Q) -> Option<&V>
where 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"));
Source§

fn peek_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
where 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"));
Source§

fn remove<Q>(&mut self, k: &Q) -> Option<V>
where 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);
Source§

fn contains<Q>(&self, k: &Q) -> bool
where 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));
Source§

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

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

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

fn is_empty(&self) -> bool

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

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

Source§

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

Formats the value using the given formatter. Read more

Auto Trait Implementations§

§

impl<K, V, RH, FH, GH> Freeze for TwoQueueCache<K, V, RH, FH, GH>
where RH: Freeze, FH: Freeze, GH: Freeze,

§

impl<K, V, RH, FH, GH> RefUnwindSafe for TwoQueueCache<K, V, RH, FH, GH>
where RH: RefUnwindSafe, FH: RefUnwindSafe, GH: RefUnwindSafe, K: RefUnwindSafe, V: RefUnwindSafe,

§

impl<K, V, RH, FH, GH> Send for TwoQueueCache<K, V, RH, FH, GH>
where K: Send, V: Send, RH: Send, FH: Send, GH: Send,

§

impl<K, V, RH, FH, GH> Sync for TwoQueueCache<K, V, RH, FH, GH>
where K: Sync, V: Sync, RH: Sync, FH: Sync, GH: Sync,

§

impl<K, V, RH, FH, GH> Unpin for TwoQueueCache<K, V, RH, FH, GH>
where RH: Unpin, FH: Unpin, GH: Unpin,

§

impl<K, V, RH, FH, GH> UnwindSafe for TwoQueueCache<K, V, RH, FH, GH>
where RH: UnwindSafe, FH: UnwindSafe, GH: UnwindSafe, K: RefUnwindSafe, V: RefUnwindSafe,

Blanket Implementations§

Source§

impl<T> Any for T
where T: 'static + ?Sized,

Source§

fn type_id(&self) -> TypeId

Gets the TypeId of self. Read more
Source§

impl<T> Borrow<T> for T
where T: ?Sized,

Source§

fn borrow(&self) -> &T

Immutably borrows from an owned value. Read more
Source§

impl<T> BorrowMut<T> for T
where T: ?Sized,

Source§

fn borrow_mut(&mut self) -> &mut T

Mutably borrows from an owned value. Read more
Source§

impl<T> From<T> for T

Source§

fn from(t: T) -> T

Returns the argument unchanged.

Source§

impl<T, U> Into<U> for T
where U: From<T>,

Source§

fn into(self) -> U

Calls U::from(self).

That is, this conversion is whatever the implementation of From<T> for U chooses to do.

Source§

impl<T, U> TryFrom<U> for T
where U: Into<T>,

Source§

type Error = Infallible

The type returned in the event of a conversion error.
Source§

fn try_from(value: U) -> Result<T, <T as TryFrom<U>>::Error>

Performs the conversion.
Source§

impl<T, U> TryInto<U> for T
where U: TryFrom<T>,

Source§

type Error = <U as TryFrom<T>>::Error

The type returned in the event of a conversion error.
Source§

fn try_into(self) -> Result<U, <U as TryFrom<T>>::Error>

Performs the conversion.
Source§

impl<V, T> VZip<V> for T
where V: MultiLane<T>,

Source§

fn vzip(self) -> V