• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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