1 /* General bitsets. 2 3 Copyright (C) 2002-2006, 2009-2012 Free Software Foundation, Inc. 4 5 Contributed by Michael Hayes (m.hayes (at) elec.canterbury.ac.nz). 6 7 This program is free software: you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation, either version 3 of the License, or 10 (at your option) any later version. 11 12 This program is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with this program. If not, see <http://www.gnu.org/licenses/>. */ 19 20 #include <config.h> 21 22 #include "bitset.h" 23 24 #include <stdlib.h> 25 #include <string.h> 26 #include "abitset.h" 27 #include "lbitset.h" 28 #include "ebitset.h" 29 #include "vbitset.h" 30 #include "bitset_stats.h" 31 #include "obstack.h" 32 33 const char * const bitset_type_names[] = BITSET_TYPE_NAMES; 34 35 36 /* Return number of bytes required to create a N_BIT bitset 37 of TYPE. The bitset may grow to require more bytes than this. */ 38 size_t 39 bitset_bytes (enum bitset_type type, bitset_bindex n_bits) 40 { 41 size_t bytes; 42 43 if (bitset_stats_enabled) 44 return bitset_stats_bytes (); 45 46 switch (type) 47 { 48 default: 49 abort (); 50 51 case BITSET_ARRAY: 52 bytes = abitset_bytes (n_bits); 53 break; 54 55 case BITSET_LIST: 56 bytes = lbitset_bytes (n_bits); 57 break; 58 59 case BITSET_TABLE: 60 bytes = ebitset_bytes (n_bits); 61 break; 62 63 case BITSET_VARRAY: 64 bytes = vbitset_bytes (n_bits); 65 break; 66 } 67 68 return bytes; 69 } 70 71 72 /* Initialise bitset BSET of TYPE for N_BITS. */ 73 bitset 74 bitset_init (bitset bset, bitset_bindex n_bits, enum bitset_type type) 75 { 76 if (bitset_stats_enabled) 77 return bitset_stats_init (bset, n_bits, type); 78 79 switch (type) 80 { 81 default: 82 abort (); 83 84 case BITSET_ARRAY: 85 return abitset_init (bset, n_bits); 86 87 case BITSET_LIST: 88 return lbitset_init (bset, n_bits); 89 90 case BITSET_TABLE: 91 return ebitset_init (bset, n_bits); 92 93 case BITSET_VARRAY: 94 return vbitset_init (bset, n_bits); 95 } 96 } 97 98 99 /* Select a bitset type for a set of N_BITS and with attribute hints 100 specified by ATTR. For variable size bitsets, N_BITS is only a 101 hint and may be zero. */ 102 enum bitset_type 103 bitset_type_choose (bitset_bindex n_bits ATTRIBUTE_UNUSED, unsigned int attr) 104 { 105 /* Check attributes. */ 106 if (attr & BITSET_FIXED && attr & BITSET_VARIABLE) 107 abort (); 108 if (attr & BITSET_SPARSE && attr & BITSET_DENSE) 109 abort (); 110 111 /* Choose the type of bitset. Note that sometimes we will be asked 112 for a zero length fixed size bitset. */ 113 114 115 /* If no attributes selected, choose a good compromise. */ 116 if (!attr) 117 return BITSET_VARRAY; 118 119 if (attr & BITSET_SPARSE) 120 return BITSET_LIST; 121 122 if (attr & BITSET_FIXED) 123 return BITSET_ARRAY; 124 125 if (attr & BITSET_GREEDY) 126 return BITSET_TABLE; 127 128 return BITSET_VARRAY; 129 } 130 131 132 /* Create a bitset of N_BITS of type TYPE. */ 133 bitset 134 bitset_alloc (bitset_bindex n_bits, enum bitset_type type) 135 { 136 size_t bytes; 137 bitset bset; 138 139 bytes = bitset_bytes (type, n_bits); 140 141 bset = xcalloc (1, bytes); 142 143 /* The cache is disabled until some elements are allocated. If we 144 have variable length arrays, then we may need to allocate a dummy 145 element. */ 146 147 return bitset_init (bset, n_bits, type); 148 } 149 150 151 /* Create a bitset of N_BITS of type TYPE. */ 152 bitset 153 bitset_obstack_alloc (struct obstack *bobstack, 154 bitset_bindex n_bits, enum bitset_type type) 155 { 156 size_t bytes; 157 bitset bset; 158 159 bytes = bitset_bytes (type, n_bits); 160 161 bset = obstack_alloc (bobstack, bytes); 162 memset (bset, 0, bytes); 163 164 return bitset_init (bset, n_bits, type); 165 } 166 167 168 /* Create a bitset of N_BITS and with attribute hints specified by 169 ATTR. */ 170 bitset 171 bitset_create (bitset_bindex n_bits, unsigned int attr) 172 { 173 enum bitset_type type; 174 175 type = bitset_type_choose (n_bits, attr); 176 177 return bitset_alloc (n_bits, type); 178 } 179 180 181 /* Free bitset BSET. */ 182 void 183 bitset_free (bitset bset) 184 { 185 BITSET_FREE_ (bset); 186 free (bset); 187 } 188 189 190 /* Free bitset BSET allocated on obstack. */ 191 void 192 bitset_obstack_free (bitset bset) 193 { 194 BITSET_FREE_ (bset); 195 } 196 197 198 /* Return bitset type. */ 199 enum bitset_type 200 bitset_type_get (bitset bset) 201 { 202 enum bitset_type type; 203 204 type = BITSET_TYPE_ (bset); 205 if (type != BITSET_STATS) 206 return type; 207 208 return bitset_stats_type_get (bset); 209 } 210 211 212 /* Return name of bitset type. */ 213 const char * 214 bitset_type_name_get (bitset bset) 215 { 216 enum bitset_type type; 217 218 type = bitset_type_get (bset); 219 220 return bitset_type_names[type]; 221 } 222 223 224 /* Find next bit set in SRC starting from and including BITNO. 225 Return BITSET_BINDEX_MAX if SRC empty. */ 226 bitset_bindex 227 bitset_next (bitset src, bitset_bindex bitno) 228 { 229 bitset_bindex val; 230 bitset_bindex next = bitno; 231 232 if (!bitset_list (src, &val, 1, &next)) 233 return BITSET_BINDEX_MAX; 234 return val; 235 } 236 237 238 /* Return true if both bitsets are of the same type and size. */ 239 extern bool 240 bitset_compatible_p (bitset bset1, bitset bset2) 241 { 242 return BITSET_COMPATIBLE_ (bset1, bset2); 243 } 244 245 246 /* Find previous bit set in SRC starting from and including BITNO. 247 Return BITSET_BINDEX_MAX if SRC empty. */ 248 bitset_bindex 249 bitset_prev (bitset src, bitset_bindex bitno) 250 { 251 bitset_bindex val; 252 bitset_bindex next = bitno; 253 254 if (!bitset_list_reverse (src, &val, 1, &next)) 255 return BITSET_BINDEX_MAX; 256 return val; 257 } 258 259 260 /* Find first set bit. */ 261 bitset_bindex 262 bitset_first (bitset src) 263 { 264 return bitset_next (src, 0); 265 } 266 267 268 /* Find last set bit. */ 269 bitset_bindex 270 bitset_last (bitset src) 271 { 272 return bitset_prev (src, 0); 273 } 274 275 276 /* Is BITNO in SRC the only set bit? */ 277 bool 278 bitset_only_set_p (bitset src, bitset_bindex bitno) 279 { 280 bitset_bindex val[2]; 281 bitset_bindex next = 0; 282 283 if (bitset_list (src, val, 2, &next) != 1) 284 return false; 285 return val[0] == bitno; 286 } 287 288 289 /* Print contents of bitset BSET to FILE. */ 290 static void 291 bitset_print (FILE *file, bitset bset, bool verbose) 292 { 293 unsigned int pos; 294 bitset_bindex i; 295 bitset_iterator iter; 296 297 if (verbose) 298 fprintf (file, "n_bits = %lu, set = {", 299 (unsigned long int) bitset_size (bset)); 300 301 pos = 30; 302 BITSET_FOR_EACH (iter, bset, i, 0) 303 { 304 if (pos > 70) 305 { 306 fprintf (file, "\n"); 307 pos = 0; 308 } 309 310 fprintf (file, "%lu ", (unsigned long int) i); 311 pos += 1 + (i >= 10) + (i >= 100); 312 }; 313 314 if (verbose) 315 fprintf (file, "}\n"); 316 } 317 318 319 /* Dump bitset BSET to FILE. */ 320 void 321 bitset_dump (FILE *file, bitset bset) 322 { 323 bitset_print (file, bset, false); 324 } 325 326 327 /* Release memory associated with bitsets. */ 328 void 329 bitset_release_memory (void) 330 { 331 lbitset_release_memory (); 332 ebitset_release_memory (); 333 } 334 335 336 /* Toggle bit BITNO in bitset BSET and the new value of the bit. */ 337 bool 338 bitset_toggle_ (bitset bset, bitset_bindex bitno) 339 { 340 /* This routine is for completeness. It could be optimized if 341 required. */ 342 if (bitset_test (bset, bitno)) 343 { 344 bitset_reset (bset, bitno); 345 return false; 346 } 347 else 348 { 349 bitset_set (bset, bitno); 350 return true; 351 } 352 } 353 354 355 /* Return number of bits in bitset SRC. */ 356 bitset_bindex 357 bitset_size_ (bitset src) 358 { 359 return BITSET_NBITS_ (src); 360 } 361 362 363 /* Return number of bits set in bitset SRC. */ 364 bitset_bindex 365 bitset_count_ (bitset src) 366 { 367 bitset_bindex list[BITSET_LIST_SIZE]; 368 bitset_bindex next; 369 bitset_bindex num; 370 bitset_bindex count; 371 372 /* This could be greatly sped up by adding a count method for each 373 bitset implementation that uses a direct technique (based on 374 masks) for counting the number of bits set in a word. */ 375 376 next = 0; 377 for (count = 0; (num = bitset_list (src, list, BITSET_LIST_SIZE, &next)); 378 count += num) 379 continue; 380 381 return count; 382 } 383 384 385 /* DST = SRC. Return true if DST != SRC. 386 This is a fallback for the case where SRC and DST are different 387 bitset types. */ 388 bool 389 bitset_copy_ (bitset dst, bitset src) 390 { 391 bitset_bindex i; 392 bitset_iterator iter; 393 394 /* Convert bitset types. We assume that the DST bitset 395 is large enough to hold the SRC bitset. */ 396 bitset_zero (dst); 397 BITSET_FOR_EACH (iter, src, i, 0) 398 { 399 bitset_set (dst, i); 400 }; 401 402 return true; 403 } 404 405 406 /* This is a fallback for implementations that do not support 407 four operand operations. */ 408 static inline bool 409 bitset_op4_cmp (bitset dst, bitset src1, bitset src2, bitset src3, 410 enum bitset_ops op) 411 { 412 bool changed = false; 413 bool stats_enabled_save; 414 bitset tmp; 415 416 /* Create temporary bitset. */ 417 stats_enabled_save = bitset_stats_enabled; 418 bitset_stats_enabled = false; 419 tmp = bitset_alloc (0, bitset_type_get (dst)); 420 bitset_stats_enabled = stats_enabled_save; 421 422 switch (op) 423 { 424 default: 425 abort (); 426 427 case BITSET_OP_OR_AND: 428 bitset_or (tmp, src1, src2); 429 changed = bitset_and_cmp (dst, src3, tmp); 430 break; 431 432 case BITSET_OP_AND_OR: 433 bitset_and (tmp, src1, src2); 434 changed = bitset_or_cmp (dst, src3, tmp); 435 break; 436 437 case BITSET_OP_ANDN_OR: 438 bitset_andn (tmp, src1, src2); 439 changed = bitset_or_cmp (dst, src3, tmp); 440 break; 441 } 442 443 bitset_free (tmp); 444 return changed; 445 } 446 447 448 /* DST = (SRC1 & SRC2) | SRC3. */ 449 void 450 bitset_and_or_ (bitset dst, bitset src1, bitset src2, bitset src3) 451 { 452 bitset_and_or_cmp_ (dst, src1, src2, src3); 453 } 454 455 456 /* DST = (SRC1 & SRC2) | SRC3. Return non-zero if 457 DST != (SRC1 & SRC2) | SRC3. */ 458 bool 459 bitset_and_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) 460 { 461 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_AND_OR); 462 } 463 464 465 /* DST = (SRC1 & ~SRC2) | SRC3. */ 466 void 467 bitset_andn_or_ (bitset dst, bitset src1, bitset src2, bitset src3) 468 { 469 bitset_andn_or_cmp_ (dst, src1, src2, src3); 470 } 471 472 473 /* DST = (SRC1 & ~SRC2) | SRC3. Return non-zero if 474 DST != (SRC1 & ~SRC2) | SRC3. */ 475 bool 476 bitset_andn_or_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) 477 { 478 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_ANDN_OR); 479 } 480 481 482 /* DST = (SRC1 | SRC2) & SRC3. */ 483 void 484 bitset_or_and_ (bitset dst, bitset src1, bitset src2, bitset src3) 485 { 486 bitset_or_and_cmp_ (dst, src1, src2, src3); 487 } 488 489 490 /* DST = (SRC1 | SRC2) & SRC3. Return non-zero if 491 DST != (SRC1 | SRC2) & SRC3. */ 492 bool 493 bitset_or_and_cmp_ (bitset dst, bitset src1, bitset src2, bitset src3) 494 { 495 return bitset_op4_cmp (dst, src1, src2, src3, BITSET_OP_OR_AND); 496 } 497 498 499 /* Function to be called from debugger to print bitset. */ 500 void 501 debug_bitset (bitset bset) 502 { 503 if (bset) 504 bitset_print (stderr, bset, true); 505 } 506
