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