41 using Value =
decltype(InvalidValue);
44 : hasher(hasher_), equality(equality_)
61 grow(std::bit_ceil(2 * n));
66 return (mask + 1) / 2;
69 [[nodiscard]]
size_t size()
const
73 [[nodiscard]]
bool empty()
const
78 template<
typename Value2>
81 auto h = hash(val) & mask;
83 while (table[h] != InvalidValue) {
84 if (equal(table[h], val)) {
92 table[h] = std::forward<Value2>(val);
94 growAndInsert(std::forward<Value2>(val));
100 template<
typename Value2>
103 auto pos1 = locate(val);
104 if (pos1 ==
size_t(-1))
return false;
107 auto mustMove = [&](
size_t p1,
size_t p2,
size_t p3) {
108 p2 = (p2 - p1 - 1) & mask;
109 p3 = (
p3 - p1 - 1) & mask;
114 pos2 = (pos2 + 1) & mask;
115 if (table[pos2] == InvalidValue) {
117 table[pos1] = InvalidValue;
123 auto pos3 = hash(table[pos2] & mask);
124 if (mustMove(pos1, pos2, pos3)) {
128 table[pos1] = std::move(table[pos2]);
134 template<
typename Value2>
135 [[nodiscard]] Value*
find(
const Value2& val)
const
137 auto h = locate(val);
138 return (h ==
size_t(-1)) ? nullptr : &table[h];
141 template<
typename Value2>
142 [[nodiscard]]
bool contains(
const Value2& val)
const
144 return locate(val) != size_t(-1);
148 template<
typename Value2>
149 [[nodiscard]]
size_t hash(
const Value2& val)
const
154 template<
typename Value2>
155 [[nodiscard]]
bool equal(
const Value& val,
const Value2& val2)
const
157 return equality(val, val2);
160 template<
typename Value2>
161 [[nodiscard]]
size_t locate(
const Value2& val)
const
164 auto h = hash(val) & mask;
165 while (table[h] != InvalidValue) {
166 if (equal(table[h], val)) {
176 template<
typename Value2>
177 void insertValue(Value2&& val, Value* tab,
size_t msk)
179 auto h = hash(val) & msk;
180 while (tab[h] != InvalidValue) {
183 tab[h] = std::forward<Value2>(val);
186 void grow(
size_t newSize)
188 assert(std::has_single_bit(newSize));
189 assert(newSize > (mask + 1));
191 auto* newTable =
static_cast<Value*
>(malloc(newSize *
sizeof(Value)));
192 std::uninitialized_fill(newTable, newTable + newSize, InvalidValue);
194 size_t newMask = newSize - 1;
196 for (
size_t i = 0; i <= mask; ++i) {
197 if (table[i] != InvalidValue) {
198 insertValue(std::move(table[i]), newTable, newMask);
205 mask =
static_cast<decltype(mask)
>(newMask);
208 template<
typename Value2>
209 void growAndInsert(Value2&& val)
211 grow(std::max<size_t>(4, 2 * (mask + 1)));
212 insertValue(std::forward<Value2>(val), table, mask);
217 if (!std::is_trivially_destructible_v<Value> && table) {
218 for (
size_t i = 0; i <= mask; ++i) {
226 [[no_unique_address]] Hasher hasher;
227 [[no_unique_address]] Equality equality;
228 Value* table =
nullptr;
230 uint32_t num_elems = 0;
mat3 p3(vec3(1, 2, 3), vec3(4, 5, 6), vec3(7, 0, 9))