81[[nodiscard]]
constexpr auto create(
const Hash& hash,
const GetKey& getKey)
83 static_assert(N < 128);
84 constexpr size_t M = std::bit_ceil(N);
85 constexpr auto bucket_max = size_t(2 *
cstd::sqrt(M));
91 std::array<static_vector<uint8_t, bucket_max>, r.tab1.size()> buckets;
93 buckets[hash(getKey(i)) % r.tab1.size()].push_back(uint8_t(i));
99 if (x.size() != y.size()) {
100 return x.size() > y.size();
103 return std::lexicographical_compare(x.begin(), x.end(),
108 constexpr auto UNUSED = uint8_t(-1);
110 for (
const auto& bucket : buckets) {
111 auto const bSize = bucket.size();
112 if (bSize == 0)
break;
113 auto hash1 = hash(getKey(bucket[0])) % r.tab1.size();
116 r.tab1[hash1] = bucket[0];
123 while (bucket_slots.
size() < bSize) {
124 auto hash2 = hash(getKey(bucket[bucket_slots.
size()]));
125 assert((hash2 % r.tab1.size()) == hash1);
126 auto slot = (hash2 >> shift) % r.tab2.size();
127 if (r.tab2[slot] != UNUSED ||
contains(bucket_slots, slot)) {
130 bucket_slots.
clear();
137 r.tab1[hash1] = shift | 0x80;
138 for (
auto i :
xrange(bSize)) {
139 r.tab2[bucket_slots[i]] = bucket[i];