This source file includes following definitions.
- lbitset_elt_alloc
- lbitset_elt_calloc
- lbitset_elt_free
- lbitset_elt_unlink
- lbitset_prune
- lbitset_elt_zero_p
- lbitset_elt_link
- lbitset_elt_find
- lbitset_weed
- lbitset_zero
- lbitset_equal_p
- lbitset_copy_
- lbitset_copy
- lbitset_copy_cmp
- lbitset_resize
- lbitset_set
- lbitset_reset
- lbitset_test
- lbitset_free
- lbitset_list_reverse
- lbitset_list
- lbitset_empty_p
- lbitset_unused_clear
- lbitset_ones
- lbitset_not
- lbitset_subset_p
- lbitset_disjoint_p
- lbitset_op3_cmp
- lbitset_and_cmp
- lbitset_and
- lbitset_andn_cmp
- lbitset_andn
- lbitset_or_cmp
- lbitset_or
- lbitset_xor_cmp
- lbitset_xor
- lbitset_bytes
- lbitset_init
- lbitset_release_memory
- debug_lbitset
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21 #include <config.h>
22
23 #include "bitset/list.h"
24
25 #include <stddef.h>
26 #include <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29
30 #include "obstack.h"
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50 #define LBITSET_ELT_WORDS 2
51
52 typedef bitset_word lbitset_word;
53
54 #define LBITSET_WORD_BITS BITSET_WORD_BITS
55
56
57 #define LBITSET_ELT_BITS \
58 ((unsigned) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
59
60
61
62 typedef struct lbitset_elt_struct
63 {
64 struct lbitset_elt_struct *next;
65 struct lbitset_elt_struct *prev;
66 bitset_windex index;
67 bitset_word words[LBITSET_ELT_WORDS];
68 }
69 lbitset_elt;
70
71
72 enum lbitset_find_mode
73 { LBITSET_FIND, LBITSET_CREATE, LBITSET_SUBST };
74
75 static lbitset_elt lbitset_zero_elts[3];
76
77
78 static struct obstack lbitset_obstack;
79 static bool lbitset_obstack_init = false;
80 static lbitset_elt *lbitset_free_list;
81
82 extern void debug_lbitset (bitset);
83
84 #define LBITSET_CURRENT1(X) \
85 ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
86
87 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
88
89 #define LBITSET_HEAD(X) ((X)->l.head)
90 #define LBITSET_TAIL(X) ((X)->l.tail)
91
92
93 static inline lbitset_elt *
94 lbitset_elt_alloc (void)
95 {
96 lbitset_elt *elt;
97
98 if (lbitset_free_list != 0)
99 {
100 elt = lbitset_free_list;
101 lbitset_free_list = elt->next;
102 }
103 else
104 {
105 if (!lbitset_obstack_init)
106 {
107 lbitset_obstack_init = true;
108
109
110
111 #ifndef OBSTACK_CHUNK_SIZE
112 # define OBSTACK_CHUNK_SIZE 0
113 #endif
114
115
116
117 #ifndef OBSTACK_CHUNK_ALLOC
118 # define OBSTACK_CHUNK_ALLOC xmalloc
119 #endif
120
121 #ifndef OBSTACK_CHUNK_FREE
122 # define OBSTACK_CHUNK_FREE free
123 #endif
124
125 #if !(defined __GNUC__ || defined __clang__)
126 # define __alignof__(type) 0
127 #endif
128
129 obstack_specify_allocation (&lbitset_obstack, OBSTACK_CHUNK_SIZE,
130 __alignof__ (lbitset_elt),
131 OBSTACK_CHUNK_ALLOC,
132 OBSTACK_CHUNK_FREE);
133 }
134
135
136
137 elt = (lbitset_elt *) obstack_alloc (&lbitset_obstack,
138 sizeof (lbitset_elt));
139 }
140
141 return elt;
142 }
143
144
145
146 static inline lbitset_elt *
147 lbitset_elt_calloc (void)
148 {
149 lbitset_elt *elt = lbitset_elt_alloc ();
150 memset (elt->words, 0, sizeof (elt->words));
151 return elt;
152 }
153
154
155 static inline void
156 lbitset_elt_free (lbitset_elt *elt)
157 {
158 elt->next = lbitset_free_list;
159 lbitset_free_list = elt;
160 }
161
162
163
164 static inline void
165 lbitset_elt_unlink (bitset bset, lbitset_elt *elt)
166 {
167 lbitset_elt *next = elt->next;
168 lbitset_elt *prev = elt->prev;
169
170 if (prev)
171 prev->next = next;
172
173 if (next)
174 next->prev = prev;
175
176 if (LBITSET_HEAD (bset) == elt)
177 LBITSET_HEAD (bset) = next;
178 if (LBITSET_TAIL (bset) == elt)
179 LBITSET_TAIL (bset) = prev;
180
181
182
183
184 if (LBITSET_CURRENT (bset) == elt)
185 {
186 if (next)
187 {
188 bset->b.cdata = next->words;
189 bset->b.cindex = next->index;
190 }
191 else if (prev)
192 {
193 bset->b.cdata = prev->words;
194 bset->b.cindex = prev->index;
195 }
196 else
197 {
198 bset->b.csize = 0;
199 bset->b.cdata = 0;
200 }
201 }
202
203 lbitset_elt_free (elt);
204 }
205
206
207
208
209 static inline void
210 lbitset_prune (bitset bset, lbitset_elt *elt)
211 {
212 if (!elt)
213 return;
214
215 if (elt->prev)
216 {
217 LBITSET_TAIL (bset) = elt->prev;
218 bset->b.cdata = elt->prev->words;
219 bset->b.cindex = elt->prev->index;
220 elt->prev->next = 0;
221 }
222 else
223 {
224 LBITSET_HEAD (bset) = 0;
225 LBITSET_TAIL (bset) = 0;
226 bset->b.cdata = 0;
227 bset->b.csize = 0;
228 }
229
230 lbitset_elt *next;
231 for (; elt; elt = next)
232 {
233 next = elt->next;
234 lbitset_elt_free (elt);
235 }
236 }
237
238
239
240 static inline bool
241 lbitset_elt_zero_p (lbitset_elt *elt)
242 {
243 for (int i = 0; i < LBITSET_ELT_WORDS; i++)
244 if (elt->words[i])
245 return false;
246 return true;
247 }
248
249
250
251 static inline void
252 lbitset_elt_link (bitset bset, lbitset_elt *elt)
253 {
254 bitset_windex windex = elt->index;
255
256 lbitset_elt *current = bset->b.csize ? LBITSET_CURRENT (bset) : LBITSET_HEAD (bset);
257
258
259 if (LBITSET_HEAD (bset) == 0)
260 {
261 elt->next = elt->prev = 0;
262 LBITSET_HEAD (bset) = elt;
263 LBITSET_TAIL (bset) = elt;
264 }
265
266
267
268 else if (windex < bset->b.cindex)
269 {
270 lbitset_elt *ptr;
271 for (ptr = current;
272 ptr->prev && ptr->prev->index > windex; ptr = ptr->prev)
273 continue;
274
275 if (ptr->prev)
276 ptr->prev->next = elt;
277 else
278 LBITSET_HEAD (bset) = elt;
279
280 elt->prev = ptr->prev;
281 elt->next = ptr;
282 ptr->prev = elt;
283 }
284
285
286 else
287 {
288 lbitset_elt *ptr;
289 for (ptr = current;
290 ptr->next && ptr->next->index < windex; ptr = ptr->next)
291 continue;
292
293 if (ptr->next)
294 ptr->next->prev = elt;
295 else
296 LBITSET_TAIL (bset) = elt;
297
298 elt->next = ptr->next;
299 elt->prev = ptr;
300 ptr->next = elt;
301 }
302
303
304 bset->b.cindex = windex;
305 bset->b.csize = LBITSET_ELT_WORDS;
306 bset->b.cdata = elt->words;
307 }
308
309
310 static lbitset_elt *
311 lbitset_elt_find (bitset bset, bitset_windex windex,
312 enum lbitset_find_mode mode)
313 {
314 lbitset_elt *current;
315
316 if (bset->b.csize)
317 {
318 current = LBITSET_CURRENT (bset);
319
320 if ((windex - bset->b.cindex) < bset->b.csize)
321 return current;
322 }
323 else
324 {
325 current = LBITSET_HEAD (bset);
326 }
327
328 if (current)
329 {
330 lbitset_elt *elt;
331 if (windex < bset->b.cindex)
332 {
333 for (elt = current;
334 elt->prev && elt->index > windex; elt = elt->prev)
335 continue;
336 }
337 else
338 {
339 for (elt = current;
340 elt->next && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
341 elt = elt->next)
342 continue;
343 }
344
345
346
347 if (windex - elt->index < LBITSET_ELT_WORDS)
348 {
349 bset->b.cindex = elt->index;
350 bset->b.csize = LBITSET_ELT_WORDS;
351 bset->b.cdata = elt->words;
352 return elt;
353 }
354 }
355
356 switch (mode)
357 {
358 default:
359 abort ();
360
361 case LBITSET_FIND:
362 return 0;
363
364 case LBITSET_CREATE:
365 windex -= windex % LBITSET_ELT_WORDS;
366 lbitset_elt *elt = lbitset_elt_calloc ();
367 elt->index = windex;
368 lbitset_elt_link (bset, elt);
369 return elt;
370
371 case LBITSET_SUBST:
372 return &lbitset_zero_elts[0];
373 }
374 }
375
376
377
378 static inline void
379 lbitset_weed (bitset bset)
380 {
381 lbitset_elt *next;
382 for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = next)
383 {
384 next = elt->next;
385 if (lbitset_elt_zero_p (elt))
386 lbitset_elt_unlink (bset, elt);
387 }
388 }
389
390
391
392 static void
393 lbitset_zero (bitset bset)
394 {
395 lbitset_elt *head = LBITSET_HEAD (bset);
396 if (!head)
397 return;
398
399
400 lbitset_prune (bset, head);
401 }
402
403
404
405 static inline bool
406 lbitset_equal_p (bitset dst, bitset src)
407 {
408 if (src == dst)
409 return true;
410
411 lbitset_weed (src);
412 lbitset_weed (dst);
413 lbitset_elt *selt;
414 lbitset_elt *delt;
415 for (selt = LBITSET_HEAD (src), delt = LBITSET_HEAD (dst);
416 selt && delt; selt = selt->next, delt = delt->next)
417 {
418 if (selt->index != delt->index)
419 return false;
420
421 for (int j = 0; j < LBITSET_ELT_WORDS; j++)
422 if (delt->words[j] != selt->words[j])
423 return false;
424 }
425 return !selt && !delt;
426 }
427
428
429
430 static inline void
431 lbitset_copy_ (bitset dst, bitset src)
432 {
433 if (src == dst)
434 return;
435
436 lbitset_zero (dst);
437
438 lbitset_elt *head = LBITSET_HEAD (src);
439 if (!head)
440 return;
441
442 lbitset_elt *prev = 0;
443 lbitset_elt *tmp;
444 for (lbitset_elt *elt = head; elt; elt = elt->next)
445 {
446 tmp = lbitset_elt_alloc ();
447 tmp->index = elt->index;
448 tmp->prev = prev;
449 tmp->next = 0;
450 if (prev)
451 prev->next = tmp;
452 else
453 LBITSET_HEAD (dst) = tmp;
454 prev = tmp;
455
456 memcpy (tmp->words, elt->words, sizeof (elt->words));
457 }
458 LBITSET_TAIL (dst) = tmp;
459
460 dst->b.csize = LBITSET_ELT_WORDS;
461 dst->b.cdata = LBITSET_HEAD (dst)->words;
462 dst->b.cindex = LBITSET_HEAD (dst)->index;
463 }
464
465
466 static void
467 lbitset_copy (bitset dst, bitset src)
468 {
469 if (BITSET_COMPATIBLE_ (dst, src))
470 lbitset_copy_ (dst, src);
471 else
472 bitset_copy_ (dst, src);
473 }
474
475
476
477 static inline bool
478 lbitset_copy_cmp (bitset dst, bitset src)
479 {
480 if (src == dst)
481 return false;
482
483 if (!LBITSET_HEAD (dst))
484 {
485 lbitset_copy (dst, src);
486 return LBITSET_HEAD (src) != 0;
487 }
488
489 if (lbitset_equal_p (dst, src))
490 return false;
491
492 lbitset_copy (dst, src);
493 return true;
494 }
495
496
497 static bitset_bindex
498 lbitset_resize (bitset src, bitset_bindex size)
499 {
500 BITSET_NBITS_ (src) = size;
501
502
503 return size;
504 }
505
506
507 static void
508 lbitset_set (bitset dst, bitset_bindex bitno)
509 {
510 bitset_windex windex = bitno / BITSET_WORD_BITS;
511
512 lbitset_elt_find (dst, windex, LBITSET_CREATE);
513
514 dst->b.cdata[windex - dst->b.cindex] |=
515 (bitset_word) 1 << (bitno % BITSET_WORD_BITS);
516 }
517
518
519
520 static void
521 lbitset_reset (bitset dst, bitset_bindex bitno)
522 {
523 bitset_windex windex = bitno / BITSET_WORD_BITS;
524
525 if (!lbitset_elt_find (dst, windex, LBITSET_FIND))
526 return;
527
528 dst->b.cdata[windex - dst->b.cindex] &=
529 ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
530
531
532 }
533
534
535
536 static bool
537 lbitset_test (bitset src, bitset_bindex bitno)
538 {
539 bitset_windex windex = bitno / BITSET_WORD_BITS;
540
541 return (lbitset_elt_find (src, windex, LBITSET_FIND)
542 && ((src->b.cdata[windex - src->b.cindex]
543 >> (bitno % BITSET_WORD_BITS))
544 & 1));
545 }
546
547
548 static void
549 lbitset_free (bitset bset)
550 {
551 lbitset_zero (bset);
552 }
553
554
555
556
557
558 static bitset_bindex
559 lbitset_list_reverse (bitset bset, bitset_bindex *list,
560 bitset_bindex num, bitset_bindex *next)
561 {
562 lbitset_elt *elt = LBITSET_TAIL (bset);
563 if (!elt)
564 return 0;
565
566 bitset_bindex n_bits = (elt->index + LBITSET_ELT_WORDS) * BITSET_WORD_BITS;
567 bitset_bindex rbitno = *next;
568
569 if (rbitno >= n_bits)
570 return 0;
571
572 bitset_bindex bitno = n_bits - (rbitno + 1);
573
574 bitset_windex windex = bitno / BITSET_WORD_BITS;
575
576
577 for (; elt && elt->index > windex; elt = elt->prev)
578 continue;
579
580 if (!elt)
581 return 0;
582
583 unsigned bitcnt;
584 if (windex >= elt->index + LBITSET_ELT_WORDS)
585 {
586
587
588 bitcnt = BITSET_WORD_BITS - 1;
589 windex = elt->index + LBITSET_ELT_WORDS - 1;
590 }
591 else
592 {
593 bitcnt = bitno % BITSET_WORD_BITS;
594 }
595
596 bitset_bindex count = 0;
597 bitset_bindex bitoff = windex * BITSET_WORD_BITS;
598
599
600
601
602 while (elt)
603 {
604 bitset_word *srcp = elt->words;
605
606 for (; (windex - elt->index) < LBITSET_ELT_WORDS;
607 windex--)
608 {
609 bitset_word word = srcp[windex - elt->index];
610 if (bitcnt + 1 < BITSET_WORD_BITS)
611
612 word &= ((bitset_word) 1 << (bitcnt + 1)) - 1;
613 BITSET_FOR_EACH_BIT_REVERSE(pos, word)
614 {
615 list[count++] = bitoff + pos;
616 if (count >= num)
617 {
618 *next = n_bits - (bitoff + pos);
619 return count;
620 }
621 }
622 bitoff -= BITSET_WORD_BITS;
623 bitcnt = BITSET_WORD_BITS - 1;
624 }
625
626 elt = elt->prev;
627 if (elt)
628 {
629 windex = elt->index + LBITSET_ELT_WORDS - 1;
630 bitoff = windex * BITSET_WORD_BITS;
631 }
632 }
633
634 *next = n_bits - (bitoff + 1);
635 return count;
636 }
637
638
639
640
641
642 static bitset_bindex
643 lbitset_list (bitset bset, bitset_bindex *list,
644 bitset_bindex num, bitset_bindex *next)
645 {
646 lbitset_elt *head = LBITSET_HEAD (bset);
647 if (!head)
648 return 0;
649
650 bitset_windex windex;
651 lbitset_elt *elt;
652
653 bitset_bindex bitno = *next;
654 bitset_bindex count = 0;
655
656 if (!bitno)
657 {
658
659
660
661 elt = head;
662 windex = elt->index;
663 bitno = windex * BITSET_WORD_BITS;
664 }
665 else
666 {
667 windex = bitno / BITSET_WORD_BITS;
668
669
670 for (elt = head;
671 elt && (elt->index + LBITSET_ELT_WORDS - 1) < windex;
672 elt = elt->next)
673 continue;
674
675 if (!elt)
676 return 0;
677
678 if (windex < elt->index)
679 {
680 windex = elt->index;
681 bitno = windex * BITSET_WORD_BITS;
682 }
683 else
684 {
685 bitset_word *srcp = elt->words;
686
687
688
689 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
690 {
691 bitset_word word = srcp[windex - elt->index] >> (bitno % BITSET_WORD_BITS);
692 BITSET_FOR_EACH_BIT (pos, word)
693 {
694 list[count++] = bitno + pos;
695 if (count >= num)
696 {
697 *next = bitno + pos + 1;
698 return count;
699 }
700 }
701 bitno = (windex + 1) * BITSET_WORD_BITS;
702 }
703
704 elt = elt->next;
705 if (elt)
706 {
707 windex = elt->index;
708 bitno = windex * BITSET_WORD_BITS;
709 }
710 }
711 }
712
713 while (elt)
714 {
715 bitset_word *srcp = elt->words;
716
717
718 if ((count + LBITSET_ELT_BITS) < num)
719 {
720
721
722 #if LBITSET_ELT_WORDS == 2
723 bitset_word word = srcp[0];
724 if (word)
725 BITSET_FOR_EACH_BIT (pos, word)
726 list[count++] = bitno + pos;
727 windex++;
728 bitno = windex * BITSET_WORD_BITS;
729
730 word = srcp[1];
731 if (word)
732 BITSET_FOR_EACH_BIT (pos, word)
733 list[count++] = bitno + pos;
734 windex++;
735 bitno = windex * BITSET_WORD_BITS;
736 #else
737 for (int i = 0; i < LBITSET_ELT_WORDS; i++)
738 {
739 bitset_word word = srcp[i];
740 if (word)
741 BITSET_FOR_EACH_BIT (pos, word)
742 list[count++] = bitno + pos;
743 windex++;
744 bitno = windex * BITSET_WORD_BITS;
745 }
746 #endif
747 }
748 else
749 {
750
751
752 for (int i = 0; i < LBITSET_ELT_WORDS; i++)
753 {
754 bitset_word word = srcp[i];
755 if (word)
756 BITSET_FOR_EACH_BIT (pos, word)
757 {
758 list[count++] = bitno + pos;
759 if (count >= num)
760 {
761 *next = bitno + pos + 1;
762 return count;
763 }
764 }
765 windex++;
766 bitno = windex * BITSET_WORD_BITS;
767 }
768 }
769
770 elt = elt->next;
771 if (elt)
772 {
773 windex = elt->index;
774 bitno = windex * BITSET_WORD_BITS;
775 }
776 }
777
778 *next = bitno;
779 return count;
780 }
781
782
783 static bool
784 lbitset_empty_p (bitset dst)
785 {
786 lbitset_elt *elt;
787 lbitset_elt *next;
788
789 for (elt = LBITSET_HEAD (dst); elt; elt = next)
790 {
791 next = elt->next;
792 if (!lbitset_elt_zero_p (elt))
793 return false;
794
795 lbitset_elt_unlink (dst, elt);
796 }
797
798 return true;
799 }
800
801
802
803 static inline void
804 lbitset_unused_clear (bitset dst)
805 {
806 bitset_bindex n_bits = BITSET_SIZE_ (dst);
807 unsigned last_bit = n_bits % LBITSET_ELT_BITS;
808
809 if (last_bit)
810 {
811 lbitset_elt *elt = LBITSET_TAIL (dst);
812 bitset_word *srcp = elt->words;
813 bitset_windex windex = n_bits / BITSET_WORD_BITS;
814
815 srcp[windex - elt->index]
816 &= ((bitset_word) 1 << (last_bit % BITSET_WORD_BITS)) - 1;
817 windex++;
818
819 for (; (windex - elt->index) < LBITSET_ELT_WORDS; windex++)
820 srcp[windex - elt->index] = 0;
821 }
822 }
823
824
825 static void
826 lbitset_ones (bitset dst)
827 {
828
829
830
831
832
833 bitset_windex windex
834 = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
835
836 for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
837 {
838
839 lbitset_elt *elt = lbitset_elt_find (dst, i, LBITSET_CREATE);
840 memset (elt->words, -1, sizeof (elt->words));
841 }
842
843 lbitset_unused_clear (dst);
844 }
845
846
847 static void
848 lbitset_not (bitset dst, bitset src)
849 {
850 bitset_windex windex
851 = (BITSET_SIZE_ (dst) + BITSET_WORD_BITS - 1) / BITSET_WORD_BITS;
852
853 for (bitset_windex i = 0; i < windex; i += LBITSET_ELT_WORDS)
854 {
855
856
857 lbitset_elt *selt = lbitset_elt_find (src, i, LBITSET_SUBST);
858 lbitset_elt *delt = lbitset_elt_find (dst, i, LBITSET_CREATE);
859
860 for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
861 delt->words[j] = ~selt->words[j];
862 }
863 lbitset_unused_clear (dst);
864 lbitset_weed (dst);
865 }
866
867
868
869 static bool
870 lbitset_subset_p (bitset dst, bitset src)
871 {
872 for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
873 selt || delt; selt = selt->next, delt = delt->next)
874 {
875 if (!selt)
876 selt = &lbitset_zero_elts[0];
877 else if (!delt)
878 delt = &lbitset_zero_elts[0];
879 else if (selt->index != delt->index)
880 {
881 if (selt->index < delt->index)
882 {
883 lbitset_zero_elts[2].next = delt;
884 delt = &lbitset_zero_elts[2];
885 }
886 else
887 {
888 lbitset_zero_elts[1].next = selt;
889 selt = &lbitset_zero_elts[1];
890 }
891 }
892
893 for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
894 if (delt->words[j] != (selt->words[j] | delt->words[j]))
895 return false;
896 }
897 return true;
898 }
899
900
901
902 static bool
903 lbitset_disjoint_p (bitset dst, bitset src)
904 {
905 for (lbitset_elt *selt = LBITSET_HEAD (src), *delt = LBITSET_HEAD (dst);
906 selt && delt; selt = selt->next, delt = delt->next)
907 {
908 if (selt->index != delt->index)
909 {
910 if (selt->index < delt->index)
911 {
912 lbitset_zero_elts[2].next = delt;
913 delt = &lbitset_zero_elts[2];
914 }
915 else
916 {
917 lbitset_zero_elts[1].next = selt;
918 selt = &lbitset_zero_elts[1];
919 }
920
921
922 continue;
923 }
924
925 for (unsigned j = 0; j < LBITSET_ELT_WORDS; j++)
926 if (selt->words[j] & delt->words[j])
927 return false;
928 }
929 return true;
930 }
931
932
933 static bool
934 lbitset_op3_cmp (bitset dst, bitset src1, bitset src2, enum bitset_ops op)
935 {
936 lbitset_elt *selt1 = LBITSET_HEAD (src1);
937 lbitset_elt *selt2 = LBITSET_HEAD (src2);
938 lbitset_elt *delt = LBITSET_HEAD (dst);
939 bool changed = false;
940
941 LBITSET_HEAD (dst) = 0;
942 dst->b.csize = 0;
943
944 bitset_windex windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
945 bitset_windex windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
946
947 while (selt1 || selt2)
948 {
949 bitset_windex windex;
950 lbitset_elt *stmp1;
951 lbitset_elt *stmp2;
952
953
954
955 if (windex1 == windex2)
956 {
957 windex = windex1;
958 stmp1 = selt1;
959 stmp2 = selt2;
960 selt1 = selt1->next;
961 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
962 selt2 = selt2->next;
963 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
964 }
965 else if (windex1 < windex2)
966 {
967 windex = windex1;
968 stmp1 = selt1;
969 stmp2 = &lbitset_zero_elts[0];
970 selt1 = selt1->next;
971 windex1 = (selt1) ? selt1->index : BITSET_WINDEX_MAX;
972 }
973 else
974 {
975 windex = windex2;
976 stmp1 = &lbitset_zero_elts[0];
977 stmp2 = selt2;
978 selt2 = selt2->next;
979 windex2 = (selt2) ? selt2->index : BITSET_WINDEX_MAX;
980 }
981
982
983
984 lbitset_elt *dtmp;
985 while (delt && delt->index < windex)
986 {
987 changed = true;
988 dtmp = delt;
989 delt = delt->next;
990 lbitset_elt_free (dtmp);
991 }
992 if (delt && delt->index == windex)
993 {
994 dtmp = delt;
995 delt = delt->next;
996 }
997 else
998 dtmp = lbitset_elt_calloc ();
999
1000
1001
1002 bitset_word *srcp1 = stmp1->words;
1003 bitset_word *srcp2 = stmp2->words;
1004 bitset_word *dstp = dtmp->words;
1005 switch (op)
1006 {
1007 default:
1008 abort ();
1009
1010 case BITSET_OP_OR:
1011 for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1012 {
1013 bitset_word tmp = *srcp1++ | *srcp2++;
1014
1015 if (*dstp != tmp)
1016 {
1017 changed = true;
1018 *dstp = tmp;
1019 }
1020 }
1021 break;
1022
1023 case BITSET_OP_AND:
1024 for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1025 {
1026 bitset_word tmp = *srcp1++ & *srcp2++;
1027
1028 if (*dstp != tmp)
1029 {
1030 changed = true;
1031 *dstp = tmp;
1032 }
1033 }
1034 break;
1035
1036 case BITSET_OP_XOR:
1037 for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1038 {
1039 bitset_word tmp = *srcp1++ ^ *srcp2++;
1040
1041 if (*dstp != tmp)
1042 {
1043 changed = true;
1044 *dstp = tmp;
1045 }
1046 }
1047 break;
1048
1049 case BITSET_OP_ANDN:
1050 for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++, dstp++)
1051 {
1052 bitset_word tmp = *srcp1++ & ~(*srcp2++);
1053
1054 if (*dstp != tmp)
1055 {
1056 changed = true;
1057 *dstp = tmp;
1058 }
1059 }
1060 break;
1061 }
1062
1063 if (!lbitset_elt_zero_p (dtmp))
1064 {
1065 dtmp->index = windex;
1066
1067 lbitset_elt_link (dst, dtmp);
1068 }
1069 else
1070 {
1071 lbitset_elt_free (dtmp);
1072 }
1073 }
1074
1075
1076 if (delt)
1077 {
1078 changed = true;
1079 lbitset_prune (dst, delt);
1080 }
1081
1082 return changed;
1083 }
1084
1085
1086 static bool
1087 lbitset_and_cmp (bitset dst, bitset src1, bitset src2)
1088 {
1089 lbitset_elt *selt1 = LBITSET_HEAD (src1);
1090 lbitset_elt *selt2 = LBITSET_HEAD (src2);
1091
1092 if (!selt2)
1093 {
1094 lbitset_weed (dst);
1095 bool changed = !LBITSET_HEAD (dst);
1096 lbitset_zero (dst);
1097 return changed;
1098 }
1099 else if (!selt1)
1100 {
1101 lbitset_weed (dst);
1102 bool changed = !LBITSET_HEAD (dst);
1103 lbitset_zero (dst);
1104 return changed;
1105 }
1106 else
1107 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_AND);
1108 }
1109
1110
1111 static void
1112 lbitset_and (bitset dst, bitset src1, bitset src2)
1113 {
1114 lbitset_and_cmp (dst, src1, src2);
1115 }
1116
1117
1118 static bool
1119 lbitset_andn_cmp (bitset dst, bitset src1, bitset src2)
1120 {
1121 lbitset_elt *selt1 = LBITSET_HEAD (src1);
1122 lbitset_elt *selt2 = LBITSET_HEAD (src2);
1123
1124 if (!selt2)
1125 {
1126 return lbitset_copy_cmp (dst, src1);
1127 }
1128 else if (!selt1)
1129 {
1130 lbitset_weed (dst);
1131 bool changed = !LBITSET_HEAD (dst);
1132 lbitset_zero (dst);
1133 return changed;
1134 }
1135 else
1136 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_ANDN);
1137 }
1138
1139
1140 static void
1141 lbitset_andn (bitset dst, bitset src1, bitset src2)
1142 {
1143 lbitset_andn_cmp (dst, src1, src2);
1144 }
1145
1146
1147 static bool
1148 lbitset_or_cmp (bitset dst, bitset src1, bitset src2)
1149 {
1150 lbitset_elt *selt1 = LBITSET_HEAD (src1);
1151 lbitset_elt *selt2 = LBITSET_HEAD (src2);
1152
1153 if (!selt2)
1154 return lbitset_copy_cmp (dst, src1);
1155 else if (!selt1)
1156 return lbitset_copy_cmp (dst, src2);
1157 else
1158 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_OR);
1159 }
1160
1161
1162 static void
1163 lbitset_or (bitset dst, bitset src1, bitset src2)
1164 {
1165 lbitset_or_cmp (dst, src1, src2);
1166 }
1167
1168
1169 static bool
1170 lbitset_xor_cmp (bitset dst, bitset src1, bitset src2)
1171 {
1172 lbitset_elt *selt1 = LBITSET_HEAD (src1);
1173 lbitset_elt *selt2 = LBITSET_HEAD (src2);
1174
1175 if (!selt2)
1176 return lbitset_copy_cmp (dst, src1);
1177 else if (!selt1)
1178 return lbitset_copy_cmp (dst, src2);
1179 else
1180 return lbitset_op3_cmp (dst, src1, src2, BITSET_OP_XOR);
1181 }
1182
1183
1184 static void
1185 lbitset_xor (bitset dst, bitset src1, bitset src2)
1186 {
1187 lbitset_xor_cmp (dst, src1, src2);
1188 }
1189
1190
1191
1192
1193 struct bitset_vtable lbitset_vtable = {
1194 lbitset_set,
1195 lbitset_reset,
1196 bitset_toggle_,
1197 lbitset_test,
1198 lbitset_resize,
1199 bitset_size_,
1200 bitset_count_,
1201 lbitset_empty_p,
1202 lbitset_ones,
1203 lbitset_zero,
1204 lbitset_copy,
1205 lbitset_disjoint_p,
1206 lbitset_equal_p,
1207 lbitset_not,
1208 lbitset_subset_p,
1209 lbitset_and,
1210 lbitset_and_cmp,
1211 lbitset_andn,
1212 lbitset_andn_cmp,
1213 lbitset_or,
1214 lbitset_or_cmp,
1215 lbitset_xor,
1216 lbitset_xor_cmp,
1217 bitset_and_or_,
1218 bitset_and_or_cmp_,
1219 bitset_andn_or_,
1220 bitset_andn_or_cmp_,
1221 bitset_or_and_,
1222 bitset_or_and_cmp_,
1223 lbitset_list,
1224 lbitset_list_reverse,
1225 lbitset_free,
1226 BITSET_LIST
1227 };
1228
1229
1230
1231 size_t
1232 lbitset_bytes (MAYBE_UNUSED bitset_bindex n_bits)
1233 {
1234 return sizeof (struct lbitset_struct);
1235 }
1236
1237
1238
1239 bitset
1240 lbitset_init (bitset bset, MAYBE_UNUSED bitset_bindex n_bits)
1241 {
1242 BITSET_NBITS_ (bset) = n_bits;
1243 bset->b.vtable = &lbitset_vtable;
1244 return bset;
1245 }
1246
1247
1248 void
1249 lbitset_release_memory (void)
1250 {
1251 lbitset_free_list = 0;
1252 if (lbitset_obstack_init)
1253 {
1254 lbitset_obstack_init = false;
1255 obstack_free (&lbitset_obstack, NULL);
1256 }
1257 }
1258
1259
1260
1261 void
1262 debug_lbitset (bitset bset)
1263 {
1264 if (!bset)
1265 return;
1266
1267 for (lbitset_elt *elt = LBITSET_HEAD (bset); elt; elt = elt->next)
1268 {
1269 fprintf (stderr, "Elt %lu\n", (unsigned long) elt->index);
1270 for (unsigned i = 0; i < LBITSET_ELT_WORDS; i++)
1271 {
1272 bitset_word word = elt->words[i];
1273
1274 fprintf (stderr, " Word %u:", i);
1275 for (unsigned j = 0; j < LBITSET_WORD_BITS; j++)
1276 if ((word & ((bitset_word) 1 << j)))
1277 fprintf (stderr, " %u", j);
1278 fprintf (stderr, "\n");
1279 }
1280 }
1281 }