OLD | NEW |
(Empty) | |
| 1 /* Base bitset stuff. |
| 2 Copyright (C) 2002, 2003, 2004, 2006 Free Software Foundation, Inc. |
| 3 Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz). |
| 4 |
| 5 This program is free software: you can redistribute it and/or modify |
| 6 it under the terms of the GNU General Public License as published by |
| 7 the Free Software Foundation, either version 3 of the License, or |
| 8 (at your option) any later version. |
| 9 |
| 10 This program is distributed in the hope that it will be useful, |
| 11 but WITHOUT ANY WARRANTY; without even the implied warranty of |
| 12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
| 13 GNU General Public License for more details. |
| 14 |
| 15 You should have received a copy of the GNU General Public License |
| 16 along with this program. If not, see <http://www.gnu.org/licenses/>. */ |
| 17 |
| 18 #ifndef _BBITSET_H |
| 19 #define _BBITSET_H |
| 20 |
| 21 #include "libiberty.h" |
| 22 |
| 23 #include <stdbool.h> |
| 24 #include <limits.h> |
| 25 #include <stddef.h> |
| 26 |
| 27 /* Currently we support five flavours of bitsets: |
| 28 BITSET_ARRAY: Array of bits (fixed size, fast for dense bitsets). |
| 29 Memory for bit array and bitset structure allocated |
| 30 contiguously. |
| 31 BITSET_LIST: Linked list of arrays of bits (variable size, least storage |
| 32 for large very sparse sets). |
| 33 BITSET_TABLE: Expandable table of pointers to arrays of bits |
| 34 (variable size, less storage for large sparse sets). |
| 35 Faster than BITSET_LIST for random access. |
| 36 BITSET_VARRAY: Variable array of bits (variable size, fast for |
| 37 dense bitsets). |
| 38 BITSET_STATS: Wrapper bitset for internal use only. Used for gathering |
| 39 statistics and/or better run-time checking. |
| 40 */ |
| 41 enum bitset_type {BITSET_ARRAY, BITSET_LIST, BITSET_TABLE, BITSET_VARRAY, |
| 42 BITSET_TYPE_NUM, BITSET_STATS}; |
| 43 #define BITSET_TYPE_NAMES {"abitset", "lbitset", "ebitset", "vbitset"} |
| 44 |
| 45 extern const char * const bitset_type_names[]; |
| 46 |
| 47 enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC}; |
| 48 |
| 49 /* Data type used to store a word of bits. */ |
| 50 typedef unsigned long int bitset_word; |
| 51 #define BITSET_WORD_BITS ((unsigned int) (CHAR_BIT * sizeof (bitset_word))) |
| 52 |
| 53 /* Bit index. In theory we might need a type wider than size_t, but |
| 54 in practice we lose at most a factor of CHAR_BIT by going with |
| 55 size_t, and that is good enough. If this type is changed to be |
| 56 wider than size_t, the code needs to be modified to check for |
| 57 overflow when converting bit counts to byte or word counts. |
| 58 The bit and word index types must be unsigned. */ |
| 59 typedef size_t bitset_bindex; |
| 60 |
| 61 /* Word index. */ |
| 62 typedef size_t bitset_windex; |
| 63 |
| 64 /* Maximum values for commonly-used unsigned types. BITSET_SIZE_MAX |
| 65 always equals SIZE_MAX, but some older systems lack SIZE_MAX. */ |
| 66 #define BITSET_BINDEX_MAX ((bitset_bindex) -1) |
| 67 |
| 68 /* Limit max word index to the maximum value of a signed integer |
| 69 to simplify cache disabling. */ |
| 70 #define BITSET_WINDEX_MAX (((bitset_windex) -1) >> 1) |
| 71 #define BITSET_SIZE_MAX ((size_t) -1) |
| 72 |
| 73 #define BITSET_MSB ((bitset_word) 1 << (BITSET_WORD_BITS - 1)) |
| 74 |
| 75 #define BITSET_LIST_SIZE 1024 |
| 76 |
| 77 enum bitset_ops {BITSET_OP_ZERO, BITSET_OP_ONES, |
| 78 BITSET_OP_COPY, BITSET_OP_NOT, |
| 79 BITSET_OP_EMPTY_P, BITSET_OP_EQUAL_P, |
| 80 BITSET_OP_SUBSET_P, BITSET_OP_DISJOINT_P, |
| 81 BITSET_OP_AND, BITSET_OP_OR, BITSET_OP_XOR, BITSET_OP_ANDN, |
| 82 BITSET_OP_OR_AND, BITSET_OP_AND_OR, BITSET_OP_ANDN_OR}; |
| 83 |
| 84 struct bbitset_struct |
| 85 { |
| 86 const struct bitset_vtable *vtable; |
| 87 bitset_windex cindex; /* Cache word index. */ |
| 88 bitset_windex csize; /* Cache size in words. */ |
| 89 bitset_word *cdata; /* Cache data pointer. */ |
| 90 bitset_bindex n_bits; /* Number of bits. */ |
| 91 /* Perhaps we could sacrifice another word to indicate |
| 92 that the bitset is known to be zero, that a bit has been set |
| 93 in the cache, and that a bit has been cleared in the cache. |
| 94 This would speed up some of the searches but slightly slow down |
| 95 bit set/reset operations of cached bits. */ |
| 96 }; |
| 97 |
| 98 |
| 99 typedef union bitset_union *bitset; |
| 100 |
| 101 |
| 102 /* Private accessor macros to bitset structure. */ |
| 103 #define BITSET_VTABLE_(SRC) (SRC)->b.vtable |
| 104 #define BITSET_CINDEX_(SRC) (SRC)->b.cindex |
| 105 #define BITSET_CDATA_(SRC) (SRC)->b.cdata |
| 106 #define BITSET_CSIZE_(SRC) (SRC)->b.csize |
| 107 #define BITSET_NBITS_(SRC) (SRC)->b.n_bits |
| 108 |
| 109 |
| 110 /* The contents of this structure should be considered private. */ |
| 111 struct bitset_vtable |
| 112 { |
| 113 void (*set) (bitset, bitset_bindex); |
| 114 void (*reset) (bitset, bitset_bindex); |
| 115 bool (*toggle) (bitset, bitset_bindex); |
| 116 bool (*test) (bitset, bitset_bindex); |
| 117 bitset_bindex (*resize) (bitset, bitset_bindex); |
| 118 bitset_bindex (*size) (bitset); |
| 119 bitset_bindex (*count) (bitset); |
| 120 |
| 121 bool (*empty_p) (bitset); |
| 122 void (*ones) (bitset); |
| 123 void (*zero) (bitset); |
| 124 |
| 125 void (*copy) (bitset, bitset); |
| 126 bool (*disjoint_p) (bitset, bitset); |
| 127 bool (*equal_p) (bitset, bitset); |
| 128 void (*not_) (bitset, bitset); |
| 129 bool (*subset_p) (bitset, bitset); |
| 130 |
| 131 void (*and_) (bitset, bitset, bitset); |
| 132 bool (*and_cmp) (bitset, bitset, bitset); |
| 133 void (*andn) (bitset, bitset, bitset); |
| 134 bool (*andn_cmp) (bitset, bitset, bitset); |
| 135 void (*or_) (bitset, bitset, bitset); |
| 136 bool (*or_cmp) (bitset, bitset, bitset); |
| 137 void (*xor_) (bitset, bitset, bitset); |
| 138 bool (*xor_cmp) (bitset, bitset, bitset); |
| 139 |
| 140 void (*and_or) (bitset, bitset, bitset, bitset); |
| 141 bool (*and_or_cmp) (bitset, bitset, bitset, bitset); |
| 142 void (*andn_or) (bitset, bitset, bitset, bitset); |
| 143 bool (*andn_or_cmp) (bitset, bitset, bitset, bitset); |
| 144 void (*or_and) (bitset, bitset, bitset, bitset); |
| 145 bool (*or_and_cmp) (bitset, bitset, bitset, bitset); |
| 146 |
| 147 bitset_bindex (*list) (bitset, bitset_bindex *, bitset_bindex, |
| 148 bitset_bindex *); |
| 149 bitset_bindex (*list_reverse) (bitset, bitset_bindex *, bitset_bindex, |
| 150 bitset_bindex *); |
| 151 void (*free) (bitset); |
| 152 enum bitset_type type; |
| 153 }; |
| 154 |
| 155 #define BITSET_COMPATIBLE_(BSET1, BSET2) \ |
| 156 ((BSET1)->b.vtable == (BSET2)->b.vtable) |
| 157 |
| 158 #define BITSET_CHECK2_(DST, SRC) \ |
| 159 if (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); |
| 160 |
| 161 #define BITSET_CHECK3_(DST, SRC1, SRC2) \ |
| 162 if (!BITSET_COMPATIBLE_ (DST, SRC1) \ |
| 163 || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); |
| 164 |
| 165 #define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ |
| 166 if (!BITSET_COMPATIBLE_ (DST, SRC1) || !BITSET_COMPATIBLE_ (DST, SRC2) \ |
| 167 || !BITSET_COMPATIBLE_ (DST, SRC3)) abort (); |
| 168 |
| 169 |
| 170 /* Redefine number of bits in bitset DST. */ |
| 171 #define BITSET_RESIZE_(DST, SIZE) (DST)->b.vtable->resize (DST, SIZE) |
| 172 |
| 173 /* Return size in bits of bitset SRC. */ |
| 174 #define BITSET_SIZE_(SRC) (SRC)->b.vtable->size (SRC) |
| 175 |
| 176 /* Return number of bits set in bitset SRC. */ |
| 177 #define BITSET_COUNT_(SRC) (SRC)->b.vtable->count (SRC) |
| 178 |
| 179 /* Return type of bitset SRC. */ |
| 180 #define BITSET_TYPE_(DST) (DST)->b.vtable->type |
| 181 |
| 182 /* Set bit BITNO in bitset DST. */ |
| 183 #define BITSET_SET_(DST, BITNO) (DST)->b.vtable->set (DST, BITNO) |
| 184 |
| 185 /* Reset bit BITNO in bitset DST. */ |
| 186 #define BITSET_RESET_(DST, BITNO) (DST)->b.vtable->reset (DST, BITNO) |
| 187 |
| 188 /* Toggle bit BITNO in bitset DST. */ |
| 189 #define BITSET_TOGGLE_(DST, BITNO) (DST)->b.vtable->toggle (DST, BITNO) |
| 190 |
| 191 /* Return non-zero if bit BITNO in bitset SRC is set. */ |
| 192 #define BITSET_TEST_(SRC, BITNO) (SRC)->b.vtable->test (SRC, BITNO) |
| 193 |
| 194 /* Free bitset SRC. */ |
| 195 #define BITSET_FREE_(SRC)\ |
| 196 ((SRC)->b.vtable->free ? (SRC)->b.vtable->free (SRC) :(void)0) |
| 197 |
| 198 |
| 199 /* Return SRC == 0. */ |
| 200 #define BITSET_EMPTY_P_(SRC) (SRC)->b.vtable->empty_p (SRC) |
| 201 |
| 202 /* DST = ~0. */ |
| 203 #define BITSET_ONES_(DST) (DST)->b.vtable->ones (DST) |
| 204 |
| 205 /* DST = 0. */ |
| 206 #define BITSET_ZERO_(DST) (DST)->b.vtable->zero (DST) |
| 207 |
| 208 |
| 209 |
| 210 /* DST = SRC. */ |
| 211 #define BITSET_COPY_(DST, SRC) (SRC)->b.vtable->copy (DST, SRC) |
| 212 |
| 213 /* Return DST & SRC == 0. */ |
| 214 #define BITSET_DISJOINT_P_(DST, SRC) (SRC)->b.vtable->disjoint_p (DST, SRC) |
| 215 |
| 216 /* Return DST == SRC. */ |
| 217 #define BITSET_EQUAL_P_(DST, SRC) (SRC)->b.vtable->equal_p (DST, SRC) |
| 218 |
| 219 /* DST = ~SRC. */ |
| 220 #define BITSET_NOT_(DST, SRC) (SRC)->b.vtable->not_ (DST, SRC) |
| 221 |
| 222 /* Return DST == DST | SRC. */ |
| 223 #define BITSET_SUBSET_P_(DST, SRC) (SRC)->b.vtable->subset_p (DST, SRC) |
| 224 |
| 225 |
| 226 /* DST = SRC1 & SRC2. */ |
| 227 #define BITSET_AND_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_ (DST, SRC1, SRC2) |
| 228 #define BITSET_AND_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->and_cmp (DST, SRC1, S
RC2) |
| 229 |
| 230 /* DST = SRC1 & ~SRC2. */ |
| 231 #define BITSET_ANDN_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn (DST, SRC1, SRC2) |
| 232 #define BITSET_ANDN_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->andn_cmp (DST, SRC1,
SRC2) |
| 233 |
| 234 /* DST = SRC1 | SRC2. */ |
| 235 #define BITSET_OR_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_ (DST, SRC1, SRC2) |
| 236 #define BITSET_OR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->or_cmp (DST, SRC1, SRC
2) |
| 237 |
| 238 /* DST = SRC1 ^ SRC2. */ |
| 239 #define BITSET_XOR_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_ (DST, SRC1, SRC2) |
| 240 #define BITSET_XOR_CMP_(DST, SRC1, SRC2) (SRC1)->b.vtable->xor_cmp (DST, SRC1, S
RC2) |
| 241 |
| 242 |
| 243 |
| 244 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if |
| 245 DST != (SRC1 & SRC2) | SRC3. */ |
| 246 #define BITSET_AND_OR_(DST, SRC1, SRC2, SRC3) \ |
| 247 (SRC1)->b.vtable->and_or (DST, SRC1, SRC2, SRC3) |
| 248 #define BITSET_AND_OR_CMP_(DST, SRC1, SRC2, SRC3) \ |
| 249 (SRC1)->b.vtable->and_or_cmp (DST, SRC1, SRC2, SRC3) |
| 250 |
| 251 /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if |
| 252 DST != (SRC1 & ~SRC2) | SRC3. */ |
| 253 #define BITSET_ANDN_OR_(DST, SRC1, SRC2, SRC3) \ |
| 254 (SRC1)->b.vtable->andn_or (DST, SRC1, SRC2, SRC3) |
| 255 #define BITSET_ANDN_OR_CMP_(DST, SRC1, SRC2, SRC3) \ |
| 256 (SRC1)->b.vtable->andn_or_cmp (DST, SRC1, SRC2, SRC3) |
| 257 |
| 258 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if |
| 259 DST != (SRC1 | SRC2) & SRC3. */ |
| 260 #define BITSET_OR_AND_(DST, SRC1, SRC2, SRC3) \ |
| 261 (SRC1)->b.vtable->or_and (DST, SRC1, SRC2, SRC3) |
| 262 #define BITSET_OR_AND_CMP_(DST, SRC1, SRC2, SRC3) \ |
| 263 (SRC1)->b.vtable->or_and_cmp (DST, SRC1, SRC2, SRC3) |
| 264 |
| 265 |
| 266 /* Find list of up to NUM bits set in BSET starting from and including |
| 267 *NEXT. Return with actual number of bits found and with *NEXT |
| 268 indicating where search stopped. */ |
| 269 #define BITSET_LIST_(BSET, LIST, NUM, NEXT) \ |
| 270 (BSET)->b.vtable->list (BSET, LIST, NUM, NEXT) |
| 271 |
| 272 /* Find reverse list of up to NUM bits set in BSET starting from and |
| 273 including NEXT. Return with actual number of bits found and with |
| 274 *NEXT indicating where search stopped. */ |
| 275 #define BITSET_LIST_REVERSE_(BSET, LIST, NUM, NEXT) \ |
| 276 (BSET)->b.vtable->list_reverse (BSET, LIST, NUM, NEXT) |
| 277 |
| 278 |
| 279 /* Private functions for bitset implementations. */ |
| 280 |
| 281 extern bool bitset_toggle_ (bitset, bitset_bindex); |
| 282 |
| 283 extern bitset_bindex bitset_count_ (bitset); |
| 284 |
| 285 extern bitset_bindex bitset_size_ (bitset); |
| 286 |
| 287 extern bool bitset_copy_ (bitset, bitset); |
| 288 |
| 289 extern void bitset_and_or_ (bitset, bitset, bitset, bitset); |
| 290 |
| 291 extern bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset); |
| 292 |
| 293 extern void bitset_andn_or_ (bitset, bitset, bitset, bitset); |
| 294 |
| 295 extern bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset); |
| 296 |
| 297 extern void bitset_or_and_ (bitset, bitset, bitset, bitset); |
| 298 |
| 299 extern bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset); |
| 300 |
| 301 #endif /* _BBITSET_H */ |
OLD | NEW |