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