Trait associative_cache::Indices

pub trait Indices<K, C> where
    K: ?Sized,
    C: Capacity, {
    type Indices: ExactSizeIterator<Item = usize>;
    fn indices(key: &K) -> Self::Indices;
}

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:

1. Hash-based implementations: HashDirectMapped and Hash{Two,Four,Eight,Sixteen,ThirtyTwo}Way provide various associativity levels based on the key's Hash implementation.

2. Pointer-based implementations: PointerDirectMapped and Pointer{Two,Four,Eight,Sixteen,ThirtyTwo}Way provide 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.

Associated Types

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.

Loading content...

Required methods

fn indices(key: &K) -> Self::Indices

Get the indices within the range 0..C::CAPACITY representing slots in the cache where the given key's entry might reside.

Loading content...

Implementors

impl<T, C> Indices<*const T, C> for PointerDirectMapped where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*const T, C> for PointerEightWay where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*const T, C> for PointerFourWay where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*const T, C> for PointerSixteenWay where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*const T, C> for PointerThirtyTwoWay where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*const T, C> for PointerTwoWay where
    C: Capacity, 

type Indices = Self::Indices

fn indices(ptr: &*const T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerDirectMapped where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerEightWay where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerFourWay where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerSixteenWay where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerThirtyTwoWay where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T, C> Indices<*mut T, C> for PointerTwoWay where
    C: Capacity, 

type Indices = Range<usize>

fn indices(ptr: &*mut T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashDirectMapped<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashEightWay<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashFourWay<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashSixteenWay<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashThirtyTwoWay<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

impl<T: ?Sized, C, H> Indices<T, C> for HashTwoWay<H> where
    T: Hash,
    C: Capacity,
    H: Hasher + Default, 

type Indices = Range<usize>

fn indices(key: &T) -> Self::Indices

Loading content...