Changeset View
Changeset View
Standalone View
Standalone View
src/cuckoocache.h
Show First 20 Lines • Show All 409 Lines • ▼ Show 20 Lines | public: | ||||
*/ | */ | ||||
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); | ||||
// 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 (uint32_t loc : locs) | for (const uint32_t loc : locs) | ||||
if (table[loc] == e) { | if (table[loc] == e) { | ||||
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 (uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (!collection_flags.bit_is_set(loc)) continue; | if (!collection_flags.bit_is_set(loc)) continue; | ||||
table[loc] = std::move(e); | table[loc] = std::move(e); | ||||
please_keep(loc); | please_keep(loc); | ||||
epoch_flags[loc] = last_epoch; | epoch_flags[loc] = last_epoch; | ||||
return; | return; | ||||
} | } | ||||
/** | /** | ||||
* Swap with the element at the location that was not the last one | * Swap with the element at the location that was not the last one | ||||
▲ Show 20 Lines • Show All 48 Lines • ▼ Show 20 Lines | public: | ||||
* @param erase | * @param erase | ||||
* | * | ||||
* @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 Element &e, const bool erase) const { | ||||
std::array<uint32_t, 8> locs = compute_hashes(e); | std::array<uint32_t, 8> locs = compute_hashes(e); | ||||
for (uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (table[loc] == e) { | if (table[loc] == e) { | ||||
if (erase) { | if (erase) { | ||||
allow_erase(loc); | allow_erase(loc); | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
}; | }; | ||||
} // namespace CuckooCache | } // namespace CuckooCache | ||||
#endif // BITCOIN_CUCKOOCACHE_H | #endif // BITCOIN_CUCKOOCACHE_H |