Struct cuckoocache::cache::Cache

pub struct Cache<Element, H> where
    H: SaltedHasher<Element>,  { /* fields omitted */ }

Methods

impl<Element, HasherInstance> Cache<Element, HasherInstance> where
    HasherInstance: SaltedHasher<Element>, 

pub fn allow_erase(&self, n: usize)

allow_erase marks the element at index n as discardable.

Safety

Threadsafe without any concurrent insert.

Arguments

• n the index to allow erasure of

pub fn please_keep(&self, n: usize)

please_keep marks the element at index n as an entry that should be kept.

Safety

Threadsafe without any concurrent insert.

Arguments

• n the index to prioritize keeping

pub fn empty() -> Self where
    HasherInstance: Default, 

You must always construct a cache with some elements via a subsequent call to setup or setup_bytes, otherwise operations may segfault.

pub fn setup(&mut self, new_size: u32) -> usize

setup initializes the container to store no more than new_size elements. Returns the maximum number of elements storable

Safety

setup should only be called once.

Arguments

• new_size the desired number of elements to store. It can be any u32

pub fn setup_bytes(&mut self, new_size: usize) -> usize

pub fn insert(&mut self, e: &Element)

insert loops at most depth_limit times trying to insert a hash at various locations in the table via a variant of the Cuckoo Algorithm with eight hash locations.

It drops the last tried element if it runs out of depth before encountering an open slot.

Thus

    let x = 1;
    let mut c = cache::Cache::empty();
    c.setup(100_000);
    c.insert(x);
    c.contains(x, false);

is not guaranteed to return true.

Arguments

• e the element to insert

Posconditions

one of the following:

• All previously inserted elements and e are now in the table
• one previously inserted element is evicted from the table -the entry attempted to be inserted is evicted.

pub fn contains(&self, e: &Element, erase: bool) -> bool

contains iterates through the hash locations for a given element and checks to see if it is present. Returns true if the element is found, false otherwise

contains does not check garbage collected state (in other words, garbage is only collected when the space is needed), so:

    let mut c = cache::Cache::empty();
    c.setup(100_000);
    let x = 1;
    c.insert(x);
    if c.contains(x, true) {
        c.contains(x, false)
    } else {
        /// with low probability, insert failed
        true
    }

executed on a single thread will always return true!

This is a great property for re-org performance for example.

contains returns a bool set true if the element was found.

Arguments

• e the element to check
• erase

Postconditions

if erase is true and the element is found, then the garbage collect flag is set