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