pub trait Indices<K, C>{
type Indices: ExactSizeIterator<Item = usize>;
// Required method
fn indices(key: &K) -> Self::Indices;
}Expand description
Given a cache key, return all the slots within the cache where its entry might be.
§Associativity
The associativity of a cache is how many slots in the cache a key might reside in. There are generally many more possible values than there is capacity in the cache. Allowing a entry to be in one of multiple slots within the cache raises the cache hit rate, but takes a little extra time when querying the cache because each of those multiple slots need to be considered.
-
Direct-mapped: A cache key corresponds to only one possible slot in the cache.
-
Two-way: A cache key corresponds to two possible slots in the cache.
-
Four-way: A cache key corresponds to four possible slots in the cache.
-
Etc…
Wikipedia has more details on cache associativity.
§Provided Implementations
This crate provides two flavors of associativity out of the box:
-
Hash-based implementations:HashDirectMappedandHash{Two,Four,Eight,Sixteen,ThirtyTwo}Wayprovide various associativity levels based on the key’sHashimplementation. -
Pointer-based implementations:
PointerDirectMappedandPointer{Two,Four,Eight,Sixteen,ThirtyTwo}Wayprovide various associativity levels based on the pointer value, taking advantage of its referenced type’s alignment. This will generally provide faster lookups than hashing, but is less general.
§Custom Implementation Requirements
Implementations must be determinisitc.
All indices yielded must be within the capacity.
The iterator must always be non-empty.
For example, to implement a two-way cache, return an iterator of two indices.
Required Associated Types§
Sourcetype Indices: ExactSizeIterator<Item = usize>
type Indices: ExactSizeIterator<Item = usize>
The iterator over indices within the range 0..C::CAPACITY yielding the
slots in the cache where the key’s entry might reside.
Required Methods§
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.