Module cuckoocache::cache

cache implements a cache with properties similar to a cuckoo-set The cache is able to hold up to 2^32 elements.

Safety

Read Operations:

• contains(*, false)

Read+Erase Operations:

• contains(*, true)

Erase Operations:

• allow_erase()

Write Operations:

• setup()
• setup_bytes()
• insert()
• please_keep()

Synchronization Free Operations:

• compute_indexes()

User Must Guarantee:

1. Write Requires synchronized access (e.g., a lock)
2. Read Requires no concurrent Write, synchronized with the last insert.
3. Erase requires no concurrent Write, synchronized with last insert.
4. An Erase caller must release all memory before allowing a new Writer.

Note on function names:

• The name "allow_erase" is used because the real discard happens later.
• The name "please_keep" is used because elements may be erased anyways on insert.

Generic Types

• Element should be a movable and copyable type
• Hash should be a function/callable which takes a template parameter hash_select and an Element and extracts a hash from it. Should return high-entropy uint32_t hashes for Hash h; h<0>(e) ... h<7>(e).

Structs

Cache

Traits

SaltedHasher

Trait