|
0
|
1 /* Sparse array based bitmaps.
|
|
|
2 Copyright (C) 2007, 2008, 2009 Free Software Foundation, Inc.
|
|
|
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
|
|
|
8 Software Foundation; either version 3, or (at your option) any later
|
|
|
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
|
|
|
17 along with GCC; see the file COPYING3. If not see
|
|
|
18 <http://www.gnu.org/licenses/>. */
|
|
|
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
|
|
|
32 nonzero. */
|
|
|
33 unsigned int numwords; /* number of nonzero words. */
|
|
|
34 unsigned int cacheindex; /* which word cache is. */
|
|
|
35 EBITMAP_ELT_TYPE *elts; /* nonzero element array. */
|
|
|
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)
|
|
|
98 {
|
|
|
99 i->ptr = NULL;
|
|
|
100 i->eltnum = 0;
|
|
|
101 i->bit_num = 0;
|
|
|
102 i->word = 0;
|
|
|
103 return;
|
|
|
104 }
|
|
|
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 {
|
|
|
130 unsigned int ourn = 0;
|
|
|
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 */
|
