| // Copyright (c) 2013, Facebook, Inc. All rights reserved. |
| // This source code is licensed under both the GPLv2 (found in the |
| // COPYING file in the root directory) and Apache 2.0 License |
| // (found in the LICENSE.Apache file in the root directory). |
| // |
| #include <stdlib.h> |
| #include <iostream> |
| #include <set> |
| #include <string> |
| |
| #include "db/db_test_util.h" |
| #include "util/arena.h" |
| #include "util/random.h" |
| #include "util/testharness.h" |
| #include "utilities/persistent_cache/hash_table.h" |
| #include "utilities/persistent_cache/hash_table_evictable.h" |
| |
| #ifndef ROCKSDB_LITE |
| |
| namespace rocksdb { |
| |
| struct HashTableTest : public testing::Test { |
| ~HashTableTest() { map_.Clear(&HashTableTest::ClearNode); } |
| |
| struct Node { |
| Node() {} |
| explicit Node(const uint64_t key, const std::string& val = std::string()) |
| : key_(key), val_(val) {} |
| |
| uint64_t key_ = 0; |
| std::string val_; |
| }; |
| |
| struct Equal { |
| bool operator()(const Node& lhs, const Node& rhs) { |
| return lhs.key_ == rhs.key_; |
| } |
| }; |
| |
| struct Hash { |
| uint64_t operator()(const Node& node) { |
| return std::hash<uint64_t>()(node.key_); |
| } |
| }; |
| |
| static void ClearNode(Node node) {} |
| |
| HashTable<Node, Hash, Equal> map_; |
| }; |
| |
| struct EvictableHashTableTest : public testing::Test { |
| ~EvictableHashTableTest() { map_.Clear(&EvictableHashTableTest::ClearNode); } |
| |
| struct Node : LRUElement<Node> { |
| Node() {} |
| explicit Node(const uint64_t key, const std::string& val = std::string()) |
| : key_(key), val_(val) {} |
| |
| uint64_t key_ = 0; |
| std::string val_; |
| std::atomic<uint32_t> refs_{0}; |
| }; |
| |
| struct Equal { |
| bool operator()(const Node* lhs, const Node* rhs) { |
| return lhs->key_ == rhs->key_; |
| } |
| }; |
| |
| struct Hash { |
| uint64_t operator()(const Node* node) { |
| return std::hash<uint64_t>()(node->key_); |
| } |
| }; |
| |
| static void ClearNode(Node* node) {} |
| |
| EvictableHashTable<Node, Hash, Equal> map_; |
| }; |
| |
| TEST_F(HashTableTest, TestInsert) { |
| const uint64_t max_keys = 1024 * 1024; |
| |
| // insert |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| map_.Insert(Node(k, std::string(1000, k % 255))); |
| } |
| |
| // verify |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| Node val; |
| port::RWMutex* rlock = nullptr; |
| assert(map_.Find(Node(k), &val, &rlock)); |
| rlock->ReadUnlock(); |
| assert(val.val_ == std::string(1000, k % 255)); |
| } |
| } |
| |
| TEST_F(HashTableTest, TestErase) { |
| const uint64_t max_keys = 1024 * 1024; |
| // insert |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| map_.Insert(Node(k, std::string(1000, k % 255))); |
| } |
| |
| auto rand = Random64(time(nullptr)); |
| // erase a few keys randomly |
| std::set<uint64_t> erased; |
| for (int i = 0; i < 1024; ++i) { |
| uint64_t k = rand.Next() % max_keys; |
| if (erased.find(k) != erased.end()) { |
| continue; |
| } |
| assert(map_.Erase(Node(k), /*ret=*/nullptr)); |
| erased.insert(k); |
| } |
| |
| // verify |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| Node val; |
| port::RWMutex* rlock = nullptr; |
| bool status = map_.Find(Node(k), &val, &rlock); |
| if (erased.find(k) == erased.end()) { |
| assert(status); |
| rlock->ReadUnlock(); |
| assert(val.val_ == std::string(1000, k % 255)); |
| } else { |
| assert(!status); |
| } |
| } |
| } |
| |
| TEST_F(EvictableHashTableTest, TestEvict) { |
| const uint64_t max_keys = 1024 * 1024; |
| |
| // insert |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| map_.Insert(new Node(k, std::string(1000, k % 255))); |
| } |
| |
| // verify |
| for (uint64_t k = 0; k < max_keys; ++k) { |
| Node* val = map_.Evict(); |
| // unfortunately we can't predict eviction value since it is from any one of |
| // the lock stripe |
| assert(val); |
| assert(val->val_ == std::string(1000, val->key_ % 255)); |
| delete val; |
| } |
| } |
| |
| } // namespace rocksdb |
| #endif |
| |
| int main(int argc, char** argv) { |
| ::testing::InitGoogleTest(&argc, argv); |
| return RUN_ALL_TESTS(); |
| } |