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