]>
Commit | Line | Data |
---|---|---|
096ab9ea | 1 | /* Functions to support general ended bitmaps. |
6fb5fa3c | 2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, |
66647d44 | 3 | 2006, 2007, 2008, 2009 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 | |
9dcd6f09 | 9 | Software Foundation; either version 3, or (at your option) any later |
1322177d | 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 | |
9dcd6f09 NC |
18 | along with GCC; see the file COPYING3. If not see |
19 | <http://www.gnu.org/licenses/>. */ | |
096ab9ea | 20 | |
88657302 | 21 | #ifndef GCC_BITMAP_H |
ca7fd9cd | 22 | #define GCC_BITMAP_H |
1af4bba8 | 23 | #include "hashtab.h" |
f75709c6 | 24 | #include "statistics.h" |
b60db1ba | 25 | #include "obstack.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. */ |
e326eeb5 | 96 | extern void bitmap_copy (bitmap, const_bitmap); |
096ab9ea | 97 | |
8229306b | 98 | /* True if two bitmaps are identical. */ |
e326eeb5 | 99 | extern bool bitmap_equal_p (const_bitmap, const_bitmap); |
8229306b | 100 | |
55994078 | 101 | /* True if the bitmaps intersect (their AND is non-empty). */ |
e326eeb5 | 102 | extern bool bitmap_intersect_p (const_bitmap, const_bitmap); |
55994078 NS |
103 | |
104 | /* True if the complement of the second intersects the first (their | |
105 | AND_COMPL is non-empty). */ | |
e326eeb5 | 106 | extern bool bitmap_intersect_compl_p (const_bitmap, const_bitmap); |
55994078 NS |
107 | |
108 | /* True if MAP is an empty bitmap. */ | |
eb59b8de NS |
109 | #define bitmap_empty_p(MAP) (!(MAP)->first) |
110 | ||
76e910c6 RG |
111 | /* True if the bitmap has only a single bit set. */ |
112 | extern bool bitmap_single_bit_set_p (const_bitmap); | |
113 | ||
1bc40c7e | 114 | /* Count the number of bits set in the bitmap. */ |
e326eeb5 | 115 | extern unsigned long bitmap_count_bits (const_bitmap); |
1bc40c7e | 116 | |
88c4f655 NS |
117 | /* Boolean operations on bitmaps. The _into variants are two operand |
118 | versions that modify the first source operand. The other variants | |
119 | are three operand versions that to not destroy the source bitmaps. | |
120 | The operations supported are &, & ~, |, ^. */ | |
e326eeb5 KG |
121 | extern void bitmap_and (bitmap, const_bitmap, const_bitmap); |
122 | extern void bitmap_and_into (bitmap, const_bitmap); | |
123 | extern bool bitmap_and_compl (bitmap, const_bitmap, const_bitmap); | |
124 | extern bool bitmap_and_compl_into (bitmap, const_bitmap); | |
1bc40c7e | 125 | #define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) |
e326eeb5 | 126 | extern void bitmap_compl_and_into (bitmap, const_bitmap); |
1bc40c7e | 127 | extern void bitmap_clear_range (bitmap, unsigned int, unsigned int); |
6fb5fa3c | 128 | extern void bitmap_set_range (bitmap, unsigned int, unsigned int); |
e326eeb5 KG |
129 | extern bool bitmap_ior (bitmap, const_bitmap, const_bitmap); |
130 | extern bool bitmap_ior_into (bitmap, const_bitmap); | |
131 | extern void bitmap_xor (bitmap, const_bitmap, const_bitmap); | |
132 | extern void bitmap_xor_into (bitmap, const_bitmap); | |
88c4f655 NS |
133 | |
134 | /* DST = A | (B & ~C). Return true if DST changes. */ | |
e326eeb5 | 135 | extern bool bitmap_ior_and_compl (bitmap DST, const_bitmap A, const_bitmap B, const_bitmap C); |
88c4f655 | 136 | /* A |= (B & ~C). Return true if A changes. */ |
e326eeb5 | 137 | extern bool bitmap_ior_and_compl_into (bitmap DST, const_bitmap B, const_bitmap C); |
096ab9ea | 138 | |
5f0d975b RG |
139 | /* Clear a single bit in a bitmap. Return true if the bit changed. */ |
140 | extern bool bitmap_clear_bit (bitmap, int); | |
096ab9ea | 141 | |
5f0d975b RG |
142 | /* Set a single bit in a bitmap. Return true if the bit changed. */ |
143 | extern bool bitmap_set_bit (bitmap, int); | |
096ab9ea RK |
144 | |
145 | /* Return true if a register is set in a register set. */ | |
4682ae04 | 146 | extern int bitmap_bit_p (bitmap, int); |
096ab9ea RK |
147 | |
148 | /* Debug functions to print a bitmap linked list. */ | |
e326eeb5 KG |
149 | extern void debug_bitmap (const_bitmap); |
150 | extern void debug_bitmap_file (FILE *, const_bitmap); | |
096ab9ea | 151 | |
f9da5064 | 152 | /* Print a bitmap. */ |
e326eeb5 | 153 | extern void bitmap_print (FILE *, const_bitmap, const char *, const char *); |
22fa5b8a | 154 | |
5765e552 | 155 | /* Initialize and release a bitmap obstack. */ |
7932a3db NS |
156 | extern void bitmap_obstack_initialize (bitmap_obstack *); |
157 | extern void bitmap_obstack_release (bitmap_obstack *); | |
f75709c6 JH |
158 | extern void bitmap_register (bitmap MEM_STAT_DECL); |
159 | extern void dump_bitmap_statistics (void); | |
096ab9ea | 160 | |
7932a3db NS |
161 | /* Initialize a bitmap header. OBSTACK indicates the bitmap obstack |
162 | to allocate from, NULL for GC'd bitmap. */ | |
163 | ||
164 | static inline void | |
f75709c6 | 165 | bitmap_initialize_stat (bitmap head, bitmap_obstack *obstack MEM_STAT_DECL) |
7932a3db NS |
166 | { |
167 | head->first = head->current = NULL; | |
168 | head->obstack = obstack; | |
f75709c6 JH |
169 | #ifdef GATHER_STATISTICS |
170 | bitmap_register (head PASS_MEM_STAT); | |
171 | #endif | |
7932a3db | 172 | } |
f75709c6 | 173 | #define bitmap_initialize(h,o) bitmap_initialize_stat (h,o MEM_STAT_INFO) |
7932a3db NS |
174 | |
175 | /* Allocate and free bitmaps from obstack, malloc and gc'd memory. */ | |
f75709c6 JH |
176 | extern bitmap bitmap_obstack_alloc_stat (bitmap_obstack *obstack MEM_STAT_DECL); |
177 | #define bitmap_obstack_alloc(t) bitmap_obstack_alloc_stat (t MEM_STAT_INFO) | |
178 | extern bitmap bitmap_gc_alloc_stat (ALONE_MEM_STAT_DECL); | |
179 | #define bitmap_gc_alloc() bitmap_gc_alloc_stat (ALONE_MEM_STAT_INFO) | |
7932a3db | 180 | extern void bitmap_obstack_free (bitmap); |
096ab9ea | 181 | |
ea193996 DB |
182 | /* A few compatibility/functions macros for compatibility with sbitmaps */ |
183 | #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") | |
184 | #define bitmap_zero(a) bitmap_clear (a) | |
e326eeb5 | 185 | extern unsigned bitmap_first_set_bit (const_bitmap); |
ea193996 | 186 | |
1af4bba8 | 187 | /* Compute bitmap hash (for purposes of hashing etc.) */ |
e326eeb5 | 188 | extern hashval_t bitmap_hash(const_bitmap); |
1af4bba8 | 189 | |
7932a3db | 190 | /* Allocate a bitmap from a bit obstack. */ |
cc175e7c | 191 | #define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK) |
e2500fed | 192 | |
7932a3db NS |
193 | /* Allocate a gc'd bitmap. */ |
194 | #define BITMAP_GGC_ALLOC() bitmap_gc_alloc () | |
ca7fd9cd | 195 | |
096ab9ea | 196 | /* Do any cleanup needed on a bitmap when it is no longer used. */ |
61ad0914 BE |
197 | #define BITMAP_FREE(BITMAP) \ |
198 | ((void) (bitmap_obstack_free ((bitmap) BITMAP), (BITMAP) = (bitmap) NULL)) | |
e7749837 | 199 | |
87c476a2 | 200 | /* Iterator for bitmaps. */ |
096ab9ea | 201 | |
87c476a2 ZD |
202 | typedef struct |
203 | { | |
e90ea8cb NS |
204 | /* Pointer to the current bitmap element. */ |
205 | bitmap_element *elt1; | |
c22cacf3 | 206 | |
e90ea8cb NS |
207 | /* Pointer to 2nd bitmap element when two are involved. */ |
208 | bitmap_element *elt2; | |
209 | ||
210 | /* Word within the current element. */ | |
211 | unsigned word_no; | |
c22cacf3 | 212 | |
87c476a2 ZD |
213 | /* Contents of the actually processed word. When finding next bit |
214 | it is shifted right, so that the actual bit is always the least | |
215 | significant bit of ACTUAL. */ | |
e90ea8cb | 216 | BITMAP_WORD bits; |
87c476a2 ZD |
217 | } bitmap_iterator; |
218 | ||
e90ea8cb NS |
219 | /* Initialize a single bitmap iterator. START_BIT is the first bit to |
220 | iterate from. */ | |
87c476a2 | 221 | |
e90ea8cb | 222 | static inline void |
e326eeb5 | 223 | bmp_iter_set_init (bitmap_iterator *bi, const_bitmap map, |
e90ea8cb | 224 | unsigned start_bit, unsigned *bit_no) |
87c476a2 | 225 | { |
e90ea8cb NS |
226 | bi->elt1 = map->first; |
227 | bi->elt2 = NULL; | |
228 | ||
229 | /* Advance elt1 until it is not before the block containing start_bit. */ | |
230 | while (1) | |
87c476a2 | 231 | { |
e90ea8cb NS |
232 | if (!bi->elt1) |
233 | { | |
234 | bi->elt1 = &bitmap_zero_bits; | |
235 | break; | |
236 | } | |
c22cacf3 | 237 | |
e90ea8cb NS |
238 | if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) |
239 | break; | |
240 | bi->elt1 = bi->elt1->next; | |
87c476a2 ZD |
241 | } |
242 | ||
e90ea8cb NS |
243 | /* We might have gone past the start bit, so reinitialize it. */ |
244 | if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) | |
245 | start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; | |
c22cacf3 | 246 | |
e90ea8cb NS |
247 | /* Initialize for what is now start_bit. */ |
248 | bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; | |
249 | bi->bits = bi->elt1->bits[bi->word_no]; | |
250 | bi->bits >>= start_bit % BITMAP_WORD_BITS; | |
251 | ||
252 | /* If this word is zero, we must make sure we're not pointing at the | |
253 | first bit, otherwise our incrementing to the next word boundary | |
254 | will fail. It won't matter if this increment moves us into the | |
255 | next word. */ | |
256 | start_bit += !bi->bits; | |
c22cacf3 | 257 | |
e90ea8cb | 258 | *bit_no = start_bit; |
87c476a2 ZD |
259 | } |
260 | ||
e90ea8cb NS |
261 | /* Initialize an iterator to iterate over the intersection of two |
262 | bitmaps. START_BIT is the bit to commence from. */ | |
87c476a2 | 263 | |
e90ea8cb | 264 | static inline void |
e326eeb5 | 265 | bmp_iter_and_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2, |
e90ea8cb | 266 | unsigned start_bit, unsigned *bit_no) |
87c476a2 | 267 | { |
e90ea8cb NS |
268 | bi->elt1 = map1->first; |
269 | bi->elt2 = map2->first; | |
87c476a2 | 270 | |
e90ea8cb NS |
271 | /* Advance elt1 until it is not before the block containing |
272 | start_bit. */ | |
87c476a2 ZD |
273 | while (1) |
274 | { | |
e90ea8cb | 275 | if (!bi->elt1) |
87c476a2 | 276 | { |
e90ea8cb NS |
277 | bi->elt2 = NULL; |
278 | break; | |
87c476a2 | 279 | } |
c22cacf3 | 280 | |
e90ea8cb NS |
281 | if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) |
282 | break; | |
283 | bi->elt1 = bi->elt1->next; | |
87c476a2 | 284 | } |
c22cacf3 | 285 | |
e90ea8cb NS |
286 | /* Advance elt2 until it is not before elt1. */ |
287 | while (1) | |
87c476a2 | 288 | { |
e90ea8cb NS |
289 | if (!bi->elt2) |
290 | { | |
291 | bi->elt1 = bi->elt2 = &bitmap_zero_bits; | |
292 | break; | |
293 | } | |
c22cacf3 | 294 | |
e90ea8cb NS |
295 | if (bi->elt2->indx >= bi->elt1->indx) |
296 | break; | |
297 | bi->elt2 = bi->elt2->next; | |
87c476a2 ZD |
298 | } |
299 | ||
e28d0cfb | 300 | /* If we're at the same index, then we have some intersecting bits. */ |
e90ea8cb | 301 | if (bi->elt1->indx == bi->elt2->indx) |
87c476a2 | 302 | { |
e90ea8cb | 303 | /* We might have advanced beyond the start_bit, so reinitialize |
c22cacf3 | 304 | for that. */ |
e90ea8cb NS |
305 | if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) |
306 | start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; | |
c22cacf3 | 307 | |
e90ea8cb NS |
308 | bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
309 | bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; | |
310 | bi->bits >>= start_bit % BITMAP_WORD_BITS; | |
87c476a2 ZD |
311 | } |
312 | else | |
313 | { | |
e90ea8cb NS |
314 | /* Otherwise we must immediately advance elt1, so initialize for |
315 | that. */ | |
316 | bi->word_no = BITMAP_ELEMENT_WORDS - 1; | |
317 | bi->bits = 0; | |
87c476a2 | 318 | } |
c22cacf3 | 319 | |
e90ea8cb NS |
320 | /* If this word is zero, we must make sure we're not pointing at the |
321 | first bit, otherwise our incrementing to the next word boundary | |
322 | will fail. It won't matter if this increment moves us into the | |
323 | next word. */ | |
324 | start_bit += !bi->bits; | |
c22cacf3 | 325 | |
e90ea8cb | 326 | *bit_no = start_bit; |
87c476a2 ZD |
327 | } |
328 | ||
e90ea8cb NS |
329 | /* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. |
330 | */ | |
87c476a2 | 331 | |
e90ea8cb | 332 | static inline void |
e326eeb5 | 333 | bmp_iter_and_compl_init (bitmap_iterator *bi, const_bitmap map1, const_bitmap map2, |
e90ea8cb | 334 | unsigned start_bit, unsigned *bit_no) |
87c476a2 | 335 | { |
e90ea8cb NS |
336 | bi->elt1 = map1->first; |
337 | bi->elt2 = map2->first; | |
87c476a2 | 338 | |
e90ea8cb | 339 | /* Advance elt1 until it is not before the block containing start_bit. */ |
87c476a2 ZD |
340 | while (1) |
341 | { | |
e90ea8cb | 342 | if (!bi->elt1) |
87c476a2 | 343 | { |
e90ea8cb NS |
344 | bi->elt1 = &bitmap_zero_bits; |
345 | break; | |
87c476a2 | 346 | } |
c22cacf3 | 347 | |
e90ea8cb NS |
348 | if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) |
349 | break; | |
350 | bi->elt1 = bi->elt1->next; | |
87c476a2 | 351 | } |
e90ea8cb NS |
352 | |
353 | /* Advance elt2 until it is not before elt1. */ | |
354 | while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) | |
355 | bi->elt2 = bi->elt2->next; | |
356 | ||
357 | /* We might have advanced beyond the start_bit, so reinitialize for | |
358 | that. */ | |
359 | if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) | |
360 | start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; | |
c22cacf3 | 361 | |
e90ea8cb NS |
362 | bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; |
363 | bi->bits = bi->elt1->bits[bi->word_no]; | |
364 | if (bi->elt2 && bi->elt1->indx == bi->elt2->indx) | |
365 | bi->bits &= ~bi->elt2->bits[bi->word_no]; | |
366 | bi->bits >>= start_bit % BITMAP_WORD_BITS; | |
c22cacf3 | 367 | |
e90ea8cb NS |
368 | /* If this word is zero, we must make sure we're not pointing at the |
369 | first bit, otherwise our incrementing to the next word boundary | |
370 | will fail. It won't matter if this increment moves us into the | |
371 | next word. */ | |
372 | start_bit += !bi->bits; | |
c22cacf3 | 373 | |
e90ea8cb | 374 | *bit_no = start_bit; |
87c476a2 ZD |
375 | } |
376 | ||
e90ea8cb | 377 | /* Advance to the next bit in BI. We don't advance to the next |
d46aed51 | 378 | nonzero bit yet. */ |
87c476a2 | 379 | |
e90ea8cb NS |
380 | static inline void |
381 | bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no) | |
87c476a2 | 382 | { |
e90ea8cb NS |
383 | bi->bits >>= 1; |
384 | *bit_no += 1; | |
385 | } | |
87c476a2 | 386 | |
d46aed51 | 387 | /* Advance to the next nonzero bit of a single bitmap, we will have |
e90ea8cb NS |
388 | already advanced past the just iterated bit. Return true if there |
389 | is a bit to iterate. */ | |
87c476a2 | 390 | |
e90ea8cb NS |
391 | static inline bool |
392 | bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) | |
393 | { | |
d46aed51 | 394 | /* If our current word is nonzero, it contains the bit we want. */ |
e90ea8cb | 395 | if (bi->bits) |
87c476a2 | 396 | { |
e90ea8cb NS |
397 | next_bit: |
398 | while (!(bi->bits & 1)) | |
399 | { | |
400 | bi->bits >>= 1; | |
401 | *bit_no += 1; | |
402 | } | |
403 | return true; | |
87c476a2 ZD |
404 | } |
405 | ||
e90ea8cb NS |
406 | /* Round up to the word boundary. We might have just iterated past |
407 | the end of the last word, hence the -1. It is not possible for | |
408 | bit_no to point at the beginning of the now last word. */ | |
409 | *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) | |
410 | / BITMAP_WORD_BITS * BITMAP_WORD_BITS); | |
411 | bi->word_no++; | |
87c476a2 | 412 | |
e90ea8cb | 413 | while (1) |
87c476a2 | 414 | { |
d46aed51 | 415 | /* Find the next nonzero word in this elt. */ |
e90ea8cb NS |
416 | while (bi->word_no != BITMAP_ELEMENT_WORDS) |
417 | { | |
418 | bi->bits = bi->elt1->bits[bi->word_no]; | |
419 | if (bi->bits) | |
420 | goto next_bit; | |
421 | *bit_no += BITMAP_WORD_BITS; | |
422 | bi->word_no++; | |
423 | } | |
c22cacf3 | 424 | |
e90ea8cb NS |
425 | /* Advance to the next element. */ |
426 | bi->elt1 = bi->elt1->next; | |
427 | if (!bi->elt1) | |
428 | return false; | |
429 | *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; | |
430 | bi->word_no = 0; | |
87c476a2 | 431 | } |
87c476a2 ZD |
432 | } |
433 | ||
d46aed51 KH |
434 | /* Advance to the next nonzero bit of an intersecting pair of |
435 | bitmaps. We will have already advanced past the just iterated bit. | |
e90ea8cb | 436 | Return true if there is a bit to iterate. */ |
87c476a2 | 437 | |
e90ea8cb NS |
438 | static inline bool |
439 | bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no) | |
87c476a2 | 440 | { |
d46aed51 | 441 | /* If our current word is nonzero, it contains the bit we want. */ |
e90ea8cb NS |
442 | if (bi->bits) |
443 | { | |
444 | next_bit: | |
445 | while (!(bi->bits & 1)) | |
446 | { | |
447 | bi->bits >>= 1; | |
448 | *bit_no += 1; | |
449 | } | |
450 | return true; | |
451 | } | |
87c476a2 | 452 | |
e90ea8cb NS |
453 | /* Round up to the word boundary. We might have just iterated past |
454 | the end of the last word, hence the -1. It is not possible for | |
455 | bit_no to point at the beginning of the now last word. */ | |
456 | *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) | |
457 | / BITMAP_WORD_BITS * BITMAP_WORD_BITS); | |
458 | bi->word_no++; | |
c22cacf3 | 459 | |
87c476a2 ZD |
460 | while (1) |
461 | { | |
d46aed51 | 462 | /* Find the next nonzero word in this elt. */ |
e90ea8cb | 463 | while (bi->word_no != BITMAP_ELEMENT_WORDS) |
87c476a2 | 464 | { |
e90ea8cb NS |
465 | bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; |
466 | if (bi->bits) | |
467 | goto next_bit; | |
468 | *bit_no += BITMAP_WORD_BITS; | |
469 | bi->word_no++; | |
87c476a2 | 470 | } |
c22cacf3 | 471 | |
e90ea8cb | 472 | /* Advance to the next identical element. */ |
87c476a2 ZD |
473 | do |
474 | { | |
e90ea8cb NS |
475 | /* Advance elt1 while it is less than elt2. We always want |
476 | to advance one elt. */ | |
477 | do | |
87c476a2 | 478 | { |
e90ea8cb NS |
479 | bi->elt1 = bi->elt1->next; |
480 | if (!bi->elt1) | |
481 | return false; | |
482 | } | |
483 | while (bi->elt1->indx < bi->elt2->indx); | |
c22cacf3 | 484 | |
e90ea8cb NS |
485 | /* Advance elt2 to be no less than elt1. This might not |
486 | advance. */ | |
487 | while (bi->elt2->indx < bi->elt1->indx) | |
488 | { | |
489 | bi->elt2 = bi->elt2->next; | |
490 | if (!bi->elt2) | |
491 | return false; | |
87c476a2 ZD |
492 | } |
493 | } | |
e90ea8cb | 494 | while (bi->elt1->indx != bi->elt2->indx); |
c22cacf3 | 495 | |
e90ea8cb NS |
496 | *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; |
497 | bi->word_no = 0; | |
87c476a2 ZD |
498 | } |
499 | } | |
500 | ||
d46aed51 | 501 | /* Advance to the next nonzero bit in the intersection of |
e90ea8cb NS |
502 | complemented bitmaps. We will have already advanced past the just |
503 | iterated bit. */ | |
87c476a2 | 504 | |
e90ea8cb NS |
505 | static inline bool |
506 | bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) | |
87c476a2 | 507 | { |
d46aed51 | 508 | /* If our current word is nonzero, it contains the bit we want. */ |
e90ea8cb | 509 | if (bi->bits) |
87c476a2 | 510 | { |
e90ea8cb NS |
511 | next_bit: |
512 | while (!(bi->bits & 1)) | |
87c476a2 | 513 | { |
e90ea8cb NS |
514 | bi->bits >>= 1; |
515 | *bit_no += 1; | |
87c476a2 | 516 | } |
e90ea8cb | 517 | return true; |
87c476a2 ZD |
518 | } |
519 | ||
e90ea8cb NS |
520 | /* Round up to the word boundary. We might have just iterated past |
521 | the end of the last word, hence the -1. It is not possible for | |
522 | bit_no to point at the beginning of the now last word. */ | |
523 | *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) | |
524 | / BITMAP_WORD_BITS * BITMAP_WORD_BITS); | |
525 | bi->word_no++; | |
87c476a2 | 526 | |
e90ea8cb | 527 | while (1) |
87c476a2 | 528 | { |
d46aed51 | 529 | /* Find the next nonzero word in this elt. */ |
e90ea8cb NS |
530 | while (bi->word_no != BITMAP_ELEMENT_WORDS) |
531 | { | |
532 | bi->bits = bi->elt1->bits[bi->word_no]; | |
533 | if (bi->elt2 && bi->elt2->indx == bi->elt1->indx) | |
534 | bi->bits &= ~bi->elt2->bits[bi->word_no]; | |
535 | if (bi->bits) | |
536 | goto next_bit; | |
537 | *bit_no += BITMAP_WORD_BITS; | |
538 | bi->word_no++; | |
539 | } | |
c22cacf3 | 540 | |
e90ea8cb NS |
541 | /* Advance to the next element of elt1. */ |
542 | bi->elt1 = bi->elt1->next; | |
543 | if (!bi->elt1) | |
544 | return false; | |
545 | ||
546 | /* Advance elt2 until it is no less than elt1. */ | |
547 | while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) | |
548 | bi->elt2 = bi->elt2->next; | |
c22cacf3 | 549 | |
e90ea8cb NS |
550 | *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; |
551 | bi->word_no = 0; | |
87c476a2 | 552 | } |
87c476a2 ZD |
553 | } |
554 | ||
e90ea8cb NS |
555 | /* Loop over all bits set in BITMAP, starting with MIN and setting |
556 | BITNUM to the bit number. ITER is a bitmap iterator. BITNUM | |
557 | should be treated as a read-only variable as it contains loop | |
558 | state. */ | |
87c476a2 | 559 | |
e90ea8cb NS |
560 | #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ |
561 | for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ | |
562 | bmp_iter_set (&(ITER), &(BITNUM)); \ | |
563 | bmp_iter_next (&(ITER), &(BITNUM))) | |
564 | ||
565 | /* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN | |
566 | and setting BITNUM to the bit number. ITER is a bitmap iterator. | |
567 | BITNUM should be treated as a read-only variable as it contains | |
568 | loop state. */ | |
569 | ||
570 | #define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ | |
c22cacf3 | 571 | for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ |
e90ea8cb NS |
572 | &(BITNUM)); \ |
573 | bmp_iter_and (&(ITER), &(BITNUM)); \ | |
574 | bmp_iter_next (&(ITER), &(BITNUM))) | |
575 | ||
576 | /* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN | |
577 | and setting BITNUM to the bit number. ITER is a bitmap iterator. | |
578 | BITNUM should be treated as a read-only variable as it contains | |
579 | loop state. */ | |
580 | ||
581 | #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ | |
582 | for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ | |
c22cacf3 | 583 | &(BITNUM)); \ |
e90ea8cb NS |
584 | bmp_iter_and_compl (&(ITER), &(BITNUM)); \ |
585 | bmp_iter_next (&(ITER), &(BITNUM))) | |
a05924f9 | 586 | |
88657302 | 587 | #endif /* GCC_BITMAP_H */ |