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