1/* Array bitsets.
2
3   Copyright (C) 2002-2003, 2006, 2009-2012 Free Software Foundation,
4   Inc.
5
6   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
7
8   This program is free software: you can redistribute it and/or modify
9   it under the terms of the GNU General Public License as published by
10   the Free Software Foundation, either version 3 of the License, or
11   (at your option) any later version.
12
13   This program is distributed in the hope that it will be useful,
14   but WITHOUT ANY WARRANTY; without even the implied warranty of
15   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16   GNU General Public License for more details.
17
18   You should have received a copy of the GNU General Public License
19   along with this program.  If not, see <http://www.gnu.org/licenses/>.  */
20
21#include <config.h>
22
23#include "abitset.h"
24#include <stddef.h>
25#include <stdlib.h>
26#include <string.h>
27
28/* This file implements fixed size bitsets stored as an array
29   of words.  Any unused bits in the last word must be zero.  */
30
31#define ABITSET_N_WORDS(N) (((N) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS)
32#define ABITSET_WORDS(X) ((X)->a.words)
33
34
35static bitset_bindex
36abitset_resize (bitset src, bitset_bindex size)
37{
38    /* These bitsets have a fixed size.  */
39    if (BITSET_SIZE_ (src) != size)
40      abort ();
41
42    return size;
43}
44
45/* Find list of up to NUM bits set in BSET starting from and including
46 *NEXT and store in array LIST.  Return with actual number of bits
47 found and with *NEXT indicating where search stopped.  */
48static bitset_bindex
49abitset_small_list (bitset src, bitset_bindex *list,
50		    bitset_bindex num, bitset_bindex *next)
51{
52  bitset_bindex bitno;
53  bitset_bindex count;
54  bitset_windex size;
55  bitset_word word;
56
57  word = ABITSET_WORDS (src)[0];
58
59  /* Short circuit common case.  */
60  if (!word)
61    return 0;
62
63  size = BITSET_SIZE_ (src);
64  bitno = *next;
65  if (bitno >= size)
66    return 0;
67
68  word >>= bitno;
69
70  /* If num is 1, we could speed things up with a binary search
71     of the word of interest.  */
72
73  if (num >= BITSET_WORD_BITS)
74    {
75      for (count = 0; word; bitno++)
76	{
77	  if (word & 1)
78	    list[count++] = bitno;
79	  word >>= 1;
80	}
81    }
82  else
83    {
84      for (count = 0; word; bitno++)
85	{
86	  if (word & 1)
87	    {
88	      list[count++] = bitno;
89	      if (count >= num)
90		{
91		  bitno++;
92		  break;
93		}
94	    }
95	  word >>= 1;
96	}
97    }
98
99  *next = bitno;
100  return count;
101}
102
103
104/* Set bit BITNO in bitset DST.  */
105static void
106abitset_set (bitset dst ATTRIBUTE_UNUSED, bitset_bindex bitno ATTRIBUTE_UNUSED)
107{
108  /* This should never occur for abitsets since we should always hit
109     the cache.  It is likely someone is trying to access outside the
110     bounds of the bitset.  */
111  abort ();
112}
113
114
115/* Reset bit BITNO in bitset DST.  */
116static void
117abitset_reset (bitset dst ATTRIBUTE_UNUSED,
118	       bitset_bindex bitno ATTRIBUTE_UNUSED)
119{
120  /* This should never occur for abitsets since we should always hit
121     the cache.  It is likely someone is trying to access outside the
122     bounds of the bitset.  Since the bit is zero anyway, let it pass.  */
123}
124
125
126/* Test bit BITNO in bitset SRC.  */
127static bool
128abitset_test (bitset src ATTRIBUTE_UNUSED,
129	      bitset_bindex bitno ATTRIBUTE_UNUSED)
130{
131  /* This should never occur for abitsets since we should always
132     hit the cache.  */
133  return false;
134}
135
136
137/* Find list of up to NUM bits set in BSET in reverse order, starting
138   from and including NEXT and store in array LIST.  Return with
139   actual number of bits found and with *NEXT indicating where search
140   stopped.  */
141static bitset_bindex
142abitset_list_reverse (bitset src, bitset_bindex *list,
143		      bitset_bindex num, bitset_bindex *next)
144{
145  bitset_bindex bitno;
146  bitset_bindex rbitno;
147  bitset_bindex count;
148  bitset_windex windex;
149  unsigned int bitcnt;
150  bitset_bindex bitoff;
151  bitset_word *srcp = ABITSET_WORDS (src);
152  bitset_bindex n_bits = BITSET_SIZE_ (src);
153
154  rbitno = *next;
155
156  /* If num is 1, we could speed things up with a binary search
157     of the word of interest.  */
158
159  if (rbitno >= n_bits)
160    return 0;
161
162  count = 0;
163
164  bitno = n_bits - (rbitno + 1);
165
166  windex = bitno / BITSET_WORD_BITS;
167  bitcnt = bitno % BITSET_WORD_BITS;
168  bitoff = windex * BITSET_WORD_BITS;
169
170  do
171    {
172      bitset_word word;
173
174      word = srcp[windex] << (BITSET_WORD_BITS - 1 - bitcnt);
175      for (; word; bitcnt--)
176	{
177	  if (word & BITSET_MSB)
178	    {
179	      list[count++] = bitoff + bitcnt;
180	      if (count >= num)
181		{
182		  *next = n_bits - (bitoff + bitcnt);
183		  return count;
184		}
185	    }
186	  word <<= 1;
187	}
188      bitoff -= BITSET_WORD_BITS;
189      bitcnt = BITSET_WORD_BITS - 1;
190    }
191  while (windex--);
192
193  *next = n_bits - (bitoff + 1);
194  return count;
195}
196
197
198/* Find list of up to NUM bits set in BSET starting from and including
199 *NEXT and store in array LIST.  Return with actual number of bits
200 found and with *NEXT indicating where search stopped.  */
201static bitset_bindex
202abitset_list (bitset src, bitset_bindex *list,
203	      bitset_bindex num, bitset_bindex *next)
204{
205  bitset_bindex bitno;
206  bitset_bindex count;
207  bitset_windex windex;
208  bitset_bindex bitoff;
209  bitset_windex size = src->b.csize;
210  bitset_word *srcp = ABITSET_WORDS (src);
211  bitset_word word;
212
213  bitno = *next;
214
215  count = 0;
216  if (!bitno)
217    {
218      /* Many bitsets are zero, so make this common case fast.  */
219      for (windex = 0; windex < size && !srcp[windex]; windex++)
220	continue;
221      if (windex >= size)
222	return 0;
223
224      /* If num is 1, we could speed things up with a binary search
225	 of the current word.  */
226
227      bitoff = windex * BITSET_WORD_BITS;
228    }
229  else
230    {
231      if (bitno >= BITSET_SIZE_ (src))
232	return 0;
233
234      windex = bitno / BITSET_WORD_BITS;
235      bitno = bitno % BITSET_WORD_BITS;
236
237      if (bitno)
238	{
239	  /* Handle the case where we start within a word.
240	     Most often, this is executed with large bitsets
241	     with many set bits where we filled the array
242	     on the previous call to this function.  */
243
244	  bitoff = windex * BITSET_WORD_BITS;
245	  word = srcp[windex] >> bitno;
246	  for (bitno = bitoff + bitno; word; bitno++)
247	    {
248	      if (word & 1)
249		{
250		  list[count++] = bitno;
251		  if (count >= num)
252		    {
253		      *next = bitno + 1;
254		      return count;
255		    }
256		}
257	      word >>= 1;
258	    }
259	  windex++;
260	}
261      bitoff = windex * BITSET_WORD_BITS;
262    }
263
264  for (; windex < size; windex++, bitoff += BITSET_WORD_BITS)
265    {
266      if (!(word = srcp[windex]))
267	continue;
268
269      if ((count + BITSET_WORD_BITS) < num)
270	{
271	  for (bitno = bitoff; word; bitno++)
272	    {
273	      if (word & 1)
274		list[count++] = bitno;
275	      word >>= 1;
276	    }
277	}
278      else
279	{
280	  for (bitno = bitoff; word; bitno++)
281	    {
282	      if (word & 1)
283		{
284		  list[count++] = bitno;
285		  if (count >= num)
286		    {
287		      *next = bitno + 1;
288		      return count;
289		    }
290		}
291	      word >>= 1;
292	    }
293	}
294    }
295
296  *next = bitoff;
297  return count;
298}
299
300
301/* Ensure that any unused bits within the last word are clear.  */
302static inline void
303abitset_unused_clear (bitset dst)
304{
305  unsigned int last_bit;
306
307  last_bit = BITSET_SIZE_ (dst) % BITSET_WORD_BITS;
308  if (last_bit)
309    ABITSET_WORDS (dst)[dst->b.csize - 1] &=
310      ((bitset_word) 1 << last_bit) - 1;
311}
312
313
314static void
315abitset_ones (bitset dst)
316{
317  bitset_word *dstp = ABITSET_WORDS (dst);
318  size_t bytes;
319
320  bytes = sizeof (bitset_word) * dst->b.csize;
321
322  memset (dstp, -1, bytes);
323  abitset_unused_clear (dst);
324}
325
326
327static void
328abitset_zero (bitset dst)
329{
330  bitset_word *dstp = ABITSET_WORDS (dst);
331  size_t bytes;
332
333  bytes = sizeof (bitset_word) * dst->b.csize;
334
335  memset (dstp, 0, bytes);
336}
337
338
339static bool
340abitset_empty_p (bitset dst)
341{
342  bitset_windex i;
343  bitset_word *dstp = ABITSET_WORDS (dst);
344
345  for (i = 0; i < dst->b.csize; i++)
346    if (dstp[i])
347      return false;
348
349  return true;
350}
351
352
353static void
354abitset_copy1 (bitset dst, bitset src)
355{
356  bitset_word *srcp = ABITSET_WORDS (src);
357  bitset_word *dstp = ABITSET_WORDS (dst);
358  bitset_windex size = dst->b.csize;
359
360  if (srcp == dstp)
361      return;
362  memcpy (dstp, srcp, sizeof (bitset_word) * size);
363}
364
365
366static void
367abitset_not (bitset dst, bitset src)
368{
369  bitset_windex i;
370  bitset_word *srcp = ABITSET_WORDS (src);
371  bitset_word *dstp = ABITSET_WORDS (dst);
372  bitset_windex size = dst->b.csize;
373
374  for (i = 0; i < size; i++)
375      *dstp++ = ~(*srcp++);
376  abitset_unused_clear (dst);
377}
378
379
380static bool
381abitset_equal_p (bitset dst, bitset src)
382{
383  bitset_windex i;
384  bitset_word *srcp = ABITSET_WORDS (src);
385  bitset_word *dstp = ABITSET_WORDS (dst);
386  bitset_windex size = dst->b.csize;
387
388  for (i = 0; i < size; i++)
389      if (*srcp++ != *dstp++)
390	  return false;
391  return true;
392}
393
394
395static bool
396abitset_subset_p (bitset dst, bitset src)
397{
398  bitset_windex i;
399  bitset_word *srcp = ABITSET_WORDS (src);
400  bitset_word *dstp = ABITSET_WORDS (dst);
401  bitset_windex size = dst->b.csize;
402
403  for (i = 0; i < size; i++, dstp++, srcp++)
404      if (*dstp != (*srcp | *dstp))
405	  return false;
406  return true;
407}
408
409
410static bool
411abitset_disjoint_p (bitset dst, bitset src)
412{
413  bitset_windex i;
414  bitset_word *srcp = ABITSET_WORDS (src);
415  bitset_word *dstp = ABITSET_WORDS (dst);
416  bitset_windex size = dst->b.csize;
417
418  for (i = 0; i < size; i++)
419      if (*srcp++ & *dstp++)
420	  return false;
421
422  return true;
423}
424
425
426static void
427abitset_and (bitset dst, bitset src1, bitset src2)
428{
429  bitset_windex i;
430  bitset_word *src1p = ABITSET_WORDS (src1);
431  bitset_word *src2p = ABITSET_WORDS (src2);
432  bitset_word *dstp = ABITSET_WORDS (dst);
433  bitset_windex size = dst->b.csize;
434
435  for (i = 0; i < size; i++)
436      *dstp++ = *src1p++ & *src2p++;
437}
438
439
440static bool
441abitset_and_cmp (bitset dst, bitset src1, bitset src2)
442{
443  bitset_windex i;
444  bool changed = false;
445  bitset_word *src1p = ABITSET_WORDS (src1);
446  bitset_word *src2p = ABITSET_WORDS (src2);
447  bitset_word *dstp = ABITSET_WORDS (dst);
448  bitset_windex size = dst->b.csize;
449
450  for (i = 0; i < size; i++, dstp++)
451    {
452      bitset_word tmp = *src1p++ & *src2p++;
453
454      if (*dstp != tmp)
455	{
456	  changed = true;
457	  *dstp = tmp;
458	}
459    }
460  return changed;
461}
462
463
464static void
465abitset_andn (bitset dst, bitset src1, bitset src2)
466{
467  bitset_windex i;
468  bitset_word *src1p = ABITSET_WORDS (src1);
469  bitset_word *src2p = ABITSET_WORDS (src2);
470  bitset_word *dstp = ABITSET_WORDS (dst);
471  bitset_windex size = dst->b.csize;
472
473  for (i = 0; i < size; i++)
474      *dstp++ = *src1p++ & ~(*src2p++);
475}
476
477
478static bool
479abitset_andn_cmp (bitset dst, bitset src1, bitset src2)
480{
481  bitset_windex i;
482  bool changed = false;
483  bitset_word *src1p = ABITSET_WORDS (src1);
484  bitset_word *src2p = ABITSET_WORDS (src2);
485  bitset_word *dstp = ABITSET_WORDS (dst);
486  bitset_windex size = dst->b.csize;
487
488  for (i = 0; i < size; i++, dstp++)
489    {
490      bitset_word tmp = *src1p++ & ~(*src2p++);
491
492      if (*dstp != tmp)
493	{
494	  changed = true;
495	  *dstp = tmp;
496	}
497    }
498  return changed;
499}
500
501
502static void
503abitset_or (bitset dst, bitset src1, bitset src2)
504{
505  bitset_windex i;
506  bitset_word *src1p = ABITSET_WORDS (src1);
507  bitset_word *src2p = ABITSET_WORDS (src2);
508  bitset_word *dstp = ABITSET_WORDS (dst);
509  bitset_windex size = dst->b.csize;
510
511  for (i = 0; i < size; i++)
512      *dstp++ = *src1p++ | *src2p++;
513}
514
515
516static bool
517abitset_or_cmp (bitset dst, bitset src1, bitset src2)
518{
519  bitset_windex i;
520  bool changed = false;
521  bitset_word *src1p = ABITSET_WORDS (src1);
522  bitset_word *src2p = ABITSET_WORDS (src2);
523  bitset_word *dstp = ABITSET_WORDS (dst);
524  bitset_windex size = dst->b.csize;
525
526  for (i = 0; i < size; i++, dstp++)
527    {
528      bitset_word tmp = *src1p++ | *src2p++;
529
530      if (*dstp != tmp)
531	{
532	  changed = true;
533	  *dstp = tmp;
534	}
535    }
536  return changed;
537}
538
539
540static void
541abitset_xor (bitset dst, bitset src1, bitset src2)
542{
543  bitset_windex i;
544  bitset_word *src1p = ABITSET_WORDS (src1);
545  bitset_word *src2p = ABITSET_WORDS (src2);
546  bitset_word *dstp = ABITSET_WORDS (dst);
547  bitset_windex size = dst->b.csize;
548
549  for (i = 0; i < size; i++)
550      *dstp++ = *src1p++ ^ *src2p++;
551}
552
553
554static bool
555abitset_xor_cmp (bitset dst, bitset src1, bitset src2)
556{
557  bitset_windex i;
558  bool changed = false;
559  bitset_word *src1p = ABITSET_WORDS (src1);
560  bitset_word *src2p = ABITSET_WORDS (src2);
561  bitset_word *dstp = ABITSET_WORDS (dst);
562  bitset_windex size = dst->b.csize;
563
564  for (i = 0; i < size; i++, dstp++)
565    {
566      bitset_word tmp = *src1p++ ^ *src2p++;
567
568      if (*dstp != tmp)
569	{
570	  changed = true;
571	  *dstp = tmp;
572	}
573    }
574  return changed;
575}
576
577
578static void
579abitset_and_or (bitset dst, bitset src1, bitset src2, bitset src3)
580{
581  bitset_windex i;
582  bitset_word *src1p = ABITSET_WORDS (src1);
583  bitset_word *src2p = ABITSET_WORDS (src2);
584  bitset_word *src3p = ABITSET_WORDS (src3);
585  bitset_word *dstp = ABITSET_WORDS (dst);
586  bitset_windex size = dst->b.csize;
587
588  for (i = 0; i < size; i++)
589      *dstp++ = (*src1p++ & *src2p++) | *src3p++;
590}
591
592
593static bool
594abitset_and_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
595{
596  bitset_windex i;
597  bool changed = false;
598  bitset_word *src1p = ABITSET_WORDS (src1);
599  bitset_word *src2p = ABITSET_WORDS (src2);
600  bitset_word *src3p = ABITSET_WORDS (src3);
601  bitset_word *dstp = ABITSET_WORDS (dst);
602  bitset_windex size = dst->b.csize;
603
604  for (i = 0; i < size; i++, dstp++)
605    {
606      bitset_word tmp = (*src1p++ & *src2p++) | *src3p++;
607
608      if (*dstp != tmp)
609	{
610	  changed = true;
611	  *dstp = tmp;
612	}
613    }
614  return changed;
615}
616
617
618static void
619abitset_andn_or (bitset dst, bitset src1, bitset src2, bitset src3)
620{
621  bitset_windex i;
622  bitset_word *src1p = ABITSET_WORDS (src1);
623  bitset_word *src2p = ABITSET_WORDS (src2);
624  bitset_word *src3p = ABITSET_WORDS (src3);
625  bitset_word *dstp = ABITSET_WORDS (dst);
626  bitset_windex size = dst->b.csize;
627
628  for (i = 0; i < size; i++)
629      *dstp++ = (*src1p++ & ~(*src2p++)) | *src3p++;
630}
631
632
633static bool
634abitset_andn_or_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
635{
636  bitset_windex i;
637  bool changed = false;
638  bitset_word *src1p = ABITSET_WORDS (src1);
639  bitset_word *src2p = ABITSET_WORDS (src2);
640  bitset_word *src3p = ABITSET_WORDS (src3);
641  bitset_word *dstp = ABITSET_WORDS (dst);
642  bitset_windex size = dst->b.csize;
643
644  for (i = 0; i < size; i++, dstp++)
645    {
646      bitset_word tmp = (*src1p++ & ~(*src2p++)) | *src3p++;
647
648      if (*dstp != tmp)
649	{
650	  changed = true;
651	  *dstp = tmp;
652	}
653    }
654  return changed;
655}
656
657
658static void
659abitset_or_and (bitset dst, bitset src1, bitset src2, bitset src3)
660{
661  bitset_windex i;
662  bitset_word *src1p = ABITSET_WORDS (src1);
663  bitset_word *src2p = ABITSET_WORDS (src2);
664  bitset_word *src3p = ABITSET_WORDS (src3);
665  bitset_word *dstp = ABITSET_WORDS (dst);
666  bitset_windex size = dst->b.csize;
667
668  for (i = 0; i < size; i++)
669      *dstp++ = (*src1p++ | *src2p++) & *src3p++;
670}
671
672
673static bool
674abitset_or_and_cmp (bitset dst, bitset src1, bitset src2, bitset src3)
675{
676  bitset_windex i;
677  bool changed = false;
678  bitset_word *src1p = ABITSET_WORDS (src1);
679  bitset_word *src2p = ABITSET_WORDS (src2);
680  bitset_word *src3p = ABITSET_WORDS (src3);
681  bitset_word *dstp = ABITSET_WORDS (dst);
682  bitset_windex size = dst->b.csize;
683
684  for (i = 0; i < size; i++, dstp++)
685    {
686      bitset_word tmp = (*src1p++ | *src2p++) & *src3p++;
687
688      if (*dstp != tmp)
689	{
690	  changed = true;
691	  *dstp = tmp;
692	}
693    }
694  return changed;
695}
696
697
698static void
699abitset_copy (bitset dst, bitset src)
700{
701  if (BITSET_COMPATIBLE_ (dst, src))
702      abitset_copy1 (dst, src);
703  else
704      bitset_copy_ (dst, src);
705}
706
707
708/* Vector of operations for single word bitsets.  */
709struct bitset_vtable abitset_small_vtable = {
710  abitset_set,
711  abitset_reset,
712  bitset_toggle_,
713  abitset_test,
714  abitset_resize,
715  bitset_size_,
716  bitset_count_,
717  abitset_empty_p,
718  abitset_ones,
719  abitset_zero,
720  abitset_copy,
721  abitset_disjoint_p,
722  abitset_equal_p,
723  abitset_not,
724  abitset_subset_p,
725  abitset_and,
726  abitset_and_cmp,
727  abitset_andn,
728  abitset_andn_cmp,
729  abitset_or,
730  abitset_or_cmp,
731  abitset_xor,
732  abitset_xor_cmp,
733  abitset_and_or,
734  abitset_and_or_cmp,
735  abitset_andn_or,
736  abitset_andn_or_cmp,
737  abitset_or_and,
738  abitset_or_and_cmp,
739  abitset_small_list,
740  abitset_list_reverse,
741  NULL,
742  BITSET_ARRAY
743};
744
745
746/* Vector of operations for multiple word bitsets.  */
747struct bitset_vtable abitset_vtable = {
748  abitset_set,
749  abitset_reset,
750  bitset_toggle_,
751  abitset_test,
752  abitset_resize,
753  bitset_size_,
754  bitset_count_,
755  abitset_empty_p,
756  abitset_ones,
757  abitset_zero,
758  abitset_copy,
759  abitset_disjoint_p,
760  abitset_equal_p,
761  abitset_not,
762  abitset_subset_p,
763  abitset_and,
764  abitset_and_cmp,
765  abitset_andn,
766  abitset_andn_cmp,
767  abitset_or,
768  abitset_or_cmp,
769  abitset_xor,
770  abitset_xor_cmp,
771  abitset_and_or,
772  abitset_and_or_cmp,
773  abitset_andn_or,
774  abitset_andn_or_cmp,
775  abitset_or_and,
776  abitset_or_and_cmp,
777  abitset_list,
778  abitset_list_reverse,
779  NULL,
780  BITSET_ARRAY
781};
782
783
784size_t
785abitset_bytes (bitset_bindex n_bits)
786{
787  bitset_windex size;
788  size_t bytes;
789  size_t header_size = offsetof (union bitset_union, a.words);
790  struct bitset_align_struct { char a; union bitset_union b; };
791  size_t bitset_alignment = offsetof (struct bitset_align_struct, b);
792
793  size = ABITSET_N_WORDS (n_bits);
794  bytes = header_size + size * sizeof (bitset_word);
795
796  /* Align the size properly for a vector of abitset objects.  */
797  if (header_size % bitset_alignment != 0
798      || sizeof (bitset_word) % bitset_alignment != 0)
799    {
800      bytes += bitset_alignment - 1;
801      bytes -= bytes % bitset_alignment;
802    }
803
804  return bytes;
805}
806
807
808bitset
809abitset_init (bitset bset, bitset_bindex n_bits)
810{
811  bitset_windex size;
812
813  size = ABITSET_N_WORDS (n_bits);
814  BITSET_NBITS_ (bset) = n_bits;
815
816  /* Use optimized routines if bitset fits within a single word.
817     There is probably little merit if using caching since
818     the small bitset will always fit in the cache.  */
819  if (size == 1)
820    bset->b.vtable = &abitset_small_vtable;
821  else
822    bset->b.vtable = &abitset_vtable;
823
824  bset->b.cindex = 0;
825  bset->b.csize = size;
826  bset->b.cdata = ABITSET_WORDS (bset);
827  return bset;
828}
829