1 /* Variable array bitsets.
2
3 Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc.
4
5 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
19
20 #include <config.h>
21
22 #include "vbitset.h"
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 /* This file implements variable size bitsets stored as a variable
28 length array of words. Any unused bits in the last word must be
29 zero.
30
31 Note that binary or ternary operations assume that each bitset operand
32 has the same size.
33 */
34
35 static void vbitset_unused_clear (bitset);
36
37 static void vbitset_set (bitset, bitset_bindex);
38 static void vbitset_reset (bitset, bitset_bindex);
39 static bool vbitset_test (bitset, bitset_bindex);
40 static bitset_bindex vbitset_list (bitset, bitset_bindex *,
41 bitset_bindex, bitset_bindex *);
42 static bitset_bindex vbitset_list_reverse (bitset, bitset_bindex *,
43 bitset_bindex, bitset_bindex *);
44
45 #define VBITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
46 #define VBITSET_WORDS(X) ((X)->b.cdata)
47 #define VBITSET_SIZE(X) ((X)->b.csize)
48 #define VBITSET_ASIZE(X) ((X)->v.size)
49
50 #undef min
51 #undef max
52 #define min(a, b) ((a) > (b) ? (b) : (a))
53 #define max(a, b) ((a) > (b) ? (a) : (b))
54
55 static bitset_bindex
vbitset_resize(bitset src,bitset_bindex n_bits)56 vbitset_resize (bitset src, bitset_bindex n_bits)
57 {
58 bitset_windex oldsize;
59 bitset_windex newsize;
60
61 if (n_bits == BITSET_NBITS_ (src))
62 return n_bits;
63
64 oldsize = VBITSET_SIZE (src);
65 newsize = VBITSET_N_WORDS (n_bits);
66
67 if (oldsize < newsize)
68 {
69 bitset_windex size;
70
71 /* The bitset needs to grow. If we already have enough memory
72 allocated, then just zero what we need. */
73 if (newsize > VBITSET_ASIZE (src))
74 {
75 /* We need to allocate more memory. When oldsize is
76 non-zero this means that we are changing the size, so
77 grow the bitset 25% larger than requested to reduce
78 number of reallocations. */
79
80 if (oldsize == 0)
81 size = newsize;
82 else
83 size = newsize + newsize / 4;
84
85 VBITSET_WORDS (src)
86 = realloc (VBITSET_WORDS (src), size * sizeof (bitset_word));
87 VBITSET_ASIZE (src) = size;
88 }
89
90 memset (VBITSET_WORDS (src) + oldsize, 0,
91 (newsize - oldsize) * sizeof (bitset_word));
92 VBITSET_SIZE (src) = newsize;
93 }
94 else
95 {
96 /* The bitset needs to shrink. There's no point deallocating
97 the memory unless it is shrinking by a reasonable amount. */
98 if ((oldsize - newsize) >= oldsize / 2)
99 {
100 VBITSET_WORDS (src)
101 = realloc (VBITSET_WORDS (src), newsize * sizeof (bitset_word));
102 VBITSET_ASIZE (src) = newsize;
103 }
104
105 /* Need to prune any excess bits. FIXME. */
106
107 VBITSET_SIZE (src) = newsize;
108 }
109
110 BITSET_NBITS_ (src) = n_bits;
111 return n_bits;
112 }
113
114
115 /* Set bit BITNO in bitset DST. */
116 static void
vbitset_set(dst,bitno)117 vbitset_set (dst, bitno)
118 bitset dst;
119 bitset_bindex bitno;
120 {
121 bitset_windex windex = bitno / BITSET_WORD_BITS;
122
123 /* Perhaps we should abort. The user should explicitly call
124 bitset_resize since this will not catch the case when we set a
125 bit larger than the current size but smaller than the allocated
126 size. */
127 vbitset_resize (dst, bitno);
128
129 dst->b.cdata[windex - dst->b.cindex] |=
130 (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
131 }
132
133
134 /* Reset bit BITNO in bitset DST. */
135 static void
vbitset_reset(dst,bitno)136 vbitset_reset (dst, bitno)
137 bitset dst ATTRIBUTE_UNUSED;
138 bitset_bindex bitno ATTRIBUTE_UNUSED;
139 {
140 /* We must be accessing outside the cache so the bit is
141 zero anyway. */
142 }
143
144
145 /* Test bit BITNO in bitset SRC. */
146 static bool
vbitset_test(src,bitno)147 vbitset_test (src, bitno)
148 bitset src ATTRIBUTE_UNUSED;
149 bitset_bindex bitno ATTRIBUTE_UNUSED;
150 {
151 /* We must be accessing outside the cache so the bit is
152 zero anyway. */
153 return 0;
154 }
155
156
157 /* Find list of up to NUM bits set in BSET in reverse order, starting
158 from and including NEXT and store in array LIST. Return with
159 actual number of bits found and with *NEXT indicating where search
160 stopped. */
161 static bitset_bindex
vbitset_list_reverse(src,list,num,next)162 vbitset_list_reverse (src, list, num, next)
163 bitset src;
164 bitset_bindex *list;
165 bitset_bindex num;
166 bitset_bindex *next;
167 {
168 bitset_bindex bitno;
169 bitset_bindex rbitno;
170 bitset_bindex count;
171 bitset_windex windex;
172 unsigned int bitcnt;
173 bitset_bindex bitoff;
174 bitset_word *srcp = VBITSET_WORDS (src);
175 bitset_bindex n_bits = BITSET_SIZE_ (src);
176
177 rbitno = *next;
178
179 /* If num is 1, we could speed things up with a binary search
180 of the word of interest. */
181
182 if (rbitno >= n_bits)
183 return 0;
184
185 count = 0;
186
187 bitno = n_bits - (rbitno + 1);
188
189 windex = bitno / BITSET_WORD_BITS;
190 bitcnt = bitno % BITSET_WORD_BITS;
191 bitoff = windex * BITSET_WORD_BITS;
192
193 do
194 {
195 bitset_word word;
196
197 word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
198 for (; word; bitcnt--)
199 {
200 if (word & BITSET_MSB)
201 {
202 list[count++] = bitoff + bitcnt;
203 if (count >= num)
204 {
205 *next = n_bits - (bitoff + bitcnt);
206 return count;
207 }
208 }
209 word <<= 1;
210 }
211 bitoff -= BITSET_WORD_BITS;
212 bitcnt = BITSET_WORD_BITS - 1;
213 }
214 while (windex--);
215
216 *next = n_bits - (bitoff + 1);
217 return count;
218 }
219
220
221 /* Find list of up to NUM bits set in BSET starting from and including
222 *NEXT and store in array LIST. Return with actual number of bits
223 found and with *NEXT indicating where search stopped. */
224 static bitset_bindex
vbitset_list(src,list,num,next)225 vbitset_list (src, list, num, next)
226 bitset src;
227 bitset_bindex *list;
228 bitset_bindex num;
229 bitset_bindex *next;
230 {
231 bitset_bindex bitno;
232 bitset_bindex count;
233 bitset_windex windex;
234 bitset_bindex bitoff;
235 bitset_windex size = VBITSET_SIZE (src);
236 bitset_word *srcp = VBITSET_WORDS (src);
237 bitset_word word;
238
239 bitno = *next;
240
241 count = 0;
242 if (!bitno)
243 {
244 /* Many bitsets are zero, so make this common case fast. */
245 for (windex = 0; windex < size && !srcp[windex]; windex++)
246 continue;
247 if (windex >= size)
248 return 0;
249
250 /* If num is 1, we could speed things up with a binary search
251 of the current word. */
252
253 bitoff = windex * BITSET_WORD_BITS;
254 }
255 else
256 {
257 if (bitno >= BITSET_SIZE_ (src))
258 return 0;
259
260 windex = bitno / BITSET_WORD_BITS;
261 bitno = bitno % BITSET_WORD_BITS;
262
263 if (bitno)
264 {
265 /* Handle the case where we start within a word.
266 Most often, this is executed with large bitsets
267 with many set bits where we filled the array
268 on the previous call to this function. */
269
270 bitoff = windex * BITSET_WORD_BITS;
271 word = srcp[windex] >> bitno;
272 for (bitno = bitoff + bitno; word; bitno++)
273 {
274 if (word & 1)
275 {
276 list[count++] = bitno;
277 if (count >= num)
278 {
279 *next = bitno + 1;
280 return count;
281 }
282 }
283 word >>= 1;
284 }
285 windex++;
286 }
287 bitoff = windex * BITSET_WORD_BITS;
288 }
289
290 for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
291 {
292 if (!(word = srcp[windex]))
293 continue;
294
295 if ((count + BITSET_WORD_BITS) < num)
296 {
297 for (bitno = bitoff; word; bitno++)
298 {
299 if (word & 1)
300 list[count++] = bitno;
301 word >>= 1;
302 }
303 }
304 else
305 {
306 for (bitno = bitoff; word; bitno++)
307 {
308 if (word & 1)
309 {
310 list[count++] = bitno;
311 if (count >= num)
312 {
313 *next = bitno + 1;
314 return count;
315 }
316 }
317 word >>= 1;
318 }
319 }
320 }
321
322 *next = bitoff;
323 return count;
324 }
325
326
327 /* Ensure that any unused bits within the last word are clear. */
328 static inline void
vbitset_unused_clear(dst)329 vbitset_unused_clear (dst)
330 bitset dst;
331 {
332 unsigned int last_bit;
333
334 last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
335 if (last_bit)
336 VBITSET_WORDS (dst)[VBITSET_SIZE (dst) - 1] &=
337 ((bitset_word) 1 << last_bit) - 1;
338 }
339
340
341 static void
vbitset_ones(bitset dst)342 vbitset_ones (bitset dst)
343 {
344 bitset_word *dstp = VBITSET_WORDS (dst);
345 unsigned int bytes;
346
347 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
348
349 memset (dstp, -1, bytes);
350 vbitset_unused_clear (dst);
351 }
352
353
354 static void
vbitset_zero(bitset dst)355 vbitset_zero (bitset dst)
356 {
357 bitset_word *dstp = VBITSET_WORDS (dst);
358 unsigned int bytes;
359
360 bytes = sizeof (bitset_word) * VBITSET_SIZE (dst);
361
362 memset (dstp, 0, bytes);
363 }
364
365
366 static bool
vbitset_empty_p(bitset dst)367 vbitset_empty_p (bitset dst)
368 {
369 unsigned int i;
370 bitset_word *dstp = VBITSET_WORDS (dst);
371
372 for (i = 0; i < VBITSET_SIZE (dst); i++)
373 if (dstp[i])
374 return 0;
375
376 return 1;
377 }
378
379
380 static void
vbitset_copy1(bitset dst,bitset src)381 vbitset_copy1 (bitset dst, bitset src)
382 {
383 bitset_word *srcp;
384 bitset_word *dstp;
385 bitset_windex ssize;
386 bitset_windex dsize;
387
388 if (src == dst)
389 return;
390
391 vbitset_resize (dst, BITSET_SIZE_ (src));
392
393 srcp = VBITSET_WORDS (src);
394 dstp = VBITSET_WORDS (dst);
395 ssize = VBITSET_SIZE (src);
396 dsize = VBITSET_SIZE (dst);
397
398 memcpy (dstp, srcp, sizeof (bitset_word) * ssize);
399
400 memset (dstp + sizeof (bitset_word) * ssize, 0,
401 sizeof (bitset_word) * (dsize - ssize));
402 }
403
404
405 static void
vbitset_not(bitset dst,bitset src)406 vbitset_not (bitset dst, bitset src)
407 {
408 unsigned int i;
409 bitset_word *srcp;
410 bitset_word *dstp;
411 bitset_windex ssize;
412 bitset_windex dsize;
413
414 vbitset_resize (dst, BITSET_SIZE_ (src));
415
416 srcp = VBITSET_WORDS (src);
417 dstp = VBITSET_WORDS (dst);
418 ssize = VBITSET_SIZE (src);
419 dsize = VBITSET_SIZE (dst);
420
421 for (i = 0; i < ssize; i++)
422 *dstp++ = ~(*srcp++);
423
424 vbitset_unused_clear (dst);
425 memset (dstp + sizeof (bitset_word) * ssize, 0,
426 sizeof (bitset_word) * (dsize - ssize));
427 }
428
429
430 static bool
vbitset_equal_p(bitset dst,bitset src)431 vbitset_equal_p (bitset dst, bitset src)
432 {
433 unsigned int i;
434 bitset_word *srcp = VBITSET_WORDS (src);
435 bitset_word *dstp = VBITSET_WORDS (dst);
436 bitset_windex ssize = VBITSET_SIZE (src);
437 bitset_windex dsize = VBITSET_SIZE (dst);
438
439 for (i = 0; i < min (ssize, dsize); i++)
440 if (*srcp++ != *dstp++)
441 return 0;
442
443 if (ssize > dsize)
444 {
445 for (; i < ssize; i++)
446 if (*srcp++)
447 return 0;
448 }
449 else
450 {
451 for (; i < dsize; i++)
452 if (*dstp++)
453 return 0;
454 }
455
456 return 1;
457 }
458
459
460 static bool
vbitset_subset_p(bitset dst,bitset src)461 vbitset_subset_p (bitset dst, bitset src)
462 {
463 unsigned int i;
464 bitset_word *srcp = VBITSET_WORDS (src);
465 bitset_word *dstp = VBITSET_WORDS (dst);
466 bitset_windex ssize = VBITSET_SIZE (src);
467 bitset_windex dsize = VBITSET_SIZE (dst);
468
469 for (i = 0; i < min (ssize, dsize); i++, dstp++, srcp++)
470 if (*dstp != (*srcp | *dstp))
471 return 0;
472
473 if (ssize > dsize)
474 {
475 for (; i < ssize; i++)
476 if (*srcp++)
477 return 0;
478 }
479
480 return 1;
481 }
482
483
484 static bool
vbitset_disjoint_p(bitset dst,bitset src)485 vbitset_disjoint_p (bitset dst, bitset src)
486 {
487 unsigned int i;
488 bitset_word *srcp = VBITSET_WORDS (src);
489 bitset_word *dstp = VBITSET_WORDS (dst);
490 bitset_windex ssize = VBITSET_SIZE (src);
491 bitset_windex dsize = VBITSET_SIZE (dst);
492
493 for (i = 0; i < min (ssize, dsize); i++)
494 if (*srcp++ & *dstp++)
495 return 0;
496
497 return 1;
498 }
499
500
501 static void
vbitset_and(bitset dst,bitset src1,bitset src2)502 vbitset_and (bitset dst, bitset src1, bitset src2)
503 {
504 unsigned int i;
505 bitset_word *src1p;
506 bitset_word *src2p;
507 bitset_word *dstp;
508 bitset_windex ssize1;
509 bitset_windex ssize2;
510 bitset_windex dsize;
511
512 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
513
514 dsize = VBITSET_SIZE (dst);
515 ssize1 = VBITSET_SIZE (src1);
516 ssize2 = VBITSET_SIZE (src2);
517 dstp = VBITSET_WORDS (dst);
518 src1p = VBITSET_WORDS (src1);
519 src2p = VBITSET_WORDS (src2);
520
521 for (i = 0; i < min (ssize1, ssize2); i++)
522 *dstp++ = *src1p++ & *src2p++;
523
524 memset (dstp, 0, sizeof (bitset_word) * (dsize - min (ssize1, ssize2)));
525 }
526
527
528 static bool
vbitset_and_cmp(bitset dst,bitset src1,bitset src2)529 vbitset_and_cmp (bitset dst, bitset src1, bitset src2)
530 {
531 unsigned int i;
532 int changed = 0;
533 bitset_word *src1p;
534 bitset_word *src2p;
535 bitset_word *dstp;
536 bitset_windex ssize1;
537 bitset_windex ssize2;
538 bitset_windex dsize;
539
540 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
541
542 dsize = VBITSET_SIZE (dst);
543 ssize1 = VBITSET_SIZE (src1);
544 ssize2 = VBITSET_SIZE (src2);
545 dstp = VBITSET_WORDS (dst);
546 src1p = VBITSET_WORDS (src1);
547 src2p = VBITSET_WORDS (src2);
548
549 for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
550 {
551 bitset_word tmp = *src1p++ & *src2p++;
552
553 if (*dstp != tmp)
554 {
555 changed = 1;
556 *dstp = tmp;
557 }
558 }
559
560 if (ssize2 > ssize1)
561 {
562 src1p = src2p;
563 ssize1 = ssize2;
564 }
565
566 for (; i < ssize1; i++, dstp++)
567 {
568 if (*dstp != 0)
569 {
570 changed = 1;
571 *dstp = 0;
572 }
573 }
574
575 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
576
577 return changed;
578 }
579
580
581 static void
vbitset_andn(bitset dst,bitset src1,bitset src2)582 vbitset_andn (bitset dst, bitset src1, bitset src2)
583 {
584 unsigned int i;
585 bitset_word *src1p;
586 bitset_word *src2p;
587 bitset_word *dstp;
588 bitset_windex ssize1;
589 bitset_windex ssize2;
590 bitset_windex dsize;
591
592 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
593
594 dsize = VBITSET_SIZE (dst);
595 ssize1 = VBITSET_SIZE (src1);
596 ssize2 = VBITSET_SIZE (src2);
597 dstp = VBITSET_WORDS (dst);
598 src1p = VBITSET_WORDS (src1);
599 src2p = VBITSET_WORDS (src2);
600
601 for (i = 0; i < min (ssize1, ssize2); i++)
602 *dstp++ = *src1p++ & ~(*src2p++);
603
604 if (ssize2 > ssize1)
605 {
606 for (; i < ssize2; i++)
607 *dstp++ = 0;
608
609 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
610 }
611 else
612 {
613 for (; i < ssize1; i++)
614 *dstp++ = *src1p++;
615
616 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
617 }
618 }
619
620
621 static bool
vbitset_andn_cmp(bitset dst,bitset src1,bitset src2)622 vbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
623 {
624 unsigned int i;
625 int changed = 0;
626 bitset_word *src1p;
627 bitset_word *src2p;
628 bitset_word *dstp;
629 bitset_windex ssize1;
630 bitset_windex ssize2;
631 bitset_windex dsize;
632
633 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
634
635 dsize = VBITSET_SIZE (dst);
636 ssize1 = VBITSET_SIZE (src1);
637 ssize2 = VBITSET_SIZE (src2);
638 dstp = VBITSET_WORDS (dst);
639 src1p = VBITSET_WORDS (src1);
640 src2p = VBITSET_WORDS (src2);
641
642 for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
643 {
644 bitset_word tmp = *src1p++ & ~(*src2p++);
645
646 if (*dstp != tmp)
647 {
648 changed = 1;
649 *dstp = tmp;
650 }
651 }
652
653 if (ssize2 > ssize1)
654 {
655 for (; i < ssize2; i++, dstp++)
656 {
657 if (*dstp != 0)
658 {
659 changed = 1;
660 *dstp = 0;
661 }
662 }
663
664 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize2));
665 }
666 else
667 {
668 for (; i < ssize1; i++, dstp++)
669 {
670 bitset_word tmp = *src1p++;
671
672 if (*dstp != tmp)
673 {
674 changed = 1;
675 *dstp = tmp;
676 }
677 }
678
679 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
680 }
681
682 return changed;
683 }
684
685
686 static void
vbitset_or(bitset dst,bitset src1,bitset src2)687 vbitset_or (bitset dst, bitset src1, bitset src2)
688 {
689 unsigned int i;
690 bitset_word *src1p;
691 bitset_word *src2p;
692 bitset_word *dstp;
693 bitset_windex ssize1;
694 bitset_windex ssize2;
695 bitset_windex dsize;
696
697 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
698
699 dsize = VBITSET_SIZE (dst);
700 ssize1 = VBITSET_SIZE (src1);
701 ssize2 = VBITSET_SIZE (src2);
702 dstp = VBITSET_WORDS (dst);
703 src1p = VBITSET_WORDS (src1);
704 src2p = VBITSET_WORDS (src2);
705
706 for (i = 0; i < min (ssize1, ssize2); i++)
707 *dstp++ = *src1p++ | *src2p++;
708
709 if (ssize2 > ssize1)
710 {
711 src1p = src2p;
712 ssize1 = ssize2;
713 }
714
715 for (; i < ssize1; i++)
716 *dstp++ = *src1p++;
717
718 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
719 }
720
721
722 static bool
vbitset_or_cmp(bitset dst,bitset src1,bitset src2)723 vbitset_or_cmp (bitset dst, bitset src1, bitset src2)
724 {
725 unsigned int i;
726 int changed = 0;
727 bitset_word *src1p;
728 bitset_word *src2p;
729 bitset_word *dstp;
730 bitset_windex ssize1;
731 bitset_windex ssize2;
732 bitset_windex dsize;
733
734 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
735
736 dsize = VBITSET_SIZE (dst);
737 ssize1 = VBITSET_SIZE (src1);
738 ssize2 = VBITSET_SIZE (src2);
739 dstp = VBITSET_WORDS (dst);
740 src1p = VBITSET_WORDS (src1);
741 src2p = VBITSET_WORDS (src2);
742
743 for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
744 {
745 bitset_word tmp = *src1p++ | *src2p++;
746
747 if (*dstp != tmp)
748 {
749 changed = 1;
750 *dstp = tmp;
751 }
752 }
753
754 if (ssize2 > ssize1)
755 {
756 src1p = src2p;
757 ssize1 = ssize2;
758 }
759
760 for (; i < ssize1; i++, dstp++)
761 {
762 bitset_word tmp = *src1p++;
763
764 if (*dstp != tmp)
765 {
766 changed = 1;
767 *dstp = tmp;
768 }
769 }
770
771 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
772
773 return changed;
774 }
775
776
777 static void
vbitset_xor(bitset dst,bitset src1,bitset src2)778 vbitset_xor (bitset dst, bitset src1, bitset src2)
779 {
780 unsigned int i;
781 bitset_word *src1p;
782 bitset_word *src2p;
783 bitset_word *dstp;
784 bitset_windex ssize1;
785 bitset_windex ssize2;
786 bitset_windex dsize;
787
788 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
789
790 dsize = VBITSET_SIZE (dst);
791 ssize1 = VBITSET_SIZE (src1);
792 ssize2 = VBITSET_SIZE (src2);
793 dstp = VBITSET_WORDS (dst);
794 src1p = VBITSET_WORDS (src1);
795 src2p = VBITSET_WORDS (src2);
796
797 for (i = 0; i < min (ssize1, ssize2); i++)
798 *dstp++ = *src1p++ ^ *src2p++;
799
800 if (ssize2 > ssize1)
801 {
802 src1p = src2p;
803 ssize1 = ssize2;
804 }
805
806 for (; i < ssize1; i++)
807 *dstp++ = *src1p++;
808
809 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
810 }
811
812
813 static bool
vbitset_xor_cmp(bitset dst,bitset src1,bitset src2)814 vbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
815 {
816 unsigned int i;
817 int changed = 0;
818 bitset_word *src1p;
819 bitset_word *src2p;
820 bitset_word *dstp;
821 bitset_windex ssize1;
822 bitset_windex ssize2;
823 bitset_windex dsize;
824
825 vbitset_resize (dst, max (BITSET_SIZE_ (src1), BITSET_SIZE_ (src2)));
826
827 dsize = VBITSET_SIZE (dst);
828 ssize1 = VBITSET_SIZE (src1);
829 ssize2 = VBITSET_SIZE (src2);
830 dstp = VBITSET_WORDS (dst);
831 src1p = VBITSET_WORDS (src1);
832 src2p = VBITSET_WORDS (src2);
833
834 for (i = 0; i < min (ssize1, ssize2); i++, dstp++)
835 {
836 bitset_word tmp = *src1p++ ^ *src2p++;
837
838 if (*dstp != tmp)
839 {
840 changed = 1;
841 *dstp = tmp;
842 }
843 }
844
845 if (ssize2 > ssize1)
846 {
847 src1p = src2p;
848 ssize1 = ssize2;
849 }
850
851 for (; i < ssize1; i++, dstp++)
852 {
853 bitset_word tmp = *src1p++;
854
855 if (*dstp != tmp)
856 {
857 changed = 1;
858 *dstp = tmp;
859 }
860 }
861
862 memset (dstp, 0, sizeof (bitset_word) * (dsize - ssize1));
863
864 return changed;
865 }
866
867
868 /* FIXME, these operations need fixing for different size
869 bitsets. */
870
871 static void
vbitset_and_or(bitset dst,bitset src1,bitset src2,bitset src3)872 vbitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
873 {
874 unsigned int i;
875 bitset_word *src1p;
876 bitset_word *src2p;
877 bitset_word *src3p;
878 bitset_word *dstp;
879 bitset_windex size;
880
881 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
882 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
883 {
884 bitset_and_or_ (dst, src1, src2, src3);
885 return;
886 }
887
888 vbitset_resize (dst, BITSET_NBITS_ (src1));
889
890 src1p = VBITSET_WORDS (src1);
891 src2p = VBITSET_WORDS (src2);
892 src3p = VBITSET_WORDS (src3);
893 dstp = VBITSET_WORDS (dst);
894 size = VBITSET_SIZE (dst);
895
896 for (i = 0; i < size; i++)
897 *dstp++ = (*src1p++ & *src2p++) | *src3p++;
898 }
899
900
901 static bool
vbitset_and_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)902 vbitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
903 {
904 unsigned int i;
905 int changed = 0;
906 bitset_word *src1p;
907 bitset_word *src2p;
908 bitset_word *src3p;
909 bitset_word *dstp;
910 bitset_windex size;
911
912 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
913 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
914 return bitset_and_or_cmp_ (dst, src1, src2, src3);
915
916 vbitset_resize (dst, BITSET_NBITS_ (src1));
917
918 src1p = VBITSET_WORDS (src1);
919 src2p = VBITSET_WORDS (src2);
920 src3p = VBITSET_WORDS (src3);
921 dstp = VBITSET_WORDS (dst);
922 size = VBITSET_SIZE (dst);
923
924 for (i = 0; i < size; i++, dstp++)
925 {
926 bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
927
928 if (*dstp != tmp)
929 {
930 changed = 1;
931 *dstp = tmp;
932 }
933 }
934 return changed;
935 }
936
937
938 static void
vbitset_andn_or(bitset dst,bitset src1,bitset src2,bitset src3)939 vbitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
940 {
941 unsigned int i;
942 bitset_word *src1p;
943 bitset_word *src2p;
944 bitset_word *src3p;
945 bitset_word *dstp;
946 bitset_windex size;
947
948 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
949 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
950 {
951 bitset_andn_or_ (dst, src1, src2, src3);
952 return;
953 }
954
955 vbitset_resize (dst, BITSET_NBITS_ (src1));
956
957 src1p = VBITSET_WORDS (src1);
958 src2p = VBITSET_WORDS (src2);
959 src3p = VBITSET_WORDS (src3);
960 dstp = VBITSET_WORDS (dst);
961 size = VBITSET_SIZE (dst);
962
963 for (i = 0; i < size; i++)
964 *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
965 }
966
967
968 static bool
vbitset_andn_or_cmp(bitset dst,bitset src1,bitset src2,bitset src3)969 vbitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
970 {
971 unsigned int i;
972 int changed = 0;
973 bitset_word *src1p;
974 bitset_word *src2p;
975 bitset_word *src3p;
976 bitset_word *dstp;
977 bitset_windex size;
978
979 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
980 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
981 return bitset_andn_or_cmp_ (dst, src1, src2, src3);
982
983 vbitset_resize (dst, BITSET_NBITS_ (src1));
984
985 src1p = VBITSET_WORDS (src1);
986 src2p = VBITSET_WORDS (src2);
987 src3p = VBITSET_WORDS (src3);
988 dstp = VBITSET_WORDS (dst);
989 size = VBITSET_SIZE (dst);
990
991 for (i = 0; i < size; i++, dstp++)
992 {
993 bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
994
995 if (*dstp != tmp)
996 {
997 changed = 1;
998 *dstp = tmp;
999 }
1000 }
1001 return changed;
1002 }
1003
1004
1005 static void
vbitset_or_and(bitset dst,bitset src1,bitset src2,bitset src3)1006 vbitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
1007 {
1008 unsigned int i;
1009 bitset_word *src1p;
1010 bitset_word *src2p;
1011 bitset_word *src3p;
1012 bitset_word *dstp;
1013 bitset_windex size;
1014
1015 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1016 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1017 {
1018 bitset_or_and_ (dst, src1, src2, src3);
1019 return;
1020 }
1021
1022 vbitset_resize (dst, BITSET_NBITS_ (src1));
1023
1024 src1p = VBITSET_WORDS (src1);
1025 src2p = VBITSET_WORDS (src2);
1026 src3p = VBITSET_WORDS (src3);
1027 dstp = VBITSET_WORDS (dst);
1028 size = VBITSET_SIZE (dst);
1029
1030 for (i = 0; i < size; i++)
1031 *dstp++ = (*src1p++ | *src2p++) & *src3p++;
1032 }
1033
1034
1035 static bool
vbitset_or_and_cmp(bitset dst,bitset src1,bitset src2,bitset src3)1036 vbitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
1037 {
1038 unsigned int i;
1039 int changed = 0;
1040 bitset_word *src1p;
1041 bitset_word *src2p;
1042 bitset_word *src3p;
1043 bitset_word *dstp;
1044 bitset_windex size;
1045
1046 if (BITSET_NBITS_ (src1) != BITSET_NBITS_ (src2)
1047 || BITSET_NBITS_ (src1) != BITSET_NBITS_ (src3))
1048 return bitset_or_and_cmp_ (dst, src1, src2, src3);
1049
1050 vbitset_resize (dst, BITSET_NBITS_ (src1));
1051
1052 src1p = VBITSET_WORDS (src1);
1053 src2p = VBITSET_WORDS (src2);
1054 src3p = VBITSET_WORDS (src3);
1055 dstp = VBITSET_WORDS (dst);
1056 size = VBITSET_SIZE (dst);
1057
1058 for (i = 0; i < size; i++, dstp++)
1059 {
1060 bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
1061
1062 if (*dstp != tmp)
1063 {
1064 changed = 1;
1065 *dstp = tmp;
1066 }
1067 }
1068 return changed;
1069 }
1070
1071
1072 static void
vbitset_copy(bitset dst,bitset src)1073 vbitset_copy (bitset dst, bitset src)
1074 {
1075 if (BITSET_COMPATIBLE_ (dst, src))
1076 vbitset_copy1 (dst, src);
1077 else
1078 bitset_copy_ (dst, src);
1079 }
1080
1081
1082 /* Vector of operations for multiple word bitsets. */
1083 struct bitset_vtable vbitset_vtable = {
1084 vbitset_set,
1085 vbitset_reset,
1086 bitset_toggle_,
1087 vbitset_test,
1088 vbitset_resize,
1089 bitset_size_,
1090 bitset_count_,
1091 vbitset_empty_p,
1092 vbitset_ones,
1093 vbitset_zero,
1094 vbitset_copy,
1095 vbitset_disjoint_p,
1096 vbitset_equal_p,
1097 vbitset_not,
1098 vbitset_subset_p,
1099 vbitset_and,
1100 vbitset_and_cmp,
1101 vbitset_andn,
1102 vbitset_andn_cmp,
1103 vbitset_or,
1104 vbitset_or_cmp,
1105 vbitset_xor,
1106 vbitset_xor_cmp,
1107 vbitset_and_or,
1108 vbitset_and_or_cmp,
1109 vbitset_andn_or,
1110 vbitset_andn_or_cmp,
1111 vbitset_or_and,
1112 vbitset_or_and_cmp,
1113 vbitset_list,
1114 vbitset_list_reverse,
1115 NULL,
1116 BITSET_VARRAY
1117 };
1118
1119
1120 size_t
vbitset_bytes(n_bits)1121 vbitset_bytes (n_bits)
1122 bitset_bindex n_bits ATTRIBUTE_UNUSED;
1123 {
1124 return sizeof (struct vbitset_struct);
1125 }
1126
1127
1128 bitset
vbitset_init(bset,n_bits)1129 vbitset_init (bset, n_bits)
1130 bitset bset;
1131 bitset_bindex n_bits;
1132 {
1133 bset->b.vtable = &vbitset_vtable;
1134
1135 bset->b.cindex = 0;
1136
1137 VBITSET_SIZE (bset) = 0;
1138 vbitset_resize (bset, n_bits);
1139 return bset;
1140 }
1141