1 /* Functions to support expandable bitsets.
2
3 Copyright (C) 2002-2006, 2009-2015, 2018-2021 Free Software Foundation, Inc.
4
5 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
6
7 This program is free software: you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation, either version 3 of the License, or
10 (at your option) any later version.
11
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with this program. If not, see <https://www.gnu.org/licenses/>. */
19
20 #include <config.h>
21
22 #include "bitset/table.h"
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 #include "obstack.h"
28 #include "xalloc.h"
29
30 /* This file implements expandable bitsets. These bitsets can be of
31 arbitrary length and are more efficient than arrays of bits for
32 large sparse sets.
33
34 Empty elements are represented by a NULL pointer in the table of
35 element pointers. An alternative is to point to a special zero
36 element. Similarly, we could represent an all 1's element with
37 another special ones element pointer.
38
39 Bitsets are commonly empty so we need to ensure that this special
40 case is fast. A zero bitset is indicated when cdata is 0. This is
41 conservative since cdata may be non zero and the bitset may still
42 be zero.
43
44 The bitset cache can be disabled either by setting cindex to
45 BITSET_WINDEX_MAX or by setting csize to 0. Here
46 we use the former approach since cindex needs to be updated whenever
47 cdata is changed.
48 */
49
50
51 /* Number of words to use for each element. */
52 #define TBITSET_ELT_WORDS 2
53
54 /* Number of bits stored in each element. */
55 #define TBITSET_ELT_BITS \
56 ((unsigned) (TBITSET_ELT_WORDS * BITSET_WORD_BITS))
57
58 /* Tbitset element. We use an array of bits. */
59 typedef struct tbitset_elt_struct
60 {
61 union
62 {
63 bitset_word words[TBITSET_ELT_WORDS]; /* Bits that are set. */
64 struct tbitset_elt_struct *next;
65 }
66 u;
67 }
68 tbitset_elt;
69
70
71 typedef tbitset_elt *tbitset_elts;
72
73
74 /* Number of elements to initially allocate. */
75
76 #ifndef TBITSET_INITIAL_SIZE
77 # define TBITSET_INITIAL_SIZE 2
78 #endif
79
80
81 enum tbitset_find_mode
82 { TBITSET_FIND, TBITSET_CREATE, TBITSET_SUBST };
83
84 static tbitset_elt tbitset_zero_elts[1]; /* Elements of all zero bits. */
85
86 /* Obstack to allocate bitset elements from. */
87 static struct obstack tbitset_obstack;
88 static bool tbitset_obstack_init = false;
89 static tbitset_elt *tbitset_free_list; /* Free list of bitset elements. */
90
91 #define TBITSET_N_ELTS(N) (((N) + TBITSET_ELT_BITS - 1) / TBITSET_ELT_BITS)
92 #define TBITSET_ELTS(BSET) ((BSET)->e.elts)
93 #define TBITSET_SIZE(BSET) TBITSET_N_ELTS (BITSET_NBITS_ (BSET))
94 #define TBITSET_ASIZE(BSET) ((BSET)->e.size)
95
96 #define TBITSET_NEXT(ELT) ((ELT)->u.next)
97 #define TBITSET_WORDS(ELT) ((ELT)->u.words)
98
99 /* Disable bitset cache and mark BSET as being zero. */
100 #define TBITSET_ZERO_SET(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX, \
101 (BSET)->b.cdata = 0)
102
103 #define TBITSET_CACHE_DISABLE(BSET) ((BSET)->b.cindex = BITSET_WINDEX_MAX)
104
105 /* Disable bitset cache and mark BSET as being possibly non-zero. */
106 #define TBITSET_NONZERO_SET(BSET) \
107 (TBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
108
109 /* A conservative estimate of whether the bitset is zero.
110 This is non-zero only if we know for sure that the bitset is zero. */
111 #define TBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
112
113 /* Enable cache to point to element with table index EINDEX.
114 The element must exist. */
115 #define TBITSET_CACHE_SET(BSET, EINDEX) \
116 ((BSET)->b.cindex = (EINDEX) * TBITSET_ELT_WORDS, \
117 (BSET)->b.cdata = TBITSET_WORDS (TBITSET_ELTS (BSET) [EINDEX]))
118
119 #undef min
120 #undef max
121 #define min(a, b) ((a) > (b) ? (b) : (a))
122 #define max(a, b) ((a) > (b) ? (a) : (b))
123
124 static bitset_bindex
125 tbitset_resize (bitset src, bitset_bindex n_bits)
126 {
127 if (n_bits == BITSET_NBITS_ (src))
128 return n_bits;
129
130 bitset_windex oldsize = TBITSET_SIZE (src);
131 bitset_windex newsize = TBITSET_N_ELTS (n_bits);
132
133 if (oldsize < newsize)
134 {
135 /* The bitset needs to grow. If we already have enough memory
136 allocated, then just zero what we need. */
137 if (newsize > TBITSET_ASIZE (src))
138 {
139 /* We need to allocate more memory. When oldsize is
140 non-zero this means that we are changing the size, so
141 grow the bitset 25% larger than requested to reduce
142 number of reallocations. */
143
144 bitset_windex size = oldsize == 0 ? newsize : newsize + newsize / 4;
145 TBITSET_ELTS (src)
146 = xrealloc (TBITSET_ELTS (src), size * sizeof (tbitset_elt *));
147 TBITSET_ASIZE (src) = size;
148 }
149
150 memset (TBITSET_ELTS (src) + oldsize, 0,
151 (newsize - oldsize) * sizeof (tbitset_elt *));
152 }
153 else
154 {
155 /* The bitset needs to shrink. There's no point deallocating
156 the memory unless it is shrinking by a reasonable amount. */
157 if ((oldsize - newsize) >= oldsize / 2)
158 {
159 void *p
160 = realloc (TBITSET_ELTS (src), newsize * sizeof (tbitset_elt *));
161 if (p)
162 {
163 TBITSET_ELTS (src) = p;
164 TBITSET_ASIZE (src) = newsize;
165 }
166 }
167
168 /* Need to prune any excess bits. FIXME. */
169 }
170
171 BITSET_NBITS_ (src) = n_bits;
172 return n_bits;
173 }
174
175
176 /* Allocate a tbitset element. The bits are not cleared. */
177 static inline tbitset_elt *
178 tbitset_elt_alloc (void)
179 {
180 tbitset_elt *elt;
181
182 if (tbitset_free_list != 0)
183 {
184 elt = tbitset_free_list;
185 tbitset_free_list = TBITSET_NEXT (elt);
186 }
187 else
188 {
189 if (!tbitset_obstack_init)
190 {
191 tbitset_obstack_init = true;
192
193 /* Let particular systems override the size of a chunk. */
194
195 #ifndef OBSTACK_CHUNK_SIZE
196 # define OBSTACK_CHUNK_SIZE 0
197 #endif
198
199 /* Let them override the alloc and free routines too. */
200
201 #ifndef OBSTACK_CHUNK_ALLOC
202 # define OBSTACK_CHUNK_ALLOC xmalloc
203 #endif
204
205 #ifndef OBSTACK_CHUNK_FREE
206 # define OBSTACK_CHUNK_FREE free
207 #endif
208
209 #if !(defined __GNUC__ || defined __clang__)
210 # define __alignof__(type) 0
211 #endif
212
213 obstack_specify_allocation (&tbitset_obstack, OBSTACK_CHUNK_SIZE,
214 __alignof__ (tbitset_elt),
215 OBSTACK_CHUNK_ALLOC,
216 OBSTACK_CHUNK_FREE);
217 }
218
219 /* Perhaps we should add a number of new elements to the free
220 list. */
221 elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack,
222 sizeof (tbitset_elt));
223 }
224
225 return elt;
226 }
227
228
229 /* Allocate a tbitset element. The bits are cleared. */
230 static inline tbitset_elt *
231 tbitset_elt_calloc (void)
232 {
233 tbitset_elt *elt = tbitset_elt_alloc ();
234 memset (TBITSET_WORDS (elt), 0, sizeof (TBITSET_WORDS (elt)));
235 return elt;
236 }
237
238
239 static inline void
240 tbitset_elt_free (tbitset_elt *elt)
241 {
242 TBITSET_NEXT (elt) = tbitset_free_list;
243 tbitset_free_list = elt;
244 }
245
246
247 /* Remove element with index EINDEX from bitset BSET. */
248 static inline void
249 tbitset_elt_remove (bitset bset, bitset_windex eindex)
250 {
251 tbitset_elts *elts = TBITSET_ELTS (bset);
252 tbitset_elt *elt = elts[eindex];
253
254 elts[eindex] = 0;
255 tbitset_elt_free (elt);
256 }
257
258
259 /* Add ELT into elts at index EINDEX of bitset BSET. */
260 static inline void
261 tbitset_elt_add (bitset bset, tbitset_elt *elt, bitset_windex eindex)
262 {
263 tbitset_elts *elts = TBITSET_ELTS (bset);
264 /* Assume that the elts entry not allocated. */
265 elts[eindex] = elt;
266 }
267
268
269 /* Are all bits in an element zero? */
270 static inline bool
271 tbitset_elt_zero_p (tbitset_elt *elt)
272 {
273 for (int i = 0; i < TBITSET_ELT_WORDS; i++)
274 if (TBITSET_WORDS (elt)[i])
275 return false;
276 return true;
277 }
278
279
280 static tbitset_elt *
281 tbitset_elt_find (bitset bset, bitset_bindex bindex,
282 enum tbitset_find_mode mode)
283 {
284 bitset_windex eindex = bindex / TBITSET_ELT_BITS;
285
286 tbitset_elts *elts = TBITSET_ELTS (bset);
287 bitset_windex size = TBITSET_SIZE (bset);
288
289 if (eindex < size)
290 {
291 tbitset_elt *elt = elts[eindex];
292 if (elt)
293 {
294 if (TBITSET_WORDS (elt) != bset->b.cdata)
295 TBITSET_CACHE_SET (bset, eindex);
296 return elt;
297 }
298 }
299
300 /* The element could not be found. */
301
302 switch (mode)
303 {
304 default:
305 abort ();
306
307 case TBITSET_FIND:
308 return NULL;
309
310 case TBITSET_CREATE:
311 if (eindex >= size)
312 tbitset_resize (bset, bindex);
313
314 /* Create a new element. */
315 {
316 tbitset_elt *elt = tbitset_elt_calloc ();
317 tbitset_elt_add (bset, elt, eindex);
318 TBITSET_CACHE_SET (bset, eindex);
319 return elt;
320 }
321
322 case TBITSET_SUBST:
323 return &tbitset_zero_elts[0];
324 }
325 }
326
327
328 /* Weed out the zero elements from the elts. */
329 static inline bitset_windex
330 tbitset_weed (bitset bset)
331 {
332 if (TBITSET_ZERO_P (bset))
333 return 0;
334
335 tbitset_elts *elts = TBITSET_ELTS (bset);
336 bitset_windex count = 0;
337 bitset_windex j;
338 for (j = 0; j < TBITSET_SIZE (bset); j++)
339 {
340 tbitset_elt *elt = elts[j];
341
342 if (elt)
343 {
344 if (tbitset_elt_zero_p (elt))
345 {
346 tbitset_elt_remove (bset, j);
347 count++;
348 }
349 }
350 else
351 count++;
352 }
353
354 count = j - count;
355 if (!count)
356 {
357 /* All the bits are zero. We could shrink the elts.
358 For now just mark BSET as known to be zero. */
359 TBITSET_ZERO_SET (bset);
360 }
361 else
362 TBITSET_NONZERO_SET (bset);
363
364 return count;
365 }
366
367
368 /* Set all bits in the bitset to zero. */
369 static inline void
370 tbitset_zero (bitset bset)
371 {
372 if (TBITSET_ZERO_P (bset))
373 return;
374
375 tbitset_elts *elts = TBITSET_ELTS (bset);
376 for (bitset_windex j = 0; j < TBITSET_SIZE (bset); j++)
377 {
378 tbitset_elt *elt = elts[j];
379 if (elt)
380 tbitset_elt_remove (bset, j);
381 }
382
383 /* All the bits are zero. We could shrink the elts.
384 For now just mark BSET as known to be zero. */
385 TBITSET_ZERO_SET (bset);
386 }
387
388
389 static inline bool
390 tbitset_equal_p (bitset dst, bitset src)
391 {
392 if (src == dst)
393 return true;
394
395 tbitset_weed (dst);
396 tbitset_weed (src);
397
398 if (TBITSET_SIZE (src) != TBITSET_SIZE (dst))
399 return false;
400
401 tbitset_elts *selts = TBITSET_ELTS (src);
402 tbitset_elts *delts = TBITSET_ELTS (dst);
403
404 for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
405 {
406 tbitset_elt *selt = selts[j];
407 tbitset_elt *delt = delts[j];
408
409 if (!selt && !delt)
410 continue;
411 if ((selt && !delt) || (!selt && delt))
412 return false;
413
414 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
415 if (TBITSET_WORDS (selt)[i] != TBITSET_WORDS (delt)[i])
416 return false;
417 }
418 return true;
419 }
420
421
422 /* Copy bits from bitset SRC to bitset DST. */
423 static inline void
424 tbitset_copy_ (bitset dst, bitset src)
425 {
426 if (src == dst)
427 return;
428
429 tbitset_zero (dst);
430
431 if (BITSET_NBITS_ (dst) != BITSET_NBITS_ (src))
432 tbitset_resize (dst, BITSET_NBITS_ (src));
433
434 tbitset_elts *selts = TBITSET_ELTS (src);
435 tbitset_elts *delts = TBITSET_ELTS (dst);
436 for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
437 {
438 tbitset_elt *selt = selts[j];
439 if (selt)
440 {
441 tbitset_elt *tmp = tbitset_elt_alloc ();
442 delts[j] = tmp;
443 memcpy (TBITSET_WORDS (tmp), TBITSET_WORDS (selt),
444 sizeof (TBITSET_WORDS (selt)));
445 }
446 }
447 TBITSET_NONZERO_SET (dst);
448 }
449
450
451 /* Copy bits from bitset SRC to bitset DST. Return true if
452 bitsets different. */
453 static inline bool
454 tbitset_copy_cmp (bitset dst, bitset src)
455 {
456 if (src == dst)
457 return false;
458
459 if (TBITSET_ZERO_P (dst))
460 {
461 tbitset_copy_ (dst, src);
462 return !TBITSET_ZERO_P (src);
463 }
464
465 if (tbitset_equal_p (dst, src))
466 return false;
467
468 tbitset_copy_ (dst, src);
469 return true;
470 }
471
472
473 /* Set bit BITNO in bitset DST. */
474 static void
475 tbitset_set (bitset dst, bitset_bindex bitno)
476 {
477 bitset_windex windex = bitno / BITSET_WORD_BITS;
478
479 tbitset_elt_find (dst, bitno, TBITSET_CREATE);
480
481 dst->b.cdata[windex - dst->b.cindex] |=
482 (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
483 }
484
485
486 /* Reset bit BITNO in bitset DST. */
487 static void
488 tbitset_reset (bitset dst, bitset_bindex bitno)
489 {
490 bitset_windex windex = bitno / BITSET_WORD_BITS;
491
492 if (!tbitset_elt_find (dst, bitno, TBITSET_FIND))
493 return;
494
495 dst->b.cdata[windex - dst->b.cindex] &=
496 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
497
498 /* If all the data is zero, perhaps we should remove it now...
499 However, there is a good chance that the element will be needed
500 again soon. */
501 }
502
503
504 /* Test bit BITNO in bitset SRC. */
505 static bool
506 tbitset_test (bitset src, bitset_bindex bitno)
507 {
508 bitset_windex windex = bitno / BITSET_WORD_BITS;
509
510 return (tbitset_elt_find (src, bitno, TBITSET_FIND)
511 && ((src->b.cdata[windex - src->b.cindex]
512 >> (bitno % BITSET_WORD_BITS))
513 & 1));
514 }
515
516
517 static void
518 tbitset_free (bitset bset)
519 {
520 tbitset_zero (bset);
521 free (TBITSET_ELTS (bset));
522 }
523
524
525 /* Find list of up to NUM bits set in BSET starting from and including
526 *NEXT and store in array LIST. Return with actual number of bits
527 found and with *NEXT indicating where search stopped. */
528 static bitset_bindex
529 tbitset_list_reverse (bitset bset, bitset_bindex *list,
530 bitset_bindex num, bitset_bindex *next)
531 {
532 if (TBITSET_ZERO_P (bset))
533 return 0;
534
535 bitset_windex size = TBITSET_SIZE (bset);
536 bitset_bindex n_bits = size * TBITSET_ELT_BITS;
537 bitset_bindex rbitno = *next;
538
539 if (rbitno >= n_bits)
540 return 0;
541
542 tbitset_elts *elts = TBITSET_ELTS (bset);
543
544 bitset_bindex bitno = n_bits - (rbitno + 1);
545
546 bitset_windex windex = bitno / BITSET_WORD_BITS;
547 bitset_windex eindex = bitno / TBITSET_ELT_BITS;
548 bitset_windex woffset = windex - eindex * TBITSET_ELT_WORDS;
549
550 /* If num is 1, we could speed things up with a binary search
551 of the word of interest. */
552 bitset_bindex count = 0;
553 unsigned bitcnt = bitno % BITSET_WORD_BITS;
554 bitset_bindex bitoff = windex * BITSET_WORD_BITS;
555
556 do
557 {
558 tbitset_elt *elt = elts[eindex];
559 if (elt)
560 {
561 bitset_word *srcp = TBITSET_WORDS (elt);
562
563 do
564 {
565 bitset_word word = srcp[woffset];
566 if (bitcnt + 1 < BITSET_WORD_BITS)
567 /* We're starting in the middle of a word: smash bits to ignore. */
568 word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
569 BITSET_FOR_EACH_BIT_REVERSE(pos, word)
570 {
571 list[count++] = bitoff + pos;
572 if (count >= num)
573 {
574 *next = n_bits - (bitoff + pos);
575 return count;
576 }
577 }
578 bitoff -= BITSET_WORD_BITS;
579 bitcnt = BITSET_WORD_BITS - 1;
580 }
581 while (woffset--);
582 }
583
584 woffset = TBITSET_ELT_WORDS - 1;
585 bitoff = eindex * TBITSET_ELT_BITS - BITSET_WORD_BITS;
586 }
587 while (eindex--);
588
589 *next = n_bits - (bitoff + 1);
590 return count;
591 }
592
593
594 /* Find list of up to NUM bits set in BSET starting from and including
595 *NEXT and store in array LIST. Return with actual number of bits
596 found and with *NEXT indicating where search stopped. */
597 static bitset_bindex
598 tbitset_list (bitset bset, bitset_bindex *list,
599 bitset_bindex num, bitset_bindex *next)
600 {
601 if (TBITSET_ZERO_P (bset))
602 return 0;
603
604 bitset_bindex bitno = *next;
605 bitset_bindex count = 0;
606
607 tbitset_elts *elts = TBITSET_ELTS (bset);
608 bitset_windex size = TBITSET_SIZE (bset);
609 bitset_windex eindex = bitno / TBITSET_ELT_BITS;
610
611 if (bitno % TBITSET_ELT_BITS)
612 {
613 /* We need to start within an element. This is not very common. */
614 tbitset_elt *elt = elts[eindex];
615 if (elt)
616 {
617 bitset_word *srcp = TBITSET_WORDS (elt);
618 bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
619
620 for (bitset_windex windex = bitno / BITSET_WORD_BITS;
621 (windex - woffset) < TBITSET_ELT_WORDS; windex++)
622 {
623 bitset_word word = srcp[windex - woffset] >> (bitno % BITSET_WORD_BITS);
624
625 BITSET_FOR_EACH_BIT (pos, word)
626 {
627 list[count++] = bitno + pos;
628 if (count >= num)
629 {
630 *next = bitno + pos + 1;
631 return count;
632 }
633 }
634 bitno = (windex + 1) * BITSET_WORD_BITS;
635 }
636 }
637
638 /* Skip to next element. */
639 eindex++;
640 }
641
642 /* If num is 1, we could speed things up with a binary search
643 of the word of interest. */
644
645 for (; eindex < size; eindex++)
646 {
647 tbitset_elt *elt = elts[eindex];
648 if (!elt)
649 continue;
650
651 bitset_word *srcp = TBITSET_WORDS (elt);
652 bitset_windex windex = eindex * TBITSET_ELT_WORDS;
653 bitno = windex * BITSET_WORD_BITS;
654
655 /* Is there enough room to avoid checking in each iteration? */
656 if ((count + TBITSET_ELT_BITS) < num)
657 {
658 /* The coast is clear, plant boot! */
659
660 #if TBITSET_ELT_WORDS == 2
661 bitset_word word = srcp[0];
662 if (word)
663 BITSET_FOR_EACH_BIT (pos, word)
664 list[count++] = bitno + pos;
665 windex++;
666 bitno = windex * BITSET_WORD_BITS;
667
668 word = srcp[1];
669 if (word)
670 BITSET_FOR_EACH_BIT (pos, word)
671 list[count++] = bitno + pos;
672 windex++;
673 bitno = windex * BITSET_WORD_BITS;
674 #else
675 for (int i = 0; i < TBITSET_ELT_WORDS; i++, windex++)
676 {
677 bitset_word word = srcp[i];
678 if (word)
679 BITSET_FOR_EACH_BIT (pos, word)
680 list[count++] = bitno + pos;
681 bitno = windex * BITSET_WORD_BITS;
682 }
683 #endif
684 }
685 else
686 {
687 /* Tread more carefully since we need to check
688 if array overflows. */
689 for (int i = 0; i < TBITSET_ELT_WORDS; i++)
690 {
691 bitset_word word = srcp[i];
692 if (word)
693 BITSET_FOR_EACH_BIT (pos, word)
694 {
695 list[count++] = bitno + pos;
696 if (count >= num)
697 {
698 *next = bitno + pos + 1;
699 return count;
700 }
701 }
702 windex++;
703 bitno = windex * BITSET_WORD_BITS;
704 }
705 }
706 }
707
708 *next = bitno;
709 return count;
710 }
711
712
713 /* Ensure that any unused bits within the last element are clear. */
714 static inline void
715 tbitset_unused_clear (bitset dst)
716 {
717 bitset_bindex n_bits = BITSET_NBITS_ (dst);
718 unsigned last_bit = n_bits % TBITSET_ELT_BITS;
719
720 if (last_bit)
721 {
722 tbitset_elts *elts = TBITSET_ELTS (dst);
723
724 bitset_windex eindex = n_bits / TBITSET_ELT_BITS;
725
726 tbitset_elt *elt = elts[eindex];
727 if (elt)
728 {
729 bitset_word *srcp = TBITSET_WORDS (elt);
730
731 bitset_windex windex = n_bits / BITSET_WORD_BITS;
732 bitset_windex woffset = eindex * TBITSET_ELT_WORDS;
733
734 srcp[windex - woffset]
735 &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
736 windex++;
737 for (; (windex - woffset) < TBITSET_ELT_WORDS; windex++)
738 srcp[windex - woffset] = 0;
739 }
740 }
741 }
742
743
744 static void
745 tbitset_ones (bitset dst)
746 {
747 for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
748 {
749 /* Create new elements if they cannot be found. Perhaps
750 we should just add pointers to a ones element? */
751 tbitset_elt *elt =
752 tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
753 memset (TBITSET_WORDS (elt), -1, sizeof (TBITSET_WORDS (elt)));
754 }
755 TBITSET_NONZERO_SET (dst);
756 tbitset_unused_clear (dst);
757 }
758
759
760 static bool
761 tbitset_empty_p (bitset dst)
762 {
763 if (TBITSET_ZERO_P (dst))
764 return true;
765
766 tbitset_elts *elts = TBITSET_ELTS (dst);
767 for (bitset_windex j = 0; j < TBITSET_SIZE (dst); j++)
768 {
769 tbitset_elt *elt = elts[j];
770
771 if (elt)
772 {
773 if (!tbitset_elt_zero_p (elt))
774 return false;
775 /* Do some weeding as we go. */
776 tbitset_elt_remove (dst, j);
777 }
778 }
779
780 /* All the bits are zero. We could shrink the elts.
781 For now just mark DST as known to be zero. */
782 TBITSET_ZERO_SET (dst);
783 return true;
784 }
785
786
787 static void
788 tbitset_not (bitset dst, bitset src)
789 {
790 tbitset_resize (dst, BITSET_NBITS_ (src));
791
792 for (bitset_windex j = 0; j < TBITSET_SIZE (src); j++)
793 {
794 /* Create new elements for dst if they cannot be found
795 or substitute zero elements if src elements not found. */
796 tbitset_elt *selt =
797 tbitset_elt_find (src, j * TBITSET_ELT_BITS, TBITSET_SUBST);
798 tbitset_elt *delt =
799 tbitset_elt_find (dst, j * TBITSET_ELT_BITS, TBITSET_CREATE);
800
801 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
802 TBITSET_WORDS (delt)[i] = ~TBITSET_WORDS (selt)[i];
803 }
804 TBITSET_NONZERO_SET (dst);
805 tbitset_unused_clear (dst);
806 }
807
808
809 /* Is DST == DST | SRC? */
810 static bool
811 tbitset_subset_p (bitset dst, bitset src)
812 {
813 tbitset_elts *selts = TBITSET_ELTS (src);
814 tbitset_elts *delts = TBITSET_ELTS (dst);
815
816 bitset_windex ssize = TBITSET_SIZE (src);
817 bitset_windex dsize = TBITSET_SIZE (dst);
818
819 for (bitset_windex j = 0; j < ssize; j++)
820 {
821 tbitset_elt *selt = j < ssize ? selts[j] : 0;
822 tbitset_elt *delt = j < dsize ? delts[j] : 0;
823
824 if (!selt && !delt)
825 continue;
826
827 if (!selt)
828 selt = &tbitset_zero_elts[0];
829 if (!delt)
830 delt = &tbitset_zero_elts[0];
831
832 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
833 if (TBITSET_WORDS (delt)[i]
834 != (TBITSET_WORDS (selt)[i] | TBITSET_WORDS (delt)[i]))
835 return false;
836 }
837 return true;
838 }
839
840
841 /* Is DST & SRC == 0? */
842 static bool
843 tbitset_disjoint_p (bitset dst, bitset src)
844 {
845 tbitset_elts *selts = TBITSET_ELTS (src);
846 tbitset_elts *delts = TBITSET_ELTS (dst);
847
848 bitset_windex ssize = TBITSET_SIZE (src);
849 bitset_windex dsize = TBITSET_SIZE (dst);
850
851 for (bitset_windex j = 0; j < ssize; j++)
852 {
853 tbitset_elt *selt = j < ssize ? selts[j] : 0;
854 tbitset_elt *delt = j < dsize ? delts[j] : 0;
855
856 if (!selt || !delt)
857 continue;
858
859 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++)
860 if ((TBITSET_WORDS (selt)[i] & TBITSET_WORDS (delt)[i]))
861 return false;
862 }
863 return true;
864 }
865
866
867
868 static bool
869 tbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
870 {
871 bool changed = false;
872
873 tbitset_resize (dst, max (BITSET_NBITS_ (src1), BITSET_NBITS_ (src2)));
874
875 bitset_windex ssize1 = TBITSET_SIZE (src1);
876 bitset_windex ssize2 = TBITSET_SIZE (src2);
877 bitset_windex dsize = TBITSET_SIZE (dst);
878 bitset_windex size = ssize1;
879 if (size < ssize2)
880 size = ssize2;
881
882 tbitset_elts *selts1 = TBITSET_ELTS (src1);
883 tbitset_elts *selts2 = TBITSET_ELTS (src2);
884 tbitset_elts *delts = TBITSET_ELTS (dst);
885
886 bitset_windex j = 0;
887 for (j = 0; j < size; j++)
888 {
889 tbitset_elt *selt1 = j < ssize1 ? selts1[j] : 0;
890 tbitset_elt *selt2 = j < ssize2 ? selts2[j] : 0;
891 tbitset_elt *delt = j < dsize ? delts[j] : 0;
892
893 if (!selt1 && !selt2)
894 {
895 if (delt)
896 {
897 changed = true;
898 tbitset_elt_remove (dst, j);
899 }
900 continue;
901 }
902
903 if (!selt1)
904 selt1 = &tbitset_zero_elts[0];
905 if (!selt2)
906 selt2 = &tbitset_zero_elts[0];
907 if (!delt)
908 delt = tbitset_elt_calloc ();
909 else
910 delts[j] = 0;
911
912 bitset_word *srcp1 = TBITSET_WORDS (selt1);
913 bitset_word *srcp2 = TBITSET_WORDS (selt2);
914 bitset_word *dstp = TBITSET_WORDS (delt);
915 switch (op)
916 {
917 default:
918 abort ();
919
920 case BITSET_OP_OR:
921 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
922 {
923 bitset_word tmp = *srcp1++ | *srcp2++;
924
925 if (*dstp != tmp)
926 {
927 changed = true;
928 *dstp = tmp;
929 }
930 }
931 break;
932
933 case BITSET_OP_AND:
934 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
935 {
936 bitset_word tmp = *srcp1++ & *srcp2++;
937
938 if (*dstp != tmp)
939 {
940 changed = true;
941 *dstp = tmp;
942 }
943 }
944 break;
945
946 case BITSET_OP_XOR:
947 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
948 {
949 bitset_word tmp = *srcp1++ ^ *srcp2++;
950
951 if (*dstp != tmp)
952 {
953 changed = true;
954 *dstp = tmp;
955 }
956 }
957 break;
958
959 case BITSET_OP_ANDN:
960 for (unsigned i = 0; i < TBITSET_ELT_WORDS; i++, dstp++)
961 {
962 bitset_word tmp = *srcp1++ & ~(*srcp2++);
963
964 if (*dstp != tmp)
965 {
966 changed = true;
967 *dstp = tmp;
968 }
969 }
970 break;
971 }
972
973 if (!tbitset_elt_zero_p (delt))
974 tbitset_elt_add (dst, delt, j);
975 else
976 tbitset_elt_free (delt);
977 }
978
979 /* If we have elements of DST left over, free them all. */
980 for (; j < dsize; j++)
981 {
982 changed = true;
983
984 tbitset_elt *delt = delts[j];
985 if (delt)
986 tbitset_elt_remove (dst, j);
987 }
988
989 TBITSET_NONZERO_SET (dst);
990 return changed;
991 }
992
993
994 static bool
995 tbitset_and_cmp (bitset dst, bitset src1, bitset src2)
996 {
997 if (TBITSET_ZERO_P (src2))
998 {
999 tbitset_weed (dst);
1000 bool changed = TBITSET_ZERO_P (dst);
1001 tbitset_zero (dst);
1002 return changed;
1003 }
1004 else if (TBITSET_ZERO_P (src1))
1005 {
1006 tbitset_weed (dst);
1007 bool changed = TBITSET_ZERO_P (dst);
1008 tbitset_zero (dst);
1009 return changed;
1010 }
1011 else
1012 return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1013 }
1014
1015
1016 static void
1017 tbitset_and (bitset dst, bitset src1, bitset src2)
1018 {
1019 tbitset_and_cmp (dst, src1, src2);
1020 }
1021
1022
1023 static bool
1024 tbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1025 {
1026 if (TBITSET_ZERO_P (src2))
1027 return tbitset_copy_cmp (dst, src1);
1028 else if (TBITSET_ZERO_P (src1))
1029 {
1030 tbitset_weed (dst);
1031 bool changed = TBITSET_ZERO_P (dst);
1032 tbitset_zero (dst);
1033 return changed;
1034 }
1035 else
1036 return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1037 }
1038
1039
1040 static void
1041 tbitset_andn (bitset dst, bitset src1, bitset src2)
1042 {
1043 tbitset_andn_cmp (dst, src1, src2);
1044 }
1045
1046
1047 static bool
1048 tbitset_or_cmp (bitset dst, bitset src1, bitset src2)
1049 {
1050 if (TBITSET_ZERO_P (src2))
1051 return tbitset_copy_cmp (dst, src1);
1052 else if (TBITSET_ZERO_P (src1))
1053 return tbitset_copy_cmp (dst, src2);
1054 else
1055 return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1056 }
1057
1058
1059 static void
1060 tbitset_or (bitset dst, bitset src1, bitset src2)
1061 {
1062 tbitset_or_cmp (dst, src1, src2);
1063 }
1064
1065
1066 static bool
1067 tbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1068 {
1069 if (TBITSET_ZERO_P (src2))
1070 return tbitset_copy_cmp (dst, src1);
1071 else if (TBITSET_ZERO_P (src1))
1072 return tbitset_copy_cmp (dst, src2);
1073 else
1074 return tbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1075 }
1076
1077
1078 static void
1079 tbitset_xor (bitset dst, bitset src1, bitset src2)
1080 {
1081 tbitset_xor_cmp (dst, src1, src2);
1082 }
1083
1084
1085 static void
1086 tbitset_copy (bitset dst, bitset src)
1087 {
1088 if (BITSET_COMPATIBLE_ (dst, src))
1089 tbitset_copy_ (dst, src);
1090 else
1091 bitset_copy_ (dst, src);
1092 }
1093
1094
1095 /* Vector of operations for linked-list bitsets. */
1096 struct bitset_vtable tbitset_vtable = {
1097 tbitset_set,
1098 tbitset_reset,
1099 bitset_toggle_,
1100 tbitset_test,
1101 tbitset_resize,
1102 bitset_size_,
1103 bitset_count_,
1104 tbitset_empty_p,
1105 tbitset_ones,
1106 tbitset_zero,
1107 tbitset_copy,
1108 tbitset_disjoint_p,
1109 tbitset_equal_p,
1110 tbitset_not,
1111 tbitset_subset_p,
1112 tbitset_and,
1113 tbitset_and_cmp,
1114 tbitset_andn,
1115 tbitset_andn_cmp,
1116 tbitset_or,
1117 tbitset_or_cmp,
1118 tbitset_xor,
1119 tbitset_xor_cmp,
1120 bitset_and_or_,
1121 bitset_and_or_cmp_,
1122 bitset_andn_or_,
1123 bitset_andn_or_cmp_,
1124 bitset_or_and_,
1125 bitset_or_and_cmp_,
1126 tbitset_list,
1127 tbitset_list_reverse,
1128 tbitset_free,
1129 BITSET_TABLE
1130 };
1131
1132
1133 /* Return size of initial structure. */
1134 size_t
1135 tbitset_bytes (MAYBE_UNUSED bitset_bindex n_bits)
1136 {
1137 return sizeof (struct tbitset_struct);
1138 }
1139
1140
1141 /* Initialize a bitset. */
1142
1143 bitset
1144 tbitset_init (bitset bset, bitset_bindex n_bits)
1145 {
1146 bset->b.vtable = &tbitset_vtable;
1147
1148 bset->b.csize = TBITSET_ELT_WORDS;
1149
1150 TBITSET_ZERO_SET (bset);
1151
1152 TBITSET_ASIZE (bset) = 0;
1153 TBITSET_ELTS (bset) = 0;
1154 tbitset_resize (bset, n_bits);
1155
1156 return bset;
1157 }
1158
1159
1160 void
1161 tbitset_release_memory (void)
1162 {
1163 tbitset_free_list = 0;
1164 if (tbitset_obstack_init)
1165 {
1166 tbitset_obstack_init = false;
1167 obstack_free (&tbitset_obstack, NULL);
1168 }
1169 }