Merge branch 'master' of ssh://crater.dragonflybsd.org/repository/git/dragonfly
[dragonfly.git] / contrib / gcc-3.4 / gcc / bitmap.h
CommitLineData
003757ed
MD
1/* Functions to support general ended bitmaps.
2 Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003
3 Free Software Foundation, Inc.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 2, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING. If not, write to the Free
19Software Foundation, 59 Temple Place - Suite 330, Boston, MA
2002111-1307, USA. */
21
22#ifndef GCC_BITMAP_H
23#define GCC_BITMAP_H
24
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 */
29typedef unsigned long BITMAP_WORD;
30#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
31#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
32
33/* Number of words to use for each element in the linked list. */
34
35#ifndef BITMAP_ELEMENT_WORDS
36#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
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 \
44 ((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
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
51typedef struct bitmap_element_def GTY(())
52{
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. */
56 BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */
57} bitmap_element;
58
59/* Head of bitmap linked list. */
60typedef struct bitmap_head_def GTY(()) {
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. */
64 int using_obstack; /* Are we using an obstack or ggc for
65 allocation? */
66} bitmap_head;
67typedef struct bitmap_head_def *bitmap;
68
69/* Enumeration giving the various operations we support. */
70enum bitmap_bits {
71 BITMAP_AND, /* TO = FROM1 & FROM2 */
72 BITMAP_AND_COMPL, /* TO = FROM1 & ~ FROM2 */
73 BITMAP_IOR, /* TO = FROM1 | FROM2 */
74 BITMAP_XOR, /* TO = FROM1 ^ FROM2 */
75 BITMAP_IOR_COMPL /* TO = FROM1 | ~FROM2 */
76};
77
78/* Global data */
79extern bitmap_element bitmap_zero_bits; /* Zero bitmap element */
80
81/* Clear a bitmap by freeing up the linked list. */
82extern void bitmap_clear (bitmap);
83
84/* Copy a bitmap to another bitmap. */
85extern void bitmap_copy (bitmap, bitmap);
86
87/* True if two bitmaps are identical. */
88extern int bitmap_equal_p (bitmap, bitmap);
89
90/* Perform an operation on two bitmaps, yielding a third. */
91extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
92
93/* `or' into one bitmap the `and' of a second bitmap witih the complement
94 of a third. */
95extern void bitmap_ior_and_compl (bitmap, bitmap, bitmap);
96
97/* Clear a single register in a register set. */
98extern void bitmap_clear_bit (bitmap, int);
99
100/* Set a single register in a register set. */
101extern void bitmap_set_bit (bitmap, int);
102
103/* Return true if a register is set in a register set. */
104extern int bitmap_bit_p (bitmap, int);
105
106/* Debug functions to print a bitmap linked list. */
107extern void debug_bitmap (bitmap);
108extern void debug_bitmap_file (FILE *, bitmap);
109
110/* Print a bitmap. */
111extern void bitmap_print (FILE *, bitmap, const char *, const char *);
112
113/* Initialize a bitmap header. If HEAD is NULL, a new header will be
114 allocated. USING_OBSTACK indicates how elements should be allocated. */
115extern bitmap bitmap_initialize (bitmap head, int using_obstack);
116
117/* Release all memory used by the bitmap obstack. */
118extern void bitmap_release_memory (void);
119
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)
125extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap);
126extern int bitmap_first_set_bit (bitmap);
127extern int bitmap_last_set_bit (bitmap);
128
129/* Allocate a bitmap with oballoc. */
130#define BITMAP_OBSTACK_ALLOC(OBSTACK) \
131 bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
132
133/* Allocate a bitmap with ggc_alloc. */
134#define BITMAP_GGC_ALLOC() \
135 bitmap_initialize (NULL, 0)
136
137/* Allocate a bitmap with xmalloc. */
138#define BITMAP_XMALLOC() \
139 bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
140
141/* Do any cleanup needed on a bitmap when it is no longer used. */
142#define BITMAP_FREE(BITMAP) \
143do { \
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) \
153do { \
154 if (BITMAP) \
155 { \
156 bitmap_clear (BITMAP); \
157 free (BITMAP); \
158 (BITMAP) = 0; \
159 } \
160} while (0)
161
162/* Do any one-time initializations needed for bitmaps. */
163#define BITMAP_INIT_ONCE()
164
165/* Loop over all bits in BITMAP, starting with MIN, setting BITNUM to the
166 bit number and executing CODE for all bits that are set. */
167
168#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, CODE) \
169do { \
170 bitmap_element *ptr_ = (BITMAP)->first; \
171 unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
172 unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
173 unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
174 \
175 \
176 /* Find the block the minimum bit is in. */ \
177 while (ptr_ != 0 && ptr_->indx < indx_) \
178 ptr_ = ptr_->next; \
179 \
180 if (ptr_ != 0 && ptr_->indx != indx_) \
181 { \
182 bit_num_ = 0; \
183 word_num_ = 0; \
184 } \
185 \
186 for (; ptr_ != 0; ptr_ = ptr_->next) \
187 { \
188 for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
189 { \
190 BITMAP_WORD word_ = ptr_->bits[word_num_]; \
191 \
192 if (word_ != 0) \
193 { \
194 for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
195 { \
196 BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
197 \
198 if ((word_ & mask_) != 0) \
199 { \
200 word_ &= ~ mask_; \
201 (BITNUM) = (ptr_->indx * BITMAP_ELEMENT_ALL_BITS \
202 + word_num_ * BITMAP_WORD_BITS \
203 + bit_num_); \
204 CODE; \
205 \
206 if (word_ == 0) \
207 break; \
208 } \
209 } \
210 } \
211 \
212 bit_num_ = 0; \
213 } \
214 \
215 word_num_ = 0; \
216 } \
217} while (0)
218
219/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
220 BITNUM to the bit number and executing CODE for all bits that are set in
221 the first bitmap and not set in the second. */
222
223#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
224do { \
225 bitmap_element *ptr1_ = (BITMAP1)->first; \
226 bitmap_element *ptr2_ = (BITMAP2)->first; \
227 unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
228 unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
229 unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
230 \
231 /* Find the block the minimum bit is in in the first bitmap. */ \
232 while (ptr1_ != 0 && ptr1_->indx < indx_) \
233 ptr1_ = ptr1_->next; \
234 \
235 if (ptr1_ != 0 && ptr1_->indx != indx_) \
236 { \
237 bit_num_ = 0; \
238 word_num_ = 0; \
239 } \
240 \
241 for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \
242 { \
243 /* Advance BITMAP2 to the equivalent link, using an all \
244 zero element if an equivalent link doesn't exist. */ \
245 bitmap_element *tmp2_; \
246 \
247 while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \
248 ptr2_ = ptr2_->next; \
249 \
250 tmp2_ = ((ptr2_ != 0 && ptr2_->indx == ptr1_->indx) \
251 ? ptr2_ : &bitmap_zero_bits); \
252 \
253 for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
254 { \
255 BITMAP_WORD word_ = (ptr1_->bits[word_num_] \
256 & ~ tmp2_->bits[word_num_]); \
257 if (word_ != 0) \
258 { \
259 for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
260 { \
261 BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
262 \
263 if ((word_ & mask_) != 0) \
264 { \
265 word_ &= ~ mask_; \
266 (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
267 + word_num_ * BITMAP_WORD_BITS \
268 + bit_num_); \
269 \
270 CODE; \
271 if (word_ == 0) \
272 break; \
273 } \
274 } \
275 } \
276 \
277 bit_num_ = 0; \
278 } \
279 \
280 word_num_ = 0; \
281 } \
282} while (0)
283
284/* Loop over all bits in BITMAP1 and BITMAP2, starting with MIN, setting
285 BITNUM to the bit number and executing CODE for all bits that are set in
286 the both bitmaps. */
287
288#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, CODE) \
289do { \
290 bitmap_element *ptr1_ = (BITMAP1)->first; \
291 bitmap_element *ptr2_ = (BITMAP2)->first; \
292 unsigned int indx_ = (MIN) / BITMAP_ELEMENT_ALL_BITS; \
293 unsigned bit_num_ = (MIN) % BITMAP_WORD_BITS; \
294 unsigned word_num_ = (MIN) / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; \
295 \
296 /* Find the block the minimum bit is in in the first bitmap. */ \
297 while (ptr1_ != 0 && ptr1_->indx < indx_) \
298 ptr1_ = ptr1_->next; \
299 \
300 if (ptr1_ != 0 && ptr1_->indx != indx_) \
301 { \
302 bit_num_ = 0; \
303 word_num_ = 0; \
304 } \
305 \
306 for (; ptr1_ != 0 ; ptr1_ = ptr1_->next) \
307 { \
308 /* Advance BITMAP2 to the equivalent link. */ \
309 while (ptr2_ != 0 && ptr2_->indx < ptr1_->indx) \
310 ptr2_ = ptr2_->next; \
311 \
312 if (ptr2_ == 0) \
313 { \
314 /* If there are no more elements in BITMAP2, exit loop now. */ \
315 ptr1_ = (bitmap_element *)0; \
316 break; \
317 } \
318 else if (ptr2_->indx > ptr1_->indx) \
319 { \
320 bit_num_ = word_num_ = 0; \
321 continue; \
322 } \
323 \
324 for (; word_num_ < BITMAP_ELEMENT_WORDS; word_num_++) \
325 { \
326 BITMAP_WORD word_ = (ptr1_->bits[word_num_] \
327 & ptr2_->bits[word_num_]); \
328 if (word_ != 0) \
329 { \
330 for (; bit_num_ < BITMAP_WORD_BITS; bit_num_++) \
331 { \
332 BITMAP_WORD mask_ = ((BITMAP_WORD) 1) << bit_num_; \
333 \
334 if ((word_ & mask_) != 0) \
335 { \
336 word_ &= ~ mask_; \
337 (BITNUM) = (ptr1_->indx * BITMAP_ELEMENT_ALL_BITS \
338 + word_num_ * BITMAP_WORD_BITS \
339 + bit_num_); \
340 \
341 CODE; \
342 if (word_ == 0) \
343 break; \
344 } \
345 } \
346 } \
347 \
348 bit_num_ = 0; \
349 } \
350 \
351 word_num_ = 0; \
352 } \
353} while (0)
354
355#endif /* GCC_BITMAP_H */