Debian Codegraph @

src/kj/table-test.c++

raw
1 // Copyright (c) 2018 Kenton Varda and contributors
2 // Licensed under the MIT License:
3 //
4 // Permission is hereby granted, free of charge, to any person obtaining a copy
5 // of this software and associated documentation files (the "Software"), to deal
6 // in the Software without restriction, including without limitation the rights
7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
8 // copies of the Software, and to permit persons to whom the Software is
9 // furnished to do so, subject to the following conditions:
10 //
11 // The above copyright notice and this permission notice shall be included in
12 // all copies or substantial portions of the Software.
13 //
14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
20 // THE SOFTWARE.
21
22 #include "table.h"
23 #include <kj/test.h>
24 #include <set>
25 #include <unordered_set>
26 #include "hash.h"
27 #include "time.h"
28 #include <stdlib.h>
29
30 namespace kj {
31 namespace _ {
32 namespace {
33
34 #if defined(KJ_DEBUG) && !__OPTIMIZE__
35 static constexpr uint MEDIUM_PRIME = 619;
36 static constexpr uint BIG_PRIME = 6143;
37 #else
38 static constexpr uint MEDIUM_PRIME = 6143;
39 static constexpr uint BIG_PRIME = 101363;
40 #endif
41 // Some of the tests build large tables. These numbers are used as the table sizes. We use primes
42 // to avoid any unintended aliasing affects -- this is probably just paranoia, but why not?
43 //
44 // We use smaller values for debug builds to keep runtime down.
45
46 KJ_TEST("_::tryReserveSize() works") {
47 {
48 Vector<int> vec;
49 tryReserveSize(vec, "foo"_kj);
50 KJ_EXPECT(vec.capacity() == 4); // Vectors always grow by powers of two.
51 }
52 {
53 Vector<int> vec;
54 tryReserveSize(vec, 123);
55 KJ_EXPECT(vec.capacity() == 0);
56 }
57 }
58
59 class StringHasher {
60 public:
61 StringPtr keyForRow(StringPtr s) const { return s; }
62
63 bool matches(StringPtr a, StringPtr b) const {
64 return a == b;
65 }
66 uint hashCode(StringPtr str) const {
67 return kj::hashCode(str);
68 }
69 };
70
71 KJ_TEST("simple table") {
72 Table<StringPtr, HashIndex<StringHasher>> table;
73
74 KJ_EXPECT(table.find("foo") == nullptr);
75
76 KJ_EXPECT(table.size() == 0);
77 KJ_EXPECT(table.insert("foo") == "foo");
78 KJ_EXPECT(table.size() == 1);
79 KJ_EXPECT(table.insert("bar") == "bar");
80 KJ_EXPECT(table.size() == 2);
81
82 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("foo")) == "foo");
83 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
84 KJ_EXPECT(table.find("fop") == nullptr);
85 KJ_EXPECT(table.find("baq") == nullptr);
86
87 {
88 StringPtr& ref = table.insert("baz");
89 KJ_EXPECT(ref == "baz");
90 StringPtr& ref2 = KJ_ASSERT_NONNULL(table.find("baz"));
91 KJ_EXPECT(&ref == &ref2);
92 }
93
94 KJ_EXPECT(table.size() == 3);
95
96 {
97 auto iter = table.begin();
98 KJ_EXPECT(*iter++ == "foo");
99 KJ_EXPECT(*iter++ == "bar");
100 KJ_EXPECT(*iter++ == "baz");
101 KJ_EXPECT(iter == table.end());
102 }
103
104 KJ_EXPECT(table.eraseMatch("foo"));
105 KJ_EXPECT(table.size() == 2);
106 KJ_EXPECT(table.find("foo") == nullptr);
107 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
108 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("baz")) == "baz");
109
110 {
111 auto iter = table.begin();
112 KJ_EXPECT(*iter++ == "baz");
113 KJ_EXPECT(*iter++ == "bar");
114 KJ_EXPECT(iter == table.end());
115 }
116
117 {
118 auto& row = table.upsert("qux", [&](StringPtr&, StringPtr&&) {
119 KJ_FAIL_ASSERT("shouldn't get here");
120 });
121
122 auto copy = kj::str("qux");
123 table.upsert(StringPtr(copy), [&](StringPtr& existing, StringPtr&& param) {
124 KJ_EXPECT(param.begin() == copy.begin());
125 KJ_EXPECT(&existing == &row);
126 });
127
128 auto& found = KJ_ASSERT_NONNULL(table.find("qux"));
129 KJ_EXPECT(&found == &row);
130 }
131
132 StringPtr STRS[] = { "corge"_kj, "grault"_kj, "garply"_kj };
133 table.insertAll(ArrayPtr<StringPtr>(STRS));
134 KJ_EXPECT(table.size() == 6);
135 KJ_EXPECT(table.find("corge") != nullptr);
136 KJ_EXPECT(table.find("grault") != nullptr);
137 KJ_EXPECT(table.find("garply") != nullptr);
138
139 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table", table.insert("bar"));
140
141 KJ_EXPECT(table.size() == 6);
142
143 KJ_EXPECT(table.insert("baa") == "baa");
144
145 KJ_EXPECT(table.eraseAll([](StringPtr s) { return s.startsWith("ba"); }) == 3);
146 KJ_EXPECT(table.size() == 4);
147
148 {
149 auto iter = table.begin();
150 KJ_EXPECT(*iter++ == "garply");
151 KJ_EXPECT(*iter++ == "grault");
152 KJ_EXPECT(*iter++ == "qux");
153 KJ_EXPECT(*iter++ == "corge");
154 KJ_EXPECT(iter == table.end());
155 }
156
157 auto& graultRow = table.begin()[1];
158 kj::StringPtr origGrault = graultRow;
159
160 KJ_EXPECT(&table.findOrCreate("grault",
161 [&]() -> kj::StringPtr { KJ_FAIL_ASSERT("shouldn't have called this"); }) == &graultRow);
162 KJ_EXPECT(graultRow.begin() == origGrault.begin());
163 KJ_EXPECT(&KJ_ASSERT_NONNULL(table.find("grault")) == &graultRow);
164 KJ_EXPECT(table.find("waldo") == nullptr);
165 KJ_EXPECT(table.size() == 4);
166
167 kj::String searchWaldo = kj::str("waldo");
168 kj::String insertWaldo = kj::str("waldo");
169
170 auto& waldo = table.findOrCreate(searchWaldo,
171 [&]() -> kj::StringPtr { return insertWaldo; });
172 KJ_EXPECT(waldo == "waldo");
173 KJ_EXPECT(waldo.begin() == insertWaldo.begin());
174 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("grault")) == "grault");
175 KJ_EXPECT(&KJ_ASSERT_NONNULL(table.find("waldo")) == &waldo);
176 KJ_EXPECT(table.size() == 5);
177
178 {
179 auto iter = table.begin();
180 KJ_EXPECT(*iter++ == "garply");
181 KJ_EXPECT(*iter++ == "grault");
182 KJ_EXPECT(*iter++ == "qux");
183 KJ_EXPECT(*iter++ == "corge");
184 KJ_EXPECT(*iter++ == "waldo");
185 KJ_EXPECT(iter == table.end());
186 }
187 }
188
189 class BadHasher {
190 // String hash that always returns the same hash code. This should not affect correctness, only
191 // performance.
192 public:
193 StringPtr keyForRow(StringPtr s) const { return s; }
194
195 bool matches(StringPtr a, StringPtr b) const {
196 return a == b;
197 }
198 uint hashCode(StringPtr str) const {
199 return 1234;
200 }
201 };
202
203 KJ_TEST("hash tables when hash is always same") {
204 Table<StringPtr, HashIndex<BadHasher>> table;
205
206 KJ_EXPECT(table.size() == 0);
207 KJ_EXPECT(table.insert("foo") == "foo");
208 KJ_EXPECT(table.size() == 1);
209 KJ_EXPECT(table.insert("bar") == "bar");
210 KJ_EXPECT(table.size() == 2);
211
212 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("foo")) == "foo");
213 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
214 KJ_EXPECT(table.find("fop") == nullptr);
215 KJ_EXPECT(table.find("baq") == nullptr);
216
217 {
218 StringPtr& ref = table.insert("baz");
219 KJ_EXPECT(ref == "baz");
220 StringPtr& ref2 = KJ_ASSERT_NONNULL(table.find("baz"));
221 KJ_EXPECT(&ref == &ref2);
222 }
223
224 KJ_EXPECT(table.size() == 3);
225
226 {
227 auto iter = table.begin();
228 KJ_EXPECT(*iter++ == "foo");
229 KJ_EXPECT(*iter++ == "bar");
230 KJ_EXPECT(*iter++ == "baz");
231 KJ_EXPECT(iter == table.end());
232 }
233
234 KJ_EXPECT(table.eraseMatch("foo"));
235 KJ_EXPECT(table.size() == 2);
236 KJ_EXPECT(table.find("foo") == nullptr);
237 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
238 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("baz")) == "baz");
239
240 {
241 auto iter = table.begin();
242 KJ_EXPECT(*iter++ == "baz");
243 KJ_EXPECT(*iter++ == "bar");
244 KJ_EXPECT(iter == table.end());
245 }
246
247 {
248 auto& row = table.upsert("qux", [&](StringPtr&, StringPtr&&) {
249 KJ_FAIL_ASSERT("shouldn't get here");
250 });
251
252 auto copy = kj::str("qux");
253 table.upsert(StringPtr(copy), [&](StringPtr& existing, StringPtr&& param) {
254 KJ_EXPECT(param.begin() == copy.begin());
255 KJ_EXPECT(&existing == &row);
256 });
257
258 auto& found = KJ_ASSERT_NONNULL(table.find("qux"));
259 KJ_EXPECT(&found == &row);
260 }
261
262 StringPtr STRS[] = { "corge"_kj, "grault"_kj, "garply"_kj };
263 table.insertAll(ArrayPtr<StringPtr>(STRS));
264 KJ_EXPECT(table.size() == 6);
265 KJ_EXPECT(table.find("corge") != nullptr);
266 KJ_EXPECT(table.find("grault") != nullptr);
267 KJ_EXPECT(table.find("garply") != nullptr);
268
269 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table", table.insert("bar"));
270 }
271
272 class IntHasher {
273 // Dumb integer hasher that just returns the integer itself.
274 public:
275 uint keyForRow(uint i) const { return i; }
276
277 bool matches(uint a, uint b) const {
278 return a == b;
279 }
280 uint hashCode(uint i) const {
281 return i;
282 }
283 };
284
285 KJ_TEST("HashIndex with many erasures doesn't keep growing") {
286 HashIndex<IntHasher> index;
287
288 kj::ArrayPtr<uint> rows = nullptr;
289
290 for (uint i: kj::zeroTo(1000000)) {
291 KJ_ASSERT(index.insert(rows, 0, i) == nullptr);
292 index.erase(rows, 0, i);
293 }
294
295 KJ_ASSERT(index.capacity() < 10);
296 }
297
298 struct SiPair {
299 kj::StringPtr str;
300 uint i;
301
302 inline bool operator==(SiPair other) const {
303 return str == other.str && i == other.i;
304 }
305 };
306
307 class SiPairStringHasher {
308 public:
309 StringPtr keyForRow(SiPair s) const { return s.str; }
310
311 bool matches(SiPair a, StringPtr b) const {
312 return a.str == b;
313 }
314 uint hashCode(StringPtr str) const {
315 return inner.hashCode(str);
316 }
317
318 private:
319 StringHasher inner;
320 };
321
322 class SiPairIntHasher {
323 public:
324 uint keyForRow(SiPair s) const { return s.i; }
325
326 bool matches(SiPair a, uint b) const {
327 return a.i == b;
328 }
329 uint hashCode(uint i) const {
330 return i;
331 }
332 };
333
334 KJ_TEST("double-index table") {
335 Table<SiPair, HashIndex<SiPairStringHasher>, HashIndex<SiPairIntHasher>> table;
336
337 KJ_EXPECT(table.size() == 0);
338 KJ_EXPECT(table.insert({"foo", 123}) == (SiPair {"foo", 123}));
339 KJ_EXPECT(table.size() == 1);
340 KJ_EXPECT(table.insert({"bar", 456}) == (SiPair {"bar", 456}));
341 KJ_EXPECT(table.size() == 2);
342
343 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<HashIndex<SiPairStringHasher>>("foo")) ==
344 (SiPair {"foo", 123}));
345 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<HashIndex<SiPairIntHasher>>(123)) ==
346 (SiPair {"foo", 123}));
347
348 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("foo")) == (SiPair {"foo", 123}));
349 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(123)) == (SiPair {"foo", 123}));
350
351 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table", table.insert({"foo", 111}));
352 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table", table.insert({"qux", 123}));
353
354 KJ_EXPECT(table.size() == 2);
355 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("foo")) == (SiPair {"foo", 123}));
356 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(123)) == (SiPair {"foo", 123}));
357
358 KJ_EXPECT(
359 table.findOrCreate<0>("foo",
360 []() -> SiPair { KJ_FAIL_ASSERT("shouldn't have called this"); })
361 == (SiPair {"foo", 123}));
362 KJ_EXPECT(table.size() == 2);
363 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table",
364 table.findOrCreate<0>("corge", []() -> SiPair { return {"corge", 123}; }));
365
366 KJ_EXPECT(table.size() == 2);
367 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("foo")) == (SiPair {"foo", 123}));
368 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(123)) == (SiPair {"foo", 123}));
369 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("bar")) == (SiPair {"bar", 456}));
370 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(456)) == (SiPair {"bar", 456}));
371 KJ_EXPECT(table.find<0>("corge") == nullptr);
372
373 KJ_EXPECT(
374 table.findOrCreate<0>("corge", []() -> SiPair { return {"corge", 789}; })
375 == (SiPair {"corge", 789}));
376
377 KJ_EXPECT(table.size() == 3);
378 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("foo")) == (SiPair {"foo", 123}));
379 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(123)) == (SiPair {"foo", 123}));
380 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("bar")) == (SiPair {"bar", 456}));
381 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(456)) == (SiPair {"bar", 456}));
382 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("corge")) == (SiPair {"corge", 789}));
383 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(789)) == (SiPair {"corge", 789}));
384
385 KJ_EXPECT(
386 table.findOrCreate<1>(234, []() -> SiPair { return {"grault", 234}; })
387 == (SiPair {"grault", 234}));
388
389 KJ_EXPECT(table.size() == 4);
390 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("foo")) == (SiPair {"foo", 123}));
391 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(123)) == (SiPair {"foo", 123}));
392 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("bar")) == (SiPair {"bar", 456}));
393 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(456)) == (SiPair {"bar", 456}));
394 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("corge")) == (SiPair {"corge", 789}));
395 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(789)) == (SiPair {"corge", 789}));
396 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<0>("grault")) == (SiPair {"grault", 234}));
397 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find<1>(234)) == (SiPair {"grault", 234}));
398 }
399
400 class UintHasher {
401 public:
402 uint keyForRow(uint i) const { return i; }
403
404 bool matches(uint a, uint b) const {
405 return a == b;
406 }
407 uint hashCode(uint i) const {
408 return i;
409 }
410 };
411
412 KJ_TEST("benchmark: kj::Table<uint, HashIndex>") {
413 constexpr uint SOME_PRIME = BIG_PRIME;
414 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
415
416 for (auto step: STEP) {
417 KJ_CONTEXT(step);
418 Table<uint, HashIndex<UintHasher>> table;
419 for (uint i: kj::zeroTo(SOME_PRIME)) {
420 uint j = (i * step) % SOME_PRIME;
421 table.insert(j * 5 + 123);
422 }
423 for (uint i: kj::zeroTo(SOME_PRIME)) {
424 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
425 KJ_ASSERT(value == i * 5 + 123);
426 KJ_ASSERT(table.find(i * 5 + 122) == nullptr);
427 KJ_ASSERT(table.find(i * 5 + 124) == nullptr);
428 }
429
430 for (uint i: kj::zeroTo(SOME_PRIME)) {
431 if (i % 2 == 0 || i % 7 == 0) {
432 table.erase(KJ_ASSERT_NONNULL(table.find(i * 5 + 123)));
433 }
434 }
435
436 for (uint i: kj::zeroTo(SOME_PRIME)) {
437 if (i % 2 == 0 || i % 7 == 0) {
438 // erased
439 KJ_ASSERT(table.find(i * 5 + 123) == nullptr);
440 } else {
441 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
442 KJ_ASSERT(value == i * 5 + 123);
443 }
444 }
445 }
446 }
447
448 KJ_TEST("benchmark: std::unordered_set<uint>") {
449 constexpr uint SOME_PRIME = BIG_PRIME;
450 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
451
452 for (auto step: STEP) {
453 KJ_CONTEXT(step);
454 std::unordered_set<uint> table;
455 for (uint i: kj::zeroTo(SOME_PRIME)) {
456 uint j = (i * step) % SOME_PRIME;
457 table.insert(j * 5 + 123);
458 }
459 for (uint i: kj::zeroTo(SOME_PRIME)) {
460 auto iter = table.find(i * 5 + 123);
461 KJ_ASSERT(iter != table.end());
462 uint value = *iter;
463 KJ_ASSERT(value == i * 5 + 123);
464 KJ_ASSERT(table.find(i * 5 + 122) == table.end());
465 KJ_ASSERT(table.find(i * 5 + 124) == table.end());
466 }
467
468 for (uint i: kj::zeroTo(SOME_PRIME)) {
469 if (i % 2 == 0 || i % 7 == 0) {
470 KJ_ASSERT(table.erase(i * 5 + 123) > 0);
471 }
472 }
473
474 for (uint i: kj::zeroTo(SOME_PRIME)) {
475 if (i % 2 == 0 || i % 7 == 0) {
476 // erased
477 KJ_ASSERT(table.find(i * 5 + 123) == table.end());
478 } else {
479 auto iter = table.find(i * 5 + 123);
480 KJ_ASSERT(iter != table.end());
481 uint value = *iter;
482 KJ_ASSERT(value == i * 5 + 123);
483 }
484 }
485 }
486 }
487
488 KJ_TEST("benchmark: kj::Table<StringPtr, HashIndex>") {
489 constexpr uint SOME_PRIME = BIG_PRIME;
490 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
491
492 kj::Vector<String> strings(SOME_PRIME);
493 for (uint i: kj::zeroTo(SOME_PRIME)) {
494 strings.add(kj::str(i * 5 + 123));
495 }
496
497 for (auto step: STEP) {
498 KJ_CONTEXT(step);
499 Table<StringPtr, HashIndex<StringHasher>> table;
500 for (uint i: kj::zeroTo(SOME_PRIME)) {
501 uint j = (i * step) % SOME_PRIME;
502 table.insert(strings[j]);
503 }
504 for (uint i: kj::zeroTo(SOME_PRIME)) {
505 StringPtr value = KJ_ASSERT_NONNULL(table.find(strings[i]));
506 KJ_ASSERT(value == strings[i]);
507 }
508
509 for (uint i: kj::zeroTo(SOME_PRIME)) {
510 if (i % 2 == 0 || i % 7 == 0) {
511 table.erase(KJ_ASSERT_NONNULL(table.find(strings[i])));
512 }
513 }
514
515 for (uint i: kj::zeroTo(SOME_PRIME)) {
516 if (i % 2 == 0 || i % 7 == 0) {
517 // erased
518 KJ_ASSERT(table.find(strings[i]) == nullptr);
519 } else {
520 StringPtr value = KJ_ASSERT_NONNULL(table.find(strings[i]));
521 KJ_ASSERT(value == strings[i]);
522 }
523 }
524 }
525 }
526
527 struct StlStringHash {
528 inline size_t operator()(StringPtr str) const {
529 return kj::hashCode(str);
530 }
531 };
532
533 KJ_TEST("benchmark: std::unordered_set<StringPtr>") {
534 constexpr uint SOME_PRIME = BIG_PRIME;
535 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
536
537 kj::Vector<String> strings(SOME_PRIME);
538 for (uint i: kj::zeroTo(SOME_PRIME)) {
539 strings.add(kj::str(i * 5 + 123));
540 }
541
542 for (auto step: STEP) {
543 KJ_CONTEXT(step);
544 std::unordered_set<StringPtr, StlStringHash> table;
545 for (uint i: kj::zeroTo(SOME_PRIME)) {
546 uint j = (i * step) % SOME_PRIME;
547 table.insert(strings[j]);
548 }
549 for (uint i: kj::zeroTo(SOME_PRIME)) {
550 auto iter = table.find(strings[i]);
551 KJ_ASSERT(iter != table.end());
552 StringPtr value = *iter;
553 KJ_ASSERT(value == strings[i]);
554 }
555
556 for (uint i: kj::zeroTo(SOME_PRIME)) {
557 if (i % 2 == 0 || i % 7 == 0) {
558 KJ_ASSERT(table.erase(strings[i]) > 0);
559 }
560 }
561
562 for (uint i: kj::zeroTo(SOME_PRIME)) {
563 if (i % 2 == 0 || i % 7 == 0) {
564 // erased
565 KJ_ASSERT(table.find(strings[i]) == table.end());
566 } else {
567 auto iter = table.find(strings[i]);
568 KJ_ASSERT(iter != table.end());
569 StringPtr value = *iter;
570 KJ_ASSERT(value == strings[i]);
571 }
572 }
573 }
574 }
575
576 // =======================================================================================
577
578 KJ_TEST("B-tree internals") {
579 {
580 BTreeImpl::Leaf leaf;
581 memset(&leaf, 0, sizeof(leaf));
582
583 for (auto i: kj::indices(leaf.rows)) {
584 KJ_CONTEXT(i);
585
586 KJ_EXPECT(leaf.size() == i);
587
588 if (i < kj::size(leaf.rows) / 2) {
589 #ifdef KJ_DEBUG
590 KJ_EXPECT_THROW(FAILED, leaf.isHalfFull());
591 #endif
592 KJ_EXPECT(!leaf.isMostlyFull());
593 }
594
595 if (i == kj::size(leaf.rows) / 2) {
596 KJ_EXPECT(leaf.isHalfFull());
597 KJ_EXPECT(!leaf.isMostlyFull());
598 }
599
600 if (i > kj::size(leaf.rows) / 2) {
601 KJ_EXPECT(!leaf.isHalfFull());
602 KJ_EXPECT(leaf.isMostlyFull());
603 }
604
605 if (i == kj::size(leaf.rows)) {
606 KJ_EXPECT(leaf.isFull());
607 } else {
608 KJ_EXPECT(!leaf.isFull());
609 }
610
611 leaf.rows[i] = 1;
612 }
613 KJ_EXPECT(leaf.size() == kj::size(leaf.rows));
614 }
615
616 {
617 BTreeImpl::Parent parent;
618 memset(&parent, 0, sizeof(parent));
619
620 for (auto i: kj::indices(parent.keys)) {
621 KJ_CONTEXT(i);
622
623 KJ_EXPECT(parent.keyCount() == i);
624
625 if (i < kj::size(parent.keys) / 2) {
626 #ifdef KJ_DEBUG
627 KJ_EXPECT_THROW(FAILED, parent.isHalfFull());
628 #endif
629 KJ_EXPECT(!parent.isMostlyFull());
630 }
631
632 if (i == kj::size(parent.keys) / 2) {
633 KJ_EXPECT(parent.isHalfFull());
634 KJ_EXPECT(!parent.isMostlyFull());
635 }
636
637 if (i > kj::size(parent.keys) / 2) {
638 KJ_EXPECT(!parent.isHalfFull());
639 KJ_EXPECT(parent.isMostlyFull());
640 }
641
642 if (i == kj::size(parent.keys)) {
643 KJ_EXPECT(parent.isFull());
644 } else {
645 KJ_EXPECT(!parent.isFull());
646 }
647
648 parent.keys[i] = 1;
649 }
650 KJ_EXPECT(parent.keyCount() == kj::size(parent.keys));
651 }
652 }
653
654 class StringCompare {
655 public:
656 StringPtr keyForRow(StringPtr s) const { return s; }
657
658 bool isBefore(StringPtr a, StringPtr b) const {
659 return a < b;
660 }
661 bool matches(StringPtr a, StringPtr b) const {
662 return a == b;
663 }
664 };
665
666 KJ_TEST("simple tree table") {
667 Table<StringPtr, TreeIndex<StringCompare>> table;
668
669 KJ_EXPECT(table.find("foo") == nullptr);
670
671 KJ_EXPECT(table.size() == 0);
672 KJ_EXPECT(table.insert("foo") == "foo");
673 KJ_EXPECT(table.size() == 1);
674 KJ_EXPECT(table.insert("bar") == "bar");
675 KJ_EXPECT(table.size() == 2);
676
677 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("foo")) == "foo");
678 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
679 KJ_EXPECT(table.find("fop") == nullptr);
680 KJ_EXPECT(table.find("baq") == nullptr);
681
682 {
683 StringPtr& ref = table.insert("baz");
684 KJ_EXPECT(ref == "baz");
685 StringPtr& ref2 = KJ_ASSERT_NONNULL(table.find("baz"));
686 KJ_EXPECT(&ref == &ref2);
687 }
688
689 KJ_EXPECT(table.size() == 3);
690
691 {
692 auto range = table.ordered();
693 auto iter = range.begin();
694 KJ_EXPECT(*iter++ == "bar");
695 KJ_EXPECT(*iter++ == "baz");
696 KJ_EXPECT(*iter++ == "foo");
697 KJ_EXPECT(iter == range.end());
698 }
699
700 KJ_EXPECT(table.eraseMatch("foo"));
701 KJ_EXPECT(table.size() == 2);
702 KJ_EXPECT(table.find("foo") == nullptr);
703 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("bar")) == "bar");
704 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("baz")) == "baz");
705
706 {
707 auto range = table.ordered();
708 auto iter = range.begin();
709 KJ_EXPECT(*iter++ == "bar");
710 KJ_EXPECT(*iter++ == "baz");
711 KJ_EXPECT(iter == range.end());
712 }
713
714 {
715 auto& row = table.upsert("qux", [&](StringPtr&, StringPtr&&) {
716 KJ_FAIL_ASSERT("shouldn't get here");
717 });
718
719 auto copy = kj::str("qux");
720 table.upsert(StringPtr(copy), [&](StringPtr& existing, StringPtr&& param) {
721 KJ_EXPECT(param.begin() == copy.begin());
722 KJ_EXPECT(&existing == &row);
723 });
724
725 auto& found = KJ_ASSERT_NONNULL(table.find("qux"));
726 KJ_EXPECT(&found == &row);
727 }
728
729 StringPtr STRS[] = { "corge"_kj, "grault"_kj, "garply"_kj };
730 table.insertAll(ArrayPtr<StringPtr>(STRS));
731 KJ_EXPECT(table.size() == 6);
732 KJ_EXPECT(table.find("corge") != nullptr);
733 KJ_EXPECT(table.find("grault") != nullptr);
734 KJ_EXPECT(table.find("garply") != nullptr);
735
736 KJ_EXPECT_THROW_MESSAGE("inserted row already exists in table", table.insert("bar"));
737
738 KJ_EXPECT(table.size() == 6);
739
740 KJ_EXPECT(table.insert("baa") == "baa");
741
742 KJ_EXPECT(table.eraseAll([](StringPtr s) { return s.startsWith("ba"); }) == 3);
743 KJ_EXPECT(table.size() == 4);
744
745 {
746 auto range = table.ordered();
747 auto iter = range.begin();
748 KJ_EXPECT(*iter++ == "corge");
749 KJ_EXPECT(*iter++ == "garply");
750 KJ_EXPECT(*iter++ == "grault");
751 KJ_EXPECT(*iter++ == "qux");
752 KJ_EXPECT(iter == range.end());
753 }
754
755 {
756 auto range = table.range("foo", "har");
757 auto iter = range.begin();
758 KJ_EXPECT(*iter++ == "garply");
759 KJ_EXPECT(*iter++ == "grault");
760 KJ_EXPECT(iter == range.end());
761 }
762
763 {
764 auto range = table.range("garply", "grault");
765 auto iter = range.begin();
766 KJ_EXPECT(*iter++ == "garply");
767 KJ_EXPECT(iter == range.end());
768 }
769
770 {
771 auto iter = table.seek("garply");
772 KJ_EXPECT(*iter++ == "garply");
773 KJ_EXPECT(*iter++ == "grault");
774 KJ_EXPECT(*iter++ == "qux");
775 KJ_EXPECT(iter == table.ordered().end());
776 }
777
778 {
779 auto iter = table.seek("gorply");
780 KJ_EXPECT(*iter++ == "grault");
781 KJ_EXPECT(*iter++ == "qux");
782 KJ_EXPECT(iter == table.ordered().end());
783 }
784
785 auto& graultRow = table.begin()[1];
786 kj::StringPtr origGrault = graultRow;
787
788 KJ_EXPECT(&table.findOrCreate("grault",
789 [&]() -> kj::StringPtr { KJ_FAIL_ASSERT("shouldn't have called this"); }) == &graultRow);
790 KJ_EXPECT(graultRow.begin() == origGrault.begin());
791 KJ_EXPECT(&KJ_ASSERT_NONNULL(table.find("grault")) == &graultRow);
792 KJ_EXPECT(table.find("waldo") == nullptr);
793 KJ_EXPECT(table.size() == 4);
794
795 kj::String searchWaldo = kj::str("waldo");
796 kj::String insertWaldo = kj::str("waldo");
797
798 auto& waldo = table.findOrCreate(searchWaldo,
799 [&]() -> kj::StringPtr { return insertWaldo; });
800 KJ_EXPECT(waldo == "waldo");
801 KJ_EXPECT(waldo.begin() == insertWaldo.begin());
802 KJ_EXPECT(KJ_ASSERT_NONNULL(table.find("grault")) == "grault");
803 KJ_EXPECT(&KJ_ASSERT_NONNULL(table.find("waldo")) == &waldo);
804 KJ_EXPECT(table.size() == 5);
805
806 {
807 auto iter = table.begin();
808 KJ_EXPECT(*iter++ == "garply");
809 KJ_EXPECT(*iter++ == "grault");
810 KJ_EXPECT(*iter++ == "qux");
811 KJ_EXPECT(*iter++ == "corge");
812 KJ_EXPECT(*iter++ == "waldo");
813 KJ_EXPECT(iter == table.end());
814 }
815
816 // Verify that move constructor/assignment work.
817 Table<StringPtr, TreeIndex<StringCompare>> other(kj::mv(table));
818 KJ_EXPECT(other.size() == 5);
819 KJ_EXPECT(table.size() == 0);
820 KJ_EXPECT(table.begin() == table.end());
821 {
822 auto iter = other.begin();
823 KJ_EXPECT(*iter++ == "garply");
824 KJ_EXPECT(*iter++ == "grault");
825 KJ_EXPECT(*iter++ == "qux");
826 KJ_EXPECT(*iter++ == "corge");
827 KJ_EXPECT(*iter++ == "waldo");
828 KJ_EXPECT(iter == other.end());
829 }
830
831 table = kj::mv(other);
832 KJ_EXPECT(other.size() == 0);
833 KJ_EXPECT(table.size() == 5);
834 {
835 auto iter = table.begin();
836 KJ_EXPECT(*iter++ == "garply");
837 KJ_EXPECT(*iter++ == "grault");
838 KJ_EXPECT(*iter++ == "qux");
839 KJ_EXPECT(*iter++ == "corge");
840 KJ_EXPECT(*iter++ == "waldo");
841 KJ_EXPECT(iter == table.end());
842 }
843 KJ_EXPECT(other.begin() == other.end());
844 }
845
846 class UintCompare {
847 public:
848 uint keyForRow(uint i) const { return i; }
849
850 bool isBefore(uint a, uint b) const {
851 return a < b;
852 }
853 bool matches(uint a, uint b) const {
854 return a == b;
855 }
856 };
857
858 KJ_TEST("large tree table") {
859 constexpr uint SOME_PRIME = MEDIUM_PRIME;
860 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
861
862 for (auto step: STEP) {
863 KJ_CONTEXT(step);
864 Table<uint, TreeIndex<UintCompare>> table;
865 for (uint i: kj::zeroTo(SOME_PRIME)) {
866 uint j = (i * step) % SOME_PRIME;
867 table.insert(j * 5 + 123);
868 }
869 for (uint i: kj::zeroTo(SOME_PRIME)) {
870 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
871 KJ_ASSERT(value == i * 5 + 123);
872 KJ_ASSERT(table.find(i * 5 + 122) == nullptr);
873 KJ_ASSERT(table.find(i * 5 + 124) == nullptr);
874 }
875 table.verify();
876
877 {
878 auto range = table.ordered();
879 auto iter = range.begin();
880 for (uint i: kj::zeroTo(SOME_PRIME)) {
881 KJ_ASSERT(*iter++ == i * 5 + 123);
882 }
883 KJ_ASSERT(iter == range.end());
884 }
885
886 for (uint i: kj::zeroTo(SOME_PRIME)) {
887 KJ_CONTEXT(i);
888 if (i % 2 == 0 || i % 7 == 0) {
889 table.erase(KJ_ASSERT_NONNULL(table.find(i * 5 + 123), i));
890 table.verify();
891 }
892 }
893
894 {
895 auto range = table.ordered();
896 auto iter = range.begin();
897 for (uint i: kj::zeroTo(SOME_PRIME)) {
898 if (i % 2 == 0 || i % 7 == 0) {
899 // erased
900 KJ_ASSERT(table.find(i * 5 + 123) == nullptr);
901 } else {
902 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
903 KJ_ASSERT(value == i * 5 + 123);
904 KJ_ASSERT(*iter++ == i * 5 + 123);
905 }
906 }
907 KJ_ASSERT(iter == range.end());
908 }
909 }
910 }
911
912 KJ_TEST("TreeIndex fuzz test") {
913 // A test which randomly modifies a TreeIndex to try to discover buggy state changes.
914
915 uint seed = (kj::systemPreciseCalendarClock().now() - kj::UNIX_EPOCH) / kj::NANOSECONDS;
916 KJ_CONTEXT(seed); // print the seed if the test fails
917 srand(seed);
918
919 Table<uint, TreeIndex<UintCompare>> table;
920
921 auto randomInsert = [&]() {
922 table.upsert(rand(), [](auto&&, auto&&) {});
923 };
924 auto randomErase = [&]() {
925 if (table.size() > 0) {
926 auto& row = table.begin()[rand() % table.size()];
927 table.erase(row);
928 }
929 };
930 auto randomLookup = [&]() {
931 if (table.size() > 0) {
932 auto& row = table.begin()[rand() % table.size()];
933 auto& found = KJ_ASSERT_NONNULL(table.find(row));
934 KJ_ASSERT(&found == &row);
935 }
936 };
937
938 // First pass: focus on insertions, aim to do 2x as many insertions as deletions.
939 for (auto i KJ_UNUSED: kj::zeroTo(1000)) {
940 switch (rand() % 4) {
941 case 0:
942 case 1:
943 randomInsert();
944 break;
945 case 2:
946 randomErase();
947 break;
948 case 3:
949 randomLookup();
950 break;
951 }
952
953 table.verify();
954 }
955
956 // Second pass: focus on deletions, aim to do 2x as many deletions as insertions.
957 for (auto i KJ_UNUSED: kj::zeroTo(1000)) {
958 switch (rand() % 4) {
959 case 0:
960 randomInsert();
961 break;
962 case 1:
963 case 2:
964 randomErase();
965 break;
966 case 3:
967 randomLookup();
968 break;
969 }
970
971 table.verify();
972 }
973 }
974
975 KJ_TEST("TreeIndex clear() leaves tree in valid state") {
976 // A test which ensures that calling clear() does not break the internal state of a TreeIndex.
977 // It used to be the case that clearing a non-empty tree would leave it thinking that it had room
978 // for one more node than it really did, causing it to write and read beyond the end of its
979 // internal array of nodes.
980 Table<uint, TreeIndex<UintCompare>> table;
981
982 // Insert at least one value to allocate an initial set of tree nodes.
983 table.upsert(1, [](auto&&, auto&&) {});
984 KJ_EXPECT(table.find(1) != nullptr);
985 table.clear();
986
987 // Insert enough values to force writes/reads beyond the end of the tree's internal node array.
988 for (uint i = 0; i < 29; ++i) {
989 table.upsert(i, [](auto&&, auto&&) {});
990 }
991 for (uint i = 0; i < 29; ++i) {
992 KJ_EXPECT(table.find(i) != nullptr);
993 }
994 }
995
996 KJ_TEST("benchmark: kj::Table<uint, TreeIndex>") {
997 constexpr uint SOME_PRIME = BIG_PRIME;
998 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
999
1000 for (auto step: STEP) {
1001 KJ_CONTEXT(step);
1002 Table<uint, TreeIndex<UintCompare>> table;
1003 table.reserve(SOME_PRIME);
1004 for (uint i: kj::zeroTo(SOME_PRIME)) {
1005 uint j = (i * step) % SOME_PRIME;
1006 table.insert(j * 5 + 123);
1007 }
1008 for (uint i: kj::zeroTo(SOME_PRIME)) {
1009 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
1010 KJ_ASSERT(value == i * 5 + 123);
1011 KJ_ASSERT(table.find(i * 5 + 122) == nullptr);
1012 KJ_ASSERT(table.find(i * 5 + 124) == nullptr);
1013 }
1014
1015 for (uint i: kj::zeroTo(SOME_PRIME)) {
1016 if (i % 2 == 0 || i % 7 == 0) {
1017 table.erase(KJ_ASSERT_NONNULL(table.find(i * 5 + 123)));
1018 }
1019 }
1020
1021 for (uint i: kj::zeroTo(SOME_PRIME)) {
1022 if (i % 2 == 0 || i % 7 == 0) {
1023 // erased
1024 KJ_ASSERT(table.find(i * 5 + 123) == nullptr);
1025 } else {
1026 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123));
1027 KJ_ASSERT(value == i * 5 + 123);
1028 }
1029 }
1030 }
1031 }
1032
1033 KJ_TEST("benchmark: std::set<uint>") {
1034 constexpr uint SOME_PRIME = BIG_PRIME;
1035 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
1036
1037 for (auto step: STEP) {
1038 KJ_CONTEXT(step);
1039 std::set<uint> table;
1040 for (uint i: kj::zeroTo(SOME_PRIME)) {
1041 uint j = (i * step) % SOME_PRIME;
1042 table.insert(j * 5 + 123);
1043 }
1044 for (uint i: kj::zeroTo(SOME_PRIME)) {
1045 auto iter = table.find(i * 5 + 123);
1046 KJ_ASSERT(iter != table.end());
1047 uint value = *iter;
1048 KJ_ASSERT(value == i * 5 + 123);
1049 KJ_ASSERT(table.find(i * 5 + 122) == table.end());
1050 KJ_ASSERT(table.find(i * 5 + 124) == table.end());
1051 }
1052
1053 for (uint i: kj::zeroTo(SOME_PRIME)) {
1054 if (i % 2 == 0 || i % 7 == 0) {
1055 KJ_ASSERT(table.erase(i * 5 + 123) > 0);
1056 }
1057 }
1058
1059 for (uint i: kj::zeroTo(SOME_PRIME)) {
1060 if (i % 2 == 0 || i % 7 == 0) {
1061 // erased
1062 KJ_ASSERT(table.find(i * 5 + 123) == table.end());
1063 } else {
1064 auto iter = table.find(i * 5 + 123);
1065 KJ_ASSERT(iter != table.end());
1066 uint value = *iter;
1067 KJ_ASSERT(value == i * 5 + 123);
1068 }
1069 }
1070 }
1071 }
1072
1073 KJ_TEST("benchmark: kj::Table<StringPtr, TreeIndex>") {
1074 constexpr uint SOME_PRIME = BIG_PRIME;
1075 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
1076
1077 kj::Vector<String> strings(SOME_PRIME);
1078 for (uint i: kj::zeroTo(SOME_PRIME)) {
1079 strings.add(kj::str(i * 5 + 123));
1080 }
1081
1082 for (auto step: STEP) {
1083 KJ_CONTEXT(step);
1084 Table<StringPtr, TreeIndex<StringCompare>> table;
1085 table.reserve(SOME_PRIME);
1086 for (uint i: kj::zeroTo(SOME_PRIME)) {
1087 uint j = (i * step) % SOME_PRIME;
1088 table.insert(strings[j]);
1089 }
1090 for (uint i: kj::zeroTo(SOME_PRIME)) {
1091 StringPtr value = KJ_ASSERT_NONNULL(table.find(strings[i]));
1092 KJ_ASSERT(value == strings[i]);
1093 }
1094
1095 for (uint i: kj::zeroTo(SOME_PRIME)) {
1096 if (i % 2 == 0 || i % 7 == 0) {
1097 table.erase(KJ_ASSERT_NONNULL(table.find(strings[i])));
1098 }
1099 }
1100
1101 for (uint i: kj::zeroTo(SOME_PRIME)) {
1102 if (i % 2 == 0 || i % 7 == 0) {
1103 // erased
1104 KJ_ASSERT(table.find(strings[i]) == nullptr);
1105 } else {
1106 auto& value = KJ_ASSERT_NONNULL(table.find(strings[i]));
1107 KJ_ASSERT(value == strings[i]);
1108 }
1109 }
1110 }
1111 }
1112
1113 KJ_TEST("benchmark: std::set<StringPtr>") {
1114 constexpr uint SOME_PRIME = BIG_PRIME;
1115 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127};
1116
1117 kj::Vector<String> strings(SOME_PRIME);
1118 for (uint i: kj::zeroTo(SOME_PRIME)) {
1119 strings.add(kj::str(i * 5 + 123));
1120 }
1121
1122 for (auto step: STEP) {
1123 KJ_CONTEXT(step);
1124 std::set<StringPtr> table;
1125 for (uint i: kj::zeroTo(SOME_PRIME)) {
1126 uint j = (i * step) % SOME_PRIME;
1127 table.insert(strings[j]);
1128 }
1129 for (uint i: kj::zeroTo(SOME_PRIME)) {
1130 auto iter = table.find(strings[i]);
1131 KJ_ASSERT(iter != table.end());
1132 StringPtr value = *iter;
1133 KJ_ASSERT(value == strings[i]);
1134 }
1135
1136 for (uint i: kj::zeroTo(SOME_PRIME)) {
1137 if (i % 2 == 0 || i % 7 == 0) {
1138 KJ_ASSERT(table.erase(strings[i]) > 0);
1139 }
1140 }
1141
1142 for (uint i: kj::zeroTo(SOME_PRIME)) {
1143 if (i % 2 == 0 || i % 7 == 0) {
1144 // erased
1145 KJ_ASSERT(table.find(strings[i]) == table.end());
1146 } else {
1147 auto iter = table.find(strings[i]);
1148 KJ_ASSERT(iter != table.end());
1149 StringPtr value = *iter;
1150 KJ_ASSERT(value == strings[i]);
1151 }
1152 }
1153 }
1154 }
1155
1156 // =======================================================================================
1157
1158 KJ_TEST("insertion order index") {
1159 Table<uint, InsertionOrderIndex> table;
1160
1161 {
1162 auto range = table.ordered();
1163 KJ_EXPECT(range.begin() == range.end());
1164 }
1165
1166 table.insert(12);
1167 table.insert(34);
1168 table.insert(56);
1169 table.insert(78);
1170
1171 {
1172 auto range = table.ordered();
1173 auto iter = range.begin();
1174 KJ_ASSERT(iter != range.end());
1175 KJ_EXPECT(*iter++ == 12);
1176 KJ_ASSERT(iter != range.end());
1177 KJ_EXPECT(*iter++ == 34);
1178 KJ_ASSERT(iter != range.end());
1179 KJ_EXPECT(*iter++ == 56);
1180 KJ_ASSERT(iter != range.end());
1181 KJ_EXPECT(*iter++ == 78);
1182 KJ_EXPECT(iter == range.end());
1183 KJ_EXPECT(*--iter == 78);
1184 KJ_EXPECT(*--iter == 56);
1185 KJ_EXPECT(*--iter == 34);
1186 KJ_EXPECT(*--iter == 12);
1187 KJ_EXPECT(iter == range.begin());
1188 }
1189
1190 table.erase(table.begin()[1]);
1191
1192 {
1193 auto range = table.ordered();
1194 auto iter = range.begin();
1195 KJ_ASSERT(iter != range.end());
1196 KJ_EXPECT(*iter++ == 12);
1197 KJ_ASSERT(iter != range.end());
1198 KJ_EXPECT(*iter++ == 56);
1199 KJ_ASSERT(iter != range.end());
1200 KJ_EXPECT(*iter++ == 78);
1201 KJ_EXPECT(iter == range.end());
1202 KJ_EXPECT(*--iter == 78);
1203 KJ_EXPECT(*--iter == 56);
1204 KJ_EXPECT(*--iter == 12);
1205 KJ_EXPECT(iter == range.begin());
1206 }
1207
1208 // Allocate enough more elements to cause a resize.
1209 table.insert(111);
1210 table.insert(222);
1211 table.insert(333);
1212 table.insert(444);
1213 table.insert(555);
1214 table.insert(666);
1215 table.insert(777);
1216 table.insert(888);
1217 table.insert(999);
1218
1219 {
1220 auto range = table.ordered();
1221 auto iter = range.begin();
1222 KJ_ASSERT(iter != range.end());
1223 KJ_EXPECT(*iter++ == 12);
1224 KJ_ASSERT(iter != range.end());
1225 KJ_EXPECT(*iter++ == 56);
1226 KJ_ASSERT(iter != range.end());
1227 KJ_EXPECT(*iter++ == 78);
1228 KJ_ASSERT(iter != range.end());
1229 KJ_EXPECT(*iter++ == 111);
1230 KJ_ASSERT(iter != range.end());
1231 KJ_EXPECT(*iter++ == 222);
1232 KJ_ASSERT(iter != range.end());
1233 KJ_EXPECT(*iter++ == 333);
1234 KJ_ASSERT(iter != range.end());
1235 KJ_EXPECT(*iter++ == 444);
1236 KJ_ASSERT(iter != range.end());
1237 KJ_EXPECT(*iter++ == 555);
1238 KJ_ASSERT(iter != range.end());
1239 KJ_EXPECT(*iter++ == 666);
1240 KJ_ASSERT(iter != range.end());
1241 KJ_EXPECT(*iter++ == 777);
1242 KJ_ASSERT(iter != range.end());
1243 KJ_EXPECT(*iter++ == 888);
1244 KJ_ASSERT(iter != range.end());
1245 KJ_EXPECT(*iter++ == 999);
1246 KJ_EXPECT(iter == range.end());
1247 }
1248
1249 // Remove everything.
1250 while (table.size() > 0) {
1251 table.erase(*table.begin());
1252 }
1253
1254 {
1255 auto range = table.ordered();
1256 KJ_EXPECT(range.begin() == range.end());
1257 }
1258 }
1259
1260 KJ_TEST("insertion order index is movable") {
1261 using UintTable = Table<uint, InsertionOrderIndex>;
1262
1263 kj::Maybe<UintTable> myTable;
1264
1265 {
1266 UintTable yourTable;
1267
1268 yourTable.insert(12);
1269 yourTable.insert(34);
1270 yourTable.insert(56);
1271 yourTable.insert(78);
1272 yourTable.insert(111);
1273 yourTable.insert(222);
1274 yourTable.insert(333);
1275 yourTable.insert(444);
1276 yourTable.insert(555);
1277 yourTable.insert(666);
1278 yourTable.insert(777);
1279 yourTable.insert(888);
1280 yourTable.insert(999);
1281
1282 myTable = kj::mv(yourTable);
1283 }
1284
1285 auto& table = KJ_ASSERT_NONNULL(myTable);
1286
1287 // At one time the following induced a segfault/double-free, due to incorrect memory management in
1288 // InsertionOrderIndex's move ctor and dtor.
1289 auto range = table.ordered();
1290 auto iter = range.begin();
1291 KJ_ASSERT(iter != range.end());
1292 KJ_EXPECT(*iter++ == 12);
1293 KJ_ASSERT(iter != range.end());
1294 KJ_EXPECT(*iter++ == 34);
1295 KJ_ASSERT(iter != range.end());
1296 KJ_EXPECT(*iter++ == 56);
1297 KJ_ASSERT(iter != range.end());
1298 KJ_EXPECT(*iter++ == 78);
1299 KJ_ASSERT(iter != range.end());
1300 KJ_EXPECT(*iter++ == 111);
1301 KJ_ASSERT(iter != range.end());
1302 KJ_EXPECT(*iter++ == 222);
1303 KJ_ASSERT(iter != range.end());
1304 KJ_EXPECT(*iter++ == 333);
1305 KJ_ASSERT(iter != range.end());
1306 KJ_EXPECT(*iter++ == 444);
1307 KJ_ASSERT(iter != range.end());
1308 KJ_EXPECT(*iter++ == 555);
1309 KJ_ASSERT(iter != range.end());
1310 KJ_EXPECT(*iter++ == 666);
1311 KJ_ASSERT(iter != range.end());
1312 KJ_EXPECT(*iter++ == 777);
1313 KJ_ASSERT(iter != range.end());
1314 KJ_EXPECT(*iter++ == 888);
1315 KJ_ASSERT(iter != range.end());
1316 KJ_EXPECT(*iter++ == 999);
1317 KJ_EXPECT(iter == range.end());
1318 }
1319
1320 // =======================================================================================
1321 // Test bug where insertion failure on a later index in the table would not be rolled back
1322 // correctly if a previous index was TreeIndex.
1323
1324 class StringLengthCompare {
1325 // Considers two strings equal if they have the same length.
1326 public:
1327 inline size_t keyForRow(StringPtr entry) const {
1328 return entry.size();
1329 }
1330
1331 inline bool matches(StringPtr e, size_t key) const {
1332 return e.size() == key;
1333 }
1334
1335 inline bool isBefore(StringPtr e, size_t key) const {
1336 return e.size() < key;
1337 }
1338
1339 uint hashCode(size_t size) const {
1340 return size;
1341 }
1342 };
1343
1344 KJ_TEST("HashIndex rollback on insertion failure") {
1345 // Test that when an insertion produces a duplicate on a later index, changes to previous indexes
1346 // are properly rolled back.
1347
1348 Table<StringPtr, HashIndex<StringHasher>, HashIndex<StringLengthCompare>> table;
1349 table.insert("a"_kj);
1350 table.insert("ab"_kj);
1351 table.insert("abc"_kj);
1352
1353 {
1354 // We use upsert() so that we don't throw an exception from the duplicate, but this exercises
1355 // the same logic as a duplicate insert() other than throwing.
1356 kj::StringPtr& found = table.upsert("xyz"_kj, [&](StringPtr& existing, StringPtr&& param) {
1357 KJ_EXPECT(existing == "abc");
1358 KJ_EXPECT(param == "xyz");
1359 });
1360 KJ_EXPECT(found == "abc");
1361
1362 table.erase(found);
1363 }
1364
1365 table.insert("xyz"_kj);
1366
1367 {
1368 kj::StringPtr& found = table.upsert("tuv"_kj, [&](StringPtr& existing, StringPtr&& param) {
1369 KJ_EXPECT(existing == "xyz");
1370 KJ_EXPECT(param == "tuv");
1371 });
1372 KJ_EXPECT(found == "xyz");
1373 }
1374 }
1375
1376 KJ_TEST("TreeIndex rollback on insertion failure") {
1377 // Test that when an insertion produces a duplicate on a later index, changes to previous indexes
1378 // are properly rolled back.
1379
1380 Table<StringPtr, TreeIndex<StringCompare>, TreeIndex<StringLengthCompare>> table;
1381 table.insert("a"_kj);
1382 table.insert("ab"_kj);
1383 table.insert("abc"_kj);
1384
1385 {
1386 // We use upsert() so that we don't throw an exception from the duplicate, but this exercises
1387 // the same logic as a duplicate insert() other than throwing.
1388 kj::StringPtr& found = table.upsert("xyz"_kj, [&](StringPtr& existing, StringPtr&& param) {
1389 KJ_EXPECT(existing == "abc");
1390 KJ_EXPECT(param == "xyz");
1391 });
1392 KJ_EXPECT(found == "abc");
1393
1394 table.erase(found);
1395 }
1396
1397 table.insert("xyz"_kj);
1398
1399 {
1400 kj::StringPtr& found = table.upsert("tuv"_kj, [&](StringPtr& existing, StringPtr&& param) {
1401 KJ_EXPECT(existing == "xyz");
1402 KJ_EXPECT(param == "tuv");
1403 });
1404 KJ_EXPECT(found == "xyz");
1405 }
1406 }
1407
1408 } // namespace
1409 } // namespace _
1410 } // namespace kj