1 // Copyright (c) 2020 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file.
4
5 #include "hash_table_base.h"
6
7 #include "util/test/test.h"
8
9 #include <algorithm>
10 #include <vector>
11
12 // This unit-test is also used to illustrate how to use HashTableBase<>
13 // in a concrete way. Here, each node is a simple pointer to a Int class
14 // that wraps a simple integer, but also keeps tracks of
15 // construction/destruction steps in global counters. This is used by the
16 // test to verify that operations like copies or moves do not miss or
17 // create allocations/deallocations.
18 //
19 // Because the derived table HashTableTest owns all pointer objects, it
20 // needs to manually create/deallocate them in its destructor, copy/move
21 // constructors and operators, as well as insert()/erase()/clear() methods.
22 //
23 // Finally, iteration support is provided through const_iterator and
24 // begin(), end() methods, which are enough for range-based for loops.
25 //
26
27 // A simple int wrapper class that can also count creation/destruction.
28 class Int {
29 public:
Int(int x)30 explicit Int(int x) : x_(x) { creation_counter++; }
31
Int(const Int & other)32 Int(const Int& other) : x_(other.x_) { creation_counter++; }
33
~Int()34 ~Int() { destruction_counter++; }
35
x()36 int& x() { return x_; }
x() const37 const int& x() const { return x_; }
38
hash() const39 size_t hash() const { return static_cast<size_t>(x_); }
40
ResetCounters()41 static void ResetCounters() {
42 creation_counter = 0;
43 destruction_counter = 0;
44 }
45
46 int x_;
47
48 static size_t creation_counter;
49 static size_t destruction_counter;
50 };
51
52 size_t Int::creation_counter;
53 size_t Int::destruction_counter;
54
55 // A HashTableBase<> node type that contains a simple pointer to a Int value.
56 struct TestHashNode {
57 Int* int_ptr;
58
is_nullTestHashNode59 bool is_null() const { return !int_ptr; }
is_tombstoneTestHashNode60 bool is_tombstone() const { return int_ptr == &kTombstone; }
is_validTestHashNode61 bool is_valid() const { return !is_null() && !is_tombstone(); }
hash_valueTestHashNode62 size_t hash_value() const { return int_ptr->hash(); }
63
64 static Int kTombstone;
65 };
66
67 // Value is irrelevant since only its address is used.
68 Int TestHashNode::kTombstone(-1);
69
70 // TestHashTable derives a HashTableBase<> instantiation to demonstrate
71 // full uses of the template. This includes:
72 //
73 // - Storing a pointer in each node, and managing ownership of pointed
74 // objects explicitly in the destructor, copy/move constructor and
75 // operator, as well as insert() and erase() methods.
76 //
77 // - The internal pointed objects are Int instance, but the TestHashTable
78 // API masks that entirely, instead implementing a simple set of integers,
79 // including iteration support.
80 //
81 // Note that placing the integers directly in the nodes would be much easier,
82 // but would not allow demonstrating how to manage ownership in thedestructor
83 class TestHashTable : public HashTableBase<TestHashNode> {
84 public:
85 using BaseType = HashTableBase<TestHashNode>;
86 using Node = BaseType::Node;
87
88 static_assert(std::is_same<Node, TestHashNode>::value,
89 "HashTableBase<>::Node is not defined properly!");
90
asBaseType()91 BaseType& asBaseType() { return *this; }
asBaseType() const92 const BaseType& asBaseType() const { return *this; }
93
94 TestHashTable() = default;
95
96 // IMPORTANT NOTE: Because the table contains bare owning pointers, we
97 // have to use explicit copy and move constructor/operators for things
98 // to work as expected. This is yet another reason why HashTableBase<>
99 // should only be used with care (preferably with non-owning pointers).
100 //
TestHashTable(const TestHashTable & other)101 TestHashTable(const TestHashTable& other) : BaseType(other) {
102 // Only node (i.e. pointers) are copied by the base type.
103 for (Node& node : ValidNodesRange()) {
104 node.int_ptr = new Int(*node.int_ptr);
105 }
106 }
107
operator =(const TestHashTable & other)108 TestHashTable& operator=(const TestHashTable& other) {
109 if (this != &other) {
110 this->~TestHashTable();
111 new (this) TestHashTable(other);
112 }
113 return *this;
114 }
115
TestHashTable(TestHashTable && other)116 TestHashTable(TestHashTable&& other) noexcept : BaseType(std::move(other)) {}
operator =(TestHashTable && other)117 TestHashTable& operator=(TestHashTable&& other) noexcept {
118 if (this != &other) {
119 this->~TestHashTable();
120 new (this) TestHashTable(std::move(other));
121 }
122 return *this;
123 }
124
~TestHashTable()125 ~TestHashTable() {
126 // Discard all valid Int pointers in the hash table.
127 for (Node& node : ValidNodesRange())
128 delete node.int_ptr;
129 }
130
131 // Return true iff the table contains |x|.
contains(int x) const132 bool contains(int x) const {
133 size_t hash = static_cast<size_t>(x);
134 Node* node = NodeLookup(
135 hash, [&](const Node* node) { return node->int_ptr->x() == x; });
136 return node->is_valid();
137 }
138
139 // Try to insert |x| in the table. Returns true on success, or false if
140 // the value was already in it.
insert(int x)141 bool insert(int x) {
142 size_t hash = static_cast<size_t>(x);
143 Node* node = NodeLookup(
144 hash, [&](const Node* node) { return node->int_ptr->x() == x; });
145 if (node->is_valid())
146 return false;
147
148 node->int_ptr = new Int(x);
149 UpdateAfterInsert();
150 return true;
151 }
152
153 // Try to remove |x| from the table. Return true on success, or false
154 // if the value was not in it.
erase(int x)155 bool erase(int x) {
156 size_t hash = static_cast<size_t>(x);
157 Node* node = NodeLookup(
158 hash, [&](const Node* node) { return node->int_ptr->x() == x; });
159 if (!node->is_valid())
160 return false;
161
162 delete node->int_ptr;
163 node->int_ptr = &TestHashNode::kTombstone;
164 UpdateAfterRemoval();
165 return true;
166 }
167
168 // Remove all items
clear()169 void clear() {
170 // Remove all pointed objects, since NodeClear() will not do it.
171 for (Node& node : ValidNodesRange())
172 delete node.int_ptr;
173
174 NodeClear();
175 }
176
177 // Define const_iterator that point to the integer value instead of the node
178 // of the Int instance to completely hide these from this class' API.
179 struct const_iterator : public BaseType::NodeIterator {
operator *TestHashTable::const_iterator180 const int& operator*() const {
181 return (this->BaseType::NodeIterator::operator*()).int_ptr->x();
182 }
operator ->TestHashTable::const_iterator183 const int* operator->() const { return &(this->operator*()); }
184 };
185
begin() const186 const_iterator begin() const { return {BaseType::NodeBegin()}; }
187
end() const188 const_iterator end() const { return {BaseType::NodeEnd()}; }
189 };
190
TEST(HashTableBaseTest,Construction)191 TEST(HashTableBaseTest, Construction) {
192 Int::ResetCounters();
193 {
194 TestHashTable table;
195 EXPECT_TRUE(table.empty());
196 EXPECT_EQ(table.size(), 0u);
197 EXPECT_EQ(table.begin(), table.end());
198 }
199
200 // No item was created or destroyed.
201 EXPECT_EQ(Int::creation_counter, 0u);
202 EXPECT_EQ(Int::destruction_counter, 0u);
203 }
204
TEST(HashTableBaseTest,InsertionsAndLookups)205 TEST(HashTableBaseTest, InsertionsAndLookups) {
206 Int::ResetCounters();
207 {
208 TestHashTable table;
209 table.insert(1);
210 table.insert(5);
211 table.insert(7);
212
213 EXPECT_FALSE(table.empty());
214 EXPECT_EQ(table.size(), 3u);
215 EXPECT_NE(table.begin(), table.end());
216
217 EXPECT_EQ(Int::creation_counter, 3u);
218 EXPECT_EQ(Int::destruction_counter, 0u);
219
220 EXPECT_FALSE(table.contains(0));
221 EXPECT_TRUE(table.contains(1));
222 EXPECT_FALSE(table.contains(2));
223 EXPECT_FALSE(table.contains(3));
224 EXPECT_TRUE(table.contains(5));
225 EXPECT_FALSE(table.contains(6));
226 EXPECT_TRUE(table.contains(7));
227 EXPECT_FALSE(table.contains(8));
228 }
229
230 EXPECT_EQ(Int::creation_counter, 3u);
231 EXPECT_EQ(Int::destruction_counter, 3u);
232 }
233
TEST(HashTableBaseTest,CopyAssignment)234 TEST(HashTableBaseTest, CopyAssignment) {
235 Int::ResetCounters();
236 {
237 TestHashTable table;
238 table.insert(1);
239 table.insert(5);
240 table.insert(7);
241
242 EXPECT_FALSE(table.empty());
243 EXPECT_EQ(table.size(), 3u);
244
245 TestHashTable table2;
246 EXPECT_TRUE(table2.empty());
247 table2 = table;
248 EXPECT_FALSE(table2.empty());
249 EXPECT_EQ(table2.size(), 3u);
250 EXPECT_FALSE(table.empty());
251 EXPECT_EQ(table.size(), 3u);
252
253 EXPECT_EQ(Int::creation_counter, 6u);
254 EXPECT_EQ(Int::destruction_counter, 0u);
255
256 EXPECT_FALSE(table.contains(0));
257 EXPECT_TRUE(table.contains(1));
258 EXPECT_FALSE(table.contains(2));
259 EXPECT_FALSE(table.contains(3));
260 EXPECT_TRUE(table.contains(5));
261 EXPECT_FALSE(table.contains(6));
262 EXPECT_TRUE(table.contains(7));
263 EXPECT_FALSE(table.contains(8));
264
265 EXPECT_FALSE(table2.contains(0));
266 EXPECT_TRUE(table2.contains(1));
267 EXPECT_FALSE(table2.contains(2));
268 EXPECT_FALSE(table2.contains(3));
269 EXPECT_TRUE(table2.contains(5));
270 EXPECT_FALSE(table2.contains(6));
271 EXPECT_TRUE(table2.contains(7));
272 EXPECT_FALSE(table2.contains(8));
273 }
274
275 EXPECT_EQ(Int::creation_counter, 6u);
276 EXPECT_EQ(Int::destruction_counter, 6u);
277 }
278
TEST(HashTableBaseTest,MoveAssignment)279 TEST(HashTableBaseTest, MoveAssignment) {
280 Int::ResetCounters();
281 {
282 TestHashTable table;
283 table.insert(1);
284 table.insert(5);
285 table.insert(7);
286
287 EXPECT_FALSE(table.empty());
288 EXPECT_EQ(table.size(), 3u);
289
290 TestHashTable table2;
291 EXPECT_TRUE(table2.empty());
292 table2 = std::move(table);
293 EXPECT_FALSE(table2.empty());
294 EXPECT_EQ(table2.size(), 3u);
295 EXPECT_TRUE(table.empty());
296 EXPECT_EQ(table.size(), 0u);
297
298 EXPECT_EQ(Int::creation_counter, 3u);
299 EXPECT_EQ(Int::destruction_counter, 0u);
300
301 EXPECT_FALSE(table2.contains(0));
302 EXPECT_TRUE(table2.contains(1));
303 EXPECT_FALSE(table2.contains(2));
304 EXPECT_FALSE(table2.contains(3));
305 EXPECT_TRUE(table2.contains(5));
306 EXPECT_FALSE(table2.contains(6));
307 EXPECT_TRUE(table2.contains(7));
308 EXPECT_FALSE(table2.contains(8));
309 }
310
311 EXPECT_EQ(Int::creation_counter, 3u);
312 EXPECT_EQ(Int::destruction_counter, 3u);
313 }
314
TEST(HashTableBaseTest,Clear)315 TEST(HashTableBaseTest, Clear) {
316 Int::ResetCounters();
317 {
318 TestHashTable table;
319 table.insert(1);
320 table.insert(5);
321 table.insert(7);
322
323 EXPECT_FALSE(table.empty());
324 EXPECT_EQ(table.size(), 3u);
325
326 table.clear();
327 EXPECT_TRUE(table.empty());
328
329 EXPECT_EQ(Int::creation_counter, 3u);
330 EXPECT_EQ(Int::destruction_counter, 3u);
331 }
332
333 EXPECT_EQ(Int::creation_counter, 3u);
334 EXPECT_EQ(Int::destruction_counter, 3u);
335 }
336
TEST(HashTableBaseTest,Iteration)337 TEST(HashTableBaseTest, Iteration) {
338 TestHashTable table;
339 table.insert(1);
340 table.insert(5);
341 table.insert(7);
342
343 EXPECT_FALSE(table.empty());
344 EXPECT_EQ(table.size(), 3u);
345
346 std::vector<int> values;
347
348 for (const int& x : table)
349 values.push_back(x);
350
351 std::sort(values.begin(), values.end());
352 EXPECT_EQ(values.size(), 3u);
353 EXPECT_EQ(values[0], 1);
354 EXPECT_EQ(values[1], 5);
355 EXPECT_EQ(values[2], 7);
356 }
357