1 /* Functions to support link list bitsets.
3 Copyright (C) 2002-2004, 2006, 2009-2011 Free Software Foundation,
6 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
8 This program is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with this program. If not, see <http://www.gnu.org/licenses/>. */
31 /* This file implements linked-list bitsets. These bitsets can be of
32 arbitrary length and are more efficient than arrays of bits for
35 Usually if all the bits in an element are zero we remove the element
36 from the list. However, a side effect of the bit caching is that we
37 do not always notice when an element becomes zero. Hence the
38 lbitset_weed function which removes zero elements. */
41 /* Number of words to use for each element. The larger the value the
42 greater the size of the cache and the shorter the time to find a given bit
43 but the more memory wasted for sparse bitsets and the longer the time
44 to search for set bits.
46 The routines that dominate timing profiles are lbitset_elt_find
47 and lbitset_elt_link, especially when accessing the bits randomly. */
49 #define LBITSET_ELT_WORDS 2
51 typedef bitset_word lbitset_word
;
53 #define LBITSET_WORD_BITS BITSET_WORD_BITS
55 /* Number of bits stored in each element. */
56 #define LBITSET_ELT_BITS \
57 ((unsigned int) (LBITSET_ELT_WORDS * LBITSET_WORD_BITS))
59 /* Lbitset element. We use an array of bits for each element.
60 These are linked together in a doubly-linked list. */
61 typedef struct lbitset_elt_struct
63 struct lbitset_elt_struct
*next
; /* Next element. */
64 struct lbitset_elt_struct
*prev
; /* Previous element. */
65 bitset_windex index
; /* bitno / BITSET_WORD_BITS. */
66 bitset_word words
[LBITSET_ELT_WORDS
]; /* Bits that are set. */
71 enum lbitset_find_mode
72 { LBITSET_FIND
, LBITSET_CREATE
, LBITSET_SUBST
};
74 static lbitset_elt lbitset_zero_elts
[3]; /* Elements of all zero bits. */
76 /* Obstack to allocate bitset elements from. */
77 static struct obstack lbitset_obstack
;
78 static bool lbitset_obstack_init
= false;
79 static lbitset_elt
*lbitset_free_list
; /* Free list of bitset elements. */
81 extern void debug_lbitset (bitset
);
83 #define LBITSET_CURRENT1(X) \
84 ((lbitset_elt *) (void *) ((char *) (X) - offsetof (lbitset_elt, words)))
86 #define LBITSET_CURRENT(X) LBITSET_CURRENT1((X)->b.cdata)
88 #define LBITSET_HEAD(X) ((X)->l.head)
89 #define LBITSET_TAIL(X) ((X)->l.tail)
91 /* Allocate a lbitset element. The bits are not cleared. */
92 static inline lbitset_elt
*
93 lbitset_elt_alloc (void)
97 if (lbitset_free_list
!= 0)
99 elt
= lbitset_free_list
;
100 lbitset_free_list
= elt
->next
;
104 if (!lbitset_obstack_init
)
106 lbitset_obstack_init
= true;
108 /* Let particular systems override the size of a chunk. */
110 #ifndef OBSTACK_CHUNK_SIZE
111 #define OBSTACK_CHUNK_SIZE 0
114 /* Let them override the alloc and free routines too. */
116 #ifndef OBSTACK_CHUNK_ALLOC
117 #define OBSTACK_CHUNK_ALLOC xmalloc
120 #ifndef OBSTACK_CHUNK_FREE
121 #define OBSTACK_CHUNK_FREE free
124 #if ! defined __GNUC__ || __GNUC__ < 2
125 #define __alignof__(type) 0
128 obstack_specify_allocation (&lbitset_obstack
, OBSTACK_CHUNK_SIZE
,
129 __alignof__ (lbitset_elt
),
134 /* Perhaps we should add a number of new elements to the free
136 elt
= (lbitset_elt
*) obstack_alloc (&lbitset_obstack
,
137 sizeof (lbitset_elt
));
144 /* Allocate a lbitset element. The bits are cleared. */
145 static inline lbitset_elt
*
146 lbitset_elt_calloc (void)
150 elt
= lbitset_elt_alloc ();
151 memset (elt
->words
, 0, sizeof (elt
->words
));
157 lbitset_elt_free (lbitset_elt
*elt
)
159 elt
->next
= lbitset_free_list
;
160 lbitset_free_list
= elt
;
164 /* Unlink element ELT from bitset BSET. */
166 lbitset_elt_unlink (bitset bset
, lbitset_elt
*elt
)
168 lbitset_elt
*next
= elt
->next
;
169 lbitset_elt
*prev
= elt
->prev
;
177 if (LBITSET_HEAD (bset
) == elt
)
178 LBITSET_HEAD (bset
) = next
;
179 if (LBITSET_TAIL (bset
) == elt
)
180 LBITSET_TAIL (bset
) = prev
;
182 /* Update cache pointer. Since the first thing we try is to insert
183 before current, make current the next entry in preference to the
185 if (LBITSET_CURRENT (bset
) == elt
)
189 bset
->b
.cdata
= next
->words
;
190 bset
->b
.cindex
= next
->index
;
194 bset
->b
.cdata
= prev
->words
;
195 bset
->b
.cindex
= prev
->index
;
204 lbitset_elt_free (elt
);
208 /* Cut the chain of bitset BSET before element ELT and free the
211 lbitset_prune (bitset bset
, lbitset_elt
*elt
)
220 LBITSET_TAIL (bset
) = elt
->prev
;
221 bset
->b
.cdata
= elt
->prev
->words
;
222 bset
->b
.cindex
= elt
->prev
->index
;
227 LBITSET_HEAD (bset
) = 0;
228 LBITSET_TAIL (bset
) = 0;
233 for (; elt
; elt
= next
)
236 lbitset_elt_free (elt
);
241 /* Are all bits in an element zero? */
243 lbitset_elt_zero_p (lbitset_elt
*elt
)
247 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++)
255 /* Link the bitset element into the current bitset linked list. */
257 lbitset_elt_link (bitset bset
, lbitset_elt
*elt
)
259 bitset_windex windex
= elt
->index
;
261 lbitset_elt
*current
;
264 current
= LBITSET_CURRENT (bset
);
266 current
= LBITSET_HEAD (bset
);
268 /* If this is the first and only element, add it in. */
269 if (LBITSET_HEAD (bset
) == 0)
271 elt
->next
= elt
->prev
= 0;
272 LBITSET_HEAD (bset
) = elt
;
273 LBITSET_TAIL (bset
) = elt
;
276 /* If this index is less than that of the current element, it goes
277 somewhere before the current element. */
278 else if (windex
< bset
->b
.cindex
)
281 ptr
->prev
&& ptr
->prev
->index
> windex
; ptr
= ptr
->prev
)
285 ptr
->prev
->next
= elt
;
287 LBITSET_HEAD (bset
) = elt
;
289 elt
->prev
= ptr
->prev
;
294 /* Otherwise, it must go somewhere after the current element. */
298 ptr
->next
&& ptr
->next
->index
< windex
; ptr
= ptr
->next
)
302 ptr
->next
->prev
= elt
;
304 LBITSET_TAIL (bset
) = elt
;
306 elt
->next
= ptr
->next
;
311 /* Set up so this is the first element searched. */
312 bset
->b
.cindex
= windex
;
313 bset
->b
.csize
= LBITSET_ELT_WORDS
;
314 bset
->b
.cdata
= elt
->words
;
319 lbitset_elt_find (bitset bset
, bitset_windex windex
,
320 enum lbitset_find_mode mode
)
323 lbitset_elt
*current
;
327 current
= LBITSET_CURRENT (bset
);
328 /* Check if element is the cached element. */
329 if ((windex
- bset
->b
.cindex
) < bset
->b
.csize
)
334 current
= LBITSET_HEAD (bset
);
339 if (windex
< bset
->b
.cindex
)
342 elt
->prev
&& elt
->index
> windex
; elt
= elt
->prev
)
348 elt
->next
&& (elt
->index
+ LBITSET_ELT_WORDS
- 1) < windex
;
353 /* ELT is the nearest to the one we want. If it's not the one
354 we want, the one we want does not exist. */
355 if (elt
&& (windex
- elt
->index
) < LBITSET_ELT_WORDS
)
357 bset
->b
.cindex
= elt
->index
;
358 bset
->b
.csize
= LBITSET_ELT_WORDS
;
359 bset
->b
.cdata
= elt
->words
;
373 windex
-= windex
% LBITSET_ELT_WORDS
;
375 elt
= lbitset_elt_calloc ();
377 lbitset_elt_link (bset
, elt
);
381 return &lbitset_zero_elts
[0];
386 /* Weed out the zero elements from the list. */
388 lbitset_weed (bitset bset
)
393 for (elt
= LBITSET_HEAD (bset
); elt
; elt
= next
)
396 if (lbitset_elt_zero_p (elt
))
397 lbitset_elt_unlink (bset
, elt
);
402 /* Set all bits in the bitset to zero. */
404 lbitset_zero (bitset bset
)
408 head
= LBITSET_HEAD (bset
);
412 /* Clear a bitset by freeing the linked list at the head element. */
413 lbitset_prune (bset
, head
);
419 lbitset_equal_p (bitset dst
, bitset src
)
430 for (selt
= LBITSET_HEAD (src
), delt
= LBITSET_HEAD (dst
);
431 selt
&& delt
; selt
= selt
->next
, delt
= delt
->next
)
433 if (selt
->index
!= delt
->index
)
436 for (j
= 0; j
< LBITSET_ELT_WORDS
; j
++)
437 if (delt
->words
[j
] != selt
->words
[j
])
440 return !selt
&& !delt
;
444 /* Copy bits from bitset SRC to bitset DST. */
446 lbitset_copy (bitset dst
, bitset src
)
458 head
= LBITSET_HEAD (src
);
463 for (elt
= head
; elt
; elt
= elt
->next
)
465 tmp
= lbitset_elt_alloc ();
466 tmp
->index
= elt
->index
;
472 LBITSET_HEAD (dst
) = tmp
;
475 memcpy (tmp
->words
, elt
->words
, sizeof (elt
->words
));
477 LBITSET_TAIL (dst
) = tmp
;
479 dst
->b
.csize
= LBITSET_ELT_WORDS
;
480 dst
->b
.cdata
= LBITSET_HEAD (dst
)->words
;
481 dst
->b
.cindex
= LBITSET_HEAD (dst
)->index
;
485 /* Copy bits from bitset SRC to bitset DST. Return true if
486 bitsets different. */
488 lbitset_copy_cmp (bitset dst
, bitset src
)
493 if (!LBITSET_HEAD (dst
))
495 lbitset_copy (dst
, src
);
496 return LBITSET_HEAD (src
) != 0;
499 if (lbitset_equal_p (dst
, src
))
502 lbitset_copy (dst
, src
);
508 lbitset_resize (bitset src
, bitset_bindex size
)
510 BITSET_NBITS_ (src
) = size
;
512 /* Need to prune any excess bits. FIXME. */
516 /* Set bit BITNO in bitset DST. */
518 lbitset_set (bitset dst
, bitset_bindex bitno
)
520 bitset_windex windex
= bitno
/ BITSET_WORD_BITS
;
522 lbitset_elt_find (dst
, windex
, LBITSET_CREATE
);
524 dst
->b
.cdata
[windex
- dst
->b
.cindex
] |=
525 (bitset_word
) 1 << (bitno
% BITSET_WORD_BITS
);
529 /* Reset bit BITNO in bitset DST. */
531 lbitset_reset (bitset dst
, bitset_bindex bitno
)
533 bitset_windex windex
= bitno
/ BITSET_WORD_BITS
;
535 if (!lbitset_elt_find (dst
, windex
, LBITSET_FIND
))
538 dst
->b
.cdata
[windex
- dst
->b
.cindex
] &=
539 ~((bitset_word
) 1 << (bitno
% BITSET_WORD_BITS
));
541 /* If all the data is zero, perhaps we should unlink it now... */
545 /* Test bit BITNO in bitset SRC. */
547 lbitset_test (bitset src
, bitset_bindex bitno
)
549 bitset_windex windex
= bitno
/ BITSET_WORD_BITS
;
551 return (lbitset_elt_find (src
, windex
, LBITSET_FIND
)
552 && ((src
->b
.cdata
[windex
- src
->b
.cindex
]
553 >> (bitno
% BITSET_WORD_BITS
))
559 lbitset_free (bitset bset
)
565 /* Find list of up to NUM bits set in BSET starting from and including
566 *NEXT and store in array LIST. Return with actual number of bits
567 found and with *NEXT indicating where search stopped. */
569 lbitset_list_reverse (bitset bset
, bitset_bindex
*list
,
570 bitset_bindex num
, bitset_bindex
*next
)
572 bitset_bindex rbitno
;
575 bitset_bindex boffset
;
576 bitset_windex windex
;
580 bitset_bindex n_bits
;
582 elt
= LBITSET_TAIL (bset
);
586 n_bits
= (elt
->index
+ LBITSET_ELT_WORDS
) * BITSET_WORD_BITS
;
589 if (rbitno
>= n_bits
)
592 bitno
= n_bits
- (rbitno
+ 1);
594 windex
= bitno
/ BITSET_WORD_BITS
;
596 /* Skip back to starting element. */
597 for (; elt
&& elt
->index
> windex
; elt
= elt
->prev
)
603 if (windex
>= elt
->index
+ LBITSET_ELT_WORDS
)
605 /* We are trying to start in no-mans land so start
606 at end of current elt. */
607 bcount
= BITSET_WORD_BITS
- 1;
608 windex
= elt
->index
+ LBITSET_ELT_WORDS
- 1;
612 bcount
= bitno
% BITSET_WORD_BITS
;
616 boffset
= windex
* BITSET_WORD_BITS
;
618 /* If num is 1, we could speed things up with a binary search
619 of the word of interest. */
623 bitset_word
*srcp
= elt
->words
;
625 for (; (windex
- elt
->index
) < LBITSET_ELT_WORDS
;
626 windex
--, boffset
-= BITSET_WORD_BITS
,
627 bcount
= BITSET_WORD_BITS
- 1)
630 srcp
[windex
- elt
->index
] << (BITSET_WORD_BITS
- 1 - bcount
);
632 for (; word
; bcount
--)
634 if (word
& BITSET_MSB
)
636 list
[count
++] = boffset
+ bcount
;
639 *next
= n_bits
- (boffset
+ bcount
);
650 windex
= elt
->index
+ LBITSET_ELT_WORDS
- 1;
651 boffset
= windex
* BITSET_WORD_BITS
;
655 *next
= n_bits
- (boffset
+ 1);
660 /* Find list of up to NUM bits set in BSET starting from and including
661 *NEXT and store in array LIST. Return with actual number of bits
662 found and with *NEXT indicating where search stopped. */
664 lbitset_list (bitset bset
, bitset_bindex
*list
,
665 bitset_bindex num
, bitset_bindex
*next
)
668 bitset_windex windex
;
674 head
= LBITSET_HEAD (bset
);
683 /* This is the most common case. */
685 /* Start with the first element. */
688 bitno
= windex
* BITSET_WORD_BITS
;
692 windex
= bitno
/ BITSET_WORD_BITS
;
694 /* Skip to starting element. */
696 elt
&& (elt
->index
+ LBITSET_ELT_WORDS
- 1) < windex
;
703 if (windex
< elt
->index
)
706 bitno
= windex
* BITSET_WORD_BITS
;
710 bitset_word
*srcp
= elt
->words
;
712 /* We are starting within an element. */
714 for (; (windex
- elt
->index
) < LBITSET_ELT_WORDS
; windex
++)
716 word
= srcp
[windex
- elt
->index
] >> (bitno
% BITSET_WORD_BITS
);
718 for (; word
; bitno
++)
722 list
[count
++] = bitno
;
731 bitno
= (windex
+ 1) * BITSET_WORD_BITS
;
738 bitno
= windex
* BITSET_WORD_BITS
;
744 /* If num is 1, we could speed things up with a binary search
745 of the word of interest. */
750 bitset_word
*srcp
= elt
->words
;
752 if ((count
+ LBITSET_ELT_BITS
) < num
)
754 /* The coast is clear, plant boot! */
756 #if LBITSET_ELT_WORDS == 2
760 if (!(word
& 0xffff))
770 for (; word
; bitno
++)
773 list
[count
++] = bitno
;
778 bitno
= windex
* BITSET_WORD_BITS
;
783 if (!(word
& 0xffff))
788 for (; word
; bitno
++)
791 list
[count
++] = bitno
;
796 bitno
= windex
* BITSET_WORD_BITS
;
798 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++)
803 if (!(word
& 0xffff))
813 for (; word
; bitno
++)
816 list
[count
++] = bitno
;
821 bitno
= windex
* BITSET_WORD_BITS
;
827 /* Tread more carefully since we need to check
828 if array overflows. */
830 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++)
832 for (word
= srcp
[i
]; word
; bitno
++)
836 list
[count
++] = bitno
;
846 bitno
= windex
* BITSET_WORD_BITS
;
854 bitno
= windex
* BITSET_WORD_BITS
;
864 lbitset_empty_p (bitset dst
)
869 for (elt
= LBITSET_HEAD (dst
); elt
; elt
= next
)
872 if (!lbitset_elt_zero_p (elt
))
875 lbitset_elt_unlink (dst
, elt
);
882 /* Ensure that any unused bits within the last element are clear. */
884 lbitset_unused_clear (bitset dst
)
886 unsigned int last_bit
;
887 bitset_bindex n_bits
;
889 n_bits
= BITSET_SIZE_ (dst
);
890 last_bit
= n_bits
% LBITSET_ELT_BITS
;
895 bitset_windex windex
;
898 elt
= LBITSET_TAIL (dst
);
900 windex
= n_bits
/ BITSET_WORD_BITS
;
902 srcp
[windex
- elt
->index
] &= ((bitset_word
) 1 << last_bit
) - 1;
905 for (; (windex
- elt
->index
) < LBITSET_ELT_WORDS
; windex
++)
906 srcp
[windex
- elt
->index
] = 0;
912 lbitset_ones (bitset dst
)
915 bitset_windex windex
;
918 /* This is a decidedly unfriendly operation for a linked list
919 bitset! It makes a sparse bitset become dense. An alternative
920 is to have a flag that indicates that the bitset stores the
921 complement of what it indicates. */
923 windex
= (BITSET_SIZE_ (dst
) + BITSET_WORD_BITS
- 1) / BITSET_WORD_BITS
;
925 for (i
= 0; i
< windex
; i
+= LBITSET_ELT_WORDS
)
927 /* Create new elements if they cannot be found. */
928 elt
= lbitset_elt_find (dst
, i
, LBITSET_CREATE
);
929 memset (elt
->words
, -1, sizeof (elt
->words
));
932 lbitset_unused_clear (dst
);
937 lbitset_not (bitset dst
, bitset src
)
943 bitset_windex windex
;
945 windex
= (BITSET_SIZE_ (dst
) + BITSET_WORD_BITS
- 1) / BITSET_WORD_BITS
;
947 for (i
= 0; i
< windex
; i
+= LBITSET_ELT_WORDS
)
949 /* Create new elements for dst if they cannot be found
950 or substitute zero elements if src elements not found. */
951 selt
= lbitset_elt_find (src
, i
, LBITSET_SUBST
);
952 delt
= lbitset_elt_find (dst
, i
, LBITSET_CREATE
);
954 for (j
= 0; j
< LBITSET_ELT_WORDS
; j
++)
955 delt
->words
[j
] = ~selt
->words
[j
];
957 lbitset_unused_clear (dst
);
963 /* Is DST == DST | SRC? */
965 lbitset_subset_p (bitset dst
, bitset src
)
971 for (selt
= LBITSET_HEAD (src
), delt
= LBITSET_HEAD (dst
);
972 selt
|| delt
; selt
= selt
->next
, delt
= delt
->next
)
975 selt
= &lbitset_zero_elts
[0];
977 delt
= &lbitset_zero_elts
[0];
978 else if (selt
->index
!= delt
->index
)
980 if (selt
->index
< delt
->index
)
982 lbitset_zero_elts
[2].next
= delt
;
983 delt
= &lbitset_zero_elts
[2];
987 lbitset_zero_elts
[1].next
= selt
;
988 selt
= &lbitset_zero_elts
[1];
992 for (j
= 0; j
< LBITSET_ELT_WORDS
; j
++)
993 if (delt
->words
[j
] != (selt
->words
[j
] | delt
->words
[j
]))
1000 /* Is DST & SRC == 0? */
1002 lbitset_disjoint_p (bitset dst
, bitset src
)
1008 for (selt
= LBITSET_HEAD (src
), delt
= LBITSET_HEAD (dst
);
1009 selt
&& delt
; selt
= selt
->next
, delt
= delt
->next
)
1011 if (selt
->index
!= delt
->index
)
1013 if (selt
->index
< delt
->index
)
1015 lbitset_zero_elts
[2].next
= delt
;
1016 delt
= &lbitset_zero_elts
[2];
1020 lbitset_zero_elts
[1].next
= selt
;
1021 selt
= &lbitset_zero_elts
[1];
1023 /* Since the elements are different, there is no
1024 intersection of these elements. */
1028 for (j
= 0; j
< LBITSET_ELT_WORDS
; j
++)
1029 if (selt
->words
[j
] & delt
->words
[j
])
1037 lbitset_op3_cmp (bitset dst
, bitset src1
, bitset src2
, enum bitset_ops op
)
1039 lbitset_elt
*selt1
= LBITSET_HEAD (src1
);
1040 lbitset_elt
*selt2
= LBITSET_HEAD (src2
);
1041 lbitset_elt
*delt
= LBITSET_HEAD (dst
);
1042 bitset_windex windex1
;
1043 bitset_windex windex2
;
1044 bitset_windex windex
;
1051 bool changed
= false;
1054 LBITSET_HEAD (dst
) = 0;
1057 windex1
= (selt1
) ? selt1
->index
: BITSET_WINDEX_MAX
;
1058 windex2
= (selt2
) ? selt2
->index
: BITSET_WINDEX_MAX
;
1060 while (selt1
|| selt2
)
1062 /* Figure out whether we need to substitute zero elements for
1064 if (windex1
== windex2
)
1069 selt1
= selt1
->next
;
1070 windex1
= (selt1
) ? selt1
->index
: BITSET_WINDEX_MAX
;
1071 selt2
= selt2
->next
;
1072 windex2
= (selt2
) ? selt2
->index
: BITSET_WINDEX_MAX
;
1074 else if (windex1
< windex2
)
1078 stmp2
= &lbitset_zero_elts
[0];
1079 selt1
= selt1
->next
;
1080 windex1
= (selt1
) ? selt1
->index
: BITSET_WINDEX_MAX
;
1085 stmp1
= &lbitset_zero_elts
[0];
1087 selt2
= selt2
->next
;
1088 windex2
= (selt2
) ? selt2
->index
: BITSET_WINDEX_MAX
;
1091 /* Find the appropriate element from DST. Begin by discarding
1092 elements that we've skipped. */
1093 while (delt
&& delt
->index
< windex
)
1098 lbitset_elt_free (dtmp
);
1100 if (delt
&& delt
->index
== windex
)
1106 dtmp
= lbitset_elt_calloc ();
1108 /* Do the operation, and if any bits are set, link it into the
1110 srcp1
= stmp1
->words
;
1111 srcp2
= stmp2
->words
;
1119 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++, dstp
++)
1121 bitset_word tmp
= *srcp1
++ | *srcp2
++;
1132 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++, dstp
++)
1134 bitset_word tmp
= *srcp1
++ & *srcp2
++;
1145 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++, dstp
++)
1147 bitset_word tmp
= *srcp1
++ ^ *srcp2
++;
1157 case BITSET_OP_ANDN
:
1158 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++, dstp
++)
1160 bitset_word tmp
= *srcp1
++ & ~(*srcp2
++);
1171 if (!lbitset_elt_zero_p (dtmp
))
1173 dtmp
->index
= windex
;
1174 /* Perhaps this could be optimised... */
1175 lbitset_elt_link (dst
, dtmp
);
1179 lbitset_elt_free (dtmp
);
1183 /* If we have elements of DST left over, free them all. */
1187 lbitset_prune (dst
, delt
);
1195 lbitset_and_cmp (bitset dst
, bitset src1
, bitset src2
)
1197 lbitset_elt
*selt1
= LBITSET_HEAD (src1
);
1198 lbitset_elt
*selt2
= LBITSET_HEAD (src2
);
1204 changed
= !LBITSET_HEAD (dst
);
1211 changed
= !LBITSET_HEAD (dst
);
1215 return lbitset_op3_cmp (dst
, src1
, src2
, BITSET_OP_AND
);
1220 lbitset_and (bitset dst
, bitset src1
, bitset src2
)
1222 lbitset_and_cmp (dst
, src1
, src2
);
1227 lbitset_andn_cmp (bitset dst
, bitset src1
, bitset src2
)
1229 lbitset_elt
*selt1
= LBITSET_HEAD (src1
);
1230 lbitset_elt
*selt2
= LBITSET_HEAD (src2
);
1235 return lbitset_copy_cmp (dst
, src1
);
1240 changed
= !LBITSET_HEAD (dst
);
1244 return lbitset_op3_cmp (dst
, src1
, src2
, BITSET_OP_ANDN
);
1249 lbitset_andn (bitset dst
, bitset src1
, bitset src2
)
1251 lbitset_andn_cmp (dst
, src1
, src2
);
1256 lbitset_or_cmp (bitset dst
, bitset src1
, bitset src2
)
1258 lbitset_elt
*selt1
= LBITSET_HEAD (src1
);
1259 lbitset_elt
*selt2
= LBITSET_HEAD (src2
);
1263 return lbitset_copy_cmp (dst
, src1
);
1267 return lbitset_copy_cmp (dst
, src2
);
1269 return lbitset_op3_cmp (dst
, src1
, src2
, BITSET_OP_OR
);
1274 lbitset_or (bitset dst
, bitset src1
, bitset src2
)
1276 lbitset_or_cmp (dst
, src1
, src2
);
1281 lbitset_xor_cmp (bitset dst
, bitset src1
, bitset src2
)
1283 lbitset_elt
*selt1
= LBITSET_HEAD (src1
);
1284 lbitset_elt
*selt2
= LBITSET_HEAD (src2
);
1288 return lbitset_copy_cmp (dst
, src1
);
1292 return lbitset_copy_cmp (dst
, src2
);
1294 return lbitset_op3_cmp (dst
, src1
, src2
, BITSET_OP_XOR
);
1299 lbitset_xor (bitset dst
, bitset src1
, bitset src2
)
1301 lbitset_xor_cmp (dst
, src1
, src2
);
1306 /* Vector of operations for linked-list bitsets. */
1307 struct bitset_vtable lbitset_vtable
= {
1334 bitset_andn_or_cmp_
,
1338 lbitset_list_reverse
,
1344 /* Return size of initial structure. */
1346 lbitset_bytes (bitset_bindex n_bits ATTRIBUTE_UNUSED
)
1348 return sizeof (struct lbitset_struct
);
1352 /* Initialize a bitset. */
1354 lbitset_init (bitset bset
, bitset_bindex n_bits ATTRIBUTE_UNUSED
)
1356 BITSET_NBITS_ (bset
) = n_bits
;
1357 bset
->b
.vtable
= &lbitset_vtable
;
1363 lbitset_release_memory (void)
1365 lbitset_free_list
= 0;
1366 if (lbitset_obstack_init
)
1368 lbitset_obstack_init
= false;
1369 obstack_free (&lbitset_obstack
, NULL
);
1374 /* Function to be called from debugger to debug lbitset. */
1376 debug_lbitset (bitset bset
)
1384 for (elt
= LBITSET_HEAD (bset
); elt
; elt
= elt
->next
)
1386 fprintf (stderr
, "Elt %lu\n", (unsigned long int) elt
->index
);
1387 for (i
= 0; i
< LBITSET_ELT_WORDS
; i
++)
1392 word
= elt
->words
[i
];
1394 fprintf (stderr
, " Word %u:", i
);
1395 for (j
= 0; j
< LBITSET_WORD_BITS
; j
++)
1396 if ((word
& ((bitset_word
) 1 << j
)))
1397 fprintf (stderr
, " %u", j
);
1398 fprintf (stderr
, "\n");