cache implements a cache with properties similar to a cuckoo-set.
Declared in <cuckoocache.h>
template<
typename Element,
typename Hash>
class cache;The cache is able to hold up to (~(uint32_t)0) - 1 elements.
Read Operations:
contains() for erase=false
Read+Erase Operations:
contains() for erase=true
Erase Operations:
allow_erase()
Write Operations:
setup()
setup_bytes()
insert()
please_keep()
Synchronization Free Operations:
invalid()
compute_hashes()
User Must Guarantee:
1. Write requires synchronized access (e.g. a lock) 2. Read requires no concurrent Write, synchronized with 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.
| Name | Description |
|---|---|
cache [constructor] | You must always construct a cache with some elements via a subsequent call to setup or setup_bytes, otherwise operations may segfault. |
TestOnlyReset | Empty the cache and re-run setup(). |
contains | contains iterates through the hash locations for a given element and checks to see if it is present. |
insert | 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. |
setup | setup initializes the container to store no more than new_size elements and no less than 2 elements. |
setup_bytes | setup_bytes is a convenience function which accounts for internal memory usage when deciding how many elements to store. It isn't perfect because it doesn't account for any overhead (struct size, MallocUsage, collection and epoch flags). This was done to simplify selecting a power of two size. In the expected use case, an extra two bits per entry should be negligible compared to the size of the elements. |
| Name | Description |
|---|---|
| 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). |