Struct associative_cache::AssociativeCache

pub struct AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>,  { /* fields omitted */ }

A fixed-size associative cache mapping K keys to V values.

Capacity

The cache has a constant, fixed-size capacity which is controlled by the C type parameter and the Capacity trait. The memory for the cache entries is eagerly allocated once and never resized.

Associativity

The cache can be configured as direct-mapped, two-way associative, four-way associative, etc... via the I type parameter and Indices trait.

Replacement Policy

Can be configured to replace the least-recently used entry, or a random entry via the R type parameter and the Replacement trait.

Examples

use associative_cache::*;

// A two-way associative cache with random replacement mapping
// `String`s to `usize`s.
let cache = AssociativeCache::<
    String,
    usize,
    Capacity512,
    HashTwoWay,
    RandomReplacement
>::default();

// A four-way associative cache with random replacement mapping
// `*mut usize`s to `Vec<u8>`s.
let cache = AssociativeCache::<
    *mut usize,
    Vec<u8>,
    Capacity32,
    PointerFourWay,
    RandomReplacement
>::default();

// An eight-way associative, least recently used (LRU) cache mapping
// `std::path::PathBuf`s to `std::fs::File`s.
let cache = AssociativeCache::<
    std::path::PathBuf,
    WithLruTimestamp<std::fs::File>,
    Capacity128,
    HashEightWay,
    LruReplacement,
>::default();

Methods

impl<K, V, C, I, R> AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>, 

pub fn with_replacement_policy(replacement_policy: R) -> Self

Construct an AssociativeCache with the given replacement policy.

Example

use associative_cache::*;
use rand::{rngs::StdRng, SeedableRng};
use std::path::PathBuf;
use std::fs::File;

// Note: `RandomReplacement` requires the "rand" feature to be enabled.
let policy = RandomReplacement::with_rng(StdRng::seed_from_u64(42));

let cache = AssociativeCache::<
    PathBuf,
    File,
    Capacity128,
    HashEightWay,
    _,
>::with_replacement_policy(policy);

pub fn replacement_policy(&self) -> &R

Get a shared reference to this cache's replacement policy.

pub fn replacement_policy_mut(&mut self) -> &mut R

Get an exclusive reference to this cache's replacement policy.

pub fn capacity(&self) -> usize

Get this cache's constant capacity, aka C::CAPACITY.

pub fn len(&self) -> usize

Get the number of entries in this cache.

This is always less than or equal to the capacity.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity16,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

// Initially, the cache is empty.
assert_eq!(cache.len(), 0);

let old_entry = cache.insert("hi".to_string(), 2);

// We know the cache was empty, so there can't be an old entry that was
// replaced.
assert!(old_entry.is_none());

// And now the length is 1.
assert_eq!(cache.len(), 1);

// Insert another entry. If this doesn't conflict with the existing
// entry, then we should have a length of 2. If it did conflict, and we
// replaced the old entry, then we should still have a length of 1.
if cache.insert("bye".to_string(), 3).is_none() {
    assert_eq!(cache.len(), 2);
} else {
    assert_eq!(cache.len(), 1);
}

pub fn insert(&mut self, key: K, value: V) -> Option<(K, V)> where
    I: Indices<K, C>,
    K: PartialEq, 

Insert a new entry into the cache.

If there is an old entry for this key, or if another entry ends up getting replaced by this new one, return the old entry.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity1,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

// Insert an entry for "hi" into the cache.
let old_entry = cache.insert("hi".to_string(), 42);

// The cache was empty, so no old entry.
assert!(old_entry.is_none());

// Insert an entry for "bye" into the cache.
let old_entry = cache.insert("bye".to_string(), 1337);

// Because the cache only has a capacity of one, we replaced "hi" when
// inserting "bye".
assert_eq!(old_entry, Some(("hi".to_string(), 42)));

pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V> where
    K: Borrow<Q>,
    I: Indices<Q, C>,
    Q: PartialEq, 

Get a shared reference to the value for a given key, if it exists in the cache.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity1,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

// Returns `None` if there is no cache entry for the key.
assert!(cache.get("hi").is_none());

cache.insert("hi".to_string(), 1234);

// Otherwise, returns the value if there is an entry for the key.
assert_eq!(cache.get("hi"), Some(&1234));

pub fn get_mut<Q: ?Sized>(&mut self, key: &Q) -> Option<&mut V> where
    K: Borrow<Q>,
    I: Indices<Q, C>,
    Q: PartialEq, 

Get an exclusive reference to the value for a given key, if it exists in the cache.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity1,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

// Returns `None` if there is no cache entry for the key.
assert!(cache.get_mut("hi").is_none());

cache.insert("hi".to_string(), 1234);

// Otherwise, returns the value if there is an entry for the key.
let val = cache.get_mut("hi").unwrap();
assert_eq!(*val, 1234);

// And we can assign to the cache value.
*val = 5678;

pub fn remove<Q: ?Sized>(&mut self, key: &Q) -> Option<V> where
    K: Borrow<Q>,
    I: Indices<Q, C>,
    Q: PartialEq, 

Remove an entry from the cache.

If an entry for the key existed in the cache, it is removed and Some is returned. Otherwise, None is returned.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity1,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

// Returns `None` if there is no cache entry for the key and therefore
// nothing was removed.
assert!(cache.remove("hi").is_none());

cache.insert("hi".to_string(), 1234);

// Otherwise, returns the value that was removed if there was an entry
// for the key.
assert_eq!(cache.remove("hi"), Some(1234));

pub fn retain(&mut self, f: impl FnMut(&K, &mut V) -> bool)

Retain only the cache entries specified by the predicate.

Calls f with each entry in the cache, and removes all entries where f returned false.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    char,
    usize,
    Capacity8,
    HashDirectMapped,
    RoundRobinReplacement,
>::default();

for (i, ch) in "I let my tape rock, 'til my tape popped".char_indices() {
    cache.insert(ch, i);
}

for (key, val) in cache.iter() {
    println!("Last saw character '{}' at index {}", key, val);
}

pub fn entry<Q: ?Sized>(&mut self, key: &Q) -> Entry<K, V, C, I, R> where
    K: Borrow<Q>,
    I: Indices<Q, C>,
    Q: PartialEq, 

Get the key's corresponding slot within the cache for in-place mutation and performing get-or-create operations.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity4,
    HashTwoWay,
    RoundRobinReplacement,
>::default();

for word in "she sells sea shells down by the sea shore".split_whitespace() {
    let count = cache.entry(word).or_insert_with(
        || word.to_string(),
        || 0,
    );
    *count += 1;
}

Important traits for Iter<'a, K, V>

impl<'a, K, V> Iterator for Iter<'a, K, V> type Item = (&'a K, &'a V);

pub fn iter(&self) -> Iter<K, V>

Iterate over shared references to this cache's keys and values.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity4,
    HashTwoWay,
    RoundRobinReplacement,
>::default();

// First, insert some entries into the cache. Note that this is more
// entries than the cache has capacity for.
for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
    cache.insert(s.to_string(), s.len());
}

// Now iterate over the entries that are still in the cache:
for (k, v) in cache.iter() {
    println!("{} -> {}", k, v);
}

Important traits for IterMut<'a, K, V>

impl<'a, K, V> Iterator for IterMut<'a, K, V> type Item = (&'a K, &'a mut V);

pub fn iter_mut(&mut self) -> IterMut<K, V>

Iterate over shared references to this cache's keys and exclusive references to its values.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity4,
    HashTwoWay,
    RoundRobinReplacement,
>::default();

// First, insert some entries into the cache. Note that this is more
// entries than the cache has capacity for.
for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
    cache.insert(s.to_string(), s.len());
}

// Now iterate over the entries that are still in the cache and mutate
// them:
for (k, v) in cache.iter_mut() {
    println!("{} was {}...", k, v);
    *v += 1;
    println!("...but now it's {}!", v);
}

Important traits for IntoIter<K, V>

impl<K, V> Iterator for IntoIter<K, V> type Item = (K, V);

pub fn into_iter(self) -> IntoIter<K, V>

Consume this cache, and iterate over its keys and values.

Example

use associative_cache::*;

let mut cache = AssociativeCache::<
    String,
    usize,
    Capacity4,
    HashTwoWay,
    RoundRobinReplacement,
>::default();

// First, insert some entries into the cache. Note that this is more
// entries than the cache has capacity for.
for s in vec!["red", "blue", "green", "pink", "purple", "orange"] {
    cache.insert(s.to_string(), s.len());
}

// Not possible with `iter` or `iter_mut` without cloning.
let v: Vec<(String, usize)> = cache.into_iter().collect();

Trait Implementations

impl<K, V, C, I, R> Default for AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Default + Replacement<V, C>, 

fn default() -> Self

Returns the "default value" for a type.

impl<'a, K, V, C, I, R> IntoIterator for &'a AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>, 

type Item = (&'a K, &'a V)

The type of the elements being iterated over.

type IntoIter = Iter<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<'a, K, V, C, I, R> IntoIterator for &'a mut AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>, 

type Item = (&'a K, &'a mut V)

The type of the elements being iterated over.

type IntoIter = IterMut<'a, K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K, V, C, I, R> IntoIterator for AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>, 

type Item = (K, V)

The type of the elements being iterated over.

type IntoIter = IntoIter<K, V>

Which kind of iterator are we turning this into?

fn into_iter(self) -> Self::IntoIter

Creates an iterator from a value.

impl<K: Debug, V: Debug, C: Debug, I: Debug, R: Debug> Debug for AssociativeCache<K, V, C, I, R> where
    C: Capacity,
    R: Replacement<V, C>, 

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

Formats the value using the given formatter.