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