1/* Variable array bitsets.
2   Copyright (C) 2002, 2003, 2004, 2005, 2006 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 Foundation,
17   Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.  */
18
19#ifdef HAVE_CONFIG_H
20# include <config.h>
21#endif
22
23#include "vbitset.h"
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
35static void vbitset_unused_clear (bitset);
36
37static void vbitset_set (bitset, bitset_bindex);
38static void vbitset_reset (bitset, bitset_bindex);
39static bool vbitset_test (bitset, bitset_bindex);
40static bitset_bindex vbitset_list (bitset, bitset_bindex *,
41				   bitset_bindex, bitset_bindex *);
42static 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
55static bitset_bindex
56vbitset_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.  */
116static void
117vbitset_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.  */
135static void
136vbitset_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.  */
146static bool
147vbitset_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.  */
161static bitset_bindex
162vbitset_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.  */
224static bitset_bindex
225vbitset_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.  */
328static inline void
329vbitset_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
341static void
342vbitset_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
354static void
355vbitset_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
366static bool
367vbitset_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
380static void
381vbitset_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
405static void
406vbitset_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
430static bool
431vbitset_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
460static bool
461vbitset_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
484static bool
485vbitset_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
501static void
502vbitset_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
528static bool
529vbitset_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
581static void
582vbitset_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
621static bool
622vbitset_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
686static void
687vbitset_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
722static bool
723vbitset_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
777static void
778vbitset_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
813static bool
814vbitset_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
871static void
872vbitset_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
901static bool
902vbitset_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
938static void
939vbitset_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
968static bool
969vbitset_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
1005static void
1006vbitset_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
1035static bool
1036vbitset_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
1072static void
1073vbitset_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.  */
1083struct 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
1120size_t
1121vbitset_bytes (n_bits)
1122     bitset_bindex n_bits ATTRIBUTE_UNUSED;
1123{
1124  return sizeof (struct vbitset_struct);
1125}
1126
1127
1128bitset
1129vbitset_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