Changeset View
Changeset View
Standalone View
Standalone View
src/cuckoocache.h
Show First 20 Lines • Show All 113 Lines • ▼ Show 20 Lines | |||||
/** | /** | ||||
* cache implements a cache with properties similar to a cuckoo-set | * cache implements a cache with properties similar to a cuckoo-set | ||||
* | * | ||||
* The cache is able to hold up to (~(uint32_t)0) - 1 elements. | * The cache is able to hold up to (~(uint32_t)0) - 1 elements. | ||||
* | * | ||||
* Read Operations: | * Read Operations: | ||||
* - contains(*, false) | * - contains(*, false) | ||||
* - get(*, false) | |||||
* | * | ||||
* Read+Erase Operations: | * Read+Erase Operations: | ||||
* - contains(*, true) | * - contains(*, true) | ||||
* - get(*, true) | |||||
* | * | ||||
* Erase Operations: | * Erase Operations: | ||||
* - allow_erase() | * - allow_erase() | ||||
* | * | ||||
* Write Operations: | * Write Operations: | ||||
* - setup() | * - setup() | ||||
* - setup_bytes() | * - setup_bytes() | ||||
* - insert() | * - insert() | ||||
▲ Show 20 Lines • Show All 270 Lines • ▼ Show 20 Lines | public: | ||||
* Thus | * Thus | ||||
* | * | ||||
* insert(x); | * insert(x); | ||||
* return contains(x, false); | * return contains(x, false); | ||||
* | * | ||||
* is not guaranteed to return true. | * is not guaranteed to return true. | ||||
* | * | ||||
* @param e the element to insert | * @param e the element to insert | ||||
* @param replace | |||||
* @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. If replace is true | ||||
* and a matching element already exists, it is updated accordingly. | |||||
*/ | */ | ||||
inline void insert(Element e) { | inline void insert(Element e, bool replace = false) { | ||||
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 (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (table[loc] == e) { | if (table[loc] == e) { | ||||
if (replace) { | |||||
table[loc] = e; | |||||
// In theory if other copies existed in the table, we should | |||||
// continue searching all 8 locs to replace any other | |||||
// copies. However, due to this very check, is not possible | |||||
// for the table to reach a state with >1 copy of any given | |||||
// element. | |||||
deadalnix: I think this comment adds more to the confusion than anything else. | |||||
} | |||||
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 20 Lines • Show All 68 Lines • ▼ Show 20 Lines | inline bool contains(const Element &e, const bool erase) const { | ||||
if (erase) { | if (erase) { | ||||
allow_erase(loc); | allow_erase(loc); | ||||
} | } | ||||
return true; | return true; | ||||
} | } | ||||
} | } | ||||
return false; | return false; | ||||
} | } | ||||
/** | |||||
* get is almost identical to contains(), with the difference that it | |||||
deadalnixAuthorUnsubmitted Not Done Inline ActionsThat comment in itself is a strong tel there is some factoring that needs to takes place. deadalnix: That comment in itself is a strong tel there is some factoring that needs to takes place. | |||||
* obtains the found element (for Elements that contain key and value, | |||||
* this has the effect of obtaining the found value). | |||||
* | |||||
* @param e the element to check | |||||
* @param erase | |||||
* | |||||
* @post If the element is found, it is copied into e. If erase is true | |||||
* and the element is found, then the garbage collect flag is set. | |||||
* @returns true if the element is found, false otherwise | |||||
*/ | |||||
inline bool get(Element &e, const bool erase) const { | |||||
std::array<uint32_t, 8> locs = compute_hashes(e); | |||||
for (const uint32_t loc : locs) { | |||||
if (table[loc] == e) { | |||||
e = table[loc]; | |||||
if (erase) { | |||||
allow_erase(loc); | |||||
} | |||||
return true; | |||||
} | |||||
} | |||||
return false; | |||||
} | |||||
}; | }; | ||||
} // namespace CuckooCache | } // namespace CuckooCache | ||||
#endif // BITCOIN_CUCKOOCACHE_H | #endif // BITCOIN_CUCKOOCACHE_H |
I think this comment adds more to the confusion than anything else.