table-test.c++ (36924B)
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() == 3); 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("benchmark: kj::Table<uint, TreeIndex>") { 976 constexpr uint SOME_PRIME = BIG_PRIME; 977 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127}; 978 979 for (auto step: STEP) { 980 KJ_CONTEXT(step); 981 Table<uint, TreeIndex<UintCompare>> table; 982 table.reserve(SOME_PRIME); 983 for (uint i: kj::zeroTo(SOME_PRIME)) { 984 uint j = (i * step) % SOME_PRIME; 985 table.insert(j * 5 + 123); 986 } 987 for (uint i: kj::zeroTo(SOME_PRIME)) { 988 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123)); 989 KJ_ASSERT(value == i * 5 + 123); 990 KJ_ASSERT(table.find(i * 5 + 122) == nullptr); 991 KJ_ASSERT(table.find(i * 5 + 124) == nullptr); 992 } 993 994 for (uint i: kj::zeroTo(SOME_PRIME)) { 995 if (i % 2 == 0 || i % 7 == 0) { 996 table.erase(KJ_ASSERT_NONNULL(table.find(i * 5 + 123))); 997 } 998 } 999 1000 for (uint i: kj::zeroTo(SOME_PRIME)) { 1001 if (i % 2 == 0 || i % 7 == 0) { 1002 // erased 1003 KJ_ASSERT(table.find(i * 5 + 123) == nullptr); 1004 } else { 1005 uint value = KJ_ASSERT_NONNULL(table.find(i * 5 + 123)); 1006 KJ_ASSERT(value == i * 5 + 123); 1007 } 1008 } 1009 } 1010 } 1011 1012 KJ_TEST("benchmark: std::set<uint>") { 1013 constexpr uint SOME_PRIME = BIG_PRIME; 1014 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127}; 1015 1016 for (auto step: STEP) { 1017 KJ_CONTEXT(step); 1018 std::set<uint> table; 1019 for (uint i: kj::zeroTo(SOME_PRIME)) { 1020 uint j = (i * step) % SOME_PRIME; 1021 table.insert(j * 5 + 123); 1022 } 1023 for (uint i: kj::zeroTo(SOME_PRIME)) { 1024 auto iter = table.find(i * 5 + 123); 1025 KJ_ASSERT(iter != table.end()); 1026 uint value = *iter; 1027 KJ_ASSERT(value == i * 5 + 123); 1028 KJ_ASSERT(table.find(i * 5 + 122) == table.end()); 1029 KJ_ASSERT(table.find(i * 5 + 124) == table.end()); 1030 } 1031 1032 for (uint i: kj::zeroTo(SOME_PRIME)) { 1033 if (i % 2 == 0 || i % 7 == 0) { 1034 KJ_ASSERT(table.erase(i * 5 + 123) > 0); 1035 } 1036 } 1037 1038 for (uint i: kj::zeroTo(SOME_PRIME)) { 1039 if (i % 2 == 0 || i % 7 == 0) { 1040 // erased 1041 KJ_ASSERT(table.find(i * 5 + 123) == table.end()); 1042 } else { 1043 auto iter = table.find(i * 5 + 123); 1044 KJ_ASSERT(iter != table.end()); 1045 uint value = *iter; 1046 KJ_ASSERT(value == i * 5 + 123); 1047 } 1048 } 1049 } 1050 } 1051 1052 KJ_TEST("benchmark: kj::Table<StringPtr, TreeIndex>") { 1053 constexpr uint SOME_PRIME = BIG_PRIME; 1054 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127}; 1055 1056 kj::Vector<String> strings(SOME_PRIME); 1057 for (uint i: kj::zeroTo(SOME_PRIME)) { 1058 strings.add(kj::str(i * 5 + 123)); 1059 } 1060 1061 for (auto step: STEP) { 1062 KJ_CONTEXT(step); 1063 Table<StringPtr, TreeIndex<StringCompare>> table; 1064 table.reserve(SOME_PRIME); 1065 for (uint i: kj::zeroTo(SOME_PRIME)) { 1066 uint j = (i * step) % SOME_PRIME; 1067 table.insert(strings[j]); 1068 } 1069 for (uint i: kj::zeroTo(SOME_PRIME)) { 1070 StringPtr value = KJ_ASSERT_NONNULL(table.find(strings[i])); 1071 KJ_ASSERT(value == strings[i]); 1072 } 1073 1074 for (uint i: kj::zeroTo(SOME_PRIME)) { 1075 if (i % 2 == 0 || i % 7 == 0) { 1076 table.erase(KJ_ASSERT_NONNULL(table.find(strings[i]))); 1077 } 1078 } 1079 1080 for (uint i: kj::zeroTo(SOME_PRIME)) { 1081 if (i % 2 == 0 || i % 7 == 0) { 1082 // erased 1083 KJ_ASSERT(table.find(strings[i]) == nullptr); 1084 } else { 1085 auto& value = KJ_ASSERT_NONNULL(table.find(strings[i])); 1086 KJ_ASSERT(value == strings[i]); 1087 } 1088 } 1089 } 1090 } 1091 1092 KJ_TEST("benchmark: std::set<StringPtr>") { 1093 constexpr uint SOME_PRIME = BIG_PRIME; 1094 constexpr uint STEP[] = {1, 2, 4, 7, 43, 127}; 1095 1096 kj::Vector<String> strings(SOME_PRIME); 1097 for (uint i: kj::zeroTo(SOME_PRIME)) { 1098 strings.add(kj::str(i * 5 + 123)); 1099 } 1100 1101 for (auto step: STEP) { 1102 KJ_CONTEXT(step); 1103 std::set<StringPtr> table; 1104 for (uint i: kj::zeroTo(SOME_PRIME)) { 1105 uint j = (i * step) % SOME_PRIME; 1106 table.insert(strings[j]); 1107 } 1108 for (uint i: kj::zeroTo(SOME_PRIME)) { 1109 auto iter = table.find(strings[i]); 1110 KJ_ASSERT(iter != table.end()); 1111 StringPtr value = *iter; 1112 KJ_ASSERT(value == strings[i]); 1113 } 1114 1115 for (uint i: kj::zeroTo(SOME_PRIME)) { 1116 if (i % 2 == 0 || i % 7 == 0) { 1117 KJ_ASSERT(table.erase(strings[i]) > 0); 1118 } 1119 } 1120 1121 for (uint i: kj::zeroTo(SOME_PRIME)) { 1122 if (i % 2 == 0 || i % 7 == 0) { 1123 // erased 1124 KJ_ASSERT(table.find(strings[i]) == table.end()); 1125 } else { 1126 auto iter = table.find(strings[i]); 1127 KJ_ASSERT(iter != table.end()); 1128 StringPtr value = *iter; 1129 KJ_ASSERT(value == strings[i]); 1130 } 1131 } 1132 } 1133 } 1134 1135 // ======================================================================================= 1136 1137 KJ_TEST("insertion order index") { 1138 Table<uint, InsertionOrderIndex> table; 1139 1140 { 1141 auto range = table.ordered(); 1142 KJ_EXPECT(range.begin() == range.end()); 1143 } 1144 1145 table.insert(12); 1146 table.insert(34); 1147 table.insert(56); 1148 table.insert(78); 1149 1150 { 1151 auto range = table.ordered(); 1152 auto iter = range.begin(); 1153 KJ_ASSERT(iter != range.end()); 1154 KJ_EXPECT(*iter++ == 12); 1155 KJ_ASSERT(iter != range.end()); 1156 KJ_EXPECT(*iter++ == 34); 1157 KJ_ASSERT(iter != range.end()); 1158 KJ_EXPECT(*iter++ == 56); 1159 KJ_ASSERT(iter != range.end()); 1160 KJ_EXPECT(*iter++ == 78); 1161 KJ_EXPECT(iter == range.end()); 1162 KJ_EXPECT(*--iter == 78); 1163 KJ_EXPECT(*--iter == 56); 1164 KJ_EXPECT(*--iter == 34); 1165 KJ_EXPECT(*--iter == 12); 1166 KJ_EXPECT(iter == range.begin()); 1167 } 1168 1169 table.erase(table.begin()[1]); 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++ == 56); 1178 KJ_ASSERT(iter != range.end()); 1179 KJ_EXPECT(*iter++ == 78); 1180 KJ_EXPECT(iter == range.end()); 1181 KJ_EXPECT(*--iter == 78); 1182 KJ_EXPECT(*--iter == 56); 1183 KJ_EXPECT(*--iter == 12); 1184 KJ_EXPECT(iter == range.begin()); 1185 } 1186 1187 // Allocate enough more elements to cause a resize. 1188 table.insert(111); 1189 table.insert(222); 1190 table.insert(333); 1191 table.insert(444); 1192 table.insert(555); 1193 table.insert(666); 1194 table.insert(777); 1195 table.insert(888); 1196 table.insert(999); 1197 1198 { 1199 auto range = table.ordered(); 1200 auto iter = range.begin(); 1201 KJ_ASSERT(iter != range.end()); 1202 KJ_EXPECT(*iter++ == 12); 1203 KJ_ASSERT(iter != range.end()); 1204 KJ_EXPECT(*iter++ == 56); 1205 KJ_ASSERT(iter != range.end()); 1206 KJ_EXPECT(*iter++ == 78); 1207 KJ_ASSERT(iter != range.end()); 1208 KJ_EXPECT(*iter++ == 111); 1209 KJ_ASSERT(iter != range.end()); 1210 KJ_EXPECT(*iter++ == 222); 1211 KJ_ASSERT(iter != range.end()); 1212 KJ_EXPECT(*iter++ == 333); 1213 KJ_ASSERT(iter != range.end()); 1214 KJ_EXPECT(*iter++ == 444); 1215 KJ_ASSERT(iter != range.end()); 1216 KJ_EXPECT(*iter++ == 555); 1217 KJ_ASSERT(iter != range.end()); 1218 KJ_EXPECT(*iter++ == 666); 1219 KJ_ASSERT(iter != range.end()); 1220 KJ_EXPECT(*iter++ == 777); 1221 KJ_ASSERT(iter != range.end()); 1222 KJ_EXPECT(*iter++ == 888); 1223 KJ_ASSERT(iter != range.end()); 1224 KJ_EXPECT(*iter++ == 999); 1225 KJ_EXPECT(iter == range.end()); 1226 } 1227 1228 // Remove everything. 1229 while (table.size() > 0) { 1230 table.erase(*table.begin()); 1231 } 1232 1233 { 1234 auto range = table.ordered(); 1235 KJ_EXPECT(range.begin() == range.end()); 1236 } 1237 } 1238 1239 KJ_TEST("insertion order index is movable") { 1240 using UintTable = Table<uint, InsertionOrderIndex>; 1241 1242 kj::Maybe<UintTable> myTable; 1243 1244 { 1245 UintTable yourTable; 1246 1247 yourTable.insert(12); 1248 yourTable.insert(34); 1249 yourTable.insert(56); 1250 yourTable.insert(78); 1251 yourTable.insert(111); 1252 yourTable.insert(222); 1253 yourTable.insert(333); 1254 yourTable.insert(444); 1255 yourTable.insert(555); 1256 yourTable.insert(666); 1257 yourTable.insert(777); 1258 yourTable.insert(888); 1259 yourTable.insert(999); 1260 1261 myTable = kj::mv(yourTable); 1262 } 1263 1264 auto& table = KJ_ASSERT_NONNULL(myTable); 1265 1266 // At one time the following induced a segfault/double-free, due to incorrect memory management in 1267 // InsertionOrderIndex's move ctor and dtor. 1268 auto range = table.ordered(); 1269 auto iter = range.begin(); 1270 KJ_ASSERT(iter != range.end()); 1271 KJ_EXPECT(*iter++ == 12); 1272 KJ_ASSERT(iter != range.end()); 1273 KJ_EXPECT(*iter++ == 34); 1274 KJ_ASSERT(iter != range.end()); 1275 KJ_EXPECT(*iter++ == 56); 1276 KJ_ASSERT(iter != range.end()); 1277 KJ_EXPECT(*iter++ == 78); 1278 KJ_ASSERT(iter != range.end()); 1279 KJ_EXPECT(*iter++ == 111); 1280 KJ_ASSERT(iter != range.end()); 1281 KJ_EXPECT(*iter++ == 222); 1282 KJ_ASSERT(iter != range.end()); 1283 KJ_EXPECT(*iter++ == 333); 1284 KJ_ASSERT(iter != range.end()); 1285 KJ_EXPECT(*iter++ == 444); 1286 KJ_ASSERT(iter != range.end()); 1287 KJ_EXPECT(*iter++ == 555); 1288 KJ_ASSERT(iter != range.end()); 1289 KJ_EXPECT(*iter++ == 666); 1290 KJ_ASSERT(iter != range.end()); 1291 KJ_EXPECT(*iter++ == 777); 1292 KJ_ASSERT(iter != range.end()); 1293 KJ_EXPECT(*iter++ == 888); 1294 KJ_ASSERT(iter != range.end()); 1295 KJ_EXPECT(*iter++ == 999); 1296 KJ_EXPECT(iter == range.end()); 1297 } 1298 1299 } // namespace 1300 } // namespace _ 1301 } // namespace kj