Mercurial > hg > CbC > CbC_gcc

comparison gcc/ebitmap.h @ 0:a06113de4d67

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
first commit
author kent <kent@cr.ie.u-ryukyu.ac.jp>
date Fri, 17 Jul 2009 14:47:48 +0900
parents
children 77e2b8dfacca
comparison
equal deleted inserted replaced
-1:000000000000 0:a06113de4d67
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 */