Struct caches::WTinyLFUCache

pub struct WTinyLFUCache<K: Hash, V, KH = DefaultKeyHasher<K>, FH = DefaultHashBuilder, RH = DefaultHashBuilder, WH = DefaultHashBuilder> { /* private fields */ }

WTinyLFUCache implements the W-TinyLFU, based on the paper TinyLFU: A Highly Efficient Cache Admission Policy

Example

use caches::{WTinyLFUCache, PutResult, Cache};
 
let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).unwrap();
assert_eq!(cache.cap(), 5);
assert_eq!(cache.window_cache_cap(), 1);
assert_eq!(cache.main_cache_cap(), 4);

assert_eq!(cache.put(1, 1), PutResult::Put);
assert!(cache.contains(&1));
assert_eq!(cache.put(2, 2), PutResult::Put);
assert!(cache.contains(&2));
assert_eq!(cache.put(3, 3), PutResult::Put);
assert!(cache.contains(&3));

// current state
// window cache:        (MRU) [3] (LRU)
// probationary cache:  (MRU) [2, 1] (LRU)
// protected cache:     (MRU) [] (LRU)
assert_eq!(cache.window_cache_len(), 1);
assert_eq!(cache.main_cache_len(), 2);

assert_eq!(cache.put(2, 22), PutResult::Update(2));
assert_eq!(cache.put(1, 11), PutResult::Update(1));

// current state
// window cache:        (MRU) [3] (LRU)
// probationary cache:  (MRU) [] (LRU)
// protected cache:     (MRU) [1, 2] (LRU)
assert_eq!(cache.window_cache_len(), 1);

assert_eq!(cache.put(3, 33), PutResult::Update(3));

// current state
// window cache:        (MRU) [2] (LRU)
// probationary cache:  (MRU) [] (LRU)
// protected cache:     (MRU) [3, 1] (LRU)
assert_eq!(cache.window_cache_len(), 1);

assert_eq!(cache.put(4, 4), PutResult::Put);
assert_eq!(cache.put(5, 5), PutResult::Put);

// current state
// window cache:        (MRU) [5] (LRU)
// probationary cache:  (MRU) [4, 2] (LRU)
// protected cache:     (MRU) [3, 1] (LRU)

assert_eq!(cache.get(&4), Some(&4));
assert_eq!(cache.get_mut(&5), Some(&mut 5));

// current state
// window cache:        (MRU) [5] (LRU)
// probationary cache:  (MRU) [1, 2] (LRU)
// protected cache:     (MRU) [4, 3] (LRU)
assert_eq!(cache.peek(&3), Some(&33));
assert_eq!(cache.peek_mut(&2), Some(&mut 22));

assert_eq!(cache.remove(&3), Some(33));
assert_eq!(cache.remove(&2), Some(22));

Implementations

impl<K: Hash + Eq, V> WTinyLFUCache<K, V, DefaultKeyHasher<K>>

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

Returns a WTinyLFUCache based on the size and samples

NOTE: the size is not the actual cache size, the actual size is calculated base on the size param.

pub fn with_sizes(
    window_cache_size: usize,
    protected_cache_size: usize,
    probationary_cache_size: usize,
    samples: usize
) -> Result<Self, WTinyLFUError>

Returns a WTinyLFUCache based on the related cache sizes and samples

Note

According to the TinyLFU: A Highly Efficient Cache Admission Policy

pub fn builder() -> WTinyLFUCacheBuilder<K>

Returns a WTinyLFUCacheBuilder with default configurations.

pub fn window_cache_len(&self) -> usize

pub fn window_cache_cap(&self) -> usize

pub fn main_cache_len(&self) -> usize

pub fn main_cache_cap(&self) -> usize

impl<K: Hash + Eq, V, KH: KeyHasher<K>, FH: BuildHasher, RH: BuildHasher, WH: BuildHasher> WTinyLFUCache<K, V, KH, FH, RH, WH>

pub fn from_builder(
    builder: WTinyLFUCacheBuilder<K, KH, FH, RH, WH>
) -> Result<Self, WTinyLFUError>

Creates a WTinyLFUCache according to WTinyLFUCacheBuilder

Trait Implementations

impl<K: Hash + Eq, V, KH: KeyHasher<K>, FH: BuildHasher, RH: BuildHasher, WH: BuildHasher> Cache<K, V> for WTinyLFUCache<K, V, KH, FH, RH, WH>

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

Puts a key-value pair into cache, returns a PutResult.

Example

use caches::{Cache, WTinyLFUCache};
use caches::PutResult;
let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).unwrap();

assert_eq!(PutResult::Put, cache.put(1, "a"));
assert_eq!(PutResult::Put, cache.put(2, "b"));
assert_eq!(PutResult::Update("b"), cache.put(2, "beta"));
assert_eq!(PutResult::Put, cache.put(3, "c"));

assert_eq!(cache.get(&1), Some(&"a"));
assert_eq!(cache.get(&2), Some(&"beta"));

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

Returns a reference to the value of the key in the cache or None.

Example

use caches::{Cache, WTinyLFUCache};
let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).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.

Example

use caches::{Cache, WTinyLFUCache};
let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).unwrap();

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

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

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, WTinyLFUCache};

let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).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, WTinyLFUCache};

let mut cache = WTinyLFUCache::with_sizes(1, 2, 2, 5).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 contains<Q>(&self, k: &Q) -> boolwhere
    KeyRef<K>: Borrow<Q>,
    Q: Eq + Hash + ?Sized,

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

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

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

fn purge(&mut self)

Clears the contents of the cache.

fn len(&self) -> usize

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

fn cap(&self) -> usize

Returns the maximum number of key-value pairs the cache can hold.

fn is_empty(&self) -> bool

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