5 #ifndef BITCOIN_CUCKOOCACHE_H
6 #define BITCOIN_CUCKOOCACHE_H
47 std::unique_ptr<std::atomic<uint8_t>[]>
mem;
67 size = (size + 7) / 8;
68 mem.reset(
new std::atomic<uint8_t>[size]);
69 for (uint32_t i = 0; i < size; ++i)
96 mem[s >> 3].fetch_or(uint8_t(1 << (s & 7)), std::memory_order_relaxed);
107 mem[s >> 3].fetch_and(uint8_t(~(1 << (s & 7))), std::memory_order_relaxed);
117 return (1 << (s & 7)) &
mem[s >> 3].load(std::memory_order_relaxed);
161 template <
typename Element,
typename Hash>
295 uint32_t epoch_unused_count = 0;
296 for (uint32_t i = 0; i <
size; ++i)
304 for (uint32_t i = 0; i <
size; ++i)
340 size = std::max<uint32_t>(2, new_size);
341 depth_limit =
static_cast<uint8_t
>(std::log2(
static_cast<float>(
size)));
365 std::optional<std::pair<uint32_t, size_t>>
setup_bytes(
size_t bytes)
367 size_t requested_num_elems = bytes /
sizeof(Element);
368 if (std::numeric_limits<uint32_t>::max() < requested_num_elems) {
372 auto num_elems =
setup(bytes/
sizeof(Element));
374 size_t approx_size_bytes = num_elems *
sizeof(Element);
375 return std::make_pair(num_elems, approx_size_bytes);
403 bool last_epoch =
true;
407 for (
const uint32_t loc : locs)
408 if (
table[loc] == e) {
413 for (uint8_t depth = 0; depth <
depth_limit; ++depth) {
415 for (
const uint32_t loc : locs) {
418 table[loc] = std::move(e);
437 last_loc = locs[(1 + (std::find(locs.begin(), locs.end(), last_loc) - locs.begin())) & 7];
438 std::swap(
table[last_loc], e);
440 bool epoch = last_epoch;
476 inline bool contains(
const Element& e,
const bool erase)
const
479 for (
const uint32_t loc : locs)
480 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 b 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 an epoch might be aged & an expensive scan should b...
uint32_t setup(uint32_t new_size)
setup initializes the container to store no more than new_size elements and no less than 2 elements.
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 ...
std::optional< std::pair< uint32_t, size_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
invalid returns a special index that can never be inserted to
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
contains iterates through the hash locations for a given element and checks to see if it is present.
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,...
static uint32_t FastRange32(uint32_t x, uint32_t n)
Fast range reduction with 32-bit input and 32-bit range.
uint256 Hash(const T &in1)
Compute the 256-bit hash of an object.
High-performance cache primitives.