5 #ifndef _BITCOIN_CUCKOOCACHE_H_
6 #define _BITCOIN_CUCKOOCACHE_H_
44 std::unique_ptr<std::atomic<uint8_t>[]>
mem;
64 size = (size + 7) / 8;
65 mem.reset(
new std::atomic<uint8_t>[size]);
66 for (uint32_t i = 0; i < size; ++i)
94 mem[s >> 3].fetch_or(1 << (s & 7), std::memory_order_relaxed);
105 mem[s >> 3].fetch_and(~(1 << (s & 7)), std::memory_order_relaxed);
115 return (1 << (s & 7)) &
mem[s >> 3].load(std::memory_order_relaxed);
159 template <
typename Element,
typename Hash>
272 uint32_t epoch_unused_count = 0;
273 for (uint32_t i = 0; i <
size; ++i)
281 for (uint32_t i = 0; i <
size; ++i)
318 depth_limit =
static_cast<uint8_t
>(std::log2(
static_cast<float>(std::max((uint32_t)2, new_size))));
345 return setup(bytes/
sizeof(Element));
372 bool last_epoch =
true;
376 for (uint32_t loc : locs)
377 if (
table[loc] == e) {
382 for (uint8_t depth = 0; depth <
depth_limit; ++depth) {
384 for (uint32_t loc : locs) {
387 table[loc] = std::move(e);
406 last_loc = locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) - locs.begin())) & 7];
407 std::swap(
table[last_loc], e);
409 bool epoch = last_epoch;
443 inline bool contains(
const Element& e,
const bool erase)
const
446 for (uint32_t loc : locs)
447 if (
table[loc] == e) {
bit_packed_atomic_flags implements a container for garbage collection flags that is only thread unsaf...
void bit_set(uint32_t s)
bit_set sets an entry as discardable.
void setup(uint32_t b)
setup marks all entries and ensures that bit_packed_atomic_flags can store at least size entries
bit_packed_atomic_flags()=delete
No default constructor as there must be some size.
bool bit_is_set(uint32_t s) const
bit_is_set queries the table for discardability at s
void bit_unset(uint32_t s)
bit_unset marks an entry as something that should not be overwritten
bit_packed_atomic_flags(uint32_t size)
bit_packed_atomic_flags constructor creates memory to sufficiently keep track of garbage collection i...
std::unique_ptr< std::atomic< uint8_t >[]> mem
cache implements a cache with properties similar to a cuckoo-set
uint32_t size
size stores the total available slots in the hash table
uint8_t depth_limit
depth_limit determines how many elements insert should try to replace.
std::vector< Element > table
table stores all the elements
uint32_t epoch_heuristic_counter
epoch_heuristic_counter is used to determine when a epoch might be aged & an expensive scan should be...
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements.
uint32_t hash_mask
hash_mask should be set to appropriately mask out a hash such that every masked hash is [0,...
void epoch_check()
epoch_check handles the changing of epochs for elements stored in the cache.
uint32_t epoch_size
epoch_size is set to be the number of elements supposed to be in a epoch.
std::vector< bool > epoch_flags
epoch_flags tracks how recently an element was inserted into the cache.
void insert(Element e)
insert loops at most depth_limit times trying to insert a hash at various locations in the table via ...
bit_packed_atomic_flags collection_flags
The bit_packed_atomic_flags array is marked mutable because we want garbage collection to be allowed ...
std::array< uint32_t, 8 > compute_hashes(const Element &e) const
compute_hashes is convenience for not having to write out this expression everywhere we use the hash ...
uint32_t setup_bytes(size_t bytes)
setup_bytes is a convenience function which accounts for internal memory usage when deciding how many...
constexpr uint32_t invalid() const
const Hash hash_function
hash_function is a const instance of the hash function.
void allow_erase(uint32_t n) const
allow_erase marks the element at index n as discardable.
bool contains(const Element &e, const bool erase) const
void please_keep(uint32_t n) const
please_keep marks the element at index n as an entry that should be kept.
cache()
You must always construct a cache with some elements via a subsequent call to setup or setup_bytes,...
uint256 Hash(const T1 pbegin, const T1 pend)
Compute the 256-bit hash of an object.
namespace CuckooCache provides high performance cache primitives