diff --git a/src/cuckoocache.h b/src/cuckoocache.h
--- a/src/cuckoocache.h
+++ b/src/cuckoocache.h
@@ -121,9 +121,11 @@
*
* Read Operations:
* - contains() for `erase=false`
+ * - get() for `erase=false`
*
* Read+Erase Operations:
* - contains() for `erase=true`
+ * - get() for `erase=true`
*
* Erase Operations:
* - allow_erase()
@@ -421,11 +423,14 @@
* is not guaranteed to return true.
*
* @param e the element to insert
+ * @param weither to replace if an existing element witht he same key is
+ * found.
* @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;
@@ -434,6 +439,9 @@
// If we have, make sure that it does not get deleted.
for (const uint32_t loc : locs) {
if (table[loc].getKey() == e.getKey()) {
+ if (replace) {
+ table[loc] = std::move(e);
+ }
please_keep(loc);
epoch_flags[loc] = last_epoch;
return;
@@ -508,17 +516,43 @@
* flag is set
* @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);
for (const uint32_t loc : locs) {
if (table[loc].getKey() == k) {
if (erase) {
allow_erase(loc);
}
- return true;
+ return &table[loc];
}
}
- return false;
+ return nullptr;
}
};
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
@@ -27,6 +27,80 @@
*/
BOOST_AUTO_TEST_SUITE(cuckoocache_tests);
+/**
+ * Example key/value element. The key is 28 bytes long and the value 4, for a
+ * total of 32 bytes.
+ */
+struct TestMapElement {
+ struct KeyType {
+ std::array<uint8_t, 28> data;
+
+ KeyType() = default;
+ KeyType(const KeyType &rhs) = default;
+
+ KeyType(const uint256 &k) {
+ std::copy(k.begin() + 4, k.end(), data.begin());
+ }
+
+ bool operator==(const KeyType &rhs) const { return rhs.data == data; }
+ };
+
+private:
+ KeyType key;
+ uint32_t value;
+
+public:
+ TestMapElement() = default;
+ TestMapElement(const TestMapElement &rhs) = default;
+
+ TestMapElement(const uint256 &data)
+ : TestMapElement(data, data.GetUint64(0)) {}
+ TestMapElement(const KeyType &keyIn, uint32_t valueIn)
+ : key(keyIn), value(valueIn) {}
+
+ const KeyType &getKey() const { return key; }
+ uint32_t getValue() const { return value; }
+
+ class CacheHasher {
+ public:
+ template <uint8_t hash_select>
+ uint32_t operator()(const KeyType &k) const {
+ static_assert(hash_select < 8, "only has 8 hashes available.");
+
+ const auto &d = k.data;
+
+ uint32_t u;
+ if (hash_select < 7) {
+ std::memcpy(&u, d.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(d[0] & 0x07) << 29) +
+ (uint32_t(d[4] & 0x07) << 26) +
+ (uint32_t(d[8] & 0x0f) << 22) +
+ (uint32_t(d[16] & 0x3f) << 16) +
+ (uint32_t(d[20] & 0xff) << 8) +
+ (uint32_t(d[24] & 0xff) << 0);
+ }
+ return u;
+ }
+ };
+
+ friend class CuckooCache::cache<TestMapElement, CacheHasher>;
+};
+
+static_assert(sizeof(TestMapElement) == 32, "TestMapElement must be 32 bytes");
+
+// For convenience.
+using CuckooCacheSet =
+ CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher>;
+using CuckooCacheMap =
+ CuckooCache::cache<TestMapElement, TestMapElement::CacheHasher>;
+using TestMapKey = TestMapElement::KeyType;
+
/**
* Test that no values not inserted into the cache are read out of it.
*
@@ -34,8 +108,7 @@
*/
BOOST_AUTO_TEST_CASE(test_cuckoocache_no_fakes) {
SeedInsecureRand(true);
- CuckooCache::cache<CuckooCache::KeyOnly<uint256>, SignatureCacheHasher>
- cc{};
+ CuckooCacheSet cc{};
size_t megabytes = 4;
cc.setup_bytes(megabytes << 20);
for (int x = 0; x < 100000; ++x) {
@@ -44,6 +117,15 @@
for (int x = 0; x < 100000; ++x) {
BOOST_CHECK(!cc.contains(InsecureRand256(), false));
}
+
+ CuckooCacheMap cm{};
+ cm.setup_bytes(megabytes << 20);
+ for (int x = 0; x < 100000; ++x) {
+ cm.insert(TestMapElement(InsecureRand256()));
+ }
+ for (int x = 0; x < 100000; ++x) {
+ BOOST_CHECK(!cm.contains(TestMapKey(InsecureRand256()), false));
+ }
};
/**
@@ -58,12 +140,9 @@
size_t bytes = megabytes * (1 << 20);
set.setup_bytes(bytes);
uint32_t n_insert = static_cast<uint32_t>(load * (bytes / sizeof(uint256)));
- hashes.resize(n_insert);
+ hashes.reserve(n_insert);
for (uint32_t i = 0; i < n_insert; ++i) {
- uint32_t *ptr = (uint32_t *)hashes[i].begin();
- for (uint8_t j = 0; j < 8; ++j) {
- *(ptr++) = InsecureRand32();
- }
+ hashes.emplace_back(InsecureRand256());
}
/**
* We make a copy of the hashes because future optimizations of the
@@ -115,10 +194,12 @@
double HitRateThresh = 0.98;
size_t megabytes = 4;
for (double load = 0.1; load < 2; load *= 2) {
- double hits =
- test_cache<CuckooCache::cache<CuckooCache::KeyOnly<uint256>,
- SignatureCacheHasher>>(megabytes,
- load);
+ double hits = test_cache<CuckooCacheSet>(megabytes, load);
+ BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
+ }
+
+ for (double load = 0.1; load < 2; load *= 2) {
+ double hits = test_cache<CuckooCacheMap>(megabytes, load);
BOOST_CHECK(normalize_hit_rate(hits, load) > HitRateThresh);
}
}
@@ -193,8 +274,8 @@
BOOST_AUTO_TEST_CASE(cuckoocache_erase_ok) {
size_t megabytes = 4;
- test_cache_erase<CuckooCache::cache<CuckooCache::KeyOnly<uint256>,
- SignatureCacheHasher>>(megabytes);
+ test_cache_erase<CuckooCacheSet>(megabytes);
+ test_cache_erase<CuckooCacheMap>(megabytes);
}
template <typename Cache>
@@ -289,9 +370,8 @@
BOOST_AUTO_TEST_CASE(cuckoocache_erase_parallel_ok) {
size_t megabytes = 4;
- test_cache_erase_parallel<CuckooCache::cache<CuckooCache::KeyOnly<uint256>,
- SignatureCacheHasher>>(
- megabytes);
+ test_cache_erase_parallel<CuckooCacheSet>(megabytes);
+ test_cache_erase_parallel<CuckooCacheMap>(megabytes);
}
template <typename Cache> static void test_cache_generations() {
@@ -391,9 +471,65 @@
BOOST_CHECK(double(out_of_tight_tolerance) / double(total) <
max_rate_less_than_tight_hit_rate);
}
+
BOOST_AUTO_TEST_CASE(cuckoocache_generations) {
- test_cache_generations<CuckooCache::cache<CuckooCache::KeyOnly<uint256>,
- SignatureCacheHasher>>();
+ test_cache_generations<CuckooCacheSet>();
+ test_cache_generations<CuckooCacheMap>();
+}
+
+BOOST_AUTO_TEST_CASE(cuckoocache_map_element) {
+ SeedInsecureRand(true);
+
+ // Check the hash is parsed properly.
+ uint256 hash = uint256S(
+ "baadf00dcafebeef00000000bada550ff1ce00000000000000000000deadc0de");
+ uint256 key = uint256S(
+ "baadf00dcafebeef00000000bada550ff1ce00000000000000000000abadba5e");
+ const TestMapElement e(hash);
+
+ BOOST_CHECK_EQUAL(e.getValue(), 0xdeadc0de);
+ BOOST_CHECK(e.getKey() == TestMapElement(key).getKey());
+}
+
+BOOST_AUTO_TEST_CASE(cuckoocache_map) {
+ SeedInsecureRand(true);
+
+ // 4k cache.
+ CuckooCacheMap cm{};
+ cm.setup_bytes(4 * 1024);
+
+ for (int x = 0; x < 100000; ++x) {
+ const TestMapElement e1(InsecureRand256());
+ const TestMapElement e2(e1.getKey(), e1.getValue() ^ 0xbabe);
+
+ BOOST_CHECK(e1.getKey() == e2.getKey());
+ BOOST_CHECK(e1.getValue() != e2.getValue());
+
+ // Insert a KV pair int he map and checks that it is effectively
+ // inserted.
+ BOOST_CHECK(!cm.contains(e1.getKey(), false));
+ cm.insert(e1);
+ BOOST_CHECK(cm.contains(e1.getKey(), false));
+
+ // Check that we recover the proper value from the map.
+ TestMapElement e(e1.getKey(), 0);
+ BOOST_CHECK(cm.get(e, false));
+ BOOST_CHECK(e.getKey() == e1.getKey());
+ BOOST_CHECK(e.getValue() == e1.getValue());
+
+ // Insert without replace will not change the value.
+ e = e2;
+ cm.insert(e2);
+ BOOST_CHECK(cm.get(e, false));
+ BOOST_CHECK(e.getKey() == e1.getKey());
+ BOOST_CHECK(e.getValue() == e1.getValue());
+
+ // Insert and replace.
+ cm.insert(e2, true);
+ BOOST_CHECK(cm.get(e, false));
+ BOOST_CHECK(e.getKey() == e2.getKey());
+ BOOST_CHECK(e.getValue() == e2.getValue());
+ }
}
BOOST_AUTO_TEST_SUITE_END();