Line data Source code
1 : /** Copyright 2025 Alexander G. Lopez
2 :
3 : Licensed under the Apache License, Version 2.0 (the "License");
4 : you may not use this file except in compliance with the License.
5 : You may obtain a copy of the License at
6 :
7 : http://www.apache.org/licenses/LICENSE-2.0
8 :
9 : Unless required by applicable law or agreed to in writing, software
10 : distributed under the License is distributed on an "AS IS" BASIS,
11 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 : See the License for the specific language governing permissions and
13 : limitations under the License.
14 :
15 : This file implements an interpretation of Rust's Hashbrown Hash Map which in
16 : turn is based on Google's Abseil Flat Hash Map. This implementation is based
17 : on Rust's version which is slightly simpler and a better fit for C code. The
18 : required license for this adaptation is included at the bottom of the file.
19 : This implementation has changed a variety of types and data structures to work
20 : within the C language and its aliasing rules. Here are the two original
21 : implementations for reference.
22 :
23 : Abseil: https://github.com/abseil/abseil-cpp
24 : Hashbrown: https://github.com/rust-lang/hashbrown
25 :
26 : This implementation is focused on SIMD friendly code or portable word based
27 : code when SIMD is not available. On any platform, the goal is to query multiple
28 : candidate keys for a match in the map simultaneously. This is achieved in the
29 : best case by having 16 one-byte hash fingerprints analyzed simultaneously for
30 : a match against a candidate fingerprint. The details of how this is done and
31 : trade-offs involved can be found in the comments around the implementations
32 : and data structures. The ARM NEON implementation may be updated if they add
33 : better capabilities for 128 bit group operations. */
34 : /** C23 provided headers. */
35 : #include <limits.h>
36 : #include <stdalign.h>
37 : #include <stdckdint.h>
38 : #include <stddef.h>
39 : #include <stdint.h>
40 :
41 : /** CCC provided headers. */
42 : #include "ccc/configuration.h" /* IWYU pragma: keep */
43 : #include "ccc/flat_hash_map.h"
44 : #include "ccc/private/private_flat_hash_map.h"
45 : #include "ccc/types.h"
46 : #include "source/compiler_utilities.h"
47 :
48 : /*========================= Platform Selection ===========================*/
49 :
50 : /** Note that these includes must come after inclusion of the
51 : `private/private_flat_hash_map.h` header. Two platforms offer some form of
52 : vector instructions we can try. */
53 : #ifdef CCC_HAS_X86_SIMD
54 : # include <immintrin.h>
55 : #elifdef CCC_HAS_ARM_SIMD
56 : # include <arm_neon.h>
57 : #endif /* defined(CCC_HAS_X86_SIMD) */
58 :
59 : /* Can we vectorize instructions? Also it is possible to specify we want a
60 : portable implementation. Consider exposing to user in header docs. */
61 : #ifdef CCC_HAS_X86_SIMD
62 :
63 : /** @internal The 128 bit vector type for efficient SIMD group scanning. 16 one
64 : byte large tags fit in this type. */
65 : struct Group {
66 : __m128i v;
67 : };
68 :
69 : /** @internal Because we use 128 bit vectors over tags the results of various
70 : operations can be compressed into a 16 bit integer. */
71 : struct Match_mask {
72 : uint16_t v;
73 : };
74 :
75 : enum : typeof((struct Match_mask){}.v) {
76 : /** @internal MSB tag bit used for static assert. */
77 : MATCH_MASK_MSB = 0x8000,
78 : /** @internal All bits on in a mask except for the 0th tag bit. */
79 : MATCH_MASK_0TH_TAG_OFF = 0xFFFE,
80 : };
81 :
82 : #elifdef CCC_HAS_ARM_SIMD
83 :
84 : /** @internal The 64 bit vector is used on NEON due to a lack of ability to
85 : compress a 128 bit vector to a smaller int efficiently. */
86 : struct Group {
87 : /** @internal NEON offers a specific type for 64 bit manipulations. */
88 : uint8x8_t v;
89 : };
90 :
91 : /** @internal The mask will consist of 8 bytes with the most significant bit of
92 : each byte on to indicate match statuses. */
93 : struct Match_mask {
94 : /** @internal NEON returns this type from various uint8x8_t operations. */
95 : uint64_t v;
96 : };
97 :
98 : enum : uint64_t {
99 : /** @internal MSB tag bit used for static assert. */
100 : MATCH_MASK_MSB = 0x8000000000000000,
101 : /** @internal MSB tag bits used for byte and word level masking. */
102 : MATCH_MASK_TAGS_MSBS = 0x8080808080808080,
103 : /** @internal LSB tag bits used for byte and word level masking. */
104 : MATCH_MASK_TAGS_LSBS = 0x101010101010101,
105 : /** @internal Debug mode check for bits that must be off in match. */
106 : MATCH_MASK_TAGS_OFF_BITS = 0x7F7F7F7F7F7F7F7F,
107 : /** @internal The MSB of each byte on except 0th is 0x00. */
108 : MATCH_MASK_0TH_TAG_OFF = 0x8080808080808000,
109 : };
110 :
111 : enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
112 : /** @internal Bits in a tag used to help in creating a group of one tag. */
113 : TAG_BITS = sizeof(struct CCC_Flat_hash_map_tag) * CHAR_BIT,
114 : };
115 :
116 : #else /* PORTABLE FALLBACK */
117 :
118 : /** @internal The 8 byte word for managing multiple simultaneous equality
119 : checks. In contrast to SIMD this group size is the same as the match. */
120 : struct Group {
121 : /** @internal 64 bits allows 8 tags to be checked at once. */
122 : uint64_t v;
123 : };
124 :
125 : /** @internal The match is the same size as the group because only the most
126 : significant bit in a byte within the mask will be on to indicate the result of
127 : various queries such as matching a tag, empty, or constant. */
128 : struct Match_mask {
129 : /** @internal The match is the same as a group with MSB on. */
130 : typeof((struct Group){}.v) v;
131 : };
132 :
133 : enum : typeof((struct Group){}.v) {
134 : /** @internal MSB tag bit used for static assert. */
135 : MATCH_MASK_MSB = 0x8000000000000000,
136 : /** @internal MSB tag bits used for byte and word level masking. */
137 : MATCH_MASK_TAGS_MSBS = 0x8080808080808080,
138 : /** @internal The EMPTY special constant tag in every byte of the mask. */
139 : MATCH_MASK_TAGS_EMPTY = 0x8080808080808080,
140 : /** @internal LSB tag bits used for byte and word level masking. */
141 : MATCH_MASK_TAGS_LSBS = 0x101010101010101,
142 : /** @internal Debug mode check for bits that must be off in match. */
143 : MATCH_MASK_TAGS_OFF_BITS = 0x7F7F7F7F7F7F7F7F,
144 : /** @internal The MSB of each byte on except 0th is 0x00. */
145 : MATCH_MASK_0TH_TAG_OFF = 0x8080808080808000,
146 : };
147 :
148 : enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
149 : /** @internal Bits in a tag used to help in creating a group of one tag. */
150 : TAG_BITS = sizeof(struct CCC_Flat_hash_map_tag) * CHAR_BIT,
151 : };
152 :
153 : #endif /* defined(CCC_HAS_X86_SIMD) */
154 :
155 : /*========================= Group Count =============================*/
156 :
157 : enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
158 : /** @internal Shortened group size name for readability. */
159 : GROUP_COUNT = CCC_FLAT_HASH_MAP_GROUP_COUNT,
160 : };
161 :
162 : /*======================= Data Alignment Test ===========================*/
163 :
164 : /** @internal The following test should ensure some safety in assumptions we
165 : make when the user defines a fixed size map type. This anonymous compound
166 : literal construction is the same technique used to construct fixed maps for
167 : users. However, it is just a small type that will remain internal to this
168 : translation unit and does not use the same capacity static assert constraints.
169 : The tag array is not given a replica group size at the end of its allocation
170 : because that wastes pointless space and has no impact on the following layout
171 : and pointer arithmetic tests. One behavior we want to ensure is that our manual
172 : pointer arithmetic at runtime matches the group size aligned position of the tag
173 : metadata array. */
174 : [[maybe_unused]] static __auto_type const data_tag_layout_test = (struct {
175 : alignas(GROUP_COUNT) int const data[2 + 1];
176 : alignas(GROUP_COUNT) struct CCC_Flat_hash_map_tag const tag[2];
177 : }){};
178 : static_assert(
179 : offsetof(typeof(data_tag_layout_test), tag[2])
180 : - offsetof(typeof(data_tag_layout_test), data[0])
181 : == (CCC_roundup(sizeof(data_tag_layout_test.data), GROUP_COUNT)
182 : + (sizeof(struct CCC_Flat_hash_map_tag) * 2)),
183 : "The manually computed offset of the tag array from the start of the data "
184 : "array must match the offset chosen by compiler alignment rules."
185 : );
186 : static_assert(
187 : offsetof(typeof(data_tag_layout_test), data)
188 : + CCC_roundup(sizeof(data_tag_layout_test.data), GROUP_COUNT)
189 : == offsetof(typeof(data_tag_layout_test), tag),
190 : "We calculate the correct position of the tag array considering it may get "
191 : "extra padding at start for alignment by group size."
192 : );
193 : static_assert(
194 : (offsetof(typeof(data_tag_layout_test), tag) % GROUP_COUNT) == 0,
195 : "The tag array starts at an aligned group size byte boundary within the "
196 : "struct."
197 : );
198 :
199 : /*======================= Special Constants ===========================*/
200 :
201 : /** @internal Range of constants specified as special for this hash table. Same
202 : general design as Rust Hashbrown table. Importantly, we know these are special
203 : constants because the most significant bit is on and then empty can be easily
204 : distinguished from deleted by the least significant bit.
205 :
206 : The full case is implicit in the table as it cannot be quantified by a simple
207 : enum value.
208 :
209 : ```
210 : TAG_FULL = 0b0???_????
211 : ```
212 :
213 : The most significant bit is off and the lower 7 make up the hash bits. */
214 : enum : typeof((struct CCC_Flat_hash_map_tag){}.v) {
215 : /** @internal Deleted is applied when a removed value in a group must signal
216 : to a probe sequence to continue searching for a match or empty to stop. */
217 : TAG_DELETED = 0x80,
218 : /** @internal Empty is the starting tag value and applied when other empties
219 : are in a group upon removal. */
220 : TAG_EMPTY = 0xFF,
221 : /** @internal Used to verify if tag is constant or hash data. */
222 : TAG_MSB = TAG_DELETED,
223 : /** @internal Used to create a one byte fingerprint of user hash. */
224 : TAG_LOWER_7_MASK = (typeof((struct CCC_Flat_hash_map_tag){}.v))~TAG_DELETED,
225 : };
226 : static_assert(
227 : sizeof(struct CCC_Flat_hash_map_tag) == sizeof(uint8_t),
228 : "tag must wrap a byte in a struct without padding for better "
229 : "optimizations and no strict-aliasing exceptions."
230 : );
231 : static_assert(
232 : (TAG_DELETED | TAG_EMPTY) == (typeof((struct CCC_Flat_hash_map_tag){}.v))~0,
233 : "all bits must be accounted for across deleted and empty status."
234 : );
235 : static_assert(
236 : (TAG_DELETED ^ TAG_EMPTY) == 0x7F,
237 : "only empty should have lsb on and 7 bits are available for hash"
238 : );
239 :
240 : /*======================= Type Declarations ===========================*/
241 :
242 : /** @internal A triangular sequence of numbers is a probing sequence that will
243 : visit every group in a power of 2 capacity hash table. Here is a popular proof:
244 :
245 : https://fgiesen.wordpress.com/2015/02/22/triangular-numbers-mod-2n/
246 :
247 : See also Donald Knuth's The Art of Computer Programming Volume 3, Chapter 6.4,
248 : Answers to Exercises, problem 20, page 731 for another proof. */
249 : struct Probe {
250 : /** @internal The index this probe step has placed us on. */
251 : size_t index;
252 : /** @internal Stride increases by group size on each iteration. */
253 : size_t stride;
254 : };
255 :
256 : /*=========================== Prototypes ================================*/
257 :
258 : static void swap(void *, size_t, void *, void *);
259 : static struct CCC_Flat_hash_map_entry maybe_rehash_find_entry(
260 : struct CCC_Flat_hash_map *, void const *, CCC_Allocator const *
261 : );
262 : static CCC_Handle
263 : find_key_or_index(struct CCC_Flat_hash_map const *, void const *, uint64_t);
264 : static CCC_Count
265 : find_key_or_fail(struct CCC_Flat_hash_map const *, void const *, uint64_t);
266 : static size_t
267 : find_index_or_noreturn(struct CCC_Flat_hash_map const *, uint64_t);
268 : static void *find_first_full_index(struct CCC_Flat_hash_map const *, size_t);
269 : static struct Match_mask
270 : find_first_full_group(struct CCC_Flat_hash_map const *, size_t *);
271 : static CCC_Result
272 : maybe_rehash(struct CCC_Flat_hash_map *, size_t, CCC_Allocator const *);
273 : static void insert_and_copy(
274 : struct CCC_Flat_hash_map *,
275 : void const *,
276 : struct CCC_Flat_hash_map_tag,
277 : size_t
278 : );
279 : static void erase(struct CCC_Flat_hash_map *, size_t);
280 : static CCC_Result
281 : lazy_initialize(struct CCC_Flat_hash_map *, size_t, CCC_Allocator const *);
282 : static void rehash_in_place(struct CCC_Flat_hash_map *);
283 : static CCC_Tribool is_same_group(size_t, size_t, uint64_t, size_t);
284 : static CCC_Result
285 : rehash_resize(struct CCC_Flat_hash_map *, size_t, CCC_Allocator const *);
286 : static CCC_Tribool
287 : is_equal(struct CCC_Flat_hash_map const *, void const *, size_t);
288 : static uint64_t hasher(struct CCC_Flat_hash_map const *, void const *);
289 : static void *key_at(struct CCC_Flat_hash_map const *, size_t);
290 : static void *data_at(struct CCC_Flat_hash_map const *, size_t);
291 : static struct CCC_Flat_hash_map_tag *
292 : tags_base_address(size_t, void const *, size_t);
293 : static void *key_in_index(struct CCC_Flat_hash_map const *, void const *);
294 : static void *swap_index(struct CCC_Flat_hash_map const *);
295 : static CCC_Count data_index(struct CCC_Flat_hash_map const *, void const *);
296 : static size_t mask_to_total_bytes(size_t, size_t);
297 : static CCC_Tribool checked_mask_to_total_bytes(size_t *, size_t, size_t);
298 : static size_t mask_to_tag_bytes(size_t);
299 : static size_t mask_to_data_bytes(size_t, size_t);
300 : static void set_insert_tag(
301 : struct CCC_Flat_hash_map *, struct CCC_Flat_hash_map_tag, size_t
302 : );
303 : static size_t mask_to_capacity_with_load_factor(size_t);
304 : static void
305 : tag_set(struct CCC_Flat_hash_map *, struct CCC_Flat_hash_map_tag, size_t);
306 : static CCC_Tribool match_has_one(struct Match_mask);
307 : static size_t match_trailing_one(struct Match_mask);
308 : static size_t match_leading_zeros(struct Match_mask);
309 : static size_t match_trailing_zeros(struct Match_mask);
310 : static size_t match_next_one(struct Match_mask *);
311 : static CCC_Tribool tag_full(struct CCC_Flat_hash_map_tag);
312 : static CCC_Tribool tag_constant(struct CCC_Flat_hash_map_tag);
313 : static struct CCC_Flat_hash_map_tag tag_from(uint64_t);
314 : static struct Group group_load_unaligned(struct CCC_Flat_hash_map_tag const *);
315 : static struct Group group_load_aligned(struct CCC_Flat_hash_map_tag const *);
316 : static void group_store_aligned(struct CCC_Flat_hash_map_tag *, struct Group);
317 : static struct Match_mask match_tag(struct Group, struct CCC_Flat_hash_map_tag);
318 : static struct Match_mask match_empty(struct Group);
319 : static struct Match_mask match_deleted(struct Group);
320 : static struct Match_mask match_empty_or_deleted(struct Group);
321 : static struct Match_mask match_full(struct Group);
322 : static struct Match_mask match_leading_full(struct Group, size_t);
323 : static struct Group
324 : group_convert_constant_to_empty_and_full_to_deleted(struct Group);
325 : static unsigned count_trailing_zeros(struct Match_mask);
326 : static unsigned count_leading_zeros(struct Match_mask);
327 : static CCC_Tribool is_power_of_two(size_t);
328 : static CCC_Tribool is_uninitialized(struct CCC_Flat_hash_map const *);
329 : static void destory_each(struct CCC_Flat_hash_map *, CCC_Destructor const *);
330 : static CCC_Tribool check_replica_group(struct CCC_Flat_hash_map const *);
331 :
332 : /*=========================== Interface ================================*/
333 :
334 : CCC_Tribool
335 5628 : CCC_flat_hash_map_is_empty(CCC_Flat_hash_map const *const map) {
336 5628 : if (CCC_unlikely(!map)) {
337 1 : return CCC_TRIBOOL_ERROR;
338 : }
339 5627 : return !map->count;
340 5628 : }
341 :
342 : CCC_Count
343 5776 : CCC_flat_hash_map_count(CCC_Flat_hash_map const *const map) {
344 5776 : if (!map || map->mask < (GROUP_COUNT - 1)) {
345 6 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
346 : }
347 5770 : return (CCC_Count){.count = map->count};
348 5776 : }
349 :
350 : CCC_Count
351 9 : CCC_flat_hash_map_capacity(CCC_Flat_hash_map const *const map) {
352 9 : if (!map || (!map->data && map->mask)) {
353 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
354 : }
355 8 : return (CCC_Count){.count = map->mask ? map->mask + 1 : 0};
356 9 : }
357 :
358 : CCC_Tribool
359 10255 : CCC_flat_hash_map_contains(
360 : CCC_Flat_hash_map const *const map, void const *const key
361 : ) {
362 10255 : if (CCC_unlikely(!map || !key)) {
363 2 : return CCC_TRIBOOL_ERROR;
364 : }
365 10253 : if (CCC_unlikely(is_uninitialized(map) || !map->count)) {
366 1 : return CCC_FALSE;
367 : }
368 10252 : return !find_key_or_fail(map, key, hasher(map, key)).error;
369 10255 : }
370 :
371 : void *
372 2073 : CCC_flat_hash_map_get_key_value(
373 : CCC_Flat_hash_map const *const map, void const *const key
374 : ) {
375 2073 : if (CCC_unlikely(!map || !key || is_uninitialized(map) || !map->count)) {
376 1 : return NULL;
377 : }
378 2072 : CCC_Count const index = find_key_or_fail(map, key, hasher(map, key));
379 2072 : if (index.error) {
380 47 : return NULL;
381 : }
382 2025 : return data_at(map, index.count);
383 2073 : }
384 :
385 : CCC_Flat_hash_map_entry
386 18148 : CCC_flat_hash_map_entry(
387 : CCC_Flat_hash_map *const map,
388 : void const *const key,
389 : CCC_Allocator const *const allocator
390 : ) {
391 18148 : if (CCC_unlikely(!map || !key || !allocator)) {
392 6 : return (CCC_Flat_hash_map_entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
393 : }
394 18142 : return maybe_rehash_find_entry(map, key, allocator);
395 18148 : }
396 :
397 : void *
398 282 : CCC_flat_hash_map_or_insert(
399 : CCC_Flat_hash_map_entry const *const entry, void const *type
400 : ) {
401 282 : if (CCC_unlikely(
402 282 : !entry || !type || (entry->status & CCC_ENTRY_ARGUMENT_ERROR)
403 : )) {
404 1 : return NULL;
405 : }
406 281 : if (entry->status & CCC_ENTRY_OCCUPIED) {
407 157 : return data_at(entry->map, entry->index);
408 : }
409 124 : if (entry->status & CCC_ENTRY_INSERT_ERROR) {
410 2 : return NULL;
411 : }
412 122 : insert_and_copy(entry->map, type, entry->tag, entry->index);
413 122 : return data_at(entry->map, entry->index);
414 282 : }
415 :
416 : void *
417 7373 : CCC_flat_hash_map_insert_entry(
418 : CCC_Flat_hash_map_entry const *const entry, void const *type
419 : ) {
420 7373 : if (CCC_unlikely(
421 7373 : !entry || !type || (entry->status & CCC_ENTRY_ARGUMENT_ERROR)
422 : )) {
423 1 : return NULL;
424 : }
425 7372 : if (entry->status & CCC_ENTRY_OCCUPIED) {
426 2105 : void *const index = data_at(entry->map, entry->index);
427 2105 : (void)memcpy(index, type, entry->map->sizeof_type);
428 2105 : return index;
429 2105 : }
430 5267 : if (entry->status & CCC_ENTRY_INSERT_ERROR) {
431 4 : return NULL;
432 : }
433 5263 : insert_and_copy(entry->map, type, entry->tag, entry->index);
434 5263 : return data_at(entry->map, entry->index);
435 7373 : }
436 :
437 : CCC_Entry
438 5561 : CCC_flat_hash_map_remove_entry(CCC_Flat_hash_map_entry const *const entry) {
439 5561 : if (CCC_unlikely(!entry)) {
440 1 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
441 : }
442 5560 : if (!(entry->status & CCC_ENTRY_OCCUPIED)) {
443 1 : return (CCC_Entry){.status = CCC_ENTRY_VACANT};
444 : }
445 5559 : erase(entry->map, entry->index);
446 5559 : return (CCC_Entry){.status = CCC_ENTRY_OCCUPIED};
447 5561 : }
448 :
449 : CCC_Flat_hash_map_entry *
450 216 : CCC_flat_hash_map_and_modify(
451 : CCC_Flat_hash_map_entry *const entry, CCC_Modifier const *const modifier
452 : ) {
453 216 : if (entry && modifier && modifier->modify
454 216 : && ((entry->status & CCC_ENTRY_OCCUPIED) != 0)) {
455 330 : modifier->modify((CCC_Arguments){
456 110 : .type = data_at(entry->map, entry->index),
457 110 : .context = modifier->context,
458 : });
459 110 : }
460 216 : return entry;
461 : }
462 :
463 : CCC_Entry
464 440 : CCC_flat_hash_map_swap_entry(
465 : CCC_Flat_hash_map *const map,
466 : void *const type_output,
467 : CCC_Allocator const *const allocator
468 : ) {
469 440 : if (CCC_unlikely(!map || !type_output || !allocator)) {
470 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
471 : }
472 437 : void *const key = key_in_index(map, type_output);
473 437 : struct CCC_Flat_hash_map_entry index
474 437 : = maybe_rehash_find_entry(map, key, allocator);
475 437 : if (index.status & CCC_ENTRY_OCCUPIED) {
476 7 : swap(
477 7 : swap_index(map),
478 7 : map->sizeof_type,
479 7 : data_at(map, index.index),
480 7 : type_output
481 : );
482 14 : return (CCC_Entry){
483 7 : .type = type_output,
484 : .status = CCC_ENTRY_OCCUPIED,
485 : };
486 : }
487 430 : if (index.status & CCC_ENTRY_INSERT_ERROR) {
488 2 : return (CCC_Entry){.status = CCC_ENTRY_INSERT_ERROR};
489 : }
490 428 : insert_and_copy(index.map, type_output, index.tag, index.index);
491 856 : return (CCC_Entry){
492 428 : .type = data_at(map, index.index),
493 : .status = CCC_ENTRY_VACANT,
494 : };
495 440 : }
496 :
497 : CCC_Entry
498 2222 : CCC_flat_hash_map_try_insert(
499 : CCC_Flat_hash_map *const map,
500 : void const *const type,
501 : CCC_Allocator const *const allocator
502 : ) {
503 2222 : if (CCC_unlikely(!map || !type || !allocator)) {
504 4 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
505 : }
506 2218 : void *const key = key_in_index(map, type);
507 2218 : struct CCC_Flat_hash_map_entry const index
508 2218 : = maybe_rehash_find_entry(map, key, allocator);
509 2218 : if (index.status & CCC_ENTRY_OCCUPIED) {
510 2196 : return (CCC_Entry){
511 1098 : .type = data_at(map, index.index),
512 : .status = CCC_ENTRY_OCCUPIED,
513 : };
514 : }
515 1120 : if (index.status & CCC_ENTRY_INSERT_ERROR) {
516 1 : return (CCC_Entry){.status = CCC_ENTRY_INSERT_ERROR};
517 : }
518 1119 : insert_and_copy(index.map, type, index.tag, index.index);
519 2238 : return (CCC_Entry){
520 1119 : .type = data_at(map, index.index),
521 : .status = CCC_ENTRY_VACANT,
522 : };
523 2222 : }
524 :
525 : CCC_Entry
526 90 : CCC_flat_hash_map_insert_or_assign(
527 : CCC_Flat_hash_map *const map,
528 : void const *const type,
529 : CCC_Allocator const *const allocator
530 : ) {
531 90 : if (CCC_unlikely(!map || !type || !allocator)) {
532 3 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
533 : }
534 87 : void *const key = key_in_index(map, type);
535 87 : struct CCC_Flat_hash_map_entry const index
536 87 : = maybe_rehash_find_entry(map, key, allocator);
537 87 : if (index.status & CCC_ENTRY_OCCUPIED) {
538 59 : (void)memcpy(data_at(map, index.index), type, map->sizeof_type);
539 118 : return (CCC_Entry){
540 59 : .type = data_at(map, index.index),
541 : .status = CCC_ENTRY_OCCUPIED,
542 : };
543 : }
544 28 : if (index.status & CCC_ENTRY_INSERT_ERROR) {
545 4 : return (CCC_Entry){.status = CCC_ENTRY_INSERT_ERROR};
546 : }
547 24 : insert_and_copy(index.map, type, index.tag, index.index);
548 48 : return (CCC_Entry){
549 24 : .type = data_at(map, index.index),
550 : .status = CCC_ENTRY_VACANT,
551 : };
552 90 : }
553 :
554 : CCC_Entry
555 3081 : CCC_flat_hash_map_remove_key_value(
556 : CCC_Flat_hash_map *const map, void *const type_output
557 : ) {
558 3081 : if (CCC_unlikely(!map || !type_output)) {
559 2 : return (CCC_Entry){.status = CCC_ENTRY_ARGUMENT_ERROR};
560 : }
561 3079 : if (CCC_unlikely(is_uninitialized(map) || !map->count)) {
562 3 : return (CCC_Entry){.status = CCC_ENTRY_VACANT};
563 : }
564 3076 : void *const key = key_in_index(map, type_output);
565 3076 : CCC_Count const index = find_key_or_fail(map, key, hasher(map, key));
566 3076 : if (index.error) {
567 2 : return (CCC_Entry){.status = CCC_ENTRY_VACANT};
568 : }
569 3074 : (void)memcpy(type_output, data_at(map, index.count), map->sizeof_type);
570 3074 : erase(map, index.count);
571 6148 : return (CCC_Entry){
572 3074 : .type = type_output,
573 : .status = CCC_ENTRY_OCCUPIED,
574 : };
575 3081 : }
576 :
577 : void *
578 16 : CCC_flat_hash_map_begin(CCC_Flat_hash_map const *const map) {
579 16 : if (CCC_unlikely(
580 16 : !map || !map->mask || is_uninitialized(map) || !map->count
581 : )) {
582 4 : return NULL;
583 : }
584 12 : return find_first_full_index(map, 0);
585 16 : }
586 :
587 : void *
588 2735 : CCC_flat_hash_map_next(
589 : CCC_Flat_hash_map const *const map, void const *const type_iterator
590 : ) {
591 2735 : if (CCC_unlikely(
592 2735 : !map || !type_iterator || !map->mask || is_uninitialized(map)
593 2734 : || !map->count
594 : )) {
595 1 : return NULL;
596 : }
597 2734 : CCC_Count index = data_index(map, type_iterator);
598 2734 : if (index.error) {
599 1 : return NULL;
600 : }
601 5466 : size_t const aligned_group_start
602 2733 : = index.count & ~((typeof(index.count))(GROUP_COUNT - 1));
603 5466 : struct Match_mask m = match_leading_full(
604 2733 : group_load_aligned(&map->tag[aligned_group_start]),
605 2733 : index.count & (GROUP_COUNT - 1)
606 : );
607 2733 : size_t const bit = match_next_one(&m);
608 2733 : if (bit != GROUP_COUNT) {
609 2459 : return data_at(map, aligned_group_start + bit);
610 : }
611 274 : return find_first_full_index(map, aligned_group_start + GROUP_COUNT);
612 2735 : }
613 :
614 : void *
615 2747 : CCC_flat_hash_map_end(CCC_Flat_hash_map const *const) {
616 2747 : return NULL;
617 : }
618 :
619 : void *
620 27 : CCC_flat_hash_map_unwrap(CCC_Flat_hash_map_entry const *const entry) {
621 27 : if (CCC_unlikely(!entry) || !(entry->status & CCC_ENTRY_OCCUPIED)) {
622 12 : return NULL;
623 : }
624 15 : return data_at(entry->map, entry->index);
625 27 : }
626 :
627 : CCC_Result
628 6 : CCC_flat_hash_map_clear(
629 : CCC_Flat_hash_map *const map, CCC_Destructor const *const destructor
630 : ) {
631 6 : if (CCC_unlikely(!map || !destructor)) {
632 2 : return CCC_RESULT_ARGUMENT_ERROR;
633 : }
634 4 : if (CCC_unlikely(is_uninitialized(map) || !map->mask || !map->tag)) {
635 2 : return CCC_RESULT_OK;
636 : }
637 2 : if (destructor->destroy) {
638 1 : destory_each(map, destructor);
639 1 : }
640 2 : (void)memset(map->tag, TAG_EMPTY, mask_to_tag_bytes(map->mask));
641 2 : map->remain = mask_to_capacity_with_load_factor(map->mask);
642 2 : map->count = 0;
643 2 : return CCC_RESULT_OK;
644 6 : }
645 :
646 : CCC_Result
647 24 : CCC_flat_hash_map_clear_and_free(
648 : CCC_Flat_hash_map *const map,
649 : CCC_Destructor const *const destructor,
650 : CCC_Allocator const *const allocator
651 : ) {
652 24 : if (CCC_unlikely(
653 24 : !map || !map->data || !destructor || !allocator
654 20 : || !allocator->allocate || !map->mask
655 : )) {
656 6 : return CCC_RESULT_ARGUMENT_ERROR;
657 : }
658 18 : if (destructor->destroy && !is_uninitialized(map)) {
659 1 : destory_each(map, destructor);
660 1 : }
661 18 : map->remain = 0;
662 18 : map->mask = 0;
663 18 : map->count = 0;
664 72 : (void)allocator->allocate((CCC_Allocator_arguments){
665 18 : .input = map->data,
666 : .bytes = 0,
667 18 : .alignment = CCC_max(GROUP_COUNT, map->alignof_type),
668 18 : .context = allocator->context,
669 : });
670 18 : map->data = NULL;
671 18 : map->tag = NULL;
672 18 : return CCC_RESULT_OK;
673 24 : }
674 :
675 : CCC_Tribool
676 661 : CCC_flat_hash_map_occupied(CCC_Flat_hash_map_entry const *const entry) {
677 661 : if (CCC_unlikely(!entry)) {
678 1 : return CCC_TRIBOOL_ERROR;
679 : }
680 660 : return (entry->status & CCC_ENTRY_OCCUPIED) != 0;
681 661 : }
682 :
683 : CCC_Tribool
684 2 : CCC_flat_hash_map_insert_error(CCC_Flat_hash_map_entry const *const entry) {
685 2 : if (CCC_unlikely(!entry)) {
686 1 : return CCC_TRIBOOL_ERROR;
687 : }
688 1 : return (entry->status & CCC_ENTRY_INSERT_ERROR) != 0;
689 2 : }
690 :
691 : CCC_Entry_status
692 5 : CCC_flat_hash_map_entry_status(CCC_Flat_hash_map_entry const *const entry) {
693 5 : if (CCC_unlikely(!entry)) {
694 1 : return CCC_ENTRY_ARGUMENT_ERROR;
695 : }
696 4 : return entry->status;
697 5 : }
698 :
699 : CCC_Result
700 6 : CCC_flat_hash_map_copy(
701 : CCC_Flat_hash_map *const destination,
702 : CCC_Flat_hash_map const *const source,
703 : CCC_Allocator const *const allocator
704 : ) {
705 6 : if (!destination || !source || !allocator || source == destination
706 5 : || (source->mask && !is_power_of_two(source->mask + 1))) {
707 1 : return CCC_RESULT_ARGUMENT_ERROR;
708 : }
709 5 : destination->hasher = source->hasher;
710 5 : destination->sizeof_type = source->sizeof_type;
711 5 : destination->key_offset = source->key_offset;
712 5 : if (destination->mask < source->mask && !allocator->allocate) {
713 1 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
714 : }
715 4 : if (!source->mask || is_uninitialized(source)) {
716 1 : return CCC_RESULT_OK;
717 : }
718 6 : size_t const source_bytes
719 3 : = mask_to_total_bytes(source->sizeof_type, source->mask);
720 3 : if (destination->mask < source->mask) {
721 10 : void *const new_data = allocator->allocate((CCC_Allocator_arguments){
722 2 : .input = destination->data,
723 2 : .bytes = source_bytes,
724 2 : .alignment = CCC_max(GROUP_COUNT, destination->alignof_type),
725 2 : .context = allocator->context,
726 : });
727 2 : if (!new_data) {
728 1 : return CCC_RESULT_ALLOCATOR_ERROR;
729 : }
730 1 : destination->data = new_data;
731 2 : }
732 2 : destination->tag = tags_base_address(
733 2 : source->sizeof_type, destination->data, source->mask
734 : );
735 2 : destination->mask = source->mask;
736 2 : (void)memset(
737 2 : destination->tag, TAG_EMPTY, mask_to_tag_bytes(destination->mask)
738 : );
739 2 : destination->remain = mask_to_capacity_with_load_factor(destination->mask);
740 2 : destination->count = 0;
741 : {
742 2 : size_t group_start = 0;
743 2 : struct Match_mask full = {};
744 4 : while ((full = find_first_full_group(source, &group_start)).v) {
745 : {
746 2 : size_t tag_index = 0;
747 8 : while ((tag_index = match_next_one(&full)) != GROUP_COUNT) {
748 6 : tag_index += group_start;
749 12 : uint64_t const hash
750 6 : = hasher(source, key_at(source, tag_index));
751 12 : size_t const new_index
752 6 : = find_index_or_noreturn(destination, hash);
753 6 : tag_set(destination, tag_from(hash), new_index);
754 6 : (void)memcpy(
755 6 : data_at(destination, new_index),
756 6 : data_at(source, tag_index),
757 6 : destination->sizeof_type
758 : );
759 6 : }
760 2 : }
761 2 : group_start += GROUP_COUNT;
762 : }
763 2 : }
764 2 : destination->remain -= source->count;
765 2 : destination->count = source->count;
766 2 : return CCC_RESULT_OK;
767 6 : }
768 :
769 : CCC_Result
770 14 : CCC_flat_hash_map_reserve(
771 : CCC_Flat_hash_map *const map,
772 : size_t const to_add,
773 : CCC_Allocator const *const allocator
774 : ) {
775 14 : if (CCC_unlikely(!map || !to_add || !allocator || !to_add)) {
776 1 : return CCC_RESULT_ARGUMENT_ERROR;
777 : }
778 13 : return maybe_rehash(map, to_add, allocator);
779 14 : }
780 :
781 : CCC_Tribool
782 21406 : CCC_flat_hash_map_validate(CCC_Flat_hash_map const *const map) {
783 21406 : if (!map) {
784 0 : return CCC_TRIBOOL_ERROR;
785 : }
786 21406 : if (!is_uninitialized(map) && !map->mask) {
787 0 : return CCC_FALSE;
788 : }
789 21406 : if (is_uninitialized(map) || !map->mask) {
790 10 : return CCC_TRUE;
791 : }
792 21396 : if (!map->data || !map->tag) {
793 0 : return CCC_FALSE;
794 : }
795 21396 : if (!check_replica_group(map)) {
796 0 : return CCC_FALSE;
797 : }
798 21396 : size_t occupied = 0;
799 21396 : size_t remain = 0;
800 21396 : size_t deleted = 0;
801 27569652 : for (size_t i = 0; i < (map->mask + 1); ++i) {
802 27548256 : struct CCC_Flat_hash_map_tag const t = map->tag[i];
803 27548256 : if (tag_constant(t) && t.v != TAG_DELETED && t.v != TAG_EMPTY) {
804 0 : return CCC_FALSE;
805 : }
806 27548256 : if (t.v == TAG_EMPTY) {
807 15044837 : ++remain;
808 27548256 : } else if (t.v == TAG_DELETED) {
809 2230453 : ++deleted;
810 2230453 : } else {
811 10272966 : if (!tag_full(t)) {
812 0 : return CCC_FALSE;
813 : }
814 10272966 : if (tag_from(hasher(map, data_at(map, i))).v != t.v) {
815 0 : return CCC_FALSE;
816 : }
817 10272966 : ++occupied;
818 : }
819 27548256 : }
820 21396 : if (occupied != map->count) {
821 0 : return CCC_FALSE;
822 : }
823 21396 : if (occupied + remain + deleted != map->mask + 1) {
824 0 : return CCC_FALSE;
825 : }
826 21396 : if (mask_to_capacity_with_load_factor(occupied + remain + deleted)
827 21396 : - occupied - deleted
828 21396 : != map->remain) {
829 0 : return CCC_FALSE;
830 : }
831 21396 : return CCC_TRUE;
832 21406 : }
833 :
834 : static CCC_Tribool
835 21396 : check_replica_group(struct CCC_Flat_hash_map const *const map) {
836 363732 : for (size_t original = 0, clone = (map->mask + 1); original < GROUP_COUNT;
837 342336 : ++original, ++clone) {
838 342336 : if (map->tag[original].v != map->tag[clone].v) {
839 0 : return CCC_FALSE;
840 : }
841 342336 : }
842 21396 : return CCC_TRUE;
843 21396 : }
844 :
845 : /*====================== Private Interface =========================*/
846 :
847 : struct CCC_Flat_hash_map_entry
848 8557 : CCC_private_flat_hash_map_entry(
849 : struct CCC_Flat_hash_map *const map,
850 : void const *const key,
851 : CCC_Allocator const *const allocator
852 : ) {
853 8557 : return maybe_rehash_find_entry(map, key, allocator);
854 8557 : }
855 :
856 : void *
857 14818 : CCC_private_flat_hash_map_data_at(
858 : struct CCC_Flat_hash_map const *const map, size_t const index
859 : ) {
860 14818 : return data_at(map, index);
861 : }
862 :
863 : void *
864 8535 : CCC_private_flat_hash_map_key_at(
865 : struct CCC_Flat_hash_map const *const map, size_t const index
866 : ) {
867 8535 : return key_at(map, index);
868 : }
869 :
870 : /* This is needed to help the macros only set a new insert conditionally. */
871 : void
872 8647 : CCC_private_flat_hash_map_set_insert(
873 : struct CCC_Flat_hash_map_entry const *const entry
874 : ) {
875 8647 : return set_insert_tag(entry->map, entry->tag, entry->index);
876 8647 : }
877 :
878 : /*========================= Static Internals ============================*/
879 :
880 : /** Returns the container entry prepared for further insertion, removal, or
881 : searched queries. This entry gives a reference to the associated map and any
882 : metadata and location info necessary for future actions. If this entry was
883 : obtained in hopes of insertions but insertion will cause an error. A status
884 : flag in the handle field will indicate the error. */
885 : static struct CCC_Flat_hash_map_entry
886 29441 : maybe_rehash_find_entry(
887 : struct CCC_Flat_hash_map *const map,
888 : void const *const key,
889 : CCC_Allocator const *const allocator
890 : ) {
891 29441 : CCC_Result const index_result = maybe_rehash(map, 1, allocator);
892 29441 : if (index_result != CCC_RESULT_OK && !map->mask) {
893 18 : return (struct CCC_Flat_hash_map_entry){
894 9 : .map = (struct CCC_Flat_hash_map *)map,
895 : .status = CCC_ENTRY_INSERT_ERROR,
896 : };
897 : }
898 29432 : uint64_t const hash = hasher(map, key);
899 29432 : struct CCC_Flat_hash_map_tag const tag = tag_from(hash);
900 29432 : CCC_Handle const q = find_key_or_index(map, key, hash);
901 29432 : if (q.status == CCC_ENTRY_VACANT && index_result != CCC_RESULT_OK) {
902 : /* We need to warn the user that we did not find the key and they cannot
903 : insert new element due to fixed size, permissions, or exhaustion. */
904 28 : return (struct CCC_Flat_hash_map_entry){
905 14 : .map = (struct CCC_Flat_hash_map *)map,
906 : .status = CCC_ENTRY_INSERT_ERROR,
907 : };
908 : }
909 147090 : return (struct CCC_Flat_hash_map_entry){
910 29418 : .map = (struct CCC_Flat_hash_map *)map,
911 29418 : .index = q.index,
912 29418 : .tag = tag,
913 29418 : .status = q.status,
914 : };
915 29441 : }
916 :
917 : /** Sets the insert tag meta data and copies the user type into the associated
918 : data index. It is user's responsibility to ensure that the insert is valid. */
919 : static inline void
920 6956 : insert_and_copy(
921 : struct CCC_Flat_hash_map *const map,
922 : void const *const type,
923 : struct CCC_Flat_hash_map_tag const tag,
924 : size_t const index
925 : ) {
926 6956 : set_insert_tag(map, tag, index);
927 6956 : (void)memcpy(data_at(map, index), type, map->sizeof_type);
928 6956 : }
929 :
930 : /** Sets the insert tag meta data. It is user's responsibility to ensure that
931 : the insert is valid. */
932 : static inline void
933 15603 : set_insert_tag(
934 : struct CCC_Flat_hash_map *const map,
935 : struct CCC_Flat_hash_map_tag const tag,
936 : size_t const index
937 : ) {
938 15603 : assert(index <= map->mask);
939 15603 : assert((tag.v & TAG_MSB) == 0);
940 15603 : map->remain -= (map->tag[index].v == TAG_EMPTY);
941 15603 : ++map->count;
942 15603 : tag_set(map, tag, index);
943 15603 : }
944 :
945 : /** Erases an element at the provided index from the tag array, forfeiting its
946 : data in the data array for re-use later. The erase procedure decides how to mark
947 : a removal from the table: deleted or empty. Which option to choose is
948 : determined by what is required to ensure the probing sequence works correctly in
949 : all future cases. */
950 : static inline void
951 8633 : erase(struct CCC_Flat_hash_map *const map, size_t const index) {
952 8633 : assert(index <= map->mask);
953 8633 : size_t const prev_index = (index - GROUP_COUNT) & map->mask;
954 8633 : struct Match_mask const prev_empties
955 8633 : = match_empty(group_load_unaligned(&map->tag[prev_index]));
956 8633 : struct Match_mask const empties
957 8633 : = match_empty(group_load_unaligned(&map->tag[index]));
958 : /* Leading means start at most significant bit aka last group member.
959 : Trailing means start at the least significant bit aka first group member.
960 :
961 : Marking the index as empty is ideal. This will allow future probe
962 : sequences to stop as early as possible for best performance.
963 :
964 : However, we have asked how many DELETED or FULL indices are before and
965 : after our current position. If the answer is greater than or equal to the
966 : size of a group we must mark ourselves as deleted so that probing does
967 : not stop too early. All the other entries in this group are either full
968 : or deleted and empty would incorrectly signal to search functions that
969 : the requested value does not exist in the table. Instead, the request
970 : needs to see that hash collisions or removals have created displacements
971 : that must be probed past to be sure the element in question is absent.
972 :
973 : Because probing operates on groups this check ensures that any group
974 : load at any position that includes this item will continue as long as
975 : needed to ensure the searched key is absent. An important edge case this
976 : covers is one in which the previous group is completely full of FULL or
977 : DELETED entries and this tag will be the first in the next group. This
978 : is an important case where we must mark our tag as deleted. */
979 8633 : struct CCC_Flat_hash_map_tag const m
980 17266 : = (match_leading_zeros(prev_empties) + match_trailing_zeros(empties)
981 8633 : >= GROUP_COUNT)
982 4976 : ? (struct CCC_Flat_hash_map_tag){TAG_DELETED}
983 3657 : : (struct CCC_Flat_hash_map_tag){TAG_EMPTY};
984 8633 : map->remain += (TAG_EMPTY == m.v);
985 8633 : --map->count;
986 8633 : tag_set(map, m, index);
987 8633 : }
988 :
989 : /** Finds the specified hash or first available index where the hash could be
990 : inserted. If the element does not exist and a non-occupied index is returned
991 : that index will have been the first empty or deleted index encountered in the
992 : probe sequence. This function assumes an empty index exists in the table. */
993 : static CCC_Handle
994 29432 : find_key_or_index(
995 : struct CCC_Flat_hash_map const *const map,
996 : void const *const key,
997 : uint64_t const hash
998 : ) {
999 29432 : struct CCC_Flat_hash_map_tag const tag = tag_from(hash);
1000 29432 : size_t const mask = map->mask;
1001 58864 : struct Probe probe = {
1002 29432 : .index = hash & mask,
1003 : .stride = 0,
1004 : };
1005 29432 : CCC_Count empty_deleted = {.error = CCC_RESULT_FAIL};
1006 89242 : for (;;) {
1007 89242 : struct Group const group = group_load_unaligned(&map->tag[probe.index]);
1008 : {
1009 89242 : size_t tag_index = 0;
1010 89242 : struct Match_mask m = match_tag(group, tag);
1011 714921 : while ((tag_index = match_next_one(&m)) != GROUP_COUNT) {
1012 639419 : tag_index = (probe.index + tag_index) & mask;
1013 639419 : if (CCC_likely(is_equal(map, key, tag_index))) {
1014 27480 : return (CCC_Handle){
1015 13740 : .index = tag_index,
1016 : .status = CCC_ENTRY_OCCUPIED,
1017 : };
1018 : }
1019 : }
1020 89242 : }
1021 : /* Taking the first available index once probing is done is important
1022 : to preserve probing operation and efficiency. */
1023 75502 : if (CCC_likely(empty_deleted.error)) {
1024 85100 : size_t const i_take
1025 42550 : = match_trailing_one(match_empty_or_deleted(group));
1026 42550 : if (CCC_likely(i_take != GROUP_COUNT)) {
1027 16637 : empty_deleted.count = (probe.index + i_take) & mask;
1028 16637 : empty_deleted.error = CCC_RESULT_OK;
1029 16637 : }
1030 42550 : }
1031 : /* We just did the work of checking for an empty or deleted index. If we
1032 : didn't find one we should not force another pointless SIMD load and
1033 : match check. */
1034 75502 : if (!empty_deleted.error
1035 75502 : && CCC_likely(match_has_one(match_empty(group)))) {
1036 31384 : return (CCC_Handle){
1037 15692 : .index = empty_deleted.count,
1038 : .status = CCC_ENTRY_VACANT,
1039 : };
1040 : }
1041 59810 : probe.stride += GROUP_COUNT;
1042 59810 : probe.index += probe.stride;
1043 59810 : probe.index &= mask;
1044 89242 : }
1045 29432 : }
1046 :
1047 : /** Finds key or fails when first empty index is encountered after a group fails
1048 : to match. If the search is successful the Count holds the index of the desired
1049 : key, otherwise the Count holds the failure status flag and the index is
1050 : default initialized. This index would not be helpful if an insert index is
1051 : desired because we may have passed preferred deleted indices for insertion to
1052 : find this empty one.
1053 :
1054 : This function is better when a simple lookup is needed as a few branches and
1055 : loads are omitted compared to the search with intention to insert or remove. */
1056 : static CCC_Count
1057 15400 : find_key_or_fail(
1058 : struct CCC_Flat_hash_map const *const map,
1059 : void const *const key,
1060 : uint64_t const hash
1061 : ) {
1062 15400 : struct CCC_Flat_hash_map_tag const tag = tag_from(hash);
1063 15400 : size_t const mask = map->mask;
1064 30800 : struct Probe probe = {
1065 15400 : .index = hash & mask,
1066 : .stride = 0,
1067 : };
1068 48382 : for (;;) {
1069 48382 : struct Group const group = group_load_unaligned(&map->tag[probe.index]);
1070 : {
1071 48382 : size_t tag_index = 0;
1072 48382 : struct Match_mask match = match_tag(group, tag);
1073 57238 : while ((tag_index = match_next_one(&match)) != GROUP_COUNT) {
1074 24143 : tag_index = (probe.index + tag_index) & mask;
1075 24143 : if (CCC_likely(is_equal(map, key, tag_index))) {
1076 15287 : return (CCC_Count){.count = tag_index};
1077 : }
1078 : }
1079 48382 : }
1080 33095 : if (CCC_likely(match_has_one(match_empty(group)))) {
1081 113 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1082 : }
1083 32982 : probe.stride += GROUP_COUNT;
1084 32982 : probe.index += probe.stride;
1085 32982 : probe.index &= mask;
1086 48382 : }
1087 15400 : }
1088 :
1089 : /** Finds the first available empty or deleted insert index or loops forever.
1090 : The caller of this function must know that there is an available empty or
1091 : deleted index in the table. */
1092 : static size_t
1093 16763 : find_index_or_noreturn(
1094 : struct CCC_Flat_hash_map const *const map, uint64_t const hash
1095 : ) {
1096 16763 : size_t const mask = map->mask;
1097 33526 : struct Probe p = {
1098 16763 : .index = hash & mask,
1099 : .stride = 0,
1100 : };
1101 73955 : for (;;) {
1102 147910 : size_t const available_index = match_trailing_one(
1103 73955 : match_empty_or_deleted(group_load_unaligned(&map->tag[p.index]))
1104 : );
1105 73955 : if (CCC_likely(available_index != GROUP_COUNT)) {
1106 16763 : return (p.index + available_index) & mask;
1107 : }
1108 57192 : p.stride += GROUP_COUNT;
1109 57192 : p.index += p.stride;
1110 57192 : p.index &= mask;
1111 73955 : }
1112 16763 : }
1113 :
1114 : /** Finds the first occupied index in the table. The full index is one where the
1115 : user has hash bits occupying the lower 7 bits of the tag. Assumes that the start
1116 : index is the base index of a group of tags such that as we scan groups the
1117 : loads are aligned for performance. */
1118 : static inline void *
1119 286 : find_first_full_index(struct CCC_Flat_hash_map const *const map, size_t start) {
1120 286 : assert((start & ~((size_t)(GROUP_COUNT - 1))) == start);
1121 288 : while (start < (map->mask + 1)) {
1122 552 : size_t const full_index = match_trailing_one(
1123 276 : match_full(group_load_aligned(&map->tag[start]))
1124 : );
1125 276 : if (full_index != GROUP_COUNT) {
1126 274 : return data_at(map, start + full_index);
1127 : }
1128 2 : start += GROUP_COUNT;
1129 276 : }
1130 12 : return NULL;
1131 286 : }
1132 :
1133 : /** Returns the first full group mask if found and progresses the start index
1134 : as needed to find the index corresponding to the first element of this group.
1135 : If no group with a full index is found a 0 mask is returned and the index will
1136 : have been progressed past mask + 1 aka capacity.
1137 :
1138 : Assumes that start is aligned to the 0th tag of a group and only progresses
1139 : start by the size of a group such that it is always aligned. */
1140 : static inline struct Match_mask
1141 458 : find_first_full_group(
1142 : struct CCC_Flat_hash_map const *const map, size_t *const start
1143 : ) {
1144 458 : assert((*start & ~((size_t)(GROUP_COUNT - 1))) == *start);
1145 461 : while (*start < (map->mask + 1)) {
1146 : struct Match_mask const full_group
1147 436 : = match_full(group_load_aligned(&map->tag[*start]));
1148 436 : if (full_group.v) {
1149 433 : return full_group;
1150 : }
1151 3 : *start += GROUP_COUNT;
1152 3 : }
1153 25 : return (struct Match_mask){};
1154 458 : }
1155 :
1156 : /** Returns the first deleted group mask if found and progresses the start index
1157 : as needed to find the index corresponding to the first deleted element of this
1158 : group. If no group with a deleted index is found a 0 mask is returned and the
1159 : index will have been progressed past mask + 1 aka capacity.
1160 :
1161 : Assumes that start is aligned to the 0th tag of a group and only progresses
1162 : start by the size of a group such that it is always aligned. */
1163 : static inline struct Match_mask
1164 606 : find_first_deleted_group(
1165 : struct CCC_Flat_hash_map const *const map, size_t *const start
1166 : ) {
1167 606 : assert((*start & ~((size_t)(GROUP_COUNT - 1))) == *start);
1168 780 : while (*start < (map->mask + 1)) {
1169 : struct Match_mask const deleted_group
1170 768 : = match_deleted(group_load_aligned(&map->tag[*start]));
1171 768 : if (deleted_group.v) {
1172 594 : return deleted_group;
1173 : }
1174 174 : *start += GROUP_COUNT;
1175 174 : }
1176 12 : return (struct Match_mask){};
1177 606 : }
1178 :
1179 : /** Accepts the map, elements to add, and an allocation function if resizing
1180 : may be needed. While containers normally remember their own allocation
1181 : permissions, this function may be called in a variety of scenarios; one of which
1182 : is when the user wants to reserve the necessary space dynamically at runtime
1183 : but only once and for a container that is not given permission to resize
1184 : arbitrarily. If overflow of addition or multiplication occurs an allocator error
1185 : is returned. */
1186 : static CCC_Result
1187 29454 : maybe_rehash(
1188 : struct CCC_Flat_hash_map *const map,
1189 : size_t const to_add,
1190 : CCC_Allocator const *const allocator
1191 : ) {
1192 29454 : if (CCC_unlikely(!map->mask && !allocator->allocate)) {
1193 11 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
1194 : }
1195 29443 : size_t required_total_cap = 0;
1196 29443 : if (ckd_add(&required_total_cap, map->count, to_add)
1197 29443 : || ckd_mul(&required_total_cap, required_total_cap, 8)) {
1198 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1199 : }
1200 29443 : required_total_cap = CCC_bit_ceiling(required_total_cap / 7);
1201 29443 : CCC_Result const init = lazy_initialize(map, required_total_cap, allocator);
1202 29443 : if (init != CCC_RESULT_OK) {
1203 4 : return init;
1204 : }
1205 29439 : if (CCC_likely(map->remain)) {
1206 29377 : return CCC_RESULT_OK;
1207 : }
1208 62 : size_t const current_total_cap = map->mask + 1;
1209 62 : if (allocator->allocate && (map->count + to_add) > current_total_cap / 2) {
1210 25 : return rehash_resize(map, to_add, allocator);
1211 : }
1212 37 : if (map->count == mask_to_capacity_with_load_factor(map->mask)) {
1213 25 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
1214 : }
1215 12 : rehash_in_place(map);
1216 12 : return CCC_RESULT_OK;
1217 29454 : }
1218 :
1219 : /** Rehashes the map in place. Elements may or may not move, depending on
1220 : results. Assumes the table has been allocated and had no more remaining indices
1221 : for insertion. Rehashing in place repeatedly can be expensive so the user
1222 : should ensure to select an appropriate capacity for fixed size tables. */
1223 : static void
1224 12 : rehash_in_place(struct CCC_Flat_hash_map *const map) {
1225 12 : assert((map->mask + 1) % GROUP_COUNT == 0 && "Capacity is group aligned.");
1226 12 : assert(map->tag && map->data && "Map is initialized.");
1227 12 : size_t const mask = map->mask;
1228 780 : for (size_t i = 0; i < mask + 1; i += GROUP_COUNT) {
1229 768 : group_store_aligned(
1230 768 : &map->tag[i],
1231 768 : group_convert_constant_to_empty_and_full_to_deleted(
1232 768 : group_load_aligned(&map->tag[i])
1233 : )
1234 : );
1235 768 : }
1236 12 : (void)memcpy(map->tag + (mask + 1), map->tag, GROUP_COUNT);
1237 : {
1238 12 : size_t group = 0;
1239 12 : struct Match_mask deleted = {};
1240 : /* Because the load factor is roughly 87% we could have large spans of
1241 : unoccupied indices in large tables due to full indices we have
1242 : converted to deleted tags. There could also be many tombstones that
1243 : were just converted to empty indices in the prep loop earlier. We can
1244 : speed things up by performing aligned group scans checking for any
1245 : groups with elements that need to be rehashed. */
1246 606 : while ((deleted = find_first_deleted_group(map, &group)).v) {
1247 : {
1248 594 : size_t rehash = 0;
1249 8680 : while ((rehash = match_next_one(&deleted)) != GROUP_COUNT) {
1250 8086 : rehash += group;
1251 : /* The inner loop swap case may have made a previously
1252 : deleted entry in this group filled with the swapped
1253 : element's hash. The mask cannot be updated to notice this
1254 : and the swapped element was taken care of by retrying to
1255 : find a index in the innermost loop. Therefore skip this
1256 : index. It no longer needs processing. */
1257 8086 : if (map->tag[rehash].v != TAG_DELETED) {
1258 40 : continue;
1259 : }
1260 10723 : for (;;) {
1261 10723 : uint64_t const hash = hasher(map, key_at(map, rehash));
1262 10723 : size_t const index = find_index_or_noreturn(map, hash);
1263 10723 : struct CCC_Flat_hash_map_tag const hash_tag
1264 10723 : = tag_from(hash);
1265 : /* We analyze groups not indices. Do not move the
1266 : element to another index in the same unaligned group
1267 : load. The tag is in the proper group for an unaligned
1268 : load based on where the hashed value will start its
1269 : loads and the match and does not need relocation. */
1270 10723 : if (CCC_likely(
1271 10723 : is_same_group(rehash, index, hash, mask)
1272 : )) {
1273 7982 : tag_set(map, hash_tag, rehash);
1274 7982 : break; /* continues outer loop */
1275 : }
1276 2741 : struct CCC_Flat_hash_map_tag const occupant
1277 2741 : = map->tag[index];
1278 2741 : tag_set(map, hash_tag, index);
1279 2741 : if (occupant.v == TAG_EMPTY) {
1280 64 : tag_set(
1281 64 : map,
1282 64 : (struct CCC_Flat_hash_map_tag){TAG_EMPTY},
1283 64 : rehash
1284 : );
1285 64 : (void)memcpy(
1286 64 : data_at(map, index),
1287 64 : data_at(map, rehash),
1288 64 : map->sizeof_type
1289 : );
1290 64 : break; /* continues outer loop */
1291 : }
1292 : /* The other indices data has been swapped and we rehash
1293 : every element for this algorithm so there is no need
1294 : to write its tag to this index. It's data is in the
1295 : correct location and we now will loop to try to find
1296 : it a rehashed index. */
1297 2677 : assert(occupant.v == TAG_DELETED);
1298 2677 : swap(
1299 2677 : swap_index(map),
1300 2677 : map->sizeof_type,
1301 2677 : data_at(map, rehash),
1302 2677 : data_at(map, index)
1303 : );
1304 10723 : }
1305 : }
1306 594 : }
1307 594 : group += GROUP_COUNT;
1308 : }
1309 12 : }
1310 12 : map->remain = mask_to_capacity_with_load_factor(mask) - map->count;
1311 12 : }
1312 :
1313 : /** Returns true if the position being rehashed would be moved to a new index
1314 : in the same group it is already in. This means when this data is hashed to its
1315 : ideal index in the table, both i and new_index are already in that group that
1316 : would be loaded for simultaneous scanning. */
1317 : static inline CCC_Tribool
1318 10723 : is_same_group(
1319 : size_t const index,
1320 : size_t const new_index,
1321 : uint64_t const hash,
1322 : size_t const mask
1323 : ) {
1324 21446 : return (((index - (hash & mask)) & mask) / GROUP_COUNT)
1325 10723 : == (((new_index - (hash & mask)) & mask) / GROUP_COUNT);
1326 : }
1327 :
1328 : /** Handles resizing and rehashing of a hash table to allow for to_add elements.
1329 : If overflow occurs and allocator error is returned. */
1330 : static CCC_Result
1331 25 : rehash_resize(
1332 : struct CCC_Flat_hash_map *const map,
1333 : size_t const to_add,
1334 : CCC_Allocator const *const allocator
1335 : ) {
1336 25 : assert(((map->mask + 1) & map->mask) == 0);
1337 25 : size_t new_pow2_cap = 0;
1338 25 : if (ckd_add(&new_pow2_cap, (map->mask + 1), to_add)
1339 25 : || ckd_mul(&new_pow2_cap, new_pow2_cap, 2)) {
1340 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1341 : }
1342 25 : new_pow2_cap = CCC_bit_ceiling(new_pow2_cap);
1343 25 : if (!new_pow2_cap) {
1344 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1345 : }
1346 25 : size_t total_bytes = 0;
1347 25 : if (checked_mask_to_total_bytes(
1348 25 : &total_bytes, map->sizeof_type, new_pow2_cap - 1
1349 : )) {
1350 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1351 : }
1352 100 : void *const new_buf = allocator->allocate((CCC_Allocator_arguments){
1353 : .input = NULL,
1354 25 : .bytes = total_bytes,
1355 25 : .alignment = CCC_max(GROUP_COUNT, map->alignof_type),
1356 25 : .context = allocator->context,
1357 : });
1358 25 : if (!new_buf) {
1359 2 : return CCC_RESULT_ALLOCATOR_ERROR;
1360 : }
1361 23 : struct CCC_Flat_hash_map new_map = *map;
1362 23 : new_map.count = 0;
1363 23 : new_map.mask = new_pow2_cap - 1;
1364 23 : new_map.remain = mask_to_capacity_with_load_factor(new_map.mask);
1365 23 : new_map.data = new_buf;
1366 : /* Our static assertions at start of file guarantee this is correct. */
1367 23 : new_map.tag = memset(
1368 23 : tags_base_address(new_map.sizeof_type, new_buf, new_map.mask),
1369 : TAG_EMPTY,
1370 23 : mask_to_tag_bytes(new_map.mask)
1371 : );
1372 0 : assert(
1373 23 : (uintptr_t)new_map.tag % GROUP_COUNT == 0
1374 23 : && "Tag array is at correctly aligned offset from base address of "
1375 : "struct of arrays."
1376 : );
1377 : {
1378 23 : size_t group_start = 0;
1379 23 : struct Match_mask full = {};
1380 454 : while ((full = find_first_full_group(map, &group_start)).v) {
1381 : {
1382 431 : size_t tag_index = 0;
1383 6465 : while ((tag_index = match_next_one(&full)) != GROUP_COUNT) {
1384 6034 : tag_index += group_start;
1385 6034 : uint64_t const hash = hasher(map, key_at(map, tag_index));
1386 12068 : size_t const new_index
1387 6034 : = find_index_or_noreturn(&new_map, hash);
1388 6034 : tag_set(&new_map, tag_from(hash), new_index);
1389 6034 : (void)memcpy(
1390 6034 : data_at(&new_map, new_index),
1391 6034 : data_at(map, tag_index),
1392 6034 : new_map.sizeof_type
1393 : );
1394 6034 : }
1395 431 : }
1396 431 : group_start += GROUP_COUNT;
1397 : }
1398 23 : }
1399 92 : (void)allocator->allocate((CCC_Allocator_arguments){
1400 23 : .input = map->data,
1401 : .bytes = 0,
1402 23 : .alignment = CCC_max(GROUP_COUNT, map->alignof_type),
1403 23 : .context = allocator->context,
1404 : });
1405 23 : map->data = new_map.data;
1406 23 : map->tag = new_map.tag;
1407 23 : map->remain = new_map.remain - map->count;
1408 23 : map->mask = new_map.mask;
1409 23 : return CCC_RESULT_OK;
1410 25 : }
1411 :
1412 : /** Ensures the map is initialized due to our allowance of lazy initialization
1413 : to support various sources of memory at compile and runtime. */
1414 : static inline CCC_Result
1415 29443 : lazy_initialize(
1416 : struct CCC_Flat_hash_map *const map,
1417 : size_t required_capacity,
1418 : CCC_Allocator const *const allocator
1419 : ) {
1420 29443 : if (CCC_likely(!is_uninitialized(map))) {
1421 29379 : return CCC_RESULT_OK;
1422 : }
1423 64 : if (map->mask) {
1424 : /* A fixed size map that is not initialized. */
1425 45 : if (!map->data || map->mask + 1 < required_capacity) {
1426 1 : return CCC_RESULT_ALLOCATOR_ERROR;
1427 : }
1428 44 : if (map->mask + 1 < GROUP_COUNT || !is_power_of_two(map->mask + 1)) {
1429 1 : return CCC_RESULT_ARGUMENT_ERROR;
1430 : }
1431 43 : map->tag = tags_base_address(map->sizeof_type, map->data, map->mask);
1432 43 : (void)memset(map->tag, TAG_EMPTY, mask_to_tag_bytes(map->mask));
1433 43 : } else {
1434 : /* A dynamic map we can re-size as needed. */
1435 19 : required_capacity = CCC_max(required_capacity, GROUP_COUNT);
1436 19 : size_t total_bytes = 0;
1437 19 : if (checked_mask_to_total_bytes(
1438 19 : &total_bytes, map->sizeof_type, required_capacity - 1
1439 : )) {
1440 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1441 : }
1442 76 : map->data = allocator->allocate((CCC_Allocator_arguments){
1443 : .input = NULL,
1444 19 : .bytes = total_bytes,
1445 19 : .alignment = CCC_max(GROUP_COUNT, map->alignof_type),
1446 19 : .context = allocator->context,
1447 : });
1448 19 : if (!map->data) {
1449 2 : return CCC_RESULT_ALLOCATOR_ERROR;
1450 : }
1451 17 : map->mask = required_capacity - 1;
1452 17 : map->remain = mask_to_capacity_with_load_factor(map->mask);
1453 17 : map->tag = tags_base_address(map->sizeof_type, map->data, map->mask);
1454 17 : (void)memset(map->tag, TAG_EMPTY, mask_to_tag_bytes(map->mask));
1455 19 : }
1456 60 : return CCC_RESULT_OK;
1457 29443 : }
1458 :
1459 : static inline void
1460 2 : destory_each(
1461 : struct CCC_Flat_hash_map *const map, CCC_Destructor const *const destructor
1462 : ) {
1463 48 : for (void *i = CCC_flat_hash_map_begin(map);
1464 48 : i != CCC_flat_hash_map_end(map);
1465 46 : i = CCC_flat_hash_map_next(map, i)) {
1466 138 : destructor->destroy((CCC_Arguments){
1467 46 : .type = i,
1468 46 : .context = destructor->context,
1469 : });
1470 46 : }
1471 2 : }
1472 :
1473 : static inline uint64_t
1474 10334561 : hasher(struct CCC_Flat_hash_map const *const map, void const *const any_key) {
1475 31003683 : return map->hasher.hash((CCC_Key_arguments){
1476 10334561 : .key = any_key,
1477 10334561 : .context = map->hasher.context,
1478 : });
1479 : }
1480 :
1481 : static inline CCC_Tribool
1482 663562 : is_equal(
1483 : struct CCC_Flat_hash_map const *const map,
1484 : void const *const key,
1485 : size_t const index
1486 : ) {
1487 3317810 : return map->hasher.compare((CCC_Key_comparator_arguments){
1488 663562 : .key_left = key,
1489 663562 : .type_right = data_at(map, index),
1490 663562 : .context = map->hasher.context,
1491 : })
1492 663562 : == CCC_ORDER_EQUAL;
1493 : }
1494 :
1495 : static inline void *
1496 25298 : key_at(struct CCC_Flat_hash_map const *const map, size_t const index) {
1497 25298 : return (char *)data_at(map, index) + map->key_offset;
1498 : }
1499 :
1500 : static inline void *
1501 11019560 : data_at(struct CCC_Flat_hash_map const *const map, size_t const index) {
1502 11019560 : assert(index <= map->mask);
1503 11019560 : return (char *)map->data + (index * map->sizeof_type);
1504 : }
1505 :
1506 : static inline CCC_Count
1507 2734 : data_index(
1508 : struct CCC_Flat_hash_map const *const map, void const *const data_index
1509 : ) {
1510 2734 : if (CCC_unlikely(
1511 2734 : (char *)data_index
1512 2734 : >= (char *)map->data + (map->sizeof_type * (map->mask + 1))
1513 2734 : || (char *)data_index < (char *)map->data
1514 : )) {
1515 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
1516 : }
1517 5466 : return (CCC_Count){
1518 : .count
1519 2733 : = (size_t)((char *)data_index - (char *)map->data) / map->sizeof_type,
1520 : };
1521 2734 : }
1522 :
1523 : static inline void *
1524 2684 : swap_index(struct CCC_Flat_hash_map const *map) {
1525 2684 : return (char *)map->data + (map->sizeof_type * (map->mask + 1));
1526 : }
1527 :
1528 : static inline void
1529 2684 : swap(void *const temp, size_t const ab_size, void *const a, void *const b) {
1530 2684 : if (CCC_unlikely(!a || !b || a == b)) {
1531 0 : return;
1532 : }
1533 2684 : (void)memcpy(temp, a, ab_size);
1534 2684 : (void)memcpy(a, b, ab_size);
1535 2684 : (void)memcpy(b, temp, ab_size);
1536 5368 : }
1537 :
1538 : static inline void *
1539 5818 : key_in_index(
1540 : struct CCC_Flat_hash_map const *const map, void const *const index
1541 : ) {
1542 5818 : return (char *)index + map->key_offset;
1543 : }
1544 :
1545 : /** Returns true if n is a power of two. 0 is not considered a power of 2. */
1546 : static inline CCC_Tribool
1547 47 : is_power_of_two(size_t const n) {
1548 47 : return n && ((n & (n - 1)) == 0);
1549 : }
1550 :
1551 : /** Returns the total bytes used by the map in the contiguous allocation. This
1552 : includes the bytes for the user data array (swap index included) and the tag
1553 : array. The tag array also has an duplicate group at the end that must be
1554 : counted.
1555 :
1556 : This calculation includes any unusable padding bytes added to the end of the
1557 : user data array. Padding may be required if the alignment of the user type is
1558 : less than that of a group size. This will allow aligned group loads.
1559 :
1560 : This number of bytes should be consistently correct whether the map we are
1561 : dealing with is fixed size or dynamic. A fixed size map could technically have
1562 : more bytes as padding after the tag array but we never need or access those
1563 : bytes so we are only interested in contiguous bytes from start of user data to
1564 : last byte of tag array. */
1565 : static inline size_t
1566 3 : mask_to_total_bytes(size_t const sizeof_type, size_t const mask) {
1567 3 : if (CCC_unlikely(!mask)) {
1568 0 : return 0;
1569 : }
1570 3 : return mask_to_data_bytes(sizeof_type, mask) + mask_to_tag_bytes(mask);
1571 3 : }
1572 :
1573 : /** Returns true if overflow occurred during necessary arithmetic to determine
1574 : total bytes. This means that `size_t` can no longer index the needed bytes for
1575 : the provided mask capacity. If no overflow occurs the function returns false
1576 : and the result of the arithmetic is stored in result. Use this version when
1577 : requesting a new allocation from external user input. Use the unchecked
1578 : version when a valid allocation has already been established on a valid hash
1579 : map.
1580 :
1581 : This calculation includes the bytes for the user data array (swap index
1582 : included) and the tag array. The tag array also has an duplicate group at the
1583 : end that must be counted.
1584 :
1585 : This calculation includes any unusable padding bytes added to the end of the
1586 : user data array. Padding may be required if the alignment of the user type is
1587 : less than that of a group size. This will allow aligned group loads.
1588 :
1589 : This number of bytes should be consistently correct whether the map we are
1590 : dealing with is fixed size or dynamic. A fixed size map could technically have
1591 : more bytes as padding after the tag array but we never need or access those
1592 : bytes so we are only interested in contiguous bytes from start of user data to
1593 : last byte of tag array. */
1594 : static inline CCC_Tribool
1595 44 : checked_mask_to_total_bytes(
1596 : size_t *const result, size_t const sizeof_type, size_t const mask
1597 : ) {
1598 0 : assert(
1599 44 : mask + 2 + GROUP_COUNT > mask
1600 44 : && "mask is a valid power of 2 meaning adding GROUP_COUNT + 2 will not "
1601 : "overflow"
1602 : );
1603 44 : *result = 0;
1604 44 : if (CCC_unlikely(!mask)) {
1605 0 : return CCC_FALSE;
1606 : }
1607 44 : if (ckd_mul(result, sizeof_type, (mask + 2))
1608 44 : || CCC_checked_roundup(result, *result, GROUP_COUNT)
1609 44 : || ckd_add(result, *result, (mask + 1U + GROUP_COUNT))) {
1610 0 : return CCC_TRUE;
1611 : }
1612 44 : return CCC_FALSE;
1613 44 : }
1614 :
1615 : /** Returns the number of bytes taken by the user data array. This includes the
1616 : extra swap index provided at the start of the array. This swap index is never
1617 : accounted for in load factor or capacity calculations but must be remembered in
1618 : cases like this for resizing and allocation purposes.
1619 :
1620 : Any unusable extra alignment padding bytes added to the end of the user data
1621 : array are also accounted for here so that the tag array position starts after
1622 : the correct number of aligned user data bytes. This allows aligned group loads.
1623 :
1624 : Assumes the mask is non-zero. */
1625 : static inline size_t
1626 88 : mask_to_data_bytes(size_t const sizeof_type, size_t const mask) {
1627 : /* Add two because there is always a bonus user data type at the last index
1628 : of the data array for swapping purposes. */
1629 88 : return CCC_roundup(sizeof_type * (mask + 2), GROUP_COUNT);
1630 : }
1631 :
1632 : /** Returns the bytes needed for the tag metadata array. This includes the
1633 : bytes for the duplicate group that is at the end of the tag array.
1634 :
1635 : Assumes the mask is non-zero. */
1636 : static inline size_t
1637 90 : mask_to_tag_bytes(size_t const mask) {
1638 : static_assert(sizeof(struct CCC_Flat_hash_map_tag) == sizeof(uint8_t));
1639 90 : return mask + 1U + GROUP_COUNT;
1640 : }
1641 :
1642 : /** Returns the capacity count that is available with a current load factor of
1643 : 87.5% percent. The returned count is the maximum allowable capacity that can
1644 : store user tags and data before the load factor is reached. The total capacity
1645 : of the table is (mask + 1) which is not the capacity that this function
1646 : calculates. For example, if (mask + 1 = 64), then this function returns 56.
1647 :
1648 : Assumes the mask is non-zero. */
1649 : static inline size_t
1650 21489 : mask_to_capacity_with_load_factor(size_t const mask) {
1651 21489 : return ((mask + 1) / 8) * 7;
1652 : }
1653 :
1654 : /** Returns the correct position of the start of the tag array given the base
1655 : of the data array. This position is determined by the size of the type in the
1656 : data array and the current mask being used for the hash map to which the data
1657 : belongs. */
1658 : static inline struct CCC_Flat_hash_map_tag *
1659 85 : tags_base_address(
1660 : size_t const sizeof_type, void const *const data, size_t const mask
1661 : ) {
1662 : /* Static assertions at top of file ensure this is correct. */
1663 170 : return (struct CCC_Flat_hash_map_tag *)((char *)data
1664 85 : + mask_to_data_bytes(
1665 85 : sizeof_type, mask
1666 : ));
1667 : }
1668 :
1669 : static inline CCC_Tribool
1670 90414 : is_uninitialized(struct CCC_Flat_hash_map const *const map) {
1671 90414 : return !map->data || !map->tag;
1672 : }
1673 :
1674 : /*===================== Intrinsics and Generics =========================*/
1675 :
1676 : /** Below are the implementations of the SIMD or bitwise operations needed to
1677 : run a search on multiple entries in the hash table simultaneously. For now,
1678 : the only container that will use these operations is this one so there is no
1679 : need to break out different headers and sources and clutter the source
1680 : directory. x86 is the only platform that gets the full benefit of SIMD. Apple
1681 : and all other platforms will get a portable implementation due to concerns over
1682 : NEON speed of vectorized instructions. However, loading up groups into a
1683 : uint64_t is still good and counts as simultaneous operations just not the type
1684 : that uses CPU vector lanes for a single instruction. */
1685 :
1686 : /*======================== Tag Implementations =========================*/
1687 :
1688 : /** Sets the specified tag at the index provided. Ensures that the replica
1689 : group at the end of the tag array remains in sync with current tag if needed. */
1690 : static inline void
1691 41063 : tag_set(
1692 : struct CCC_Flat_hash_map *const map,
1693 : struct CCC_Flat_hash_map_tag const tag,
1694 : size_t const index
1695 : ) {
1696 82126 : size_t const replica_byte
1697 41063 : = ((index - GROUP_COUNT) & map->mask) + GROUP_COUNT;
1698 41063 : map->tag[index] = tag;
1699 41063 : map->tag[replica_byte] = tag;
1700 41063 : }
1701 :
1702 : /** Returns CCC_TRUE if the tag holds user hash bits, meaning it is occupied. */
1703 : static inline CCC_Tribool
1704 10272966 : tag_full(struct CCC_Flat_hash_map_tag const tag) {
1705 10272966 : return (tag.v & TAG_MSB) == 0;
1706 : }
1707 :
1708 : /** Returns CCC_TRUE if the tag is one of the two special constants EMPTY or
1709 : DELETED. */
1710 : static inline CCC_Tribool
1711 27548256 : tag_constant(struct CCC_Flat_hash_map_tag const tag) {
1712 27548256 : return (tag.v & TAG_MSB) != 0;
1713 : }
1714 :
1715 : /** Converts a full hash code to a tag fingerprint. The tag consists of the top
1716 : 7 bits of the hash code. Therefore, hash functions with good entropy in the
1717 : upper bits are desirable. */
1718 : static inline struct CCC_Flat_hash_map_tag
1719 10363993 : tag_from(uint64_t const hash) {
1720 20727986 : return (struct CCC_Flat_hash_map_tag){
1721 20727986 : (typeof((struct CCC_Flat_hash_map_tag){}
1722 10363993 : .v))(hash >> ((sizeof(hash) * CHAR_BIT) - 7))
1723 10363993 : & TAG_LOWER_7_MASK,
1724 : };
1725 10363993 : }
1726 :
1727 : /*======================== Index Mask Implementations ====================*/
1728 :
1729 : /** Returns true if any index is on in the mask otherwise false. */
1730 : static inline CCC_Tribool
1731 82684 : match_has_one(struct Match_mask const mask) {
1732 82684 : return mask.v != 0;
1733 : }
1734 :
1735 : /** Return the index of the first trailing one in the given match in the
1736 : range `[0, GROUP_COUNT]` to indicate a positive result of a
1737 : group query operation. This index represents the group member with a tag that
1738 : has matched. Because 0 is a valid index the user must check the index against
1739 : `GROUP_COUNT`, which means no trailing one is found. */
1740 : static inline size_t
1741 906826 : match_trailing_one(struct Match_mask const mask) {
1742 906826 : return count_trailing_zeros(mask);
1743 : }
1744 :
1745 : /** A function to aid in iterating over on bits/indices in a match. The
1746 : function returns the 0-based index of the current on index and then adjusts the
1747 : mask appropriately for future iteration by removing the lowest on index bit. If
1748 : no bits are found the width of the mask is returned. */
1749 : static inline size_t
1750 790045 : match_next_one(struct Match_mask *const mask) {
1751 790045 : assert(mask);
1752 790045 : size_t const index = match_trailing_one(*mask);
1753 790045 : mask->v &= (mask->v - 1);
1754 1580090 : return index;
1755 790045 : }
1756 :
1757 : /** Counts the leading zeros in a match. Leading zeros are those starting
1758 : at the most significant bit. */
1759 : static inline size_t
1760 8633 : match_leading_zeros(struct Match_mask const mask) {
1761 8633 : return count_leading_zeros(mask);
1762 : }
1763 :
1764 : /** Counts the trailing zeros in a match. Trailing zeros are those
1765 : starting at the least significant bit. */
1766 : static inline size_t
1767 8633 : match_trailing_zeros(struct Match_mask const mask) {
1768 8633 : return count_trailing_zeros(mask);
1769 : }
1770 :
1771 : /** We have abstracted at much as we can before this point. Now implementations
1772 : will need to vary based on availability of vectorized instructions. */
1773 : #ifdef CCC_HAS_X86_SIMD
1774 :
1775 : /*========================= Match SIMD Matching ========================*/
1776 :
1777 : /** Returns a match with a bit on if the tag at that index in group g
1778 : matches the provided tag m. If no indices matched this will be a 0 match.
1779 :
1780 : Here is the process to help understand the dense intrinsics.
1781 :
1782 : 1. Load the tag into a 128 bit vector (_mm_set1_epi8). For example m = 0x73:
1783 :
1784 : 0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73
1785 :
1786 : 2. g holds 16 tags from tag array. Find matches (_mm_cmpeq_epi8).
1787 :
1788 : 0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73|0x73
1789 : 0x79|0x33|0x21|0x73|0x45|0x55|0x12|0x54|0x11|0x44|0x73|0xFF|0xFF|0xFF|0xFF|0xFF
1790 : │ │
1791 : 0x00|0x00|0x00|0xFF|0x00|0x00|0x00|0x00|0x00|0x00|0xFF|0x00|0x00|0x00|0x00|0x00
1792 :
1793 : 3. Compress most significant bit of each byte to a uint16_t (_mm_movemask_epi8)
1794 :
1795 : 0x00|0x00|0x00|0xFF|0x00|0x00|0x00|0x00|0x00|0x00|0xFF|0x00|0x00|0x00|0x00|0x00
1796 : ┌──────────┘ │
1797 : │ ┌──────────────────────────────────────┘
1798 : 0b0001000000100000
1799 :
1800 : 4. Return the result as a match.
1801 :
1802 : (struct Match_mask){0b0001000000100000}
1803 :
1804 : With a good hash function it is very likely that the first match will be the
1805 : hashed data and the full comparison will evaluate to true. Note that this
1806 : method inevitably forces a call to the comparison callback function on every
1807 : match so an efficient comparison is beneficial. */
1808 : static inline struct Match_mask
1809 238342 : match_tag(struct Group const group, struct CCC_Flat_hash_map_tag const tag) {
1810 476684 : return (struct Match_mask){
1811 238342 : (typeof((struct Match_mask){}.v))_mm_movemask_epi8(
1812 238342 : _mm_cmpeq_epi8(group.v, _mm_set1_epi8((int8_t)tag.v))
1813 : ),
1814 : };
1815 238342 : }
1816 :
1817 : /** Returns 0 based match with every bit on representing those tags in
1818 : group g that are the empty special constant. The user must interpret this 0
1819 : based index in the context of the probe sequence. */
1820 : static inline struct Match_mask
1821 99950 : match_empty(struct Group const group) {
1822 99950 : return match_tag(group, (struct CCC_Flat_hash_map_tag){TAG_EMPTY});
1823 99950 : }
1824 :
1825 : /** Returns 0 based match with every bit on representing those tags in
1826 : group g that are the deleted special constant. The user must interpret this 0
1827 : based index in the context of the probe sequence. */
1828 : static inline struct Match_mask
1829 768 : match_deleted(struct Group const group) {
1830 768 : return match_tag(group, (struct CCC_Flat_hash_map_tag){TAG_DELETED});
1831 768 : }
1832 :
1833 : /** Returns a 0 based match with every bit on representing those tags
1834 : in the group that are the special constant empty or deleted. These are easy
1835 : to find because they are the one tags in a group with the most significant
1836 : bit on. */
1837 : static inline struct Match_mask
1838 119950 : match_empty_or_deleted(struct Group const group) {
1839 : static_assert(sizeof(int) >= sizeof(uint16_t));
1840 239900 : return (struct Match_mask){
1841 119950 : (typeof((struct Match_mask){}.v))_mm_movemask_epi8(group.v)};
1842 119950 : }
1843 :
1844 : /** Returns a 0 based match with every bit on representing those tags in the
1845 : group that are occupied by a hashed value. These are those tags that have the
1846 : most significant bit off and the lower 7 bits occupied by user hash. */
1847 : static inline struct Match_mask
1848 712 : match_full(struct Group const group) {
1849 1424 : return (struct Match_mask){
1850 712 : (typeof((struct Match_mask){}.v))~match_empty_or_deleted(group).v};
1851 712 : }
1852 :
1853 : /** Matches all full tag indices into a mask excluding the starting position and
1854 : only considering the leading full indices from this position. Assumes start bit
1855 : is 0 indexed such that only the exclusive range of leading bits is considered
1856 : (start_tag, GROUP_COUNT). All trailing bits in the inclusive
1857 : range from [0, start_tag] are zeroed out in the mask.
1858 :
1859 : Assumes start tag is less than group size. */
1860 : static inline struct Match_mask
1861 2733 : match_leading_full(struct Group const group, size_t const start_tag) {
1862 2733 : assert(start_tag < GROUP_COUNT);
1863 5466 : return (struct Match_mask){
1864 5466 : (typeof((struct Match_mask){}.v))(~match_empty_or_deleted(group).v)
1865 2733 : & (MATCH_MASK_0TH_TAG_OFF << start_tag),
1866 : };
1867 2733 : }
1868 :
1869 : /*========================= Group Implementations ========================*/
1870 :
1871 : /** Loads a group starting at source into a 128 bit vector. This is a aligned
1872 : load and the user must ensure the load will not go off then end of the tag
1873 : array. */
1874 : static inline struct Group
1875 4981 : group_load_aligned(struct CCC_Flat_hash_map_tag const *const source) {
1876 4981 : return (struct Group){_mm_load_si128((__m128i *)source)};
1877 4981 : }
1878 :
1879 : /** Stores the source group to destination. The store is aligned and the user
1880 : must ensure the store will not go off the end of the tag array. */
1881 : static inline void
1882 768 : group_store_aligned(
1883 : struct CCC_Flat_hash_map_tag *const destination, struct Group const source
1884 : ) {
1885 768 : _mm_store_si128((__m128i *)destination, source.v);
1886 768 : }
1887 :
1888 : /** Loads a group starting at source into a 128 bit vector. This is an unaligned
1889 : load and the user must ensure the load will not go off then end of the tag
1890 : array. */
1891 : static inline struct Group
1892 228845 : group_load_unaligned(struct CCC_Flat_hash_map_tag const *const source) {
1893 228845 : return (struct Group){_mm_loadu_si128((__m128i *)source)};
1894 228845 : }
1895 :
1896 : /** Converts the empty and deleted constants all TAG_EMPTY and the full tags
1897 : representing hashed user data TAG_DELETED. This will result in the hashed
1898 : fingerprint lower 7 bits of the user data being lost, so a rehash will be
1899 : required for the data corresponding to this index.
1900 :
1901 : For example, both of the special constant tags will be converted as follows.
1902 :
1903 : TAG_EMPTY = 0b1111_1111 -> 0b1111_1111
1904 : TAG_DELETED = 0b1000_0000 -> 0b1111_1111
1905 :
1906 : The full tags with hashed user data will be converted as follows.
1907 :
1908 : TAG_FULL = 0b0101_1101 -> 0b1000_000
1909 :
1910 : The hashed bits are lost because the full index has the high bit off and
1911 : therefore is not a match for the constants mask. */
1912 : static inline struct Group
1913 768 : group_convert_constant_to_empty_and_full_to_deleted(struct Group const group) {
1914 768 : __m128i const zero = _mm_setzero_si128();
1915 768 : __m128i const match_mask_constants = _mm_cmpgt_epi8(zero, group.v);
1916 1536 : return (struct Group){
1917 768 : _mm_or_si128(match_mask_constants, _mm_set1_epi8((int8_t)TAG_DELETED)),
1918 : };
1919 768 : }
1920 :
1921 : #elifdef CCC_HAS_ARM_SIMD
1922 :
1923 : /** Below is the experimental NEON implementation for ARM architectures. This
1924 : implementation assumes a little endian architecture as that is the norm in
1925 : 99.9% of ARM devices. However, monitor trends just in case. This implementation
1926 : is very similar to the portable one. This is largely due to the lack of an
1927 : equivalent operation to the x86_64 _mm_movemask_epi8, the operation responsible
1928 : for compressing a 128 bit vector into a uint16_t. NEON therefore opts for a
1929 : family of 64 bit operations targeted at u8 bytes. If NEON develops an efficient
1930 : instruction for compressing a 128 bit result into an int--or in our case a
1931 : uint16_t--we should revisit this section for 128 bit targeted intrinsics. */
1932 :
1933 : /*========================= Match SIMD Matching ========================*/
1934 :
1935 : /** Returns a match with the most significant bit set for each byte to
1936 : indicate if the byte in the group matched the mask to be searched. The only
1937 : bit on shall be this most significant bit to ensure iterating through index
1938 : masks is easier and counting bits make sense in the find loops. */
1939 : static inline struct Match_mask
1940 : match_tag(struct Group const group, struct CCC_Flat_hash_map_tag const tag) {
1941 : struct Match_mask const mask = {
1942 : vget_lane_u64(
1943 : vreinterpret_u64_u8(vceq_u8(group.v, vdup_n_u8(tag.v))), 0
1944 : ) & MATCH_MASK_TAGS_MSBS,
1945 : };
1946 : assert(
1947 : (mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
1948 : && "For bit counting and iteration purposes the most significant bit "
1949 : "in every byte will indicate a match for a tag has occurred."
1950 : );
1951 : return mask;
1952 : }
1953 :
1954 : /** Returns 0 based struct Match_mask with every bit on representing those tags
1955 : in group g that are the empty special constant. The user must interpret this 0
1956 : based index in the context of the probe sequence. */
1957 : static inline struct Match_mask
1958 : match_empty(struct Group const group) {
1959 : return match_tag(group, (struct CCC_Flat_hash_map_tag){TAG_EMPTY});
1960 : }
1961 :
1962 : /** Returns 0 based struct Match_mask with every bit on representing those tags
1963 : in group g that are the empty special constant. The user must interpret this 0
1964 : based index in the context of the probe sequence. */
1965 : static inline struct Match_mask
1966 : match_deleted(struct Group const group) {
1967 : return match_tag(group, (struct CCC_Flat_hash_map_tag){TAG_DELETED});
1968 : }
1969 :
1970 : /** Returns a 0 based match with every bit on representing those tags
1971 : in the group that are the special constant empty or deleted. These are easy
1972 : to find because they are the one tags in a group with the most significant
1973 : bit on. */
1974 : static inline struct Match_mask
1975 : match_empty_or_deleted(struct Group const group) {
1976 : uint8x8_t const constant_tag_matches
1977 : = vcltz_s8(vreinterpret_s8_u8(group.v));
1978 : struct Match_mask const empty_deleted_mask = {
1979 : vget_lane_u64(vreinterpret_u64_u8(constant_tag_matches), 0)
1980 : & MATCH_MASK_TAGS_MSBS,
1981 : };
1982 : assert(
1983 : (empty_deleted_mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
1984 : && "For bit counting and iteration purposes the most significant bit "
1985 : "in every byte will indicate a match for a tag has occurred."
1986 : );
1987 : return empty_deleted_mask;
1988 : }
1989 :
1990 : /** Returns a 0 based match with every bit on representing those tags in the
1991 : group that are occupied by a user hash value. These are those tags that have
1992 : the most significant bit off and the lower 7 bits occupied by user hash. */
1993 : static inline struct Match_mask
1994 : match_full(struct Group const g) {
1995 : uint8x8_t const hash_bits_matches = vcgez_s8(vreinterpret_s8_u8(g.v));
1996 : struct Match_mask const full_indices_mask = {
1997 : vget_lane_u64(vreinterpret_u64_u8(hash_bits_matches), 0)
1998 : & MATCH_MASK_TAGS_MSBS,
1999 : };
2000 : assert(
2001 : (full_indices_mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2002 : && "For bit counting and iteration purposes the most significant bit "
2003 : "in every byte will indicate a match for a tag has occurred."
2004 : );
2005 : return full_indices_mask;
2006 : }
2007 :
2008 : /** Returns a 0 based match with every bit on representing those tags in the
2009 : group that are occupied by a user hash value leading from the provided start
2010 : bit. These are those tags that have the most significant bit off and the lower 7
2011 : bits occupied by user hash. All bits in the tags from [0, start_tag] are zeroed
2012 : out such that only the tags in the range (start_tag,
2013 : GROUP_COUNT) are considered.
2014 :
2015 : Assumes start tag is less than group size. */
2016 : static inline struct Match_mask
2017 : match_leading_full(struct Group const group, size_t const start_tag) {
2018 : assert(start_tag < GROUP_COUNT);
2019 : uint8x8_t const hash_bits_matches = vcgez_s8(vreinterpret_s8_u8(group.v));
2020 : struct Match_mask const full_indices_mask = {
2021 : vget_lane_u64(vreinterpret_u64_u8(hash_bits_matches), 0)
2022 : & (MATCH_MASK_0TH_TAG_OFF << (start_tag * TAG_BITS)),
2023 : };
2024 : assert(
2025 : (full_indices_mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2026 : && "For bit counting and iteration purposes the most significant bit "
2027 : "in every byte will indicate a match for a tag has occurred."
2028 : );
2029 : return full_indices_mask;
2030 : }
2031 :
2032 : /*========================= Group Implementations ========================*/
2033 :
2034 : /** Loads a group starting at source into a 8x8 (64) bit vector. This is an
2035 : aligned load and the user must ensure the load will not go off then end of the
2036 : tag array. */
2037 : static inline struct Group
2038 : group_load_aligned(struct CCC_Flat_hash_map_tag const *const source) {
2039 : return (struct Group){vld1_u8(&source->v)};
2040 : }
2041 :
2042 : /** Stores the source group to destination. The store is aligned and the user
2043 : must ensure the store will not go off the end of the tag array. */
2044 : static inline void
2045 : group_store_aligned(
2046 : struct CCC_Flat_hash_map_tag *const destination, struct Group const source
2047 : ) {
2048 : vst1_u8(&destination->v, source.v);
2049 : }
2050 :
2051 : /** Loads a group starting at source into a 8x8 (64) bit vector. This is an
2052 : unaligned load and the user must ensure the load will not go off then end of the
2053 : tag array. */
2054 : static inline struct Group
2055 : group_load_unaligned(struct CCC_Flat_hash_map_tag const *const source) {
2056 : return (struct Group){vld1_u8(&source->v)};
2057 : }
2058 :
2059 : /** Converts the empty and deleted constants all TAG_EMPTY and the full tags
2060 : representing hashed user data TAG_DELETED. This will result in the hashed
2061 : fingerprint lower 7 bits of the user data being lost, so a rehash will be
2062 : required for the data corresponding to this index.
2063 :
2064 : For example, both of the special constant tags will be converted as follows.
2065 :
2066 : TAG_EMPTY = 0b1111_1111 -> 0b1111_1111
2067 : TAG_DELETED = 0b1000_0000 -> 0b1111_1111
2068 :
2069 : The full tags with hashed user data will be converted as follows.
2070 :
2071 : TAG_FULL = 0b0101_1101 -> 0b1000_000
2072 :
2073 : The hashed bits are lost because the full index has the high bit off and
2074 : therefore is not a match for the constants mask. */
2075 : static inline struct Group
2076 : group_convert_constant_to_empty_and_full_to_deleted(struct Group const group) {
2077 : uint8x8_t const constant = vcltz_s8(vreinterpret_s8_u8(group.v));
2078 : return (struct Group){vorr_u8(constant, vdup_n_u8(TAG_MSB))};
2079 : }
2080 :
2081 : #else /* FALLBACK PORTABLE IMPLEMENTATION */
2082 :
2083 : /* What follows is the generic portable implementation when high width SIMD
2084 : can't be achieved. This ideally works for most platforms. */
2085 :
2086 : /*========================= Endian Helpers ==============================*/
2087 :
2088 : /* Returns 1=true if platform is little endian, else false for big endian. */
2089 : static inline int
2090 : is_little_endian(void) {
2091 : unsigned int x = 1;
2092 : char *c = (char *)&x;
2093 : return (int)*c;
2094 : }
2095 :
2096 : /* Returns a mask converted to little endian byte layout. On a little endian
2097 : platform the value is returned, otherwise byte swapping occurs. */
2098 : static inline struct Match_mask
2099 : to_little_endian(struct Match_mask mask) {
2100 : if (is_little_endian()) {
2101 : return mask;
2102 : }
2103 : # if defined(__has_builtin) && __has_builtin(__builtin_bswap64)
2104 : mask.v = __builtin_bswap64(mask.v);
2105 : # else
2106 : mask.v = (mask.v & 0x00000000FFFFFFFF) << 32
2107 : | (mask.v & 0xFFFFFFFF00000000) >> 32;
2108 : mask.v = (mask.v & 0x0000FFFF0000FFFF) << 16
2109 : | (mask.v & 0xFFFF0000FFFF0000) >> 16;
2110 : mask.v = (mask.v & 0x00FF00FF00FF00FF) << 8
2111 : | (mask.v & 0xFF00FF00FF00FF00) >> 8;
2112 : # endif
2113 : return mask;
2114 : }
2115 :
2116 : /*========================= Match SRMD Matching ========================*/
2117 :
2118 : /** Returns a struct Match_mask indicating all tags in the group which may have
2119 : the given value. The struct Match_mask will only have the most significant bit
2120 : on within the byte representing the tag for the struct Match_mask. This function
2121 : may return a false positive in certain cases where the tag in the group differs
2122 : from the searched value only in its lowest bit. This is fine because:
2123 : - This never happens for `EMPTY` and `DELETED`, only full entries.
2124 : - The check for key equality will catch these.
2125 : - This only happens if there is at least 1 true match.
2126 : - The chance of this happening is very low (< 1% chance per byte).
2127 : This algorithm is derived from:
2128 : https://graphics.stanford.edu/~seander/bithacks.html##ValueInWord */
2129 : static inline struct Match_mask
2130 : match_tag(struct Group const group, struct CCC_Flat_hash_map_tag const tag) {
2131 : struct Group const match = {
2132 : group.v
2133 : ^ ((((typeof(group.v))tag.v) << (TAG_BITS * 7UL))
2134 : | (((typeof(group.v))tag.v) << (TAG_BITS * 6UL))
2135 : | (((typeof(group.v))tag.v) << (TAG_BITS * 5UL))
2136 : | (((typeof(group.v))tag.v) << (TAG_BITS * 4UL))
2137 : | (((typeof(group.v))tag.v) << (TAG_BITS * 3UL))
2138 : | (((typeof(group.v))tag.v) << (TAG_BITS * 2UL))
2139 : | (((typeof(group.v))tag.v) << TAG_BITS) | (tag.v)),
2140 : };
2141 : struct Match_mask const mask = to_little_endian((struct Match_mask){
2142 : (match.v - MATCH_MASK_TAGS_LSBS) & ~match.v & MATCH_MASK_TAGS_MSBS,
2143 : });
2144 : assert(
2145 : (mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2146 : && "For bit counting and iteration purposes the most significant bit "
2147 : "in every byte will indicate a match for a tag has occurred."
2148 : );
2149 : return mask;
2150 : }
2151 :
2152 : /** Returns a struct Match_mask with the most significant bit in every byte on
2153 : if that tag in g is empty. */
2154 : static inline struct Match_mask
2155 : match_empty(struct Group const group) {
2156 : /* EMPTY has all bits on and DELETED has the most significant bit on so
2157 : EMPTY must have the top 2 bits on. Because the empty mask has only
2158 : the most significant bit on this also ensure the mask has only the
2159 : MSB on to indicate a match. */
2160 : struct Match_mask const match = to_little_endian((struct Match_mask){
2161 : group.v & (group.v << 1) & MATCH_MASK_TAGS_EMPTY,
2162 : });
2163 : assert(
2164 : (match.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2165 : && "For bit counting and iteration purposes the most significant bit "
2166 : "in every byte will indicate a match for a tag has occurred."
2167 : );
2168 : return match;
2169 : }
2170 :
2171 : /** Returns a struct Match_mask with the most significant bit in every byte on
2172 : if that tag in g is empty. */
2173 : static inline struct Match_mask
2174 : match_deleted(struct Group const group) {
2175 : /* This is the same process as matching a tag but easier because we can
2176 : make the empty mask a constant at compile time instead of runtime. */
2177 : struct Group const empty_group = {group.v ^ MATCH_MASK_TAGS_EMPTY};
2178 : struct Match_mask const match = to_little_endian((struct Match_mask){
2179 : (empty_group.v - MATCH_MASK_TAGS_LSBS) & ~empty_group.v
2180 : & MATCH_MASK_TAGS_MSBS,
2181 : });
2182 : assert(
2183 : (match.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2184 : && "For bit counting and iteration purposes the most significant bit "
2185 : "in every byte will indicate a match for a tag has occurred."
2186 : );
2187 : return match;
2188 : }
2189 :
2190 : /** Returns a match with the most significant bit in every byte on if
2191 : that tag in g is empty or deleted. This is found by the most significant bit. */
2192 : static inline struct Match_mask
2193 : match_empty_or_deleted(struct Group const group) {
2194 : struct Match_mask const res
2195 : = to_little_endian((struct Match_mask){group.v & MATCH_MASK_TAGS_MSBS});
2196 : assert(
2197 : (res.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2198 : && "For bit counting and iteration purposes the most significant bit "
2199 : "in every byte will indicate a match for a tag has occurred."
2200 : );
2201 : return res;
2202 : }
2203 :
2204 : /** Returns a 0 based match with every bit on representing those tags in the
2205 : group that are occupied by a user hash value. These are those tags that have
2206 : the most significant bit off and the lower 7 bits occupied by user hash. */
2207 : static inline struct Match_mask
2208 : match_full(struct Group const group) {
2209 : struct Match_mask const mask = to_little_endian((struct Match_mask){
2210 : (~group.v) & MATCH_MASK_TAGS_MSBS});
2211 : assert(
2212 : (mask.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2213 : && "For bit counting and iteration purposes the most significant bit "
2214 : "in every byte will indicate a match for a tag has occurred."
2215 : );
2216 : return mask;
2217 : }
2218 :
2219 : /** Returns a 0 based match with every bit on representing those tags in the
2220 : group that are occupied by a user hash value leading from the provided start
2221 : bit. These are those tags that have the most significant bit off and the lower 7
2222 : bits occupied by user hash. All bits in the tags from [0, start_tag] are zeroed
2223 : out such that only the tags in the range (start_tag,
2224 : GROUP_COUNT) are considered.
2225 :
2226 : Assumes start_tag is less than group size. */
2227 : static inline struct Match_mask
2228 : match_leading_full(struct Group const group, size_t const start_tag) {
2229 : assert(start_tag < GROUP_COUNT);
2230 : /* The 0th tag off mask we use also happens to ensure only the MSB in each
2231 : byte of a match is on as the assert confirms after. */
2232 : struct Match_mask const match = to_little_endian((struct Match_mask){
2233 : (~group.v) & (MATCH_MASK_0TH_TAG_OFF << (start_tag * TAG_BITS)),
2234 : });
2235 : assert(
2236 : (match.v & MATCH_MASK_TAGS_OFF_BITS) == 0
2237 : && "For bit counting and iteration purposes the most significant bit "
2238 : "in every byte will indicate a match for a tag has occurred."
2239 : );
2240 : return match;
2241 : }
2242 :
2243 : /*========================= Group Implementations ========================*/
2244 :
2245 : /** Loads tags into a group without violating strict aliasing. */
2246 : static inline struct Group
2247 : group_load_aligned(struct CCC_Flat_hash_map_tag const *const source) {
2248 : struct Group group;
2249 : (void)memcpy(&group, source, sizeof(group));
2250 : return group;
2251 : }
2252 :
2253 : /** Stores a group back into the tag array without violating strict aliasing. */
2254 : static inline void
2255 : group_store_aligned(
2256 : struct CCC_Flat_hash_map_tag *const destination, struct Group const source
2257 : ) {
2258 : (void)memcpy(destination, &source, sizeof(source));
2259 : }
2260 :
2261 : /** Loads tags into a group without violating strict aliasing. */
2262 : static inline struct Group
2263 : group_load_unaligned(struct CCC_Flat_hash_map_tag const *const source) {
2264 : struct Group group;
2265 : (void)memcpy(&group, source, sizeof(group));
2266 : return group;
2267 : }
2268 :
2269 : /** Converts the empty and deleted constants all TAG_EMPTY and the full tags
2270 : representing hashed user data TAG_DELETED. This will result in the hashed
2271 : fingerprint lower 7 bits of the user data being lost, so a rehash will be
2272 : required for the data corresponding to this index.
2273 :
2274 : For example, both of the special constant tags will be converted as follows.
2275 :
2276 : TAG_EMPTY = 0b1111_1111 -> 0b1111_1111
2277 : TAG_DELETED = 0b1000_0000 -> 0b1111_1111
2278 :
2279 : The full tags with hashed user data will be converted as follows.
2280 :
2281 : TAG_FULL = 0b0101_1101 -> 0b1000_000
2282 :
2283 : The hashed bits are lost because the full index has the high bit off and
2284 : therefore is not a match for the constants mask. */
2285 : static inline struct Group
2286 : group_convert_constant_to_empty_and_full_to_deleted(struct Group group) {
2287 : group.v = ~group.v & MATCH_MASK_TAGS_MSBS;
2288 : group.v = ~group.v + (group.v >> (TAG_BITS - 1));
2289 : return group;
2290 : }
2291 :
2292 : #endif /* defined(CCC_HAS_X86_SIMD) */
2293 :
2294 : /*==================== Bit Counting for Index Mask =======================*/
2295 :
2296 : /** How we count bits can vary depending on the implementation, group size,
2297 : and struct Match_mask width. Keep the bit counting logic separate here so the
2298 : above implementations can simply rely on counting zeros that yields correct
2299 : results for their implementation. */
2300 :
2301 : #ifdef CCC_HAS_X86_SIMD
2302 :
2303 : static_assert(
2304 : sizeof((struct Match_mask){}.v) <= sizeof(unsigned),
2305 : "a struct Match_mask is expected to be smaller than an unsigned due to "
2306 : "available builtins on the given platform."
2307 : );
2308 : static_assert(
2309 : ((sizeof(typeof((struct Match_mask){}.v)) * CHAR_BIT) - 1)
2310 : == GROUP_COUNT - 1,
2311 : "trailing and leading zeros produces number of bits we expect for mask"
2312 : );
2313 :
2314 : static inline unsigned
2315 915459 : count_trailing_zeros(struct Match_mask const mask) {
2316 915459 : return (unsigned)CCC_count_trailing_zeros(mask.v);
2317 : }
2318 :
2319 : static inline unsigned
2320 8633 : count_leading_zeros(struct Match_mask const mask) {
2321 8633 : return (unsigned)CCC_count_leading_zeros(mask.v);
2322 : }
2323 :
2324 : #else /* NEON and PORTABLE implementation count bits the same way. */
2325 :
2326 : static_assert(
2327 : ((sizeof(typeof((struct Match_mask){}.v)) * CHAR_BIT) - 1) / GROUP_COUNT
2328 : == GROUP_COUNT - 1,
2329 : "trailing and leading zeros produces number of bits we expect for mask"
2330 : );
2331 :
2332 : static inline unsigned
2333 : count_trailing_zeros(struct Match_mask const mask) {
2334 : return (unsigned)CCC_count_trailing_zeros(mask.v) / GROUP_COUNT;
2335 : }
2336 :
2337 : static inline unsigned
2338 : count_leading_zeros(struct Match_mask const mask) {
2339 : return (unsigned)CCC_count_leading_zeros(mask.v) / GROUP_COUNT;
2340 : }
2341 :
2342 : #endif /* defined(CCC_HAS_X86_SIMD) */
2343 :
2344 : /** The following Apache license follows as required by the Rust Hashbrown
2345 : table which in turn is based on the Abseil Flat Hash Map developed at Google:
2346 :
2347 : Abseil: https://github.com/abseil/abseil-cpp
2348 : Hashbrown: https://github.com/rust-lang/hashbrown
2349 :
2350 : Because both Abseil and Hashbrown require inclusion of the following license,
2351 : it is included below. The implementation in this file is based strictly on the
2352 : Hashbrown version and has been modified to work with C and the C Container
2353 : Collection.
2354 :
2355 : Apache License
2356 : Version 2.0, January 2004
2357 : http://www.apache.org/licenses/
2358 :
2359 : TERMS AND CONDITIONS FOR USE, REPRODUCTION, AND DISTRIBUTION
2360 :
2361 : 1. Definitions.
2362 :
2363 : "License" shall mean the terms and conditions for use, reproduction,
2364 : and distribution as defined by Sections 1 through 9 of this document.
2365 :
2366 : "Licensor" shall mean the copyright owner or entity authorized by
2367 : the copyright owner that is granting the License.
2368 :
2369 : "Legal Entity" shall mean the union of the acting entity and all
2370 : other entities that control, are controlled by, or are under common
2371 : control with that entity. For the purposes of this definition,
2372 : "control" means (i) the power, direct or indirect, to cause the
2373 : direction or management of such entity, whether by contract or
2374 : otherwise, or (ii) ownership of fifty percent (50%) or more of the
2375 : outstanding shares, or (iii) beneficial ownership of such entity.
2376 :
2377 : "You" (or "Your") shall mean an individual or Legal Entity
2378 : exercising permissions granted by this License.
2379 :
2380 : "Source" form shall mean the preferred form for making modifications,
2381 : including but not limited to software source code, documentation
2382 : source, and configuration files.
2383 :
2384 : "Object" form shall mean any form resulting from mechanical
2385 : transformation or translation of a Source form, including but
2386 : not limited to compiled object code, generated documentation,
2387 : and conversions to other media types.
2388 :
2389 : "Work" shall mean the work of authorship, whether in Source or
2390 : Object form, made available under the License, as indicated by a
2391 : copyright notice that is included in or attached to the work
2392 : (an example is provided in the Appendix below).
2393 :
2394 : "Derivative Works" shall mean any work, whether in Source or Object
2395 : form, that is based on (or derived from) the Work and for which the
2396 : editorial revisions, annotations, elaborations, or other modifications
2397 : represent, as a whole, an original work of authorship. For the purposes
2398 : of this License, Derivative Works shall not include works that remain
2399 : separable from, or merely link (or bind by name) to the interfaces of,
2400 : the Work and Derivative Works thereof.
2401 :
2402 : "Contribution" shall mean any work of authorship, including
2403 : the original version of the Work and any modifications or additions
2404 : to that Work or Derivative Works thereof, that is intentionally
2405 : submitted to Licensor for inclusion in the Work by the copyright owner
2406 : or by an individual or Legal Entity authorized to submit on behalf of
2407 : the copyright owner. For the purposes of this definition, "submitted"
2408 : means any form of electronic, verbal, or written communication sent
2409 : to the Licensor or its representatives, including but not limited to
2410 : communication on electronic mailing lists, source code control systems,
2411 : and issue tracking systems that are managed by, or on behalf of, the
2412 : Licensor for the purpose of discussing and improving the Work, but
2413 : excluding communication that is conspicuously marked or otherwise
2414 : designated in writing by the copyright owner as "Not a Contribution."
2415 :
2416 : "Contributor" shall mean Licensor and any individual or Legal Entity
2417 : on behalf of whom a Contribution has been received by Licensor and
2418 : subsequently incorporated within the Work.
2419 :
2420 : 2. Grant of Copyright License. Subject to the terms and conditions of
2421 : this License, each Contributor hereby grants to You a perpetual,
2422 : worldwide, non-exclusive, no-charge, royalty-free, irrevocable
2423 : copyright license to reproduce, prepare Derivative Works of,
2424 : publicly display, publicly perform, sublicense, and distribute the
2425 : Work and such Derivative Works in Source or Object form.
2426 :
2427 : 3. Grant of Patent License. Subject to the terms and conditions of
2428 : this License, each Contributor hereby grants to You a perpetual,
2429 : worldwide, non-exclusive, no-charge, royalty-free, irrevocable
2430 : (except as stated in this section) patent license to make, have made,
2431 : use, offer to sell, sell, import, and otherwise transfer the Work,
2432 : where such license applies only to those patent claims licensable
2433 : by such Contributor that are necessarily infringed by their
2434 : Contribution(s) alone or by combination of their Contribution(s)
2435 : with the Work to which such Contribution(s) was submitted. If You
2436 : institute patent litigation against any entity (including a
2437 : cross-claim or counterclaim in a lawsuit) alleging that the Work
2438 : or a Contribution incorporated within the Work constitutes direct
2439 : or contributory patent infringement, then any patent licenses
2440 : granted to You under this License for that Work shall terminate
2441 : as of the date such litigation is filed.
2442 :
2443 : 4. Redistribution. You may reproduce and distribute copies of the
2444 : Work or Derivative Works thereof in any medium, with or without
2445 : modifications, and in Source or Object form, provided that You
2446 : meet the following conditions:
2447 :
2448 : (a) You must give any other recipients of the Work or
2449 : Derivative Works a copy of this License; and
2450 :
2451 : (b) You must cause any modified files to carry prominent notices
2452 : stating that You changed the files; and
2453 :
2454 : (c) You must retain, in the Source form of any Derivative Works
2455 : that You distribute, all copyright, patent, trademark, and
2456 : attribution notices from the Source form of the Work,
2457 : excluding those notices that do not pertain to any part of
2458 : the Derivative Works; and
2459 :
2460 : (d) If the Work includes a "NOTICE" text file as part of its
2461 : distribution, then any Derivative Works that You distribute must
2462 : include a readable copy of the attribution notices contained
2463 : within such NOTICE file, excluding those notices that do not
2464 : pertain to any part of the Derivative Works, in at least one
2465 : of the following places: within a NOTICE text file distributed
2466 : as part of the Derivative Works; within the Source form or
2467 : documentation, if provided along with the Derivative Works; or,
2468 : within a display generated by the Derivative Works, if and
2469 : wherever such third-party notices normally appear. The contents
2470 : of the NOTICE file are for informational purposes only and
2471 : do not modify the License. You may add Your own attribution
2472 : notices within Derivative Works that You distribute, alongside
2473 : or as an addendum to the NOTICE text from the Work, provided
2474 : that such additional attribution notices cannot be construed
2475 : as modifying the License.
2476 :
2477 : You may add Your own copyright statement to Your modifications and
2478 : may provide additional or different license terms and conditions
2479 : for use, reproduction, or distribution of Your modifications, or
2480 : for any such Derivative Works as a whole, provided Your use,
2481 : reproduction, and distribution of the Work otherwise complies with
2482 : the conditions stated in this License.
2483 :
2484 : 5. Submission of Contributions. Unless You explicitly state otherwise,
2485 : any Contribution intentionally submitted for inclusion in the Work
2486 : by You to the Licensor shall be under the terms and conditions of
2487 : this License, without any additional terms or conditions.
2488 : Notwithstanding the above, nothing herein shall supersede or modify
2489 : the terms of any separate license agreement you may have executed
2490 : with Licensor regarding such Contributions.
2491 :
2492 : 6. Trademarks. This License does not grant permission to use the trade
2493 : names, trademarks, service marks, or product names of the Licensor,
2494 : except as required for reasonable and customary use in describing the
2495 : origin of the Work and reproducing the content of the NOTICE file.
2496 :
2497 : 7. Disclaimer of Warranty. Unless required by applicable law or
2498 : agreed to in writing, Licensor provides the Work (and each
2499 : Contributor provides its Contributions) on an "AS IS" BASIS,
2500 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or
2501 : implied, including, without limitation, any warranties or conditions
2502 : of TITLE, NON-INFRINGEMENT, MERCHANTABILITY, or FITNESS FOR A
2503 : PARTICULAR PURPOSE. You are solely responsible for determining the
2504 : appropriateness of using or redistributing the Work and assume any
2505 : risks associated with Your exercise of permissions under this License.
2506 :
2507 : 8. Limitation of Liability. In no event and under no legal theory,
2508 : whether in tort (including negligence), contract, or otherwise,
2509 : unless required by applicable law (such as deliberate and grossly
2510 : negligent acts) or agreed to in writing, shall any Contributor be
2511 : liable to You for damages, including any direct, indirect, special,
2512 : incidental, or consequential damages of any character arising as a
2513 : result of this License or out of the use or inability to use the
2514 : Work (including but not limited to damages for loss of goodwill,
2515 : work stoppage, computer failure or malfunction, or any and all
2516 : other commercial damages or losses), even if such Contributor
2517 : has been advised of the possibility of such damages.
2518 :
2519 : 9. Accepting Warranty or Additional Liability. While redistributing
2520 : the Work or Derivative Works thereof, You may choose to offer,
2521 : and charge a fee for, acceptance of support, warranty, indemnity,
2522 : or other liability obligations and/or rights consistent with this
2523 : License. However, in accepting such obligations, You may act only
2524 : on Your own behalf and on Your sole responsibility, not on behalf
2525 : of any other Contributor, and only if You agree to indemnify,
2526 : defend, and hold each Contributor harmless for any liability
2527 : incurred by, or claims asserted against, such Contributor by reason
2528 : of your accepting any such warranty or additional liability.
2529 :
2530 : END OF TERMS AND CONDITIONS
2531 :
2532 : APPENDIX: How to apply the Apache License to your work.
2533 :
2534 : To apply the Apache License to your work, attach the following
2535 : boilerplate notice, with the fields enclosed by brackets "{}"
2536 : replaced with your own identifying information. (Don't include
2537 : the brackets!) The text should be enclosed in the appropriate
2538 : comment syntax for the file format. We also recommend that a
2539 : file or class name and description of purpose be included on the
2540 : same "printed page" as the copyright notice for easier
2541 : identification within third-party archives.
2542 :
2543 : Copyright {yyyy} {name of copyright owner}
2544 :
2545 : Licensed under the Apache License, Version 2.0 (the "License");
2546 : you may not use this file except in compliance with the License.
2547 : You may obtain a copy of the License at
2548 :
2549 : http://www.apache.org/licenses/LICENSE-2.0
2550 :
2551 : Unless required by applicable law or agreed to in writing, software
2552 : distributed under the License is distributed on an "AS IS" BASIS,
2553 : WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
2554 : See the License for the specific language governing permissions and
2555 : limitations under the License. */
|
