Mercurial > hg > CbC > CbC_gcc
annotate gcc/ebitmap.h @ 55:77e2b8dfacca gcc-4.4.5
update it from 4.4.3 to 4.5.0
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:39:51 +0900 |
| parents | a06113de4d67 |
| children |
| rev | line source |
|---|---|
| 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
29 { |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
89 |
| 0 | 90 static inline void |
| 91 ebitmap_iter_init (ebitmap_iterator *i, ebitmap bmp, unsigned int min) | |
| 92 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
93 sbitmap_iter_init (&i->maskiter, bmp->wordmask, |
| 0 | 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 */ |