diff --git a/src/cuckoocache.h b/src/cuckoocache.h --- a/src/cuckoocache.h +++ b/src/cuckoocache.h @@ -119,9 +119,11 @@ * * Read Operations: * - contains(*, false) + * - get(*, false) * * Read+Erase Operations: * - contains(*, true) + * - get(*, true) * * Erase Operations: * - allow_erase() @@ -408,11 +410,13 @@ * is not guaranteed to return true. * * @param e the element to insert + * @param replace * @post one of the following: All previously inserted elements and e are * 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(); uint32_t last_loc = invalid(); bool last_epoch = true; @@ -421,6 +425,14 @@ // If we have, make sure that it does not get deleted. for (const uint32_t loc : locs) { 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. + } please_keep(loc); epoch_flags[loc] = last_epoch; return; @@ -505,6 +517,32 @@ } return false; } + + /** + * 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 + */ + inline bool get(Element &e, const bool erase) const { + std::array 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 diff --git a/src/test/cuckoocache_tests.cpp b/src/test/cuckoocache_tests.cpp --- a/src/test/cuckoocache_tests.cpp +++ b/src/test/cuckoocache_tests.cpp @@ -26,6 +26,50 @@ */ BOOST_AUTO_TEST_SUITE(cuckoocache_tests); +/** Example key/value element: uses bytes 0...27 for the key, and bytes 28..31 + * for the value. + */ +class ExampleMapElement : public uint256 { +public: + class CacheHasher { + public: + template + uint32_t operator()(const ExampleMapElement &element) const { + static_assert(hash_select < 8, "only has 8 hashes available."); + uint32_t u; + if (hash_select < 7) { + std::memcpy(&u, element.begin() + 4 * hash_select, 4); + } else { + // We are required to produce 8 subhashes but all key bytes have + // been used once already. So, we grab a mix of bits from each + // of the other blobs. We try to ensure more entropy on the + // higher bits, as these are what primarily get used to + // determine the index. + u = (uint32_t(*(element.begin() + 0) & 0x07) << 29) + + (uint32_t(*(element.begin() + 4) & 0x07) << 26) + + (uint32_t(*(element.begin() + 8) & 0x0f) << 22) + + (uint32_t(*(element.begin() + 16) & 0x3f) << 16) + + (uint32_t(*(element.begin() + 20) & 0xff) << 8) + + (uint32_t(*(element.begin() + 24) & 0xff) << 0); + } + return u; + } + }; + ExampleMapElement() = default; + ExampleMapElement(const uint256 &x) { + std::copy(x.begin(), x.end(), begin()); + } + void setValue(uint32_t v) { std::memcpy(begin() + 28, &v, 4); } + uint32_t getValue() { + uint32_t v; + std::memcpy(&v, begin() + 28, 4); + return v; + } + bool operator==(const ExampleMapElement &rhs) const { + return std::equal(begin(), end() - 4, rhs.begin()); + } +}; + /** * Test that no values not inserted into the cache are read out of it. * @@ -42,6 +86,16 @@ for (int x = 0; x < 100000; ++x) { BOOST_CHECK(!cc.contains(InsecureRand256(), false)); } + + SeedInsecureRand(true); + CuckooCache::cache cm{}; + cm.setup_bytes(megabytes << 20); + for (int x = 0; x < 100000; ++x) { + cm.insert(InsecureRand256()); + } + for (int x = 0; x < 100000; ++x) { + BOOST_CHECK(!cm.contains(InsecureRand256(), false)); + } }; /** @@ -117,6 +171,13 @@ megabytes, load); BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); } + for (double load = 0.1; load < 2; load *= 2) { + double hits = + test_cache>( + megabytes, load); + BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh); + } } /** This helper checks that erased elements are preferentially inserted onto and @@ -188,6 +249,9 @@ size_t megabytes = 4; test_cache_erase>( megabytes); + test_cache_erase< + CuckooCache::cache>( + megabytes); } template @@ -282,6 +346,9 @@ size_t megabytes = 4; test_cache_erase_parallel< CuckooCache::cache>(megabytes); + test_cache_erase_parallel< + CuckooCache::cache>( + megabytes); } template static void test_cache_generations() { @@ -381,6 +448,37 @@ } BOOST_AUTO_TEST_CASE(cuckoocache_generations) { test_cache_generations>(); + test_cache_generations>(); +} + +BOOST_AUTO_TEST_CASE(map) { + SeedInsecureRand(true); + CuckooCache::cache cm{}; + cm.setup_bytes(4 << 20); + for (int x = 0; x < 100000; ++x) { + ExampleMapElement elem = InsecureRand256(); + uint32_t initvalue = elem.getValue(); + uint32_t newvalue; + while ((newvalue = InsecureRand32()) == initvalue) + ; + + BOOST_CHECK(!cm.get(elem, false)); + + cm.insert(elem); + + elem.setValue(newvalue); + BOOST_CHECK(cm.get(elem, false)); + BOOST_CHECK(elem.getValue() == initvalue); + elem.setValue(newvalue); + cm.insert(elem, false); + BOOST_CHECK(cm.get(elem, false)); + BOOST_CHECK(elem.getValue() == initvalue); + elem.setValue(newvalue); + cm.insert(elem, true); + BOOST_CHECK(cm.get(elem, false)); + BOOST_CHECK(elem.getValue() == newvalue); + } } BOOST_AUTO_TEST_SUITE_END();