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