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