3 Copyright (C) 2002-2003, 2006, 2009-2011 Free Software Foundation,
6 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
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.
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.
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/>. */
28 /* This file implements fixed size bitsets stored as an array
29 of words. Any unused bits in the last word must be zero. */
31 #define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
32 #define ABITSET_WORDS(X) ((X)->a.words)
36 abitset_resize (bitset src
, bitset_bindex size
)
38 /* These bitsets have a fixed size. */
39 if (BITSET_SIZE_ (src
) != size
)
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. */
49 abitset_small_list (bitset src
, bitset_bindex
*list
,
50 bitset_bindex num
, bitset_bindex
*next
)
57 word
= ABITSET_WORDS (src
)[0];
59 /* Short circuit common case. */
63 size
= BITSET_SIZE_ (src
);
70 /* If num is 1, we could speed things up with a binary search
71 of the word of interest. */
73 if (num
>= BITSET_WORD_BITS
)
75 for (count
= 0; word
; bitno
++)
78 list
[count
++] = bitno
;
84 for (count
= 0; word
; bitno
++)
88 list
[count
++] = bitno
;
104 /* Set bit BITNO in bitset DST. */
106 abitset_set (bitset dst ATTRIBUTE_UNUSED
, bitset_bindex bitno ATTRIBUTE_UNUSED
)
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. */
115 /* Reset bit BITNO in bitset DST. */
117 abitset_reset (bitset dst ATTRIBUTE_UNUSED
,
118 bitset_bindex bitno ATTRIBUTE_UNUSED
)
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. */
126 /* Test bit BITNO in bitset SRC. */
128 abitset_test (bitset src ATTRIBUTE_UNUSED
,
129 bitset_bindex bitno ATTRIBUTE_UNUSED
)
131 /* This should never occur for abitsets since we should always
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
142 abitset_list_reverse (bitset src
, bitset_bindex
*list
,
143 bitset_bindex num
, bitset_bindex
*next
)
146 bitset_bindex rbitno
;
148 bitset_windex windex
;
150 bitset_bindex bitoff
;
151 bitset_word
*srcp
= ABITSET_WORDS (src
);
152 bitset_bindex n_bits
= BITSET_SIZE_ (src
);
156 /* If num is 1, we could speed things up with a binary search
157 of the word of interest. */
159 if (rbitno
>= n_bits
)
164 bitno
= n_bits
- (rbitno
+ 1);
166 windex
= bitno
/ BITSET_WORD_BITS
;
167 bitcnt
= bitno
% BITSET_WORD_BITS
;
168 bitoff
= windex
* BITSET_WORD_BITS
;
174 word
= srcp
[windex
] << (BITSET_WORD_BITS
- 1 - bitcnt
);
175 for (; word
; bitcnt
--)
177 if (word
& BITSET_MSB
)
179 list
[count
++] = bitoff
+ bitcnt
;
182 *next
= n_bits
- (bitoff
+ bitcnt
);
188 bitoff
-= BITSET_WORD_BITS
;
189 bitcnt
= BITSET_WORD_BITS
- 1;
193 *next
= n_bits
- (bitoff
+ 1);
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. */
202 abitset_list (bitset src
, bitset_bindex
*list
,
203 bitset_bindex num
, bitset_bindex
*next
)
207 bitset_windex windex
;
208 bitset_bindex bitoff
;
209 bitset_windex size
= src
->b
.csize
;
210 bitset_word
*srcp
= ABITSET_WORDS (src
);
218 /* Many bitsets are zero, so make this common case fast. */
219 for (windex
= 0; windex
< size
&& !srcp
[windex
]; windex
++)
224 /* If num is 1, we could speed things up with a binary search
225 of the current word. */
227 bitoff
= windex
* BITSET_WORD_BITS
;
231 if (bitno
>= BITSET_SIZE_ (src
))
234 windex
= bitno
/ BITSET_WORD_BITS
;
235 bitno
= bitno
% BITSET_WORD_BITS
;
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. */
244 bitoff
= windex
* BITSET_WORD_BITS
;
245 word
= srcp
[windex
] >> bitno
;
246 for (bitno
= bitoff
+ bitno
; word
; bitno
++)
250 list
[count
++] = bitno
;
261 bitoff
= windex
* BITSET_WORD_BITS
;
264 for (; windex
< size
; windex
++, bitoff
+= BITSET_WORD_BITS
)
266 if (!(word
= srcp
[windex
]))
269 if ((count
+ BITSET_WORD_BITS
) < num
)
271 for (bitno
= bitoff
; word
; bitno
++)
274 list
[count
++] = bitno
;
280 for (bitno
= bitoff
; word
; bitno
++)
284 list
[count
++] = bitno
;
301 /* Ensure that any unused bits within the last word are clear. */
303 abitset_unused_clear (bitset dst
)
305 unsigned int last_bit
;
307 last_bit
= BITSET_SIZE_ (dst
) % BITSET_WORD_BITS
;
309 ABITSET_WORDS (dst
)[dst
->b
.csize
- 1] &=
310 ((bitset_word
) 1 << last_bit
) - 1;
315 abitset_ones (bitset dst
)
317 bitset_word
*dstp
= ABITSET_WORDS (dst
);
320 bytes
= sizeof (bitset_word
) * dst
->b
.csize
;
322 memset (dstp
, -1, bytes
);
323 abitset_unused_clear (dst
);
328 abitset_zero (bitset dst
)
330 bitset_word
*dstp
= ABITSET_WORDS (dst
);
333 bytes
= sizeof (bitset_word
) * dst
->b
.csize
;
335 memset (dstp
, 0, bytes
);
340 abitset_empty_p (bitset dst
)
343 bitset_word
*dstp
= ABITSET_WORDS (dst
);
345 for (i
= 0; i
< dst
->b
.csize
; i
++)
354 abitset_copy1 (bitset dst
, bitset src
)
356 bitset_word
*srcp
= ABITSET_WORDS (src
);
357 bitset_word
*dstp
= ABITSET_WORDS (dst
);
358 bitset_windex size
= dst
->b
.csize
;
362 memcpy (dstp
, srcp
, sizeof (bitset_word
) * size
);
367 abitset_not (bitset dst
, bitset src
)
370 bitset_word
*srcp
= ABITSET_WORDS (src
);
371 bitset_word
*dstp
= ABITSET_WORDS (dst
);
372 bitset_windex size
= dst
->b
.csize
;
374 for (i
= 0; i
< size
; i
++)
375 *dstp
++ = ~(*srcp
++);
376 abitset_unused_clear (dst
);
381 abitset_equal_p (bitset dst
, bitset src
)
384 bitset_word
*srcp
= ABITSET_WORDS (src
);
385 bitset_word
*dstp
= ABITSET_WORDS (dst
);
386 bitset_windex size
= dst
->b
.csize
;
388 for (i
= 0; i
< size
; i
++)
389 if (*srcp
++ != *dstp
++)
396 abitset_subset_p (bitset dst
, bitset src
)
399 bitset_word
*srcp
= ABITSET_WORDS (src
);
400 bitset_word
*dstp
= ABITSET_WORDS (dst
);
401 bitset_windex size
= dst
->b
.csize
;
403 for (i
= 0; i
< size
; i
++, dstp
++, srcp
++)
404 if (*dstp
!= (*srcp
| *dstp
))
411 abitset_disjoint_p (bitset dst
, bitset src
)
414 bitset_word
*srcp
= ABITSET_WORDS (src
);
415 bitset_word
*dstp
= ABITSET_WORDS (dst
);
416 bitset_windex size
= dst
->b
.csize
;
418 for (i
= 0; i
< size
; i
++)
419 if (*srcp
++ & *dstp
++)
427 abitset_and (bitset dst
, bitset src1
, bitset src2
)
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
;
435 for (i
= 0; i
< size
; i
++)
436 *dstp
++ = *src1p
++ & *src2p
++;
441 abitset_and_cmp (bitset dst
, bitset src1
, bitset src2
)
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
;
450 for (i
= 0; i
< size
; i
++, dstp
++)
452 bitset_word tmp
= *src1p
++ & *src2p
++;
465 abitset_andn (bitset dst
, bitset src1
, bitset src2
)
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
;
473 for (i
= 0; i
< size
; i
++)
474 *dstp
++ = *src1p
++ & ~(*src2p
++);
479 abitset_andn_cmp (bitset dst
, bitset src1
, bitset src2
)
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
;
488 for (i
= 0; i
< size
; i
++, dstp
++)
490 bitset_word tmp
= *src1p
++ & ~(*src2p
++);
503 abitset_or (bitset dst
, bitset src1
, bitset src2
)
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
;
511 for (i
= 0; i
< size
; i
++)
512 *dstp
++ = *src1p
++ | *src2p
++;
517 abitset_or_cmp (bitset dst
, bitset src1
, bitset src2
)
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
;
526 for (i
= 0; i
< size
; i
++, dstp
++)
528 bitset_word tmp
= *src1p
++ | *src2p
++;
541 abitset_xor (bitset dst
, bitset src1
, bitset src2
)
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
;
549 for (i
= 0; i
< size
; i
++)
550 *dstp
++ = *src1p
++ ^ *src2p
++;
555 abitset_xor_cmp (bitset dst
, bitset src1
, bitset src2
)
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
;
564 for (i
= 0; i
< size
; i
++, dstp
++)
566 bitset_word tmp
= *src1p
++ ^ *src2p
++;
579 abitset_and_or (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
588 for (i
= 0; i
< size
; i
++)
589 *dstp
++ = (*src1p
++ & *src2p
++) | *src3p
++;
594 abitset_and_or_cmp (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
604 for (i
= 0; i
< size
; i
++, dstp
++)
606 bitset_word tmp
= (*src1p
++ & *src2p
++) | *src3p
++;
619 abitset_andn_or (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
628 for (i
= 0; i
< size
; i
++)
629 *dstp
++ = (*src1p
++ & ~(*src2p
++)) | *src3p
++;
634 abitset_andn_or_cmp (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
644 for (i
= 0; i
< size
; i
++, dstp
++)
646 bitset_word tmp
= (*src1p
++ & ~(*src2p
++)) | *src3p
++;
659 abitset_or_and (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
668 for (i
= 0; i
< size
; i
++)
669 *dstp
++ = (*src1p
++ | *src2p
++) & *src3p
++;
674 abitset_or_and_cmp (bitset dst
, bitset src1
, bitset src2
, bitset src3
)
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
;
684 for (i
= 0; i
< size
; i
++, dstp
++)
686 bitset_word tmp
= (*src1p
++ | *src2p
++) & *src3p
++;
699 abitset_copy (bitset dst
, bitset src
)
701 if (BITSET_COMPATIBLE_ (dst
, src
))
702 abitset_copy1 (dst
, src
);
704 bitset_copy_ (dst
, src
);
708 /* Vector of operations for single word bitsets. */
709 struct bitset_vtable abitset_small_vtable
= {
740 abitset_list_reverse
,
746 /* Vector of operations for multiple word bitsets. */
747 struct bitset_vtable abitset_vtable
= {
778 abitset_list_reverse
,
785 abitset_bytes (bitset_bindex n_bits
)
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
);
793 size
= ABITSET_N_WORDS (n_bits
);
794 bytes
= header_size
+ size
* sizeof (bitset_word
);
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)
800 bytes
+= bitset_alignment
- 1;
801 bytes
-= bytes
% bitset_alignment
;
809 abitset_init (bitset bset
, bitset_bindex n_bits
)
813 size
= ABITSET_N_WORDS (n_bits
);
814 BITSET_NBITS_ (bset
) = n_bits
;
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. */
820 bset
->b
.vtable
= &abitset_small_vtable
;
822 bset
->b
.vtable
= &abitset_vtable
;
825 bset
->b
.csize
= size
;
826 bset
->b
.cdata
= ABITSET_WORDS (bset
);