]> git.saurik.com Git - bison.git/blame_incremental - lib/ebitset.c
* lib/bitset.h (BITSET_FOR_EACH, BITSET_FOR_EACH_REVERSE):
[bison.git] / lib / ebitset.c
... / ...
CommitLineData
1/* Functions to support expandable bitsets.
2 Copyright (C) 2002 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 "ebitset.h"
25#include "obstack.h"
26#include <stdlib.h>
27
28/* This file implements expandable bitsets. These bitsets can be of
29 arbitrary length and are more efficient than arrays of bits for
30 large sparse sets.
31
32 Empty elements are represented by a NULL pointer in the table of
33 element pointers. An alternative is to point to a special zero
34 element. Similarly, we could represent an all 1's element with
35 another special ones element pointer.
36
37 Bitsets are commonly empty so we need to ensure that this special
38 case is fast. A zero bitset is indicated when cdata is 0. This is
39 conservative since cdata may be non zero and the bitset may still
40 be zero.
41
42 The bitset cache can be disabled either by setting cindex to
43 BITSET_WINDEX_MAX or by setting csize to 0. Here
44 we use the former approach since cindex needs to be updated whenever
45 cdata is changed.
46*/
47
48
49/* Number of words to use for each element. */
50#define EBITSET_ELT_WORDS 2
51
52/* Number of bits stored in each element. */
53#define EBITSET_ELT_BITS \
54 ((unsigned) (EBITSET_ELT_WORDS * BITSET_WORD_BITS))
55
56/* Ebitset element. We use an array of bits. */
57typedef struct ebitset_elt_struct
58{
59 union
60 {
61 bitset_word words[EBITSET_ELT_WORDS]; /* Bits that are set. */
62 struct ebitset_elt_struct *next;
63 }
64 u;
65}
66ebitset_elt;
67
68
69typedef ebitset_elt *ebitset_elts;
70
71
72/* Number of elements to initially allocate. */
73
74#ifndef EBITSET_INITIAL_SIZE
75#define EBITSET_INITIAL_SIZE 2
76#endif
77
78/* Minimum number of elements to grow table. */
79
80#ifndef EBITSET_GROW_SIZE
81#define EBITSET_GROW_SIZE 4
82#endif
83
84enum ebitset_find_mode
85 { EBITSET_FIND, EBITSET_CREATE, EBITSET_SUBST };
86
87static ebitset_elt ebitset_zero_elts[1]; /* Elements of all zero bits. */
88
89/* Obstack to allocate bitset elements from. */
90static struct obstack ebitset_obstack;
91static int ebitset_obstack_init = 0;
92static ebitset_elt *ebitset_free_list; /* Free list of bitset elements. */
93
94#define EBITSET_ELTS(BSET) ((BSET)->e.elts)
95#define EBITSET_SIZE(BSET) ((BSET)->e.size)
96
97#define EBITSET_NEXT(ELT) ((ELT)->u.next)
98#define EBITSET_WORDS(ELT) ((ELT)->u.words)
99
100/* Disable bitset cache and mark BSET as being zero. */
101#define EBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
102 (BSET)->b.cdata = 0)
103
104#define EBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX)
105
106/* Disable bitset cache and mark BSET as being possibly non-zero. */
107#define EBITSET_NONZERO_SET(BSET) \
108 (EBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
109
110/* A conservative estimate of whether the bitset is zero.
111 This is non-zero only if we know for sure that the bitset is zero. */
112#define EBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
113
114/* Enable cache to point to element with table index EINDEX.
115 The element must exist. */
116#define EBITSET_CACHE_SET(BSET, EINDEX) \
117 ((BSET)->b.cindex = (EINDEX) * EBITSET_ELT_WORDS, \
118 (BSET)->b.cdata = EBITSET_WORDS (EBITSET_ELTS (BSET) [EINDEX]))
119
120
121/* Grow the expandable table for BSET by SIZE elements. */
122static void
123ebitset_elts_grow (bitset bset, bitset_windex size)
124{
125 bitset_windex oldsize;
126 bitset_windex newsize;
127
128 oldsize = EBITSET_SIZE (bset);
129 newsize = oldsize + size;
130
131 if (BITSET_SIZE_MAX / sizeof (ebitset_elt *) < newsize)
132 xalloc_die ();
133
134 EBITSET_ELTS (bset) = xrealloc (EBITSET_ELTS (bset),
135 newsize * sizeof (ebitset_elt *));
136 EBITSET_SIZE (bset) = newsize;
137
138 memset (EBITSET_ELTS (bset) + oldsize, 0, size * sizeof (ebitset_elt *));
139}
140
141
142/* Allocate a ebitset element. The bits are not cleared. */
143static inline ebitset_elt *
144ebitset_elt_alloc (void)
145{
146 ebitset_elt *elt;
147
148 if (ebitset_free_list != 0)
149 {
150 elt = ebitset_free_list;
151 ebitset_free_list = EBITSET_NEXT (elt);
152 }
153 else
154 {
155 if (!ebitset_obstack_init)
156 {
157 ebitset_obstack_init = 1;
158
159 /* Let particular systems override the size of a chunk. */
160
161#ifndef OBSTACK_CHUNK_SIZE
162#define OBSTACK_CHUNK_SIZE 0
163#endif
164
165 /* Let them override the alloc and free routines too. */
166
167#ifndef OBSTACK_CHUNK_ALLOC
168#define OBSTACK_CHUNK_ALLOC xmalloc
169#endif
170
171#ifndef OBSTACK_CHUNK_FREE
172#define OBSTACK_CHUNK_FREE free
173#endif
174
175#if !defined(__GNUC__) || (__GNUC__ < 2)
176#define __alignof__(type) 0
177#endif
178
179 obstack_specify_allocation (&ebitset_obstack, OBSTACK_CHUNK_SIZE,
180 __alignof__ (ebitset_elt),
181 (void *(*)PARAMS ((long)))
182 OBSTACK_CHUNK_ALLOC,
183 (void (*)PARAMS ((void *)))
184 OBSTACK_CHUNK_FREE);
185 }
186
187 /* Perhaps we should add a number of new elements to the free
188 list. */
189 elt = (ebitset_elt *) obstack_alloc (&ebitset_obstack,
190 sizeof (ebitset_elt));
191 }
192
193 return elt;
194}
195
196
197/* Allocate a ebitset element. The bits are cleared. */
198static inline ebitset_elt *
199ebitset_elt_calloc (void)
200{
201 ebitset_elt *elt;
202
203 elt = ebitset_elt_alloc ();
204 memset (EBITSET_WORDS (elt), 0, sizeof (EBITSET_WORDS (elt)));
205 return elt;
206}
207
208
209static inline void
210ebitset_elt_free (ebitset_elt *elt)
211{
212 EBITSET_NEXT (elt) = ebitset_free_list;
213 ebitset_free_list = elt;
214}
215
216
217/* Remove element with index EINDEX from bitset BSET. */
218static inline void
219ebitset_elt_remove (bitset bset, bitset_windex eindex)
220{
221 ebitset_elts *elts;
222 ebitset_elt *elt;
223
224 elts = EBITSET_ELTS (bset);
225
226 elt = elts[eindex];
227
228 elts[eindex] = 0;
229 ebitset_elt_free (elt);
230}
231
232
233/* Add ELT into elts at index EINDEX of bitset BSET. */
234static inline void
235ebitset_elt_add (bitset bset, ebitset_elt *elt, bitset_windex eindex)
236{
237 ebitset_elts *elts;
238
239 elts = EBITSET_ELTS (bset);
240 /* Assume that the elts entry not allocated. */
241 elts[eindex] = elt;
242}
243
244
245/* Return nonzero if all bits in an element are zero. */
246static inline int
247ebitset_elt_zero_p (ebitset_elt *elt)
248{
249 int i;
250
251 for (i = 0; i < EBITSET_ELT_WORDS; i++)
252 if (EBITSET_WORDS (elt)[i])
253 return 0;
254
255 return 1;
256}
257
258
259static ebitset_elt *
260ebitset_elt_find (bitset bset, bitset_windex windex,
261 enum ebitset_find_mode mode)
262{
263 ebitset_elt *elt;
264 bitset_windex size;
265 bitset_windex eindex;
266 ebitset_elts *elts;
267
268 eindex = windex / EBITSET_ELT_WORDS;
269
270 elts = EBITSET_ELTS (bset);
271 size = EBITSET_SIZE (bset);
272
273 if (eindex < size)
274 {
275 if ((elt = elts[eindex]))
276 {
277 if (EBITSET_WORDS (elt) == bset->b.cdata)
278 return elt;
279
280 EBITSET_CACHE_SET (bset, eindex);
281 return elt;
282 }
283 }
284
285 /* The element could not be found. */
286
287 switch (mode)
288 {
289 case EBITSET_FIND:
290 return 0;
291
292 case EBITSET_CREATE:
293 if (eindex >= size)
294 {
295 bitset_windex extra;
296
297 extra = eindex - size + 1;
298
299 /* We need to expand the table by EXTRA elements. It may be
300 better with large bitsets to grow the number of
301 elements by some fraction of the current size otherwise
302 we can spend a lot of time slowly increasing the size of the
303 bitset. */
304 if (extra < EBITSET_GROW_SIZE)
305 extra = EBITSET_GROW_SIZE;
306
307 ebitset_elts_grow (bset, extra);
308 }
309
310 /* Create a new element. */
311 elt = ebitset_elt_calloc ();
312 ebitset_elt_add (bset, elt, eindex);
313 EBITSET_CACHE_SET (bset, eindex);
314 return elt;
315
316 case EBITSET_SUBST:
317 return &ebitset_zero_elts[0];
318
319 default:
320 abort ();
321 }
322}
323
324
325static inline ebitset_elt *
326ebitset_elt_last (bitset bset)
327{
328 ebitset_elts *elts;
329
330 elts = EBITSET_ELTS (bset);
331
332 /* Assume that have at least one element in elts. */
333 return elts[EBITSET_SIZE (bset) - 1];
334}
335
336
337/* Weed out the zero elements from the elts. */
338static inline bitset_windex
339ebitset_weed (bitset bset)
340{
341 ebitset_elts *elts;
342 bitset_windex j;
343 bitset_windex count;
344
345 if (EBITSET_ZERO_P (bset))
346 return 0;
347
348 elts = EBITSET_ELTS (bset);
349 count = 0;
350 for (j = 0; j < EBITSET_SIZE (bset); j++)
351 {
352 ebitset_elt *elt = elts[j];
353
354 if (elt)
355 {
356 if (elt && ebitset_elt_zero_p (elt))
357 {
358 ebitset_elt_remove (bset, j);
359 count++;
360 }
361 }
362 else
363 count++;
364 }
365
366 count = j - count;
367 if (!count)
368 {
369 /* All the bits are zero. We could shrink the elts.
370 For now just mark BSET as known to be zero. */
371 EBITSET_ZERO_SET (bset);
372 }
373 else
374 EBITSET_NONZERO_SET (bset);
375
376 return count;
377}
378
379
380/* Set all bits in the bitset to zero. */
381static inline void
382ebitset_zero (bitset bset)
383{
384 ebitset_elts *elts;
385 bitset_windex j;
386
387 if (EBITSET_ZERO_P (bset))
388 return;
389
390 elts = EBITSET_ELTS (bset);
391 for (j = 0; j < EBITSET_SIZE (bset); j++)
392 {
393 ebitset_elt *elt = elts[j];
394
395 if (elt)
396 ebitset_elt_remove (bset, j);
397 }
398
399 /* All the bits are zero. We could shrink the elts.
400 For now just mark BSET as known to be zero. */
401 EBITSET_ZERO_SET (bset);
402}
403
404
405static inline int
406ebitset_equal_p (bitset dst, bitset src)
407{
408 ebitset_elts *selts;
409 ebitset_elts *delts;
410 bitset_windex j;
411
412 if (src == dst)
413 return 1;
414
415 ebitset_weed (dst);
416 ebitset_weed (src);
417
418 if (EBITSET_SIZE (src) != EBITSET_SIZE (dst))
419 return 0;
420
421 selts = EBITSET_ELTS (src);
422 delts = EBITSET_ELTS (dst);
423
424 for (j = 0; j < EBITSET_SIZE (src); j++)
425 {
426 unsigned int i;
427 ebitset_elt *selt = selts[j];
428 ebitset_elt *delt = delts[j];
429
430 if (!selt && !delt)
431 continue;
432 if ((selt && !delt) || (!selt && delt))
433 return 0;
434
435 for (i = 0; i < EBITSET_ELT_WORDS; i++)
436 if (EBITSET_WORDS (selt)[i] != EBITSET_WORDS (delt)[i])
437 return 0;
438 }
439 return 1;
440}
441
442
443/* Copy bits from bitset SRC to bitset DST. */
444static inline void
445ebitset_copy_ (bitset dst, bitset src)
446{
447 ebitset_elts *selts;
448 ebitset_elts *delts;
449 bitset_windex j;
450
451 if (src == dst)
452 return;
453
454 ebitset_zero (dst);
455
456 if (EBITSET_SIZE (dst) < EBITSET_SIZE (src))
457 ebitset_elts_grow (dst, EBITSET_SIZE (src) - EBITSET_SIZE (dst));
458
459 selts = EBITSET_ELTS (src);
460 delts = EBITSET_ELTS (dst);
461 for (j = 0; j < EBITSET_SIZE (src); j++)
462 {
463 ebitset_elt *selt = selts[j];
464
465 if (selt)
466 {
467 ebitset_elt *tmp;
468
469 tmp = ebitset_elt_alloc ();
470 delts[j] = tmp;
471 memcpy (EBITSET_WORDS (tmp), EBITSET_WORDS (selt),
472 sizeof (EBITSET_WORDS (selt)));
473 }
474 }
475 EBITSET_NONZERO_SET (dst);
476}
477
478
479/* Copy bits from bitset SRC to bitset DST. Return non-zero if
480 bitsets different. */
481static inline int
482ebitset_copy_cmp (bitset dst, bitset src)
483{
484 if (src == dst)
485 return 0;
486
487 if (EBITSET_ZERO_P (dst))
488 {
489 ebitset_copy_ (dst, src);
490 return !EBITSET_ZERO_P (src);
491 }
492
493 if (ebitset_equal_p (dst, src))
494 return 0;
495
496 ebitset_copy_ (dst, src);
497 return 1;
498}
499
500
501/* Return size in bits of bitset SRC. */
502static bitset_bindex
503ebitset_size (bitset src)
504{
505 /* Return current size of bitset in bits. */
506 return EBITSET_SIZE (src) * EBITSET_ELT_BITS;
507}
508
509
510/* Set bit BITNO in bitset DST. */
511static void
512ebitset_set (bitset dst, bitset_bindex bitno)
513{
514 bitset_windex windex = bitno / BITSET_WORD_BITS;
515
516 ebitset_elt_find (dst, windex, EBITSET_CREATE);
517
518 dst->b.cdata[windex - dst->b.cindex] |=
519 (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
520}
521
522
523/* Reset bit BITNO in bitset DST. */
524static void
525ebitset_reset (bitset dst, bitset_bindex bitno)
526{
527 bitset_windex windex = bitno / BITSET_WORD_BITS;
528
529 if (!ebitset_elt_find (dst, windex, EBITSET_FIND))
530 return;
531
532 dst->b.cdata[windex - dst->b.cindex] &=
533 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
534
535 /* If all the data is zero, perhaps we should remove it now...
536 However, there is a good chance that the element will be needed
537 again soon. */
538}
539
540
541/* Test bit BITNO in bitset SRC. */
542static int
543ebitset_test (bitset src, bitset_bindex bitno)
544{
545 bitset_windex windex = bitno / BITSET_WORD_BITS;
546
547 if (!ebitset_elt_find (src, windex, EBITSET_FIND))
548 return 0;
549
550 return (src->b.
551 cdata[windex - src->b.cindex] >> (bitno % BITSET_WORD_BITS)) & 1;
552}
553
554
555static void
556ebitset_free (bitset bset)
557{
558 ebitset_zero (bset);
559 free (EBITSET_ELTS (bset));
560}
561
562
563/* Find list of up to NUM bits set in BSET starting from and including
564 *NEXT and store in array LIST. Return with actual number of bits
565 found and with *NEXT indicating where search stopped. */
566static bitset_bindex
567ebitset_list_reverse (bitset bset, bitset_bindex *list,
568 bitset_bindex num, bitset_bindex *next)
569{
570 bitset_bindex n_bits;
571 bitset_bindex bitno;
572 bitset_bindex rbitno;
573 unsigned int bcount;
574 bitset_bindex boffset;
575 bitset_windex windex;
576 bitset_windex eindex;
577 bitset_windex woffset;
578 bitset_bindex count;
579 bitset_windex size;
580 ebitset_elts *elts;
581
582 if (EBITSET_ZERO_P (bset))
583 return 0;
584
585 size = EBITSET_SIZE (bset);
586 n_bits = size * EBITSET_ELT_BITS;
587 rbitno = *next;
588
589 if (rbitno >= n_bits)
590 return 0;
591
592 elts = EBITSET_ELTS (bset);
593
594 bitno = n_bits - (rbitno + 1);
595
596 windex = bitno / BITSET_WORD_BITS;
597 eindex = bitno / EBITSET_ELT_BITS;
598 woffset = windex - eindex * EBITSET_ELT_WORDS;
599
600 /* If num is 1, we could speed things up with a binary search
601 of the word of interest. */
602
603 count = 0;
604 bcount = bitno % BITSET_WORD_BITS;
605 boffset = windex * BITSET_WORD_BITS;
606
607 do
608 {
609 ebitset_elt *elt;
610 bitset_word *srcp;
611
612 elt = elts[eindex];
613 if (elt)
614 {
615 srcp = EBITSET_WORDS (elt);
616
617 do
618 {
619 bitset_word word;
620
621 word = srcp[woffset] << (BITSET_WORD_BITS - 1 - bcount);
622
623 for (; word; bcount--)
624 {
625 if (word & BITSET_MSB)
626 {
627 list[count++] = boffset + bcount;
628 if (count >= num)
629 {
630 *next = n_bits - (boffset + bcount);
631 return count;
632 }
633 }
634 word <<= 1;
635 }
636 boffset -= BITSET_WORD_BITS;
637 bcount = BITSET_WORD_BITS - 1;
638 }
639 while (woffset--);
640 }
641
642 woffset = EBITSET_ELT_WORDS - 1;
643 boffset = eindex * EBITSET_ELT_BITS - BITSET_WORD_BITS;
644 }
645 while (eindex--);
646
647 *next = n_bits - (boffset + 1);
648 return count;
649}
650
651
652/* Find list of up to NUM bits set in BSET starting from and including
653 *NEXT and store in array LIST. Return with actual number of bits
654 found and with *NEXT indicating where search stopped. */
655static bitset_bindex
656ebitset_list (bitset bset, bitset_bindex *list,
657 bitset_bindex num, bitset_bindex *next)
658{
659 bitset_bindex bitno;
660 bitset_windex windex;
661 bitset_windex eindex;
662 bitset_bindex count;
663 bitset_windex size;
664 ebitset_elt *elt;
665 bitset_word word;
666 ebitset_elts *elts;
667
668 if (EBITSET_ZERO_P (bset))
669 return 0;
670
671 bitno = *next;
672 count = 0;
673
674 elts = EBITSET_ELTS (bset);
675 size = EBITSET_SIZE (bset);
676 eindex = bitno / EBITSET_ELT_BITS;
677
678 if (bitno % EBITSET_ELT_BITS)
679 {
680 /* We need to start within an element. This is not very common. */
681
682 elt = elts[eindex];
683 if (elt)
684 {
685 bitset_windex woffset;
686 bitset_word *srcp = EBITSET_WORDS (elt);
687
688 windex = bitno / BITSET_WORD_BITS;
689 woffset = eindex * EBITSET_ELT_WORDS;
690
691 for (; (windex - woffset) < EBITSET_ELT_WORDS; windex++)
692 {
693 word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
694
695 for (; word; bitno++)
696 {
697 if (word & 1)
698 {
699 list[count++] = bitno;
700 if (count >= num)
701 {
702 *next = bitno + 1;
703 return count;
704 }
705 }
706 word >>= 1;
707 }
708 bitno = (windex + 1) * BITSET_WORD_BITS;
709 }
710 }
711
712 /* Skip to next element. */
713 eindex++;
714 }
715
716 /* If num is 1, we could speed things up with a binary search
717 of the word of interest. */
718
719 for (; eindex < size; eindex++)
720 {
721 int i;
722 bitset_word *srcp;
723
724 elt = elts[eindex];
725 if (!elt)
726 continue;
727
728 srcp = EBITSET_WORDS (elt);
729 windex = eindex * EBITSET_ELT_WORDS;
730
731 if ((count + EBITSET_ELT_BITS) < num)
732 {
733 /* The coast is clear, plant boot! */
734
735 for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
736 {
737 bitno = windex * BITSET_WORD_BITS;
738
739 word = srcp[i];
740 if (word)
741 {
742 if (!(word & 0xffff))
743 {
744 word >>= 16;
745 bitno += 16;
746 }
747 if (!(word & 0xff))
748 {
749 word >>= 8;
750 bitno += 8;
751 }
752 for (; word; bitno++)
753 {
754 if (word & 1)
755 list[count++] = bitno;
756 word >>= 1;
757 }
758 }
759 }
760 }
761 else
762 {
763 /* Tread more carefully since we need to check
764 if array overflows. */
765
766 for (i = 0; i < EBITSET_ELT_WORDS; i++, windex++)
767 {
768 bitno = windex * BITSET_WORD_BITS;
769
770 for (word = srcp[i]; word; bitno++)
771 {
772 if (word & 1)
773 {
774 list[count++] = bitno;
775 if (count >= num)
776 {
777 *next = bitno + 1;
778 return count;
779 }
780 }
781 word >>= 1;
782 }
783 }
784 }
785 }
786
787 *next = bitno;
788 return count;
789}
790
791
792static void
793ebitset_ones (bitset dst)
794{
795 bitset_windex j;
796 ebitset_elt *elt;
797
798
799 for (j = 0; j < EBITSET_SIZE (dst); j++)
800 {
801 /* Create new elements if they cannot be found. Perhaps
802 we should just add pointers to a ones element. */
803 elt =
804 ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
805 memset (EBITSET_WORDS (elt), -1, sizeof (EBITSET_WORDS (elt)));
806 }
807 EBITSET_NONZERO_SET (dst);
808}
809
810
811static int
812ebitset_empty_p (bitset dst)
813{
814 return !ebitset_weed (dst);
815}
816
817
818static void
819ebitset_not (bitset dst, bitset src)
820{
821 unsigned int i;
822 ebitset_elt *selt;
823 ebitset_elt *delt;
824 bitset_windex j;
825
826 for (j = 0; j < EBITSET_SIZE (src); j++)
827 {
828 /* Create new elements for dst if they cannot be found
829 or substitute zero elements if src elements not found. */
830 selt =
831 ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_SUBST);
832 delt =
833 ebitset_elt_find (dst, j * EBITSET_ELT_WORDS, EBITSET_CREATE);
834
835 for (i = 0; i < EBITSET_ELT_WORDS; i++)
836 EBITSET_WORDS (delt)[i] = ~EBITSET_WORDS (selt)[i];
837 }
838 EBITSET_NONZERO_SET (dst);
839}
840
841
842/* Return 1 if DST == DST | SRC. */
843static int
844ebitset_subset_p (bitset dst, bitset src)
845{
846 bitset_windex j;
847 ebitset_elts *selts;
848 ebitset_elts *delts;
849 bitset_windex ssize;
850 bitset_windex dsize;
851
852 selts = EBITSET_ELTS (src);
853 delts = EBITSET_ELTS (dst);
854
855 ssize = EBITSET_SIZE (src);
856 dsize = EBITSET_SIZE (dst);
857
858 for (j = 0; j < ssize; j++)
859 {
860 unsigned int i;
861 ebitset_elt *selt;
862 ebitset_elt *delt;
863
864 selt = j < ssize ? selts[j] : 0;
865 delt = j < dsize ? delts[j] : 0;
866
867 if (!selt && !delt)
868 continue;
869
870 if (!selt)
871 selt = &ebitset_zero_elts[0];
872 if (!delt)
873 delt = &ebitset_zero_elts[0];
874
875 for (i = 0; i < EBITSET_ELT_WORDS; i++)
876 if (EBITSET_WORDS (delt)[i]
877 != (EBITSET_WORDS (selt)[i] | EBITSET_WORDS (delt)[i]))
878 return 0;
879 }
880 return 1;
881}
882
883
884/* Return 1 if DST & SRC == 0. */
885static int
886ebitset_disjoint_p (bitset dst, bitset src)
887{
888 bitset_windex j;
889 ebitset_elts *selts;
890 ebitset_elts *delts;
891 bitset_windex ssize;
892 bitset_windex dsize;
893
894 selts = EBITSET_ELTS (src);
895 delts = EBITSET_ELTS (dst);
896
897 ssize = EBITSET_SIZE (src);
898 dsize = EBITSET_SIZE (dst);
899
900 for (j = 0; j < ssize; j++)
901 {
902 unsigned int i;
903 ebitset_elt *selt;
904 ebitset_elt *delt;
905
906 selt = j < ssize ? selts[j] : 0;
907 delt = j < dsize ? delts[j] : 0;
908
909 if (!selt || !delt)
910 continue;
911
912 for (i = 0; i < EBITSET_ELT_WORDS; i++)
913 if ((EBITSET_WORDS (selt)[i] & EBITSET_WORDS (delt)[i]))
914 return 0;
915 }
916 return 1;
917}
918
919
920
921static int
922ebitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
923{
924 bitset_windex ssize1;
925 bitset_windex ssize2;
926 bitset_windex dsize;
927 bitset_windex size;
928 ebitset_elts *selts1;
929 ebitset_elts *selts2;
930 ebitset_elts *delts;
931 bitset_word *srcp1;
932 bitset_word *srcp2;
933 bitset_word *dstp;
934 int changed = 0;
935 unsigned int i;
936 bitset_windex j;
937
938 ssize1 = EBITSET_SIZE (src1);
939 ssize2 = EBITSET_SIZE (src2);
940 dsize = EBITSET_SIZE (dst);
941 size = ssize1;
942 if (size < ssize2)
943 size = ssize2;
944
945 if (size > dsize)
946 ebitset_elts_grow (dst, size - dsize);
947
948 selts1 = EBITSET_ELTS (src1);
949 selts2 = EBITSET_ELTS (src2);
950 delts = EBITSET_ELTS (dst);
951
952 for (j = 0; j < size; j++)
953 {
954 ebitset_elt *selt1;
955 ebitset_elt *selt2;
956 ebitset_elt *delt;
957
958 selt1 = j < ssize1 ? selts1[j] : 0;
959 selt2 = j < ssize2 ? selts2[j] : 0;
960 delt = j < dsize ? delts[j] : 0;
961
962 if (!selt1 && !selt2)
963 {
964 if (delt)
965 {
966 changed = 1;
967 ebitset_elt_remove (dst, j);
968 }
969 continue;
970 }
971
972 if (!selt1)
973 selt1 = &ebitset_zero_elts[0];
974 if (!selt2)
975 selt2 = &ebitset_zero_elts[0];
976 if (!delt)
977 delt = ebitset_elt_calloc ();
978 else
979 delts[j] = 0;
980
981 srcp1 = EBITSET_WORDS (selt1);
982 srcp2 = EBITSET_WORDS (selt2);
983 dstp = EBITSET_WORDS (delt);
984 switch (op)
985 {
986 case BITSET_OP_OR:
987 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
988 {
989 bitset_word tmp = *srcp1++ | *srcp2++;
990
991 if (*dstp != tmp)
992 {
993 changed = 1;
994 *dstp = tmp;
995 }
996 }
997 break;
998
999 case BITSET_OP_AND:
1000 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1001 {
1002 bitset_word tmp = *srcp1++ & *srcp2++;
1003
1004 if (*dstp != tmp)
1005 {
1006 changed = 1;
1007 *dstp = tmp;
1008 }
1009 }
1010 break;
1011
1012 case BITSET_OP_XOR:
1013 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1014 {
1015 bitset_word tmp = *srcp1++ ^ *srcp2++;
1016
1017 if (*dstp != tmp)
1018 {
1019 changed = 1;
1020 *dstp = tmp;
1021 }
1022 }
1023 break;
1024
1025 case BITSET_OP_ANDN:
1026 for (i = 0; i < EBITSET_ELT_WORDS; i++, dstp++)
1027 {
1028 bitset_word tmp = *srcp1++ & ~(*srcp2++);
1029
1030 if (*dstp != tmp)
1031 {
1032 changed = 1;
1033 *dstp = tmp;
1034 }
1035 }
1036 break;
1037
1038 default:
1039 abort ();
1040 }
1041
1042 if (!ebitset_elt_zero_p (delt))
1043 {
1044 ebitset_elt_add (dst, delt, j);
1045 }
1046 else
1047 {
1048 ebitset_elt_free (delt);
1049 }
1050 }
1051
1052 /* If we have elements of DST left over, free them all. */
1053 for (; j < dsize; j++)
1054 {
1055 ebitset_elt *delt;
1056
1057 changed = 1;
1058
1059 delt = delts[j];
1060
1061 if (delt)
1062 ebitset_elt_remove (dst, j);
1063 }
1064
1065 EBITSET_NONZERO_SET (dst);
1066 return changed;
1067}
1068
1069
1070static int
1071ebitset_and_cmp (bitset dst, bitset src1, bitset src2)
1072{
1073 int changed;
1074
1075 if (EBITSET_ZERO_P (src2))
1076 {
1077 ebitset_weed (dst);
1078 changed = EBITSET_ZERO_P (dst);
1079 ebitset_zero (dst);
1080 return changed;
1081 }
1082 else if (EBITSET_ZERO_P (src1))
1083 {
1084 ebitset_weed (dst);
1085 changed = EBITSET_ZERO_P (dst);
1086 ebitset_zero (dst);
1087 return changed;
1088 }
1089 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1090}
1091
1092
1093static void
1094ebitset_and (bitset dst, bitset src1, bitset src2)
1095{
1096 ebitset_and_cmp (dst, src1, src2);
1097}
1098
1099
1100static int
1101ebitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1102{
1103 int changed;
1104
1105 if (EBITSET_ZERO_P (src2))
1106 {
1107 return ebitset_copy_cmp (dst, src1);
1108 }
1109 else if (EBITSET_ZERO_P (src1))
1110 {
1111 ebitset_weed (dst);
1112 changed = EBITSET_ZERO_P (dst);
1113 ebitset_zero (dst);
1114 return changed;
1115 }
1116 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1117}
1118
1119
1120static void
1121ebitset_andn (bitset dst, bitset src1, bitset src2)
1122{
1123 ebitset_andn_cmp (dst, src1, src2);
1124}
1125
1126
1127static int
1128ebitset_or_cmp (bitset dst, bitset src1, bitset src2)
1129{
1130 if (EBITSET_ZERO_P (src2))
1131 {
1132 return ebitset_copy_cmp (dst, src1);
1133 }
1134 else if (EBITSET_ZERO_P (src1))
1135 {
1136 return ebitset_copy_cmp (dst, src2);
1137 }
1138 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1139}
1140
1141
1142static void
1143ebitset_or (bitset dst, bitset src1, bitset src2)
1144{
1145 ebitset_or_cmp (dst, src1, src2);
1146}
1147
1148
1149static int
1150ebitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1151{
1152 if (EBITSET_ZERO_P (src2))
1153 {
1154 return ebitset_copy_cmp (dst, src1);
1155 }
1156 else if (EBITSET_ZERO_P (src1))
1157 {
1158 return ebitset_copy_cmp (dst, src2);
1159 }
1160 return ebitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1161}
1162
1163
1164static void
1165ebitset_xor (bitset dst, bitset src1, bitset src2)
1166{
1167 ebitset_xor_cmp (dst, src1, src2);
1168}
1169
1170
1171static void
1172ebitset_copy (bitset dst, bitset src)
1173{
1174 if (BITSET_COMPATIBLE_ (dst, src))
1175 ebitset_copy_ (dst, src);
1176 else
1177 bitset_copy_ (dst, src);
1178}
1179
1180
1181/* Vector of operations for linked-list bitsets. */
1182struct bitset_vtable ebitset_vtable = {
1183 ebitset_set,
1184 ebitset_reset,
1185 bitset_toggle_,
1186 ebitset_test,
1187 ebitset_size,
1188 bitset_count_,
1189 ebitset_empty_p,
1190 ebitset_ones,
1191 ebitset_zero,
1192 ebitset_copy,
1193 ebitset_disjoint_p,
1194 ebitset_equal_p,
1195 ebitset_not,
1196 ebitset_subset_p,
1197 ebitset_and,
1198 ebitset_and_cmp,
1199 ebitset_andn,
1200 ebitset_andn_cmp,
1201 ebitset_or,
1202 ebitset_or_cmp,
1203 ebitset_xor,
1204 ebitset_xor_cmp,
1205 bitset_and_or_,
1206 bitset_and_or_cmp_,
1207 bitset_andn_or_,
1208 bitset_andn_or_cmp_,
1209 bitset_or_and_,
1210 bitset_or_and_cmp_,
1211 ebitset_list,
1212 ebitset_list_reverse,
1213 ebitset_free,
1214 BITSET_TABLE
1215};
1216
1217
1218/* Return size of initial structure. */
1219size_t
1220ebitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED)
1221{
1222 return sizeof (struct ebitset_struct);
1223}
1224
1225
1226/* Initialize a bitset. */
1227
1228bitset
1229ebitset_init (bitset bset, bitset_bindex n_bits)
1230{
1231 bitset_windex size;
1232
1233 bset->b.vtable = &ebitset_vtable;
1234
1235 bset->b.csize = EBITSET_ELT_WORDS;
1236
1237 EBITSET_ZERO_SET (bset);
1238
1239 size = n_bits ? (n_bits + EBITSET_ELT_BITS - 1) / EBITSET_ELT_BITS
1240 : EBITSET_INITIAL_SIZE;
1241
1242 EBITSET_SIZE (bset) = 0;
1243 EBITSET_ELTS (bset) = 0;
1244 ebitset_elts_grow (bset, size);
1245
1246 return bset;
1247}
1248
1249
1250void
1251ebitset_release_memory (void)
1252{
1253 ebitset_free_list = 0;
1254 if (ebitset_obstack_init)
1255 {
1256 ebitset_obstack_init = 0;
1257 obstack_free (&ebitset_obstack, NULL);
1258 }
1259}