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