Struct CommonCache

Source

pub struct CommonCache<K, V, R: Rng = StdRng> { /* private fields */ }

Expand description

A collection which keeps and prioritizes the most recently and commonly used items.

See the module level documentation for details.

Implementations§

Source §

impl<K, V> CommonCache<K, V>

Source

pub fn new(base: usize, max_size: Option<usize>) -> Self

Create a new CommonCache with a specific base and Rng generated from some entropy.

Takes a base which must be >1 and optionally a max_size which must be >= 2.

Source

pub fn set_max_size(&mut self, max_size: usize)

Set the max size. Note that if this might cause many elements to be removed.

PRE: max_size >= 2

Runs in linear time if max_size < self.size(), constant time otherwise.

If the new max_size is less than the previous, all indexes to this cache will be invalidated. This is because some elements might be removed randomly from the cache and we don’t want some index lookup to randomly work/fail.

Source

pub fn clear(&mut self)

Clear the cache.

Source §

impl<K, V, R: Rng> CommonCache<K, V, R>

Source

pub fn new_with_rng(base: usize, max_size: Option<usize>, rng: R) -> Self

Create a new CommonCache with a given random generator. This can be useful if you have a psuedo random generator and want deterministic and reproduceable behaviour.

Also takes in a base which must be >1 and optionally a max_size which must be >=2.

Source

pub fn size(&self) -> usize

Get the number of elements in the cache.

Runs in O(log[base](n)) time, since the len of all levels must be summed up.

Source

pub fn max_size(&self) -> usize

Get the currently configured max size for the cache.

Source §

impl<K, V, R> CommonCache<K, V, R>
where K: Eq + Hash, R: Rng,

Source

pub fn insert(&mut self, key: K, value: V) -> Entry<'_, K, V, R>

Insert a value into the cache.

If the value is new, it will be inserted at the second lowest level. So if self.base = 2, then it will be inserted in the second quarter of the cache.

If the value exists in the cache already though, it will be updated with the new key and value and be moved to one level above its previous position.

IMPORTANT: All Index to elements in this cache will be invalidated This is because some random elements will be moved between levels in the cache, and we don’t want indexes to be invalidated randomly. It might cause some erroneous tests to pass undeterministicly.

§Returns

Returns the entry for the newly inserted item.

§Examples

use common_cache::CommonCache;

let mut cache = CommonCache::new(2, None);
let mut entry = cache.insert(4, "Hello");
assert!(matches!(*entry.get_value(), "Hello"));

Source

pub fn entry<Q>(&mut self, key: &Q) -> Option<Entry<'_, K, V, R>>
where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Get a handle to an entry in the cache.

Runs in O(log[base](n)) time.

Source

pub fn iter(&self) -> impl DoubleEndedIterator<Item = (&K, &V)> + '_

Iterate over the elements in the cache so that all items on any level will come before any item on any lower level.

This does not alter the cache in any way. So no items are promoted to higher levels in the cache when iterated over.

Source

pub fn iter_mut(&mut self) -> impl Iterator<Item = (&K, &mut V)>

Iterate over mutable references to the elements in the cache. All items on any level will come before any item on any lower level.

This does not alter the structure of the cache. So no items are promoted to higher levels in the cache when iterated over.

Source

pub fn iter_indices( &self, ) -> impl DoubleEndedIterator<Item = Index<K, V, R>> + '_

Iterate over indices to the elements in the cache so that all items on any level will come before any item on any lower level.

This does not alter the cache in any way. So no items are promoted to higher levels in the cache when iterated over.

Source

pub fn find_first( &mut self, pred: impl FnMut(&K, &V) -> bool, ) -> Option<Entry<'_, K, V, R>>

Find the first item in the cache matching a predicate.

The advantage of using this method over self.iter().find() is that you get an Entry from this which can be used to promote or remove the item with.