bbitset.h revision b7f2b4d529ee03ee0e4172cc06e7cd973bd9bef5
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 5This program is free software; you can redistribute it and/or modify 6it under the terms of the GNU General Public License as published by 7the Free Software Foundation; either version 2 of the License, or 8(at your option) any later version. 9 10This program is distributed in the hope that it will be useful, 11but WITHOUT ANY WARRANTY; without even the implied warranty of 12MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 13GNU General Public License for more details. 14 15You should have received a copy of the GNU General Public License 16along with this program; if not, write to the Free Software 17Foundation, 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*/ 42enum 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 46extern const char * const bitset_type_names[]; 47 48enum bitset_alloc_type {BITSET_MALLOC, BITSET_OBALLOC}; 49 50/* Data type used to store a word of bits. */ 51typedef 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. */ 60typedef size_t bitset_bindex; 61 62/* Word index. */ 63typedef 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 78enum 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 85struct 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 100typedef 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. */ 112struct 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) \ 160if (!BITSET_COMPATIBLE_ (DST, SRC)) abort (); 161 162#define BITSET_CHECK3_(DST, SRC1, SRC2) \ 163if (!BITSET_COMPATIBLE_ (DST, SRC1) \ 164 || !BITSET_COMPATIBLE_ (DST, SRC2)) abort (); 165 166#define BITSET_CHECK4_(DST, SRC1, SRC2, SRC3) \ 167if (!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 282extern bool bitset_toggle_ (bitset, bitset_bindex); 283 284extern bitset_bindex bitset_count_ (bitset); 285 286extern bitset_bindex bitset_size_ (bitset); 287 288extern bool bitset_copy_ (bitset, bitset); 289 290extern void bitset_and_or_ (bitset, bitset, bitset, bitset); 291 292extern bool bitset_and_or_cmp_ (bitset, bitset, bitset, bitset); 293 294extern void bitset_andn_or_ (bitset, bitset, bitset, bitset); 295 296extern bool bitset_andn_or_cmp_ (bitset, bitset, bitset, bitset); 297 298extern void bitset_or_and_ (bitset, bitset, bitset, bitset); 299 300extern bool bitset_or_and_cmp_ (bitset, bitset, bitset, bitset); 301 302#endif /* _BBITSET_H */ 303