1 /* Array bitsets.
2
3 Copyright (C) 2002-2003, 2006, 2009-2015, 2018-2021 Free Software
4 Foundation, Inc.
5
6 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
7
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <https://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22
23 #include "bitset/array.h"
24 #include <stddef.h>
25 #include <stdlib.h>
26 #include <string.h>
27
28 /* This file implements fixed size bitsets stored as an array
29 of words. Any unused bits in the last word must be zero. */
30
31 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
32 #define ABITSET_WORDS(X) ((X)->a.words)
33
34
35 static bitset_bindex
abitset_resize(bitset src,bitset_bindex size)36 abitset_resize (bitset src, bitset_bindex size)
37 {
38 /* These bitsets have a fixed size. */
39 if (BITSET_SIZE_ (src) != size)
40 abort ();
41
42 return size;
43 }
44
45 /* Find list of up to NUM bits set in SRC starting from and including
46 *NEXT and store in array LIST. Return with actual number of bits
47 found and with *NEXT indicating where search stopped. */
48 static bitset_bindex
abitset_small_list(bitset src,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)49 abitset_small_list (bitset src, bitset_bindex *list,
50 bitset_bindex num, bitset_bindex *next)
51 {
52 bitset_word word = ABITSET_WORDS (src)[0];
53
54 /* Short circuit common case. */
55 if (!word)
56 return 0;
57
58 bitset_windex size = BITSET_SIZE_ (src);
59 bitset_bindex bitno = *next;
60 if (bitno >= size)
61 return 0;
62
63 word >>= bitno;
64
65 bitset_bindex count = 0;
66 /* Is there enough room to avoid checking in each iteration? */
67 if (num >= BITSET_WORD_BITS)
68 BITSET_FOR_EACH_BIT (pos, word)
69 list[count++] = bitno + pos;
70 else
71 BITSET_FOR_EACH_BIT (pos, word)
72 {
73 list[count++] = bitno + pos;
74 if (count >= num)
75 {
76 *next = bitno + pos + 1;
77 return count;
78 }
79 }
80 *next = bitno + BITSET_WORD_BITS;
81 return count;
82 }
83
84
85 /* Set bit BITNO in bitset DST. */
86 static void
abitset_set(MAYBE_UNUSED bitset dst,MAYBE_UNUSED bitset_bindex bitno)87 abitset_set (MAYBE_UNUSED bitset dst, MAYBE_UNUSED bitset_bindex bitno)
88 {
89 /* This should never occur for abitsets since we should always hit
90 the cache. It is likely someone is trying to access outside the
91 bounds of the bitset. */
92 abort ();
93 }
94
95
96 /* Reset bit BITNO in bitset DST. */
97 static void
abitset_reset(MAYBE_UNUSED bitset dst,MAYBE_UNUSED bitset_bindex bitno)98 abitset_reset (MAYBE_UNUSED bitset dst,
99 MAYBE_UNUSED bitset_bindex bitno)
100 {
101 /* This should never occur for abitsets since we should always hit
102 the cache. It is likely someone is trying to access outside the
103 bounds of the bitset. Since the bit is zero anyway, let it pass. */
104 }
105
106
107 /* Test bit BITNO in bitset SRC. */
108 static bool
abitset_test(MAYBE_UNUSED bitset src,MAYBE_UNUSED bitset_bindex bitno)109 abitset_test (MAYBE_UNUSED bitset src,
110 MAYBE_UNUSED bitset_bindex bitno)
111 {
112 /* This should never occur for abitsets since we should always
113 hit the cache. */
114 return false;
115 }
116
117
118 /* Find list of up to NUM bits set in SRC in reverse order, starting
119 from and including NEXT and store in array LIST. Return with
120 actual number of bits found and with *NEXT indicating where search
121 stopped. */
122 static bitset_bindex
abitset_list_reverse(bitset src,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)123 abitset_list_reverse (bitset src, bitset_bindex *list,
124 bitset_bindex num, bitset_bindex *next)
125 {
126 bitset_bindex rbitno = *next;
127 bitset_word *srcp = ABITSET_WORDS (src);
128 bitset_bindex n_bits = BITSET_SIZE_ (src);
129
130 /* If num is 1, we could speed things up with a binary search
131 of the word of interest. */
132
133 if (rbitno >= n_bits)
134 return 0;
135
136 bitset_bindex count = 0;
137
138 bitset_bindex bitno = n_bits - (rbitno + 1);
139
140 bitset_windex windex = bitno / BITSET_WORD_BITS;
141 unsigned bitcnt = bitno % BITSET_WORD_BITS;
142 bitset_bindex bitoff = windex * BITSET_WORD_BITS;
143
144 do
145 {
146 bitset_word word = srcp[windex];
147 if (bitcnt + 1 < BITSET_WORD_BITS)
148 /* We're starting in the middle of a word: smash bits to ignore. */
149 word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
150 BITSET_FOR_EACH_BIT_REVERSE(pos, word)
151 {
152 list[count++] = bitoff + pos;
153 if (count >= num)
154 {
155 *next = n_bits - (bitoff + pos);
156 return count;
157 }
158 }
159 bitoff -= BITSET_WORD_BITS;
160 bitcnt = BITSET_WORD_BITS - 1;
161 }
162 while (windex--);
163
164 *next = n_bits - (bitoff + 1);
165 return count;
166 }
167
168
169 /* Find list of up to NUM bits set in SRC starting from and including
170 *NEXT and store in array LIST. Return with actual number of bits
171 found and with *NEXT indicating where search stopped. */
172 static bitset_bindex
abitset_list(bitset src,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)173 abitset_list (bitset src, bitset_bindex *list,
174 bitset_bindex num, bitset_bindex *next)
175 {
176 bitset_windex windex;
177 bitset_bindex bitoff;
178 bitset_windex size = src->b.csize;
179 bitset_word *srcp = ABITSET_WORDS (src);
180
181 bitset_bindex bitno = *next;
182
183 bitset_bindex count = 0;
184 if (!bitno)
185 {
186 /* Many bitsets are zero, so make this common case fast. */
187 for (windex = 0; windex < size && !srcp[windex]; windex++)
188 continue;
189 if (windex >= size)
190 return 0;
191
192 bitoff = windex * BITSET_WORD_BITS;
193 }
194 else
195 {
196 if (bitno >= BITSET_SIZE_ (src))
197 return 0;
198
199 windex = bitno / BITSET_WORD_BITS;
200 bitno = bitno % BITSET_WORD_BITS;
201
202 if (bitno)
203 {
204 /* Handle the case where we start within a word.
205 Most often, this is executed with large bitsets
206 with many set bits where we filled the array
207 on the previous call to this function. */
208
209 bitoff = windex * BITSET_WORD_BITS;
210 bitset_word word = srcp[windex] >> bitno;
211 bitno = bitoff + bitno;
212 BITSET_FOR_EACH_BIT (pos, word)
213 {
214 list[count++] = bitno + pos;
215 if (count >= num)
216 {
217 *next = bitno + pos + 1;
218 return count;
219 }
220 }
221 windex++;
222 }
223 bitoff = windex * BITSET_WORD_BITS;
224 }
225
226 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
227 {
228 bitset_word word = srcp[windex];
229 if (!word)
230 continue;
231
232 /* Is there enough room to avoid checking in each iteration? */
233 if ((count + BITSET_WORD_BITS) < num)
234 BITSET_FOR_EACH_BIT (pos, word)
235 list[count++] = bitoff + pos;
236 else
237 BITSET_FOR_EACH_BIT (pos, word)
238 {
239 list[count++] = bitoff + pos;
240 if (count >= num)
241 {
242 *next = bitoff + pos + 1;
243 return count;
244 }
245 }
246 }
247
248 *next = bitoff;
249 return count;
250 }
251
252
253 /* Ensure that any unused bits within the last word are clear. */
254 static inline void
abitset_unused_clear(bitset dst)255 abitset_unused_clear (bitset dst)
256 {
257 unsigned last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
258 if (last_bit)
259 ABITSET_WORDS (dst)[dst->b.csize - 1] &=
260 ((bitset_word) 1 << last_bit) - 1;
261 }
262
263
264 static void
abitset_ones(bitset dst)265 abitset_ones (bitset dst)
266 {
267 bitset_word *dstp = ABITSET_WORDS (dst);
268 size_t bytes = sizeof (bitset_word) * dst->b.csize;
269
270 memset (dstp, -1, bytes);
271 abitset_unused_clear (dst);
272 }
273
274
275 static void
abitset_zero(bitset dst)276 abitset_zero (bitset dst)
277 {
278 bitset_word *dstp = ABITSET_WORDS (dst);
279 size_t bytes = sizeof (bitset_word) * dst->b.csize;
280
281 memset (dstp, 0, bytes);
282 }
283
284
285 static bool
abitset_empty_p(bitset dst)286 abitset_empty_p (bitset dst)
287 {
288 bitset_word *dstp = ABITSET_WORDS (dst);
289
290 for (bitset_windex i = 0; i < dst->b.csize; i++)
291 if (dstp[i])
292 return false;
293 return true;
294 }
295
296
297 static void
abitset_copy1(bitset dst,bitset src)298 abitset_copy1 (bitset dst, bitset src)
299 {
300 bitset_word *srcp = ABITSET_WORDS (src);
301 bitset_word *dstp = ABITSET_WORDS (dst);
302 if (srcp == dstp)
303 return;
304 bitset_windex size = dst->b.csize;
305 memcpy (dstp, srcp, sizeof (bitset_word) * size);
306 }
307
308
309 static void
abitset_not(bitset dst,bitset src)310 abitset_not (bitset dst, bitset src)
311 {
312 bitset_word *srcp = ABITSET_WORDS (src);
313 bitset_word *dstp = ABITSET_WORDS (dst);
314 bitset_windex size = dst->b.csize;
315
316 for (bitset_windex i = 0; i < size; i++)
317 *dstp++ = ~(*srcp++);
318 abitset_unused_clear (dst);
319 }
320
321
322 static bool
abitset_equal_p(bitset dst,bitset src)323 abitset_equal_p (bitset dst, bitset src)
324 {
325 bitset_word *srcp = ABITSET_WORDS (src);
326 bitset_word *dstp = ABITSET_WORDS (dst);
327 bitset_windex size = dst->b.csize;
328
329 for (bitset_windex i = 0; i < size; i++)
330 if (*srcp++ != *dstp++)
331 return false;
332 return true;
333 }
334
335
336 static bool
abitset_subset_p(bitset dst,bitset src)337 abitset_subset_p (bitset dst, bitset src)
338 {
339 bitset_word *srcp = ABITSET_WORDS (src);
340 bitset_word *dstp = ABITSET_WORDS (dst);
341 bitset_windex size = dst->b.csize;
342
343 for (bitset_windex i = 0; i < size; i++, dstp++, srcp++)
344 if (*dstp != (*srcp | *dstp))
345 return false;
346 return true;
347 }
348
349
350 static bool
abitset_disjoint_p(bitset dst,bitset src)351 abitset_disjoint_p (bitset dst, bitset src)
352 {
353 bitset_word *srcp = ABITSET_WORDS (src);
354 bitset_word *dstp = ABITSET_WORDS (dst);
355 bitset_windex size = dst->b.csize;
356
357 for (bitset_windex i = 0; i < size; i++)
358 if (*srcp++ & *dstp++)
359 return false;
360 return true;
361 }
362
363
364 static void
abitset_and(bitset dst,bitset src1,bitset src2)365 abitset_and (bitset dst, bitset src1, bitset src2)
366 {
367 bitset_word *src1p = ABITSET_WORDS (src1);
368 bitset_word *src2p = ABITSET_WORDS (src2);
369 bitset_word *dstp = ABITSET_WORDS (dst);
370 bitset_windex size = dst->b.csize;
371
372 for (bitset_windex i = 0; i < size; i++)
373 *dstp++ = *src1p++ & *src2p++;
374 }
375
376
377 static bool
abitset_and_cmp(bitset dst,bitset src1,bitset src2)378 abitset_and_cmp (bitset dst, bitset src1, bitset src2)
379 {
380 bool changed = false;
381 bitset_word *src1p = ABITSET_WORDS (src1);
382 bitset_word *src2p = ABITSET_WORDS (src2);
383 bitset_word *dstp = ABITSET_WORDS (dst);
384 bitset_windex size = dst->b.csize;
385
386 for (bitset_windex i = 0; i < size; i++, dstp++)
387 {
388 bitset_word tmp = *src1p++ & *src2p++;
389 if (*dstp != tmp)
390 {
391 changed = true;
392 *dstp = tmp;
393 }
394 }
395 return changed;
396 }
397
398
399 static void
abitset_andn(bitset dst,bitset src1,bitset src2)400 abitset_andn (bitset dst, bitset src1, bitset src2)
401 {
402 bitset_word *src1p = ABITSET_WORDS (src1);
403 bitset_word *src2p = ABITSET_WORDS (src2);
404 bitset_word *dstp = ABITSET_WORDS (dst);
405 bitset_windex size = dst->b.csize;
406
407 for (bitset_windex i = 0; i < size; i++)
408 *dstp++ = *src1p++ & ~(*src2p++);
409 }
410
411
412 static bool
abitset_andn_cmp(bitset dst,bitset src1,bitset src2)413 abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
414 {
415 bool changed = false;
416 bitset_word *src1p = ABITSET_WORDS (src1);
417 bitset_word *src2p = ABITSET_WORDS (src2);
418 bitset_word *dstp = ABITSET_WORDS (dst);
419 bitset_windex size = dst->b.csize;
420
421 for (bitset_windex i = 0; i < size; i++, dstp++)
422 {
423 bitset_word tmp = *src1p++ & ~(*src2p++);
424 if (*dstp != tmp)
425 {
426 changed = true;
427 *dstp = tmp;
428 }
429 }
430 return changed;
431 }
432
433
434 static void
abitset_or(bitset dst,bitset src1,bitset src2)435 abitset_or (bitset dst, bitset src1, bitset src2)
436 {
437 bitset_word *src1p = ABITSET_WORDS (src1);
438 bitset_word *src2p = ABITSET_WORDS (src2);
439 bitset_word *dstp = ABITSET_WORDS (dst);
440 bitset_windex size = dst->b.csize;
441
442 for (bitset_windex i = 0; i < size; i++)
443 *dstp++ = *src1p++ | *src2p++;
444 }
445
446
447 static bool
abitset_or_cmp(bitset dst,bitset src1,bitset src2)448 abitset_or_cmp (bitset dst, bitset src1, bitset src2)
449 {
450 bool changed = false;
451 bitset_word *src1p = ABITSET_WORDS (src1);
452 bitset_word *src2p = ABITSET_WORDS (src2);
453 bitset_word *dstp = ABITSET_WORDS (dst);
454 bitset_windex size = dst->b.csize;
455
456 for (bitset_windex i = 0; i < size; i++, dstp++)
457 {
458 bitset_word tmp = *src1p++ | *src2p++;
459
460 if (*dstp != tmp)
461 {
462 changed = true;
463 *dstp = tmp;
464 }
465 }
466 return changed;
467 }
468
469
470 static void
abitset_xor(bitset dst,bitset src1,bitset src2)471 abitset_xor (bitset dst, bitset src1, bitset src2)
472 {
473 bitset_word *src1p = ABITSET_WORDS (src1);
474 bitset_word *src2p = ABITSET_WORDS (src2);
475 bitset_word *dstp = ABITSET_WORDS (dst);
476 bitset_windex size = dst->b.csize;
477
478 for (bitset_windex i = 0; i < size; i++)
479 *dstp++ = *src1p++ ^ *src2p++;
480 }
481
482
483 static bool
abitset_xor_cmp(bitset dst,bitset src1,bitset src2)484 abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
485 {
486 bool changed = false;
487 bitset_word *src1p = ABITSET_WORDS (src1);
488 bitset_word *src2p = ABITSET_WORDS (src2);
489 bitset_word *dstp = ABITSET_WORDS (dst);
490 bitset_windex size = dst->b.csize;
491
492 for (bitset_windex i = 0; i < size; i++, dstp++)
493 {
494 bitset_word tmp = *src1p++ ^ *src2p++;
495
496 if (*dstp != tmp)
497 {
498 changed = true;
499 *dstp = tmp;
500 }
501 }
502 return changed;
503 }
504
505
506 static void
abitset_and_or(bitset dst,bitset src1,bitset src2,bitset src3)507 abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
508 {
509 bitset_word *src1p = ABITSET_WORDS (src1);
510 bitset_word *src2p = ABITSET_WORDS (src2);
511 bitset_word *src3p = ABITSET_WORDS (src3);
512 bitset_word *dstp = ABITSET_WORDS (dst);
513 bitset_windex size = dst->b.csize;
514
515 for (bitset_windex i = 0; i < size; i++)
516 *dstp++ = (*src1p++ & *src2p++) | *src3p++;
517 }
518
519
520 static bool
abitset_and_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)521 abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
522 {
523 bool changed = false;
524 bitset_word *src1p = ABITSET_WORDS (src1);
525 bitset_word *src2p = ABITSET_WORDS (src2);
526 bitset_word *src3p = ABITSET_WORDS (src3);
527 bitset_word *dstp = ABITSET_WORDS (dst);
528 bitset_windex size = dst->b.csize;
529
530 for (bitset_windex i = 0; i < size; i++, dstp++)
531 {
532 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
533 if (*dstp != tmp)
534 {
535 changed = true;
536 *dstp = tmp;
537 }
538 }
539 return changed;
540 }
541
542
543 static void
abitset_andn_or(bitset dst,bitset src1,bitset src2,bitset src3)544 abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
545 {
546 bitset_word *src1p = ABITSET_WORDS (src1);
547 bitset_word *src2p = ABITSET_WORDS (src2);
548 bitset_word *src3p = ABITSET_WORDS (src3);
549 bitset_word *dstp = ABITSET_WORDS (dst);
550 bitset_windex size = dst->b.csize;
551
552 for (bitset_windex i = 0; i < size; i++)
553 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
554 }
555
556
557 static bool
abitset_andn_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)558 abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
559 {
560 bool changed = false;
561 bitset_word *src1p = ABITSET_WORDS (src1);
562 bitset_word *src2p = ABITSET_WORDS (src2);
563 bitset_word *src3p = ABITSET_WORDS (src3);
564 bitset_word *dstp = ABITSET_WORDS (dst);
565 bitset_windex size = dst->b.csize;
566
567 for (bitset_windex i = 0; i < size; i++, dstp++)
568 {
569 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
570 if (*dstp != tmp)
571 {
572 changed = true;
573 *dstp = tmp;
574 }
575 }
576 return changed;
577 }
578
579
580 static void
abitset_or_and(bitset dst,bitset src1,bitset src2,bitset src3)581 abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
582 {
583 bitset_word *src1p = ABITSET_WORDS (src1);
584 bitset_word *src2p = ABITSET_WORDS (src2);
585 bitset_word *src3p = ABITSET_WORDS (src3);
586 bitset_word *dstp = ABITSET_WORDS (dst);
587 bitset_windex size = dst->b.csize;
588
589 for (bitset_windex i = 0; i < size; i++)
590 *dstp++ = (*src1p++ | *src2p++) & *src3p++;
591 }
592
593
594 static bool
abitset_or_and_cmp(bitset dst,bitset src1,bitset src2,bitset src3)595 abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
596 {
597 bool changed = false;
598 bitset_word *src1p = ABITSET_WORDS (src1);
599 bitset_word *src2p = ABITSET_WORDS (src2);
600 bitset_word *src3p = ABITSET_WORDS (src3);
601 bitset_word *dstp = ABITSET_WORDS (dst);
602 bitset_windex size = dst->b.csize;
603
604 for (bitset_windex i = 0; i < size; i++, dstp++)
605 {
606 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
607 if (*dstp != tmp)
608 {
609 changed = true;
610 *dstp = tmp;
611 }
612 }
613 return changed;
614 }
615
616
617 static void
abitset_copy(bitset dst,bitset src)618 abitset_copy (bitset dst, bitset src)
619 {
620 if (BITSET_COMPATIBLE_ (dst, src))
621 abitset_copy1 (dst, src);
622 else
623 bitset_copy_ (dst, src);
624 }
625
626
627 /* Vector of operations for single word bitsets. */
628 struct bitset_vtable abitset_small_vtable = {
629 abitset_set,
630 abitset_reset,
631 bitset_toggle_,
632 abitset_test,
633 abitset_resize,
634 bitset_size_,
635 bitset_count_,
636 abitset_empty_p,
637 abitset_ones,
638 abitset_zero,
639 abitset_copy,
640 abitset_disjoint_p,
641 abitset_equal_p,
642 abitset_not,
643 abitset_subset_p,
644 abitset_and,
645 abitset_and_cmp,
646 abitset_andn,
647 abitset_andn_cmp,
648 abitset_or,
649 abitset_or_cmp,
650 abitset_xor,
651 abitset_xor_cmp,
652 abitset_and_or,
653 abitset_and_or_cmp,
654 abitset_andn_or,
655 abitset_andn_or_cmp,
656 abitset_or_and,
657 abitset_or_and_cmp,
658 abitset_small_list,
659 abitset_list_reverse,
660 NULL,
661 BITSET_ARRAY
662 };
663
664
665 /* Vector of operations for multiple word bitsets. */
666 struct bitset_vtable abitset_vtable = {
667 abitset_set,
668 abitset_reset,
669 bitset_toggle_,
670 abitset_test,
671 abitset_resize,
672 bitset_size_,
673 bitset_count_,
674 abitset_empty_p,
675 abitset_ones,
676 abitset_zero,
677 abitset_copy,
678 abitset_disjoint_p,
679 abitset_equal_p,
680 abitset_not,
681 abitset_subset_p,
682 abitset_and,
683 abitset_and_cmp,
684 abitset_andn,
685 abitset_andn_cmp,
686 abitset_or,
687 abitset_or_cmp,
688 abitset_xor,
689 abitset_xor_cmp,
690 abitset_and_or,
691 abitset_and_or_cmp,
692 abitset_andn_or,
693 abitset_andn_or_cmp,
694 abitset_or_and,
695 abitset_or_and_cmp,
696 abitset_list,
697 abitset_list_reverse,
698 NULL,
699 BITSET_ARRAY
700 };
701
702
703 size_t
abitset_bytes(bitset_bindex n_bits)704 abitset_bytes (bitset_bindex n_bits)
705 {
706 size_t header_size = offsetof (union bitset_union, a.words);
707 struct bitset_align_struct { char a; union bitset_union b; };
708 size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
709
710 bitset_windex size = ABITSET_N_WORDS (n_bits);
711 size_t bytes = header_size + size * sizeof (bitset_word);
712
713 /* Align the size properly for a vector of abitset objects. */
714 if (header_size % bitset_alignment != 0
715 || sizeof (bitset_word) % bitset_alignment != 0)
716 {
717 bytes += bitset_alignment - 1;
718 bytes -= bytes % bitset_alignment;
719 }
720
721 return bytes;
722 }
723
724
725 bitset
abitset_init(bitset bset,bitset_bindex n_bits)726 abitset_init (bitset bset, bitset_bindex n_bits)
727 {
728 bitset_windex size = ABITSET_N_WORDS (n_bits);
729 BITSET_NBITS_ (bset) = n_bits;
730
731 /* Use optimized routines if bitset fits within a single word.
732 There is probably little merit if using caching since
733 the small bitset will always fit in the cache. */
734 bset->b.vtable = size == 1 ? &abitset_small_vtable : &abitset_vtable;
735 bset->b.cindex = 0;
736 bset->b.csize = size;
737 bset->b.cdata = ABITSET_WORDS (bset);
738 return bset;
739 }
740