Changeset View
Changeset View
Standalone View
Standalone View
src/cuckoocache.h
Show First 20 Lines • Show All 204 Lines • ▼ Show 20 Lines | private: | ||||
/** | /** | ||||
* hash_function is a const instance of the hash function. It cannot be | * hash_function is a const instance of the hash function. It cannot be | ||||
* static or initialized at call time as it may have internal state (such as | * static or initialized at call time as it may have internal state (such as | ||||
* a nonce). | * a nonce). | ||||
*/ | */ | ||||
const Hash hash_function; | const Hash hash_function; | ||||
/** | /** | ||||
* Key is the key type for this map or set. | |||||
*/ | |||||
using Key = typename Element::KeyType; | |||||
/** | |||||
* compute_hashes is convenience for not having to write out this expression | * compute_hashes is convenience for not having to write out this expression | ||||
* everywhere we use the hash values of an Element. | * everywhere we use the hash values of an Element. | ||||
* | * | ||||
* We need to map the 32-bit input hash onto a hash bucket in a range [0, | * We need to map the 32-bit input hash onto a hash bucket in a range [0, | ||||
* size) in a manner which preserves as much of the hash's uniformity as | * size) in a manner which preserves as much of the hash's uniformity as | ||||
* possible. Ideally this would be done by bitmasking but the size is | * possible. Ideally this would be done by bitmasking but the size is | ||||
* usually not a power of two. | * usually not a power of two. | ||||
* | * | ||||
Show All 27 Lines | private: | ||||
* precision is required but for a 32-bit random number we only need the | * precision is required but for a 32-bit random number we only need the | ||||
* high 32 bits of a 32*32->64 multiply, which means the operation is | * high 32 bits of a 32*32->64 multiply, which means the operation is | ||||
* reasonably fast even on a typical 32-bit processor. | * reasonably fast even on a typical 32-bit processor. | ||||
* | * | ||||
* @param e The element whose hashes will be returned | * @param e The element whose hashes will be returned | ||||
* @returns Deterministic hashes derived from `e` uniformly mapped onto the | * @returns Deterministic hashes derived from `e` uniformly mapped onto the | ||||
* range [0, size) | * range [0, size) | ||||
*/ | */ | ||||
inline std::array<uint32_t, 8> compute_hashes(const Element &e) const { | inline std::array<uint32_t, 8> compute_hashes(const Key &k) const { | ||||
return {{uint32_t(uint64_t(hash_function.template operator()<0>(e)) * | return {{uint32_t(uint64_t(hash_function.template operator()<0>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<1>(e)) * | uint32_t(uint64_t(hash_function.template operator()<1>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<2>(e)) * | uint32_t(uint64_t(hash_function.template operator()<2>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<3>(e)) * | uint32_t(uint64_t(hash_function.template operator()<3>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<4>(e)) * | uint32_t(uint64_t(hash_function.template operator()<4>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<5>(e)) * | uint32_t(uint64_t(hash_function.template operator()<5>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<6>(e)) * | uint32_t(uint64_t(hash_function.template operator()<6>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32), | 32), | ||||
uint32_t(uint64_t(hash_function.template operator()<7>(e)) * | uint32_t(uint64_t(hash_function.template operator()<7>(k)) * | ||||
uint64_t(size) >> | uint64_t(size) >> | ||||
32)}}; | 32)}}; | ||||
} | } | ||||
/** | /** | ||||
* invalid returns a special index that can never be inserted to | * invalid returns a special index that can never be inserted to | ||||
* @returns the special constexpr index that can never be inserted to | * @returns the special constexpr index that can never be inserted to | ||||
*/ | */ | ||||
▲ Show 20 Lines • Show All 132 Lines • ▼ Show 20 Lines | public: | ||||
* @post one of the following: All previously inserted elements and e are | * @post one of the following: All previously inserted elements and e are | ||||
* now in the table, one previously inserted element is evicted from the | * now in the table, one previously inserted element is evicted from the | ||||
* table, the entry attempted to be inserted is evicted. | * table, the entry attempted to be inserted is evicted. | ||||
*/ | */ | ||||
inline void insert(Element e) { | inline void insert(Element e) { | ||||
epoch_check(); | epoch_check(); | ||||
uint32_t last_loc = invalid(); | uint32_t last_loc = invalid(); | ||||
bool last_epoch = true; | bool last_epoch = true; | ||||
std::array<uint32_t, 8> locs = compute_hashes(e); | std::array<uint32_t, 8> locs = compute_hashes(e.getKey()); | ||||
// Make sure we have not already inserted this element. | // Make sure we have not already inserted this element. | ||||
// If we have, make sure that it does not get deleted. | // If we have, make sure that it does not get deleted. | ||||
for (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (table[loc].matchKey(e)) { | if (table[loc].getKey() == e.getKey()) { | ||||
please_keep(loc); | please_keep(loc); | ||||
epoch_flags[loc] = last_epoch; | epoch_flags[loc] = last_epoch; | ||||
return; | return; | ||||
} | } | ||||
} | } | ||||
for (uint8_t depth = 0; depth < depth_limit; ++depth) { | for (uint8_t depth = 0; depth < depth_limit; ++depth) { | ||||
// First try to insert to an empty slot, if one exists | // First try to insert to an empty slot, if one exists | ||||
for (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
Show All 26 Lines | inline void insert(Element e) { | ||||
7]; | 7]; | ||||
std::swap(table[last_loc], e); | std::swap(table[last_loc], e); | ||||
// Can't std::swap a std::vector<bool>::reference and a bool&. | // Can't std::swap a std::vector<bool>::reference and a bool&. | ||||
bool epoch = last_epoch; | bool epoch = last_epoch; | ||||
last_epoch = epoch_flags[last_loc]; | last_epoch = epoch_flags[last_loc]; | ||||
epoch_flags[last_loc] = epoch; | epoch_flags[last_loc] = epoch; | ||||
// Recompute the locs -- unfortunately happens one too many times! | // Recompute the locs -- unfortunately happens one too many times! | ||||
locs = compute_hashes(e); | locs = compute_hashes(e.getKey()); | ||||
} | } | ||||
} | } | ||||
/** | /** | ||||
* contains iterates through the hash locations for a given element and | * contains iterates through the hash locations for a given element and | ||||
* checks to see if it is present. | * checks to see if it is present. | ||||
* | * | ||||
* contains does not check garbage collected state (in other words, garbage | * contains does not check garbage collected state (in other words, garbage | ||||
Show All 15 Lines | public: | ||||
* | * | ||||
* @param e the element to check | * @param e the element to check | ||||
* @param erase whether to attempt setting the garbage collect flag | * @param erase whether to attempt setting the garbage collect flag | ||||
* | * | ||||
* @post if erase is true and the element is found, then the garbage collect | * @post if erase is true and the element is found, then the garbage collect | ||||
* flag is set | * flag is set | ||||
* @returns true if the element is found, false otherwise | * @returns true if the element is found, false otherwise | ||||
*/ | */ | ||||
inline bool contains(const Element &e, const bool erase) const { | inline bool contains(const Key &k, const bool erase) const { | ||||
std::array<uint32_t, 8> locs = compute_hashes(e); | std::array<uint32_t, 8> locs = compute_hashes(k); | ||||
for (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (table[loc].matchKey(e)) { | if (table[loc].getKey() == k) { | ||||
if (erase) { | if (erase) { | ||||
allow_erase(loc); | allow_erase(loc); | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
}; | }; | ||||
/** | /** | ||||
* Helper class used when we only want the cache to be a set rather than a map. | * Helper class used when we only want the cache to be a set rather than a map. | ||||
*/ | */ | ||||
template <typename T> struct KeyOnly : public T { | template <typename T> struct KeyOnly : public T { | ||||
// For contains. | |||||
using KeyType = T; | |||||
// Ensure implicit conversion from T. | // Ensure implicit conversion from T. | ||||
KeyOnly() = default; | KeyOnly() = default; | ||||
KeyOnly(const T &x) : T(x) {} | KeyOnly(const T &x) : T(x) {} | ||||
// Implement required features. | // Implement required features. | ||||
bool matchKey(const T &key) const { return *this == key; } | const T &getKey() const { return *this; } | ||||
}; | }; | ||||
} // namespace CuckooCache | } // namespace CuckooCache | ||||
#endif // BITCOIN_CUCKOOCACHE_H | #endif // BITCOIN_CUCKOOCACHE_H |