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