Struct scc::hash_cache::HashCache

pub struct HashCache<K, V, H = RandomState>where
    K: Eq + Hash,
    H: BuildHasher,{ /* private fields */ }

Scalable concurrent sampling-based LRU cache backed by HashMap.

HashCache is a concurrent sampling-based LRU cache that is based on the HashMap implementation. HashCache does not keep track of the least recently used entry in the entire cache, instead each bucket maintains a doubly linked list of occupied entries which is updated on access to entries in order to keep track of the least recently used entry within the bucket.

HashCache and HashMap share the same runtime characteristic, except that HashCache does not allow a bucket to allocate a linked list of entries when it is full, instead HashCache starts evicting the least recently used entries.

Unwind safety

HashCache is impervious to out-of-memory errors and panics in user specified code on one condition; H::Hasher::hash, K::drop and V::drop must not panic.

Implementations

impl<K, V, H> HashCache<K, V, H>where K: Eq + Hash, H: BuildHasher,

pub fn with_hasher(build_hasher: H) -> Self

Creates an empty HashCache with the given BuildHasher.

The maximum capacity is set to DEFAULT_MAXIMUM_CAPACITY.

Examples

use scc::HashCache;
use std::collections::hash_map::RandomState;

let hashcache: HashCache<u64, u32, RandomState> = HashCache::with_hasher(RandomState::new());

pub fn with_capacity_and_hasher( minimum_capacity: usize, maximum_capacity: usize, build_hasher: H ) -> Self

Creates an empty HashCache with the specified capacity and BuildHasher.

The actual capacity is equal to or greater than the specified capacity.

Examples

use scc::HashCache;
use std::collections::hash_map::RandomState;

let hashcache: HashCache<u64, u32, RandomState> =
    HashCache::with_capacity_and_hasher(1000, 2000, RandomState::new());

let result = hashcache.capacity();
assert_eq!(result, 1024);

pub fn entry(&self, key: K) -> Entry<'_, K, V, H>

Gets the entry associated with the given key in the map for in-place manipulation.

Examples

use scc::HashCache;

let hashcache: HashCache<char, u32> = HashCache::default();

for ch in "a short treatise on fungi".chars() {
    hashcache.entry(ch).and_modify(|counter| *counter += 1).or_put(1);
}

assert_eq!(*hashcache.get(&'s').unwrap().get(), 2);
assert_eq!(*hashcache.get(&'t').unwrap().get(), 3);
assert!(hashcache.get(&'y').is_none());

pub async fn entry_async(&self, key: K) -> Entry<'_, K, V, H>

Gets the entry associated with the given key in the map for in-place manipulation.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<char, u32> = HashCache::default();

let future_entry = hashcache.entry_async('b');

pub fn put(&self, key: K, val: V) -> Result<EvictedEntry<K, V>, (K, V)>

Puts a key-value pair into the HashCache.

Returns Some if an entry was evicted for the new key-value pair.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert_eq!(hashcache.put(1, 1).unwrap_err(), (1, 1));

pub async fn put_async( &self, key: K, val: V ) -> Result<EvictedEntry<K, V>, (K, V)>

Puts a key-value pair into the HashCache.

Returns Some if an entry was evicted for the new key-value pair. It is an asynchronous method returning an impl Future for the caller to await.

Errors

Returns an error along with the supplied key-value pair if the key exists.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();
let future_put = hashcache.put_async(11, 17);

pub fn get<Q>(&self, key: &Q) -> Option<OccupiedEntry<'_, K, V, H>>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Gets an occupied entry corresponding to the key.

Returns None if the key does not exist.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.get(&1).is_none());
assert!(hashcache.put(1, 10).is_ok());
assert_eq!(*hashcache.get(&1).unwrap().get(), 10);

pub async fn get_async<Q>(&self, key: &Q) -> Option<OccupiedEntry<'_, K, V, H>>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Gets an occupied entry corresponding to the key.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();
let future_put = hashcache.put_async(11, 17);
let future_get = hashcache.get_async(&11);

pub fn read<Q, R, F: FnOnce(&K, &V) -> R>( &self, key: &Q, reader: F ) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Reads a key-value pair.

Returns None if the key does not exist.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.read(&1, |_, v| *v).is_none());
assert!(hashcache.put(1, 10).is_ok());
assert_eq!(hashcache.read(&1, |_, v| *v).unwrap(), 10);

pub async fn read_async<Q, R, F: FnOnce(&K, &V) -> R>( &self, key: &Q, reader: F ) -> Option<R>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Reads a key-value pair.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();
let future_put = hashcache.put_async(11, 17);
let future_read = hashcache.read_async(&11, |_, v| *v);

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

Checks if the key exists.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(!hashcache.contains(&1));
assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.contains(&1));

pub async fn contains_async<Q>(&self, key: &Q) -> boolwhere K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Checks if the key exists.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let future_contains = hashcache.contains_async(&1);

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

Removes a key-value pair if the key exists.

Returns None if the key does not exist.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.remove(&1).is_none());
assert!(hashcache.put(1, 0).is_ok());
assert_eq!(hashcache.remove(&1).unwrap(), (1, 0));
assert_eq!(hashcache.capacity(), 0);

pub async fn remove_async<Q>(&self, key: &Q) -> Option<(K, V)>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists.

Returns None if the key does not exist. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();
let future_put = hashcache.put_async(11, 17);
let future_remove = hashcache.remove_async(&11);

pub fn remove_if<Q, F: FnOnce(&mut V) -> bool>( &self, key: &Q, condition: F ) -> Option<(K, V)>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists and the given condition is met.

Returns None if the key does not exist or the condition was not met.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.remove_if(&1, |v| { *v += 1; false }).is_none());
assert_eq!(hashcache.remove_if(&1, |v| *v == 1).unwrap(), (1, 1));
assert_eq!(hashcache.capacity(), 0);

pub async fn remove_if_async<Q, F: FnOnce(&mut V) -> bool>( &self, key: &Q, condition: F ) -> Option<(K, V)>where K: Borrow<Q>, Q: Eq + Hash + ?Sized,

Removes a key-value pair if the key exists and the given condition is met.

Returns None if the key does not exist or the condition was not met. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();
let future_put = hashcache.put_async(11, 17);
let future_remove = hashcache.remove_if_async(&11, |_| true);

pub fn scan<F: FnMut(&K, &V)>(&self, scanner: F)

Scans all the entries.

This method does not affect the LRU information in each bucket.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another thread.

Examples

use scc::HashCache;

let hashcache: HashCache<usize, usize> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 1).is_ok());

let mut sum = 0;
hashcache.scan(|k, v| { sum += *k + *v; });
assert_eq!(sum, 4);

pub async fn scan_async<F: FnMut(&K, &V)>(&self, scanner: F)

Scans all the entries.

This method does not affect the LRU information in each bucket.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another task.

Examples

use scc::HashCache;

let hashcache: HashCache<usize, usize> = HashCache::default();

let future_put = hashcache.put_async(1, 0);
let future_scan = hashcache.scan_async(|k, v| println!("{k} {v}"));

pub fn any<P: FnMut(&K, &V) -> bool>(&self, pred: P) -> bool

Searches for any entry that satisfies the given predicate.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another thread.

Returns true as soon as an entry satisfying the predicate is found.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 1).is_ok());
assert!(hashcache.put(3, 2).is_ok());

assert!(hashcache.any(|k, v| *k == 1 && *v == 0));
assert!(!hashcache.any(|k, v| *k == 2 && *v == 0));

pub async fn any_async<P: FnMut(&K, &V) -> bool>(&self, pred: P) -> bool

Searches for any entry that satisfies the given predicate.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another task.

It is an asynchronous method returning an impl Future for the caller to await.

Returns true as soon as an entry satisfying the predicate is found.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let future_put = hashcache.put_async(1, 0);
let future_any = hashcache.any_async(|k, _| *k == 1);

pub fn for_each<F: FnMut(&K, &mut V)>(&self, f: F)

Iterates over all the entries in the HashCache allowing modifying each value.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another thread.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 1).is_ok());

let mut acc = 0;
hashcache.for_each(|k, v| { acc += *k; *v = 2; });
assert_eq!(acc, 3);
assert_eq!(hashcache.read(&1, |_, v| *v).unwrap(), 2);
assert_eq!(hashcache.read(&2, |_, v| *v).unwrap(), 2);

pub async fn for_each_async<F: FnMut(&K, &mut V)>(&self, f: F)

Iterates over all the entries in the HashCache allowing modifying each value.

Key-value pairs that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same key-value pair can be visited more than once if the HashCache gets resized by another task.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let future_put = hashcache.put_async(1, 0);
let future_for_each = hashcache.for_each_async(|k, v| println!("{} {}", k, v));

pub fn retain<F: FnMut(&K, &mut V) -> bool>(&self, pred: F) -> (usize, usize)

Retains the entries specified by the predicate.

This method allows the predicate closure to modify the value field.

Entries that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same entry can be visited more than once if the HashCache gets resized by another thread.

Returns (number of remaining entries, number of removed entries) where the number of remaining entries can be larger than the actual number since the same entry can be visited more than once.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert!(hashcache.put(2, 1).is_ok());
assert!(hashcache.put(3, 2).is_ok());

assert_eq!(hashcache.retain(|k, v| *k == 1 && *v == 0), (1, 2));

pub async fn retain_async<F: FnMut(&K, &mut V) -> bool>( &self, filter: F ) -> (usize, usize)

Retains the entries specified by the predicate.

This method allows the predicate closure to modify the value field.

Entries that have existed since the invocation of the method are guaranteed to be visited if they are not removed, however the same entry can be visited more than once if the HashCache gets resized by another thread.

Returns (number of remaining entries, number of removed entries) where the number of remaining entries can be larger than the actual number since the same entry can be visited more than once. It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let future_put = hashcache.put_async(1, 0);
let future_retain = hashcache.retain_async(|k, v| *k == 1);

pub fn clear(&self) -> usize

Clears all the key-value pairs.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert_eq!(hashcache.clear(), 1);

pub async fn clear_async(&self) -> usize

Clears all the key-value pairs.

It is an asynchronous method returning an impl Future for the caller to await.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let future_put = hashcache.put_async(1, 0);
let future_clear = hashcache.clear_async();

pub fn len(&self) -> usize

Returns the number of entries in the HashCache.

It reads the entire metadata area of the bucket array to calculate the number of valid entries, making its time complexity O(N). Furthermore, it may overcount entries if an old bucket array has yet to be dropped.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.put(1, 0).is_ok());
assert_eq!(hashcache.len(), 1);

pub fn is_empty(&self) -> bool

Returns true if the HashCache is empty.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert!(hashcache.is_empty());
assert!(hashcache.put(1, 0).is_ok());
assert!(!hashcache.is_empty());

pub fn capacity(&self) -> usize

Returns the capacity of the HashCache.

Examples

use scc::HashCache;

let hashcache_default: HashCache<u64, u32> = HashCache::default();
assert_eq!(hashcache_default.capacity(), 0);

let hashcache: HashCache<u64, u32> = HashCache::with_capacity(1000000, 2000000);
assert_eq!(hashcache.capacity(), 1048576);

pub fn capacity_range(&self) -> RangeInclusive<usize>

Returns the current capacity range of the HashCache.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

assert_eq!(hashcache.capacity_range(), 0..=256);

impl<K, V> HashCache<K, V, RandomState>where K: Eq + Hash,

pub fn new() -> Self

Creates an empty default HashCache.

The maximum capacity is set to DEFAULT_MAXIMUM_CAPACITY.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::new();

let result = hashcache.capacity();
assert_eq!(result, 0);

pub fn with_capacity(minimum_capacity: usize, maximum_capacity: usize) -> Self

Creates an empty HashCache with the specified capacity.

The supplied minimum and maximum capacity values are adjusted to any suitable power-of-two values that are close to them.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::with_capacity(1000, 2000);

let result = hashcache.capacity();
assert_eq!(result, 1024);

Trait Implementations

impl<K, V, H> Debug for HashCache<K, V, H>where K: Debug + Eq + Hash, V: Debug, H: BuildHasher,

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

Iterates over all the entries in the HashCache to print them.

Locking behavior

Shared locks on buckets are acquired during iteration, therefore any Entry, OccupiedEntry or VacantEntry owned by the current thread will lead to a deadlock.

impl<K, V, H> Default for HashCache<K, V, H>where K: Eq + Hash, H: BuildHasher + Default,

fn default() -> Self

Creates an empty default HashCache.

The maximum capacity is set to DEFAULT_MAXIMUM_CAPACITY.

Examples

use scc::HashCache;

let hashcache: HashCache<u64, u32> = HashCache::default();

let result = hashcache.capacity();
assert_eq!(result, 0);

impl<K, V, H> Drop for HashCache<K, V, H>where K: Eq + Hash, H: BuildHasher,

fn drop(&mut self)

Executes the destructor for this type.

impl<K, V, H> PartialEq<HashCache<K, V, H>> for HashCache<K, V, H>where K: Eq + Hash, V: PartialEq, H: BuildHasher,

fn eq(&self, other: &Self) -> bool

Compares two HashCache instances.

Locking behavior

Shared locks on buckets are acquired when comparing two instances of HashCache, therefore it may lead to a deadlock if the instances are being modified by another thread.

fn ne(&self, other: &Rhs) -> bool

This method tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.