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