1 /* Array bitsets.
2
3 Copyright (C) 2002-2003, 2006, 2009-2012 Free Software Foundation,
4 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 <http://www.gnu.org/licenses/>. */
20
21 #include <config.h>
22
23 #include "abitset.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 BSET 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_bindex bitno;
53 bitset_bindex count;
54 bitset_windex size;
55 bitset_word word;
56
57 word = ABITSET_WORDS (src)[0];
58
59 /* Short circuit common case. */
60 if (!word)
61 return 0;
62
63 size = BITSET_SIZE_ (src);
64 bitno = *next;
65 if (bitno >= size)
66 return 0;
67
68 word >>= bitno;
69
70 /* If num is 1, we could speed things up with a binary search
71 of the word of interest. */
72
73 if (num >= BITSET_WORD_BITS)
74 {
75 for (count = 0; word; bitno++)
76 {
77 if (word & 1)
78 list[count++] = bitno;
79 word >>= 1;
80 }
81 }
82 else
83 {
84 for (count = 0; word; bitno++)
85 {
86 if (word & 1)
87 {
88 list[count++] = bitno;
89 if (count >= num)
90 {
91 bitno++;
92 break;
93 }
94 }
95 word >>= 1;
96 }
97 }
98
99 *next = bitno;
100 return count;
101 }
102
103
104 /* Set bit BITNO in bitset DST. */
105 static void
abitset_set(bitset dst ATTRIBUTE_UNUSED,bitset_bindex bitno ATTRIBUTE_UNUSED)106 abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
107 {
108 /* This should never occur for abitsets since we should always hit
109 the cache. It is likely someone is trying to access outside the
110 bounds of the bitset. */
111 abort ();
112 }
113
114
115 /* Reset bit BITNO in bitset DST. */
116 static void
abitset_reset(bitset dst ATTRIBUTE_UNUSED,bitset_bindex bitno ATTRIBUTE_UNUSED)117 abitset_reset (bitset dst ATTRIBUTE_UNUSED,
118 bitset_bindex bitno ATTRIBUTE_UNUSED)
119 {
120 /* This should never occur for abitsets since we should always hit
121 the cache. It is likely someone is trying to access outside the
122 bounds of the bitset. Since the bit is zero anyway, let it pass. */
123 }
124
125
126 /* Test bit BITNO in bitset SRC. */
127 static bool
abitset_test(bitset src ATTRIBUTE_UNUSED,bitset_bindex bitno ATTRIBUTE_UNUSED)128 abitset_test (bitset src ATTRIBUTE_UNUSED,
129 bitset_bindex bitno ATTRIBUTE_UNUSED)
130 {
131 /* This should never occur for abitsets since we should always
132 hit the cache. */
133 return false;
134 }
135
136
137 /* Find list of up to NUM bits set in BSET in reverse order, starting
138 from and including NEXT and store in array LIST. Return with
139 actual number of bits found and with *NEXT indicating where search
140 stopped. */
141 static bitset_bindex
abitset_list_reverse(bitset src,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)142 abitset_list_reverse (bitset src, bitset_bindex *list,
143 bitset_bindex num, bitset_bindex *next)
144 {
145 bitset_bindex bitno;
146 bitset_bindex rbitno;
147 bitset_bindex count;
148 bitset_windex windex;
149 unsigned int bitcnt;
150 bitset_bindex bitoff;
151 bitset_word *srcp = ABITSET_WORDS (src);
152 bitset_bindex n_bits = BITSET_SIZE_ (src);
153
154 rbitno = *next;
155
156 /* If num is 1, we could speed things up with a binary search
157 of the word of interest. */
158
159 if (rbitno >= n_bits)
160 return 0;
161
162 count = 0;
163
164 bitno = n_bits - (rbitno + 1);
165
166 windex = bitno / BITSET_WORD_BITS;
167 bitcnt = bitno % BITSET_WORD_BITS;
168 bitoff = windex * BITSET_WORD_BITS;
169
170 do
171 {
172 bitset_word word;
173
174 word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
175 for (; word; bitcnt--)
176 {
177 if (word & BITSET_MSB)
178 {
179 list[count++] = bitoff + bitcnt;
180 if (count >= num)
181 {
182 *next = n_bits - (bitoff + bitcnt);
183 return count;
184 }
185 }
186 word <<= 1;
187 }
188 bitoff -= BITSET_WORD_BITS;
189 bitcnt = BITSET_WORD_BITS - 1;
190 }
191 while (windex--);
192
193 *next = n_bits - (bitoff + 1);
194 return count;
195 }
196
197
198 /* Find list of up to NUM bits set in BSET starting from and including
199 *NEXT and store in array LIST. Return with actual number of bits
200 found and with *NEXT indicating where search stopped. */
201 static bitset_bindex
abitset_list(bitset src,bitset_bindex * list,bitset_bindex num,bitset_bindex * next)202 abitset_list (bitset src, bitset_bindex *list,
203 bitset_bindex num, bitset_bindex *next)
204 {
205 bitset_bindex bitno;
206 bitset_bindex count;
207 bitset_windex windex;
208 bitset_bindex bitoff;
209 bitset_windex size = src->b.csize;
210 bitset_word *srcp = ABITSET_WORDS (src);
211 bitset_word word;
212
213 bitno = *next;
214
215 count = 0;
216 if (!bitno)
217 {
218 /* Many bitsets are zero, so make this common case fast. */
219 for (windex = 0; windex < size && !srcp[windex]; windex++)
220 continue;
221 if (windex >= size)
222 return 0;
223
224 /* If num is 1, we could speed things up with a binary search
225 of the current word. */
226
227 bitoff = windex * BITSET_WORD_BITS;
228 }
229 else
230 {
231 if (bitno >= BITSET_SIZE_ (src))
232 return 0;
233
234 windex = bitno / BITSET_WORD_BITS;
235 bitno = bitno % BITSET_WORD_BITS;
236
237 if (bitno)
238 {
239 /* Handle the case where we start within a word.
240 Most often, this is executed with large bitsets
241 with many set bits where we filled the array
242 on the previous call to this function. */
243
244 bitoff = windex * BITSET_WORD_BITS;
245 word = srcp[windex] >> bitno;
246 for (bitno = bitoff + bitno; word; bitno++)
247 {
248 if (word & 1)
249 {
250 list[count++] = bitno;
251 if (count >= num)
252 {
253 *next = bitno + 1;
254 return count;
255 }
256 }
257 word >>= 1;
258 }
259 windex++;
260 }
261 bitoff = windex * BITSET_WORD_BITS;
262 }
263
264 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
265 {
266 if (!(word = srcp[windex]))
267 continue;
268
269 if ((count + BITSET_WORD_BITS) < num)
270 {
271 for (bitno = bitoff; word; bitno++)
272 {
273 if (word & 1)
274 list[count++] = bitno;
275 word >>= 1;
276 }
277 }
278 else
279 {
280 for (bitno = bitoff; word; bitno++)
281 {
282 if (word & 1)
283 {
284 list[count++] = bitno;
285 if (count >= num)
286 {
287 *next = bitno + 1;
288 return count;
289 }
290 }
291 word >>= 1;
292 }
293 }
294 }
295
296 *next = bitoff;
297 return count;
298 }
299
300
301 /* Ensure that any unused bits within the last word are clear. */
302 static inline void
abitset_unused_clear(bitset dst)303 abitset_unused_clear (bitset dst)
304 {
305 unsigned int last_bit;
306
307 last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
308 if (last_bit)
309 ABITSET_WORDS (dst)[dst->b.csize - 1] &=
310 ((bitset_word) 1 << last_bit) - 1;
311 }
312
313
314 static void
abitset_ones(bitset dst)315 abitset_ones (bitset dst)
316 {
317 bitset_word *dstp = ABITSET_WORDS (dst);
318 size_t bytes;
319
320 bytes = sizeof (bitset_word) * dst->b.csize;
321
322 memset (dstp, -1, bytes);
323 abitset_unused_clear (dst);
324 }
325
326
327 static void
abitset_zero(bitset dst)328 abitset_zero (bitset dst)
329 {
330 bitset_word *dstp = ABITSET_WORDS (dst);
331 size_t bytes;
332
333 bytes = sizeof (bitset_word) * dst->b.csize;
334
335 memset (dstp, 0, bytes);
336 }
337
338
339 static bool
abitset_empty_p(bitset dst)340 abitset_empty_p (bitset dst)
341 {
342 bitset_windex i;
343 bitset_word *dstp = ABITSET_WORDS (dst);
344
345 for (i = 0; i < dst->b.csize; i++)
346 if (dstp[i])
347 return false;
348
349 return true;
350 }
351
352
353 static void
abitset_copy1(bitset dst,bitset src)354 abitset_copy1 (bitset dst, bitset src)
355 {
356 bitset_word *srcp = ABITSET_WORDS (src);
357 bitset_word *dstp = ABITSET_WORDS (dst);
358 bitset_windex size = dst->b.csize;
359
360 if (srcp == dstp)
361 return;
362 memcpy (dstp, srcp, sizeof (bitset_word) * size);
363 }
364
365
366 static void
abitset_not(bitset dst,bitset src)367 abitset_not (bitset dst, bitset src)
368 {
369 bitset_windex i;
370 bitset_word *srcp = ABITSET_WORDS (src);
371 bitset_word *dstp = ABITSET_WORDS (dst);
372 bitset_windex size = dst->b.csize;
373
374 for (i = 0; i < size; i++)
375 *dstp++ = ~(*srcp++);
376 abitset_unused_clear (dst);
377 }
378
379
380 static bool
abitset_equal_p(bitset dst,bitset src)381 abitset_equal_p (bitset dst, bitset src)
382 {
383 bitset_windex i;
384 bitset_word *srcp = ABITSET_WORDS (src);
385 bitset_word *dstp = ABITSET_WORDS (dst);
386 bitset_windex size = dst->b.csize;
387
388 for (i = 0; i < size; i++)
389 if (*srcp++ != *dstp++)
390 return false;
391 return true;
392 }
393
394
395 static bool
abitset_subset_p(bitset dst,bitset src)396 abitset_subset_p (bitset dst, bitset src)
397 {
398 bitset_windex i;
399 bitset_word *srcp = ABITSET_WORDS (src);
400 bitset_word *dstp = ABITSET_WORDS (dst);
401 bitset_windex size = dst->b.csize;
402
403 for (i = 0; i < size; i++, dstp++, srcp++)
404 if (*dstp != (*srcp | *dstp))
405 return false;
406 return true;
407 }
408
409
410 static bool
abitset_disjoint_p(bitset dst,bitset src)411 abitset_disjoint_p (bitset dst, bitset src)
412 {
413 bitset_windex i;
414 bitset_word *srcp = ABITSET_WORDS (src);
415 bitset_word *dstp = ABITSET_WORDS (dst);
416 bitset_windex size = dst->b.csize;
417
418 for (i = 0; i < size; i++)
419 if (*srcp++ & *dstp++)
420 return false;
421
422 return true;
423 }
424
425
426 static void
abitset_and(bitset dst,bitset src1,bitset src2)427 abitset_and (bitset dst, bitset src1, bitset src2)
428 {
429 bitset_windex i;
430 bitset_word *src1p = ABITSET_WORDS (src1);
431 bitset_word *src2p = ABITSET_WORDS (src2);
432 bitset_word *dstp = ABITSET_WORDS (dst);
433 bitset_windex size = dst->b.csize;
434
435 for (i = 0; i < size; i++)
436 *dstp++ = *src1p++ & *src2p++;
437 }
438
439
440 static bool
abitset_and_cmp(bitset dst,bitset src1,bitset src2)441 abitset_and_cmp (bitset dst, bitset src1, bitset src2)
442 {
443 bitset_windex i;
444 bool changed = false;
445 bitset_word *src1p = ABITSET_WORDS (src1);
446 bitset_word *src2p = ABITSET_WORDS (src2);
447 bitset_word *dstp = ABITSET_WORDS (dst);
448 bitset_windex size = dst->b.csize;
449
450 for (i = 0; i < size; i++, dstp++)
451 {
452 bitset_word tmp = *src1p++ & *src2p++;
453
454 if (*dstp != tmp)
455 {
456 changed = true;
457 *dstp = tmp;
458 }
459 }
460 return changed;
461 }
462
463
464 static void
abitset_andn(bitset dst,bitset src1,bitset src2)465 abitset_andn (bitset dst, bitset src1, bitset src2)
466 {
467 bitset_windex i;
468 bitset_word *src1p = ABITSET_WORDS (src1);
469 bitset_word *src2p = ABITSET_WORDS (src2);
470 bitset_word *dstp = ABITSET_WORDS (dst);
471 bitset_windex size = dst->b.csize;
472
473 for (i = 0; i < size; i++)
474 *dstp++ = *src1p++ & ~(*src2p++);
475 }
476
477
478 static bool
abitset_andn_cmp(bitset dst,bitset src1,bitset src2)479 abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
480 {
481 bitset_windex i;
482 bool changed = false;
483 bitset_word *src1p = ABITSET_WORDS (src1);
484 bitset_word *src2p = ABITSET_WORDS (src2);
485 bitset_word *dstp = ABITSET_WORDS (dst);
486 bitset_windex size = dst->b.csize;
487
488 for (i = 0; i < size; i++, dstp++)
489 {
490 bitset_word tmp = *src1p++ & ~(*src2p++);
491
492 if (*dstp != tmp)
493 {
494 changed = true;
495 *dstp = tmp;
496 }
497 }
498 return changed;
499 }
500
501
502 static void
abitset_or(bitset dst,bitset src1,bitset src2)503 abitset_or (bitset dst, bitset src1, bitset src2)
504 {
505 bitset_windex i;
506 bitset_word *src1p = ABITSET_WORDS (src1);
507 bitset_word *src2p = ABITSET_WORDS (src2);
508 bitset_word *dstp = ABITSET_WORDS (dst);
509 bitset_windex size = dst->b.csize;
510
511 for (i = 0; i < size; i++)
512 *dstp++ = *src1p++ | *src2p++;
513 }
514
515
516 static bool
abitset_or_cmp(bitset dst,bitset src1,bitset src2)517 abitset_or_cmp (bitset dst, bitset src1, bitset src2)
518 {
519 bitset_windex i;
520 bool changed = false;
521 bitset_word *src1p = ABITSET_WORDS (src1);
522 bitset_word *src2p = ABITSET_WORDS (src2);
523 bitset_word *dstp = ABITSET_WORDS (dst);
524 bitset_windex size = dst->b.csize;
525
526 for (i = 0; i < size; i++, dstp++)
527 {
528 bitset_word tmp = *src1p++ | *src2p++;
529
530 if (*dstp != tmp)
531 {
532 changed = true;
533 *dstp = tmp;
534 }
535 }
536 return changed;
537 }
538
539
540 static void
abitset_xor(bitset dst,bitset src1,bitset src2)541 abitset_xor (bitset dst, bitset src1, bitset src2)
542 {
543 bitset_windex i;
544 bitset_word *src1p = ABITSET_WORDS (src1);
545 bitset_word *src2p = ABITSET_WORDS (src2);
546 bitset_word *dstp = ABITSET_WORDS (dst);
547 bitset_windex size = dst->b.csize;
548
549 for (i = 0; i < size; i++)
550 *dstp++ = *src1p++ ^ *src2p++;
551 }
552
553
554 static bool
abitset_xor_cmp(bitset dst,bitset src1,bitset src2)555 abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
556 {
557 bitset_windex i;
558 bool changed = false;
559 bitset_word *src1p = ABITSET_WORDS (src1);
560 bitset_word *src2p = ABITSET_WORDS (src2);
561 bitset_word *dstp = ABITSET_WORDS (dst);
562 bitset_windex size = dst->b.csize;
563
564 for (i = 0; i < size; i++, dstp++)
565 {
566 bitset_word tmp = *src1p++ ^ *src2p++;
567
568 if (*dstp != tmp)
569 {
570 changed = true;
571 *dstp = tmp;
572 }
573 }
574 return changed;
575 }
576
577
578 static void
abitset_and_or(bitset dst,bitset src1,bitset src2,bitset src3)579 abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
580 {
581 bitset_windex i;
582 bitset_word *src1p = ABITSET_WORDS (src1);
583 bitset_word *src2p = ABITSET_WORDS (src2);
584 bitset_word *src3p = ABITSET_WORDS (src3);
585 bitset_word *dstp = ABITSET_WORDS (dst);
586 bitset_windex size = dst->b.csize;
587
588 for (i = 0; i < size; i++)
589 *dstp++ = (*src1p++ & *src2p++) | *src3p++;
590 }
591
592
593 static bool
abitset_and_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)594 abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
595 {
596 bitset_windex i;
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 (i = 0; i < size; i++, dstp++)
605 {
606 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
607
608 if (*dstp != tmp)
609 {
610 changed = true;
611 *dstp = tmp;
612 }
613 }
614 return changed;
615 }
616
617
618 static void
abitset_andn_or(bitset dst,bitset src1,bitset src2,bitset src3)619 abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
620 {
621 bitset_windex i;
622 bitset_word *src1p = ABITSET_WORDS (src1);
623 bitset_word *src2p = ABITSET_WORDS (src2);
624 bitset_word *src3p = ABITSET_WORDS (src3);
625 bitset_word *dstp = ABITSET_WORDS (dst);
626 bitset_windex size = dst->b.csize;
627
628 for (i = 0; i < size; i++)
629 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
630 }
631
632
633 static bool
abitset_andn_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)634 abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
635 {
636 bitset_windex i;
637 bool changed = false;
638 bitset_word *src1p = ABITSET_WORDS (src1);
639 bitset_word *src2p = ABITSET_WORDS (src2);
640 bitset_word *src3p = ABITSET_WORDS (src3);
641 bitset_word *dstp = ABITSET_WORDS (dst);
642 bitset_windex size = dst->b.csize;
643
644 for (i = 0; i < size; i++, dstp++)
645 {
646 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
647
648 if (*dstp != tmp)
649 {
650 changed = true;
651 *dstp = tmp;
652 }
653 }
654 return changed;
655 }
656
657
658 static void
abitset_or_and(bitset dst,bitset src1,bitset src2,bitset src3)659 abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
660 {
661 bitset_windex i;
662 bitset_word *src1p = ABITSET_WORDS (src1);
663 bitset_word *src2p = ABITSET_WORDS (src2);
664 bitset_word *src3p = ABITSET_WORDS (src3);
665 bitset_word *dstp = ABITSET_WORDS (dst);
666 bitset_windex size = dst->b.csize;
667
668 for (i = 0; i < size; i++)
669 *dstp++ = (*src1p++ | *src2p++) & *src3p++;
670 }
671
672
673 static bool
abitset_or_and_cmp(bitset dst,bitset src1,bitset src2,bitset src3)674 abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
675 {
676 bitset_windex i;
677 bool changed = false;
678 bitset_word *src1p = ABITSET_WORDS (src1);
679 bitset_word *src2p = ABITSET_WORDS (src2);
680 bitset_word *src3p = ABITSET_WORDS (src3);
681 bitset_word *dstp = ABITSET_WORDS (dst);
682 bitset_windex size = dst->b.csize;
683
684 for (i = 0; i < size; i++, dstp++)
685 {
686 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
687
688 if (*dstp != tmp)
689 {
690 changed = true;
691 *dstp = tmp;
692 }
693 }
694 return changed;
695 }
696
697
698 static void
abitset_copy(bitset dst,bitset src)699 abitset_copy (bitset dst, bitset src)
700 {
701 if (BITSET_COMPATIBLE_ (dst, src))
702 abitset_copy1 (dst, src);
703 else
704 bitset_copy_ (dst, src);
705 }
706
707
708 /* Vector of operations for single word bitsets. */
709 struct bitset_vtable abitset_small_vtable = {
710 abitset_set,
711 abitset_reset,
712 bitset_toggle_,
713 abitset_test,
714 abitset_resize,
715 bitset_size_,
716 bitset_count_,
717 abitset_empty_p,
718 abitset_ones,
719 abitset_zero,
720 abitset_copy,
721 abitset_disjoint_p,
722 abitset_equal_p,
723 abitset_not,
724 abitset_subset_p,
725 abitset_and,
726 abitset_and_cmp,
727 abitset_andn,
728 abitset_andn_cmp,
729 abitset_or,
730 abitset_or_cmp,
731 abitset_xor,
732 abitset_xor_cmp,
733 abitset_and_or,
734 abitset_and_or_cmp,
735 abitset_andn_or,
736 abitset_andn_or_cmp,
737 abitset_or_and,
738 abitset_or_and_cmp,
739 abitset_small_list,
740 abitset_list_reverse,
741 NULL,
742 BITSET_ARRAY
743 };
744
745
746 /* Vector of operations for multiple word bitsets. */
747 struct bitset_vtable abitset_vtable = {
748 abitset_set,
749 abitset_reset,
750 bitset_toggle_,
751 abitset_test,
752 abitset_resize,
753 bitset_size_,
754 bitset_count_,
755 abitset_empty_p,
756 abitset_ones,
757 abitset_zero,
758 abitset_copy,
759 abitset_disjoint_p,
760 abitset_equal_p,
761 abitset_not,
762 abitset_subset_p,
763 abitset_and,
764 abitset_and_cmp,
765 abitset_andn,
766 abitset_andn_cmp,
767 abitset_or,
768 abitset_or_cmp,
769 abitset_xor,
770 abitset_xor_cmp,
771 abitset_and_or,
772 abitset_and_or_cmp,
773 abitset_andn_or,
774 abitset_andn_or_cmp,
775 abitset_or_and,
776 abitset_or_and_cmp,
777 abitset_list,
778 abitset_list_reverse,
779 NULL,
780 BITSET_ARRAY
781 };
782
783
784 size_t
abitset_bytes(bitset_bindex n_bits)785 abitset_bytes (bitset_bindex n_bits)
786 {
787 bitset_windex size;
788 size_t bytes;
789 size_t header_size = offsetof (union bitset_union, a.words);
790 struct bitset_align_struct { char a; union bitset_union b; };
791 size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
792
793 size = ABITSET_N_WORDS (n_bits);
794 bytes = header_size + size * sizeof (bitset_word);
795
796 /* Align the size properly for a vector of abitset objects. */
797 if (header_size % bitset_alignment != 0
798 || sizeof (bitset_word) % bitset_alignment != 0)
799 {
800 bytes += bitset_alignment - 1;
801 bytes -= bytes % bitset_alignment;
802 }
803
804 return bytes;
805 }
806
807
808 bitset
abitset_init(bitset bset,bitset_bindex n_bits)809 abitset_init (bitset bset, bitset_bindex n_bits)
810 {
811 bitset_windex size;
812
813 size = ABITSET_N_WORDS (n_bits);
814 BITSET_NBITS_ (bset) = n_bits;
815
816 /* Use optimized routines if bitset fits within a single word.
817 There is probably little merit if using caching since
818 the small bitset will always fit in the cache. */
819 if (size == 1)
820 bset->b.vtable = &abitset_small_vtable;
821 else
822 bset->b.vtable = &abitset_vtable;
823
824 bset->b.cindex = 0;
825 bset->b.csize = size;
826 bset->b.cdata = ABITSET_WORDS (bset);
827 return bset;
828 }
829