1 #include <robin_hood.h>
2
3 #include <app/CtorDtorVerifier.h>
4 #include <app/doctest.h>
5 #include <app/fmt/hex.h>
6 #include <app/hash/Bad.h>
7 #include <app/sfc64.h>
8
9 #include <iostream>
10 #include <unordered_set>
11
12 TEST_CASE_TEMPLATE(
13 "collisions", Map,
14 robin_hood::unordered_flat_map<CtorDtorVerifier, CtorDtorVerifier, hash::Bad<CtorDtorVerifier>>,
15 robin_hood::unordered_node_map<CtorDtorVerifier, CtorDtorVerifier,
16 hash::Bad<CtorDtorVerifier>>) {
17
18 static const uint64_t max_val = 127;
19
20 // CtorDtorVerifier::mDoPrintDebugInfo = true;
21 {
22 Map m;
23 for (uint64_t i = 0; i < max_val; ++i) {
24 INFO(i);
25 m[i];
26 }
27 REQUIRE(m.size() == max_val);
28 REQUIRE_THROWS_AS(m[max_val], std::overflow_error);
29 REQUIRE(m.size() == max_val);
30 }
31 if (0 != CtorDtorVerifier::mapSize()) {
32 CtorDtorVerifier::printMap();
33 }
34 REQUIRE(CtorDtorVerifier::mapSize() == 0);
35
36 // produce overflow with insert
37 {
38 Map m;
39 for (uint64_t i = 0; i < max_val; ++i) {
40 REQUIRE(m.insert(typename Map::value_type(i, i)).second);
41 }
42 REQUIRE(m.size() == max_val);
43 REQUIRE_THROWS_AS(m.insert(typename Map::value_type(max_val, max_val)),
44 std::overflow_error);
45 REQUIRE(m.size() == max_val);
46 }
47 if (0 != CtorDtorVerifier::mapSize()) {
48 CtorDtorVerifier::printMap();
49 }
50
51 // produce overflow with emplace
52 {
53 Map m;
54 for (uint64_t i = 0; i < max_val; ++i) {
55 REQUIRE(m.insert(typename Map::value_type(i, i)).second);
56 }
57 REQUIRE(m.size() == max_val);
58 REQUIRE_THROWS_AS(m.emplace(typename Map::value_type(max_val, max_val)),
59 std::overflow_error);
60 REQUIRE(m.size() == max_val);
61 }
62 if (0 != CtorDtorVerifier::mapSize()) {
63 CtorDtorVerifier::printMap();
64 }
65 REQUIRE(CtorDtorVerifier::mapSize() == 0);
66 }
67
68 #if ROBIN_HOOD(BITNESS) == 64
69
70 namespace {
71
isColliding(uint64_t x)72 bool isColliding(uint64_t x) {
73 return UINT64_C(0) == (x & UINT64_C(0x1fffff));
74 }
75
76 } // namespace
77
skip()78 TEST_CASE("overflow_finder" * doctest::skip()) {
79 robin_hood::unordered_set<uint64_t> set;
80
81 // loop until we get an overflow
82 // auto mix = UINT64_C(0x73e6d3e6f41f53a9);
83 for (uint64_t i = 0; i < UINT64_C(1000000000); ++i) {
84 auto s = i;
85 auto h1 = robin_hood::hash<uint64_t>{}(s);
86 auto h2 = h1;
87 h1 >>= 32U;
88 // robin_hood::hash<uint64_t>{}(s * mix);
89
90 if (isColliding(h1)) {
91 std::cout << i << ": " << fmt::hex(s) << " -> " << fmt::hex(h1) << " " << fmt::hex(h2)
92 << " " << isColliding(h2) << std::endl;
93 set.insert(s);
94 }
95 }
96 }
97
skip()98 TEST_CASE("overflow_finder_simple" * doctest::skip()) {
99 robin_hood::unordered_set<uint64_t> set;
100 size_t count = 0;
101 uint64_t i = 0;
102 try {
103 while (count < 255U) {
104 auto h = robin_hood::hash<uint64_t>{}(i);
105 if (UINT64_C(0) == (h & UINT64_C(0x1fffff))) {
106 ++count;
107 set.insert(i);
108 }
109 ++i;
110 }
111 } catch (std::overflow_error&) {
112 FAIL("i=" << i << ", count=" << count);
113 }
114 }
115
116 #endif
117