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