Mercurial > hg > CbC > CbC_gcc
annotate gcc/sbitmap.h @ 158:494b0b89df80 default tip
...
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 25 May 2020 18:13:55 +0900 |
| parents | 1830386684a0 |
| children |
| rev | line source |
|---|---|
| 0 | 1 /* Simple bitmaps. |
| 145 | 2 Copyright (C) 1999-2020 Free Software Foundation, Inc. |
| 0 | 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_SBITMAP_H | |
| 21 #define GCC_SBITMAP_H | |
| 22 | |
| 111 | 23 /* Implementation of sets using simple bitmap vectors. |
| 24 | |
| 25 This set representation is suitable for non-sparse sets with a known | |
| 26 (a priori) universe. The set is represented as a simple array of the | |
| 27 host's fastest unsigned integer. For a given member I in the set: | |
| 28 - the element for I will be at sbitmap[I / (bits per element)] | |
| 29 - the position for I within element is I % (bits per element) | |
| 0 | 30 |
| 111 | 31 This representation is very space-efficient for large non-sparse sets |
| 32 with random access patterns. | |
| 33 | |
| 34 The following operations can be performed in O(1) time: | |
| 35 | |
| 36 * set_size : SBITMAP_SIZE | |
| 37 * member_p : bitmap_bit_p | |
| 38 * add_member : bitmap_set_bit | |
| 39 * remove_member : bitmap_clear_bit | |
| 40 | |
| 41 Most other operations on this set representation are O(U) where U is | |
| 42 the size of the set universe: | |
| 0 | 43 |
| 111 | 44 * clear : bitmap_clear |
| 45 * choose_one : bitmap_first_set_bit / | |
| 46 bitmap_last_set_bit | |
| 47 * forall : EXECUTE_IF_SET_IN_BITMAP | |
| 48 * set_copy : bitmap_copy | |
| 49 * set_intersection : bitmap_and | |
| 50 * set_union : bitmap_ior | |
| 51 * set_difference : bitmap_and_compl | |
| 52 * set_disjuction : (not implemented) | |
| 53 * set_compare : bitmap_equal_p | |
| 54 * bit_in_range_p : bitmap_bit_in_range_p | |
| 55 | |
| 56 Some operations on 3 sets that occur frequently in data flow problems | |
| 57 are also implemented: | |
| 58 | |
| 59 * A | (B & C) : bitmap_or_and | |
| 60 * A | (B & ~C) : bitmap_ior_and_compl | |
| 61 * A & (B | C) : bitmap_and_or | |
| 62 | |
| 63 Most of the set functions have two variants: One that returns non-zero | |
| 64 if members were added or removed from the target set, and one that just | |
| 65 performs the operation without feedback. The former operations are a | |
| 66 bit more expensive but the result can often be used to avoid iterations | |
| 67 on other sets. | |
| 68 | |
| 69 Allocating a bitmap is done with sbitmap_alloc, and resizing is | |
| 70 performed with sbitmap_resize. | |
| 71 | |
| 72 The storage requirements for simple bitmap sets is O(U) where U is the | |
| 73 size of the set universe (colloquially the number of bits in the bitmap). | |
| 74 | |
| 75 This set representation works well for relatively small data flow problems | |
| 76 (there are special routines for that, see sbitmap_vector_*). The set | |
| 77 operations can be vectorized and there is almost no computating overhead, | |
| 78 so that even sparse simple bitmap sets outperform dedicated sparse set | |
| 79 representations like linked-list bitmaps. For larger problems, the size | |
| 80 overhead of simple bitmap sets gets too high and other set representations | |
| 81 have to be used. */ | |
| 82 | |
| 83 #define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u) | |
| 84 #define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT | |
| 0 | 85 |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
86 struct simple_bitmap_def |
| 0 | 87 { |
| 88 unsigned int n_bits; /* Number of bits. */ | |
| 89 unsigned int size; /* Size in elements. */ | |
| 90 SBITMAP_ELT_TYPE elms[1]; /* The elements. */ | |
|
63
b7f97abdc517
update gcc from gcc-4.5.0 to gcc-4.6
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
91 }; |
| 0 | 92 |
| 93 /* Return the set size needed for N elements. */ | |
| 94 #define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS) | |
| 111 | 95 |
| 96 /* Return the number of bits in BITMAP. */ | |
| 97 #define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits) | |
| 98 | |
| 99 /* Verify that access at INDEX in bitmap MAP is valid. */ | |
| 0 | 100 |
| 111 | 101 static inline void |
| 102 bitmap_check_index (const_sbitmap map, int index) | |
| 103 { | |
| 104 gcc_checking_assert (index >= 0); | |
| 105 gcc_checking_assert ((unsigned int)index < map->n_bits); | |
| 106 } | |
| 0 | 107 |
| 111 | 108 /* Verify that bitmaps A and B have same size. */ |
| 0 | 109 |
| 110 static inline void | |
| 111 | 111 bitmap_check_sizes (const_sbitmap a, const_sbitmap b) |
| 112 { | |
| 113 gcc_checking_assert (a->n_bits == b->n_bits); | |
| 114 } | |
| 115 | |
| 116 /* Test if bit number bitno in the bitmap is set. */ | |
| 117 static inline SBITMAP_ELT_TYPE | |
| 118 bitmap_bit_p (const_sbitmap map, int bitno) | |
| 0 | 119 { |
| 111 | 120 bitmap_check_index (map, bitno); |
| 121 | |
| 122 size_t i = bitno / SBITMAP_ELT_BITS; | |
| 123 unsigned int s = bitno % SBITMAP_ELT_BITS; | |
| 124 return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1; | |
| 125 } | |
| 126 | |
| 127 /* Set bit number BITNO in the sbitmap MAP. */ | |
| 128 | |
| 129 static inline void | |
| 130 bitmap_set_bit (sbitmap map, int bitno) | |
| 131 { | |
| 132 bitmap_check_index (map, bitno); | |
| 133 | |
| 0 | 134 map->elms[bitno / SBITMAP_ELT_BITS] |
| 135 |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS; | |
| 136 } | |
| 137 | |
| 111 | 138 /* Reset bit number BITNO in the sbitmap MAP. */ |
| 0 | 139 |
| 140 static inline void | |
| 111 | 141 bitmap_clear_bit (sbitmap map, int bitno) |
| 0 | 142 { |
| 111 | 143 bitmap_check_index (map, bitno); |
| 144 | |
| 0 | 145 map->elms[bitno / SBITMAP_ELT_BITS] |
| 146 &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS); | |
| 147 } | |
| 148 | |
| 149 /* The iterator for sbitmap. */ | |
| 111 | 150 struct sbitmap_iterator { |
| 0 | 151 /* The pointer to the first word of the bitmap. */ |
| 152 const SBITMAP_ELT_TYPE *ptr; | |
| 153 | |
| 154 /* The size of the bitmap. */ | |
| 155 unsigned int size; | |
| 156 | |
| 157 /* The current word index. */ | |
| 158 unsigned int word_num; | |
| 159 | |
| 160 /* The current bit index (not modulo SBITMAP_ELT_BITS). */ | |
| 161 unsigned int bit_num; | |
| 162 | |
| 163 /* The words currently visited. */ | |
| 164 SBITMAP_ELT_TYPE word; | |
| 111 | 165 }; |
| 0 | 166 |
| 167 /* Initialize the iterator I with sbitmap BMP and the initial index | |
| 168 MIN. */ | |
| 169 | |
| 170 static inline void | |
| 111 | 171 bmp_iter_set_init (sbitmap_iterator *i, const_sbitmap bmp, |
| 172 unsigned int min, unsigned *bit_no ATTRIBUTE_UNUSED) | |
| 0 | 173 { |
| 174 i->word_num = min / (unsigned int) SBITMAP_ELT_BITS; | |
| 175 i->bit_num = min; | |
| 176 i->size = bmp->size; | |
| 177 i->ptr = bmp->elms; | |
| 178 | |
| 179 if (i->word_num >= i->size) | |
| 180 i->word = 0; | |
| 181 else | |
| 182 i->word = (i->ptr[i->word_num] | |
| 183 >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS)); | |
| 184 } | |
| 185 | |
| 186 /* Return true if we have more bits to visit, in which case *N is set | |
| 187 to the index of the bit to be visited. Otherwise, return | |
| 188 false. */ | |
| 189 | |
| 190 static inline bool | |
| 111 | 191 bmp_iter_set (sbitmap_iterator *i, unsigned int *n) |
| 0 | 192 { |
| 193 /* Skip words that are zeros. */ | |
| 194 for (; i->word == 0; i->word = i->ptr[i->word_num]) | |
| 195 { | |
| 196 i->word_num++; | |
| 197 | |
| 198 /* If we have reached the end, break. */ | |
| 199 if (i->word_num >= i->size) | |
| 200 return false; | |
| 201 | |
| 202 i->bit_num = i->word_num * SBITMAP_ELT_BITS; | |
| 203 } | |
| 204 | |
| 205 /* Skip bits that are zero. */ | |
| 206 for (; (i->word & 1) == 0; i->word >>= 1) | |
| 207 i->bit_num++; | |
| 208 | |
| 209 *n = i->bit_num; | |
| 210 | |
| 211 return true; | |
| 212 } | |
| 213 | |
| 214 /* Advance to the next bit. */ | |
| 215 | |
| 216 static inline void | |
| 111 | 217 bmp_iter_next (sbitmap_iterator *i, unsigned *bit_no ATTRIBUTE_UNUSED) |
| 0 | 218 { |
| 219 i->word >>= 1; | |
| 220 i->bit_num++; | |
| 221 } | |
| 222 | |
| 223 /* Loop over all elements of SBITMAP, starting with MIN. In each | |
| 224 iteration, N is set to the index of the bit being visited. ITER is | |
| 225 an instance of sbitmap_iterator used to iterate the bitmap. */ | |
| 226 | |
| 111 | 227 #ifndef EXECUTE_IF_SET_IN_BITMAP |
| 228 /* See bitmap.h for the other definition of EXECUTE_IF_SET_IN_BITMAP. */ | |
| 229 #define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ | |
| 230 for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ | |
| 231 bmp_iter_set (&(ITER), &(BITNUM)); \ | |
| 232 bmp_iter_next (&(ITER), &(BITNUM))) | |
| 233 #endif | |
| 234 | |
| 235 inline void sbitmap_free (sbitmap map) | |
| 236 { | |
| 237 free (map); | |
| 238 } | |
| 0 | 239 |
| 111 | 240 inline void sbitmap_vector_free (sbitmap * vec) |
| 241 { | |
| 242 free (vec); | |
| 243 } | |
| 0 | 244 |
| 111 | 245 extern void dump_bitmap (FILE *, const_sbitmap); |
| 246 extern void debug_raw (const simple_bitmap_def &ref); | |
| 247 extern void debug_raw (const simple_bitmap_def *ptr); | |
| 248 extern void dump_bitmap_file (FILE *, const_sbitmap); | |
| 249 extern void debug (const simple_bitmap_def &ref); | |
| 250 extern void debug (const simple_bitmap_def *ptr); | |
| 251 extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *, | |
| 0 | 252 int); |
| 253 extern sbitmap sbitmap_alloc (unsigned int); | |
| 254 extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int); | |
| 255 extern sbitmap sbitmap_resize (sbitmap, unsigned int, int); | |
| 111 | 256 extern void bitmap_copy (sbitmap, const_sbitmap); |
| 257 extern int bitmap_equal_p (const_sbitmap, const_sbitmap); | |
| 258 extern unsigned int bitmap_count_bits (const_sbitmap); | |
| 259 extern bool bitmap_empty_p (const_sbitmap); | |
| 260 extern void bitmap_clear (sbitmap); | |
| 261 extern void bitmap_clear_range (sbitmap, unsigned, unsigned); | |
| 262 extern void bitmap_set_range (sbitmap, unsigned, unsigned); | |
| 263 extern void bitmap_ones (sbitmap); | |
| 264 extern void bitmap_vector_clear (sbitmap *, unsigned int); | |
| 265 extern void bitmap_vector_ones (sbitmap *, unsigned int); | |
| 0 | 266 |
| 111 | 267 extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap, |
| 268 const_sbitmap, const_sbitmap); | |
| 269 extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap); | |
| 270 extern void bitmap_not (sbitmap, const_sbitmap); | |
| 271 extern bool bitmap_or_and (sbitmap, const_sbitmap, | |
| 272 const_sbitmap, const_sbitmap); | |
| 273 extern bool bitmap_and_or (sbitmap, const_sbitmap, | |
| 274 const_sbitmap, const_sbitmap); | |
| 275 extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap); | |
| 276 extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap); | |
| 277 extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap); | |
| 278 extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap); | |
| 279 extern bool bitmap_subset_p (const_sbitmap, const_sbitmap); | |
| 280 extern bool bitmap_bit_in_range_p (const_sbitmap, unsigned int, unsigned int); | |
| 281 | |
| 282 extern int bitmap_first_set_bit (const_sbitmap); | |
| 283 extern int bitmap_last_set_bit (const_sbitmap); | |
| 0 | 284 |
| 111 | 285 extern void debug_bitmap (const_sbitmap); |
| 286 extern sbitmap sbitmap_realloc (sbitmap, unsigned int); | |
| 0 | 287 |
| 111 | 288 /* a class that ties the lifetime of a sbitmap to its scope. */ |
| 289 class auto_sbitmap | |
| 290 { | |
| 291 public: | |
| 292 explicit auto_sbitmap (unsigned int size) : | |
| 293 m_bitmap (sbitmap_alloc (size)) {} | |
| 294 ~auto_sbitmap () { sbitmap_free (m_bitmap); } | |
| 0 | 295 |
| 111 | 296 /* Allow calling sbitmap functions on our bitmap. */ |
| 297 operator sbitmap () { return m_bitmap; } | |
| 145 | 298 operator const_sbitmap () const { return m_bitmap; } |
| 0 | 299 |
| 111 | 300 private: |
| 301 /* Prevent making a copy that refers to our sbitmap. */ | |
| 302 auto_sbitmap (const auto_sbitmap &); | |
| 303 auto_sbitmap &operator = (const auto_sbitmap &); | |
| 304 #if __cplusplus >= 201103L | |
| 305 auto_sbitmap (auto_sbitmap &&); | |
| 306 auto_sbitmap &operator = (auto_sbitmap &&); | |
| 307 #endif | |
| 0 | 308 |
| 111 | 309 /* The bitmap we are managing. */ |
| 310 sbitmap m_bitmap; | |
| 311 }; | |
| 0 | 312 |
| 313 #endif /* ! GCC_SBITMAP_H */ |