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 a Bit Set using blocks of platform defined integers
16 : for speed and efficiency. The implementation aims for constant and linear time
17 : operations at all times, specifically when implementing more complicated range
18 : based operations over the set.
19 :
20 : It is also important to avoid modulo and division operations whenever possible.
21 : This is why much of the code revolves around obtaining indices by processing
22 : entire blocks at a time, rather than using mathematical operations to
23 : conceptually iterate over individual bits.
24 :
25 : Finally, the code is able to unite most functions for finding zeros or ones
26 : into a single function that accepts true or false as an additional argument.
27 : This is because every search for a zero can be solved by bitwise inverting a
28 : block and searching for a 1 instead. This elimination of identical functions
29 : costs a single branch in the function and is worth it to avoid code duplication
30 : and bug doubling. */
31 : /** C23 provided headers. */
32 : #include <assert.h>
33 : #include <limits.h>
34 : #include <stdckdint.h>
35 : #include <stddef.h>
36 : #include <stdint.h>
37 :
38 : /** CCC provided headers. */
39 : #include "ccc/configuration.h" /* IWYU pragma: keep */
40 : #include "ccc/flat_bitset.h"
41 : #include "ccc/private/private_flat_bitset.h"
42 : #include "ccc/types.h"
43 : #include "source/compiler_utilities.h"
44 :
45 : /*========================= Type Declarations ============================*/
46 :
47 : /** @internal The type representing the word size used for each block of the
48 : Flat_bitset. This type may vary depending on the platform in order to maximize
49 : performance, so it is given a type. The implementation then should not concern
50 : itself with the word size.
51 :
52 : The implementation may assume that the block is a standard integer width on
53 : the given platform that is compatible with all basic arithmetic and bitwise
54 : operations. If SIMD is implemented then multiple blocks may be processed under
55 : this same assumption. */
56 : typedef typeof(*(struct CCC_Flat_bitset){}.blocks) Bit_block;
57 :
58 : /** @internal Used frequently so call the builtin just once. */
59 : enum : size_t {
60 : /** @internal Bytes of a bit block to help with byte calculations. */
61 : SIZEOF_BLOCK = sizeof(Bit_block),
62 : };
63 :
64 : /** @internal Various constants to support bit block size bit ops. */
65 : enum : Bit_block {
66 : /** @internal A mask of a bit block with all bits on. */
67 : BLOCK_ON = (Bit_block)~0,
68 : /** @internal The Most Significant Bit of a bit block turned on to 1. */
69 : BLOCK_MSB = (Bit_block)1 << ((SIZEOF_BLOCK * CHAR_BIT) - 1),
70 : };
71 :
72 : /** @internal An index into the block array or count of bit blocks. The block
73 : array is constructed by the number of blocks required to support the current bit
74 : set capacity. Assume this index type has range [0, block count to support N
75 : bits].
76 :
77 : User input is given as a `size_t` so distinguish from that input with this type
78 : to make it clear to the reader the index refers to a block not the given bit
79 : index the user has provided. */
80 : typedef size_t Block_count;
81 :
82 : /** @internal An index within a block. A block is set to some number of bits
83 : as determined by the type used for each block. This type is intended to count
84 : bits in a block and therefore cannot count up to arbitrary indices. Assume its
85 : range is `[0, BIT_BLOCK_BITS]`, for ease of use and clarity.
86 :
87 : There are many types of indexing and counting that take place in a bit set so
88 : use this type specifically for counting bits in a block so the reader is clear
89 : on intent. */
90 : typedef uint8_t Bit_count;
91 :
92 : enum : Bit_count {
93 : /** @internal How many total bits that fit in a bit block. */
94 : BLOCK_BITS = SIZEOF_BLOCK * CHAR_BIT,
95 : /** @internal Used for static assert clarity. */
96 : U8_BLOCK_MAX = UINT8_MAX,
97 : /** @internal log2 of block bits to avoid division. */
98 : BLOCK_BITS_LOG2 = CCC_log2((Bit_count)BLOCK_BITS),
99 : };
100 : static_assert(
101 : (BLOCK_BITS & (BLOCK_BITS - 1)) == 0,
102 : "the number of bits in a block is always a power of two, "
103 : "helping avoid division and modulo operations when possible"
104 : );
105 : static_assert(
106 : BLOCK_BITS >> BLOCK_BITS_LOG2 == 1,
107 : "hand coded log2 of bitblock bits is always correct"
108 : );
109 : static_assert(
110 : (Bit_count) ~((Bit_count)0) >= (Bit_count)0, "Bit_count must be unsigned"
111 : );
112 : static_assert(UINT8_MAX >= BLOCK_BITS, "Bit_count counts all block bits.");
113 :
114 : /*========================= Prototypes ============================*/
115 :
116 : static size_t block_count_index(size_t);
117 : static Bit_block *block_at(struct CCC_Flat_bitset const *, size_t);
118 : static void set(Bit_block *, size_t, CCC_Tribool);
119 : static Bit_block on(size_t);
120 : static void fix_end(struct CCC_Flat_bitset *);
121 : static CCC_Tribool status(Bit_block const *, size_t);
122 : static size_t block_count(size_t);
123 : static inline CCC_Tribool
124 : checked_block_count(Block_count *result, size_t bit_count);
125 : static CCC_Tribool
126 : any_or_none_range(struct CCC_Flat_bitset const *, size_t, size_t, CCC_Tribool);
127 : static CCC_Tribool all_range(struct CCC_Flat_bitset const *, size_t, size_t);
128 : static CCC_Count first_trailing_bit_range(
129 : struct CCC_Flat_bitset const *, size_t, size_t, CCC_Tribool
130 : );
131 : static CCC_Count first_leading_bit_range(
132 : struct CCC_Flat_bitset const *, size_t, size_t, CCC_Tribool
133 : );
134 : static CCC_Count first_trailing_bits_range(
135 : struct CCC_Flat_bitset const *, size_t, size_t, size_t, CCC_Tribool
136 : );
137 : static CCC_Count first_leading_bits_range(
138 : struct CCC_Flat_bitset const *, size_t, size_t, size_t, CCC_Tribool
139 : );
140 : static CCC_Result
141 : maybe_resize(struct CCC_Flat_bitset *, size_t, CCC_Allocator const *);
142 : static CCC_Tribool is_mask_match(Bit_block, Bit_block);
143 : static Bit_block trailing_ones_mask(Bit_count);
144 : static Bit_block leading_ones_mask(Bit_count);
145 : static void set_all(struct CCC_Flat_bitset *, CCC_Tribool);
146 : static Bit_count bit_count_index(size_t);
147 : static CCC_Tribool
148 : is_subset_of(struct CCC_Flat_bitset const *, struct CCC_Flat_bitset const *);
149 : static Bit_count popcount(Bit_block);
150 : static Bit_count count_trailing_zeros(Bit_block);
151 : static Bit_count count_leading_zeros(Bit_block);
152 :
153 : /*======================= Public Interface ==============================*/
154 :
155 : CCC_Tribool
156 4 : CCC_flat_bitset_is_proper_subset(
157 : CCC_Flat_bitset const *const subset, CCC_Flat_bitset const *const set
158 : ) {
159 4 : if (!set || !subset) {
160 2 : return CCC_TRIBOOL_ERROR;
161 : }
162 2 : if (set->count <= subset->count) {
163 1 : return CCC_FALSE;
164 : }
165 1 : return is_subset_of(subset, set);
166 4 : }
167 :
168 : CCC_Tribool
169 11 : CCC_flat_bitset_is_subset(
170 : CCC_Flat_bitset const *const subset, CCC_Flat_bitset const *const set
171 : ) {
172 11 : if (!set || !subset) {
173 2 : return CCC_TRIBOOL_ERROR;
174 : }
175 9 : if (set->count < subset->count) {
176 1 : return CCC_FALSE;
177 : }
178 8 : return is_subset_of(subset, set);
179 11 : }
180 :
181 : CCC_Result
182 8 : CCC_flat_bitset_or(
183 : CCC_Flat_bitset *const destination, CCC_Flat_bitset const *const source
184 : ) {
185 8 : if (!destination || !source) {
186 2 : return CCC_RESULT_ARGUMENT_ERROR;
187 : }
188 6 : if (!destination->count || !source->count) {
189 4 : return CCC_RESULT_OK;
190 : }
191 4 : Block_count const end_block
192 2 : = block_count(CCC_min(destination->count, source->count));
193 26 : for (size_t b = 0; b < end_block; ++b) {
194 24 : destination->blocks[b] |= source->blocks[b];
195 24 : }
196 2 : fix_end(destination);
197 2 : return CCC_RESULT_OK;
198 8 : }
199 :
200 : CCC_Result
201 6 : CCC_flat_bitset_xor(
202 : CCC_Flat_bitset *const destination, CCC_Flat_bitset const *const source
203 : ) {
204 6 : if (!destination || !source) {
205 2 : return CCC_RESULT_ARGUMENT_ERROR;
206 : }
207 4 : if (!destination->count || !source->count) {
208 2 : return CCC_RESULT_OK;
209 : }
210 4 : Block_count const end_block
211 2 : = block_count(CCC_min(destination->count, source->count));
212 26 : for (Block_count b = 0; b < end_block; ++b) {
213 24 : destination->blocks[b] ^= source->blocks[b];
214 24 : }
215 2 : fix_end(destination);
216 2 : return CCC_RESULT_OK;
217 6 : }
218 :
219 : CCC_Result
220 6 : CCC_flat_bitset_and(
221 : CCC_Flat_bitset *destination, CCC_Flat_bitset const *source
222 : ) {
223 6 : if (!destination || !source) {
224 2 : return CCC_RESULT_ARGUMENT_ERROR;
225 : }
226 4 : if (!source->count) {
227 1 : set_all(destination, CCC_FALSE);
228 1 : return CCC_RESULT_OK;
229 : }
230 3 : if (!destination->count) {
231 1 : return CCC_RESULT_OK;
232 : }
233 4 : Block_count const end_block
234 2 : = block_count(CCC_min(destination->count, source->count));
235 26 : for (Block_count b = 0; b < end_block; ++b) {
236 24 : destination->blocks[b] &= source->blocks[b];
237 24 : }
238 2 : if (destination->count <= source->count) {
239 1 : return CCC_RESULT_OK;
240 : }
241 : /* The source widens to align with destination as integers would; same
242 : consequences. */
243 1 : Block_count const destination_blocks = block_count(destination->count);
244 1 : Block_count const remain = destination_blocks - end_block;
245 2 : (void)memset(
246 2 : destination->blocks + end_block, CCC_FALSE, remain * SIZEOF_BLOCK
247 : );
248 1 : fix_end(destination);
249 1 : return CCC_RESULT_OK;
250 6 : }
251 :
252 : CCC_Result
253 9 : CCC_flat_bitset_shift_left(
254 : CCC_Flat_bitset *const bitset, size_t const left_shifts
255 : ) {
256 9 : if (!bitset) {
257 1 : return CCC_RESULT_ARGUMENT_ERROR;
258 : }
259 8 : if (!bitset->count || !left_shifts) {
260 1 : return CCC_RESULT_OK;
261 : }
262 7 : if (left_shifts >= bitset->count) {
263 1 : set_all(bitset, CCC_FALSE);
264 1 : return CCC_RESULT_OK;
265 : }
266 6 : Block_count const end = block_count_index(bitset->count - 1);
267 6 : Block_count const blocks = block_count_index(left_shifts);
268 6 : Bit_count const split = bit_count_index(left_shifts);
269 6 : if (!split) {
270 31 : for (Block_count shift = end - blocks + 1, write = end; shift--;
271 29 : --write) {
272 29 : bitset->blocks[write] = bitset->blocks[shift];
273 29 : }
274 2 : } else {
275 4 : Bit_count const remain = BLOCK_BITS - split;
276 32 : for (Block_count shift = end - blocks, write = end; shift > 0;
277 28 : --shift, --write) {
278 56 : bitset->blocks[write] = (bitset->blocks[shift] << split)
279 28 : | (bitset->blocks[shift - 1] >> remain);
280 28 : }
281 4 : bitset->blocks[blocks] = bitset->blocks[0] << split;
282 4 : }
283 : /* Zero fills in lower bits just as an integer shift would. */
284 26 : for (Block_count i = 0; i < blocks; ++i) {
285 20 : bitset->blocks[i] = 0;
286 20 : }
287 6 : fix_end(bitset);
288 6 : return CCC_RESULT_OK;
289 9 : }
290 :
291 : CCC_Result
292 9 : CCC_flat_bitset_shift_right(
293 : CCC_Flat_bitset *const bitset, size_t const right_shifts
294 : ) {
295 9 : if (!bitset) {
296 1 : return CCC_RESULT_ARGUMENT_ERROR;
297 : }
298 8 : if (!bitset->count || !right_shifts) {
299 1 : return CCC_RESULT_OK;
300 : }
301 7 : if (right_shifts >= bitset->count) {
302 1 : set_all(bitset, CCC_FALSE);
303 1 : return CCC_RESULT_OK;
304 : }
305 6 : Block_count const end = block_count_index(bitset->count - 1);
306 6 : Block_count const blocks = block_count_index(right_shifts);
307 6 : Bit_count const split = bit_count_index(right_shifts);
308 6 : if (!split) {
309 31 : for (Block_count shift = blocks, write = 0; shift < end + 1;
310 29 : ++shift, ++write) {
311 29 : bitset->blocks[write] = bitset->blocks[shift];
312 29 : }
313 2 : } else {
314 4 : Bit_count const remain = BLOCK_BITS - split;
315 32 : for (Block_count shift = blocks, write = 0; shift < end;
316 28 : ++shift, ++write) {
317 56 : bitset->blocks[write] = (bitset->blocks[shift + 1] << remain)
318 28 : | (bitset->blocks[shift] >> split);
319 28 : }
320 4 : bitset->blocks[end - blocks] = bitset->blocks[end] >> split;
321 4 : }
322 : /* This is safe for a few reasons:
323 : - If shifts equals count we set all to 0 and returned early.
324 : - If we only have one block i will be equal to end and we are done.
325 : - If end is the 0th block we will stop after 1. A meaningful shift
326 : occurred in the 0th block so zeroing would be a mistake.
327 : - All other cases ensure it is safe to decrease i (no underflow).
328 : This operation emulates the zeroing of high bits on a right shift and
329 : a bit set is considered unsigned so we don't sign bit fill. */
330 26 : for (Block_count i = end; i > end - blocks; --i) {
331 20 : bitset->blocks[i] = 0;
332 20 : }
333 6 : fix_end(bitset);
334 6 : return CCC_RESULT_OK;
335 9 : }
336 :
337 : CCC_Tribool
338 4144 : CCC_flat_bitset_test(CCC_Flat_bitset const *const bitset, size_t const i) {
339 4144 : if (!bitset) {
340 1 : return CCC_TRIBOOL_ERROR;
341 : }
342 4143 : if (i >= bitset->count) {
343 7 : return CCC_TRIBOOL_ERROR;
344 : }
345 4136 : return status(block_at(bitset, i), i);
346 4144 : }
347 :
348 : CCC_Tribool
349 13721 : CCC_flat_bitset_set(
350 : CCC_Flat_bitset *const bitset, size_t const i, CCC_Tribool const b
351 : ) {
352 13721 : if (!bitset) {
353 1 : return CCC_TRIBOOL_ERROR;
354 : }
355 13720 : if (i >= bitset->count) {
356 2 : return CCC_TRIBOOL_ERROR;
357 : }
358 13718 : Bit_block *const block = block_at(bitset, i);
359 13718 : CCC_Tribool const was = status(block, i);
360 13718 : set(block, i, b);
361 13718 : return was;
362 13721 : }
363 :
364 : CCC_Result
365 34 : CCC_flat_bitset_set_all(CCC_Flat_bitset *const bitset, CCC_Tribool const b) {
366 34 : if (!bitset) {
367 1 : return CCC_RESULT_ARGUMENT_ERROR;
368 : }
369 33 : if (bitset->count) {
370 33 : set_all(bitset, b);
371 33 : }
372 33 : return CCC_RESULT_OK;
373 34 : }
374 :
375 : /** A naive implementation might just call set for every index between the
376 : start and start + count. However, calculating the block and index within each
377 : block for every call to set costs a division and a modulo operation. This also
378 : loads and stores a block multiple times just to set each bit within a block to
379 : the same value. We can avoid this by handling the first and last block with one
380 : operations and then handling everything in between with a bulk memset. */
381 : CCC_Result
382 10452 : CCC_flat_bitset_set_range(
383 : CCC_Flat_bitset *const bitset,
384 : size_t const range_start_index,
385 : size_t const range_bit_count,
386 : CCC_Tribool const b
387 : ) {
388 10452 : size_t range_end = 0;
389 10452 : if (ckd_add(&range_end, range_start_index, range_bit_count) || !bitset
390 10452 : || !range_bit_count || range_start_index >= bitset->count
391 10452 : || range_end > bitset->count) {
392 1 : return CCC_RESULT_ARGUMENT_ERROR;
393 : }
394 10451 : Block_count start_block = block_count_index(range_start_index);
395 10451 : Bit_count const start_bit = bit_count_index(range_start_index);
396 10451 : Bit_block range_mask = leading_ones_mask(BLOCK_BITS - start_bit);
397 10451 : if (start_bit + range_bit_count < BLOCK_BITS) {
398 : range_mask
399 1687 : &= trailing_ones_mask((Bit_count)(start_bit + range_bit_count));
400 1687 : }
401 :
402 : /* Logic is uniform except for key lines to turn bits on or off. */
403 10451 : b ? (bitset->blocks[start_block] |= range_mask)
404 4201 : : (bitset->blocks[start_block] &= ~range_mask);
405 :
406 10451 : Block_count const end_block = block_count_index(range_end - 1);
407 10451 : if (end_block == start_block) {
408 1972 : fix_end(bitset);
409 1972 : return CCC_RESULT_OK;
410 : }
411 8479 : if (++start_block != end_block) {
412 5766 : int const v = b ? ~0 : 0;
413 11532 : (void)memset(
414 5766 : &bitset->blocks[start_block],
415 5766 : v,
416 5766 : (end_block - start_block) * SIZEOF_BLOCK
417 : );
418 5766 : }
419 : /* Need the final included bit position modulo block size but then feed to
420 : mask creation function as a count. */
421 16958 : Bit_block const last_block_mask
422 8479 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
423 :
424 8479 : b ? (bitset->blocks[end_block] |= last_block_mask)
425 3248 : : (bitset->blocks[end_block] &= ~last_block_mask);
426 :
427 8479 : fix_end(bitset);
428 8479 : return CCC_RESULT_OK;
429 10452 : }
430 :
431 : CCC_Tribool
432 4 : CCC_flat_bitset_reset(CCC_Flat_bitset *const bitset, size_t const i) {
433 4 : if (!bitset) {
434 1 : return CCC_TRIBOOL_ERROR;
435 : }
436 3 : if (i >= bitset->count) {
437 1 : return CCC_TRIBOOL_ERROR;
438 : }
439 2 : Bit_block *const block = block_at(bitset, i);
440 2 : CCC_Tribool const was = status(block, i);
441 2 : *block &= ~on(i);
442 2 : fix_end(bitset);
443 2 : return was;
444 4 : }
445 :
446 : CCC_Result
447 11 : CCC_flat_bitset_reset_all(CCC_Flat_bitset *const bitset) {
448 11 : if (!bitset) {
449 1 : return CCC_RESULT_ARGUMENT_ERROR;
450 : }
451 10 : if (bitset->count) {
452 10 : (void)memset(
453 10 : bitset->blocks, CCC_FALSE, block_count(bitset->count) * SIZEOF_BLOCK
454 : );
455 10 : }
456 10 : return CCC_RESULT_OK;
457 11 : }
458 :
459 : /** Same concept as set range but easier. Handle first and last then set
460 : everything in between to false with memset. */
461 : CCC_Result
462 2050 : CCC_flat_bitset_reset_range(
463 : CCC_Flat_bitset *const bitset,
464 : size_t const range_start_index,
465 : size_t const range_bit_count
466 : ) {
467 2050 : size_t range_end = 0;
468 2050 : if (ckd_add(&range_end, range_start_index, range_bit_count) || !bitset
469 2050 : || !range_bit_count || range_start_index >= bitset->count
470 2049 : || range_end > bitset->count) {
471 1 : return CCC_RESULT_ARGUMENT_ERROR;
472 : }
473 2049 : Block_count start_block = block_count_index(range_start_index);
474 2049 : Bit_count const start_bit = bit_count_index(range_start_index);
475 2049 : Bit_block first_block_mask = leading_ones_mask(BLOCK_BITS - start_bit);
476 2049 : if (start_bit + range_bit_count < BLOCK_BITS) {
477 : first_block_mask
478 33 : &= trailing_ones_mask((Bit_count)(start_bit + range_bit_count));
479 33 : }
480 2049 : bitset->blocks[start_block] &= ~first_block_mask;
481 2049 : Block_count const end_block = block_count_index(range_end - 1);
482 2049 : if (end_block == start_block) {
483 66 : fix_end(bitset);
484 66 : return CCC_RESULT_OK;
485 : }
486 1983 : if (++start_block != end_block) {
487 1792 : (void)memset(
488 1792 : &bitset->blocks[start_block],
489 : CCC_FALSE,
490 1792 : (end_block - start_block) * SIZEOF_BLOCK
491 : );
492 1792 : }
493 3966 : Bit_block const last_block_mask
494 1983 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
495 1983 : bitset->blocks[end_block] &= ~last_block_mask;
496 1983 : fix_end(bitset);
497 1983 : return CCC_RESULT_OK;
498 2050 : }
499 :
500 : CCC_Tribool
501 4 : CCC_flat_bitset_flip(CCC_Flat_bitset *const bitset, size_t const i) {
502 4 : if (!bitset || i > bitset->count) {
503 2 : return CCC_TRIBOOL_ERROR;
504 : }
505 2 : Block_count const b_i = block_count_index(i);
506 2 : Bit_block *const block = &bitset->blocks[b_i];
507 2 : CCC_Tribool const was = status(block, i);
508 2 : *block ^= on(i);
509 2 : fix_end(bitset);
510 2 : return was;
511 4 : }
512 :
513 : CCC_Result
514 3 : CCC_flat_bitset_flip_all(CCC_Flat_bitset *const bitset) {
515 3 : if (!bitset) {
516 1 : return CCC_RESULT_ARGUMENT_ERROR;
517 : }
518 2 : if (!bitset->count) {
519 1 : return CCC_RESULT_OK;
520 : }
521 1 : Block_count const end = block_count(bitset->count);
522 2 : for (size_t i = 0; i < end; ++i) {
523 1 : bitset->blocks[i] = ~bitset->blocks[i];
524 1 : }
525 1 : fix_end(bitset);
526 1 : return CCC_RESULT_OK;
527 3 : }
528 :
529 : /** Maybe future SIMD vectorization could speed things up here because we use
530 : the same strat of handling first and last which just leaves a simpler bulk
531 : operation in the middle. But we don't benefit from memset here. */
532 : CCC_Result
533 2563 : CCC_flat_bitset_flip_range(
534 : CCC_Flat_bitset *const bitset,
535 : size_t const range_start_index,
536 : size_t const range_bit_count
537 : ) {
538 2563 : size_t range_end = 0;
539 2563 : if (ckd_add(&range_end, range_start_index, range_bit_count) || !bitset
540 2563 : || !range_bit_count || range_start_index >= bitset->count
541 2562 : || range_end > bitset->count) {
542 3 : return CCC_RESULT_ARGUMENT_ERROR;
543 : }
544 2560 : Block_count start_block = block_count_index(range_start_index);
545 2560 : Bit_count const start_bit = bit_count_index(range_start_index);
546 2560 : Bit_block first_block_on = leading_ones_mask(BLOCK_BITS - start_bit);
547 2560 : if (start_bit + range_bit_count < BLOCK_BITS) {
548 : first_block_on
549 62 : &= trailing_ones_mask((Bit_count)(start_bit + range_bit_count));
550 62 : }
551 2560 : bitset->blocks[start_block] ^= first_block_on;
552 2560 : Block_count const end_block = block_count_index(range_end - 1);
553 2560 : if (end_block == start_block) {
554 128 : fix_end(bitset);
555 128 : return CCC_RESULT_OK;
556 : }
557 19456 : while (++start_block < end_block) {
558 17024 : bitset->blocks[start_block] = ~bitset->blocks[start_block];
559 : }
560 4864 : Bit_block const last_block_mask
561 2432 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
562 2432 : bitset->blocks[end_block] ^= last_block_mask;
563 2432 : fix_end(bitset);
564 2432 : return CCC_RESULT_OK;
565 2563 : }
566 :
567 : CCC_Count
568 76 : CCC_flat_bitset_capacity(CCC_Flat_bitset const *const bitset) {
569 76 : if (!bitset) {
570 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
571 : }
572 75 : return (CCC_Count){.count = bitset->capacity};
573 76 : }
574 :
575 : CCC_Count
576 2 : CCC_flat_bitset_blocks_capacity(CCC_Flat_bitset const *const bitset) {
577 2 : if (!bitset) {
578 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
579 : }
580 2 : return (CCC_Count){
581 1 : .count = block_count(bitset->capacity),
582 : };
583 2 : }
584 :
585 : CCC_Count
586 1679 : CCC_flat_bitset_count(CCC_Flat_bitset const *const bitset) {
587 1679 : if (!bitset) {
588 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
589 : }
590 1678 : return (CCC_Count){.count = bitset->count};
591 1679 : }
592 :
593 : CCC_Count
594 2 : CCC_flat_bitset_blocks_count(CCC_Flat_bitset const *const bitset) {
595 2 : if (!bitset) {
596 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
597 : }
598 2 : return (CCC_Count){
599 1 : .count = block_count(bitset->count),
600 : };
601 2 : }
602 :
603 : CCC_Tribool
604 2304 : CCC_flat_bitset_is_empty(CCC_Flat_bitset const *const bitset) {
605 2304 : if (!bitset) {
606 1 : return CCC_TRIBOOL_ERROR;
607 : }
608 2303 : return !bitset->count;
609 2304 : }
610 :
611 : CCC_Count
612 9297 : CCC_flat_bitset_popcount(CCC_Flat_bitset const *const bitset) {
613 9297 : if (!bitset) {
614 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
615 : }
616 9296 : if (!bitset->count) {
617 9 : return (CCC_Count){.count = 0};
618 : }
619 9287 : Block_count const end = block_count(bitset->count);
620 9287 : size_t count = 0;
621 157390 : for (Block_count i = 0; i < end; ++i) {
622 148103 : count += popcount(bitset->blocks[i]);
623 148103 : }
624 9287 : return (CCC_Count){.count = count};
625 9297 : }
626 :
627 : CCC_Count
628 9220 : CCC_flat_bitset_popcount_range(
629 : CCC_Flat_bitset const *const bitset,
630 : size_t const range_start_index,
631 : size_t const range_bit_count
632 : ) {
633 9220 : size_t range_end = 0;
634 9220 : if (ckd_add(&range_end, range_start_index, range_bit_count) || !bitset
635 9220 : || !range_bit_count || range_start_index >= bitset->count
636 9218 : || range_end > bitset->count) {
637 2 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
638 : }
639 9218 : size_t popped = 0;
640 9218 : Block_count start_block = block_count_index(range_start_index);
641 9218 : Bit_count const start_bit = bit_count_index(range_start_index);
642 9218 : Bit_block first_block_mask = leading_ones_mask(BLOCK_BITS - start_bit);
643 9218 : if (start_bit + range_bit_count < BLOCK_BITS) {
644 : first_block_mask
645 188 : &= trailing_ones_mask((Bit_count)(start_bit + range_bit_count));
646 188 : }
647 9218 : popped += popcount(first_block_mask & bitset->blocks[start_block]);
648 9218 : Block_count const end_block = block_count_index(range_end - 1);
649 9218 : if (end_block == start_block) {
650 388 : return (CCC_Count){.count = popped};
651 : }
652 70640 : while (++start_block < end_block) {
653 61810 : popped += popcount(bitset->blocks[start_block]);
654 : }
655 17660 : Bit_block const last_block_mask
656 8830 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
657 8830 : popped += popcount(last_block_mask & bitset->blocks[end_block]);
658 8830 : return (CCC_Count){.count = popped};
659 9220 : }
660 :
661 : CCC_Result
662 1700 : CCC_flat_bitset_push_back(
663 : CCC_Flat_bitset *const bitset,
664 : CCC_Tribool const b,
665 : CCC_Allocator const *const allocator
666 : ) {
667 1700 : if (!bitset || !allocator || b > CCC_TRUE || b < CCC_FALSE) {
668 3 : return CCC_RESULT_ARGUMENT_ERROR;
669 : }
670 1697 : CCC_Result const check_resize = maybe_resize(bitset, 1, allocator);
671 1697 : if (check_resize != CCC_RESULT_OK) {
672 3 : return check_resize;
673 : }
674 1694 : ++bitset->count;
675 1694 : set(block_at(bitset, bitset->count - 1), bitset->count - 1, b);
676 1694 : fix_end(bitset);
677 1694 : return CCC_RESULT_OK;
678 1700 : }
679 :
680 : CCC_Tribool
681 2279 : CCC_flat_bitset_pop_back(CCC_Flat_bitset *const bitset) {
682 2279 : if (!bitset || !bitset->count) {
683 1 : return CCC_TRIBOOL_ERROR;
684 : }
685 4556 : CCC_Tribool const was
686 2278 : = status(block_at(bitset, bitset->count - 1), bitset->count - 1);
687 2278 : --bitset->count;
688 2278 : fix_end(bitset);
689 2278 : return was;
690 2279 : }
691 :
692 : CCC_Tribool
693 1035 : CCC_flat_bitset_any_range(
694 : CCC_Flat_bitset const *const bitset,
695 : size_t const range_start_index,
696 : size_t const range_bit_count
697 : ) {
698 1035 : return any_or_none_range(
699 1035 : bitset, range_start_index, range_bit_count, CCC_TRUE
700 : );
701 : }
702 :
703 : CCC_Tribool
704 512 : CCC_flat_bitset_any(CCC_Flat_bitset const *const bitset) {
705 512 : return any_or_none_range(bitset, 0, bitset->count, CCC_TRUE);
706 : }
707 :
708 : CCC_Tribool
709 512 : CCC_flat_bitset_none_range(
710 : CCC_Flat_bitset const *const bitset,
711 : size_t const range_start_index,
712 : size_t const range_bit_count
713 : ) {
714 512 : return any_or_none_range(
715 512 : bitset, range_start_index, range_bit_count, CCC_FALSE
716 : );
717 : }
718 :
719 : CCC_Tribool
720 512 : CCC_flat_bitset_none(CCC_Flat_bitset const *const bitset) {
721 512 : return any_or_none_range(bitset, 0, bitset->count, CCC_FALSE);
722 : }
723 :
724 : CCC_Tribool
725 524 : CCC_flat_bitset_all_range(
726 : CCC_Flat_bitset const *const bitset,
727 : size_t const range_start_index,
728 : size_t const range_bit_count
729 : ) {
730 524 : return all_range(bitset, range_start_index, range_bit_count);
731 : }
732 :
733 : CCC_Tribool
734 513 : CCC_flat_bitset_all(CCC_Flat_bitset const *const bitset) {
735 513 : return all_range(bitset, 0, bitset->count);
736 : }
737 :
738 : CCC_Count
739 1029 : CCC_flat_bitset_first_trailing_one_range(
740 : CCC_Flat_bitset const *const bitset,
741 : size_t const range_start_index,
742 : size_t const range_bit_count
743 : ) {
744 1029 : return first_trailing_bit_range(
745 1029 : bitset, range_start_index, range_bit_count, CCC_TRUE
746 : );
747 1029 : }
748 :
749 : CCC_Count
750 511 : CCC_flat_bitset_first_trailing_one(CCC_Flat_bitset const *const bitset) {
751 511 : return first_trailing_bit_range(bitset, 0, bitset->count, CCC_TRUE);
752 511 : }
753 :
754 : CCC_Count
755 4289 : CCC_flat_bitset_first_trailing_ones(
756 : CCC_Flat_bitset const *const bitset, size_t const ones_count
757 : ) {
758 4289 : return first_trailing_bits_range(
759 4289 : bitset, 0, bitset->count, ones_count, CCC_TRUE
760 : );
761 4289 : }
762 :
763 : CCC_Count
764 4325 : CCC_flat_bitset_first_trailing_ones_range(
765 : CCC_Flat_bitset const *const bitset,
766 : size_t const range_start_index,
767 : size_t const range_bit_count,
768 : size_t const ones_count
769 : ) {
770 4325 : return first_trailing_bits_range(
771 4325 : bitset, range_start_index, range_bit_count, ones_count, CCC_TRUE
772 : );
773 4325 : }
774 :
775 : CCC_Count
776 1022 : CCC_flat_bitset_first_trailing_zero_range(
777 : CCC_Flat_bitset const *const bitset,
778 : size_t const range_start_index,
779 : size_t const range_bit_count
780 : ) {
781 1022 : return first_trailing_bit_range(
782 1022 : bitset, range_start_index, range_bit_count, CCC_FALSE
783 : );
784 1022 : }
785 :
786 : CCC_Count
787 511 : CCC_flat_bitset_first_trailing_zero(CCC_Flat_bitset const *const bitset) {
788 511 : return first_trailing_bit_range(bitset, 0, bitset->count, CCC_FALSE);
789 511 : }
790 :
791 : CCC_Count
792 4289 : CCC_flat_bitset_first_trailing_zeros(
793 : CCC_Flat_bitset const *const bitset, size_t const zeros_count
794 : ) {
795 4289 : return first_trailing_bits_range(
796 4289 : bitset, 0, bitset->count, zeros_count, CCC_FALSE
797 : );
798 4289 : }
799 :
800 : CCC_Count
801 4322 : CCC_flat_bitset_first_trailing_zeros_range(
802 : CCC_Flat_bitset const *const bitset,
803 : size_t const range_start_index,
804 : size_t const range_bit_count,
805 : size_t const zeros_count
806 : ) {
807 4322 : return first_trailing_bits_range(
808 4322 : bitset, range_start_index, range_bit_count, zeros_count, CCC_FALSE
809 : );
810 4322 : }
811 :
812 : CCC_Count
813 1035 : CCC_flat_bitset_first_leading_one_range(
814 : CCC_Flat_bitset const *const bitset,
815 : size_t const range_start_index,
816 : size_t const range_bit_count
817 : ) {
818 1035 : return first_leading_bit_range(
819 1035 : bitset, range_start_index, range_bit_count, CCC_TRUE
820 : );
821 1035 : }
822 :
823 : CCC_Count
824 512 : CCC_flat_bitset_first_leading_one(CCC_Flat_bitset const *const bitset) {
825 512 : return first_leading_bit_range(bitset, 0, bitset->count, CCC_TRUE);
826 512 : }
827 :
828 : CCC_Count
829 4280 : CCC_flat_bitset_first_leading_ones(
830 : CCC_Flat_bitset const *const bitset, size_t const ones_count
831 : ) {
832 4280 : return first_leading_bits_range(
833 4280 : bitset, 0, bitset->count, ones_count, CCC_TRUE
834 : );
835 4280 : }
836 :
837 : CCC_Count
838 4316 : CCC_flat_bitset_first_leading_ones_range(
839 : CCC_Flat_bitset const *const bitset,
840 : size_t const range_start_index,
841 : size_t const range_bit_count,
842 : size_t const ones_count
843 : ) {
844 4316 : return first_leading_bits_range(
845 4316 : bitset, range_start_index, range_bit_count, ones_count, CCC_TRUE
846 : );
847 4316 : }
848 :
849 : CCC_Count
850 1029 : CCC_flat_bitset_first_leading_zero_range(
851 : CCC_Flat_bitset const *const bitset,
852 : size_t const range_start_index,
853 : size_t const range_bit_count
854 : ) {
855 1029 : return first_leading_bit_range(
856 1029 : bitset, range_start_index, range_bit_count, CCC_FALSE
857 : );
858 1029 : }
859 :
860 : CCC_Count
861 512 : CCC_flat_bitset_first_leading_zero(CCC_Flat_bitset const *const bitset) {
862 512 : return first_leading_bit_range(bitset, 0, bitset->count, CCC_FALSE);
863 512 : }
864 :
865 : CCC_Count
866 4280 : CCC_flat_bitset_first_leading_zeros(
867 : CCC_Flat_bitset const *const bitset, size_t const zeros_count
868 : ) {
869 4280 : return first_leading_bits_range(
870 4280 : bitset, 0, bitset->count, zeros_count, CCC_FALSE
871 : );
872 4280 : }
873 :
874 : CCC_Count
875 4313 : CCC_flat_bitset_first_leading_zeros_range(
876 : CCC_Flat_bitset const *const bitset,
877 : size_t const range_start_index,
878 : size_t const range_bit_count,
879 : size_t const zeros_count
880 : ) {
881 4313 : return first_leading_bits_range(
882 4313 : bitset, range_start_index, range_bit_count, zeros_count, CCC_FALSE
883 : );
884 4313 : }
885 :
886 : CCC_Result
887 6 : CCC_flat_bitset_clear(CCC_Flat_bitset *const bitset) {
888 6 : if (!bitset) {
889 1 : return CCC_RESULT_ARGUMENT_ERROR;
890 : }
891 5 : if (bitset->blocks) {
892 5 : assert(bitset->capacity);
893 5 : (void)memset(
894 5 : bitset->blocks,
895 : CCC_FALSE,
896 5 : block_count(bitset->capacity) * SIZEOF_BLOCK
897 : );
898 5 : }
899 5 : bitset->count = 0;
900 5 : return CCC_RESULT_OK;
901 6 : }
902 :
903 : CCC_Result
904 11 : CCC_flat_bitset_clear_and_free(
905 : CCC_Flat_bitset *const bitset, CCC_Allocator const *const allocator
906 : ) {
907 11 : if (!bitset || !allocator) {
908 2 : return CCC_RESULT_ARGUMENT_ERROR;
909 : }
910 9 : if (!allocator->allocate) {
911 5 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
912 : }
913 4 : if (bitset->blocks) {
914 9 : (void)allocator->allocate((CCC_Allocator_arguments){
915 3 : .input = bitset->blocks,
916 : .bytes = 0,
917 : .alignment = alignof(*bitset->blocks),
918 3 : .context = allocator->context,
919 : });
920 3 : }
921 4 : bitset->count = 0;
922 4 : bitset->capacity = 0;
923 4 : bitset->blocks = NULL;
924 4 : return CCC_RESULT_OK;
925 11 : }
926 :
927 : CCC_Result
928 49 : CCC_flat_bitset_reserve(
929 : CCC_Flat_bitset *const bitset,
930 : size_t const to_add,
931 : CCC_Allocator const *const allocator
932 : ) {
933 49 : if (!bitset || !allocator || !allocator->allocate || !to_add) {
934 3 : return CCC_RESULT_ARGUMENT_ERROR;
935 : }
936 46 : return maybe_resize(bitset, to_add, allocator);
937 49 : }
938 :
939 : CCC_Result
940 8 : CCC_flat_bitset_copy(
941 : CCC_Flat_bitset *const destination,
942 : CCC_Flat_bitset const *const source,
943 : CCC_Allocator const *const allocator
944 : ) {
945 8 : if (!destination || !source || !allocator
946 6 : || (destination->capacity < source->capacity && !allocator->allocate)) {
947 3 : return CCC_RESULT_ARGUMENT_ERROR;
948 : }
949 5 : if (!source->capacity) {
950 1 : destination->count = 0;
951 1 : return CCC_RESULT_OK;
952 : }
953 4 : if (destination->capacity < source->capacity) {
954 6 : Bit_block *const new_data
955 12 : = allocator->allocate((CCC_Allocator_arguments){
956 3 : .input = destination->blocks,
957 3 : .bytes = block_count(source->capacity) * SIZEOF_BLOCK,
958 : .alignment = alignof((*destination->blocks)),
959 3 : .context = allocator->context,
960 : });
961 3 : if (!new_data) {
962 1 : return CCC_RESULT_ALLOCATOR_ERROR;
963 : }
964 2 : destination->blocks = new_data;
965 2 : destination->capacity = source->capacity;
966 3 : }
967 3 : if (!source->blocks || !destination->blocks) {
968 1 : return CCC_RESULT_ARGUMENT_ERROR;
969 : }
970 2 : destination->count = source->count;
971 2 : (void)memcpy(
972 2 : destination->blocks,
973 2 : source->blocks,
974 2 : block_count(source->capacity) * SIZEOF_BLOCK
975 : );
976 2 : fix_end(destination);
977 2 : return CCC_RESULT_OK;
978 8 : }
979 :
980 : void *
981 2 : CCC_flat_bitset_data(CCC_Flat_bitset const *const bitset) {
982 2 : if (!bitset) {
983 1 : return NULL;
984 : }
985 1 : return bitset->blocks;
986 2 : }
987 :
988 : CCC_Tribool
989 7 : CCC_flat_bitset_is_equal(
990 : CCC_Flat_bitset const *const left, CCC_Flat_bitset const *const right
991 : ) {
992 7 : if (!left || !right) {
993 2 : return CCC_TRIBOOL_ERROR;
994 : }
995 5 : if (left->count != right->count) {
996 1 : return CCC_FALSE;
997 : }
998 4 : if (!left->count) {
999 1 : return CCC_TRUE;
1000 : }
1001 6 : return memcmp(
1002 3 : left->blocks,
1003 3 : right->blocks,
1004 3 : block_count(left->count) * SIZEOF_BLOCK
1005 : )
1006 3 : == 0;
1007 7 : }
1008 :
1009 : /*========================= Private Interface =========================*/
1010 :
1011 : CCC_Result
1012 46 : CCC_private_flat_bitset_reserve(
1013 : struct CCC_Flat_bitset *const bitset,
1014 : size_t const to_add,
1015 : CCC_Allocator const *const allocator
1016 : ) {
1017 46 : return CCC_flat_bitset_reserve(bitset, to_add, allocator);
1018 : }
1019 :
1020 : CCC_Tribool
1021 2508 : CCC_private_flat_bitset_set(
1022 : struct CCC_Flat_bitset *const bitset,
1023 : size_t const index,
1024 : CCC_Tribool const bit
1025 : ) {
1026 2508 : return CCC_flat_bitset_set(bitset, index, bit);
1027 : }
1028 :
1029 : /*======================= Static Helpers ==============================*/
1030 :
1031 : /** Assumes set size is greater than or equal to subset size. */
1032 : static inline CCC_Tribool
1033 9 : is_subset_of(
1034 : struct CCC_Flat_bitset const *const subset,
1035 : struct CCC_Flat_bitset const *const set
1036 : ) {
1037 9 : assert(set->count >= subset->count);
1038 69 : for (Block_count i = 0, end = block_count(subset->count); i < end; ++i) {
1039 : /* Invariant: the last N unused bits in a set zero so this works. */
1040 60 : if (!is_mask_match(set->blocks[i], subset->blocks[i])) {
1041 4 : return CCC_FALSE;
1042 : }
1043 56 : }
1044 5 : return CCC_TRUE;
1045 9 : }
1046 :
1047 : static CCC_Result
1048 1743 : maybe_resize(
1049 : struct CCC_Flat_bitset *const bitset,
1050 : size_t const to_add,
1051 : CCC_Allocator const *const allocator
1052 : ) {
1053 1743 : size_t bits_needed = 0;
1054 1743 : if (ckd_add(&bits_needed, bitset->count, to_add)) {
1055 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1056 : }
1057 1743 : if (bits_needed <= bitset->capacity) {
1058 1692 : return CCC_RESULT_OK;
1059 : }
1060 51 : if (!allocator->allocate) {
1061 3 : return CCC_RESULT_NO_ALLOCATION_FUNCTION;
1062 : }
1063 48 : if (to_add == 1 && ckd_mul(&bits_needed, bits_needed, 2)) {
1064 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1065 : }
1066 : static_assert(
1067 : (BLOCK_BITS & (BLOCK_BITS - 1)) == 0,
1068 : "rounding trick only works for powers of 2"
1069 : );
1070 48 : size_t new_capacity = 0;
1071 48 : if (CCC_checked_roundup(&new_capacity, bits_needed, BLOCK_BITS)) {
1072 1 : return CCC_RESULT_ALLOCATOR_ERROR;
1073 : }
1074 47 : size_t new_bytes = 0;
1075 47 : if (checked_block_count(&new_bytes, new_capacity - bitset->count)
1076 47 : || ckd_mul(&new_bytes, new_bytes, (size_t)SIZEOF_BLOCK)) {
1077 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1078 : }
1079 : /* Don't need to check old allocation for overflow because it has already
1080 : been successfully allocated. */
1081 94 : size_t const old_bytes
1082 47 : = bitset->count ? block_count(bitset->count) * SIZEOF_BLOCK : 0;
1083 47 : size_t total_allocation_bytes = 0;
1084 47 : if (checked_block_count(&total_allocation_bytes, new_capacity)
1085 47 : || ckd_mul(
1086 : &total_allocation_bytes,
1087 47 : total_allocation_bytes,
1088 : (size_t)SIZEOF_BLOCK
1089 : )) {
1090 0 : return CCC_RESULT_ALLOCATOR_ERROR;
1091 : }
1092 188 : Bit_block *const new_data = allocator->allocate((CCC_Allocator_arguments){
1093 47 : .input = bitset->blocks,
1094 47 : .bytes = total_allocation_bytes,
1095 : .alignment = alignof(*bitset->blocks),
1096 47 : .context = allocator->context,
1097 : });
1098 47 : if (!new_data) {
1099 1 : return CCC_RESULT_ALLOCATOR_ERROR;
1100 : }
1101 46 : (void)memset((char *)new_data + old_bytes, 0, new_bytes);
1102 46 : bitset->capacity = new_capacity;
1103 46 : bitset->blocks = new_data;
1104 46 : return CCC_RESULT_OK;
1105 1743 : }
1106 :
1107 : /** A trailing bit in a range is the first bit set to the specified boolean
1108 : value in the provided range. The input i gives the starting bit of the search,
1109 : meaning a bit within a block that is the inclusive start of the range. The count
1110 : gives us the end of the search for an overall range of `[i, i + count)`. This
1111 : means if the search range is greater than a single block we will iterate in
1112 : ascending order through our blocks and from least to most significant bit within
1113 : each block. */
1114 : static CCC_Count
1115 3073 : first_trailing_bit_range(
1116 : struct CCC_Flat_bitset const *const bitset,
1117 : size_t const i,
1118 : size_t const count,
1119 : CCC_Tribool const is_one
1120 : ) {
1121 3073 : size_t exclusive_end = 0;
1122 3073 : if (ckd_add(&exclusive_end, i, count) || !bitset || !count
1123 3073 : || i >= bitset->count || exclusive_end > bitset->count) {
1124 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
1125 : }
1126 3072 : Block_count start_block = block_count_index(i);
1127 3072 : Bit_count const start_bit = bit_count_index(i);
1128 3072 : Bit_block first_block_mask = leading_ones_mask(BLOCK_BITS - start_bit);
1129 3072 : if (start_bit + count < BLOCK_BITS) {
1130 65 : first_block_mask &= trailing_ones_mask((Bit_count)(start_bit + count));
1131 65 : }
1132 6144 : Bit_count trailing_zeros = count_trailing_zeros(
1133 3072 : first_block_mask
1134 3072 : & (is_one ? bitset->blocks[start_block] : ~bitset->blocks[start_block])
1135 : );
1136 3072 : if (trailing_zeros != BLOCK_BITS) {
1137 2112 : return (CCC_Count){
1138 1056 : .count = (start_block * BLOCK_BITS) + trailing_zeros,
1139 : };
1140 : }
1141 2016 : Block_count const end_block = block_count_index(exclusive_end - 1);
1142 2016 : if (end_block == start_block) {
1143 66 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1144 : }
1145 15364 : while (++start_block < end_block) {
1146 14338 : trailing_zeros = count_trailing_zeros(
1147 14338 : is_one ? bitset->blocks[start_block] : ~bitset->blocks[start_block]
1148 : );
1149 14338 : if (trailing_zeros != BLOCK_BITS) {
1150 1848 : return (CCC_Count){
1151 924 : .count = (start_block * BLOCK_BITS) + trailing_zeros,
1152 : };
1153 : }
1154 : }
1155 2052 : Bit_block const last_block_mask
1156 1026 : = trailing_ones_mask(bit_count_index(exclusive_end - 1) + 1);
1157 1026 : trailing_zeros = count_trailing_zeros(
1158 1026 : last_block_mask
1159 1026 : & (is_one ? bitset->blocks[end_block] : ~bitset->blocks[end_block])
1160 : );
1161 1026 : if (trailing_zeros != BLOCK_BITS) {
1162 134 : return (CCC_Count){
1163 67 : .count = (end_block * BLOCK_BITS) + trailing_zeros,
1164 : };
1165 : }
1166 959 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1167 3073 : }
1168 :
1169 : /** Finds the starting index of a sequence of 1's or 0's of the num_bits size in
1170 : linear time. The algorithm aims to efficiently skip as many bits as possible
1171 : while searching for the desired group. This avoids both an O(N^2) runtime and
1172 : the use of any unnecessary modulo or division operations in a hot loop. */
1173 : static CCC_Count
1174 17225 : first_trailing_bits_range( /* NOLINT (*cognitive-complexity) */
1175 : struct CCC_Flat_bitset const *const bitset,
1176 : size_t const i,
1177 : size_t const count,
1178 : size_t const num_bits,
1179 : CCC_Tribool const ones
1180 : ) {
1181 17225 : size_t exclusive_end = 0;
1182 17225 : if (ckd_add(&exclusive_end, i, count) || !bitset || !count || !num_bits
1183 17218 : || i >= bitset->count || num_bits > count
1184 17218 : || exclusive_end > bitset->count) {
1185 209 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
1186 : }
1187 17016 : size_t bit_count = 0;
1188 17016 : size_t window_start = i;
1189 17016 : Block_count block_index = block_count_index(i);
1190 17016 : size_t window_end = (block_index * BLOCK_BITS) + BLOCK_BITS;
1191 17016 : Bit_count bit_index = bit_count_index(i);
1192 34032 : Bit_block bits
1193 17016 : = ones ? bitset->blocks[block_index] : ~bitset->blocks[block_index];
1194 17016 : bits &= leading_ones_mask(BLOCK_BITS - bit_index);
1195 125970 : for (;;) {
1196 125970 : if (window_end > exclusive_end) {
1197 6317 : bits &= trailing_ones_mask(bit_count_index(exclusive_end - 1) + 1);
1198 6317 : }
1199 125970 : if (!bits) {
1200 97187 : window_start = (block_index + 1) * BLOCK_BITS;
1201 97187 : bit_count = 0;
1202 97187 : } else {
1203 28783 : size_t bits_remain = num_bits - bit_count;
1204 : /* I would rather check for a prefix that could be completing in
1205 : this block here than check for a failure and reset to number of
1206 : bits on every iteration of the next loop. Think of this like loop
1207 : unrolling while also making next block simpler. */
1208 28783 : if (bits_remain <= BLOCK_BITS && bits_remain < num_bits) {
1209 10068 : assert(bit_index < BLOCK_BITS && "shifts are valid for block");
1210 10068 : Bit_block const shifted_bits = bits >> bit_index;
1211 10068 : if (is_mask_match(
1212 10068 : shifted_bits, trailing_ones_mask((Bit_count)bits_remain)
1213 : )) {
1214 6052 : return (CCC_Count){.count = window_start};
1215 : }
1216 4016 : bits_remain = num_bits;
1217 4016 : bit_index += count_trailing_zeros(~shifted_bits);
1218 4016 : bit_count = 0;
1219 4016 : window_start = (block_index * BLOCK_BITS) + bit_index;
1220 10068 : }
1221 22731 : if (bits_remain <= BLOCK_BITS) {
1222 10269 : assert(bit_index < BLOCK_BITS && "shifts are valid for block");
1223 10269 : Bit_block shifted_bits = bits >> bit_index;
1224 20538 : Bit_block const bits_remain_mask
1225 10269 : = trailing_ones_mask((Bit_count)bits_remain);
1226 : /* The loop continues only while our block is numerically
1227 : greater than the mask. Because unsigned integers are
1228 : represented in base 2 we get two automatic early exits here.
1229 : - If the block is missing a high-order bit in the
1230 : required mask, it is numerically smaller than the mask
1231 : and cannot match with further shifting.
1232 : - If all high bits match but some lower required bits are
1233 : zero, the block is numerically smaller than the mask
1234 : and cannot match with further shifting.
1235 : If the block has high order bits not in the mask it is
1236 : greater than the mask and we continue checking, which is
1237 : correct. This strategy optimizes out some useless shifts. */
1238 54884 : while (shifted_bits >= bits_remain_mask) {
1239 47162 : if (is_mask_match(shifted_bits, bits_remain_mask)) {
1240 5094 : return (CCC_Count){
1241 2547 : .count = (block_index * BLOCK_BITS) + bit_index,
1242 : };
1243 : }
1244 44615 : ++bit_index;
1245 44615 : shifted_bits >>= 1;
1246 : }
1247 7722 : bit_count = 0;
1248 10269 : }
1249 : /* 2 cases covered: the ones remaining are greater than this block
1250 : could hold or we did not find a match by the masking we just did.
1251 : In either case we need the maximum contiguous ones that run all
1252 : the way to the MSB. The best we could have is a full block of
1253 : 1's. Otherwise we need to find where to start our new search for
1254 : contiguous 1's. This could be the next block if there are not 1's
1255 : that continue to MSB. */
1256 20184 : Bit_count const leading_ones = count_leading_zeros(~bits);
1257 20184 : bit_count += leading_ones;
1258 20184 : if (leading_ones < BLOCK_BITS) {
1259 : window_start
1260 15658 : = (block_index * BLOCK_BITS) + (BLOCK_BITS - leading_ones);
1261 15658 : }
1262 28783 : }
1263 117371 : if (window_start + num_bits > exclusive_end) {
1264 8417 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1265 : }
1266 108954 : bit_index = 0;
1267 108954 : ++block_index;
1268 108954 : window_end += BLOCK_BITS;
1269 0 : assert(
1270 108954 : block_index < block_count_index(bitset->capacity)
1271 108954 : && "only load bits within block array capacity"
1272 : );
1273 : bits
1274 108954 : = ones ? bitset->blocks[block_index] : ~bitset->blocks[block_index];
1275 : }
1276 17225 : }
1277 :
1278 : /** A leading bit is the first bit in the range to be set to the indicated value
1279 : within a block starting the search from the Most Significant Bit of each block.
1280 : This means that if the range is larger than a single block we iterate in
1281 : descending order through the set of blocks starting at `i + count
1282 : - 1` for the range of `[i, i + count)`. The search within a given block
1283 : proceeds from Most Significant Bit toward Least Significant Bit. */
1284 : static CCC_Count
1285 3088 : first_leading_bit_range(
1286 : struct CCC_Flat_bitset const *const bitset,
1287 : size_t const start_index,
1288 : size_t const count,
1289 : CCC_Tribool const is_one
1290 : ) {
1291 3088 : size_t window_start = 0;
1292 3088 : if (ckd_add(&window_start, start_index, count) || !bitset || !count
1293 3088 : || start_index >= bitset->count || window_start > bitset->count) {
1294 1022 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
1295 : }
1296 2066 : window_start -= 1;
1297 2066 : Bit_count const start_bit = bit_count_index(window_start);
1298 2066 : Bit_count const end_bit = bit_count_index(start_index);
1299 2066 : Block_count start_block = block_count_index(window_start);
1300 2066 : Bit_block first_block_mask = trailing_ones_mask(start_bit + 1);
1301 2066 : if (start_index + count < BLOCK_BITS) {
1302 76 : first_block_mask &= leading_ones_mask(BLOCK_BITS - end_bit);
1303 76 : }
1304 4132 : Bit_count leading_zeros = count_leading_zeros(
1305 2066 : first_block_mask
1306 2066 : & (is_one ? bitset->blocks[start_block] : ~bitset->blocks[start_block])
1307 : );
1308 2066 : if (leading_zeros != BLOCK_BITS) {
1309 2132 : return (CCC_Count){
1310 1066 : .count = (start_block * BLOCK_BITS)
1311 1066 : + (Block_count)(BLOCK_BITS - leading_zeros - 1),
1312 : };
1313 : }
1314 1000 : Block_count const end_block = block_count_index(start_index);
1315 1000 : if (start_block == end_block) {
1316 4 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1317 : }
1318 7774 : while (--start_block > end_block) {
1319 7702 : leading_zeros = count_leading_zeros(
1320 7702 : is_one ? bitset->blocks[start_block] : ~bitset->blocks[start_block]
1321 : );
1322 7702 : if (leading_zeros != BLOCK_BITS) {
1323 1848 : return (CCC_Count){
1324 924 : .count = (start_block * BLOCK_BITS)
1325 924 : + (Block_count)(BLOCK_BITS - leading_zeros - 1),
1326 : };
1327 : }
1328 : }
1329 72 : Bit_block const last_block_on = leading_ones_mask(BLOCK_BITS - end_bit);
1330 72 : leading_zeros = count_leading_zeros(
1331 72 : last_block_on
1332 72 : & (is_one ? bitset->blocks[end_block] : ~bitset->blocks[end_block])
1333 : );
1334 72 : if (leading_zeros != BLOCK_BITS) {
1335 138 : return (CCC_Count){
1336 69 : .count = (end_block * BLOCK_BITS)
1337 69 : + (Block_count)(BLOCK_BITS - leading_zeros - 1),
1338 : };
1339 : }
1340 3 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1341 3088 : }
1342 :
1343 : /** Iterating backward from MSB to LSB requires more care to avoid unsigned
1344 : integer wrapping. Therefore, this code is not identical to the trailing version
1345 : due to a few more branches. This function previously used signed types to avoid
1346 : this branching but that required making new signed types, copious casting, and
1347 : verification of input to be within ptrdiff_t limits. For consistency and
1348 : portability I think committing to unsigned is better for this function. */
1349 : static CCC_Count
1350 17189 : first_leading_bits_range( /* NOLINT (*cognitive-complexity) */
1351 : struct CCC_Flat_bitset const *const bitset,
1352 : size_t const index,
1353 : size_t const range_count,
1354 : size_t const bits_required,
1355 : CCC_Tribool const ones
1356 : ) {
1357 17189 : size_t window_start = 0;
1358 17189 : if (ckd_add(&window_start, index, range_count) || !bitset || !range_count
1359 17189 : || !bits_required || index >= bitset->count
1360 17188 : || bits_required > range_count) {
1361 1 : return (CCC_Count){.error = CCC_RESULT_ARGUMENT_ERROR};
1362 : }
1363 17188 : window_start -= 1;
1364 17188 : size_t bit_count = 0;
1365 17188 : Block_count block_index = block_count_index(window_start);
1366 17188 : Block_count window_inclusive_end = ((block_index * BLOCK_BITS));
1367 17188 : Bit_count bit_index = bit_count_index(window_start);
1368 34376 : Bit_block bits
1369 17188 : = ones ? bitset->blocks[block_index] : ~bitset->blocks[block_index];
1370 17188 : bits &= trailing_ones_mask(bit_index + 1);
1371 130737 : for (;;) {
1372 130737 : if (window_inclusive_end < index) {
1373 5545 : bits &= leading_ones_mask(BLOCK_BITS - bit_count_index(index));
1374 5545 : }
1375 130737 : if (!bits) {
1376 96355 : window_start = block_index ? (block_index * BLOCK_BITS) - 1 : 0;
1377 96355 : bit_count = 0;
1378 96355 : } else {
1379 34382 : size_t bits_remain = bits_required - bit_count;
1380 : /* I would rather check for a prefix that could be completing in
1381 : this block here than check for a failure and reset to number of
1382 : bits on every iteration of the next loop. Think of this like loop
1383 : unrolling while also making next block simpler. */
1384 34382 : if (bits_remain <= BLOCK_BITS && bits_remain < bits_required) {
1385 11987 : assert(bit_index < BLOCK_BITS && "shifts are valid for block");
1386 23974 : Bit_block const shifted_block = bits
1387 11987 : << (BLOCK_BITS - bit_index - 1);
1388 11987 : if (is_mask_match(
1389 11987 : shifted_block, leading_ones_mask((Bit_count)bits_remain)
1390 : )) {
1391 6038 : return (CCC_Count){.count = window_start};
1392 : }
1393 5949 : bits_remain = bits_required;
1394 11898 : Bit_count const leading_ones
1395 5949 : = count_leading_zeros(~shifted_block);
1396 5949 : assert(bit_index >= leading_ones && "index cannot underflow");
1397 5949 : bit_index -= leading_ones;
1398 5949 : window_start = (block_index * BLOCK_BITS) + bit_index;
1399 5949 : bit_count = 0;
1400 11987 : }
1401 28344 : if (bits_remain <= BLOCK_BITS) {
1402 13287 : assert(bit_index < BLOCK_BITS && "shifts are valid for block");
1403 13287 : Bit_block shifted_block = bits << (BLOCK_BITS - bit_index - 1);
1404 26574 : Bit_block const bits_remain_mask
1405 13287 : = leading_ones_mask((Bit_count)bits_remain);
1406 : /* Can't find a clever way to reduce shifts like trailing. */
1407 13287 : Bit_count const end_index = (Bit_count)(bits_remain - 1);
1408 103330 : while (bit_index >= end_index) {
1409 92586 : if (is_mask_match(shifted_block, bits_remain_mask)) {
1410 5086 : return (CCC_Count){
1411 2543 : .count = (block_index * BLOCK_BITS) + bit_index,
1412 : };
1413 : }
1414 90043 : --bit_index;
1415 90043 : shifted_block <<= 1;
1416 : }
1417 10744 : bit_count = 0;
1418 13287 : }
1419 25801 : Bit_count const trailing_ones = count_trailing_zeros(~bits);
1420 25801 : bit_count += trailing_ones;
1421 25801 : if (trailing_ones < BLOCK_BITS) {
1422 20402 : window_start = (block_index * BLOCK_BITS) + trailing_ones;
1423 20402 : if (window_start) {
1424 19876 : --window_start;
1425 19876 : }
1426 20402 : }
1427 34382 : }
1428 122156 : if (window_start < index + bits_required - 1) {
1429 8607 : return (CCC_Count){.error = CCC_RESULT_FAIL};
1430 : }
1431 113549 : bit_index = BLOCK_BITS - 1;
1432 113549 : --block_index;
1433 113549 : window_inclusive_end = window_inclusive_end >= BLOCK_BITS
1434 113549 : ? window_inclusive_end - BLOCK_BITS
1435 : : 0;
1436 0 : assert(
1437 113549 : block_index < block_count_index(bitset->capacity)
1438 113549 : && "current block within range while iterating toward LSB"
1439 : );
1440 : bits
1441 113549 : = ones ? bitset->blocks[block_index] : ~bitset->blocks[block_index];
1442 : }
1443 17189 : }
1444 :
1445 : /** Performs the any or none scan operation over the specified range. The only
1446 : difference between the operations is the return value. Specify the desired
1447 : Tribool value to return upon encountering an on bit. For any this is CCC_TRUE.
1448 : For none this is CCC_FALSE. Saves writing two identical fns. */
1449 : static CCC_Tribool
1450 2571 : any_or_none_range(
1451 : struct CCC_Flat_bitset const *const bitset,
1452 : size_t const i,
1453 : size_t const count,
1454 : CCC_Tribool const any_or_none
1455 : ) {
1456 2571 : size_t range_end = 0;
1457 2571 : if (ckd_add(&range_end, i, count) || !bitset || !count || i >= bitset->count
1458 2570 : || range_end > bitset->count || any_or_none < CCC_FALSE
1459 2570 : || any_or_none > CCC_TRUE) {
1460 1 : return CCC_TRIBOOL_ERROR;
1461 : }
1462 2570 : Block_count start_block = block_count_index(i);
1463 2570 : Bit_count const start_bit = bit_count_index(i);
1464 2570 : Bit_block first_block_mask = leading_ones_mask(BLOCK_BITS - start_bit);
1465 2570 : if (start_bit + count < BLOCK_BITS) {
1466 18 : first_block_mask &= trailing_ones_mask((Bit_count)(start_bit + count));
1467 18 : }
1468 2570 : if (first_block_mask & bitset->blocks[start_block]) {
1469 166 : return any_or_none;
1470 : }
1471 2404 : Block_count const end_block = block_count_index(range_end - 1);
1472 2404 : if (end_block == start_block) {
1473 18 : return !any_or_none;
1474 : }
1475 : /* If this is the any check we might get lucky by checking the last
1476 : block before looping over everything. */
1477 4772 : Bit_block const last_block_mask
1478 2386 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
1479 2386 : if (last_block_mask & bitset->blocks[end_block]) {
1480 226 : return any_or_none;
1481 : }
1482 20864 : for (++start_block; start_block < end_block; ++start_block) {
1483 19600 : if (bitset->blocks[start_block] & BLOCK_ON) {
1484 896 : return any_or_none;
1485 : }
1486 18704 : }
1487 1264 : return !any_or_none;
1488 2571 : }
1489 :
1490 : /** Check for all on is slightly different from the any or none checks so we
1491 : need a painfully repetitive function. */
1492 : static CCC_Tribool
1493 1037 : all_range(
1494 : struct CCC_Flat_bitset const *const bitset,
1495 : size_t const i,
1496 : size_t const count
1497 : ) {
1498 1037 : size_t range_end = 0;
1499 1037 : if (ckd_add(&range_end, i, count) || !bitset || !count || i >= bitset->count
1500 1036 : || range_end > bitset->count) {
1501 1 : return CCC_TRIBOOL_ERROR;
1502 : }
1503 1036 : Block_count start_block = block_count_index(i);
1504 1036 : Bit_count const start_bit = bit_count_index(i);
1505 1036 : Bit_block first_block_mask = leading_ones_mask(BLOCK_BITS - start_bit);
1506 1036 : if (start_bit + count < BLOCK_BITS) {
1507 5 : first_block_mask &= trailing_ones_mask((Bit_count)(start_bit + count));
1508 5 : }
1509 1036 : if ((first_block_mask & bitset->blocks[start_block]) != first_block_mask) {
1510 771 : return CCC_FALSE;
1511 : }
1512 265 : Block_count const end_block = block_count_index(range_end - 1);
1513 265 : if (end_block == start_block) {
1514 4 : return CCC_TRUE;
1515 : }
1516 2079 : while (++start_block < end_block) {
1517 1819 : if (bitset->blocks[start_block] != BLOCK_ON) {
1518 1 : return CCC_FALSE;
1519 : }
1520 : }
1521 520 : Bit_block const last_block_mask
1522 260 : = trailing_ones_mask(bit_count_index(range_end - 1) + 1);
1523 260 : return is_mask_match(bitset->blocks[end_block], last_block_mask);
1524 1037 : }
1525 :
1526 : /** Given the 0 based index from `[0, count of used bits in set)` returns a
1527 : reference to the block that such a bit belongs to. This block reference will
1528 : point to some block at index [0, count of blocks used in the set). */
1529 : static inline Bit_block *
1530 40900 : block_at(
1531 : struct CCC_Flat_bitset const *const bitset, size_t const flat_bitset_index
1532 : ) {
1533 40900 : return &bitset->blocks[block_count_index(flat_bitset_index)];
1534 : }
1535 :
1536 : /** Sets all bits in bulk to value b and fixes the end block to ensure all bits
1537 : in the final block that are not in use are zeroed out. */
1538 : static inline void
1539 36 : set_all(struct CCC_Flat_bitset *const bitset, CCC_Tribool const b) {
1540 36 : int const v = b ? ~0 : 0;
1541 36 : (void)memset(bitset->blocks, v, block_count(bitset->count) * SIZEOF_BLOCK);
1542 36 : fix_end(bitset);
1543 36 : }
1544 :
1545 : /** Given the appropriate block in which bit_i resides, sets the bits position
1546 : to 0 or 1 as specified by the CCC_Tribool argument b.
1547 :
1548 : Assumes block has been retrieved correctly in range [0, count of blocks in set)
1549 : and that bit_i is in range [0, count of active bits in set). */
1550 : static inline void
1551 15412 : set(Bit_block *const block,
1552 : size_t const flat_bitset_index,
1553 : CCC_Tribool const b) {
1554 15412 : if (b) {
1555 8986 : *block |= on(flat_bitset_index);
1556 8986 : } else {
1557 6426 : *block &= ~on(flat_bitset_index);
1558 : }
1559 15412 : }
1560 :
1561 : /** Given the bit set and the set index, set index is allowed to be greater than
1562 : the size of one block, returns the status of the bit at that index. */
1563 : static inline CCC_Tribool
1564 20136 : status(Bit_block const *const bitset, size_t const flat_bitset_index) {
1565 : /* Be careful. The & op does not promise to evaluate to 1 or 0. We often
1566 : just use it where that conversion takes place implicitly for us. */
1567 20136 : return (*bitset & on(flat_bitset_index)) != 0;
1568 : }
1569 :
1570 : /** Given the true bit index in the bit set, expected to be in the range
1571 : [0, count of active bits in set), returns a Bit_block mask with only this bit
1572 : on in block to which it belongs. This mask guarantees to have a bit on within
1573 : a bit block at index [0, BIT_BLOCK_BITS - 1). */
1574 : static inline Bit_block
1575 35552 : on(size_t flat_bitset_index) {
1576 35552 : return (Bit_block)1 << bit_count_index(flat_bitset_index);
1577 : }
1578 :
1579 : /** Clears unused bits in the last block according to count. Sets the last block
1580 : to have only the used bits set to their given values and all bits after to zero.
1581 : This is used as a safety mechanism throughout the code after complex operations
1582 : on bit blocks to ensure any side effects on unused bits are deleted. */
1583 : static inline void
1584 19092 : fix_end(struct CCC_Flat_bitset *const bitset) {
1585 19092 : bitset->count
1586 19072 : ? (*block_at(bitset, bitset->count - 1)
1587 38144 : &= trailing_ones_mask(bit_count_index(bitset->count - 1) + 1))
1588 20 : : (bitset->blocks[0] = 0);
1589 19092 : }
1590 :
1591 : /** Returns the 0-based index of the block in the block array allocation to
1592 : which the given index belongs. Assumes the given index is somewhere between [0,
1593 : count of bits set). The returned index then represents the block in which this
1594 : index resides which is in the range [0, block containing last in use bit). */
1595 : static inline Block_count
1596 360618 : block_count_index(size_t const flat_bitset_index) {
1597 : static_assert(
1598 : (typeof(flat_bitset_index))~((typeof(flat_bitset_index))0)
1599 : >= (typeof(flat_bitset_index))0,
1600 : "shifting to avoid division with power of 2 divisor is only "
1601 : "defined for unsigned types"
1602 : );
1603 360618 : return flat_bitset_index >> BLOCK_BITS_LOG2;
1604 : }
1605 :
1606 : /** Returns the 0-based index within a block to which the given index belongs.
1607 : This index will always be between [0, BIT_BLOCK_BITS - 1). */
1608 : static inline Bit_count
1609 161186 : bit_count_index(size_t const flat_bitset_index) {
1610 161186 : return flat_bitset_index & (BLOCK_BITS - 1);
1611 : }
1612 :
1613 : /** Returns the number of blocks required to store the given bits. Assumes bits
1614 : is non-zero. For any bits > 1 the block count is always less than bits. */
1615 : static inline Block_count
1616 9365 : block_count(size_t const bit_count) {
1617 : static_assert(
1618 : (typeof(bit_count))~((typeof(bit_count))0) >= (typeof(bit_count))0,
1619 : "shifting to avoid division with power of 2 divisor is only "
1620 : "defined for unsigned types"
1621 : );
1622 9365 : assert(bit_count && "calculating block count for non-empty bitset");
1623 9365 : return (bit_count + (BLOCK_BITS - 1)) >> BLOCK_BITS_LOG2;
1624 : }
1625 :
1626 : /** Returns the number of blocks required to store the given bits. Assumes bits
1627 : is non-zero. For any bits > 1 the block count is always less than bits.
1628 :
1629 : This function checks for overflow when obtaining the count and returns CCC_TRUE
1630 : if overflow occured otherwise CCC_FALSE. */
1631 : static inline CCC_Tribool
1632 94 : checked_block_count(Block_count *const result, size_t const bit_count) {
1633 94 : assert(bit_count && "calculating block count for non-empty bitset");
1634 94 : if (ckd_add(result, bit_count, (BLOCK_BITS - 1))) {
1635 0 : return CCC_TRUE;
1636 : }
1637 94 : *result >>= BLOCK_BITS_LOG2;
1638 94 : return CCC_FALSE;
1639 94 : }
1640 :
1641 : /** Returns true if the on bit mask is present in the block. All one bits in the
1642 : mask must be found at the same positions in the block being queried. */
1643 : static inline CCC_Tribool
1644 162123 : is_mask_match(Bit_block const block, Bit_block const on_mask) {
1645 162123 : return (block & on_mask) == on_mask;
1646 : }
1647 :
1648 : /** Returns a mask of the specified count of trailing bits set to 1 (CCC_TRUE)
1649 : within a bit block. This is the same integer type that is stored in the bit set
1650 : integer block array. Trailing ones are ones starting from index 0, the Least
1651 : Significant Bit, counting toward the Most Significant Bit of the block. A count
1652 : of zero will return 0. A count equivalent to the block bit width will return a
1653 : mask with all bits set to 1. */
1654 : static inline Bit_block
1655 92434 : trailing_ones_mask(Bit_count const ones_count) {
1656 92434 : assert(ones_count <= BLOCK_BITS && "shift is well defined for mask");
1657 92434 : return ones_count ? BLOCK_ON >> (BLOCK_BITS - ones_count) : 0;
1658 : }
1659 :
1660 : /** Returns a mask of the specified count of leading bits set to 1 (CCC_TRUE)
1661 : within a bit block. This is the same integer type that is stored in the bit set
1662 : integer block array. Leading ones are ones starting from index BLOCK_BITS - 1,
1663 : the Most Significant Bit, counting toward 0, the Least Significant Bit, of the
1664 : block. A count of zero will return 0. A count equivalent to the block bit width
1665 : will return a mask with all bits set to 1. */
1666 : static inline Bit_block
1667 78939 : leading_ones_mask(Bit_count const ones_count) {
1668 78939 : assert(ones_count <= BLOCK_BITS && "shift is well defined for mask");
1669 78939 : return ones_count ? BLOCK_ON << (BLOCK_BITS - ones_count) : 0;
1670 : }
1671 :
1672 : /** The following asserts assure that whether portable or built in bit
1673 : operations are used in the coming section we are safe in our assumptions about
1674 : widths and counts. Much of the code relies on the assumption that iterating
1675 : over blocks at at a time is faster than using mathematical operations to
1676 : conceptually iterate over bits. This assumptions mostly comes from the use of
1677 : these built-ins to keep the processing time linear for range based queries,
1678 : while avoiding division and modulo operations. I should test to see the
1679 : performance implications when these built-ins are gone. However they are pretty
1680 : ubiquitous these days. */
1681 :
1682 : static_assert(
1683 : BLOCK_MSB < BLOCK_ON, "most significant bit is set for correct block width"
1684 : );
1685 : static_assert(
1686 : SIZEOF_BLOCK == sizeof(unsigned),
1687 : "builtins remain in sync with bitset block width"
1688 : );
1689 : static_assert(
1690 : sizeof(Bit_block) * CHAR_BIT <= U8_BLOCK_MAX,
1691 : "bit counts are valid for smaller width types a bit set uses"
1692 : );
1693 :
1694 : /** Counts the number of trailing zeros in a bit block starting from least
1695 : significant bit. */
1696 : static inline Bit_count
1697 48253 : count_trailing_zeros(Bit_block const b) {
1698 48253 : return (Bit_count)CCC_count_trailing_zeros(b);
1699 : }
1700 :
1701 : /** Counts the leading zeros in a bit block starting from the most significant
1702 : bit. */
1703 : static inline Bit_count
1704 35973 : count_leading_zeros(Bit_block const b) {
1705 35973 : return (Bit_count)CCC_count_leading_zeros(b);
1706 : }
1707 :
1708 : /** Counts the on bits in a bit block. */
1709 : static inline Bit_count
1710 227961 : popcount(Bit_block const b) {
1711 227961 : return (Bit_count)CCC_popcount(b);
1712 : }
|
