Branch data Line data Source code
1 : : #include "backend/WasmAlgo.hpp"
2 : :
3 : : #include <mutable/catalog/Catalog.hpp>
4 : : #include <numeric>
5 : :
6 : :
7 : : using namespace m;
8 : : using namespace m::wasm;
9 : :
10 : :
11 : : namespace {
12 : :
13 : : namespace options {
14 : :
15 : : /** Whether there must not occur any rehashing. */
16 : : bool insist_no_rehashing = false;
17 : : /** Whether to add special case handling for sorting two elements using quicksort. */
18 : : bool special_case_quicksort_two_elements = true;
19 : : /** Whether to partition using a hard boundary, i.e. pivot element strictly splits the data. Otherwise, a soft
20 : : * boundary is used, i.e. boundary can be anywhere in the data range equal to the pivot. */
21 : : bool partition_hard_boundary = false;
22 : :
23 : : }
24 : :
25 : : __attribute__((constructor(201)))
26 : 1 : static void add_wasm_algo_args()
27 : : {
28 : 1 : Catalog &C = Catalog::Get();
29 : :
30 : : /*----- Command-line arguments -----*/
31 : 1 : C.arg_parser().add<bool>(
32 : : /* group= */ "Wasm",
33 : : /* short= */ nullptr,
34 : : /* long= */ "--insist-no-rehashing",
35 : : /* description= */ "insist that no rehashing occurs",
36 : 0 : /* callback= */ [](bool){ options::insist_no_rehashing = true; }
37 : : );
38 : 1 : C.arg_parser().add<bool>(
39 : : /* group= */ "Wasm",
40 : : /* short= */ nullptr,
41 : : /* long= */ "--no-special-case-quicksort-two-elements",
42 : : /* description= */ "disable special case handling for sorting two elements using quicksort",
43 : 0 : /* callback= */ [](bool){ options::special_case_quicksort_two_elements = false; }
44 : : );
45 : 1 : C.arg_parser().add<bool>(
46 : : /* group= */ "Wasm",
47 : : /* short= */ nullptr,
48 : : /* long= */ "--partition-hard-boundary",
49 : : /* description= */ "partition data using a hard boundary, i.e. pivot element strictly splits the data; "
50 : : "otherwise, a soft boundary is used, i.e. boundary can be anywhere in the data range equal "
51 : : "to the pivot",
52 : 0 : /* callback= */ [](bool){ options::partition_hard_boundary = true; }
53 : : );
54 : 1 : }
55 : :
56 : : }
57 : :
58 : :
59 : : /*======================================================================================================================
60 : : * sorting
61 : : *====================================================================================================================*/
62 : :
63 : : template<bool CmpPredicated, bool IsGlobal>
64 : 0 : void m::wasm::quicksort(Buffer<IsGlobal> &buffer, const std::vector<SortingOperator::order_type> &order)
65 : : {
66 : : static_assert(IsGlobal, "quicksort on local buffers is not yet supported");
67 : 0 :
68 : : /*----- Create load and swap proxies for buffer. -----*/
69 : 0 : auto load = buffer.create_load_proxy();
70 : 0 : auto swap = buffer.create_swap_proxy();
71 : :
72 : : /*---- Create branchless binary partition function. -----*/
73 : : /* Receives the ID of the first tuple to partition, the past-the-end ID to partition, and an environment
74 : 1 : * containing the entries of the pivot element needed for ordering as parameters (note that the pivot element
75 : : * must not be contained in the interval [begin, end[ since these entries may be swapped which would render the
76 : : * given environment invalid). Returns ID of partition boundary s.t. all elements before this boundary are smaller
77 : : * than or equal to the pivot element and all elements after or equal this boundary are greater than (or equal to
78 : : * iff `options::partition_hard_boundary` is unset) the pivot element. */
79 : 0 : auto partition = [&](U32x1 _begin, U32x1 _end, const Environment &env_pivot) -> U32x1 {
80 [ # # # # ]: 0 : Var<U32x1> begin(_begin), end(_end);
81 : :
82 [ # # # # : 0 : Wasm_insist(begin < end);
# # # # #
# # # ]
83 : :
84 [ # # # # ]: 0 : U32x1 last = end - 1U;
85 : :
86 [ # # # # : 0 : DO_WHILE(begin < end) {
# # # # #
# # # ]
87 : : /*----- Load entire begin tuple. -----*/
88 [ # # # # ]: 0 : auto env_begin = [&](){
89 : 0 : auto S = CodeGenContext::Get().scoped_environment();
90 [ # # # # : 0 : load(begin);
# # # # ]
91 [ # # # # ]: 0 : return S.extract();
92 : 0 : }();
93 : :
94 : : /*----- Load entire last tuple. -----*/
95 [ # # # # ]: 0 : auto env_last = [&](){
96 : 0 : auto S = CodeGenContext::Get().scoped_environment();
97 [ # # # # : 0 : load(last.clone());
# # # # ]
98 [ # # # # ]: 0 : return S.extract();
99 : 0 : }();
100 : :
101 : : /*----- Swap entire begin and last tuples. -----*/
102 [ # # # # : 0 : swap(begin, last, env_begin, env_last);
# # # # #
# # # ]
103 : : /* Note that environments are now also swapped, i.e. `env_begin` contains still the values of the former
104 : : * begin tuple which is now located at ID `last` and vice versa, except for `NChar`s since they are only
105 : : * pointers to the actual values, i.e. `env_begin` contains still the addresses of the former begin tuple
106 : : * where now the values of the last tuple are stored and vice versa. */
107 : :
108 : : /*----- Adapt environments to match their previous meanings before swapping tuples. -----*/
109 [ # # # # : 0 : for (auto &e : buffer.schema()) {
# # # # #
# # # # #
# # ]
110 [ # # # # : 0 : M_insist(env_begin.template is<NChar>(e.id) == env_last.template is<NChar>(e.id),
# # # # #
# # # ]
111 : : "either both or none of the entries must be `NChar`s");
112 [ # # # # : 0 : if (not env_begin.template is<NChar>(e.id)) {
# # # # ]
113 : : /* Swap entry in environments. */
114 [ # # # # ]: 0 : auto tmp = env_begin.extract(e.id);
115 [ # # # # : 0 : env_begin.add(e.id, env_last.extract(e.id));
# # # # #
# # # ]
116 [ # # # # : 0 : env_last.add(e.id, std::move(tmp));
# # # # ]
117 : 0 : }
118 : : }
119 : :
120 : : /*----- Compare begin and last tuples to pivot element and advance cursors respectively. -----*/
121 : : Boolx1 begin_cmp_pivot =
122 [ # # # # : 0 : options::partition_hard_boundary ? compare<CmpPredicated>(env_begin, env_pivot, order) < 0
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
123 [ # # # # : 0 : : compare<CmpPredicated>(env_begin, env_pivot, order) <= 0;
# # # # ]
124 [ # # # # : 0 : Boolx1 last_ge_pivot = compare<CmpPredicated>(env_last, env_pivot, order) >= 0;
# # # # ]
125 : :
126 [ # # # # : 0 : begin += begin_cmp_pivot.to<uint32_t>();
# # # # ]
127 [ # # # # : 0 : end -= last_ge_pivot.to<uint32_t>();
# # # # ]
128 : 0 : }
129 : :
130 [ # # # # ]: 0 : return begin;
131 : 0 : };
132 : :
133 : : /*---- Create quicksort function. -----*/
134 : : /* Receives the ID of the first tuple to sort and the past-the-end ID to sort. */
135 [ # # # # : 0 : FUNCTION(quicksort, void(uint32_t, uint32_t))
# # # # #
# # # ]
136 : : {
137 [ # # # # : 0 : auto S = CodeGenContext::Get().scoped_environment(); // create scoped environment
# # # # ]
138 : :
139 [ # # # # ]: 0 : buffer.setup_base_address(); // to access base address during loading and swapping as local
140 : :
141 [ # # # # ]: 0 : const auto begin = PARAMETER(0); // first ID to sort
142 [ # # # # ]: 0 : auto end = PARAMETER(1); // past-the-end ID to sort
143 [ # # # # : 0 : Wasm_insist(begin <= end);
# # # # #
# # # ]
144 : :
145 [ # # # # ]: 0 : U32x1 last = end - 1U;
146 : :
147 [ # # # # : 0 : Boolx1 cmp = options::special_case_quicksort_two_elements ? end - begin > 2U : end - begin >= 2U;
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
148 [ # # # # : 0 : WHILE(cmp) {
# # # # #
# # # ]
149 [ # # # # : 0 : Var<U32x1> mid((begin + end) >> 1U); // (begin + end) / 2
# # # # #
# # # ]
150 : :
151 : : /*----- Load entire begin tuple. -----*/
152 [ # # # # ]: 0 : auto env_begin = [&](){
153 : 0 : auto S = CodeGenContext::Get().scoped_environment();
154 [ # # # # : 0 : load(begin);
# # # # ]
155 [ # # # # ]: 0 : return S.extract();
156 : 0 : }();
157 : :
158 : : /*----- Load entire mid tuple. -----*/
159 [ # # # # ]: 0 : auto env_mid = [&](){
160 : 0 : auto S = CodeGenContext::Get().scoped_environment();
161 [ # # # # : 0 : load(mid);
# # # # ]
162 [ # # # # ]: 0 : return S.extract();
163 : 0 : }();
164 : :
165 : : /*----- Load entire last tuple. -----*/
166 [ # # # # ]: 0 : auto env_last = [&](){
167 : 0 : auto S = CodeGenContext::Get().scoped_environment();
168 [ # # # # : 0 : load(last.clone());
# # # # ]
169 [ # # # # ]: 0 : return S.extract();
170 : 0 : }();
171 : :
172 : : /*----- Swap pivot (median of three) to begin. -----.*/
173 [ # # # # : 0 : Boolx1 begin_le_mid = compare<CmpPredicated>(env_begin, env_mid, order) <= 0;
# # # # ]
174 [ # # # # : 0 : Boolx1 begin_le_last = compare<CmpPredicated>(env_begin, env_last, order) <= 0;
# # # # ]
175 [ # # # # : 0 : Boolx1 mid_le_last = compare<CmpPredicated>(env_mid, env_last, order) <= 0;
# # # # ]
176 [ # # # # : 0 : IF (begin_le_mid) {
# # # # ]
177 [ # # # # : 0 : IF (begin_le_last.clone()) {
# # # # ]
178 [ # # # # : 0 : IF (mid_le_last.clone()) {
# # # # ]
179 [ # # # # : 0 : swap(begin, mid, env_begin, env_mid); // [begin, mid, last]
# # # # ]
180 [ # # # # ]: 0 : } ELSE {
181 [ # # # # : 0 : swap(begin, last.clone(), env_begin, env_last); // [begin, last, mid]
# # # # ]
182 : 0 : };
183 : 0 : }; // else [last, begin, mid]
184 [ # # # # ]: 0 : } ELSE {
185 [ # # # # ]: 0 : IF (mid_le_last) {
186 [ # # # # : 0 : IF (not begin_le_last) {
# # # # ]
187 [ # # # # : 0 : swap(begin, last.clone(), env_begin, env_last); // [mid, last, begin]
# # # # ]
188 : 0 : }; // else [mid, begin, last]
189 [ # # # # ]: 0 : } ELSE {
190 [ # # # # : 0 : swap(begin, mid, env_begin, env_mid); // [last, mid, begin]
# # # # ]
191 : 0 : };
192 : 0 : };
193 : :
194 : : /*----- Load entire pivot tuple. Must be loaded again as begin tuple may be swapped above. -----*/
195 [ # # # # ]: 0 : U32x1 pivot = begin; // use begin as pivot
196 [ # # # # ]: 0 : auto env_pivot = [&](){
197 : 0 : auto S = CodeGenContext::Get().scoped_environment();
198 [ # # # # : 0 : load(pivot.clone());
# # # # ]
199 [ # # # # ]: 0 : return S.extract();
200 : 0 : }();
201 : :
202 : : /*----- Partition range [begin + 1, end[ using pivot. -----*/
203 [ # # # # : 0 : mid = partition(begin + 1U, end, env_pivot);
# # # # #
# # # # #
# # ]
204 [ # # # # : 0 : swap(pivot, mid - 1U, env_pivot); // patch mid
# # # # #
# # # ]
205 : :
206 : : /*----- Recurse right partition, if necessary. -----*/
207 [ # # # # : 0 : IF (end - mid >= 2U) {
# # # # #
# # # # #
# # ]
208 : 0 : quicksort(mid, end);
209 : 0 : };
210 : :
211 : : /*----- Update end pointer. -----*/
212 [ # # # # : 0 : end = mid - 1U;
# # # # ]
213 : 0 : }
214 : :
215 [ # # # # ]: 0 : if (options::special_case_quicksort_two_elements) {
216 [ # # # # : 0 : IF (end - begin == 2U) {
# # # # #
# # # # #
# # ]
217 : : /*----- Load entire begin tuple. -----*/
218 : 0 : auto env_begin = [&](){
219 : 0 : auto S = CodeGenContext::Get().scoped_environment();
220 [ # # # # : 0 : load(begin);
# # # # ]
221 [ # # # # ]: 0 : return S.extract();
222 : 0 : }();
223 : :
224 : : /*----- Load entire last tuple. -----*/
225 [ # # # # ]: 0 : auto env_last = [&](){
226 : 0 : auto S = CodeGenContext::Get().scoped_environment();
227 [ # # # # : 0 : load(last.clone());
# # # # ]
228 [ # # # # ]: 0 : return S.extract();
229 : 0 : }();
230 : :
231 : : /*----- Swap begin and last if they are not yet sorted. -----.*/
232 [ # # # # : 0 : Boolx1 begin_gt_last = compare<CmpPredicated>(env_begin, env_last, order) > 0;
# # # # ]
233 [ # # # # : 0 : IF (begin_gt_last) {
# # # # ]
234 [ # # # # : 0 : swap(begin, last, env_begin, env_last);
# # # # ]
235 : 0 : };
236 : 0 : };
237 : 0 : } else {
238 [ # # # # ]: 0 : last.discard(); // since it was always cloned
239 : : }
240 : :
241 [ # # # # ]: 0 : buffer.teardown_base_address();
242 : 0 : }
243 [ # # # # : 0 : quicksort(0, buffer.size());
# # # # ]
244 : 0 : }
245 : :
246 : : // explicit instantiations to prevent linker errors
247 : : template void m::wasm::quicksort<false>(GlobalBuffer&, const std::vector<SortingOperator::order_type>&);
248 : : template void m::wasm::quicksort<true>(GlobalBuffer&, const std::vector<SortingOperator::order_type>&);
249 : :
250 : :
251 : : /*======================================================================================================================
252 : : * hashing
253 : : *====================================================================================================================*/
254 : :
255 : : /*----- helper functions ---------------------------------------------------------------------------------------------*/
256 : :
257 : : template<typename T>
258 : : requires unsigned_integral<T>
259 : : U64x1 reinterpret_to_U64(m::wasm::PrimitiveExpr<T> value) { return value; }
260 : :
261 : : template<typename T>
262 : : requires signed_integral<T>
263 [ # # # # : 0 : U64x1 reinterpret_to_U64(m::wasm::PrimitiveExpr<T> value) { return value.make_unsigned(); }
# # ]
264 : :
265 : : template<typename T>
266 : : requires std::floating_point<T> and (sizeof(T) == 4)
267 [ # # # # ]: 0 : U64x1 reinterpret_to_U64(m::wasm::PrimitiveExpr<T> value) { return value.template reinterpret<int32_t>().make_unsigned(); }
268 : :
269 : : template<typename T>
270 : : requires std::floating_point<T> and (sizeof(T) == 8)
271 [ # # ]: 0 : U64x1 reinterpret_to_U64(m::wasm::PrimitiveExpr<T> value) { return value.template reinterpret<int64_t>().make_unsigned(); }
272 : :
273 : : template<typename T>
274 : : requires std::same_as<T, bool>
275 : 0 : U64x1 reinterpret_to_U64(m::wasm::PrimitiveExpr<T> value) { return value.template to<uint64_t>(); }
276 : :
277 : :
278 : : /*----- bit mix functions --------------------------------------------------------------------------------------------*/
279 : :
280 : 0 : U64x1 m::wasm::murmur3_bit_mix(U64x1 bits)
281 : : {
282 : : /* Taken from https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp by Austin Appleby. We use the
283 : : * optimized constants found by David Stafford, in particular the values for `Mix01`, as reported at
284 : : * http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html. */
285 : 0 : Var<U64x1> res(bits);
286 [ # # # # ]: 0 : res ^= res >> uint64_t(31);
287 [ # # ]: 0 : res *= uint64_t(0x7fb5d329728ea185UL);
288 [ # # # # ]: 0 : res ^= res >> uint64_t(27);
289 [ # # ]: 0 : res *= uint64_t(0x81dadef4bc2dd44dUL);
290 [ # # # # ]: 0 : res ^= res >> uint64_t(33);
291 [ # # ]: 0 : return res;
292 : 0 : }
293 : :
294 : :
295 : : /*----- hash functions -----------------------------------------------------------------------------------------------*/
296 : :
297 : 0 : U64x1 m::wasm::fnv_1a(Ptr<U8x1> bytes, U32x1 num_bytes)
298 : : {
299 [ # # # # : 0 : Wasm_insist(not bytes.clone().is_nullptr(), "cannot compute hash of nullptr");
# # ]
300 : :
301 : 0 : Var<U64x1> h(0xcbf29ce484222325UL);
302 : :
303 [ # # # # ]: 0 : Var<Ptr<U8x1>> ptr(bytes.clone());
304 [ # # # # : 0 : WHILE (ptr != bytes + num_bytes.make_signed() and U8x1(*ptr).to<bool>()) {
# # # # #
# # # # #
# # # # #
# ]
305 [ # # # # ]: 0 : h ^= *ptr;
306 [ # # ]: 0 : h *= uint64_t(0x100000001b3UL);
307 [ # # ]: 0 : ptr += 1;
308 : : }
309 : :
310 [ # # ]: 0 : return h;
311 : 0 : }
312 : :
313 : 0 : U64x1 m::wasm::str_hash(NChar _str)
314 : : {
315 : 0 : Var<U64x1> h(0); // always set here
316 : :
317 [ # # # # : 0 : IF (_str.clone().is_null()) {
# # ]
318 : 0 : h = uint64_t(1UL << 63);
319 : 0 : } ELSE {
320 [ # # ]: 0 : if (_str.length() <= 8) {
321 : : /*----- If the string fits in a single U64x1, combine all characters and bit mix. -----*/
322 [ # # ]: 0 : const Var<Ptr<Charx1>> str(_str.val());
323 [ # # ]: 0 : for (int32_t i = 0; i != _str.length(); ++i) {
324 [ # # ]: 0 : h <<= 8U;
325 [ # # # # : 0 : Charx1 c = *(str + i);
# # ]
326 [ # # # # ]: 0 : h |= c.to<uint64_t>();
327 : 0 : }
328 [ # # # # : 0 : h = murmur3_bit_mix(h);
# # ]
329 : 0 : } else {
330 : : /*----- Compute FNV-1a hash of string. -----*/
331 [ # # # # : 0 : h = fnv_1a(_str.to<void*>().to<uint8_t*>(), U32x1(_str.length()));
# # # # ]
332 : : }
333 : 0 : };
334 : :
335 [ # # ]: 0 : return h;
336 : 0 : }
337 : :
338 : 0 : U64x1 m::wasm::murmur3_64a_hash(std::vector<std::pair<const Type*, SQL_t>> values)
339 : : {
340 : : /* Inspired by https://github.com/aappleby/smhasher/blob/master/src/MurmurHash3.cpp by Austin Appleby. We use
341 : : * constants from MurmurHash2_64 as reported on https://sites.google.com/site/murmurhash/. */
342 : 0 : M_insist(values.size() != 0, "cannot compute hash of an empty sequence of values");
343 : :
344 : : /*----- Handle a single value. -----*/
345 [ # # ]: 0 : if (values.size() == 1) {
346 : 0 : return std::visit(overloaded {
347 [ # # # # : 0 : [&]<typename T>(Expr<T> val) -> U64x1 { return murmur3_bit_mix(val.hash()); },
# # # # #
# # # #
# ]
348 [ # # ]: 0 : [&](NChar val) -> U64x1 { return str_hash(val); },
349 : 0 : [](auto) -> U64x1 { M_unreachable("SIMDfication currently not supported"); },
350 : 0 : [](std::monostate) -> U64x1 { M_unreachable("invalid variant"); }
351 : 0 : }, values.front().second);
352 : : }
353 : :
354 : : /*----- Compute total size in bits of all values including NULL bits or rather nullptr. -----*/
355 : 0 : uint64_t total_size_in_bits = 0;
356 [ # # ]: 0 : for (const auto &p : values) {
357 : 0 : std::visit(overloaded {
358 : 0 : [&]<typename T>(const Expr<T> &val) -> void { total_size_in_bits += p.first->size(); },
359 : 0 : [&](const NChar &val) -> void { total_size_in_bits += 8 * val.length(); },
360 : 0 : [](auto&) -> void { M_unreachable("SIMDfication currently not supported"); },
361 : : [](std::monostate&) -> void { M_unreachable("invalid variant"); }
362 : 0 : }, p.second);
363 : : }
364 : :
365 : : /*----- If all values can be combined into a single U64x1 value, combine all values and bit mix. -----*/
366 [ # # ]: 0 : if (total_size_in_bits <= 64) {
367 : 0 : Var<U64x1> h(0);
368 [ # # ]: 0 : for (auto &p : values) {
369 [ # # # # ]: 0 : std::visit(overloaded {
370 : 0 : [&]<typename T>(Expr<T> _val) -> void {
371 : 0 : h <<= p.first->size();
372 [ # # # # : 0 : if (_val.can_be_null()) {
# # # # #
# # # #
# ]
373 : 0 : auto [val, is_null] = _val.split();
374 : : #if 0
375 : : IF (not is_null) {
376 : : h |= reinterpret_to_U64(val); // add reinterpreted value
377 : : };
378 : : #else
379 [ # # # # : 0 : h |= (~uint64_t(0) + is_null.template to<uint64_t>()) bitand reinterpret_to_U64(val);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
380 : : #endif
381 : 0 : } else {
382 : 0 : auto val = _val.insist_not_null();
383 [ # # # # : 0 : h |= reinterpret_to_U64(val); // add reinterpreted value
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
384 : 0 : }
385 : 0 : },
386 : 0 : [&](NChar _val) -> void {
387 [ # # # # ]: 0 : IF (_val.clone().is_null()) {
388 : 0 : uint64_t len_in_bits = 8 * _val.length();
389 : 0 : h <<= len_in_bits;
390 : 0 : } ELSE {
391 [ # # ]: 0 : const Var<Ptr<Charx1>> val(_val.val());
392 [ # # ]: 0 : for (int32_t i = 0; i != _val.length(); ++i) {
393 [ # # ]: 0 : h <<= 8U;
394 [ # # # # : 0 : Charx1 c = *(val + i);
# # ]
395 [ # # # # ]: 0 : h |= c.to<uint64_t>(); // add reinterpreted character
396 : 0 : }
397 : 0 : };
398 : 0 : },
399 : 0 : [](auto) -> void { M_unreachable("SIMDfication currently not supported"); },
400 : 0 : [](std::monostate) -> void { M_unreachable("invalid variant"); }
401 : 0 : }, p.second);
402 : : }
403 [ # # # # ]: 0 : return murmur3_bit_mix(h);
404 : 0 : }
405 : :
406 : : /*----- Perform general Murmur3_64a. -----*/
407 : 0 : U64x1 m(0xc6a4a7935bd1e995UL);
408 [ # # ]: 0 : Var<U64x1> k; // always set before used
409 [ # # # # : 0 : Var<U64x1> h(uint64_t(values.size()) * m.clone());
# # ]
410 : :
411 [ # # ]: 0 : for (auto &p : values) {
412 [ # # # # ]: 0 : std::visit(overloaded {
413 : 0 : [&]<typename T>(Expr<T> val) -> void {
414 [ # # # # : 0 : k = val.hash();
# # # # #
# # # #
# ]
415 [ # # # # : 0 : k *= m.clone();
# # # # #
# # # #
# ]
416 [ # # # # : 0 : k = rotl(k, 47UL);
# # # # #
# # # #
# ]
417 [ # # # # : 0 : k *= m.clone();
# # # # #
# # # #
# ]
418 : 0 : h ^= k;
419 [ # # # # : 0 : h = rotl(h, 45UL);
# # # # #
# # # #
# ]
420 [ # # # # : 0 : h = h * uint64_t(5UL) + uint64_t(0xe6546b64UL);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
421 : 0 : },
422 [ # # # # ]: 0 : [&](NChar val) -> void { h ^= str_hash(val); },
423 : 0 : [](auto) -> void { M_unreachable("SIMDfication currently not supported"); },
424 : 0 : [](std::monostate) -> void { M_unreachable("invalid variant"); }
425 : 0 : }, p.second);
426 : : }
427 [ # # ]: 0 : h ^= uint64_t(values.size());
428 : :
429 [ # # ]: 0 : m.discard(); // since it was always cloned
430 : :
431 [ # # # # ]: 0 : return murmur3_bit_mix(h);
432 : 0 : }
433 : :
434 : :
435 : : /*----- hash tables --------------------------------------------------------------------------------------------------*/
436 : :
437 : : std::pair<HashTable::size_t, HashTable::size_t>
438 : 0 : HashTable::set_byte_offsets(std::vector<HashTable::offset_t> &offsets_in_bytes, const std::vector<const Type*> &types,
439 : : HashTable::offset_t initial_offset_in_bytes,
440 : : HashTable::offset_t initial_max_alignment_in_bytes)
441 : : {
442 [ # # ]: 0 : if (types.empty())
443 : 0 : return { initial_offset_in_bytes, initial_max_alignment_in_bytes };
444 : :
445 : : /*----- Collect all indices. -----*/
446 : 0 : std::size_t indices[types.size()];
447 : 0 : std::iota(indices, indices + types.size(), 0);
448 : :
449 : : /*----- Sort indices by alignment. -----*/
450 : 0 : std::stable_sort(indices, indices + types.size(), [&](std::size_t left, std::size_t right) {
451 : 0 : return types[left]->alignment() > types[right]->alignment();
452 : : });
453 : :
454 : : /*----- Compute offsets. -----*/
455 : 0 : offsets_in_bytes.resize(types.size());
456 : 0 : HashTable::offset_t current_offset_in_bytes = initial_offset_in_bytes;
457 : 0 : HashTable::offset_t max_alignment_in_bytes = initial_max_alignment_in_bytes;
458 [ # # ]: 0 : for (std::size_t idx = 0; idx != types.size(); ++idx) {
459 : 0 : const auto sorted_idx = indices[idx];
460 : 0 : offsets_in_bytes[sorted_idx] = current_offset_in_bytes;
461 : 0 : current_offset_in_bytes += (types[sorted_idx]->size() + 7) / 8;
462 : 0 : max_alignment_in_bytes =
463 : 0 : std::max<HashTable::offset_t>(max_alignment_in_bytes, (types[sorted_idx]->alignment() + 7) / 8);
464 : 0 : }
465 : :
466 : : /*----- Compute entry size with padding. -----*/
467 [ # # ]: 0 : if (const auto rem = current_offset_in_bytes % max_alignment_in_bytes; rem)
468 : 0 : current_offset_in_bytes += max_alignment_in_bytes - rem;
469 : 0 : return { current_offset_in_bytes, max_alignment_in_bytes };
470 : 0 : }
471 : :
472 : :
473 : : /*----- chained hash tables ------------------------------------------------------------------------------------------*/
474 : :
475 : : template<bool IsGlobal>
476 : 0 : ChainedHashTable<IsGlobal>::ChainedHashTable(const Schema &schema, std::vector<HashTable::index_t> key_indices,
477 : : uint32_t initial_capacity)
478 [ # # # # ]: 0 : : HashTable(schema, std::move(key_indices))
479 : 0 : {
480 : 0 : std::vector<const Type*> types;
481 : 0 : bool has_nullable = false;
482 : :
483 : : /*----- Add pointer to next entry in linked collision list. -----*/
484 [ # # # # : 0 : types.push_back(Type::Get_Integer(Type::TY_Vector, sizeof(uint32_t)));
# # # # #
# # # ]
485 : :
486 : : /*----- Add schema types. -----*/
487 [ # # # # : 0 : for (auto &e : schema_.get()) {
# # # # #
# # # ]
488 [ # # # # ]: 0 : types.push_back(e.type);
489 [ # # # # ]: 0 : has_nullable |= e.nullable();
490 : : }
491 : :
492 [ # # # # ]: 0 : if (has_nullable) {
493 : : /*----- Add type for NULL bitmap. Pointer to next entry in collision list cannot be NULL. -----*/
494 [ # # # # : 0 : types.push_back(Type::Get_Bitmap(Type::TY_Vector, types.size() - 1));
# # # # #
# # # ]
495 : 0 : }
496 : :
497 : : /*----- Compute entry offsets and set entry size and alignment requirement. -----*/
498 : 0 : std::vector<HashTable::offset_t> offsets;
499 [ # # # # ]: 0 : std::tie(entry_size_in_bytes_, entry_max_alignment_in_bytes_) = set_byte_offsets(offsets, types);
500 : :
501 : : /*----- Set offset for pointer to next entry in collision list. -----*/
502 : 0 : ptr_offset_in_bytes_ = offsets.front();
503 : :
504 [ # # # # ]: 0 : if (has_nullable) {
505 : : /*----- Set offset for NULL bitmap and remove it from `offsets`. -----*/
506 : 0 : null_bitmap_offset_in_bytes_ = offsets.back();
507 : 0 : offsets.pop_back();
508 : 0 : }
509 : :
510 : : /*----- Set entry offset. Exclude offset for pointer to next entry in collision list. -----*/
511 [ # # # # : 0 : entry_offsets_in_bytes_ = std::vector<HashTable::offset_t>(std::next(offsets.begin()), offsets.end());
# # # # ]
512 : :
513 : : /*----- Initialize capacity and absolute high watermark. -----*/
514 [ # # # # ]: 0 : const auto capacity_init = ceil_to_pow_2(initial_capacity);
515 : 0 : const auto mask_init = capacity_init - 1U;
516 : 0 : const auto high_watermark_absolute_init = capacity_init;
517 : : if constexpr (IsGlobal) {
518 [ # # ]: 0 : storage_.address_.init(0), // init with nullptr
519 [ # # ]: 0 : storage_.mask_.init(mask_init);
520 [ # # ]: 0 : storage_.high_watermark_absolute_.init(high_watermark_absolute_init);
521 : : } else {
522 [ # # ]: 0 : mask_.emplace(mask_init);
523 [ # # ]: 0 : high_watermark_absolute_.emplace(high_watermark_absolute_init);
524 : : }
525 : 0 : }
526 : :
527 : : template<bool IsGlobal>
528 : 0 : ChainedHashTable<IsGlobal>::~ChainedHashTable()
529 : 0 : {
530 : : if constexpr (IsGlobal) { // free memory of global hash table when object is destroyed and no use may occur later
531 : : /*----- Free collision list entries. -----*/
532 [ # # ]: 0 : Var<Ptr<void>> it(storage_.address_);
533 [ # # # # : 0 : const Var<Ptr<void>> end(storage_.address_ + ((storage_.mask_ + 1U) * uint32_t(sizeof(uint32_t))).make_signed());
# # # # #
# ]
534 [ # # # # : 0 : WHILE (it != end) {
# # # # ]
535 [ # # # # : 0 : Wasm_insist(storage_.address_ <= it and it < end, "bucket out-of-bounds");
# # # # #
# ]
536 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*it.to<uint32_t*>()));
# # # # #
# ]
537 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
# # # # #
# ]
538 [ # # ]: 0 : const Var<Ptr<void>> tmp(bucket_it);
539 [ # # # # : 0 : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # ]
540 [ # # # # : 0 : Module::Allocator().deallocate(tmp, entry_size_in_bytes_);
# # ]
541 : 0 : }
542 [ # # ]: 0 : it += int32_t(sizeof(uint32_t));
543 : 0 : }
544 : :
545 : : /*----- Free all buckets. -----*/
546 [ # # # # : 0 : Module::Allocator().deallocate(storage_.address_, (storage_.mask_ + 1U) * uint32_t(sizeof(uint32_t)));
# # # # #
# ]
547 : :
548 : : /*----- Free dummy entries. -----*/
549 [ # # # # : 0 : for (auto it = dummy_allocations_.rbegin(); it != dummy_allocations_.rend(); ++it)
# # ]
550 [ # # # # : 0 : Module::Allocator().deallocate(it->first, it->second);
# # # # #
# # # ]
551 [ # # ]: 0 : if (predication_dummy_) {
552 : : #if 1
553 [ # # # # : 0 : Wasm_insist(Ptr<void>(*predication_dummy_->template to<uint32_t*>()).is_nullptr(),
# # # # #
# # # #
# ]
554 : : "predication dummy must always contain an empty collision list");
555 : : #else
556 : : Var<Ptr<void>> bucket_it(Ptr<void>(*predication_dummy_->template to<uint32_t*>()));
557 : : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
558 : : const Var<Ptr<void>> tmp(bucket_it);
559 : : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).to<uint32_t*>());
560 : : Module::Allocator().deallocate(tmp, entry_size_in_bytes_);
561 : : }
562 : : #endif
563 [ # # # # : 0 : Module::Allocator().deallocate(*predication_dummy_, sizeof(uint32_t));
# # ]
564 : 0 : }
565 : 0 : }
566 : 0 : }
567 : :
568 : : template<bool IsGlobal>
569 : 0 : void ChainedHashTable<IsGlobal>::setup()
570 : : {
571 : 0 : M_insist(not address_, "must not call `setup()` twice");
572 : 0 : M_insist(not num_entries_, "must not call `setup()` twice");
573 : :
574 : : /*----- Create local variables. -----*/
575 : 0 : address_.emplace();
576 : 0 : num_entries_.emplace();
577 : : if constexpr (IsGlobal) {
578 : 0 : M_insist(not mask_, "must not call `setup()` twice");
579 : 0 : M_insist(not high_watermark_absolute_, "must not call `setup()` twice");
580 : 0 : mask_.emplace();
581 : 0 : high_watermark_absolute_.emplace();
582 : : } else {
583 : 0 : M_insist(bool(mask_)); // already initialized in c'tor
584 : 0 : M_insist(bool(high_watermark_absolute_)); // already initialized in c'tor
585 : : }
586 : :
587 [ + - ]: 1 : /*----- For global hash tables, read values from global backups into local variables. -----*/
588 : : if constexpr (IsGlobal) {
589 [ + - ]: 1 : /* omit assigning address here as it will always be set below */
590 [ + - ]: 1 : *mask_ = storage_.mask_;
591 : 0 : *num_entries_ = storage_.num_entries_;
592 : 0 : *high_watermark_absolute_ = storage_.high_watermark_absolute_;
593 : : }
594 : :
595 : : if constexpr (IsGlobal) {
596 [ # # ]: 0 : IF (storage_.address_.is_nullptr()) { // hash table not yet allocated
597 : : /*----- Allocate memory for initial capacity. -----*/
598 [ # # # # ]: 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), sizeof(uint32_t));
599 : :
600 : : /*----- Clear initial hash table. -----*/
601 : 0 : clear();
602 : 0 : } ELSE {
603 : 0 : *address_ = storage_.address_;
604 : 0 : };
605 : : } else {
606 : : /*----- Allocate memory for initial capacity. -----*/
607 [ # # # # ]: 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), sizeof(uint32_t));
608 : :
609 : : /*----- Clear initial hash table. -----*/
610 : 0 : clear();
611 : : }
612 : 0 : }
613 : :
614 : : template<bool IsGlobal>
615 : 0 : void ChainedHashTable<IsGlobal>::teardown()
616 : : {
617 : 0 : M_insist(bool(address_), "must call `setup()` before");
618 : 0 : M_insist(bool(mask_), "must call `setup()` before");
619 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
620 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
621 : :
622 : : if constexpr (not IsGlobal) { // free memory of local hash table when user calls teardown method
623 : : /*----- Free collision list entries. -----*/
624 [ # # ]: 0 : Var<Ptr<void>> it(begin());
625 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# ]
626 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "bucket out-of-bounds");
# # # # #
# # # #
# ]
627 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*it.to<uint32_t*>()));
# # # # #
# ]
628 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
# # # # #
# ]
629 [ # # ]: 0 : const Var<Ptr<void>> tmp(bucket_it);
630 [ # # # # : 0 : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # ]
631 [ # # # # : 0 : Module::Allocator().deallocate(tmp, entry_size_in_bytes_);
# # ]
632 : 0 : }
633 [ # # ]: 0 : it += int32_t(sizeof(uint32_t));
634 : 0 : }
635 : :
636 : : /*----- Free all buckets. -----*/
637 [ # # # # : 0 : Module::Allocator().deallocate(*address_, size_in_bytes());
# # # # ]
638 : :
639 : : /*----- Free dummy entries. -----*/
640 [ # # # # : 0 : for (auto it = dummy_allocations_.rbegin(); it != dummy_allocations_.rend(); ++it)
# # ]
641 [ # # # # : 0 : Module::Allocator().deallocate(it->first, it->second);
# # # # #
# # # ]
642 [ # # ]: 0 : if (predication_dummy_) {
643 : 0 : #if 1
644 [ # # # # : 0 : Wasm_insist(Ptr<void>(*predication_dummy_->template to<uint32_t*>()).is_nullptr(),
# # # # #
# # # #
# ]
645 : : "predication dummy must always contain an empty collision list");
646 : : #else
647 : : Var<Ptr<void>> bucket_it(Ptr<void>(*predication_dummy_->template to<uint32_t*>()));
648 : : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
649 : : const Var<Ptr<void>> tmp(bucket_it);
650 : : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).to<uint32_t*>());
651 : : Module::Allocator().deallocate(tmp, entry_size_in_bytes_);
652 : : }
653 : : #endif
654 [ # # # # : 0 : Module::Allocator().deallocate(*predication_dummy_, sizeof(uint32_t));
# # ]
655 : 0 : }
656 : 0 : }
657 [ # # # # ]: 0 :
658 : : /*----- For global hash tables, write values from local variables into global backups. -----*/
659 : : if constexpr (IsGlobal) {
660 : 0 : storage_.address_ = *address_;
661 : 0 : storage_.mask_ = *mask_;
662 : 0 : storage_.num_entries_ = *num_entries_;
663 : 0 : storage_.high_watermark_absolute_ = *high_watermark_absolute_;
664 : : }
665 : :
666 : : /*----- Destroy local variables. -----*/
667 : 0 : address_.reset();
668 : 0 : mask_.reset();
669 : 0 : num_entries_.reset();
670 : 0 : high_watermark_absolute_.reset();
671 : 0 : }
672 : :
673 : : template<bool IsGlobal>
674 : 0 : void ChainedHashTable<IsGlobal>::clear()
675 : : {
676 [ # # # # ]: 0 : Var<Ptr<void>> it(begin());
677 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# # # # #
# # # # #
# ]
678 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "entry out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
679 : : #if 0
680 : : Var<Ptr<void>> bucket_it(Ptr<void>(*it.to<uint32_t*>())); // XXX: may be random address
681 : : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
682 : : const Var<Ptr<void>> tmp(bucket_it);
683 : : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).to<uint32_t*>());
684 : : Module::Allocator().deallocate(tmp, entry_size_in_bytes_); // free collision list entry
685 : : }
686 : : #endif
687 [ # # # # : 0 : *(it + ptr_offset_in_bytes_).template to<uint32_t*>() = 0U; // set to nullptr
# # # # #
# # # # #
# # ]
688 [ # # # # ]: 0 : it += int32_t(sizeof(uint32_t));
689 : : }
690 : 0 : }
691 : :
692 : : template<bool IsGlobal>
693 : 0 : Ptr<void> ChainedHashTable<IsGlobal>::hash_to_bucket(std::vector<SQL_t> key) const
694 : : {
695 : 0 : M_insist(bool(mask_), "must call `setup()` before");
696 : 0 : M_insist(key.size() == key_indices_.size(),
697 : : "provided number of key elements does not match hash table's number of key indices");
698 : :
699 : : /*----- Collect types of key together with the respective value. -----*/
700 : 0 : std::vector<std::pair<const Type*, SQL_t>> values;
701 [ # # # # ]: 0 : values.reserve(key_indices_.size());
702 : 0 : auto key_it = key.begin();
703 [ # # # # ]: 0 : for (auto k : key_indices_)
704 [ # # # # : 0 : values.emplace_back(schema_.get()[k].type, std::move(*key_it++));
# # # # ]
705 : :
706 : : /*----- Compute hash of key using Murmur3_64a. -----*/
707 [ # # # # ]: 0 : U64x1 hash = murmur3_64a_hash(std::move(values));
708 : :
709 : : /*----- Compute bucket address. -----*/
710 [ # # # # : 0 : U32x1 bucket_idx = hash.to<uint32_t>() bitand *mask_; // modulo capacity
# # # # ]
711 [ # # # # : 0 : Ptr<void> bucket = begin() + (bucket_idx * uint32_t(sizeof(uint32_t))).make_signed();
# # # # #
# # # # #
# # ]
712 [ # # # # : 0 : Wasm_insist(begin() <= bucket.clone() and bucket.clone() < end(), "bucket out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
713 : 0 : return bucket;
714 [ # # # # ]: 0 : }
715 : :
716 : : template<bool IsGlobal>
717 : 0 : Ptr<void> ChainedHashTable<IsGlobal>::compute_bucket(std::vector<SQL_t> key) const
718 : : {
719 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
720 : 0 : std::optional<Boolx1> pred;
721 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # ]
722 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # ]
723 [ # # # # : 0 : pred.emplace(env.extract_predicate<_Boolx1>().is_true_and_not_null());
# # # # #
# # # ]
724 [ # # # # ]: 0 : if (not predication_dummy_)
725 [ # # # # ]: 0 : const_cast<ChainedHashTable<IsGlobal>*>(this)->create_predication_dummy();
726 : 0 : }
727 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # ]
728 : :
729 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
730 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
731 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(std::move(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # ]
732 [ # # # # ]: 0 : : hash_to_bucket(std::move(key))
733 : : );
734 : :
735 [ # # # # ]: 0 : return bucket;
736 : 0 : }
737 : :
738 : : template<bool IsGlobal>
739 : 0 : HashTable::entry_t ChainedHashTable<IsGlobal>::emplace(std::vector<SQL_t> key)
740 : : {
741 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
742 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
743 : :
744 : : /*----- If high watermark is reached, perform rehashing and update high watermark. -----*/
745 [ # # # # ]: 0 : IF (*num_entries_ == *high_watermark_absolute_) { // XXX: num_entries_ - 1U iff predication predicate is not fulfilled
746 : 0 : rehash();
747 : 0 : update_high_watermark();
748 : 0 : };
749 : :
750 [ # # # # ]: 0 : return emplace_without_rehashing(std::move(key));
751 : 0 : }
752 : :
753 : : template<bool IsGlobal>
754 : 0 : HashTable::entry_t ChainedHashTable<IsGlobal>::emplace_without_rehashing(std::vector<SQL_t> key)
755 : : {
756 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
757 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
758 : :
759 [ # # # # ]: 0 : Wasm_insist(*num_entries_ < *high_watermark_absolute_);
760 : :
761 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
762 : 0 : std::optional<Var<Boolx1>> pred;
763 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # ]
764 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # ]
765 [ # # # # : 0 : pred = env.extract_predicate<_Boolx1>().is_true_and_not_null();
# # # # #
# # # ]
766 [ # # # # ]: 0 : if (not predication_dummy_)
767 [ # # # # ]: 0 : create_predication_dummy();
768 : 0 : }
769 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # ]
770 : :
771 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
772 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
773 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(clone(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # # #
# # ]
774 [ # # # # : 0 : : hash_to_bucket(clone(key))
# # # # ]
775 : : ); // clone key since we need it again for insertion
776 : :
777 : : /*----- Allocate memory for entry. -----*/
778 [ # # # # : 0 : Var<Ptr<void>> entry = Module::Allocator().allocate(entry_size_in_bytes_, entry_max_alignment_in_bytes_);
# # # # ]
779 : :
780 : : /*----- Iff no predication is used or predicate is fulfilled, insert entry at collision list's front. -----*/
781 [ # # # # : 0 : *(entry + ptr_offset_in_bytes_).template to<uint32_t*>() = *bucket.to<uint32_t*>();
# # # # #
# # # # #
# # # # #
# # # #
# ]
782 [ # # # # : 0 : *bucket.to<uint32_t*>() = pred ? Select(*pred, entry.to<uint32_t>(), *bucket.to<uint32_t*>())
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
783 [ # # # # ]: 0 : : entry.to<uint32_t>(); // FIXME: entry memory never freed iff predicate is not fulfilled
784 : :
785 : : /*----- Update number of entries. -----*/
786 [ # # # # : 0 : *num_entries_ += pred ? pred->to<uint32_t>() : U32x1(1);
# # # # #
# # # # #
# # ]
787 : :
788 : : /*----- Insert key. -----*/
789 [ # # # # : 0 : insert_key(entry, std::move(key)); // move key at last use
# # # # ]
790 : :
791 : : /*----- Return entry handle containing all values. -----*/
792 [ # # # # : 0 : return value_entry(entry);
# # # # ]
793 : 0 : }
794 : :
795 : : template<bool IsGlobal>
796 : 0 : std::pair<HashTable::entry_t, Boolx1> ChainedHashTable<IsGlobal>::try_emplace(std::vector<SQL_t> key)
797 : : {
798 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
799 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
800 : :
801 : : /*----- If high watermark is reached, perform rehashing and update high watermark. -----*/
802 [ # # # # ]: 0 : IF (*num_entries_ == *high_watermark_absolute_) { // XXX: num_entries_ - 1U iff predication predicate is not fulfilled
803 : 0 : rehash();
804 : 0 : update_high_watermark();
805 : 0 : };
806 [ # # # # ]: 0 : Wasm_insist(*num_entries_ < *high_watermark_absolute_);
807 : :
808 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
809 : 0 : std::optional<Var<Boolx1>> pred;
810 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # ]
811 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # ]
812 [ # # # # : 0 : pred = env.extract_predicate<_Boolx1>().is_true_and_not_null();
# # # # #
# # # ]
813 [ # # # # ]: 0 : if (not predication_dummy_)
814 [ # # # # ]: 0 : create_predication_dummy();
815 : 0 : }
816 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # ]
817 : :
818 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
819 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
820 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(clone(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # # #
# # ]
821 [ # # # # : 0 : : hash_to_bucket(clone(key))
# # # # ]
822 : : ); // clone key since we need it again for insertion
823 : :
824 : : /*----- Probe collision list, abort and skip insertion if key already exists. -----*/
825 [ # # # # ]: 0 : Var<Boolx1> entry_inserted(false);
826 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*bucket.to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# ]
827 [ # # # # : 0 : BLOCK(insert_entry) {
# # # # ]
828 [ # # # # : 0 : IF (bucket_it.is_nullptr()) { // empty collision list
# # # # #
# # # ]
829 [ # # # # ]: 0 : bucket_it = bucket - ptr_offset_in_bytes_; // set bucket iterator to point to bucket's collision list front
830 [ # # # # ]: 0 : } ELSE {
831 [ # # # # ]: 0 : LOOP () {
832 [ # # # # : 0 : GOTO(equal_key(bucket_it, clone(key)), insert_entry); // clone key (see above)
# # # # #
# # # # #
# # ]
833 [ # # # # ]: 0 : const Var<Ptr<void>> next_bucket_it(
834 [ # # # # : 0 : Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>())
# # # # #
# # # # #
# # # # #
# ]
835 : : );
836 [ # # # # : 0 : BREAK(next_bucket_it.is_nullptr());
# # # # ]
837 [ # # # # ]: 0 : bucket_it = next_bucket_it;
838 [ # # # # ]: 0 : CONTINUE();
839 : 0 : }
840 : 0 : };
841 [ # # # # : 0 : Wasm_insist(Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>()).is_nullptr());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
842 [ # # # # ]: 0 : if (pred)
843 [ # # # # : 0 : Wasm_insist(*pred or bucket_it == bucket - ptr_offset_in_bytes_,
# # # # #
# # # # #
# # # # #
# ]
844 : : "predication dummy must always contain an empty collision list");
845 : :
846 : : /*----- Set flag to indicate insertion. -----*/
847 [ # # # # ]: 0 : entry_inserted = true;
848 : :
849 : : /*----- Allocate memory for entry. -----*/
850 [ # # # # : 0 : Var<Ptr<void>> entry = Module::Allocator().allocate(entry_size_in_bytes_, entry_max_alignment_in_bytes_);
# # # # ]
851 : :
852 : : /*----- Iff no predication is used or predicate is fulfilled, insert entry at the collision list's end. -----*/
853 [ # # # # : 0 : *(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>() = pred ? Select(*pred, entry.to<uint32_t>(), 0U)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
854 [ # # # # ]: 0 : : entry.to<uint32_t>(); // FIXME: entry memory never freed iff predicate is not fulfilled
855 : :
856 : : /*----- Set bucket iterator to inserted entry. -----*/
857 [ # # # # ]: 0 : bucket_it = entry;
858 : :
859 : : /*----- Update number of entries. -----*/
860 [ # # # # : 0 : *num_entries_ += pred ? pred->to<uint32_t>() : U32x1(1);
# # # # #
# # # # #
# # ]
861 : :
862 : : /*----- Insert key. -----*/
863 [ # # # # : 0 : insert_key(entry, std::move(key)); // move key at last use
# # # # ]
864 : 0 : }
865 : :
866 : : /* GOTO from above jumps here */
867 : :
868 : : /*----- Return entry handle containing all values and the flag whether an insertion was performed. -----*/
869 [ # # # # : 0 : return { value_entry(bucket_it), entry_inserted };
# # # # #
# # # ]
870 : 0 : }
871 : :
872 : : template<bool IsGlobal>
873 : 0 : std::pair<HashTable::entry_t, Boolx1> ChainedHashTable<IsGlobal>::find(std::vector<SQL_t> key, hint_t bucket_hint)
874 : : {
875 : : Ptr<void> bucket =
876 [ # # # # : 0 : bucket_hint ? *bucket_hint : compute_bucket(clone(key)); // clone key since we need it again for comparison
# # # # #
# # # # #
# # ]
877 : :
878 : : /*----- Probe collision list, abort if key already exists. -----*/
879 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*bucket.to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# ]
880 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
# # # # #
# # # # #
# # # # #
# ]
881 [ # # # # : 0 : BREAK(equal_key(bucket_it, std::move(key))); // move key at last use
# # # # #
# # # ]
882 [ # # # # : 0 : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # # #
# # # # #
# # # #
# ]
883 : : }
884 : :
885 : : /*----- Key is found iff end of collision list is not yet reached. -----*/
886 [ # # # # : 0 : Boolx1 key_found = not bucket_it.is_nullptr();
# # # # ]
887 : :
888 : : /*----- Return entry handle containing both keys and values and the flag whether key was found. -----*/
889 [ # # # # : 0 : return { value_entry(bucket_it), key_found };
# # # # #
# # # ]
890 : 0 : }
891 : :
892 : : template<bool IsGlobal>
893 : 0 : void ChainedHashTable<IsGlobal>::for_each(callback_t Pipeline) const
894 : : {
895 : : /*----- Iterate over all collision list entries and call pipeline (with entry handle argument). -----*/
896 [ # # # # ]: 0 : Var<Ptr<void>> it(begin());
897 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# # # # #
# # # # #
# ]
898 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "bucket out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
899 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*it.to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# ]
900 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
# # # # #
# # # # #
# # # # #
# ]
901 [ # # # # : 0 : Pipeline(entry(bucket_it));
# # # # #
# # # ]
902 [ # # # # : 0 : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # # #
# # # # #
# # # #
# ]
903 : : }
904 [ # # # # ]: 0 : it += int32_t(sizeof(uint32_t));
905 : 0 : }
906 : 0 : }
907 : :
908 : : template<bool IsGlobal>
909 : 0 : void ChainedHashTable<IsGlobal>::for_each_in_equal_range(std::vector<SQL_t> key, callback_t Pipeline,
910 : : bool predicated, hint_t bucket_hint) const
911 : : {
912 : : Ptr<void> bucket =
913 [ # # # # : 0 : bucket_hint ? *bucket_hint : compute_bucket(clone(key)); // clone key since we need it again for comparison
# # # # #
# # # # #
# # ]
914 : :
915 : : /*----- Iterate over collision list entries and call pipeline (with entry handle argument) on matches. -----*/
916 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*bucket.to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# ]
917 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in collision list
# # # # #
# # # # #
# # # # #
# ]
918 [ # # # # ]: 0 : if (predicated) {
919 [ # # # # : 0 : CodeGenContext::Get().env().add_predicate(equal_key(bucket_it, std::move(key)));
# # # # #
# # # # #
# # # # #
# # # #
# ]
920 [ # # # # : 0 : Pipeline(entry(bucket_it));
# # # # #
# # # ]
921 : 0 : } else {
922 [ # # # # : 0 : IF (equal_key(bucket_it, std::move(key))) { // match found
# # # # #
# # # # #
# # # # #
# ]
923 [ # # # # : 0 : Pipeline(entry(bucket_it));
# # # # ]
924 : 0 : };
925 : : }
926 [ # # # # : 0 : bucket_it = Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # # #
# # # # #
# # # #
# ]
927 : : }
928 : 0 : }
929 : :
930 : : template<bool IsGlobal>
931 : 0 : HashTable::entry_t ChainedHashTable<IsGlobal>::dummy_entry()
932 : : {
933 : : /*----- Allocate memory for a dummy entry. -----*/
934 : 0 : var_t<Ptr<void>> entry; // create global variable iff `IsGlobal` to be able to access it later for deallocation
935 [ # # # # : 0 : entry = Module::Allocator().allocate(entry_size_in_bytes_, entry_max_alignment_in_bytes_);
# # # # #
# # # ]
936 : :
937 : : /*----- Store address and size of dummy entry to free them later. -----*/
938 [ # # # # ]: 0 : dummy_allocations_.emplace_back(entry, entry_size_in_bytes_);
939 : :
940 : : /*----- Return *local* entry handle containing all values. -----*/
941 [ # # # # : 0 : return value_entry(M_CONSTEXPR_COND(IsGlobal, Var<Ptr<void>>(entry.val()).val(), entry.val()));
# # # # #
# # # ]
942 : 0 : }
943 : :
944 : : template<bool IsGlobal>
945 : 0 : Boolx1 ChainedHashTable<IsGlobal>::equal_key(Ptr<void> entry, std::vector<SQL_t> key) const
946 : : {
947 : 0 : Var<Boolx1> res(true);
948 : :
949 [ # # # # ]: 0 : for (std::size_t i = 0; i < key_indices_.size(); ++i) {
950 : : /* do not skip duplicated comparison of the same slot since probing might need this comparison */
951 : :
952 [ # # # # ]: 0 : auto &e = schema_.get()[key_indices_[i]];
953 : 0 : const auto off = entry_offsets_in_bytes_[key_indices_[i]];
954 : 0 : auto compare_equal = [&]<typename T>() {
955 : : using type = typename T::type;
956 : 0 : M_insist(std::holds_alternative<T>(key[i]));
957 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
958 [ # # # # : 0 : const_reference_t<T> ref((entry.clone() + off).template to<type*>(),
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
959 [ # # # # : 0 : entry.clone() + null_bitmap_offset_in_bytes_, key_indices_[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
960 [ # # # # : 0 : res = res and ref == *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
961 : 0 : } else { // entry must not be NULL
962 [ # # # # : 0 : const_reference_t<T> ref((entry.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
963 [ # # # # : 0 : res = res and ref == *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
964 : 0 : }
965 : 0 : };
966 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# ]
967 : 0 : [&](const Boolean&) { compare_equal.template operator()<_Boolx1>(); },
968 : 0 : [&](const Numeric &n) {
969 [ # # # # : 0 : switch (n.kind) {
# # ]
970 : : case Numeric::N_Int:
971 : : case Numeric::N_Decimal:
972 [ # # # # : 0 : switch (n.size()) {
# # # # #
# ]
973 : 0 : default: M_unreachable("invalid size");
974 : 0 : case 8: compare_equal.template operator()<_I8x1 >(); break;
975 : 0 : case 16: compare_equal.template operator()<_I16x1>(); break;
976 : 0 : case 32: compare_equal.template operator()<_I32x1>(); break;
977 : 0 : case 64: compare_equal.template operator()<_I64x1>(); break;
978 : : }
979 : 0 : break;
980 : : case Numeric::N_Float:
981 [ # # # # ]: 0 : if (n.size() <= 32)
982 : 0 : compare_equal.template operator()<_Floatx1>();
983 : : else
984 : 0 : compare_equal.template operator()<_Doublex1>();
985 : 0 : }
986 : 0 : },
987 : 0 : [&](const CharacterSequence &cs) {
988 : 0 : M_insist(std::holds_alternative<NChar>(key[i]));
989 [ # # # # : 0 : NChar val((entry.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # ]
990 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # ]
991 [ # # # # : 0 : const_reference_t<NChar> ref(val, entry.clone() + null_bitmap_offset_in_bytes_, key_indices_[i]);
# # # # #
# # # # #
# # ]
992 [ # # # # : 0 : res = res and ref == *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # ]
993 : 0 : } else { // entry must not be NULL
994 [ # # # # : 0 : const_reference_t<NChar> ref(val);
# # # # ]
995 [ # # # # : 0 : res = res and ref == *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # ]
996 : 0 : }
997 : 0 : },
998 : 0 : [&](const Date&) { compare_equal.template operator()<_I32x1>(); },
999 : 0 : [&](const DateTime&) { compare_equal.template operator()<_I64x1>(); },
1000 : 0 : [](auto&&) { M_unreachable("invalid type"); },
1001 : 0 : }, *e.type);
1002 : 0 : }
1003 : :
1004 [ # # # # ]: 0 : entry.discard(); // since it was always cloned
1005 : :
1006 [ # # # # ]: 0 : return res;
1007 : 0 : }
1008 : :
1009 : : template<bool IsGlobal>
1010 : 0 : void ChainedHashTable<IsGlobal>::insert_key(Ptr<void> entry, std::vector<SQL_t> key)
1011 : : {
1012 [ # # # # ]: 0 : for (std::size_t i = 0; i < key_indices_.size(); ++i) {
1013 : : /* NOTE: `std::find` results in quadratic complexity but we expect rather short keys anyway */
1014 [ # # # # ]: 0 : if (std::find(key_indices_.begin(), key_indices_.begin() + i, key_indices_[i]) != key_indices_.begin() + i) {
1015 : 0 : discard(key[i]);
1016 : 0 : continue; // skip duplicated writing of the same slot
1017 : : }
1018 : :
1019 : 0 : auto &e = schema_.get()[key_indices_[i]];
1020 : 0 : const auto off = entry_offsets_in_bytes_[key_indices_[i]];
1021 : 0 : auto insert = [&]<typename T>() {
1022 : : using type = typename T::type;
1023 : 0 : M_insist(std::holds_alternative<T>(key[i]));
1024 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1025 [ # # # # : 0 : reference_t<T> ref((entry.clone() + off).template to<type*>(),
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1026 [ # # # # : 0 : entry.clone() + null_bitmap_offset_in_bytes_, key_indices_[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1027 [ # # # # : 0 : ref = *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1028 : 0 : } else { // entry must not be NULL
1029 [ # # # # : 0 : reference_t<T> ref((entry.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1030 [ # # # # : 0 : ref = *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1031 : 0 : }
1032 : 0 : };
1033 : 0 : visit(overloaded {
1034 : 0 : [&](const Boolean&) { insert.template operator()<_Boolx1>(); },
1035 : 0 : [&](const Numeric &n) {
1036 [ # # # # : 0 : switch (n.kind) {
# # ]
1037 : : case Numeric::N_Int:
1038 : : case Numeric::N_Decimal:
1039 [ # # # # : 0 : switch (n.size()) {
# # # # #
# ]
1040 : 0 : default: M_unreachable("invalid size");
1041 : 0 : case 8: insert.template operator()<_I8x1 >(); break;
1042 : 0 : case 16: insert.template operator()<_I16x1>(); break;
1043 : 0 : case 32: insert.template operator()<_I32x1>(); break;
1044 : 0 : case 64: insert.template operator()<_I64x1>(); break;
1045 : : }
1046 : 0 : break;
1047 : : case Numeric::N_Float:
1048 [ # # # # ]: 0 : if (n.size() <= 32)
1049 : 0 : insert.template operator()<_Floatx1>();
1050 : : else
1051 : 0 : insert.template operator()<_Doublex1>();
1052 : 0 : }
1053 : 0 : },
1054 : 0 : [&](const CharacterSequence &cs) {
1055 : 0 : M_insist(std::holds_alternative<NChar>(key[i]));
1056 [ # # # # : 0 : NChar val((entry.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # ]
1057 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # ]
1058 [ # # # # : 0 : reference_t<NChar> ref(val, entry.clone() + null_bitmap_offset_in_bytes_, key_indices_[i]);
# # # # #
# # # # #
# # ]
1059 [ # # # # : 0 : ref = *std::get_if<NChar>(&key[i]);
# # # # ]
1060 : 0 : } else { // entry must not be NULL
1061 [ # # # # : 0 : reference_t<NChar> ref(val);
# # # # ]
1062 [ # # # # : 0 : ref = *std::get_if<NChar>(&key[i]);
# # # # ]
1063 : 0 : }
1064 : 0 : },
1065 : 0 : [&](const Date&) { insert.template operator()<_I32x1>(); },
1066 : 0 : [&](const DateTime&) { insert.template operator()<_I64x1>(); },
1067 : 0 : [](auto&&) { M_unreachable("invalid type"); },
1068 : 0 : }, *e.type);
1069 : 0 : }
1070 : :
1071 : 0 : entry.discard(); // since it was always cloned
1072 : 0 : }
1073 : :
1074 : : template<bool IsGlobal>
1075 : 0 : HashTable::entry_t ChainedHashTable<IsGlobal>::value_entry(Ptr<void> entry) const
1076 : : {
1077 : 0 : entry_t value_entry;
1078 : :
1079 [ # # # # ]: 0 : for (std::size_t i = 0; i < value_indices_.size(); ++i) {
1080 : : /* there are no duplicates in the value indexes */
1081 : :
1082 [ # # # # ]: 0 : auto &e = schema_.get()[value_indices_[i]];
1083 : 0 : const auto off = entry_offsets_in_bytes_[value_indices_[i]];
1084 : 0 : auto add = [&]<typename T>() {
1085 : : using type = typename T::type;
1086 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1087 [ # # # # : 0 : reference_t<T> ref((entry.clone() + off).template to<type*>(),
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1088 [ # # # # : 0 : entry.clone() + null_bitmap_offset_in_bytes_, value_indices_[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1089 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1090 : 0 : } else { // entry must not be NULL
1091 [ # # # # : 0 : reference_t<T> ref((entry.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1092 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1093 : 0 : }
1094 : 0 : };
1095 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# ]
1096 : 0 : [&](const Boolean&) { add.template operator()<_Boolx1>(); },
1097 : 0 : [&](const Numeric &n) {
1098 [ # # # # : 0 : switch (n.kind) {
# # ]
1099 : : case Numeric::N_Int:
1100 : : case Numeric::N_Decimal:
1101 [ # # # # : 0 : switch (n.size()) {
# # # # #
# ]
1102 : 0 : default: M_unreachable("invalid size");
1103 : 0 : case 8: add.template operator()<_I8x1 >(); break;
1104 : 0 : case 16: add.template operator()<_I16x1>(); break;
1105 : 0 : case 32: add.template operator()<_I32x1>(); break;
1106 : 0 : case 64: add.template operator()<_I64x1>(); break;
1107 : : }
1108 : 0 : break;
1109 : : case Numeric::N_Float:
1110 [ # # # # ]: 0 : if (n.size() <= 32)
1111 : 0 : add.template operator()<_Floatx1>();
1112 : : else
1113 : 0 : add.template operator()<_Doublex1>();
1114 : 0 : }
1115 : 0 : },
1116 : 0 : [&](const CharacterSequence &cs) {
1117 [ # # # # : 0 : NChar val((entry.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # ]
1118 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # ]
1119 [ # # # # : 0 : reference_t<NChar> ref(val, entry.clone() + null_bitmap_offset_in_bytes_, value_indices_[i]);
# # # # #
# # # # #
# # ]
1120 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # ]
1121 : 0 : } else { // entry must not be NULL
1122 [ # # # # : 0 : reference_t<NChar> ref(val);
# # # # ]
1123 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # ]
1124 : 0 : }
1125 : 0 : },
1126 : 0 : [&](const Date&) { add.template operator()<_I32x1>(); },
1127 : 0 : [&](const DateTime&) { add.template operator()<_I64x1>(); },
1128 : 0 : [](auto&&) { M_unreachable("invalid type"); },
1129 : 0 : }, *e.type);
1130 : 0 : }
1131 : :
1132 [ # # # # ]: 0 : entry.discard(); // since it was always cloned
1133 : :
1134 : 0 : return value_entry;
1135 [ # # # # ]: 0 : }
1136 : :
1137 : : template<bool IsGlobal>
1138 : 0 : HashTable::const_entry_t ChainedHashTable<IsGlobal>::entry(Ptr<void> entry) const
1139 : : {
1140 : 0 : const_entry_t _entry;
1141 : :
1142 [ # # # # ]: 0 : for (std::size_t i = 0; i < key_indices_.size() + value_indices_.size(); ++i) {
1143 : 0 : const bool is_key = i < key_indices_.size();
1144 : : /* NOTE: `std::find` results in quadratic complexity but we expect rather short keys anyway */
1145 [ # # # # : 0 : if (is_key and std::find(key_indices_.begin(), key_indices_.begin() + i, key_indices_[i]) != key_indices_.begin() + i)
# # # # #
# # # ]
1146 : 0 : continue; // skip duplicated key to the same slot
1147 : :
1148 [ # # # # ]: 0 : const auto idx = is_key ? key_indices_[i] : value_indices_[i - key_indices_.size()];
1149 [ # # # # ]: 0 : auto &e = schema_.get()[idx];
1150 : 0 : const auto off = entry_offsets_in_bytes_[idx];
1151 : 0 : auto add = [&]<typename T>() {
1152 : : using type = typename T::type;
1153 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1154 [ # # # # : 0 : const_reference_t<T> ref((entry.clone() + off).template to<type*>(),
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1155 [ # # # # : 0 : entry.clone() + null_bitmap_offset_in_bytes_, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1156 [ # # # # : 0 : _entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1157 : 0 : } else { // entry must not be NULL
1158 [ # # # # : 0 : const_reference_t<T> ref((entry.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1159 [ # # # # : 0 : _entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1160 : 0 : }
1161 : 0 : };
1162 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# ]
1163 : 0 : [&](const Boolean&) { add.template operator()<_Boolx1>(); },
1164 : 0 : [&](const Numeric &n) {
1165 [ # # # # : 0 : switch (n.kind) {
# # ]
1166 : : case Numeric::N_Int:
1167 : : case Numeric::N_Decimal:
1168 [ # # # # : 0 : switch (n.size()) {
# # # # #
# ]
1169 : 0 : default: M_unreachable("invalid size");
1170 : 0 : case 8: add.template operator()<_I8x1 >(); break;
1171 : 0 : case 16: add.template operator()<_I16x1>(); break;
1172 : 0 : case 32: add.template operator()<_I32x1>(); break;
1173 : 0 : case 64: add.template operator()<_I64x1>(); break;
1174 : : }
1175 : 0 : break;
1176 : : case Numeric::N_Float:
1177 [ # # # # ]: 0 : if (n.size() <= 32)
1178 : 0 : add.template operator()<_Floatx1>();
1179 : : else
1180 : 0 : add.template operator()<_Doublex1>();
1181 : 0 : }
1182 : 0 : },
1183 : 0 : [&](const CharacterSequence &cs) {
1184 [ # # # # : 0 : NChar val((entry.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # ]
1185 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # ]
1186 [ # # # # : 0 : const_reference_t<NChar> ref(val, entry.clone() + null_bitmap_offset_in_bytes_, idx);
# # # # #
# # # # #
# # ]
1187 [ # # # # : 0 : _entry.add(e.id, std::move(ref));
# # # # ]
1188 : 0 : } else { // entry must not be NULL
1189 [ # # # # : 0 : const_reference_t<NChar> ref(val);
# # # # ]
1190 [ # # # # : 0 : _entry.add(e.id, std::move(ref));
# # # # ]
1191 : 0 : }
1192 : 0 : },
1193 : 0 : [&](const Date&) { add.template operator()<_I32x1>(); },
1194 : 0 : [&](const DateTime&) { add.template operator()<_I64x1>(); },
1195 : 0 : [](auto&&) { M_unreachable("invalid type"); },
1196 : 0 : }, *e.type);
1197 : 0 : }
1198 : :
1199 [ # # # # ]: 0 : entry.discard(); // since it was always cloned
1200 : :
1201 : 0 : return _entry;
1202 [ # # # # ]: 0 : }
1203 : :
1204 : : template<bool IsGlobal>
1205 : 0 : void ChainedHashTable<IsGlobal>::rehash()
1206 : : {
1207 [ # # # # ]: 0 : if (options::insist_no_rehashing)
1208 : 0 : Throw(exception::unreachable, "rehashing must not occur");
1209 : :
1210 : 0 : auto emit_rehash = [this](){
1211 : 0 : auto S = CodeGenContext::Get().scoped_environment(); // fresh environment to remove predication while rehashing
1212 : :
1213 [ # # # # ]: 0 : M_insist(bool(address_), "must call `setup()` before");
1214 [ # # # # ]: 0 : M_insist(bool(mask_), "must call `setup()` before");
1215 : :
1216 : : /*----- Store old begin and end (since they will be overwritten). -----*/
1217 [ # # # # : 0 : const Var<Ptr<void>> begin_old(begin());
# # # # ]
1218 [ # # # # : 0 : const Var<Ptr<void>> end_old(end());
# # # # ]
1219 : :
1220 : : /*----- Double capacity. -----*/
1221 [ # # # # : 0 : *mask_ = (*mask_ << 1U) + 1U;
# # # # #
# # # ]
1222 : :
1223 : : /*----- Allocate memory for new hash table with updated capacity. -----*/
1224 [ # # # # : 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), sizeof(uint32_t));
# # # # #
# # # # #
# # ]
1225 : :
1226 : : /*----- Clear newly created hash table. -----*/
1227 [ # # # # ]: 0 : clear();
1228 : :
1229 : : /*----- Insert each element from old hash table into new one. -----*/
1230 [ # # # # : 0 : Var<Ptr<void>> it(begin_old.val());
# # # # ]
1231 [ # # # # : 0 : WHILE (it != end_old) {
# # # # #
# # # # #
# # ]
1232 [ # # # # : 0 : Wasm_insist(begin_old <= it and it < end_old, "bucket out-of-bounds");
# # # # #
# # # # #
# # # # #
# ]
1233 [ # # # # : 0 : Var<Ptr<void>> bucket_it(Ptr<void>(*it.to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# ]
1234 [ # # # # : 0 : WHILE (not bucket_it.is_nullptr()) { // another entry in old collision list
# # # # #
# # # # #
# # # # #
# ]
1235 [ # # # # : 0 : auto e_old = entry(it);
# # # # ]
1236 : :
1237 : : /*----- Access key from old entry. -----*/
1238 : 0 : std::vector<SQL_t> key;
1239 [ # # # # ]: 0 : for (auto k : key_indices_) {
1240 [ # # # # ]: 0 : std::visit(overloaded {
1241 : 0 : [&](auto &&r) -> void { key.emplace_back(r); },
1242 : 0 : [](std::monostate) -> void { M_unreachable("invalid reference"); },
1243 [ # # # # : 0 : }, e_old.get(schema_.get()[k].id));
# # # # ]
1244 : : }
1245 : :
1246 : : /*----- Compute new bucket address by hashing the key. Create variable to do not recompute the hash. -*/
1247 [ # # # # : 0 : const Var<Ptr<void>> bucket(hash_to_bucket(std::move(key)));
# # # # ]
1248 : :
1249 : : /*----- Store next entry's address in old collision list (since it will be overwritten). -----*/
1250 [ # # # # : 0 : const Var<Ptr<void>> tmp(Ptr<void>(*(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>()));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1251 : :
1252 : : /*----- Insert old entry at new collision list's front. No reallocation of the entry is needed. -----*/
1253 [ # # # # : 0 : *(bucket_it + ptr_offset_in_bytes_).template to<uint32_t*>() = *bucket.to<uint32_t*>();
# # # # #
# # # # #
# # # # #
# # # #
# ]
1254 [ # # # # : 0 : *bucket.to<uint32_t*>() = bucket_it.to<uint32_t>();
# # # # #
# # # # #
# # ]
1255 : :
1256 : : /*----- Advance to next entry in old collision list. -----*/
1257 [ # # # # : 0 : bucket_it = tmp.val();
# # # # ]
1258 : 0 : }
1259 : :
1260 : : /*----- Advance to next bucket in old hash table. -----*/
1261 [ # # # # ]: 0 : it += int32_t(sizeof(uint32_t));
1262 : 0 : }
1263 : :
1264 : : /*----- Free old hash table (without collision list entries since they are reused). -----*/
1265 [ # # # # : 0 : U32x1 size = (end_old - begin_old).make_unsigned();
# # # # ]
1266 [ # # # # : 0 : Module::Allocator().deallocate(begin_old, size);
# # # # #
# # # # #
# # ]
1267 : 0 : };
1268 : :
1269 : : if constexpr (IsGlobal) {
1270 [ # # ]: 0 : if (not rehash_) {
1271 : : /*----- Backup former local variables to be able to use new ones for rehashing function. -----*/
1272 : 0 : auto old_address = std::exchange(address_, std::nullopt);
1273 [ # # ]: 0 : auto old_mask = std::exchange(mask_, std::nullopt);
1274 : : /* omit `num_entries_` and `high_watermark_absolute_` as they are never accessed during rehashing */
1275 : :
1276 : : /*----- Create function for rehashing. -----*/
1277 [ # # # # : 0 : FUNCTION(rehash, void(void))
# # # # ]
1278 : : {
1279 : : /*----- Perform setup for local variables. -----*/
1280 [ # # ]: 0 : address_.emplace(storage_.address_);
1281 [ # # ]: 0 : mask_.emplace(storage_.mask_);
1282 : :
1283 [ # # ]: 0 : emit_rehash();
1284 : :
1285 : : /*----- Perform teardown for local variables. -----*/
1286 [ # # ]: 0 : storage_.address_ = *address_;
1287 [ # # ]: 0 : storage_.mask_ = *mask_;
1288 : 0 : address_.reset();
1289 : 0 : mask_.reset();
1290 : : }
1291 : 0 : rehash_ = std::move(rehash);
1292 : :
1293 : : /*----- Restore local variables. -----*/
1294 [ # # ]: 0 : std::exchange(address_, std::move(old_address));
1295 [ # # ]: 0 : std::exchange(mask_, std::move(old_mask));
1296 : 0 : }
1297 : :
1298 : : /*----- Store local variables in global backups. -----*/
1299 : 0 : storage_.address_ = *address_;
1300 : 0 : storage_.mask_ = *mask_;
1301 : :
1302 : : /*----- Call rehashing function. ------*/
1303 : 0 : M_insist(bool(rehash_));
1304 : 0 : (*rehash_)();
1305 : :
1306 : : /*----- Restore local variables from global backups. -----*/
1307 : 0 : *address_ = storage_.address_;
1308 : 0 : *mask_ = storage_.mask_;
1309 : : } else {
1310 : : /*----- Emit rehashing code. ------*/
1311 : 0 : emit_rehash();
1312 : : }
1313 : 0 : }
1314 : :
1315 : : // explicit instantiations to prevent linker errors
1316 : : template struct m::wasm::ChainedHashTable<false>;
1317 : : template struct m::wasm::ChainedHashTable<true>;
1318 : :
1319 : :
1320 : : /*----- open addressing hash tables ----------------------------------------------------------------------------------*/
1321 : :
1322 : 0 : void OpenAddressingHashTableBase::clear()
1323 : : {
1324 [ # # ]: 0 : Var<Ptr<void>> it(begin());
1325 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# ]
1326 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "entry out-of-bounds");
# # # # #
# # # #
# ]
1327 [ # # # # : 0 : reference_count(it) = ref_t(0);
# # ]
1328 [ # # ]: 0 : it += int32_t(entry_size_in_bytes_);
1329 : : }
1330 : 0 : }
1331 : :
1332 : 0 : Ptr<void> OpenAddressingHashTableBase::hash_to_bucket(std::vector<SQL_t> key) const
1333 : : {
1334 : 0 : M_insist(key.size() == key_indices_.size(),
1335 : : "provided number of key elements does not match hash table's number of key indices");
1336 : :
1337 : : /*----- Collect types of key together with the respective value. -----*/
1338 : 0 : std::vector<std::pair<const Type*, SQL_t>> values;
1339 [ # # ]: 0 : values.reserve(key_indices_.size());
1340 : 0 : auto key_it = key.begin();
1341 [ # # ]: 0 : for (auto k : key_indices_)
1342 [ # # # # ]: 0 : values.emplace_back(schema_.get()[k].type, std::move(*key_it++));
1343 : :
1344 : : /*----- Compute hash of key using Murmur3_64a. -----*/
1345 [ # # ]: 0 : U64x1 hash = murmur3_64a_hash(std::move(values));
1346 : :
1347 : : /*----- Compute bucket address. -----*/
1348 [ # # # # : 0 : U32x1 bucket_idx = hash.to<uint32_t>() bitand mask(); // modulo capacity
# # ]
1349 [ # # # # : 0 : Ptr<void> bucket = begin() + (bucket_idx * entry_size_in_bytes_).make_signed();
# # # # ]
1350 [ # # # # : 0 : Wasm_insist(begin() <= bucket.clone() and bucket.clone() < end(), "bucket out-of-bounds");
# # # # #
# # # # #
# # # # ]
1351 : 0 : return bucket;
1352 [ # # ]: 0 : }
1353 : :
1354 : : template<bool IsGlobal, bool ValueInPlace>
1355 : 0 : OpenAddressingHashTable<IsGlobal, ValueInPlace>::OpenAddressingHashTable(const Schema &schema,
1356 : : std::vector<HashTable::index_t> key_indices,
1357 : : uint32_t initial_capacity)
1358 [ # # # # : 0 : : OpenAddressingHashTableBase(schema, std::move(key_indices))
# # # # ]
1359 : 0 : {
1360 : 0 : std::vector<const Type*> types;
1361 : 0 : bool has_nullable = false;
1362 : :
1363 : : /*----- Add reference counter. -----*/
1364 [ # # # # : 0 : types.push_back(Type::Get_Integer(Type::TY_Vector, sizeof(ref_t)));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1365 : :
1366 : : if constexpr (ValueInPlace) {
1367 : : /*----- Add schema types. -----*/
1368 [ # # # # : 0 : for (auto &e : schema_.get()) {
# # # # #
# # # ]
1369 [ # # # # ]: 0 : types.push_back(e.type);
1370 [ # # # # ]: 0 : has_nullable |= e.nullable();
1371 : : }
1372 : :
1373 [ # # # # ]: 0 : if (has_nullable) {
1374 : : /*----- Add type for NULL bitmap. Reference counter cannot be NULL. -----*/
1375 [ # # # # : 0 : types.push_back(Type::Get_Bitmap(Type::TY_Vector, types.size() - 1));
# # # # #
# # # ]
1376 : 0 : }
1377 : :
1378 : : /*----- Compute entry offsets and set entry size and alignment requirement. -----*/
1379 : 0 : std::vector<HashTable::offset_t> offsets;
1380 [ # # # # ]: 0 : std::tie(entry_size_in_bytes_, entry_max_alignment_in_bytes_) = set_byte_offsets(offsets, types);
1381 : :
1382 : : /*----- Set offset for reference counter. -----*/
1383 : 0 : refs_offset_in_bytes_ = offsets.front();
1384 : :
1385 [ # # # # ]: 0 : if (has_nullable) {
1386 : : /*----- Set offset for NULL bitmap and remove it from `offsets`. -----*/
1387 : 0 : layout_.null_bitmap_offset_in_bytes_ = offsets.back();
1388 : 0 : offsets.pop_back();
1389 : 0 : }
1390 : :
1391 : : /*----- Set entry offset. Exclude offset for reference counter. -----*/
1392 [ # # # # : 0 : layout_.entry_offsets_in_bytes_ = std::vector<HashTable::offset_t>(std::next(offsets.begin()), offsets.end());
# # # # ]
1393 : 0 : } else {
1394 : : /*----- Add key types. -----*/
1395 [ # # # # : 0 : for (std::size_t i = 0; i < schema_.get().num_entries(); ++i) {
# # # # ]
1396 [ # # # # : 0 : if (not contains(key_indices_, i))
# # # # ]
1397 : 0 : continue;
1398 [ # # # # : 0 : types.push_back(schema_.get()[i].type);
# # # # ]
1399 [ # # # # : 0 : has_nullable |= schema_.get()[i].nullable();
# # # # ]
1400 : 0 : }
1401 : :
1402 : : /*----- Add type for pointer to out-of-place values. -----*/
1403 [ # # # # : 0 : types.push_back(Type::Get_Integer(Type::TY_Vector, 4));
# # # # #
# # # ]
1404 : :
1405 [ # # # # ]: 0 : if (has_nullable) {
1406 : : /*----- Add type for keys NULL bitmap. Reference counter and pointer to values cannot be NULL. -----*/
1407 [ # # # # : 0 : types.push_back(Type::Get_Bitmap(Type::TY_Vector, types.size() - 2));
# # # # #
# # # ]
1408 : 0 : }
1409 : :
1410 : : /*----- Compute entry offsets and set entry size and alignment requirement. -----*/
1411 : 0 : std::vector<HashTable::offset_t> offsets;
1412 [ # # # # ]: 0 : std::tie(entry_size_in_bytes_, entry_max_alignment_in_bytes_) = set_byte_offsets(offsets, types);
1413 : :
1414 : : /*----- Set offset for reference counter. -----*/
1415 : 0 : refs_offset_in_bytes_ = offsets.front();
1416 : :
1417 [ # # # # ]: 0 : if (has_nullable) {
1418 : : /*----- Set offset for keys NULL bitmap and remove it from `offsets`. -----*/
1419 : 0 : layout_.keys_null_bitmap_offset_in_bytes_ = offsets.back();
1420 : 0 : offsets.pop_back();
1421 : 0 : }
1422 : :
1423 : : /*----- Set offset for pointer to out-of-place values and key offsets. Exclude offset for reference counter. -*/
1424 : 0 : layout_.ptr_offset_in_bytes_ = offsets.back();
1425 : 0 : layout_.key_offsets_in_bytes_ =
1426 [ # # # # : 0 : std::vector<HashTable::offset_t>(std::next(offsets.begin()), std::prev(offsets.end()));
# # # # #
# # # ]
1427 : :
1428 : : /*----- Add value types. -----*/
1429 : 0 : types.clear();
1430 : 0 : has_nullable = false;
1431 [ # # # # : 0 : for (std::size_t i = 0; i < schema_.get().num_entries(); ++i) {
# # # # ]
1432 [ # # # # : 0 : if (not contains(value_indices_, i))
# # # # ]
1433 : 0 : continue;
1434 [ # # # # : 0 : types.push_back(schema_.get()[i].type);
# # # # ]
1435 [ # # # # : 0 : has_nullable |= schema_.get()[i].nullable();
# # # # ]
1436 : 0 : }
1437 : :
1438 [ # # # # ]: 0 : if (has_nullable) {
1439 : : /*----- Add type for values NULL bitmap. -----*/
1440 [ # # # # : 0 : types.push_back(Type::Get_Bitmap(Type::TY_Vector, types.size()));
# # # # #
# # # ]
1441 : :
1442 : : /*----- Compute out-of-place entry offsets and set entry size and alignment requirement. -----*/
1443 : 0 : offsets.clear();
1444 : 0 : std::tie(layout_.values_size_in_bytes_, layout_.values_max_alignment_in_bytes_) =
1445 [ # # # # ]: 0 : set_byte_offsets(offsets, types);
1446 : :
1447 : : /*----- Set offset for values NULL bitmap and value offsets. -----*/
1448 : 0 : layout_.values_null_bitmap_offset_in_bytes_ = offsets.back();
1449 : 0 : layout_.value_offsets_in_bytes_ =
1450 [ # # # # : 0 : std::vector<HashTable::offset_t>(offsets.begin(), std::prev(offsets.end()));
# # # # ]
1451 : 0 : } else {
1452 : : /*----- Set value offsets, size, and alignment requirement. -----*/
1453 : 0 : std::tie(layout_.values_size_in_bytes_, layout_.values_max_alignment_in_bytes_) =
1454 [ # # # # ]: 0 : set_byte_offsets(layout_.value_offsets_in_bytes_, types);
1455 : : }
1456 : 0 : }
1457 : :
1458 : : /*----- Initialize capacity and absolute high watermark. -----*/
1459 [ # # # # : 0 : M_insist(initial_capacity < std::numeric_limits<uint32_t>::max(),
# # # # ]
1460 : : "incremented initial capacity would exceed data type");
1461 : 0 : ++initial_capacity; // since at least one entry must always be unoccupied for lookups
1462 : : /* at least capacity 4 to ensure absolute high watermark of at least 1 even for minimal percentage of 0.5 */
1463 [ # # # # : 0 : const auto capacity_init = std::max<uint32_t>(4, ceil_to_pow_2(initial_capacity));
# # # # #
# # # # #
# # ]
1464 : 0 : const auto mask_init = capacity_init - 1U;
1465 : 0 : const auto high_watermark_absolute_init = capacity_init - 1U; // at least one entry must always be unoccupied
1466 : : if constexpr (IsGlobal) {
1467 [ # # # # ]: 0 : storage_.address_.init(0), // init with nullptr
1468 [ # # # # ]: 0 : storage_.mask_.init(mask_init);
1469 [ # # # # ]: 0 : storage_.high_watermark_absolute_.init(high_watermark_absolute_init);
1470 : : } else {
1471 [ # # # # ]: 0 : mask_.emplace(mask_init);
1472 [ # # # # ]: 0 : high_watermark_absolute_.emplace(high_watermark_absolute_init);
1473 : : }
1474 : 0 : }
1475 : :
1476 : : template<bool IsGlobal, bool ValueInPlace>
1477 : 0 : OpenAddressingHashTable<IsGlobal, ValueInPlace>::~OpenAddressingHashTable()
1478 : 0 : {
1479 : : if constexpr (IsGlobal) { // free memory of global hash table when object is destroyed and no use may occur later
1480 : : if constexpr (not ValueInPlace) {
1481 : : /*----- Free out-of-place values. -----*/
1482 [ # # ]: 0 : Var<Ptr<void>> it(storage_.address_);
1483 [ # # # # : 0 : const Var<Ptr<void>> end(storage_.address_ + ((storage_.mask_ + 1U) * entry_size_in_bytes_).make_signed());
# # # # #
# ]
1484 [ # # # # : 0 : WHILE (it != end) {
# # # # ]
1485 [ # # # # : 0 : Wasm_insist(storage_.address_ <= it and it < end, "entry out-of-bounds");
# # # # #
# ]
1486 [ # # # # : 0 : IF (reference_count(it) != ref_t(0)) { // occupied
# # # # ]
1487 [ # # # # : 0 : Module::Allocator().deallocate(Ptr<void>(*(it + layout_.ptr_offset_in_bytes_).template to<uint32_t*>()),
# # # # #
# ]
1488 : 0 : layout_.values_size_in_bytes_);
1489 : 0 : };
1490 [ # # ]: 0 : it += int32_t(entry_size_in_bytes_);
1491 : : }
1492 : 0 : }
1493 : :
1494 : : /*----- Free all entries. -----*/
1495 [ # # # # : 0 : Module::Allocator().deallocate(storage_.address_, (storage_.mask_ + 1U) * entry_size_in_bytes_);
# # # # #
# # # # #
# # # # #
# ]
1496 : :
1497 : : /*----- Free dummy entries. -----*/
1498 [ # # # # : 0 : for (auto it = dummy_allocations_.rbegin(); it != dummy_allocations_.rend(); ++it)
# # # # #
# # # ]
1499 [ # # # # : 0 : Module::Allocator().deallocate(it->first, it->second);
# # # # #
# # # # #
# # # # #
# # # #
# ]
1500 : : }
1501 : 0 : }
1502 : :
1503 : : template<bool IsGlobal, bool ValueInPlace>
1504 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::setup()
1505 : : {
1506 : 0 : M_insist(not address_, "must not call `setup()` twice");
1507 : 0 : M_insist(not num_entries_, "must not call `setup()` twice");
1508 : :
1509 : : /*----- Create local variables. -----*/
1510 : 0 : address_.emplace();
1511 : 0 : num_entries_.emplace();
1512 : : if constexpr (IsGlobal) {
1513 : 0 : M_insist(not mask_, "must not call `setup()` twice");
1514 : 0 : M_insist(not high_watermark_absolute_, "must not call `setup()` twice");
1515 : 0 : mask_.emplace();
1516 : 0 : high_watermark_absolute_.emplace();
1517 : : } else {
1518 : 0 : M_insist(bool(mask_)); // already initialized in c'tor
1519 : 0 : M_insist(bool(high_watermark_absolute_)); // already initialized in c'tor
1520 : : }
1521 : :
1522 : : /*----- For global hash tables, read values from global backups into local variables. -----*/
1523 : : if constexpr (IsGlobal) {
1524 : : /* omit assigning address here as it will always be set below */
1525 : 0 : *mask_ = storage_.mask_;
1526 : 0 : *num_entries_ = storage_.num_entries_;
1527 : 0 : *high_watermark_absolute_ = storage_.high_watermark_absolute_;
1528 : : }
1529 : :
1530 : : if constexpr (IsGlobal) {
1531 [ # # # # ]: 0 : IF (storage_.address_.is_nullptr()) { // hash table not yet allocated
1532 : : /*----- Allocate memory for initial capacity. -----*/
1533 [ # # # # : 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), entry_max_alignment_in_bytes_);
# # # # ]
1534 : :
1535 : : /*----- Clear initial hash table. -----*/
1536 : 0 : clear();
1537 : 0 : } ELSE {
1538 : 0 : *address_ = storage_.address_;
1539 : 0 : };
1540 : : } else {
1541 : : /*----- Allocate memory for initial capacity. -----*/
1542 [ # # # # : 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), entry_max_alignment_in_bytes_);
# # # # ]
1543 : :
1544 : : /*----- Clear initial hash table. -----*/
1545 : 0 : clear();
1546 : : }
1547 : 0 : }
1548 : :
1549 : : template<bool IsGlobal, bool ValueInPlace>
1550 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::teardown()
1551 : : {
1552 : 0 : M_insist(bool(address_), "must call `setup()` before");
1553 : 0 : M_insist(bool(mask_), "must call `setup()` before");
1554 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1555 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
1556 : :
1557 : : if constexpr (not IsGlobal) { // free memory of local hash table when user calls teardown method
1558 : : if constexpr (not ValueInPlace) {
1559 : : /*----- Free out-of-place values. -----*/
1560 [ # # ]: 0 : Var<Ptr<void>> it(begin());
1561 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# ]
1562 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "entry out-of-bounds");
# # # # #
# # # #
# ]
1563 [ # # # # : 0 : IF (reference_count(it) != ref_t(0)) { // occupied
# # # # ]
1564 [ # # # # : 0 : Module::Allocator().deallocate(Ptr<void>(*(it + layout_.ptr_offset_in_bytes_).template to<uint32_t*>()),
# # # # #
# ]
1565 : 0 : layout_.values_size_in_bytes_);
1566 : 0 : };
1567 [ # # ]: 0 : it += int32_t(entry_size_in_bytes_);
1568 : : }
1569 : 0 : }
1570 : :
1571 : : /*----- Free all entries. -----*/
1572 [ # # # # : 0 : Module::Allocator().deallocate(*address_, size_in_bytes());
# # # # ]
1573 : :
1574 : : /*----- Free dummy entries. -----*/
1575 [ # # # # ]: 0 : for (auto it = dummy_allocations_.rbegin(); it != dummy_allocations_.rend(); ++it)
1576 [ # # # # : 0 : Module::Allocator().deallocate(it->first, it->second);
# # # # #
# # # ]
1577 : : }
1578 : :
1579 : : /*----- For global hash tables, write values from local variables into global backups. -----*/
1580 : : if constexpr (IsGlobal) {
1581 : 0 : storage_.address_ = *address_;
1582 : 0 : storage_.mask_ = *mask_;
1583 : 0 : storage_.num_entries_ = *num_entries_;
1584 : 0 : storage_.high_watermark_absolute_ = *high_watermark_absolute_;
1585 : : }
1586 : :
1587 : : /*----- Destroy local variables. -----*/
1588 : 0 : address_.reset();
1589 : 0 : mask_.reset();
1590 : 0 : num_entries_.reset();
1591 : 0 : high_watermark_absolute_.reset();
1592 : 0 : }
1593 : :
1594 : : template<bool IsGlobal, bool ValueInPlace>
1595 : 0 : Ptr<void> OpenAddressingHashTable<IsGlobal, ValueInPlace>::compute_bucket(std::vector<SQL_t> key) const
1596 : : {
1597 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
1598 : 0 : std::optional<Boolx1> pred;
1599 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1600 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1601 [ # # # # : 0 : pred.emplace(env.extract_predicate<_Boolx1>().is_true_and_not_null());
# # # # #
# # # # #
# # # # #
# # # #
# ]
1602 [ # # # # : 0 : if (not predication_dummy_)
# # # # ]
1603 [ # # # # : 0 : const_cast<OpenAddressingHashTable<IsGlobal, ValueInPlace>*>(this)->create_predication_dummy();
# # # # ]
1604 : 0 : }
1605 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # #
# # # # #
# # ]
1606 : :
1607 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
1608 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1609 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(std::move(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # # #
# # # # #
# # # #
# ]
1610 [ # # # # : 0 : : hash_to_bucket(std::move(key))
# # # # ]
1611 : : );
1612 : :
1613 [ # # # # : 0 : return bucket;
# # # # ]
1614 : 0 : }
1615 : :
1616 : : template<bool IsGlobal, bool ValueInPlace>
1617 : 0 : HashTable::entry_t OpenAddressingHashTable<IsGlobal, ValueInPlace>::emplace(std::vector<SQL_t> key)
1618 : : {
1619 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1620 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
1621 : :
1622 : : /*----- If high watermark is reached, perform rehashing and update high watermark. -----*/
1623 [ # # # # : 0 : IF (*num_entries_ == *high_watermark_absolute_) { // XXX: num_entries_ - 1U iff predication predicate is not fulfilled
# # # # ]
1624 : 0 : rehash();
1625 : 0 : update_high_watermark();
1626 : 0 : };
1627 : :
1628 [ # # # # : 0 : auto slot = emplace_without_rehashing(std::move(key));
# # # # ]
1629 : :
1630 : : if constexpr (ValueInPlace) {
1631 : : /*----- Return entry handle containing all values. -----*/
1632 [ # # # # : 0 : return value_entry(slot);
# # # # ]
1633 : : } else {
1634 : : /*----- Allocate memory for out-of-place values and set pointer to it. -----*/
1635 : : Ptr<void> ptr =
1636 [ # # # # : 0 : Module::Allocator().allocate(layout_.values_size_in_bytes_, layout_.values_max_alignment_in_bytes_);
# # # # #
# # # ]
1637 [ # # # # : 0 : *(slot + layout_.ptr_offset_in_bytes_).template to<uint32_t*>() = ptr.clone().to<uint32_t>();
# # # # #
# # # # #
# # # # #
# # # #
# ]
1638 : :
1639 : : /*----- Return entry handle containing all values. -----*/
1640 [ # # # # : 0 : return value_entry(ptr);
# # # # ]
1641 : 0 : }
1642 : 0 : }
1643 : :
1644 : : template<bool IsGlobal, bool ValueInPlace>
1645 : 0 : Ptr<void> OpenAddressingHashTable<IsGlobal, ValueInPlace>::emplace_without_rehashing(std::vector<SQL_t> key)
1646 : : {
1647 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1648 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
1649 : :
1650 [ # # # # : 0 : Wasm_insist(*num_entries_ < *high_watermark_absolute_);
# # # # ]
1651 : :
1652 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
1653 : 0 : std::optional<Var<Boolx1>> pred;
1654 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1655 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1656 [ # # # # : 0 : pred = env.extract_predicate<_Boolx1>().is_true_and_not_null();
# # # # #
# # # # #
# # # # #
# # # #
# ]
1657 [ # # # # : 0 : if (not predication_dummy_)
# # # # ]
1658 [ # # # # : 0 : create_predication_dummy();
# # # # ]
1659 : 0 : }
1660 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # #
# # # # #
# # ]
1661 : :
1662 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
1663 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1664 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(clone(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1665 [ # # # # : 0 : : hash_to_bucket(clone(key))
# # # # #
# # # # #
# # ]
1666 : : ); // clone key since we need it again for insertion
1667 : :
1668 : : /*----- Get reference count, i.e. occupied slots, of this bucket. -----*/
1669 [ # # # # : 0 : Var<PrimitiveExpr<ref_t>> refs(reference_count(bucket));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1670 : :
1671 : : /*----- Skip slots which are occupied anyway. -----*/
1672 [ # # # # : 0 : Ptr<void> _slot = probing_strategy().skip_slots(bucket, refs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1673 [ # # # # : 0 : Wasm_insist(begin() <= _slot.clone() and _slot.clone() < end(), "slot out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1674 [ # # # # : 0 : Var<Ptr<void>> slot(_slot);
# # # # ]
1675 : :
1676 : : /*----- Search first unoccupied slot. -----*/
1677 [ # # # # : 0 : WHILE (reference_count(slot) != ref_t(0)) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1678 [ # # # # : 0 : refs += ref_t(1);
# # # # ]
1679 [ # # # # : 0 : Wasm_insist(refs <= *num_entries_, "probing strategy has to find unoccupied slot if there is one");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1680 [ # # # # : 0 : slot = probing_strategy().advance_to_next_slot(slot, refs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1681 [ # # # # : 0 : Wasm_insist(begin() <= slot and slot < end(), "slot out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1682 : : }
1683 : :
1684 : : /*----- Update reference count of this bucket. -----*/
1685 [ # # # # : 0 : reference_count(bucket) = refs + ref_t(1); // no predication special case since bucket equals slot if dummy is used
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1686 : :
1687 : : /*----- Iff no predication is used or predicate is fulfilled, set slot as occupied. -----*/
1688 [ # # # # : 0 : reference_count(slot) = pred ? pred->to<ref_t>() : PrimitiveExpr<ref_t>(1);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1689 : :
1690 : : /*----- Update number of entries. -----*/
1691 [ # # # # : 0 : *num_entries_ += pred ? pred->to<uint32_t>() : U32x1(1);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1692 [ # # # # : 0 : Wasm_insist(*num_entries_ < capacity(), "at least one entry must always be unoccupied for lookups");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1693 : :
1694 : : /*----- Insert key. -----*/
1695 [ # # # # : 0 : insert_key(slot, std::move(key)); // move key at last use
# # # # #
# # # # #
# # ]
1696 : :
1697 [ # # # # : 0 : return slot;
# # # # ]
1698 : 0 : }
1699 : :
1700 : : template<bool IsGlobal, bool ValueInPlace>
1701 : : std::pair<HashTable::entry_t, Boolx1>
1702 : 0 : OpenAddressingHashTable<IsGlobal, ValueInPlace>::try_emplace(std::vector<SQL_t> key)
1703 : : {
1704 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1705 : 0 : M_insist(bool(high_watermark_absolute_), "must call `setup()` before");
1706 : :
1707 : : /*----- If high watermark is reached, perform rehashing and update high watermark. -----*/
1708 [ # # # # : 0 : IF (*num_entries_ == *high_watermark_absolute_) { // XXX: num_entries_ - 1U iff predication predicate is not fulfilled
# # # # ]
1709 : 0 : rehash();
1710 : 0 : update_high_watermark();
1711 : 0 : };
1712 [ # # # # : 0 : Wasm_insist(*num_entries_ < *high_watermark_absolute_);
# # # # ]
1713 : :
1714 : : /*----- If predication is used, introduce predication variable and update it before inserting a key. -----*/
1715 : 0 : std::optional<Var<Boolx1>> pred;
1716 [ # # # # : 0 : if (auto &env = CodeGenContext::Get().env(); env.predicated()) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1717 [ # # # # : 0 : M_insist(CodeGenContext::Get().num_simd_lanes() == 1, "invalid number of SIMD lanes");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1718 [ # # # # : 0 : pred = env.extract_predicate<_Boolx1>().is_true_and_not_null();
# # # # #
# # # # #
# # # # #
# # # #
# ]
1719 [ # # # # : 0 : if (not predication_dummy_)
# # # # ]
1720 [ # # # # : 0 : create_predication_dummy();
# # # # ]
1721 : 0 : }
1722 [ # # # # : 0 : M_insist(not pred or predication_dummy_);
# # # # #
# # # # #
# # ]
1723 : :
1724 : : /*----- Compute bucket address by hashing the key. Create constant variable to do not recompute the hash. -----*/
1725 [ # # # # : 0 : const Var<Ptr<void>> bucket(
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1726 [ # # # # : 0 : pred ? Select(*pred, hash_to_bucket(clone(key)), *predication_dummy_) // use dummy if predicate is not fulfilled
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1727 [ # # # # : 0 : : hash_to_bucket(clone(key))
# # # # #
# # # # #
# # ]
1728 : : ); // clone key since we need it again for insertion
1729 : :
1730 : : /*----- Set reference count, i.e. occupied slots, of this bucket to its initial value. -----*/
1731 [ # # # # : 0 : Var<PrimitiveExpr<ref_t>> refs(0);
# # # # ]
1732 : :
1733 : : /*----- Probe slots, abort and skip insertion if key already exists. -----*/
1734 [ # # # # : 0 : Var<Boolx1> entry_inserted(false);
# # # # ]
1735 [ # # # # : 0 : Var<Ptr<void>> slot(bucket.val());
# # # # #
# # # # #
# # ]
1736 [ # # # # : 0 : BLOCK(insert_entry) {
# # # # #
# # # # #
# # ]
1737 [ # # # # : 0 : WHILE (reference_count(slot) != ref_t(0)) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1738 [ # # # # : 0 : GOTO(equal_key(slot, clone(key)), insert_entry); // clone key (see above)
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1739 [ # # # # : 0 : refs += ref_t(1);
# # # # ]
1740 [ # # # # : 0 : Wasm_insist(refs <= *num_entries_, "probing strategy has to find unoccupied slot if there is one");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1741 [ # # # # : 0 : slot = probing_strategy().advance_to_next_slot(slot, refs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1742 [ # # # # : 0 : Wasm_insist(begin() <= slot and slot < end(), "slot out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1743 : : }
1744 [ # # # # : 0 : Wasm_insist(reference_count(slot) == ref_t(0));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1745 [ # # # # : 0 : if (pred)
# # # # ]
1746 [ # # # # : 0 : Wasm_insist(*pred or refs == ref_t(0), "predication dummy must always be unoccupied");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1747 : :
1748 : : /*----- Set flag to indicate insertion. -----*/
1749 [ # # # # : 0 : entry_inserted = true;
# # # # ]
1750 : :
1751 : : /*----- Update reference count of this bucket. -----*/
1752 [ # # # # : 0 : Wasm_insist(reference_count(bucket) <= refs, "reference count must increase if unoccupied slot is found");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1753 [ # # # # : 0 : reference_count(bucket) = refs + ref_t(1); // no pred. special case since bucket equals slot if dummy is used
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1754 : :
1755 : : /*----- Iff no predication is used or predicate is fulfilled, set slot as occupied. -----*/
1756 [ # # # # : 0 : reference_count(slot) = pred ? pred->to<ref_t>() : PrimitiveExpr<ref_t>(1);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1757 : :
1758 : : /*----- Update number of entries. -----*/
1759 [ # # # # : 0 : *num_entries_ += pred ? pred->to<uint32_t>() : U32x1(1);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1760 [ # # # # : 0 : Wasm_insist(*num_entries_ < capacity(), "at least one entry must always be unoccupied for lookups");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1761 : :
1762 : : /*----- Insert key. -----*/
1763 [ # # # # : 0 : insert_key(slot, std::move(key)); // move key at last use
# # # # #
# # # # #
# # ]
1764 : :
1765 : : if constexpr (not ValueInPlace) {
1766 : : /*----- Allocate memory for out-of-place values and set pointer to it. -----*/
1767 : : Ptr<void> ptr =
1768 [ # # # # : 0 : Module::Allocator().allocate(layout_.values_size_in_bytes_, layout_.values_max_alignment_in_bytes_);
# # # # #
# # # ]
1769 [ # # # # : 0 : *(slot + layout_.ptr_offset_in_bytes_).template to<uint32_t*>() = ptr.clone().to<uint32_t>();
# # # # #
# # # # #
# # # # #
# # # #
# ]
1770 : :
1771 [ # # # # ]: 0 : if (pred) {
1772 : : /*----- Store address and size of dummy predication entry to free them later. -----*/
1773 [ # # # # ]: 0 : var_t<Ptr<void>> ptr_; // create global variable iff `IsGlobal` to access it later for deallocation
1774 [ # # # # : 0 : ptr_ = ptr.clone();
# # # # ]
1775 [ # # # # ]: 0 : dummy_allocations_.emplace_back(ptr_, layout_.values_size_in_bytes_);
1776 : 0 : }
1777 : :
1778 [ # # # # ]: 0 : ptr.discard(); // since it was always cloned
1779 : 0 : }
1780 : : }
1781 : :
1782 : : /* GOTO from above jumps here */
1783 : :
1784 : : if constexpr (not ValueInPlace) {
1785 : : /*----- Set slot pointer to out-of-place values. -----*/
1786 [ # # # # : 0 : slot = *(slot + layout_.ptr_offset_in_bytes_).template to<uint32_t*>();
# # # # #
# # # # #
# # ]
1787 : : }
1788 : :
1789 : : /*----- Return entry handle containing all values and the flag whether an insertion was performed. -----*/
1790 [ # # # # : 0 : return { value_entry(slot), entry_inserted };
# # # # #
# # # # #
# # # # #
# # # #
# ]
1791 : 0 : }
1792 : :
1793 : : template<bool IsGlobal, bool ValueInPlace>
1794 : 0 : std::pair<HashTable::entry_t, Boolx1> OpenAddressingHashTable<IsGlobal, ValueInPlace>::find(std::vector<SQL_t> key,
1795 : : hint_t bucket_hint)
1796 : : {
1797 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1798 : :
1799 : : Ptr<void> bucket =
1800 [ # # # # : 0 : bucket_hint ? *bucket_hint : compute_bucket(clone(key)); // clone key since we need it again for comparison
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1801 : :
1802 : : /*----- Get reference count, i.e. occupied slots, of this bucket. -----*/
1803 [ # # # # : 0 : const Var<PrimitiveExpr<ref_t>> refs(reference_count(bucket.clone()));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1804 : :
1805 : : /*----- Probe slots, abort if end of bucket is reached or key already exists. -----*/
1806 [ # # # # : 0 : Var<Ptr<void>> slot(bucket);
# # # # ]
1807 [ # # # # : 0 : Var<PrimitiveExpr<ref_t>> steps(0);
# # # # ]
1808 [ # # # # : 0 : WHILE (steps != refs) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1809 [ # # # # : 0 : Wasm_insist(reference_count(slot) != ref_t(0), "slot in bucket list must be occupied");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1810 [ # # # # : 0 : BREAK(equal_key(slot, std::move(key))); // move key at last use
# # # # #
# # # # #
# # # # #
# # # #
# ]
1811 [ # # # # : 0 : steps += ref_t(1);
# # # # ]
1812 [ # # # # : 0 : Wasm_insist(steps <= *num_entries_, "probing strategy has to find unoccupied slot if there is one");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1813 [ # # # # : 0 : slot = probing_strategy().advance_to_next_slot(slot, steps);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1814 [ # # # # : 0 : Wasm_insist(begin() <= slot and slot < end(), "slot out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1815 : : }
1816 : :
1817 : : /*----- Key is found iff end of bucket is reached. -----*/
1818 [ # # # # : 0 : Boolx1 key_found = steps != refs;
# # # # ]
1819 : :
1820 : : if constexpr (not ValueInPlace) {
1821 : : /*----- Set slot pointer to out-of-place values. -----*/
1822 [ # # # # : 0 : slot = *(slot + layout_.ptr_offset_in_bytes_).template to<uint32_t*>();
# # # # #
# # # # #
# # ]
1823 : : }
1824 : :
1825 : : /*----- Return entry handle containing both keys and values and the flag whether key was found. -----*/
1826 [ # # # # : 0 : return { value_entry(slot), key_found };
# # # # #
# # # # #
# # # # #
# # # #
# ]
1827 : 0 : }
1828 : :
1829 : : template<bool IsGlobal, bool ValueInPlace>
1830 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::for_each(callback_t Pipeline) const
1831 : : {
1832 : : /*----- Iterate over all entries and call pipeline (with entry handle argument) on occupied ones. -----*/
1833 [ # # # # : 0 : Var<Ptr<void>> it(begin());
# # # # ]
1834 [ # # # # : 0 : WHILE (it != end()) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1835 [ # # # # : 0 : Wasm_insist(begin() <= it and it < end(), "entry out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1836 [ # # # # : 0 : IF (reference_count(it) != ref_t(0)) { // occupied
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1837 [ # # # # : 0 : Pipeline(entry(it));
# # # # #
# # # # #
# # ]
1838 : 0 : };
1839 [ # # # # : 0 : it += int32_t(entry_size_in_bytes_);
# # # # ]
1840 : : }
1841 : 0 : }
1842 : :
1843 : : template<bool IsGlobal, bool ValueInPlace>
1844 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::for_each_in_equal_range(std::vector<SQL_t> key,
1845 : : callback_t Pipeline,
1846 : : bool predicated,
1847 : : hint_t bucket_hint) const
1848 : : {
1849 : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
1850 : :
1851 : : Ptr<void> bucket =
1852 [ # # # # : 0 : bucket_hint ? *bucket_hint : compute_bucket(clone(key)); // clone key since we need it again for comparison
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1853 : :
1854 : : /*----- Get reference count, i.e. occupied slots, of this bucket. -----*/
1855 [ # # # # : 0 : const Var<PrimitiveExpr<ref_t>> refs(reference_count(bucket.clone()));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1856 : :
1857 : : /*----- Iterate over slots and call pipeline (with entry handle argument) on matches with the given key. -----*/
1858 [ # # # # : 0 : Var<Ptr<void>> slot(bucket);
# # # # ]
1859 [ # # # # : 0 : Var<PrimitiveExpr<ref_t>> steps(0);
# # # # ]
1860 [ # # # # : 0 : WHILE (steps != refs) { // end of bucket not reached
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1861 [ # # # # : 0 : Wasm_insist(reference_count(slot) != ref_t(0), "slot in bucket list must be occupied");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1862 [ # # # # : 0 : if (predicated) {
# # # # ]
1863 [ # # # # : 0 : CodeGenContext::Get().env().add_predicate(equal_key(slot, std::move(key)));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1864 [ # # # # : 0 : Pipeline(entry(slot));
# # # # #
# # # # #
# # # # #
# # # #
# ]
1865 : 0 : } else {
1866 [ # # # # : 0 : IF (equal_key(slot, std::move(key))) { // match found
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1867 [ # # # # : 0 : Pipeline(entry(slot));
# # # # #
# # # # #
# # ]
1868 : 0 : };
1869 : : }
1870 [ # # # # : 0 : steps += ref_t(1);
# # # # ]
1871 [ # # # # : 0 : Wasm_insist(steps <= *num_entries_, "probing strategy has to find unoccupied slot if there is one");
# # # # #
# # # # #
# # # # #
# # # #
# ]
1872 [ # # # # : 0 : slot = probing_strategy().advance_to_next_slot(slot, steps);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1873 [ # # # # : 0 : Wasm_insist(begin() <= slot and slot < end(), "slot out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1874 : : }
1875 : 0 : }
1876 : :
1877 : : template<bool IsGlobal, bool ValueInPlace>
1878 : 0 : HashTable::entry_t OpenAddressingHashTable<IsGlobal, ValueInPlace>::dummy_entry()
1879 : : {
1880 : : if constexpr (ValueInPlace) {
1881 : : /*----- Allocate memory for a dummy slot. -----*/
1882 : 0 : var_t<Ptr<void>> slot; // create global variable iff `IsGlobal` to be able to access it later for deallocation
1883 [ # # # # : 0 : slot = Module::Allocator().allocate(entry_size_in_bytes_, entry_max_alignment_in_bytes_);
# # # # #
# # # ]
1884 : :
1885 : : /*----- Store address and size of dummy slot to free them later. -----*/
1886 [ # # # # ]: 0 : dummy_allocations_.emplace_back(slot, entry_size_in_bytes_);
1887 : :
1888 : : /*----- Return *local* entry handle containing all values. -----*/
1889 [ # # # # : 0 : return value_entry(M_CONSTEXPR_COND(IsGlobal, Var<Ptr<void>>(slot.val()).val(), slot.val()));
# # # # #
# # # ]
1890 : 0 : } else {
1891 : : /*----- Allocate memory for out-of-place dummy values. -----*/
1892 : 0 : var_t<Ptr<void>> ptr; // create global variable iff `IsGlobal` to be able to access it later for deallocation
1893 [ # # # # : 0 : ptr = Module::Allocator().allocate(layout_.values_size_in_bytes_, layout_.values_max_alignment_in_bytes_);
# # # # #
# # # ]
1894 : :
1895 : : /*----- Store address and size of dummy values to free them later. -----*/
1896 [ # # # # ]: 0 : dummy_allocations_.emplace_back(ptr, layout_.values_size_in_bytes_);
1897 : :
1898 : : /*----- Return *local* entry handle containing all values. -----*/
1899 [ # # # # : 0 : return value_entry(M_CONSTEXPR_COND(IsGlobal, Var<Ptr<void>>(ptr.val()).val(), ptr.val()));
# # # # #
# # # ]
1900 : 0 : }
1901 : 0 : }
1902 : :
1903 : : template<bool IsGlobal, bool ValueInPlace>
1904 : 0 : Boolx1 OpenAddressingHashTable<IsGlobal, ValueInPlace>::equal_key(Ptr<void> slot, std::vector<SQL_t> key) const
1905 : : {
1906 : 0 : Var<Boolx1> res(true);
1907 : :
1908 [ # # # # : 0 : const auto off_null_bitmap = M_CONSTEXPR_COND(ValueInPlace, layout_.null_bitmap_offset_in_bytes_,
# # # # ]
1909 : : layout_.keys_null_bitmap_offset_in_bytes_);
1910 [ # # # # : 0 : for (std::size_t i = 0; i < key_indices_.size(); ++i) {
# # # # ]
1911 : : /* do not skip duplicated comparison of the same slot since probing might need this comparison */
1912 : :
1913 [ # # # # : 0 : auto &e = schema_.get()[key_indices_[i]];
# # # # ]
1914 [ # # # # : 0 : const auto idx = [&](){
# # # # ]
1915 : : if constexpr (ValueInPlace) {
1916 : 0 : return key_indices_[i];
1917 : : } else { // return number of indices in [0, key_indices_[i]) that are part of key
1918 : 0 : std::size_t count = 0;
1919 [ # # # # ]: 0 : for (index_t idx = 0; idx != key_indices_[i]; ++idx)
1920 : 0 : count += contains(key_indices_, idx);
1921 : 0 : return count;
1922 : : }
1923 : : }();
1924 [ # # # # : 0 : const auto off = M_CONSTEXPR_COND(ValueInPlace, layout_.entry_offsets_in_bytes_[idx],
# # # # ]
1925 : : layout_.key_offsets_in_bytes_[idx]);
1926 : 0 : auto compare_equal = [&]<typename T>() {
1927 : : using type = typename T::type;
1928 : 0 : M_insist(std::holds_alternative<T>(key[i]));
1929 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
1930 [ # # # # : 0 : const_reference_t<T> ref((slot.clone() + off).template to<type*>(), slot.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1931 [ # # # # : 0 : res = res and ref == *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1932 : 0 : } else { // entry must not be NULL
1933 [ # # # # : 0 : const_reference_t<T> ref((slot.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
1934 [ # # # # : 0 : res = res and ref == *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
1935 : 0 : }
1936 : 0 : };
1937 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
1938 : 0 : [&](const Boolean&) { compare_equal.template operator()<_Boolx1>(); },
1939 : 0 : [&](const Numeric &n) {
1940 [ # # # # : 0 : switch (n.kind) {
# # # # #
# # # ]
1941 : : case Numeric::N_Int:
1942 : : case Numeric::N_Decimal:
1943 [ # # # # : 0 : switch (n.size()) {
# # # # #
# # # # #
# # # # #
# ]
1944 : 0 : default: M_unreachable("invalid size");
1945 : 0 : case 8: compare_equal.template operator()<_I8x1 >(); break;
1946 : 0 : case 16: compare_equal.template operator()<_I16x1>(); break;
1947 : 0 : case 32: compare_equal.template operator()<_I32x1>(); break;
1948 : 0 : case 64: compare_equal.template operator()<_I64x1>(); break;
1949 : : }
1950 : 0 : break;
1951 : : case Numeric::N_Float:
1952 [ # # # # : 0 : if (n.size() <= 32)
# # # # ]
1953 : 0 : compare_equal.template operator()<_Floatx1>();
1954 : : else
1955 : 0 : compare_equal.template operator()<_Doublex1>();
1956 : 0 : }
1957 : 0 : },
1958 : 0 : [&](const CharacterSequence &cs) {
1959 : 0 : M_insist(std::holds_alternative<NChar>(key[i]));
1960 [ # # # # : 0 : NChar val((slot.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1961 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # ]
1962 [ # # # # : 0 : const_reference_t<NChar> ref(val, slot.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1963 [ # # # # : 0 : res = res and ref == *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1964 : 0 : } else { // entry must not be NULL
1965 [ # # # # : 0 : const_reference_t<NChar> ref(val);
# # # # #
# # # # #
# # ]
1966 [ # # # # : 0 : res = res and ref == *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
1967 : 0 : }
1968 : 0 : },
1969 : 0 : [&](const Date&) { compare_equal.template operator()<_I32x1>(); },
1970 : 0 : [&](const DateTime&) { compare_equal.template operator()<_I64x1>(); },
1971 : 0 : [](auto&&) { M_unreachable("invalid type"); },
1972 : 0 : }, *e.type);
1973 : 0 : }
1974 : :
1975 [ # # # # : 0 : slot.discard(); // since it was always cloned
# # # # ]
1976 : :
1977 [ # # # # : 0 : return res;
# # # # ]
1978 : 0 : }
1979 : :
1980 : : template<bool IsGlobal, bool ValueInPlace>
1981 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::insert_key(Ptr<void> slot, std::vector<SQL_t> key)
1982 : : {
1983 : 0 : const auto off_null_bitmap = M_CONSTEXPR_COND(ValueInPlace, layout_.null_bitmap_offset_in_bytes_,
1984 : : layout_.keys_null_bitmap_offset_in_bytes_);
1985 [ # # # # : 0 : for (std::size_t i = 0; i < key_indices_.size(); ++i) {
# # # # ]
1986 : : /* NOTE: `std::find` results in quadratic complexity but we expect rather short keys anyway */
1987 [ # # # # : 0 : if (std::find(key_indices_.begin(), key_indices_.begin() + i, key_indices_[i]) != key_indices_.begin() + i) {
# # # # ]
1988 : 0 : discard(key[i]);
1989 : 0 : continue; // skip duplicated writing of the same slot
1990 : : }
1991 : :
1992 : 0 : auto &e = schema_.get()[key_indices_[i]];
1993 : 0 : const auto idx = [&](){
1994 : : if constexpr (ValueInPlace) {
1995 : 0 : return key_indices_[i];
1996 : : } else { // return number of indices in [0, key_indices_[i]) that are part of key
1997 : 0 : std::size_t count = 0;
1998 [ # # # # ]: 0 : for (index_t idx = 0; idx != key_indices_[i]; ++idx)
1999 : 0 : count += contains(key_indices_, idx);
2000 : 0 : return count;
2001 : : }
2002 : : }();
2003 : 0 : const auto off = M_CONSTEXPR_COND(ValueInPlace, layout_.entry_offsets_in_bytes_[idx],
2004 : : layout_.key_offsets_in_bytes_[idx]);
2005 : 0 : auto insert = [&]<typename T>() {
2006 : : using type = typename T::type;
2007 : 0 : M_insist(std::holds_alternative<T>(key[i]));
2008 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
2009 [ # # # # : 0 : reference_t<T> ref((slot.clone() + off).template to<type*>(), slot.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2010 [ # # # # : 0 : ref = *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2011 : 0 : } else { // entry must not be NULL
2012 [ # # # # : 0 : reference_t<T> ref((slot.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
2013 [ # # # # : 0 : ref = *std::get_if<T>(&key[i]);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2014 : 0 : }
2015 : 0 : };
2016 : 0 : visit(overloaded {
2017 : 0 : [&](const Boolean&) { insert.template operator()<_Boolx1>(); },
2018 : 0 : [&](const Numeric &n) {
2019 [ # # # # : 0 : switch (n.kind) {
# # # # #
# # # ]
2020 : : case Numeric::N_Int:
2021 : : case Numeric::N_Decimal:
2022 [ # # # # : 0 : switch (n.size()) {
# # # # #
# # # # #
# # # # #
# ]
2023 : 0 : default: M_unreachable("invalid size");
2024 : 0 : case 8: insert.template operator()<_I8x1 >(); break;
2025 : 0 : case 16: insert.template operator()<_I16x1>(); break;
2026 : 0 : case 32: insert.template operator()<_I32x1>(); break;
2027 : 0 : case 64: insert.template operator()<_I64x1>(); break;
2028 : : }
2029 : 0 : break;
2030 : : case Numeric::N_Float:
2031 [ # # # # : 0 : if (n.size() <= 32)
# # # # ]
2032 : 0 : insert.template operator()<_Floatx1>();
2033 : : else
2034 : 0 : insert.template operator()<_Doublex1>();
2035 : 0 : }
2036 : 0 : },
2037 : 0 : [&](const CharacterSequence &cs) {
2038 : 0 : M_insist(std::holds_alternative<NChar>(key[i]));
2039 [ # # # # : 0 : NChar val((slot.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2040 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # ]
2041 [ # # # # : 0 : reference_t<NChar> ref(val, slot.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2042 [ # # # # : 0 : ref = *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # ]
2043 : 0 : } else { // entry must not be NULL
2044 [ # # # # : 0 : reference_t<NChar> ref(val);
# # # # #
# # # # #
# # ]
2045 [ # # # # : 0 : ref = *std::get_if<NChar>(&key[i]);
# # # # #
# # # # #
# # ]
2046 : 0 : }
2047 : 0 : },
2048 : 0 : [&](const Date&) { insert.template operator()<_I32x1>(); },
2049 : 0 : [&](const DateTime&) { insert.template operator()<_I64x1>(); },
2050 : 0 : [](auto&&) { M_unreachable("invalid type"); },
2051 : 0 : }, *e.type);
2052 : 0 : }
2053 : :
2054 : 0 : slot.discard(); // since it was always cloned
2055 : 0 : }
2056 : :
2057 : : template<bool IsGlobal, bool ValueInPlace>
2058 : 0 : HashTable::entry_t OpenAddressingHashTable<IsGlobal, ValueInPlace>::value_entry(Ptr<void> ptr) const
2059 : : {
2060 : 0 : entry_t value_entry;
2061 : :
2062 [ # # # # : 0 : const auto off_null_bitmap = M_CONSTEXPR_COND(ValueInPlace, layout_.null_bitmap_offset_in_bytes_,
# # # # ]
2063 : : layout_.values_null_bitmap_offset_in_bytes_);
2064 [ # # # # : 0 : for (std::size_t i = 0; i < value_indices_.size(); ++i) {
# # # # ]
2065 : : /* there are no duplicates in the value indexes */
2066 : :
2067 [ # # # # : 0 : auto &e = schema_.get()[value_indices_[i]];
# # # # ]
2068 [ # # # # : 0 : const auto idx = [&](){
# # # # ]
2069 : : if constexpr (ValueInPlace) {
2070 : 0 : return value_indices_[i];
2071 : : } else { // return number of indices in [0, value_indices_[i]) that are part of value
2072 : 0 : std::size_t count = 0;
2073 [ # # # # ]: 0 : for (index_t idx = 0; idx != value_indices_[i]; ++idx)
2074 : 0 : count += contains(value_indices_, idx);
2075 : 0 : return count;
2076 : : }
2077 : : }();
2078 [ # # # # : 0 : const auto off = M_CONSTEXPR_COND(ValueInPlace, layout_.entry_offsets_in_bytes_[idx],
# # # # ]
2079 : : layout_.value_offsets_in_bytes_[idx]);
2080 : 0 : auto add = [&]<typename T>() {
2081 : : using type = typename T::type;
2082 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
2083 [ # # # # : 0 : reference_t<T> ref((ptr.clone() + off).template to<type*>(), ptr.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2084 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2085 : 0 : } else { // entry must not be NULL
2086 [ # # # # : 0 : reference_t<T> ref((ptr.clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
2087 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2088 : 0 : }
2089 : 0 : };
2090 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2091 : 0 : [&](const Boolean&) { add.template operator()<_Boolx1>(); },
2092 : 0 : [&](const Numeric &n) {
2093 [ # # # # : 0 : switch (n.kind) {
# # # # #
# # # ]
2094 : : case Numeric::N_Int:
2095 : : case Numeric::N_Decimal:
2096 [ # # # # : 0 : switch (n.size()) {
# # # # #
# # # # #
# # # # #
# ]
2097 : 0 : default: M_unreachable("invalid size");
2098 : 0 : case 8: add.template operator()<_I8x1 >(); break;
2099 : 0 : case 16: add.template operator()<_I16x1>(); break;
2100 : 0 : case 32: add.template operator()<_I32x1>(); break;
2101 : 0 : case 64: add.template operator()<_I64x1>(); break;
2102 : : }
2103 : 0 : break;
2104 : : case Numeric::N_Float:
2105 [ # # # # : 0 : if (n.size() <= 32)
# # # # ]
2106 : 0 : add.template operator()<_Floatx1>();
2107 : : else
2108 : 0 : add.template operator()<_Doublex1>();
2109 : 0 : }
2110 : 0 : },
2111 : 0 : [&](const CharacterSequence &cs) {
2112 [ # # # # : 0 : NChar val((ptr.clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2113 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # ]
2114 [ # # # # : 0 : reference_t<NChar> ref(val, ptr.clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2115 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # ]
2116 : 0 : } else { // entry must not be NULL
2117 [ # # # # : 0 : reference_t<NChar> ref(val);
# # # # #
# # # # #
# # ]
2118 [ # # # # : 0 : value_entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # ]
2119 : 0 : }
2120 : 0 : },
2121 : 0 : [&](const Date&) { add.template operator()<_I32x1>(); },
2122 : 0 : [&](const DateTime&) { add.template operator()<_I64x1>(); },
2123 : 0 : [](auto&&) { M_unreachable("invalid type"); },
2124 : 0 : }, *e.type);
2125 : 0 : }
2126 : :
2127 [ # # # # : 0 : ptr.discard(); // since it was always cloned
# # # # ]
2128 : :
2129 : 0 : return value_entry;
2130 [ # # # # : 0 : }
# # # # ]
2131 : :
2132 : : template<bool IsGlobal, bool ValueInPlace>
2133 : 0 : HashTable::const_entry_t OpenAddressingHashTable<IsGlobal, ValueInPlace>::entry(Ptr<void> slot) const
2134 : : {
2135 : 0 : const_entry_t entry;
2136 : :
2137 : 0 : std::unique_ptr<Ptr<void>> value; ///< pointer to out-of-place values
2138 : : if constexpr (not ValueInPlace) {
2139 [ # # # # : 0 : const Var<Ptr<void>> value_(*(slot.clone() + layout_.ptr_offset_in_bytes_).template to<uint32_t*>());
# # # # #
# # # # #
# # # # #
# ]
2140 [ # # # # ]: 0 : value = std::make_unique<Ptr<void>>(value_);
2141 : 0 : }
2142 : :
2143 : 0 : auto ptr = &slot;
2144 [ # # # # : 0 : auto off_null_bitmap = M_CONSTEXPR_COND(ValueInPlace, layout_.null_bitmap_offset_in_bytes_,
# # # # ]
2145 : : layout_.keys_null_bitmap_offset_in_bytes_);
2146 [ # # # # : 0 : for (std::size_t i = 0; i < key_indices_.size() + value_indices_.size(); ++i) {
# # # # ]
2147 : : if constexpr (not ValueInPlace) {
2148 [ # # # # ]: 0 : if (i == key_indices_.size()) {
2149 : : /* If end of key is reached, switch variables to out-of-place value entries. */
2150 [ # # # # ]: 0 : M_insist(bool(value));
2151 : 0 : ptr = &*value;
2152 : 0 : off_null_bitmap = layout_.values_null_bitmap_offset_in_bytes_;
2153 : 0 : }
2154 : : }
2155 : :
2156 : 0 : const bool is_key = i < key_indices_.size();
2157 : : /* NOTE: `std::find` results in quadratic complexity but we expect rather short keys anyway */
2158 [ # # # # : 0 : if (is_key and std::find(key_indices_.begin(), key_indices_.begin() + i, key_indices_[i]) != key_indices_.begin() + i)
# # # # #
# # # # #
# # # # #
# # # #
# ]
2159 : 0 : continue; // skip duplicated key to the same slot
2160 : :
2161 [ # # # # : 0 : const auto schema_idx = is_key ? key_indices_[i] : value_indices_[i - key_indices_.size()];
# # # # ]
2162 [ # # # # : 0 : auto &e = schema_.get()[schema_idx];
# # # # ]
2163 [ # # # # : 0 : const auto idx = [&](){
# # # # ]
2164 : : if constexpr (ValueInPlace) {
2165 : 0 : return schema_idx;
2166 : : } else { // return number of indices in [0, schema_idx) that are part of key or rather value
2167 : 0 : std::size_t count = 0;
2168 [ # # # # ]: 0 : for (index_t idx = 0; idx != schema_idx; ++idx)
2169 [ # # # # ]: 0 : count += is_key ? contains(key_indices_, idx) : contains(value_indices_, idx);
2170 : 0 : return count;
2171 : : }
2172 : : }();
2173 : 0 : const auto off =
2174 [ # # # # : 0 : M_CONSTEXPR_COND(ValueInPlace,
# # # # #
# # # ]
2175 : : layout_.entry_offsets_in_bytes_[idx],
2176 : : is_key ? layout_.key_offsets_in_bytes_[idx] : layout_.value_offsets_in_bytes_[idx]);
2177 : 0 : auto add = [&]<typename T>() {
2178 : : using type = typename T::type;
2179 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # ]
2180 [ # # # # : 0 : const_reference_t<T> ref((ptr->clone() + off).template to<type*>(), ptr->clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2181 [ # # # # : 0 : entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2182 : 0 : } else { // entry must not be NULL
2183 [ # # # # : 0 : const_reference_t<T> ref((ptr->clone() + off).template to<type*>());
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # ]
2184 [ # # # # : 0 : entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2185 : 0 : }
2186 : 0 : };
2187 [ # # # # : 0 : visit(overloaded {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2188 : 0 : [&](const Boolean&) { add.template operator()<_Boolx1>(); },
2189 : 0 : [&](const Numeric &n) {
2190 [ # # # # : 0 : switch (n.kind) {
# # # # #
# # # ]
2191 : : case Numeric::N_Int:
2192 : : case Numeric::N_Decimal:
2193 [ # # # # : 0 : switch (n.size()) {
# # # # #
# # # # #
# # # # #
# ]
2194 : 0 : default: M_unreachable("invalid size");
2195 : 0 : case 8: add.template operator()<_I8x1 >(); break;
2196 : 0 : case 16: add.template operator()<_I16x1>(); break;
2197 : 0 : case 32: add.template operator()<_I32x1>(); break;
2198 : 0 : case 64: add.template operator()<_I64x1>(); break;
2199 : : }
2200 : 0 : break;
2201 : : case Numeric::N_Float:
2202 [ # # # # : 0 : if (n.size() <= 32)
# # # # ]
2203 : 0 : add.template operator()<_Floatx1>();
2204 : : else
2205 : 0 : add.template operator()<_Doublex1>();
2206 : 0 : }
2207 : 0 : },
2208 : 0 : [&](const CharacterSequence &cs) {
2209 [ # # # # : 0 : NChar val((ptr->clone() + off).template to<char*>(), e.nullable(), &cs);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2210 [ # # # # : 0 : if (e.nullable()) { // entry may be NULL
# # # # #
# # # # #
# # ]
2211 [ # # # # : 0 : const_reference_t<NChar> ref(val, ptr->clone() + off_null_bitmap, idx);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2212 [ # # # # : 0 : entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # ]
2213 : 0 : } else { // entry must not be NULL
2214 [ # # # # : 0 : const_reference_t<NChar> ref(val);
# # # # #
# # # # #
# # ]
2215 [ # # # # : 0 : entry.add(e.id, std::move(ref));
# # # # #
# # # # #
# # ]
2216 : 0 : }
2217 : 0 : },
2218 : 0 : [&](const Date&) { add.template operator()<_I32x1>(); },
2219 : 0 : [&](const DateTime&) { add.template operator()<_I64x1>(); },
2220 : 0 : [](auto&&) { M_unreachable("invalid type"); },
2221 : 0 : }, *e.type);
2222 : 0 : }
2223 : :
2224 [ # # # # : 0 : slot.discard(); // since it was always cloned
# # # # ]
2225 [ # # # # : 0 : if (value) value->discard(); // since it was always cloned
# # # # #
# # # # #
# # ]
2226 : :
2227 : 0 : return entry;
2228 [ # # # # : 0 : }
# # # # ]
2229 : :
2230 : : template<bool IsGlobal, bool ValueInPlace>
2231 : 0 : void OpenAddressingHashTable<IsGlobal, ValueInPlace>::rehash()
2232 : : {
2233 [ # # # # : 0 : if (options::insist_no_rehashing)
# # # # ]
2234 : 0 : Throw(exception::unreachable, "rehashing must not occur");
2235 : :
2236 : 0 : auto emit_rehash = [this](){
2237 : 0 : auto S = CodeGenContext::Get().scoped_environment(); // fresh environment to remove predication while rehashing
2238 : :
2239 [ # # # # : 0 : M_insist(bool(address_), "must call `setup()` before");
# # # # ]
2240 [ # # # # : 0 : M_insist(bool(mask_), "must call `setup()` before");
# # # # ]
2241 [ # # # # : 0 : M_insist(bool(num_entries_), "must call `setup()` before");
# # # # ]
2242 : :
2243 : : /*----- Store old begin and end (since they will be overwritten). -----*/
2244 [ # # # # : 0 : const Var<Ptr<void>> begin_old(begin());
# # # # #
# # # # #
# # ]
2245 [ # # # # : 0 : const Var<Ptr<void>> end_old(end());
# # # # #
# # # # #
# # ]
2246 : :
2247 : : /*----- Double capacity. -----*/
2248 [ # # # # : 0 : *mask_ = (*mask_ << 1U) + 1U;
# # # # #
# # # # #
# # # # #
# # # #
# ]
2249 : :
2250 : : /*----- Allocate memory for new hash table with updated capacity. -----*/
2251 [ # # # # : 0 : *address_ = Module::Allocator().allocate(size_in_bytes(), entry_max_alignment_in_bytes_);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2252 : :
2253 : : /*----- Clear newly created hash table. -----*/
2254 [ # # # # : 0 : clear();
# # # # ]
2255 : :
2256 : : #ifndef NDEBUG
2257 : : /*----- Store old number of entries. -----*/
2258 [ # # # # : 0 : const Var<U32x1> num_entries_old(*num_entries_);
# # # # ]
2259 : : #endif
2260 : :
2261 : : /*----- Reset number of entries (since they will be incremented at each insertion into the new hash table). --*/
2262 [ # # # # : 0 : *num_entries_ = 0U;
# # # # ]
2263 : :
2264 : : /*----- Insert each element from old hash table into new one. -----*/
2265 [ # # # # : 0 : Var<Ptr<void>> it(begin_old.val());
# # # # #
# # # # #
# # ]
2266 [ # # # # : 0 : WHILE (it != end_old) {
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2267 [ # # # # : 0 : Wasm_insist(begin_old <= it and it < end_old, "entry out-of-bounds");
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# ]
2268 [ # # # # : 0 : IF (reference_count(it) != ref_t(0)) { // entry in old hash table is occupied
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2269 [ # # # # : 0 : auto e_old = entry(it);
# # # # ]
2270 : :
2271 : : /*----- Access key from old entry. -----*/
2272 : 0 : std::vector<SQL_t> key;
2273 [ # # # # : 0 : for (auto k : key_indices_) {
# # # # ]
2274 [ # # # # : 0 : std::visit(overloaded {
# # # # ]
2275 : 0 : [&](auto &&r) -> void { key.emplace_back(r); },
2276 : 0 : [](std::monostate) -> void { M_unreachable("invalid reference"); },
2277 [ # # # # : 0 : }, e_old.get(schema_.get()[k].id));
# # # # #
# # # # #
# # ]
2278 : : }
2279 : :
2280 : : /*----- Insert key into new hash table. No rehashing needed since the new hash table is large enough. */
2281 [ # # # # : 0 : auto slot = emplace_without_rehashing(std::move(key));
# # # # ]
2282 : :
2283 : : if constexpr (ValueInPlace) {
2284 : : /*----- Get entry handle containing all values of new entry. -----*/
2285 [ # # # # : 0 : auto e_new = value_entry(slot);
# # # # ]
2286 : :
2287 : : /*----- Insert values from old entry into new one. -----*/
2288 [ # # # # ]: 0 : for (auto v : value_indices_) {
2289 [ # # # # : 0 : auto id = schema_.get()[v].id;
# # # # ]
2290 [ # # # # ]: 0 : std::visit(overloaded {
2291 [ # # # # : 0 : [&]<sql_type T>(reference_t<T> &&r) -> void { r = e_old.template extract<T>(id); },
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # #
# ]
2292 : 0 : [](std::monostate) -> void { M_unreachable("invalid reference"); },
2293 [ # # # # ]: 0 : }, e_new.extract(id));
2294 : 0 : }
2295 [ # # # # : 0 : M_insist(e_new.empty());
# # ]
2296 : 0 : } else {
2297 : : /*----- Set pointer to out-of-place values of new entry to the one of old entry. -----*/
2298 [ # # # # : 0 : *(slot + layout_.ptr_offset_in_bytes_).template to<uint32_t*>() =
# # # # #
# # # # #
# # ]
2299 [ # # # # : 0 : *(it + layout_.ptr_offset_in_bytes_).template to<uint32_t*>();
# # # # #
# # # ]
2300 : : }
2301 : 0 : };
2302 : :
2303 : : /*----- Advance to next entry in old hash table. -----*/
2304 [ # # # # : 0 : it += int32_t(entry_size_in_bytes_);
# # # # ]
2305 : : }
2306 : :
2307 : : #ifndef NDEBUG
2308 [ # # # # : 0 : Wasm_insist(*num_entries_ == num_entries_old, "number of entries of old and new hash table do not match");
# # # # #
# # # # #
# # # # #
# # # #
# ]
2309 : : #endif
2310 : :
2311 : : /*----- Free old hash table. -----*/
2312 [ # # # # : 0 : U32x1 size = (end_old - begin_old).make_unsigned();
# # # # #
# # # # #
# # ]
2313 [ # # # # : 0 : Module::Allocator().deallocate(begin_old, size);
# # # # #
# # # # #
# # # # #
# # # # #
# # # # #
# # # ]
2314 : 0 : };
2315 : :
2316 : : if constexpr (IsGlobal) {
2317 [ # # # # ]: 0 : if (not rehash_) {
2318 : : /*----- Backup former local variables to be able to use new ones for rehashing function. -----*/
2319 : 0 : auto old_address = std::exchange(address_, std::nullopt);
2320 [ # # # # ]: 0 : auto old_mask = std::exchange(mask_, std::nullopt);
2321 [ # # # # ]: 0 : auto old_num_entries = std::exchange(num_entries_, std::nullopt);
2322 [ # # # # ]: 0 : auto old_high_watermark_absolute = std::exchange(high_watermark_absolute_, std::nullopt);
2323 : :
2324 : : /*----- Create function for rehashing. -----*/
2325 [ # # # # : 0 : FUNCTION(rehash, void(void))
# # # # #
# # # # #
# # ]
2326 : : {
2327 : : /*----- Perform setup for local variables. -----*/
2328 [ # # # # ]: 0 : address_.emplace(storage_.address_);
2329 [ # # # # ]: 0 : mask_.emplace(storage_.mask_);
2330 [ # # # # ]: 0 : num_entries_.emplace(storage_.num_entries_);
2331 [ # # # # ]: 0 : high_watermark_absolute_.emplace(storage_.high_watermark_absolute_);
2332 : :
2333 [ # # # # ]: 0 : emit_rehash();
2334 : :
2335 : : /*----- Perform teardown for local variables. -----*/
2336 [ # # # # ]: 0 : storage_.address_ = *address_;
2337 [ # # # # ]: 0 : storage_.mask_ = *mask_;
2338 [ # # # # ]: 0 : storage_.num_entries_ = *num_entries_;
2339 [ # # # # ]: 0 : storage_.high_watermark_absolute_ = *high_watermark_absolute_;
2340 : 0 : address_.reset();
2341 : 0 : mask_.reset();
2342 : 0 : num_entries_.reset();
2343 : 0 : high_watermark_absolute_.reset();
2344 : : }
2345 : 0 : rehash_ = std::move(rehash);
2346 : :
2347 : : /*----- Restore local variables. -----*/
2348 [ # # # # ]: 0 : std::exchange(address_, std::move(old_address));
2349 [ # # # # ]: 0 : std::exchange(mask_, std::move(old_mask));
2350 [ # # # # ]: 0 : std::exchange(num_entries_, std::move(old_num_entries));
2351 [ # # # # ]: 0 : std::exchange(high_watermark_absolute_, std::move(old_high_watermark_absolute));
2352 : 0 : }
2353 : :
2354 : : /*----- Store local variables in global backups. -----*/
2355 : 0 : storage_.address_ = *address_;
2356 : 0 : storage_.mask_ = *mask_;
2357 : 0 : storage_.num_entries_ = *num_entries_;
2358 : 0 : storage_.high_watermark_absolute_ = *high_watermark_absolute_;
2359 : :
2360 : : /*----- Call rehashing function. ------*/
2361 : 0 : M_insist(bool(rehash_));
2362 : 0 : (*rehash_)();
2363 : :
2364 : : /*----- Restore local variables from global backups. -----*/
2365 : 0 : *address_ = storage_.address_;
2366 : 0 : *mask_ = storage_.mask_;
2367 : 0 : *num_entries_ = storage_.num_entries_;
2368 : 0 : *high_watermark_absolute_ = storage_.high_watermark_absolute_;
2369 : : } else {
2370 : : /*----- Emit rehashing code. ------*/
2371 : 0 : emit_rehash();
2372 : : }
2373 : 0 : }
2374 : :
2375 : : // explicit instantiations to prevent linker errors
2376 : : template struct m::wasm::OpenAddressingHashTable<false, false>;
2377 : : template struct m::wasm::OpenAddressingHashTable<false, true>;
2378 : : template struct m::wasm::OpenAddressingHashTable<true, false>;
2379 : : template struct m::wasm::OpenAddressingHashTable<true, true>;
2380 : :
2381 : :
2382 : : /*----- probing strategies for open addressing hash tables -----------------------------------------------------------*/
2383 : :
2384 : 0 : Ptr<void> LinearProbing::skip_slots(Ptr<void> bucket, U32x1 skips) const
2385 : : {
2386 [ # # # # : 0 : Wasm_insist(skips.clone() < ht_.capacity());
# # ]
2387 [ # # # # : 0 : const Var<Ptr<void>> slot(bucket + (skips * ht_.entry_size_in_bytes()).make_signed());
# # ]
2388 [ # # # # : 0 : Wasm_insist(slot < ht_.end() + ht_.size_in_bytes().make_signed());
# # # # #
# # # #
# ]
2389 [ # # # # : 0 : return Select(slot < ht_.end(), slot, slot - ht_.size_in_bytes().make_signed());
# # # # #
# # # ]
2390 : 0 : }
2391 : :
2392 : 0 : Ptr<void> LinearProbing::advance_to_next_slot(Ptr<void> slot, U32x1 current_step) const
2393 : : {
2394 : 0 : current_step.discard(); // not needed for linear probing
2395 : :
2396 [ # # ]: 0 : const Var<Ptr<void>> next(slot + ht_.entry_size_in_bytes());
2397 [ # # # # : 0 : Wasm_insist(next <= ht_.end());
# # # # ]
2398 [ # # # # : 0 : return Select(next < ht_.end(), next, ht_.begin());
# # # # ]
2399 : 0 : }
2400 : :
2401 : 0 : Ptr<void> QuadraticProbing::skip_slots(Ptr<void> bucket, U32x1 skips) const
2402 : : {
2403 : 0 : auto skips_cloned = skips.clone();
2404 [ # # # # : 0 : U32x1 slots_skipped = (skips_cloned * (skips + 1U)) >> 1U; // compute gaussian sum
# # ]
2405 [ # # # # ]: 0 : U32x1 slots_skipped_mod = slots_skipped bitand ht_.mask(); // modulo capacity
2406 [ # # # # : 0 : const Var<Ptr<void>> slot(bucket + (slots_skipped_mod * ht_.entry_size_in_bytes()).make_signed());
# # # # #
# ]
2407 [ # # # # : 0 : Wasm_insist(slot < ht_.end() + ht_.size_in_bytes().make_signed());
# # # # #
# # # #
# ]
2408 [ # # # # : 0 : return Select(slot < ht_.end(), slot, slot - ht_.size_in_bytes().make_signed());
# # # # #
# # # ]
2409 : 0 : }
2410 : :
2411 : 0 : Ptr<void> QuadraticProbing::advance_to_next_slot(Ptr<void> slot, U32x1 current_step) const
2412 : : {
2413 [ # # # # : 0 : const Var<Ptr<void>> next(slot + (current_step * ht_.entry_size_in_bytes()).make_signed());
# # ]
2414 [ # # # # : 0 : Wasm_insist(next < ht_.end() + ht_.size_in_bytes().make_signed());
# # # # #
# # # #
# ]
2415 [ # # # # : 0 : return Select(next < ht_.end(), next, next - ht_.size_in_bytes().make_signed());
# # # # #
# # # ]
2416 : 0 : }
|
