]>
Commit | Line | Data |
---|---|---|
53a853de | 1 | /* Sparse array based bitmaps. |
66647d44 | 2 | Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc. |
53a853de DB |
3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify it under | |
7 | the terms of the GNU General Public License as published by the Free | |
9dcd6f09 | 8 | Software Foundation; either version 3, or (at your option) any later |
53a853de DB |
9 | version. |
10 | ||
11 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY | |
12 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 | for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
9dcd6f09 NC |
17 | along with GCC; see the file COPYING3. If not see |
18 | <http://www.gnu.org/licenses/>. */ | |
53a853de DB |
19 | |
20 | #ifndef GCC_EBITMAP_H | |
21 | #define GCC_EBITMAP_H | |
22 | ||
23 | #include "sbitmap.h" | |
24 | ||
25 | #define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT) | |
26 | #define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT | |
27 | ||
28 | typedef struct ebitmap_def | |
29 | { | |
30 | unsigned int n_elts; /* number of elements in the array. */ | |
31 | sbitmap wordmask; /* wordmask saying which words are | |
110abdbc KH |
32 | nonzero. */ |
33 | unsigned int numwords; /* number of nonzero words. */ | |
53a853de | 34 | unsigned int cacheindex; /* which word cache is. */ |
110abdbc | 35 | EBITMAP_ELT_TYPE *elts; /* nonzero element array. */ |
53a853de DB |
36 | EBITMAP_ELT_TYPE *cache; /* last tested element, or NULL. */ |
37 | } *ebitmap; | |
38 | ||
39 | ||
40 | #define ebitmap_empty_p(MAP) ((MAP)->numwords == 0) | |
41 | #define ebitmap_free(MAP) (free((MAP)->elts), \ | |
42 | sbitmap_free ((MAP)->wordmask), \ | |
43 | free((MAP))) | |
44 | ||
45 | extern void ebitmap_set_bit (ebitmap, unsigned int); | |
46 | extern void ebitmap_clear_bit (ebitmap, unsigned int); | |
47 | extern bool ebitmap_bit_p (ebitmap, unsigned int); | |
48 | extern void dump_ebitmap (FILE *, ebitmap); | |
49 | extern void dump_ebitmap_file (FILE *, ebitmap); | |
50 | extern void dump_ebitmap_vector (FILE *, const char *, const char *, ebitmap *, | |
51 | int); | |
52 | extern ebitmap ebitmap_alloc (unsigned int); | |
53 | extern ebitmap *ebitmap_vector_alloc (unsigned int, unsigned int); | |
54 | extern void ebitmap_copy (ebitmap, ebitmap); | |
55 | extern void ebitmap_and (ebitmap, ebitmap, ebitmap); | |
56 | extern void ebitmap_and_into (ebitmap, ebitmap); | |
57 | extern bool ebitmap_and_compl (ebitmap, ebitmap, ebitmap); | |
58 | extern bool ebitmap_and_compl_into (ebitmap, ebitmap); | |
59 | extern bool ebitmap_ior_into (ebitmap, ebitmap); | |
60 | extern bool ebitmap_ior (ebitmap, ebitmap, ebitmap); | |
61 | extern bool ebitmap_ior_and_compl (ebitmap, ebitmap, ebitmap, ebitmap); | |
62 | extern bool ebitmap_ior_and_compl_into (ebitmap, ebitmap, ebitmap); | |
63 | extern bool ebitmap_equal_p (ebitmap, ebitmap); | |
64 | extern void ebitmap_clear (ebitmap); | |
65 | extern int ebitmap_last_set_bit (ebitmap); | |
66 | extern void debug_ebitmap (ebitmap); | |
67 | extern void dump_ebitmap (FILE *, ebitmap); | |
68 | extern unsigned long ebitmap_popcount(ebitmap, unsigned long); | |
69 | ||
70 | /* The iterator for ebitmap. */ | |
71 | typedef struct { | |
72 | /* The pointer to the first word of the bitmap. */ | |
73 | EBITMAP_ELT_TYPE *ptr; | |
74 | ||
75 | /* Element number inside ptr that we are at. */ | |
76 | unsigned int eltnum; | |
77 | ||
78 | /* The size of the bitmap. */ | |
79 | unsigned int size; | |
80 | ||
81 | /* Current bit index. */ | |
82 | unsigned int bit_num; | |
83 | ||
84 | /* The words currently visited. */ | |
85 | EBITMAP_ELT_TYPE word; | |
86 | ||
87 | /* The word mask iterator. */ | |
88 | sbitmap_iterator maskiter; | |
89 | } ebitmap_iterator; | |
90 | ||
91 | static inline void | |
92 | ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min) | |
93 | { | |
94 | sbitmap_iter_init (&i->maskiter, bmp->wordmask, | |
95 | min / EBITMAP_ELT_BITS); | |
96 | i->size = bmp->numwords; | |
97 | if (i->size == 0) | |
5be1c58c AO |
98 | { |
99 | i->ptr = NULL; | |
100 | i->eltnum = 0; | |
101 | i->bit_num = 0; | |
102 | i->word = 0; | |
103 | return; | |
104 | } | |
53a853de DB |
105 | i->ptr = bmp->elts; |
106 | i->bit_num = min; | |
107 | i->eltnum = 0; | |
108 | ||
109 | if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits) | |
110 | { | |
111 | i->word = 0; | |
112 | } | |
113 | else | |
114 | { | |
115 | if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0) | |
116 | i->word = 0; | |
117 | else | |
118 | { | |
119 | unsigned int wordindex = min / EBITMAP_ELT_BITS; | |
120 | unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex); | |
121 | i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS); | |
122 | i->eltnum = count + 1; | |
123 | } | |
124 | } | |
125 | } | |
126 | ||
127 | static inline bool | |
128 | ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n) | |
129 | { | |
726a989a | 130 | unsigned int ourn = 0; |
53a853de DB |
131 | |
132 | if (i->size == 0) | |
133 | return false; | |
134 | ||
135 | if (i->word == 0) | |
136 | { | |
137 | sbitmap_iter_next (&i->maskiter); | |
138 | if (!sbitmap_iter_cond (&i->maskiter, &ourn)) | |
139 | return false; | |
140 | i->bit_num = ourn * EBITMAP_ELT_BITS; | |
141 | i->word = i->ptr[i->eltnum++]; | |
142 | } | |
143 | ||
144 | /* Skip bits that are zero. */ | |
145 | ||
146 | for (; (i->word & 1) == 0; i->word >>= 1) | |
147 | i->bit_num++; | |
148 | ||
149 | *n = i->bit_num; | |
150 | return true; | |
151 | } | |
152 | ||
153 | static inline void | |
154 | ebitmap_iter_next (ebitmap_iterator *i) | |
155 | { | |
156 | i->word >>= 1; | |
157 | i->bit_num++; | |
158 | } | |
159 | ||
160 | /* Loop over all elements of EBITMAP, starting with MIN. In each | |
161 | iteration, N is set to the index of the bit being visited. ITER is | |
162 | an instance of ebitmap_iterator used to iterate the bitmap. */ | |
163 | ||
164 | #define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \ | |
165 | for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \ | |
166 | ebitmap_iter_cond (&(ITER), &(N)); \ | |
167 | ebitmap_iter_next (&(ITER))) | |
168 | ||
169 | ||
170 | #endif /* ! GCC_EBITMAP_H */ |