]>
Commit | Line | Data |
---|---|---|
096ab9ea | 1 | /* Functions to support general ended bitmaps. |
f30278e8 | 2 | Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004 |
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 LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
096ab9ea | 21 | |
88657302 | 22 | #ifndef GCC_BITMAP_H |
ca7fd9cd | 23 | #define GCC_BITMAP_H |
a05924f9 | 24 | |
72e42e26 SB |
25 | /* Fundamental storage type for bitmap. */ |
26 | ||
27 | /* typedef unsigned HOST_WIDE_INT BITMAP_WORD; */ | |
28 | /* #define nBITMAP_WORD_BITS HOST_BITS_PER_WIDE_INT */ | |
29 | typedef unsigned long BITMAP_WORD; | |
30 | #define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG) | |
31 | #define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS | |
32 | ||
096ab9ea RK |
33 | /* Number of words to use for each element in the linked list. */ |
34 | ||
35 | #ifndef BITMAP_ELEMENT_WORDS | |
72e42e26 | 36 | #define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS) |
096ab9ea RK |
37 | #endif |
38 | ||
39 | /* Number of bits in each actual element of a bitmap. We get slightly better | |
40 | code for bit % BITMAP_ELEMENT_ALL_BITS and bit / BITMAP_ELEMENT_ALL_BITS if | |
41 | bits is unsigned, assuming it is a power of 2. */ | |
42 | ||
43 | #define BITMAP_ELEMENT_ALL_BITS \ | |
72e42e26 | 44 | ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)) |
096ab9ea RK |
45 | |
46 | /* Bitmap set element. We use a linked list to hold only the bits that | |
47 | are set. This allows for use to grow the bitset dynamically without | |
48 | having to realloc and copy a giant bit array. The `prev' field is | |
49 | undefined for an element on the free list. */ | |
50 | ||
e2500fed | 51 | typedef struct bitmap_element_def GTY(()) |
096ab9ea | 52 | { |
eebedaa5 KH |
53 | struct bitmap_element_def *next; /* Next element. */ |
54 | struct bitmap_element_def *prev; /* Previous element. */ | |
55 | unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ | |
72e42e26 | 56 | BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ |
096ab9ea RK |
57 | } bitmap_element; |
58 | ||
59 | /* Head of bitmap linked list. */ | |
e2500fed | 60 | typedef struct bitmap_head_def GTY(()) { |
eebedaa5 KH |
61 | bitmap_element *first; /* First element in linked list. */ |
62 | bitmap_element *current; /* Last element looked at. */ | |
63 | unsigned int indx; /* Index of last element looked at. */ | |
e2500fed GK |
64 | int using_obstack; /* Are we using an obstack or ggc for |
65 | allocation? */ | |
66 | } bitmap_head; | |
67 | typedef struct bitmap_head_def *bitmap; | |
096ab9ea RK |
68 | |
69 | /* Enumeration giving the various operations we support. */ | |
70 | enum bitmap_bits { | |
71 | BITMAP_AND, /* TO = FROM1 & FROM2 */ | |
72 | BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */ | |
8229306b | 73 | BITMAP_IOR, /* TO = FROM1 | FROM2 */ |
ea193996 DB |
74 | BITMAP_XOR, /* TO = FROM1 ^ FROM2 */ |
75 | BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */ | |
096ab9ea RK |
76 | }; |
77 | ||
78 | /* Global data */ | |
ae0ed63a | 79 | extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ |
096ab9ea RK |
80 | |
81 | /* Clear a bitmap by freeing up the linked list. */ | |
4682ae04 | 82 | extern void bitmap_clear (bitmap); |
096ab9ea | 83 | |
eebedaa5 | 84 | /* Copy a bitmap to another bitmap. */ |
4682ae04 | 85 | extern void bitmap_copy (bitmap, bitmap); |
096ab9ea | 86 | |
8229306b | 87 | /* True if two bitmaps are identical. */ |
4682ae04 | 88 | extern int bitmap_equal_p (bitmap, bitmap); |
8229306b | 89 | |
096ab9ea | 90 | /* Perform an operation on two bitmaps, yielding a third. */ |
4682ae04 | 91 | extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits); |
096ab9ea RK |
92 | |
93 | /* `or' into one bitmap the `and' of a second bitmap witih the complement | |
94 | of a third. */ | |
4682ae04 | 95 | extern void bitmap_ior_and_compl (bitmap, bitmap, bitmap); |
096ab9ea RK |
96 | |
97 | /* Clear a single register in a register set. */ | |
4682ae04 | 98 | extern void bitmap_clear_bit (bitmap, int); |
096ab9ea RK |
99 | |
100 | /* Set a single register in a register set. */ | |
4682ae04 | 101 | extern void bitmap_set_bit (bitmap, int); |
096ab9ea RK |
102 | |
103 | /* Return true if a register is set in a register set. */ | |
4682ae04 | 104 | extern int bitmap_bit_p (bitmap, int); |
096ab9ea RK |
105 | |
106 | /* Debug functions to print a bitmap linked list. */ | |
4682ae04 AJ |
107 | extern void debug_bitmap (bitmap); |
108 | extern void debug_bitmap_file (FILE *, bitmap); | |
096ab9ea | 109 | |
f9da5064 | 110 | /* Print a bitmap. */ |
4682ae04 | 111 | extern void bitmap_print (FILE *, bitmap, const char *, const char *); |
22fa5b8a | 112 | |
e2500fed GK |
113 | /* Initialize a bitmap header. If HEAD is NULL, a new header will be |
114 | allocated. USING_OBSTACK indicates how elements should be allocated. */ | |
4682ae04 | 115 | extern bitmap bitmap_initialize (bitmap head, int using_obstack); |
096ab9ea | 116 | |
e2500fed | 117 | /* Release all memory used by the bitmap obstack. */ |
4682ae04 | 118 | extern void bitmap_release_memory (void); |
096ab9ea | 119 | |
ea193996 DB |
120 | /* A few compatibility/functions macros for compatibility with sbitmaps */ |
121 | #define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") | |
122 | #define bitmap_zero(a) bitmap_clear (a) | |
123 | #define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR) | |
124 | #define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND) | |
4682ae04 AJ |
125 | extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap); |
126 | extern int bitmap_first_set_bit (bitmap); | |
127 | extern int bitmap_last_set_bit (bitmap); | |
ea193996 | 128 | |
096ab9ea RK |
129 | /* Allocate a bitmap with oballoc. */ |
130 | #define BITMAP_OBSTACK_ALLOC(OBSTACK) \ | |
703ad42b | 131 | bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1) |
e2500fed GK |
132 | |
133 | /* Allocate a bitmap with ggc_alloc. */ | |
134 | #define BITMAP_GGC_ALLOC() \ | |
135 | bitmap_initialize (NULL, 0) | |
ca7fd9cd | 136 | |
67289ea6 MM |
137 | /* Allocate a bitmap with xmalloc. */ |
138 | #define BITMAP_XMALLOC() \ | |
703ad42b | 139 | bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1) |
67289ea6 | 140 | |
096ab9ea | 141 | /* Do any cleanup needed on a bitmap when it is no longer used. */ |
e7749837 RH |
142 | #define BITMAP_FREE(BITMAP) \ |
143 | do { \ | |
144 | if (BITMAP) \ | |
145 | { \ | |
146 | bitmap_clear (BITMAP); \ | |
147 | (BITMAP) = 0; \ | |
148 | } \ | |
149 | } while (0) | |
150 | ||
151 | /* Do any cleanup needed on an xmalloced bitmap when it is no longer used. */ | |
152 | #define BITMAP_XFREE(BITMAP) \ | |
153 | do { \ | |
154 | if (BITMAP) \ | |
155 | { \ | |
156 | bitmap_clear (BITMAP); \ | |
157 | free (BITMAP); \ | |
158 | (BITMAP) = 0; \ | |
159 | } \ | |
096ab9ea RK |
160 | } while (0) |
161 | ||
162 | /* Do any one-time initializations needed for bitmaps. */ | |
163 | #define BITMAP_INIT_ONCE() | |
164 | ||
87c476a2 | 165 | /* Iterator for bitmaps. */ |
096ab9ea | 166 | |
87c476a2 ZD |
167 | typedef struct |
168 | { | |
169 | /* Actual elements in the bitmaps. */ | |
170 | bitmap_element *ptr1, *ptr2; | |
22fa5b8a | 171 | |
87c476a2 ZD |
172 | /* Position of an actual word in the elements. */ |
173 | unsigned word; | |
174 | ||
175 | /* Position of a bit corresponding to the start of word. */ | |
176 | unsigned word_bit; | |
177 | ||
178 | /* Position of the actual bit. */ | |
179 | unsigned bit; | |
180 | ||
181 | /* Contents of the actually processed word. When finding next bit | |
182 | it is shifted right, so that the actual bit is always the least | |
183 | significant bit of ACTUAL. */ | |
184 | BITMAP_WORD actual; | |
185 | } bitmap_iterator; | |
186 | ||
187 | /* Moves the iterator BI to the first set bit on or after the current | |
188 | position in bitmap and returns the bit if available. The bit is | |
189 | found in ACTUAL field only. */ | |
190 | ||
191 | static inline unsigned | |
192 | bmp_iter_common_next_1 (bitmap_iterator *bi) | |
193 | { | |
194 | while (!(bi->actual & 1)) | |
195 | { | |
196 | bi->actual >>= 1; | |
197 | bi->bit++; | |
198 | } | |
199 | ||
200 | return bi->bit; | |
201 | } | |
202 | ||
203 | /* Moves the iterator BI to the first set bit on or after the current | |
204 | position in bitmap and returns the bit if available. */ | |
205 | ||
206 | static inline unsigned | |
207 | bmp_iter_single_next_1 (bitmap_iterator *bi) | |
208 | { | |
209 | if (bi->actual) | |
210 | return bmp_iter_common_next_1 (bi); | |
211 | ||
212 | bi->word++; | |
213 | bi->word_bit += BITMAP_WORD_BITS; | |
214 | ||
215 | while (1) | |
216 | { | |
217 | for (; | |
218 | bi->word < BITMAP_ELEMENT_WORDS; | |
219 | bi->word++, bi->word_bit += BITMAP_WORD_BITS) | |
220 | { | |
221 | bi->actual = bi->ptr1->bits[bi->word]; | |
222 | if (bi->actual) | |
223 | { | |
224 | bi->bit = bi->word_bit; | |
225 | return bmp_iter_common_next_1 (bi); | |
226 | } | |
227 | } | |
228 | ||
229 | bi->ptr1 = bi->ptr1->next; | |
230 | if (!bi->ptr1) | |
231 | return 0; | |
232 | ||
233 | bi->word = 0; | |
234 | bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
235 | } | |
236 | } | |
237 | ||
238 | /* Initializes a bitmap iterator BI for looping over bits of bitmap | |
239 | BMP, starting with bit MIN. Returns the first bit of BMP greater | |
240 | or equal to MIN if there is any. */ | |
241 | ||
242 | static inline unsigned | |
243 | bmp_iter_single_init (bitmap_iterator *bi, bitmap bmp, unsigned min) | |
244 | { | |
245 | unsigned indx = min / BITMAP_ELEMENT_ALL_BITS; | |
246 | ||
247 | for (bi->ptr1 = bmp->first; | |
248 | bi->ptr1 && bi->ptr1->indx < indx; | |
249 | bi->ptr1 = bi->ptr1->next) | |
250 | continue; | |
251 | ||
252 | if (!bi->ptr1) | |
253 | { | |
254 | /* To avoid warnings. */ | |
255 | bi->word = 0; | |
256 | bi->bit = 0; | |
257 | bi->word_bit = 0; | |
258 | bi->actual = 0; | |
259 | bi->ptr2 = NULL; | |
260 | return 0; | |
261 | } | |
262 | ||
263 | if (bi->ptr1->indx == indx) | |
264 | { | |
265 | unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx; | |
266 | unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS; | |
267 | unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS; | |
268 | ||
269 | bi->word = word_in_elt; | |
270 | bi->word_bit = min - bit_in_word; | |
271 | bi->bit = min; | |
49f41d06 | 272 | bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word; |
87c476a2 ZD |
273 | } |
274 | else | |
275 | { | |
276 | bi->word = 0; | |
277 | bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
278 | bi->word_bit = bi->bit; | |
279 | bi->actual = bi->ptr1->bits[0]; | |
280 | } | |
281 | ||
282 | return bmp_iter_single_next_1 (bi); | |
283 | } | |
284 | ||
75e50bd2 | 285 | /* Returns true if all elements of the bitmap referred to by iterator BI |
87c476a2 ZD |
286 | were processed. */ |
287 | ||
288 | static inline bool | |
289 | bmp_iter_end_p (bitmap_iterator bi) | |
290 | { | |
291 | return bi.ptr1 == NULL; | |
292 | } | |
293 | ||
294 | /* Moves the iterator BI to the next bit of bitmap and returns the bit | |
295 | if available. */ | |
296 | ||
297 | static inline unsigned | |
298 | bmp_iter_single_next (bitmap_iterator *bi) | |
299 | { | |
300 | bi->bit++; | |
301 | bi->actual >>= 1; | |
302 | return bmp_iter_single_next_1 (bi); | |
303 | } | |
304 | ||
305 | /* Loop over all bits in BITMAP, starting with MIN and setting BITNUM to | |
306 | the bit number. ITER is a bitmap iterator. */ | |
307 | ||
308 | #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ | |
309 | for ((BITNUM) = bmp_iter_single_init (&(ITER), (BITMAP), (MIN)); \ | |
310 | !bmp_iter_end_p (ITER); \ | |
311 | (BITNUM) = bmp_iter_single_next (&(ITER))) | |
312 | ||
313 | /* Moves the iterator BI to the first set bit on or after the current | |
314 | position in difference of bitmaps and returns the bit if available. */ | |
315 | ||
316 | static inline unsigned | |
317 | bmp_iter_and_not_next_1 (bitmap_iterator *bi) | |
318 | { | |
319 | if (bi->actual) | |
320 | return bmp_iter_common_next_1 (bi); | |
321 | ||
322 | bi->word++; | |
323 | bi->word_bit += BITMAP_WORD_BITS; | |
324 | ||
325 | while (1) | |
326 | { | |
327 | bitmap_element *snd; | |
328 | ||
329 | if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx) | |
330 | snd = bi->ptr2; | |
331 | else | |
332 | snd = &bitmap_zero_bits; | |
333 | ||
334 | for (; | |
335 | bi->word < BITMAP_ELEMENT_WORDS; | |
336 | bi->word++, bi->word_bit += BITMAP_WORD_BITS) | |
337 | { | |
338 | bi->actual = (bi->ptr1->bits[bi->word] | |
339 | & ~snd->bits[bi->word]); | |
340 | if (bi->actual) | |
341 | { | |
342 | bi->bit = bi->word_bit; | |
343 | return bmp_iter_common_next_1 (bi); | |
344 | } | |
345 | } | |
346 | ||
347 | bi->ptr1 = bi->ptr1->next; | |
348 | if (!bi->ptr1) | |
349 | return 0; | |
350 | ||
351 | while (bi->ptr2 | |
352 | && bi->ptr2->indx < bi->ptr1->indx) | |
353 | bi->ptr2 = bi->ptr2->next; | |
354 | ||
355 | bi->word = 0; | |
356 | bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
357 | } | |
358 | } | |
359 | ||
360 | /* Initializes a bitmap iterator BI for looping over bits of bitmap | |
361 | BMP1 &~ BMP2, starting with bit MIN. Returns the first bit of | |
362 | BMP1 &~ BMP2 greater or equal to MIN if there is any. */ | |
363 | ||
364 | static inline unsigned | |
365 | bmp_iter_and_not_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2, | |
366 | unsigned min) | |
367 | { | |
368 | unsigned indx = min / BITMAP_ELEMENT_ALL_BITS; | |
369 | ||
370 | for (bi->ptr1 = bmp1->first; | |
371 | bi->ptr1 && bi->ptr1->indx < indx; | |
372 | bi->ptr1 = bi->ptr1->next) | |
373 | continue; | |
374 | ||
375 | if (!bi->ptr1) | |
376 | { | |
377 | /* To avoid warnings. */ | |
378 | bi->word = 0; | |
379 | bi->bit = 0; | |
380 | bi->word_bit = 0; | |
381 | bi->actual = 0; | |
382 | bi->ptr2 = NULL; | |
383 | return 0; | |
384 | } | |
385 | ||
386 | for (bi->ptr2 = bmp2->first; | |
387 | bi->ptr2 && bi->ptr2->indx < bi->ptr1->indx; | |
388 | bi->ptr2 = bi->ptr2->next) | |
389 | continue; | |
390 | ||
391 | if (bi->ptr1->indx == indx) | |
392 | { | |
393 | unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx; | |
394 | unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS; | |
395 | unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS; | |
396 | ||
397 | bi->word = word_in_elt; | |
398 | bi->word_bit = min - bit_in_word; | |
399 | bi->bit = min; | |
400 | ||
401 | if (bi->ptr2 && bi->ptr2->indx == indx) | |
402 | bi->actual = (bi->ptr1->bits[word_in_elt] | |
4badaa41 | 403 | & ~bi->ptr2->bits[word_in_elt]) >> bit_in_word; |
87c476a2 | 404 | else |
49f41d06 | 405 | bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word; |
87c476a2 ZD |
406 | } |
407 | else | |
408 | { | |
409 | bi->word = 0; | |
410 | bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
411 | bi->word_bit = bi->bit; | |
412 | ||
413 | if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx) | |
414 | bi->actual = (bi->ptr1->bits[0] & ~bi->ptr2->bits[0]); | |
415 | else | |
416 | bi->actual = bi->ptr1->bits[0]; | |
417 | } | |
418 | ||
419 | return bmp_iter_and_not_next_1 (bi); | |
420 | } | |
421 | ||
422 | /* Moves the iterator BI to the next bit of difference of bitmaps and returns | |
423 | the bit if available. */ | |
424 | ||
425 | static inline unsigned | |
426 | bmp_iter_and_not_next (bitmap_iterator *bi) | |
427 | { | |
428 | bi->bit++; | |
429 | bi->actual >>= 1; | |
430 | return bmp_iter_and_not_next_1 (bi); | |
431 | } | |
432 | ||
433 | /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting | |
434 | BITNUM to the bit number for all bits that are set in the first bitmap | |
435 | and not set in the second. ITER is a bitmap iterator. */ | |
436 | ||
437 | #define EXECUTE_IF_AND_COMPL_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER) \ | |
438 | for ((BITNUM) = bmp_iter_and_not_init (&(ITER), (BMP1), (BMP2), (MIN)); \ | |
439 | !bmp_iter_end_p (ITER); \ | |
440 | (BITNUM) = bmp_iter_and_not_next (&(ITER))) | |
441 | ||
442 | /* Moves the iterator BI to the first set bit on or after the current | |
443 | position in intersection of bitmaps and returns the bit if available. */ | |
444 | ||
445 | static inline unsigned | |
446 | bmp_iter_and_next_1 (bitmap_iterator *bi) | |
447 | { | |
448 | if (bi->actual) | |
449 | return bmp_iter_common_next_1 (bi); | |
450 | ||
451 | bi->word++; | |
452 | bi->word_bit += BITMAP_WORD_BITS; | |
453 | ||
454 | while (1) | |
455 | { | |
456 | for (; | |
457 | bi->word < BITMAP_ELEMENT_WORDS; | |
458 | bi->word++, bi->word_bit += BITMAP_WORD_BITS) | |
459 | { | |
460 | bi->actual = (bi->ptr1->bits[bi->word] | |
461 | & bi->ptr2->bits[bi->word]); | |
462 | if (bi->actual) | |
463 | { | |
464 | bi->bit = bi->word_bit; | |
465 | return bmp_iter_common_next_1 (bi); | |
466 | } | |
467 | } | |
468 | ||
469 | do | |
470 | { | |
471 | bi->ptr1 = bi->ptr1->next; | |
472 | if (!bi->ptr1) | |
473 | return 0; | |
474 | ||
475 | while (bi->ptr2->indx < bi->ptr1->indx) | |
476 | { | |
477 | bi->ptr2 = bi->ptr2->next; | |
478 | if (!bi->ptr2) | |
479 | { | |
480 | bi->ptr1 = NULL; | |
481 | return 0; | |
482 | } | |
483 | } | |
484 | } | |
485 | while (bi->ptr1->indx != bi->ptr2->indx); | |
486 | ||
487 | bi->word = 0; | |
488 | bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
489 | } | |
490 | } | |
491 | ||
492 | /* Initializes a bitmap iterator BI for looping over bits of bitmap | |
493 | BMP1 & BMP2, starting with bit MIN. Returns the first bit of | |
494 | BMP1 & BMP2 greater or equal to MIN if there is any. */ | |
495 | ||
496 | static inline unsigned | |
497 | bmp_iter_and_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2, | |
498 | unsigned min) | |
499 | { | |
500 | unsigned indx = min / BITMAP_ELEMENT_ALL_BITS; | |
501 | ||
502 | for (bi->ptr1 = bmp1->first; | |
503 | bi->ptr1 && bi->ptr1->indx < indx; | |
504 | bi->ptr1 = bi->ptr1->next) | |
505 | continue; | |
506 | ||
507 | if (!bi->ptr1) | |
508 | goto empty; | |
509 | ||
510 | bi->ptr2 = bmp2->first; | |
511 | if (!bi->ptr2) | |
512 | goto empty; | |
513 | ||
514 | while (1) | |
515 | { | |
516 | while (bi->ptr2->indx < bi->ptr1->indx) | |
517 | { | |
518 | bi->ptr2 = bi->ptr2->next; | |
519 | if (!bi->ptr2) | |
520 | goto empty; | |
521 | } | |
522 | ||
523 | if (bi->ptr1->indx == bi->ptr2->indx) | |
524 | break; | |
525 | ||
526 | bi->ptr1 = bi->ptr1->next; | |
527 | if (!bi->ptr1) | |
528 | goto empty; | |
529 | } | |
530 | ||
531 | if (bi->ptr1->indx == indx) | |
532 | { | |
533 | unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx; | |
534 | unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS; | |
535 | unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS; | |
536 | ||
537 | bi->word = word_in_elt; | |
538 | bi->word_bit = min - bit_in_word; | |
539 | bi->bit = min; | |
540 | ||
541 | bi->actual = (bi->ptr1->bits[word_in_elt] | |
4badaa41 | 542 | & bi->ptr2->bits[word_in_elt]) >> bit_in_word; |
87c476a2 ZD |
543 | } |
544 | else | |
545 | { | |
546 | bi->word = 0; | |
547 | bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS; | |
548 | bi->word_bit = bi->bit; | |
549 | ||
550 | bi->actual = (bi->ptr1->bits[0] & bi->ptr2->bits[0]); | |
551 | } | |
552 | ||
553 | return bmp_iter_and_next_1 (bi); | |
554 | ||
555 | empty: | |
556 | /* To avoid warnings. */ | |
557 | bi->word = 0; | |
558 | bi->bit = 0; | |
559 | bi->word_bit = 0; | |
560 | bi->actual = 0; | |
561 | bi->ptr1 = NULL; | |
562 | bi->ptr2 = NULL; | |
563 | return 0; | |
564 | } | |
565 | ||
566 | /* Moves the iterator BI to the next bit of intersection of bitmaps and returns | |
567 | the bit if available. */ | |
568 | ||
569 | static inline unsigned | |
570 | bmp_iter_and_next (bitmap_iterator *bi) | |
571 | { | |
572 | bi->bit++; | |
573 | bi->actual >>= 1; | |
574 | return bmp_iter_and_next_1 (bi); | |
575 | } | |
576 | ||
577 | /* Loop over all bits in BMP1 and BMP2, starting with MIN, setting | |
578 | BITNUM to the bit number for all bits that are set in both bitmaps. | |
579 | ITER is a bitmap iterator. */ | |
580 | ||
581 | #define EXECUTE_IF_AND_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER) \ | |
582 | for ((BITNUM) = bmp_iter_and_init (&(ITER), (BMP1), (BMP2), (MIN)); \ | |
583 | !bmp_iter_end_p (ITER); \ | |
584 | (BITNUM) = bmp_iter_and_next (&(ITER))) | |
a05924f9 | 585 | |
88657302 | 586 | #endif /* GCC_BITMAP_H */ |