]>
Commit | Line | Data |
---|---|---|
7c673cae | 1 | // Copyright (c) 2013, Facebook, Inc. All rights reserved. |
11fdf7f2 TL |
2 | // This source code is licensed under both the GPLv2 (found in the |
3 | // COPYING file in the root directory) and Apache 2.0 License | |
4 | // (found in the LICENSE.Apache file in the root directory). | |
7c673cae FG |
5 | // |
6 | #include <stdlib.h> | |
7 | #include <iostream> | |
8 | #include <set> | |
9 | #include <string> | |
10 | ||
11 | #include "db/db_test_util.h" | |
f67539c2 TL |
12 | #include "memory/arena.h" |
13 | #include "test_util/testharness.h" | |
7c673cae | 14 | #include "util/random.h" |
7c673cae FG |
15 | #include "utilities/persistent_cache/hash_table.h" |
16 | #include "utilities/persistent_cache/hash_table_evictable.h" | |
17 | ||
18 | #ifndef ROCKSDB_LITE | |
19 | ||
f67539c2 | 20 | namespace ROCKSDB_NAMESPACE { |
7c673cae FG |
21 | |
22 | struct HashTableTest : public testing::Test { | |
494da23a | 23 | ~HashTableTest() override { map_.Clear(&HashTableTest::ClearNode); } |
7c673cae FG |
24 | |
25 | struct Node { | |
26 | Node() {} | |
27 | explicit Node(const uint64_t key, const std::string& val = std::string()) | |
28 | : key_(key), val_(val) {} | |
29 | ||
30 | uint64_t key_ = 0; | |
31 | std::string val_; | |
32 | }; | |
33 | ||
34 | struct Equal { | |
35 | bool operator()(const Node& lhs, const Node& rhs) { | |
36 | return lhs.key_ == rhs.key_; | |
37 | } | |
38 | }; | |
39 | ||
40 | struct Hash { | |
41 | uint64_t operator()(const Node& node) { | |
42 | return std::hash<uint64_t>()(node.key_); | |
43 | } | |
44 | }; | |
45 | ||
11fdf7f2 | 46 | static void ClearNode(Node /*node*/) {} |
7c673cae FG |
47 | |
48 | HashTable<Node, Hash, Equal> map_; | |
49 | }; | |
50 | ||
51 | struct EvictableHashTableTest : public testing::Test { | |
494da23a TL |
52 | ~EvictableHashTableTest() override { |
53 | map_.Clear(&EvictableHashTableTest::ClearNode); | |
54 | } | |
7c673cae FG |
55 | |
56 | struct Node : LRUElement<Node> { | |
57 | Node() {} | |
58 | explicit Node(const uint64_t key, const std::string& val = std::string()) | |
59 | : key_(key), val_(val) {} | |
60 | ||
61 | uint64_t key_ = 0; | |
62 | std::string val_; | |
63 | std::atomic<uint32_t> refs_{0}; | |
64 | }; | |
65 | ||
66 | struct Equal { | |
67 | bool operator()(const Node* lhs, const Node* rhs) { | |
68 | return lhs->key_ == rhs->key_; | |
69 | } | |
70 | }; | |
71 | ||
72 | struct Hash { | |
73 | uint64_t operator()(const Node* node) { | |
74 | return std::hash<uint64_t>()(node->key_); | |
75 | } | |
76 | }; | |
77 | ||
11fdf7f2 | 78 | static void ClearNode(Node* /*node*/) {} |
7c673cae FG |
79 | |
80 | EvictableHashTable<Node, Hash, Equal> map_; | |
81 | }; | |
82 | ||
83 | TEST_F(HashTableTest, TestInsert) { | |
84 | const uint64_t max_keys = 1024 * 1024; | |
85 | ||
86 | // insert | |
87 | for (uint64_t k = 0; k < max_keys; ++k) { | |
88 | map_.Insert(Node(k, std::string(1000, k % 255))); | |
89 | } | |
90 | ||
91 | // verify | |
92 | for (uint64_t k = 0; k < max_keys; ++k) { | |
93 | Node val; | |
94 | port::RWMutex* rlock = nullptr; | |
95 | assert(map_.Find(Node(k), &val, &rlock)); | |
96 | rlock->ReadUnlock(); | |
97 | assert(val.val_ == std::string(1000, k % 255)); | |
98 | } | |
99 | } | |
100 | ||
101 | TEST_F(HashTableTest, TestErase) { | |
102 | const uint64_t max_keys = 1024 * 1024; | |
103 | // insert | |
104 | for (uint64_t k = 0; k < max_keys; ++k) { | |
105 | map_.Insert(Node(k, std::string(1000, k % 255))); | |
106 | } | |
107 | ||
108 | auto rand = Random64(time(nullptr)); | |
109 | // erase a few keys randomly | |
110 | std::set<uint64_t> erased; | |
111 | for (int i = 0; i < 1024; ++i) { | |
112 | uint64_t k = rand.Next() % max_keys; | |
113 | if (erased.find(k) != erased.end()) { | |
114 | continue; | |
115 | } | |
116 | assert(map_.Erase(Node(k), /*ret=*/nullptr)); | |
117 | erased.insert(k); | |
118 | } | |
119 | ||
120 | // verify | |
121 | for (uint64_t k = 0; k < max_keys; ++k) { | |
122 | Node val; | |
123 | port::RWMutex* rlock = nullptr; | |
124 | bool status = map_.Find(Node(k), &val, &rlock); | |
125 | if (erased.find(k) == erased.end()) { | |
126 | assert(status); | |
127 | rlock->ReadUnlock(); | |
128 | assert(val.val_ == std::string(1000, k % 255)); | |
129 | } else { | |
130 | assert(!status); | |
131 | } | |
132 | } | |
133 | } | |
134 | ||
135 | TEST_F(EvictableHashTableTest, TestEvict) { | |
136 | const uint64_t max_keys = 1024 * 1024; | |
137 | ||
138 | // insert | |
139 | for (uint64_t k = 0; k < max_keys; ++k) { | |
140 | map_.Insert(new Node(k, std::string(1000, k % 255))); | |
141 | } | |
142 | ||
143 | // verify | |
144 | for (uint64_t k = 0; k < max_keys; ++k) { | |
145 | Node* val = map_.Evict(); | |
146 | // unfortunately we can't predict eviction value since it is from any one of | |
147 | // the lock stripe | |
148 | assert(val); | |
149 | assert(val->val_ == std::string(1000, val->key_ % 255)); | |
150 | delete val; | |
151 | } | |
152 | } | |
153 | ||
f67539c2 | 154 | } // namespace ROCKSDB_NAMESPACE |
7c673cae FG |
155 | #endif |
156 | ||
157 | int main(int argc, char** argv) { | |
158 | ::testing::InitGoogleTest(&argc, argv); | |
159 | return RUN_ALL_TESTS(); | |
160 | } |