Changeset View
Changeset View
Standalone View
Standalone View
src/cuckoocache.h
Show First 20 Lines • Show All 115 Lines • ▼ Show 20 Lines | |||||
/** | /** | ||||
* @ref cache implements a cache with properties similar to a cuckoo-set. | * @ref 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() for `erase=false` | * - contains() for `erase=false` | ||||
* - get() for `erase=false` | |||||
* | * | ||||
* Read+Erase Operations: | * Read+Erase Operations: | ||||
* - contains() for `erase=true` | * - contains() for `erase=true` | ||||
* - get() for `erase=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 281 Lines • ▼ Show 20 Lines | public: | ||||
* ``` | * ``` | ||||
* 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 weither to replace if an existing element with the same key is | |||||
* found. | |||||
* @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.getKey()); | 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].getKey() == e.getKey()) { | if (table[loc].getKey() == e.getKey()) { | ||||
if (replace) { | |||||
table[loc] = std::move(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 (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
▲ Show 20 Lines • Show All 51 Lines • ▼ Show 20 Lines | public: | ||||
* ``` | * ``` | ||||
* | * | ||||
* executed on a single thread will always return true! | * executed on a single thread will always return true! | ||||
* | * | ||||
* This is a great property for re-org performance for example. | * This is a great property for re-org performance for example. | ||||
* | * | ||||
* contains returns a bool set true if the element was found. | * contains returns a bool set true if the element was found. | ||||
* | * | ||||
* @param e the element to check | * @param k the key 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 Key &k, const bool erase) const { | bool contains(const Key &k, const bool erase) const { | ||||
return find(k, erase) != nullptr; | |||||
} | |||||
/** | |||||
* get is almost identical to contains(), with the difference that it | |||||
* 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 | |||||
*/ | |||||
bool get(Element &e, const bool erase) const { | |||||
if (const Element *eptr = find(e.getKey(), erase)) { | |||||
e = *eptr; | |||||
return true; | |||||
} | |||||
return false; | |||||
} | |||||
private: | |||||
const Element *find(const Key &k, const bool erase) const { | |||||
std::array<uint32_t, 8> locs = compute_hashes(k); | std::array<uint32_t, 8> locs = compute_hashes(k); | ||||
for (const uint32_t loc : locs) { | for (const uint32_t loc : locs) { | ||||
if (table[loc].getKey() == k) { | if (table[loc].getKey() == k) { | ||||
if (erase) { | if (erase) { | ||||
allow_erase(loc); | allow_erase(loc); | ||||
} | } | ||||
return true; | return &table[loc]; | ||||
} | } | ||||
} | } | ||||
return false; | return nullptr; | ||||
} | } | ||||
}; | }; | ||||
/** | /** | ||||
* 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. | // For contains. | ||||
Show All 13 Lines |