1*404b540aSrobert /* Functions to support general ended bitmaps.
2*404b540aSrobert Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005
3*404b540aSrobert Free Software Foundation, Inc.
4*404b540aSrobert
5*404b540aSrobert This file is part of GCC.
6*404b540aSrobert
7*404b540aSrobert GCC is free software; you can redistribute it and/or modify it under
8*404b540aSrobert the terms of the GNU General Public License as published by the Free
9*404b540aSrobert Software Foundation; either version 2, or (at your option) any later
10*404b540aSrobert version.
11*404b540aSrobert
12*404b540aSrobert GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13*404b540aSrobert WARRANTY; without even the implied warranty of MERCHANTABILITY or
14*404b540aSrobert FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15*404b540aSrobert for more details.
16*404b540aSrobert
17*404b540aSrobert You should have received a copy of the GNU General Public License
18*404b540aSrobert along with GCC; see the file COPYING. If not, write to the Free
19*404b540aSrobert Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20*404b540aSrobert 02110-1301, USA. */
21*404b540aSrobert
22*404b540aSrobert #ifndef GCC_BITMAP_H
23*404b540aSrobert #define GCC_BITMAP_H
24*404b540aSrobert #include "hashtab.h"
25*404b540aSrobert
26*404b540aSrobert /* Fundamental storage type for bitmap. */
27*404b540aSrobert
28*404b540aSrobert typedef unsigned long BITMAP_WORD;
29*404b540aSrobert /* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as
30*404b540aSrobert it is used in preprocessor directives -- hence the 1u. */
31*404b540aSrobert #define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
32*404b540aSrobert
33*404b540aSrobert /* Number of words to use for each element in the linked list. */
34*404b540aSrobert
35*404b540aSrobert #ifndef BITMAP_ELEMENT_WORDS
36*404b540aSrobert #define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
37*404b540aSrobert #endif
38*404b540aSrobert
39*404b540aSrobert /* Number of bits in each actual element of a bitmap. */
40*404b540aSrobert
41*404b540aSrobert #define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
42*404b540aSrobert
43*404b540aSrobert /* Obstack for allocating bitmaps and elements from. */
44*404b540aSrobert typedef struct bitmap_obstack GTY (())
45*404b540aSrobert {
46*404b540aSrobert struct bitmap_element_def *elements;
47*404b540aSrobert struct bitmap_head_def *heads;
48*404b540aSrobert struct obstack GTY ((skip)) obstack;
49*404b540aSrobert } bitmap_obstack;
50*404b540aSrobert
51*404b540aSrobert /* Bitmap set element. We use a linked list to hold only the bits that
52*404b540aSrobert are set. This allows for use to grow the bitset dynamically without
53*404b540aSrobert having to realloc and copy a giant bit array.
54*404b540aSrobert
55*404b540aSrobert The free list is implemented as a list of lists. There is one
56*404b540aSrobert outer list connected together by prev fields. Each element of that
57*404b540aSrobert outer is an inner list (that may consist only of the outer list
58*404b540aSrobert element) that are connected by the next fields. The prev pointer
59*404b540aSrobert is undefined for interior elements. This allows
60*404b540aSrobert bitmap_elt_clear_from to be implemented in unit time rather than
61*404b540aSrobert linear in the number of elements to be freed. */
62*404b540aSrobert
63*404b540aSrobert typedef struct bitmap_element_def GTY(())
64*404b540aSrobert {
65*404b540aSrobert struct bitmap_element_def *next; /* Next element. */
66*404b540aSrobert struct bitmap_element_def *prev; /* Previous element. */
67*404b540aSrobert unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */
68*404b540aSrobert BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
69*404b540aSrobert } bitmap_element;
70*404b540aSrobert
71*404b540aSrobert /* Head of bitmap linked list. */
72*404b540aSrobert typedef struct bitmap_head_def GTY(()) {
73*404b540aSrobert bitmap_element *first; /* First element in linked list. */
74*404b540aSrobert bitmap_element *current; /* Last element looked at. */
75*404b540aSrobert unsigned int indx; /* Index of last element looked at. */
76*404b540aSrobert bitmap_obstack *obstack; /* Obstack to allocate elements from.
77*404b540aSrobert If NULL, then use ggc_alloc. */
78*404b540aSrobert } bitmap_head;
79*404b540aSrobert
80*404b540aSrobert
81*404b540aSrobert /* Global data */
82*404b540aSrobert extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
83*404b540aSrobert extern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */
84*404b540aSrobert
85*404b540aSrobert /* Clear a bitmap by freeing up the linked list. */
86*404b540aSrobert extern void bitmap_clear (bitmap);
87*404b540aSrobert
88*404b540aSrobert /* Copy a bitmap to another bitmap. */
89*404b540aSrobert extern void bitmap_copy (bitmap, bitmap);
90*404b540aSrobert
91*404b540aSrobert /* True if two bitmaps are identical. */
92*404b540aSrobert extern bool bitmap_equal_p (bitmap, bitmap);
93*404b540aSrobert
94*404b540aSrobert /* True if the bitmaps intersect (their AND is non-empty). */
95*404b540aSrobert extern bool bitmap_intersect_p (bitmap, bitmap);
96*404b540aSrobert
97*404b540aSrobert /* True if the complement of the second intersects the first (their
98*404b540aSrobert AND_COMPL is non-empty). */
99*404b540aSrobert extern bool bitmap_intersect_compl_p (bitmap, bitmap);
100*404b540aSrobert
101*404b540aSrobert /* True if MAP is an empty bitmap. */
102*404b540aSrobert #define bitmap_empty_p(MAP) (!(MAP)->first)
103*404b540aSrobert
104*404b540aSrobert /* Count the number of bits set in the bitmap. */
105*404b540aSrobert extern unsigned long bitmap_count_bits (bitmap);
106*404b540aSrobert
107*404b540aSrobert /* Boolean operations on bitmaps. The _into variants are two operand
108*404b540aSrobert versions that modify the first source operand. The other variants
109*404b540aSrobert are three operand versions that to not destroy the source bitmaps.
110*404b540aSrobert The operations supported are &, & ~, |, ^. */
111*404b540aSrobert extern void bitmap_and (bitmap, bitmap, bitmap);
112*404b540aSrobert extern void bitmap_and_into (bitmap, bitmap);
113*404b540aSrobert extern void bitmap_and_compl (bitmap, bitmap, bitmap);
114*404b540aSrobert extern bool bitmap_and_compl_into (bitmap, bitmap);
115*404b540aSrobert #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A)
116*404b540aSrobert extern void bitmap_compl_and_into (bitmap, bitmap);
117*404b540aSrobert extern void bitmap_clear_range (bitmap, unsigned int, unsigned int);
118*404b540aSrobert extern bool bitmap_ior (bitmap, bitmap, bitmap);
119*404b540aSrobert extern bool bitmap_ior_into (bitmap, bitmap);
120*404b540aSrobert extern void bitmap_xor (bitmap, bitmap, bitmap);
121*404b540aSrobert extern void bitmap_xor_into (bitmap, bitmap);
122*404b540aSrobert
123*404b540aSrobert /* DST = A | (B & ~C). Return true if DST changes. */
124*404b540aSrobert extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
125*404b540aSrobert /* A |= (B & ~C). Return true if A changes. */
126*404b540aSrobert extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
127*404b540aSrobert
128*404b540aSrobert /* Clear a single register in a register set. */
129*404b540aSrobert extern void bitmap_clear_bit (bitmap, int);
130*404b540aSrobert
131*404b540aSrobert /* Set a single register in a register set. */
132*404b540aSrobert extern void bitmap_set_bit (bitmap, int);
133*404b540aSrobert
134*404b540aSrobert /* Return true if a register is set in a register set. */
135*404b540aSrobert extern int bitmap_bit_p (bitmap, int);
136*404b540aSrobert
137*404b540aSrobert /* Debug functions to print a bitmap linked list. */
138*404b540aSrobert extern void debug_bitmap (bitmap);
139*404b540aSrobert extern void debug_bitmap_file (FILE *, bitmap);
140*404b540aSrobert
141*404b540aSrobert /* Print a bitmap. */
142*404b540aSrobert extern void bitmap_print (FILE *, bitmap, const char *, const char *);
143*404b540aSrobert
144*404b540aSrobert /* Initialize and release a bitmap obstack. */
145*404b540aSrobert extern void bitmap_obstack_initialize (bitmap_obstack *);
146*404b540aSrobert extern void bitmap_obstack_release (bitmap_obstack *);
147*404b540aSrobert
148*404b540aSrobert /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack
149*404b540aSrobert to allocate from, NULL for GC'd bitmap. */
150*404b540aSrobert
151*404b540aSrobert static inline void
bitmap_initialize(bitmap head,bitmap_obstack * obstack)152*404b540aSrobert bitmap_initialize (bitmap head, bitmap_obstack *obstack)
153*404b540aSrobert {
154*404b540aSrobert head->first = head->current = NULL;
155*404b540aSrobert head->obstack = obstack;
156*404b540aSrobert }
157*404b540aSrobert
158*404b540aSrobert /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */
159*404b540aSrobert extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
160*404b540aSrobert extern bitmap bitmap_gc_alloc (void);
161*404b540aSrobert extern void bitmap_obstack_free (bitmap);
162*404b540aSrobert
163*404b540aSrobert /* A few compatibility/functions macros for compatibility with sbitmaps */
164*404b540aSrobert #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
165*404b540aSrobert #define bitmap_zero(a) bitmap_clear (a)
166*404b540aSrobert extern unsigned bitmap_first_set_bit (bitmap);
167*404b540aSrobert
168*404b540aSrobert /* Compute bitmap hash (for purposes of hashing etc.) */
169*404b540aSrobert extern hashval_t bitmap_hash(bitmap);
170*404b540aSrobert
171*404b540aSrobert /* Allocate a bitmap from a bit obstack. */
172*404b540aSrobert #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
173*404b540aSrobert
174*404b540aSrobert /* Allocate a gc'd bitmap. */
175*404b540aSrobert #define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
176*404b540aSrobert
177*404b540aSrobert /* Do any cleanup needed on a bitmap when it is no longer used. */
178*404b540aSrobert #define BITMAP_FREE(BITMAP) \
179*404b540aSrobert ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
180*404b540aSrobert
181*404b540aSrobert /* Iterator for bitmaps. */
182*404b540aSrobert
183*404b540aSrobert typedef struct
184*404b540aSrobert {
185*404b540aSrobert /* Pointer to the current bitmap element. */
186*404b540aSrobert bitmap_element *elt1;
187*404b540aSrobert
188*404b540aSrobert /* Pointer to 2nd bitmap element when two are involved. */
189*404b540aSrobert bitmap_element *elt2;
190*404b540aSrobert
191*404b540aSrobert /* Word within the current element. */
192*404b540aSrobert unsigned word_no;
193*404b540aSrobert
194*404b540aSrobert /* Contents of the actually processed word. When finding next bit
195*404b540aSrobert it is shifted right, so that the actual bit is always the least
196*404b540aSrobert significant bit of ACTUAL. */
197*404b540aSrobert BITMAP_WORD bits;
198*404b540aSrobert } bitmap_iterator;
199*404b540aSrobert
200*404b540aSrobert /* Initialize a single bitmap iterator. START_BIT is the first bit to
201*404b540aSrobert iterate from. */
202*404b540aSrobert
203*404b540aSrobert static inline void
bmp_iter_set_init(bitmap_iterator * bi,bitmap map,unsigned start_bit,unsigned * bit_no)204*404b540aSrobert bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
205*404b540aSrobert unsigned start_bit, unsigned *bit_no)
206*404b540aSrobert {
207*404b540aSrobert bi->elt1 = map->first;
208*404b540aSrobert bi->elt2 = NULL;
209*404b540aSrobert
210*404b540aSrobert /* Advance elt1 until it is not before the block containing start_bit. */
211*404b540aSrobert while (1)
212*404b540aSrobert {
213*404b540aSrobert if (!bi->elt1)
214*404b540aSrobert {
215*404b540aSrobert bi->elt1 = &bitmap_zero_bits;
216*404b540aSrobert break;
217*404b540aSrobert }
218*404b540aSrobert
219*404b540aSrobert if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
220*404b540aSrobert break;
221*404b540aSrobert bi->elt1 = bi->elt1->next;
222*404b540aSrobert }
223*404b540aSrobert
224*404b540aSrobert /* We might have gone past the start bit, so reinitialize it. */
225*404b540aSrobert if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
226*404b540aSrobert start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
227*404b540aSrobert
228*404b540aSrobert /* Initialize for what is now start_bit. */
229*404b540aSrobert bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
230*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no];
231*404b540aSrobert bi->bits >>= start_bit % BITMAP_WORD_BITS;
232*404b540aSrobert
233*404b540aSrobert /* If this word is zero, we must make sure we're not pointing at the
234*404b540aSrobert first bit, otherwise our incrementing to the next word boundary
235*404b540aSrobert will fail. It won't matter if this increment moves us into the
236*404b540aSrobert next word. */
237*404b540aSrobert start_bit += !bi->bits;
238*404b540aSrobert
239*404b540aSrobert *bit_no = start_bit;
240*404b540aSrobert }
241*404b540aSrobert
242*404b540aSrobert /* Initialize an iterator to iterate over the intersection of two
243*404b540aSrobert bitmaps. START_BIT is the bit to commence from. */
244*404b540aSrobert
245*404b540aSrobert static inline void
bmp_iter_and_init(bitmap_iterator * bi,bitmap map1,bitmap map2,unsigned start_bit,unsigned * bit_no)246*404b540aSrobert bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
247*404b540aSrobert unsigned start_bit, unsigned *bit_no)
248*404b540aSrobert {
249*404b540aSrobert bi->elt1 = map1->first;
250*404b540aSrobert bi->elt2 = map2->first;
251*404b540aSrobert
252*404b540aSrobert /* Advance elt1 until it is not before the block containing
253*404b540aSrobert start_bit. */
254*404b540aSrobert while (1)
255*404b540aSrobert {
256*404b540aSrobert if (!bi->elt1)
257*404b540aSrobert {
258*404b540aSrobert bi->elt2 = NULL;
259*404b540aSrobert break;
260*404b540aSrobert }
261*404b540aSrobert
262*404b540aSrobert if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
263*404b540aSrobert break;
264*404b540aSrobert bi->elt1 = bi->elt1->next;
265*404b540aSrobert }
266*404b540aSrobert
267*404b540aSrobert /* Advance elt2 until it is not before elt1. */
268*404b540aSrobert while (1)
269*404b540aSrobert {
270*404b540aSrobert if (!bi->elt2)
271*404b540aSrobert {
272*404b540aSrobert bi->elt1 = bi->elt2 = &bitmap_zero_bits;
273*404b540aSrobert break;
274*404b540aSrobert }
275*404b540aSrobert
276*404b540aSrobert if (bi->elt2->indx >= bi->elt1->indx)
277*404b540aSrobert break;
278*404b540aSrobert bi->elt2 = bi->elt2->next;
279*404b540aSrobert }
280*404b540aSrobert
281*404b540aSrobert /* If we're at the same index, then we have some intersecting bits. */
282*404b540aSrobert if (bi->elt1->indx == bi->elt2->indx)
283*404b540aSrobert {
284*404b540aSrobert /* We might have advanced beyond the start_bit, so reinitialize
285*404b540aSrobert for that. */
286*404b540aSrobert if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
287*404b540aSrobert start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
288*404b540aSrobert
289*404b540aSrobert bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
290*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
291*404b540aSrobert bi->bits >>= start_bit % BITMAP_WORD_BITS;
292*404b540aSrobert }
293*404b540aSrobert else
294*404b540aSrobert {
295*404b540aSrobert /* Otherwise we must immediately advance elt1, so initialize for
296*404b540aSrobert that. */
297*404b540aSrobert bi->word_no = BITMAP_ELEMENT_WORDS - 1;
298*404b540aSrobert bi->bits = 0;
299*404b540aSrobert }
300*404b540aSrobert
301*404b540aSrobert /* If this word is zero, we must make sure we're not pointing at the
302*404b540aSrobert first bit, otherwise our incrementing to the next word boundary
303*404b540aSrobert will fail. It won't matter if this increment moves us into the
304*404b540aSrobert next word. */
305*404b540aSrobert start_bit += !bi->bits;
306*404b540aSrobert
307*404b540aSrobert *bit_no = start_bit;
308*404b540aSrobert }
309*404b540aSrobert
310*404b540aSrobert /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2.
311*404b540aSrobert */
312*404b540aSrobert
313*404b540aSrobert static inline void
bmp_iter_and_compl_init(bitmap_iterator * bi,bitmap map1,bitmap map2,unsigned start_bit,unsigned * bit_no)314*404b540aSrobert bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
315*404b540aSrobert unsigned start_bit, unsigned *bit_no)
316*404b540aSrobert {
317*404b540aSrobert bi->elt1 = map1->first;
318*404b540aSrobert bi->elt2 = map2->first;
319*404b540aSrobert
320*404b540aSrobert /* Advance elt1 until it is not before the block containing start_bit. */
321*404b540aSrobert while (1)
322*404b540aSrobert {
323*404b540aSrobert if (!bi->elt1)
324*404b540aSrobert {
325*404b540aSrobert bi->elt1 = &bitmap_zero_bits;
326*404b540aSrobert break;
327*404b540aSrobert }
328*404b540aSrobert
329*404b540aSrobert if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
330*404b540aSrobert break;
331*404b540aSrobert bi->elt1 = bi->elt1->next;
332*404b540aSrobert }
333*404b540aSrobert
334*404b540aSrobert /* Advance elt2 until it is not before elt1. */
335*404b540aSrobert while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
336*404b540aSrobert bi->elt2 = bi->elt2->next;
337*404b540aSrobert
338*404b540aSrobert /* We might have advanced beyond the start_bit, so reinitialize for
339*404b540aSrobert that. */
340*404b540aSrobert if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
341*404b540aSrobert start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
342*404b540aSrobert
343*404b540aSrobert bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
344*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no];
345*404b540aSrobert if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
346*404b540aSrobert bi->bits &= ~bi->elt2->bits[bi->word_no];
347*404b540aSrobert bi->bits >>= start_bit % BITMAP_WORD_BITS;
348*404b540aSrobert
349*404b540aSrobert /* If this word is zero, we must make sure we're not pointing at the
350*404b540aSrobert first bit, otherwise our incrementing to the next word boundary
351*404b540aSrobert will fail. It won't matter if this increment moves us into the
352*404b540aSrobert next word. */
353*404b540aSrobert start_bit += !bi->bits;
354*404b540aSrobert
355*404b540aSrobert *bit_no = start_bit;
356*404b540aSrobert }
357*404b540aSrobert
358*404b540aSrobert /* Advance to the next bit in BI. We don't advance to the next
359*404b540aSrobert nonzero bit yet. */
360*404b540aSrobert
361*404b540aSrobert static inline void
bmp_iter_next(bitmap_iterator * bi,unsigned * bit_no)362*404b540aSrobert bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
363*404b540aSrobert {
364*404b540aSrobert bi->bits >>= 1;
365*404b540aSrobert *bit_no += 1;
366*404b540aSrobert }
367*404b540aSrobert
368*404b540aSrobert /* Advance to the next nonzero bit of a single bitmap, we will have
369*404b540aSrobert already advanced past the just iterated bit. Return true if there
370*404b540aSrobert is a bit to iterate. */
371*404b540aSrobert
372*404b540aSrobert static inline bool
bmp_iter_set(bitmap_iterator * bi,unsigned * bit_no)373*404b540aSrobert bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
374*404b540aSrobert {
375*404b540aSrobert /* If our current word is nonzero, it contains the bit we want. */
376*404b540aSrobert if (bi->bits)
377*404b540aSrobert {
378*404b540aSrobert next_bit:
379*404b540aSrobert while (!(bi->bits & 1))
380*404b540aSrobert {
381*404b540aSrobert bi->bits >>= 1;
382*404b540aSrobert *bit_no += 1;
383*404b540aSrobert }
384*404b540aSrobert return true;
385*404b540aSrobert }
386*404b540aSrobert
387*404b540aSrobert /* Round up to the word boundary. We might have just iterated past
388*404b540aSrobert the end of the last word, hence the -1. It is not possible for
389*404b540aSrobert bit_no to point at the beginning of the now last word. */
390*404b540aSrobert *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
391*404b540aSrobert / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
392*404b540aSrobert bi->word_no++;
393*404b540aSrobert
394*404b540aSrobert while (1)
395*404b540aSrobert {
396*404b540aSrobert /* Find the next nonzero word in this elt. */
397*404b540aSrobert while (bi->word_no != BITMAP_ELEMENT_WORDS)
398*404b540aSrobert {
399*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no];
400*404b540aSrobert if (bi->bits)
401*404b540aSrobert goto next_bit;
402*404b540aSrobert *bit_no += BITMAP_WORD_BITS;
403*404b540aSrobert bi->word_no++;
404*404b540aSrobert }
405*404b540aSrobert
406*404b540aSrobert /* Advance to the next element. */
407*404b540aSrobert bi->elt1 = bi->elt1->next;
408*404b540aSrobert if (!bi->elt1)
409*404b540aSrobert return false;
410*404b540aSrobert *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
411*404b540aSrobert bi->word_no = 0;
412*404b540aSrobert }
413*404b540aSrobert }
414*404b540aSrobert
415*404b540aSrobert /* Advance to the next nonzero bit of an intersecting pair of
416*404b540aSrobert bitmaps. We will have already advanced past the just iterated bit.
417*404b540aSrobert Return true if there is a bit to iterate. */
418*404b540aSrobert
419*404b540aSrobert static inline bool
bmp_iter_and(bitmap_iterator * bi,unsigned * bit_no)420*404b540aSrobert bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
421*404b540aSrobert {
422*404b540aSrobert /* If our current word is nonzero, it contains the bit we want. */
423*404b540aSrobert if (bi->bits)
424*404b540aSrobert {
425*404b540aSrobert next_bit:
426*404b540aSrobert while (!(bi->bits & 1))
427*404b540aSrobert {
428*404b540aSrobert bi->bits >>= 1;
429*404b540aSrobert *bit_no += 1;
430*404b540aSrobert }
431*404b540aSrobert return true;
432*404b540aSrobert }
433*404b540aSrobert
434*404b540aSrobert /* Round up to the word boundary. We might have just iterated past
435*404b540aSrobert the end of the last word, hence the -1. It is not possible for
436*404b540aSrobert bit_no to point at the beginning of the now last word. */
437*404b540aSrobert *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
438*404b540aSrobert / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
439*404b540aSrobert bi->word_no++;
440*404b540aSrobert
441*404b540aSrobert while (1)
442*404b540aSrobert {
443*404b540aSrobert /* Find the next nonzero word in this elt. */
444*404b540aSrobert while (bi->word_no != BITMAP_ELEMENT_WORDS)
445*404b540aSrobert {
446*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
447*404b540aSrobert if (bi->bits)
448*404b540aSrobert goto next_bit;
449*404b540aSrobert *bit_no += BITMAP_WORD_BITS;
450*404b540aSrobert bi->word_no++;
451*404b540aSrobert }
452*404b540aSrobert
453*404b540aSrobert /* Advance to the next identical element. */
454*404b540aSrobert do
455*404b540aSrobert {
456*404b540aSrobert /* Advance elt1 while it is less than elt2. We always want
457*404b540aSrobert to advance one elt. */
458*404b540aSrobert do
459*404b540aSrobert {
460*404b540aSrobert bi->elt1 = bi->elt1->next;
461*404b540aSrobert if (!bi->elt1)
462*404b540aSrobert return false;
463*404b540aSrobert }
464*404b540aSrobert while (bi->elt1->indx < bi->elt2->indx);
465*404b540aSrobert
466*404b540aSrobert /* Advance elt2 to be no less than elt1. This might not
467*404b540aSrobert advance. */
468*404b540aSrobert while (bi->elt2->indx < bi->elt1->indx)
469*404b540aSrobert {
470*404b540aSrobert bi->elt2 = bi->elt2->next;
471*404b540aSrobert if (!bi->elt2)
472*404b540aSrobert return false;
473*404b540aSrobert }
474*404b540aSrobert }
475*404b540aSrobert while (bi->elt1->indx != bi->elt2->indx);
476*404b540aSrobert
477*404b540aSrobert *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
478*404b540aSrobert bi->word_no = 0;
479*404b540aSrobert }
480*404b540aSrobert }
481*404b540aSrobert
482*404b540aSrobert /* Advance to the next nonzero bit in the intersection of
483*404b540aSrobert complemented bitmaps. We will have already advanced past the just
484*404b540aSrobert iterated bit. */
485*404b540aSrobert
486*404b540aSrobert static inline bool
bmp_iter_and_compl(bitmap_iterator * bi,unsigned * bit_no)487*404b540aSrobert bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
488*404b540aSrobert {
489*404b540aSrobert /* If our current word is nonzero, it contains the bit we want. */
490*404b540aSrobert if (bi->bits)
491*404b540aSrobert {
492*404b540aSrobert next_bit:
493*404b540aSrobert while (!(bi->bits & 1))
494*404b540aSrobert {
495*404b540aSrobert bi->bits >>= 1;
496*404b540aSrobert *bit_no += 1;
497*404b540aSrobert }
498*404b540aSrobert return true;
499*404b540aSrobert }
500*404b540aSrobert
501*404b540aSrobert /* Round up to the word boundary. We might have just iterated past
502*404b540aSrobert the end of the last word, hence the -1. It is not possible for
503*404b540aSrobert bit_no to point at the beginning of the now last word. */
504*404b540aSrobert *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
505*404b540aSrobert / BITMAP_WORD_BITS * BITMAP_WORD_BITS);
506*404b540aSrobert bi->word_no++;
507*404b540aSrobert
508*404b540aSrobert while (1)
509*404b540aSrobert {
510*404b540aSrobert /* Find the next nonzero word in this elt. */
511*404b540aSrobert while (bi->word_no != BITMAP_ELEMENT_WORDS)
512*404b540aSrobert {
513*404b540aSrobert bi->bits = bi->elt1->bits[bi->word_no];
514*404b540aSrobert if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
515*404b540aSrobert bi->bits &= ~bi->elt2->bits[bi->word_no];
516*404b540aSrobert if (bi->bits)
517*404b540aSrobert goto next_bit;
518*404b540aSrobert *bit_no += BITMAP_WORD_BITS;
519*404b540aSrobert bi->word_no++;
520*404b540aSrobert }
521*404b540aSrobert
522*404b540aSrobert /* Advance to the next element of elt1. */
523*404b540aSrobert bi->elt1 = bi->elt1->next;
524*404b540aSrobert if (!bi->elt1)
525*404b540aSrobert return false;
526*404b540aSrobert
527*404b540aSrobert /* Advance elt2 until it is no less than elt1. */
528*404b540aSrobert while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
529*404b540aSrobert bi->elt2 = bi->elt2->next;
530*404b540aSrobert
531*404b540aSrobert *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
532*404b540aSrobert bi->word_no = 0;
533*404b540aSrobert }
534*404b540aSrobert }
535*404b540aSrobert
536*404b540aSrobert /* Loop over all bits set in BITMAP, starting with MIN and setting
537*404b540aSrobert BITNUM to the bit number. ITER is a bitmap iterator. BITNUM
538*404b540aSrobert should be treated as a read-only variable as it contains loop
539*404b540aSrobert state. */
540*404b540aSrobert
541*404b540aSrobert #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
542*404b540aSrobert for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
543*404b540aSrobert bmp_iter_set (&(ITER), &(BITNUM)); \
544*404b540aSrobert bmp_iter_next (&(ITER), &(BITNUM)))
545*404b540aSrobert
546*404b540aSrobert /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN
547*404b540aSrobert and setting BITNUM to the bit number. ITER is a bitmap iterator.
548*404b540aSrobert BITNUM should be treated as a read-only variable as it contains
549*404b540aSrobert loop state. */
550*404b540aSrobert
551*404b540aSrobert #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
552*404b540aSrobert for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
553*404b540aSrobert &(BITNUM)); \
554*404b540aSrobert bmp_iter_and (&(ITER), &(BITNUM)); \
555*404b540aSrobert bmp_iter_next (&(ITER), &(BITNUM)))
556*404b540aSrobert
557*404b540aSrobert /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN
558*404b540aSrobert and setting BITNUM to the bit number. ITER is a bitmap iterator.
559*404b540aSrobert BITNUM should be treated as a read-only variable as it contains
560*404b540aSrobert loop state. */
561*404b540aSrobert
562*404b540aSrobert #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
563*404b540aSrobert for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
564*404b540aSrobert &(BITNUM)); \
565*404b540aSrobert bmp_iter_and_compl (&(ITER), &(BITNUM)); \
566*404b540aSrobert bmp_iter_next (&(ITER), &(BITNUM)))
567*404b540aSrobert
568*404b540aSrobert #endif /* GCC_BITMAP_H */
569