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 unsigned long ebitmap_popcount(ebitmap, unsigned long); 68 69 /* The iterator for ebitmap. */ 70 typedef struct { 71 /* The pointer to the first word of the bitmap. */ 72 EBITMAP_ELT_TYPE *ptr; 73 74 /* Element number inside ptr that we are at. */ 75 unsigned int eltnum; 76 77 /* The size of the bitmap. */ 78 unsigned int size; 79 80 /* Current bit index. */ 81 unsigned int bit_num; 82 83 /* The words currently visited. */ 84 EBITMAP_ELT_TYPE word; 85 86 /* The word mask iterator. */ 87 sbitmap_iterator maskiter; 88 } ebitmap_iterator; 89 90 static inline void 91 ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min) 92 { 93 sbitmap_iter_init (&i->maskiter, bmp->wordmask, 94 min / EBITMAP_ELT_BITS); 95 i->size = bmp->numwords; 96 if (i->size == 0) 97 { 98 i->ptr = NULL; 99 i->eltnum = 0; 100 i->bit_num = 0; 101 i->word = 0; 102 return; 103 } 104 i->ptr = bmp->elts; 105 i->bit_num = min; 106 i->eltnum = 0; 107 108 if ((min / EBITMAP_ELT_BITS) >= bmp->wordmask->n_bits) 109 { 110 i->word = 0; 111 } 112 else 113 { 114 if (TEST_BIT (bmp->wordmask, min / EBITMAP_ELT_BITS) == 0) 115 i->word = 0; 116 else 117 { 118 unsigned int wordindex = min / EBITMAP_ELT_BITS; 119 unsigned int count = sbitmap_popcount (bmp->wordmask, wordindex); 120 i->word = i->ptr[count] >> (i->bit_num % (unsigned int)EBITMAP_ELT_BITS); 121 i->eltnum = count + 1; 122 } 123 } 124 } 125 126 static inline bool 127 ebitmap_iter_cond (ebitmap_iterator *i, unsigned int *n) 128 { 129 unsigned int ourn = 0; 130 131 if (i->size == 0) 132 return false; 133 134 if (i->word == 0) 135 { 136 sbitmap_iter_next (&i->maskiter); 137 if (!sbitmap_iter_cond (&i->maskiter, &ourn)) 138 return false; 139 i->bit_num = ourn * EBITMAP_ELT_BITS; 140 i->word = i->ptr[i->eltnum++]; 141 } 142 143 /* Skip bits that are zero. */ 144 145 for (; (i->word & 1) == 0; i->word >>= 1) 146 i->bit_num++; 147 148 *n = i->bit_num; 149 return true; 150 } 151 152 static inline void 153 ebitmap_iter_next (ebitmap_iterator *i) 154 { 155 i->word >>= 1; 156 i->bit_num++; 157 } 158 159 /* Loop over all elements of EBITMAP, starting with MIN. In each 160 iteration, N is set to the index of the bit being visited. ITER is 161 an instance of ebitmap_iterator used to iterate the bitmap. */ 162 163 #define EXECUTE_IF_SET_IN_EBITMAP(EBITMAP, MIN, N, ITER) \ 164 for (ebitmap_iter_init (&(ITER), (EBITMAP), (MIN)); \ 165 ebitmap_iter_cond (&(ITER), &(N)); \ 166 ebitmap_iter_next (&(ITER))) 167 168 169 #endif /* ! GCC_EBITMAP_H */ 170