jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, thislooksfun <tlf@thislooks.fun>
3 * Copyright (c) 2023, Jelle Raaijmakers <jelle@gmta.nl>
4 *
5 * SPDX-License-Identifier: BSD-2-Clause
6 */
7
8#include <LibTest/TestCase.h>
9
10#include <AK/DeprecatedString.h>
11#include <AK/HashTable.h>
12#include <AK/NonnullOwnPtr.h>
13
14TEST_CASE(construct)
15{
16 using IntTable = HashTable<int>;
17 EXPECT(IntTable().is_empty());
18 EXPECT_EQ(IntTable().size(), 0u);
19}
20
21TEST_CASE(basic_move)
22{
23 HashTable<int> foo;
24 foo.set(1);
25 EXPECT_EQ(foo.size(), 1u);
26 auto bar = move(foo);
27 EXPECT_EQ(bar.size(), 1u);
28 EXPECT_EQ(foo.size(), 0u);
29 foo = move(bar);
30 EXPECT_EQ(bar.size(), 0u);
31 EXPECT_EQ(foo.size(), 1u);
32}
33
34TEST_CASE(move_is_not_swap)
35{
36 HashTable<int> foo;
37 foo.set(1);
38 HashTable<int> bar;
39 bar.set(2);
40 foo = move(bar);
41 EXPECT(foo.contains(2));
42 EXPECT(!bar.contains(1));
43 EXPECT_EQ(bar.size(), 0u);
44}
45
46TEST_CASE(populate)
47{
48 HashTable<DeprecatedString> strings;
49 strings.set("One");
50 strings.set("Two");
51 strings.set("Three");
52
53 EXPECT_EQ(strings.is_empty(), false);
54 EXPECT_EQ(strings.size(), 3u);
55}
56
57TEST_CASE(range_loop)
58{
59 HashTable<DeprecatedString> strings;
60 EXPECT_EQ(strings.set("One"), AK::HashSetResult::InsertedNewEntry);
61 EXPECT_EQ(strings.set("Two"), AK::HashSetResult::InsertedNewEntry);
62 EXPECT_EQ(strings.set("Three"), AK::HashSetResult::InsertedNewEntry);
63
64 int loop_counter = 0;
65 for (auto& it : strings) {
66 EXPECT_EQ(it.is_null(), false);
67 ++loop_counter;
68 }
69 EXPECT_EQ(loop_counter, 3);
70}
71
72TEST_CASE(table_remove)
73{
74 HashTable<DeprecatedString> strings;
75 EXPECT_EQ(strings.set("One"), AK::HashSetResult::InsertedNewEntry);
76 EXPECT_EQ(strings.set("Two"), AK::HashSetResult::InsertedNewEntry);
77 EXPECT_EQ(strings.set("Three"), AK::HashSetResult::InsertedNewEntry);
78
79 EXPECT_EQ(strings.remove("One"), true);
80 EXPECT_EQ(strings.size(), 2u);
81 EXPECT(strings.find("One") == strings.end());
82
83 EXPECT_EQ(strings.remove("Three"), true);
84 EXPECT_EQ(strings.size(), 1u);
85 EXPECT(strings.find("Three") == strings.end());
86 EXPECT(strings.find("Two") != strings.end());
87}
88
89TEST_CASE(remove_all_matching)
90{
91 HashTable<int> ints;
92
93 ints.set(1);
94 ints.set(2);
95 ints.set(3);
96 ints.set(4);
97
98 EXPECT_EQ(ints.size(), 4u);
99
100 EXPECT_EQ(ints.remove_all_matching([&](int value) { return value > 2; }), true);
101 EXPECT_EQ(ints.remove_all_matching([&](int) { return false; }), false);
102
103 EXPECT_EQ(ints.size(), 2u);
104
105 EXPECT(ints.contains(1));
106 EXPECT(ints.contains(2));
107
108 EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), true);
109
110 EXPECT(ints.is_empty());
111
112 EXPECT_EQ(ints.remove_all_matching([&](int) { return true; }), false);
113}
114
115TEST_CASE(case_insensitive)
116{
117 HashTable<DeprecatedString, CaseInsensitiveStringTraits> casetable;
118 EXPECT_EQ(DeprecatedString("nickserv").to_lowercase(), DeprecatedString("NickServ").to_lowercase());
119 EXPECT_EQ(casetable.set("nickserv"), AK::HashSetResult::InsertedNewEntry);
120 EXPECT_EQ(casetable.set("NickServ"), AK::HashSetResult::ReplacedExistingEntry);
121 EXPECT_EQ(casetable.size(), 1u);
122}
123
124TEST_CASE(many_strings)
125{
126 HashTable<DeprecatedString> strings;
127 for (int i = 0; i < 999; ++i) {
128 EXPECT_EQ(strings.set(DeprecatedString::number(i)), AK::HashSetResult::InsertedNewEntry);
129 }
130 EXPECT_EQ(strings.size(), 999u);
131 for (int i = 0; i < 999; ++i) {
132 EXPECT_EQ(strings.remove(DeprecatedString::number(i)), true);
133 }
134 EXPECT_EQ(strings.is_empty(), true);
135}
136
137TEST_CASE(many_collisions)
138{
139 struct StringCollisionTraits : public GenericTraits<DeprecatedString> {
140 static unsigned hash(DeprecatedString const&) { return 0; }
141 };
142
143 HashTable<DeprecatedString, StringCollisionTraits> strings;
144 for (int i = 0; i < 999; ++i) {
145 EXPECT_EQ(strings.set(DeprecatedString::number(i)), AK::HashSetResult::InsertedNewEntry);
146 }
147
148 EXPECT_EQ(strings.set("foo"), AK::HashSetResult::InsertedNewEntry);
149 EXPECT_EQ(strings.size(), 1000u);
150
151 for (int i = 0; i < 999; ++i) {
152 EXPECT_EQ(strings.remove(DeprecatedString::number(i)), true);
153 }
154
155 EXPECT(strings.find("foo") != strings.end());
156}
157
158TEST_CASE(space_reuse)
159{
160 struct StringCollisionTraits : public GenericTraits<DeprecatedString> {
161 static unsigned hash(DeprecatedString const&) { return 0; }
162 };
163
164 HashTable<DeprecatedString, StringCollisionTraits> strings;
165
166 // Add a few items to allow it to do initial resizing.
167 EXPECT_EQ(strings.set("0"), AK::HashSetResult::InsertedNewEntry);
168 for (int i = 1; i < 5; ++i) {
169 EXPECT_EQ(strings.set(DeprecatedString::number(i)), AK::HashSetResult::InsertedNewEntry);
170 EXPECT_EQ(strings.remove(DeprecatedString::number(i - 1)), true);
171 }
172
173 auto capacity = strings.capacity();
174
175 for (int i = 5; i < 999; ++i) {
176 EXPECT_EQ(strings.set(DeprecatedString::number(i)), AK::HashSetResult::InsertedNewEntry);
177 EXPECT_EQ(strings.remove(DeprecatedString::number(i - 1)), true);
178 }
179
180 EXPECT_EQ(strings.capacity(), capacity);
181}
182
183TEST_CASE(basic_remove)
184{
185 HashTable<int> table;
186 table.set(1);
187 table.set(2);
188 table.set(3);
189
190 EXPECT_EQ(table.remove(3), true);
191 EXPECT_EQ(table.remove(3), false);
192 EXPECT_EQ(table.size(), 2u);
193
194 EXPECT_EQ(table.remove(1), true);
195 EXPECT_EQ(table.remove(1), false);
196 EXPECT_EQ(table.size(), 1u);
197
198 EXPECT_EQ(table.remove(2), true);
199 EXPECT_EQ(table.remove(2), false);
200 EXPECT_EQ(table.size(), 0u);
201}
202
203TEST_CASE(basic_contains)
204{
205 HashTable<int> table;
206 table.set(1);
207 table.set(2);
208 table.set(3);
209
210 EXPECT_EQ(table.contains(1), true);
211 EXPECT_EQ(table.contains(2), true);
212 EXPECT_EQ(table.contains(3), true);
213 EXPECT_EQ(table.contains(4), false);
214
215 EXPECT_EQ(table.remove(3), true);
216 EXPECT_EQ(table.contains(3), false);
217 EXPECT_EQ(table.contains(1), true);
218 EXPECT_EQ(table.contains(2), true);
219
220 EXPECT_EQ(table.remove(2), true);
221 EXPECT_EQ(table.contains(2), false);
222 EXPECT_EQ(table.contains(3), false);
223 EXPECT_EQ(table.contains(1), true);
224
225 EXPECT_EQ(table.remove(1), true);
226 EXPECT_EQ(table.contains(1), false);
227}
228
229TEST_CASE(capacity_leak)
230{
231 HashTable<int> table;
232 for (size_t i = 0; i < 10000; ++i) {
233 table.set(i);
234 table.remove(i);
235 }
236 EXPECT(table.capacity() < 100u);
237}
238
239TEST_CASE(non_trivial_type_table)
240{
241 HashTable<NonnullOwnPtr<int>> table;
242
243 table.set(make<int>(3));
244 table.set(make<int>(11));
245
246 for (int i = 0; i < 1'000; ++i) {
247 table.set(make<int>(-i));
248 }
249 for (int i = 0; i < 10'000; ++i) {
250 table.set(make<int>(i));
251 table.remove(make<int>(i));
252 }
253
254 EXPECT_EQ(table.remove_all_matching([&](auto&) { return true; }), true);
255 EXPECT(table.is_empty());
256 EXPECT_EQ(table.remove_all_matching([&](auto&) { return true; }), false);
257}
258
259TEST_CASE(floats)
260{
261 HashTable<float> table;
262 table.set(0);
263 table.set(1.0f);
264 table.set(2.0f);
265 EXPECT_EQ(table.size(), 3u);
266 EXPECT(table.contains(0));
267 EXPECT(table.contains(1.0f));
268 EXPECT(table.contains(2.0f));
269}
270
271TEST_CASE(doubles)
272{
273 HashTable<double> table;
274 table.set(0);
275 table.set(1.0);
276 table.set(2.0);
277 EXPECT_EQ(table.size(), 3u);
278 EXPECT(table.contains(0));
279 EXPECT(table.contains(1.0));
280 EXPECT(table.contains(2.0));
281}
282
283TEST_CASE(reinsertion)
284{
285 OrderedHashTable<DeprecatedString> map;
286 map.set("ytidb::LAST_RESULT_ENTRY_KEY");
287 map.set("__sak");
288 map.remove("__sak");
289 map.set("__sak");
290}
291
292TEST_CASE(clear_with_capacity_when_empty)
293{
294 HashTable<int> map;
295 map.clear_with_capacity();
296 map.set(0);
297 map.set(1);
298 VERIFY(map.size() == 2);
299}
300
301TEST_CASE(iterator_removal)
302{
303 HashTable<int> map;
304 map.set(0);
305 map.set(1);
306
307 auto it = map.begin();
308 map.remove(it);
309 EXPECT_EQ(it, map.end());
310 EXPECT_EQ(map.size(), 1u);
311}
312
313TEST_CASE(ordered_insertion_and_deletion)
314{
315 OrderedHashTable<int> table;
316 EXPECT_EQ(table.set(0), HashSetResult::InsertedNewEntry);
317 EXPECT_EQ(table.set(1), HashSetResult::InsertedNewEntry);
318 EXPECT_EQ(table.set(2), HashSetResult::InsertedNewEntry);
319 EXPECT_EQ(table.set(3), HashSetResult::InsertedNewEntry);
320 EXPECT_EQ(table.size(), 4u);
321
322 auto expect_table = [](OrderedHashTable<int>& table, Span<int> values) {
323 auto index = 0u;
324 for (auto it = table.begin(); it != table.end(); ++it, ++index) {
325 EXPECT_EQ(*it, values[index]);
326 EXPECT(table.contains(values[index]));
327 }
328 };
329
330 expect_table(table, Array<int, 4> { 0, 1, 2, 3 });
331
332 EXPECT(table.remove(0));
333 EXPECT(table.remove(2));
334 EXPECT(!table.remove(4));
335 EXPECT_EQ(table.size(), 2u);
336
337 expect_table(table, Array<int, 2> { 1, 3 });
338}
339
340TEST_CASE(ordered_deletion_and_reinsertion)
341{
342 OrderedHashTable<int> table;
343 table.set(1);
344 table.set(3);
345 table.remove(1);
346 EXPECT_EQ(table.size(), 1u);
347
348 // By adding 1 again but this time in a different position, we
349 // test whether the bucket's neighbours are reset properly.
350 table.set(1);
351 EXPECT_EQ(table.size(), 2u);
352
353 auto it = table.begin();
354 EXPECT_EQ(*it, 3);
355 ++it;
356 EXPECT_EQ(*it, 1);
357 ++it;
358 EXPECT_EQ(it, table.end());
359}
360
361TEST_CASE(ordered_take_last)
362{
363 OrderedHashTable<int> table;
364 table.set(1);
365 table.set(2);
366 table.set(3);
367
368 EXPECT_EQ(table.take_last(), 3);
369 EXPECT_EQ(table.take_last(), 2);
370 EXPECT_EQ(table.take_last(), 1);
371 EXPECT(table.is_empty());
372}
373
374TEST_CASE(ordered_iterator_removal)
375{
376 OrderedHashTable<int> map;
377 map.set(0);
378 map.set(1);
379
380 auto it = map.begin();
381 map.remove(it);
382 EXPECT_EQ(it, map.end());
383 EXPECT_EQ(map.size(), 1u);
384}
385
386TEST_CASE(ordered_remove_from_head)
387{
388 OrderedHashTable<int> map;
389 map.set(1);
390 map.set(2);
391 map.set(3);
392 map.set(4);
393 map.set(5);
394 map.set(6);
395
396 EXPECT_EQ(map.size(), 6u);
397
398 auto it = map.begin();
399 map.remove(it);
400 it = map.begin();
401 map.remove(it);
402 it = map.begin();
403 map.remove(it);
404 it = map.begin();
405 map.remove(it);
406 it = map.begin();
407 map.remove(it);
408 it = map.begin();
409 map.remove(it);
410
411 EXPECT_EQ(map.size(), 0u);
412}