This source file includes following definitions.
- tbitset_resize
- tbitset_elt_alloc
- tbitset_elt_calloc
- tbitset_elt_free
- tbitset_elt_remove
- tbitset_elt_add
- tbitset_elt_zero_p
- tbitset_elt_find
- tbitset_weed
- tbitset_zero
- tbitset_equal_p
- tbitset_copy_
- tbitset_copy_cmp
- tbitset_set
- tbitset_reset
- tbitset_test
- tbitset_free
- tbitset_list_reverse
- tbitset_list
- tbitset_unused_clear
- tbitset_ones
- tbitset_empty_p
- tbitset_not
- tbitset_subset_p
- tbitset_disjoint_p
- tbitset_op3_cmp
- tbitset_and_cmp
- tbitset_and
- tbitset_andn_cmp
- tbitset_andn
- tbitset_or_cmp
- tbitset_or
- tbitset_xor_cmp
- tbitset_xor
- tbitset_copy
- tbitset_bytes
- tbitset_init
- tbitset_release_memory
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52 #define TBITSET_ELT_WORDS 2
53
54
55 #define TBITSET_ELT_BITS \
56 ((unsigned) (TBITSET_ELT_WORDS * BITSET_WORD_BITS))
57
58
59 typedef struct tbitset_elt_struct
60 {
61 union
62 {
63 bitset_word words[TBITSET_ELT_WORDS];
64 struct tbitset_elt_struct *next;
65 }
66 u;
67 }
68 tbitset_elt;
69
70
71 typedef tbitset_elt *tbitset_elts;
72
73
74
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];
85
86
87 static struct obstack tbitset_obstack;
88 static bool tbitset_obstack_init = false;
89 static tbitset_elt *tbitset_free_list;
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
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
106 #define TBITSET_NONZERO_SET(BSET) \
107 (TBITSET_CACHE_DISABLE (BSET), (BSET)->b.cdata = (bitset_word *)~0)
108
109
110
111 #define TBITSET_ZERO_P(BSET) ((BSET)->b.cdata == 0)
112
113
114
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
136
137 if (newsize > TBITSET_ASIZE (src))
138 {
139
140
141
142
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
156
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
169 }
170
171 BITSET_NBITS_ (src) = n_bits;
172 return n_bits;
173 }
174
175
176
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
194
195 #ifndef OBSTACK_CHUNK_SIZE
196 # define OBSTACK_CHUNK_SIZE 0
197 #endif
198
199
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
220
221 elt = (tbitset_elt *) obstack_alloc (&tbitset_obstack,
222 sizeof (tbitset_elt));
223 }
224
225 return elt;
226 }
227
228
229
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
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
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
265 elts[eindex] = elt;
266 }
267
268
269
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
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
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
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
358
359 TBITSET_ZERO_SET (bset);
360 }
361 else
362 TBITSET_NONZERO_SET (bset);
363
364 return count;
365 }
366
367
368
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
384
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
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
452
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
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
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
499
500
501 }
502
503
504
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
526
527
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
551
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
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
595
596
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
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
639 eindex++;
640 }
641
642
643
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
656 if ((count + TBITSET_ELT_BITS) < num)
657 {
658
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
688
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
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
750
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
776 tbitset_elt_remove (dst, j);
777 }
778 }
779
780
781
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
795
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
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
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
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
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
1134 size_t
1135 tbitset_bytes (MAYBE_UNUSED bitset_bindex n_bits)
1136 {
1137 return sizeof (struct tbitset_struct);
1138 }
1139
1140
1141
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 }