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