1 /* Simple bitmaps. 2 Copyright (C) 1999-2020 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 #include "config.h" 21 #include "system.h" 22 #include "coretypes.h" 23 #include "sbitmap.h" 24 #include "selftest.h" 25 26 typedef SBITMAP_ELT_TYPE *sbitmap_ptr; 27 typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; 28 29 /* Return the size in bytes of a bitmap MAP. */ 30 31 static inline unsigned int sbitmap_size_bytes (const_sbitmap map) 32 { 33 return map->size * sizeof (SBITMAP_ELT_TYPE); 34 } 35 36 37 /* Bitmap manipulation routines. */ 38 39 /* Allocate a simple bitmap of N_ELMS bits. */ 40 41 sbitmap 42 sbitmap_alloc (unsigned int n_elms) 43 { 44 unsigned int bytes, size, amt; 45 sbitmap bmap; 46 47 size = SBITMAP_SET_SIZE (n_elms); 48 bytes = size * sizeof (SBITMAP_ELT_TYPE); 49 amt = (sizeof (struct simple_bitmap_def) 50 + bytes - sizeof (SBITMAP_ELT_TYPE)); 51 bmap = (sbitmap) xmalloc (amt); 52 bmap->n_bits = n_elms; 53 bmap->size = size; 54 return bmap; 55 } 56 57 /* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the 58 size of BMAP, clear the new bits to zero if the DEF argument 59 is zero, and set them to one otherwise. */ 60 61 sbitmap 62 sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) 63 { 64 unsigned int bytes, size, amt; 65 unsigned int last_bit; 66 67 size = SBITMAP_SET_SIZE (n_elms); 68 bytes = size * sizeof (SBITMAP_ELT_TYPE); 69 if (bytes > sbitmap_size_bytes (bmap)) 70 { 71 amt = (sizeof (struct simple_bitmap_def) 72 + bytes - sizeof (SBITMAP_ELT_TYPE)); 73 bmap = (sbitmap) xrealloc (bmap, amt); 74 } 75 76 if (n_elms > bmap->n_bits) 77 { 78 if (def) 79 { 80 memset (bmap->elms + bmap->size, -1, 81 bytes - sbitmap_size_bytes (bmap)); 82 83 /* Set the new bits if the original last element. */ 84 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 85 if (last_bit) 86 bmap->elms[bmap->size - 1] 87 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 88 89 /* Clear the unused bit in the new last element. */ 90 last_bit = n_elms % SBITMAP_ELT_BITS; 91 if (last_bit) 92 bmap->elms[size - 1] 93 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 94 } 95 else 96 memset (bmap->elms + bmap->size, 0, bytes - sbitmap_size_bytes (bmap)); 97 } 98 else if (n_elms < bmap->n_bits) 99 { 100 /* Clear the surplus bits in the last word. */ 101 last_bit = n_elms % SBITMAP_ELT_BITS; 102 if (last_bit) 103 bmap->elms[size - 1] 104 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 105 } 106 107 bmap->n_bits = n_elms; 108 bmap->size = size; 109 return bmap; 110 } 111 112 /* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */ 113 114 sbitmap 115 sbitmap_realloc (sbitmap src, unsigned int n_elms) 116 { 117 unsigned int bytes, size, amt; 118 sbitmap bmap; 119 120 size = SBITMAP_SET_SIZE (n_elms); 121 bytes = size * sizeof (SBITMAP_ELT_TYPE); 122 amt = (sizeof (struct simple_bitmap_def) 123 + bytes - sizeof (SBITMAP_ELT_TYPE)); 124 125 if (sbitmap_size_bytes (src) >= bytes) 126 { 127 src->n_bits = n_elms; 128 return src; 129 } 130 131 bmap = (sbitmap) xrealloc (src, amt); 132 bmap->n_bits = n_elms; 133 bmap->size = size; 134 return bmap; 135 } 136 137 /* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 138 139 sbitmap * 140 sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) 141 { 142 unsigned int i, size; 143 size_t amt, bytes, vector_bytes, elm_bytes, offset; 144 sbitmap *bitmap_vector; 145 146 size = SBITMAP_SET_SIZE (n_elms); 147 bytes = size * sizeof (SBITMAP_ELT_TYPE); 148 elm_bytes = (sizeof (struct simple_bitmap_def) 149 + bytes - sizeof (SBITMAP_ELT_TYPE)); 150 vector_bytes = n_vecs * sizeof (sbitmap *); 151 152 /* Round up `vector_bytes' to account for the alignment requirements 153 of an sbitmap. One could allocate the vector-table and set of sbitmaps 154 separately, but that requires maintaining two pointers or creating 155 a cover struct to hold both pointers (so our result is still just 156 one pointer). Neither is a bad idea, but this is simpler for now. */ 157 { 158 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 159 struct { char x; SBITMAP_ELT_TYPE y; } align; 160 int alignment = (char *) & align.y - & align.x; 161 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 162 } 163 164 amt = vector_bytes + (n_vecs * elm_bytes); 165 bitmap_vector = (sbitmap *) xmalloc (amt); 166 167 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 168 { 169 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 170 171 bitmap_vector[i] = b; 172 b->n_bits = n_elms; 173 b->size = size; 174 } 175 176 return bitmap_vector; 177 } 178 179 /* Copy sbitmap SRC to DST. */ 180 181 void 182 bitmap_copy (sbitmap dst, const_sbitmap src) 183 { 184 gcc_checking_assert (src->size <= dst->size); 185 186 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 187 } 188 189 /* Determine if a == b. */ 190 int 191 bitmap_equal_p (const_sbitmap a, const_sbitmap b) 192 { 193 bitmap_check_sizes (a, b); 194 195 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 196 } 197 198 /* Return true if the bitmap is empty. */ 199 200 bool 201 bitmap_empty_p (const_sbitmap bmap) 202 { 203 unsigned int i; 204 for (i=0; i<bmap->size; i++) 205 if (bmap->elms[i]) 206 return false; 207 208 return true; 209 } 210 211 /* Clear COUNT bits from START in BMAP. */ 212 213 void 214 bitmap_clear_range (sbitmap bmap, unsigned int start, unsigned int count) 215 { 216 if (count == 0) 217 return; 218 219 bitmap_check_index (bmap, start + count - 1); 220 221 unsigned int start_word = start / SBITMAP_ELT_BITS; 222 unsigned int start_bitno = start % SBITMAP_ELT_BITS; 223 224 /* Clearing less than a full word, starting at the beginning of a word. */ 225 if (start_bitno == 0 && count < SBITMAP_ELT_BITS) 226 { 227 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1; 228 bmap->elms[start_word] &= ~mask; 229 return; 230 } 231 232 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS; 233 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS; 234 235 /* Clearing starts somewhere in the middle of the first word. Clear up to 236 the end of the first word or the end of the requested region, whichever 237 comes first. */ 238 if (start_bitno != 0) 239 { 240 unsigned int nbits = ((start_word == end_word) 241 ? end_bitno - start_bitno 242 : SBITMAP_ELT_BITS - start_bitno); 243 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1; 244 mask <<= start_bitno; 245 bmap->elms[start_word] &= ~mask; 246 start_word++; 247 count -= nbits; 248 } 249 250 if (count == 0) 251 return; 252 253 /* Now clear words at a time until we hit a partial word. */ 254 unsigned int nwords = (end_word - start_word); 255 if (nwords) 256 { 257 memset (&bmap->elms[start_word], 0, nwords * sizeof (SBITMAP_ELT_TYPE)); 258 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT; 259 start_word += nwords; 260 } 261 262 if (count == 0) 263 return; 264 265 /* Now handle residuals in the last word. */ 266 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1; 267 bmap->elms[start_word] &= ~mask; 268 } 269 270 /* Set COUNT bits from START in BMAP. */ 271 void 272 bitmap_set_range (sbitmap bmap, unsigned int start, unsigned int count) 273 { 274 if (count == 0) 275 return; 276 277 bitmap_check_index (bmap, start + count - 1); 278 279 unsigned int start_word = start / SBITMAP_ELT_BITS; 280 unsigned int start_bitno = start % SBITMAP_ELT_BITS; 281 282 /* Setting less than a full word, starting at the beginning of a word. */ 283 if (start_bitno == 0 && count < SBITMAP_ELT_BITS) 284 { 285 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1; 286 bmap->elms[start_word] |= mask; 287 return; 288 } 289 290 unsigned int end_word = (start + count) / SBITMAP_ELT_BITS; 291 unsigned int end_bitno = (start + count) % SBITMAP_ELT_BITS; 292 293 /* Setting starts somewhere in the middle of the first word. Set up to 294 the end of the first word or the end of the requested region, whichever 295 comes first. */ 296 if (start_bitno != 0) 297 { 298 unsigned int nbits = ((start_word == end_word) 299 ? end_bitno - start_bitno 300 : SBITMAP_ELT_BITS - start_bitno); 301 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << nbits) - 1; 302 mask <<= start_bitno; 303 bmap->elms[start_word] |= mask; 304 start_word++; 305 count -= nbits; 306 } 307 308 if (count == 0) 309 return; 310 311 /* Now set words at a time until we hit a partial word. */ 312 unsigned int nwords = (end_word - start_word); 313 if (nwords) 314 { 315 memset (&bmap->elms[start_word], 0xff, 316 nwords * sizeof (SBITMAP_ELT_TYPE)); 317 count -= nwords * sizeof (SBITMAP_ELT_TYPE) * BITS_PER_UNIT; 318 start_word += nwords; 319 } 320 321 if (count == 0) 322 return; 323 324 /* Now handle residuals in the last word. */ 325 SBITMAP_ELT_TYPE mask = ((SBITMAP_ELT_TYPE)1 << count) - 1; 326 bmap->elms[start_word] |= mask; 327 } 328 329 /* Return TRUE if any bit between START and END inclusive is set within 330 the simple bitmap BMAP. Return FALSE otherwise. */ 331 332 bool 333 bitmap_bit_in_range_p (const_sbitmap bmap, unsigned int start, unsigned int end) 334 { 335 gcc_checking_assert (start <= end); 336 bitmap_check_index (bmap, end); 337 338 unsigned int start_word = start / SBITMAP_ELT_BITS; 339 unsigned int start_bitno = start % SBITMAP_ELT_BITS; 340 341 unsigned int end_word = end / SBITMAP_ELT_BITS; 342 unsigned int end_bitno = end % SBITMAP_ELT_BITS; 343 344 /* Check beginning of first word if different from zero. */ 345 if (start_bitno != 0) 346 { 347 SBITMAP_ELT_TYPE high_mask = ~(SBITMAP_ELT_TYPE)0; 348 if (start_word == end_word && end_bitno + 1 < SBITMAP_ELT_BITS) 349 high_mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1; 350 351 SBITMAP_ELT_TYPE low_mask = ((SBITMAP_ELT_TYPE)1 << start_bitno) - 1; 352 SBITMAP_ELT_TYPE mask = high_mask - low_mask; 353 if (bmap->elms[start_word] & mask) 354 return true; 355 start_word++; 356 } 357 358 if (start_word > end_word) 359 return false; 360 361 /* Now test words at a time until we hit a partial word. */ 362 unsigned int nwords = (end_word - start_word); 363 while (nwords) 364 { 365 if (bmap->elms[start_word]) 366 return true; 367 start_word++; 368 nwords--; 369 } 370 371 /* Now handle residuals in the last word. */ 372 SBITMAP_ELT_TYPE mask = ~(SBITMAP_ELT_TYPE)0; 373 if (end_bitno + 1 < SBITMAP_ELT_BITS) 374 mask = ((SBITMAP_ELT_TYPE)1 << (end_bitno + 1)) - 1; 375 return (bmap->elms[start_word] & mask) != 0; 376 } 377 378 #if GCC_VERSION < 3400 379 /* Table of number of set bits in a character, indexed by value of char. */ 380 static const unsigned char popcount_table[] = 381 { 382 0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4,1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5, 383 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 384 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 385 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 386 1,2,2,3,2,3,3,4,2,3,3,4,3,4,4,5,2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6, 387 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 388 2,3,3,4,3,4,4,5,3,4,4,5,4,5,5,6,3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7, 389 3,4,4,5,4,5,5,6,4,5,5,6,5,6,6,7,4,5,5,6,5,6,6,7,5,6,6,7,6,7,7,8, 390 }; 391 392 static unsigned long 393 sbitmap_popcount (SBITMAP_ELT_TYPE a) 394 { 395 unsigned long ret = 0; 396 unsigned i; 397 398 /* Just do this the table way for now */ 399 for (i = 0; i < HOST_BITS_PER_WIDEST_FAST_INT; i += 8) 400 ret += popcount_table[(a >> i) & 0xff]; 401 return ret; 402 } 403 #endif 404 405 /* Count and return the number of bits set in the bitmap BMAP. */ 406 407 unsigned int 408 bitmap_count_bits (const_sbitmap bmap) 409 { 410 unsigned int count = 0; 411 for (unsigned int i = 0; i < bmap->size; i++) 412 if (bmap->elms[i]) 413 { 414 #if GCC_VERSION < 3400 415 count += sbitmap_popcount (bmap->elms[i]); 416 #else 417 # if HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONG 418 count += __builtin_popcountl (bmap->elms[i]); 419 # elif HOST_BITS_PER_WIDEST_FAST_INT == HOST_BITS_PER_LONGLONG 420 count += __builtin_popcountll (bmap->elms[i]); 421 # else 422 count += __builtin_popcount (bmap->elms[i]); 423 # endif 424 #endif 425 } 426 return count; 427 } 428 429 /* Zero all elements in a bitmap. */ 430 431 void 432 bitmap_clear (sbitmap bmap) 433 { 434 memset (bmap->elms, 0, sbitmap_size_bytes (bmap)); 435 } 436 437 /* Set all elements in a bitmap to ones. */ 438 439 void 440 bitmap_ones (sbitmap bmap) 441 { 442 unsigned int last_bit; 443 444 memset (bmap->elms, -1, sbitmap_size_bytes (bmap)); 445 446 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 447 if (last_bit) 448 bmap->elms[bmap->size - 1] 449 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 450 } 451 452 /* Zero a vector of N_VECS bitmaps. */ 453 454 void 455 bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs) 456 { 457 unsigned int i; 458 459 for (i = 0; i < n_vecs; i++) 460 bitmap_clear (bmap[i]); 461 } 462 463 /* Set a vector of N_VECS bitmaps to ones. */ 464 465 void 466 bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) 467 { 468 unsigned int i; 469 470 for (i = 0; i < n_vecs; i++) 471 bitmap_ones (bmap[i]); 472 } 473 474 /* Set DST to be A union (B - C). 475 DST = A | (B & ~C). 476 Returns true if any change is made. */ 477 478 bool 479 bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 480 { 481 bitmap_check_sizes (a, b); 482 bitmap_check_sizes (b, c); 483 484 unsigned int i, n = dst->size; 485 sbitmap_ptr dstp = dst->elms; 486 const_sbitmap_ptr ap = a->elms; 487 const_sbitmap_ptr bp = b->elms; 488 const_sbitmap_ptr cp = c->elms; 489 SBITMAP_ELT_TYPE changed = 0; 490 491 for (i = 0; i < n; i++) 492 { 493 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 494 changed |= *dstp ^ tmp; 495 *dstp++ = tmp; 496 } 497 498 return changed != 0; 499 } 500 501 /* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 502 503 void 504 bitmap_not (sbitmap dst, const_sbitmap src) 505 { 506 bitmap_check_sizes (src, dst); 507 508 unsigned int i, n = dst->size; 509 sbitmap_ptr dstp = dst->elms; 510 const_sbitmap_ptr srcp = src->elms; 511 unsigned int last_bit; 512 513 for (i = 0; i < n; i++) 514 *dstp++ = ~*srcp++; 515 516 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */ 517 last_bit = src->n_bits % SBITMAP_ELT_BITS; 518 if (last_bit) 519 dst->elms[n-1] = dst->elms[n-1] 520 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 521 } 522 523 /* Set the bits in DST to be the difference between the bits 524 in A and the bits in B. i.e. dst = a & (~b). */ 525 526 void 527 bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b) 528 { 529 bitmap_check_sizes (a, b); 530 bitmap_check_sizes (b, dst); 531 532 unsigned int i, dst_size = dst->size; 533 unsigned int min_size = dst->size; 534 sbitmap_ptr dstp = dst->elms; 535 const_sbitmap_ptr ap = a->elms; 536 const_sbitmap_ptr bp = b->elms; 537 538 /* A should be at least as large as DEST, to have a defined source. */ 539 gcc_assert (a->size >= dst_size); 540 /* If minuend is smaller, we simply pretend it to be zero bits, i.e. 541 only copy the subtrahend into dest. */ 542 if (b->size < min_size) 543 min_size = b->size; 544 for (i = 0; i < min_size; i++) 545 *dstp++ = *ap++ & (~*bp++); 546 /* Now fill the rest of dest from A, if B was too short. 547 This makes sense only when destination and A differ. */ 548 if (dst != a && i != dst_size) 549 for (; i < dst_size; i++) 550 *dstp++ = *ap++; 551 } 552 553 /* Return true if there are any bits set in A are also set in B. 554 Return false otherwise. */ 555 556 bool 557 bitmap_intersect_p (const_sbitmap a, const_sbitmap b) 558 { 559 bitmap_check_sizes (a, b); 560 561 const_sbitmap_ptr ap = a->elms; 562 const_sbitmap_ptr bp = b->elms; 563 unsigned int i, n; 564 565 n = MIN (a->size, b->size); 566 for (i = 0; i < n; i++) 567 if ((*ap++ & *bp++) != 0) 568 return true; 569 570 return false; 571 } 572 573 /* Set DST to be (A and B). 574 Return nonzero if any change is made. */ 575 576 bool 577 bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) 578 { 579 bitmap_check_sizes (a, b); 580 bitmap_check_sizes (b, dst); 581 582 unsigned int i, n = dst->size; 583 sbitmap_ptr dstp = dst->elms; 584 const_sbitmap_ptr ap = a->elms; 585 const_sbitmap_ptr bp = b->elms; 586 SBITMAP_ELT_TYPE changed = 0; 587 588 for (i = 0; i < n; i++) 589 { 590 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 591 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 592 *dstp++ = tmp; 593 changed |= wordchanged; 594 } 595 return changed != 0; 596 } 597 598 /* Set DST to be (A xor B)). 599 Return nonzero if any change is made. */ 600 601 bool 602 bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) 603 { 604 bitmap_check_sizes (a, b); 605 bitmap_check_sizes (b, dst); 606 607 unsigned int i, n = dst->size; 608 sbitmap_ptr dstp = dst->elms; 609 const_sbitmap_ptr ap = a->elms; 610 const_sbitmap_ptr bp = b->elms; 611 SBITMAP_ELT_TYPE changed = 0; 612 613 for (i = 0; i < n; i++) 614 { 615 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 616 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 617 *dstp++ = tmp; 618 changed |= wordchanged; 619 } 620 return changed != 0; 621 } 622 623 /* Set DST to be (A or B)). 624 Return nonzero if any change is made. */ 625 626 bool 627 bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) 628 { 629 bitmap_check_sizes (a, b); 630 bitmap_check_sizes (b, dst); 631 632 unsigned int i, n = dst->size; 633 sbitmap_ptr dstp = dst->elms; 634 const_sbitmap_ptr ap = a->elms; 635 const_sbitmap_ptr bp = b->elms; 636 SBITMAP_ELT_TYPE changed = 0; 637 638 for (i = 0; i < n; i++) 639 { 640 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 641 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 642 *dstp++ = tmp; 643 changed |= wordchanged; 644 } 645 return changed != 0; 646 } 647 648 /* Return nonzero if A is a subset of B. */ 649 650 bool 651 bitmap_subset_p (const_sbitmap a, const_sbitmap b) 652 { 653 bitmap_check_sizes (a, b); 654 655 unsigned int i, n = a->size; 656 const_sbitmap_ptr ap, bp; 657 658 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) 659 if ((*ap | *bp) != *bp) 660 return false; 661 662 return true; 663 } 664 665 /* Set DST to be (A or (B and C)). 666 Return nonzero if any change is made. */ 667 668 bool 669 bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 670 { 671 bitmap_check_sizes (a, b); 672 bitmap_check_sizes (b, c); 673 bitmap_check_sizes (c, dst); 674 675 unsigned int i, n = dst->size; 676 sbitmap_ptr dstp = dst->elms; 677 const_sbitmap_ptr ap = a->elms; 678 const_sbitmap_ptr bp = b->elms; 679 const_sbitmap_ptr cp = c->elms; 680 SBITMAP_ELT_TYPE changed = 0; 681 682 for (i = 0; i < n; i++) 683 { 684 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 685 changed |= *dstp ^ tmp; 686 *dstp++ = tmp; 687 } 688 689 return changed != 0; 690 } 691 692 /* Set DST to be (A and (B or C)). 693 Return nonzero if any change is made. */ 694 695 bool 696 bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 697 { 698 bitmap_check_sizes (a, b); 699 bitmap_check_sizes (b, c); 700 bitmap_check_sizes (c, dst); 701 702 unsigned int i, n = dst->size; 703 sbitmap_ptr dstp = dst->elms; 704 const_sbitmap_ptr ap = a->elms; 705 const_sbitmap_ptr bp = b->elms; 706 const_sbitmap_ptr cp = c->elms; 707 SBITMAP_ELT_TYPE changed = 0; 708 709 for (i = 0; i < n; i++) 710 { 711 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 712 changed |= *dstp ^ tmp; 713 *dstp++ = tmp; 714 } 715 716 return changed != 0; 717 } 718 719 /* Return number of first bit set in the bitmap, -1 if none. */ 720 721 int 722 bitmap_first_set_bit (const_sbitmap bmap) 723 { 724 unsigned int n = 0; 725 sbitmap_iterator sbi; 726 727 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi) 728 return n; 729 return -1; 730 } 731 732 /* Return number of last bit set in the bitmap, -1 if none. */ 733 734 int 735 bitmap_last_set_bit (const_sbitmap bmap) 736 { 737 int i; 738 const SBITMAP_ELT_TYPE *const ptr = bmap->elms; 739 740 for (i = bmap->size - 1; i >= 0; i--) 741 { 742 const SBITMAP_ELT_TYPE word = ptr[i]; 743 744 if (word != 0) 745 { 746 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 747 SBITMAP_ELT_TYPE mask 748 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 749 750 while (1) 751 { 752 if ((word & mask) != 0) 753 return index; 754 755 mask >>= 1; 756 index--; 757 } 758 } 759 } 760 761 return -1; 762 } 763 764 void 765 dump_bitmap (FILE *file, const_sbitmap bmap) 766 { 767 unsigned int i, n, j; 768 unsigned int set_size = bmap->size; 769 unsigned int total_bits = bmap->n_bits; 770 771 fprintf (file, " "); 772 for (i = n = 0; i < set_size && n < total_bits; i++) 773 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 774 { 775 if (n != 0 && n % 10 == 0) 776 fprintf (file, " "); 777 778 fprintf (file, "%d", 779 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 780 } 781 782 fprintf (file, "\n"); 783 } 784 785 DEBUG_FUNCTION void 786 debug_raw (simple_bitmap_def &ref) 787 { 788 dump_bitmap (stderr, &ref); 789 } 790 791 DEBUG_FUNCTION void 792 debug_raw (simple_bitmap_def *ptr) 793 { 794 if (ptr) 795 debug_raw (*ptr); 796 else 797 fprintf (stderr, "<nil>\n"); 798 } 799 800 void 801 dump_bitmap_file (FILE *file, const_sbitmap bmap) 802 { 803 unsigned int i, pos; 804 805 fprintf (file, "n_bits = %d, set = {", bmap->n_bits); 806 807 for (pos = 30, i = 0; i < bmap->n_bits; i++) 808 if (bitmap_bit_p (bmap, i)) 809 { 810 if (pos > 70) 811 { 812 fprintf (file, "\n "); 813 pos = 0; 814 } 815 816 fprintf (file, "%d ", i); 817 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); 818 } 819 820 fprintf (file, "}\n"); 821 } 822 823 DEBUG_FUNCTION void 824 debug_bitmap (const_sbitmap bmap) 825 { 826 dump_bitmap_file (stderr, bmap); 827 } 828 829 DEBUG_FUNCTION void 830 debug (simple_bitmap_def &ref) 831 { 832 dump_bitmap_file (stderr, &ref); 833 } 834 835 DEBUG_FUNCTION void 836 debug (simple_bitmap_def *ptr) 837 { 838 if (ptr) 839 debug (*ptr); 840 else 841 fprintf (stderr, "<nil>\n"); 842 } 843 844 void 845 dump_bitmap_vector (FILE *file, const char *title, const char *subtitle, 846 sbitmap *bmaps, int n_maps) 847 { 848 int i; 849 850 fprintf (file, "%s\n", title); 851 for (i = 0; i < n_maps; i++) 852 { 853 fprintf (file, "%s %d\n", subtitle, i); 854 dump_bitmap (file, bmaps[i]); 855 } 856 857 fprintf (file, "\n"); 858 } 859 860 #if CHECKING_P 861 862 namespace selftest { 863 864 /* Selftests for sbitmaps. */ 865 866 /* Checking function that uses both bitmap_bit_in_range_p and 867 loop of bitmap_bit_p and verifies consistent results. */ 868 869 static bool 870 bitmap_bit_in_range_p_checking (sbitmap s, unsigned int start, 871 unsigned end) 872 { 873 bool r1 = bitmap_bit_in_range_p (s, start, end); 874 bool r2 = false; 875 876 for (unsigned int i = start; i <= end; i++) 877 if (bitmap_bit_p (s, i)) 878 { 879 r2 = true; 880 break; 881 } 882 883 ASSERT_EQ (r1, r2); 884 return r1; 885 } 886 887 /* Verify bitmap_set_range functions for sbitmap. */ 888 889 static void 890 test_set_range () 891 { 892 sbitmap s = sbitmap_alloc (16); 893 bitmap_clear (s); 894 895 bitmap_set_range (s, 0, 1); 896 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 0, 0)); 897 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 15)); 898 bitmap_set_range (s, 15, 1); 899 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 1, 14)); 900 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 15, 15)); 901 sbitmap_free (s); 902 903 s = sbitmap_alloc (1024); 904 bitmap_clear (s); 905 bitmap_set_range (s, 512, 1); 906 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511)); 907 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 513, 1023)); 908 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512)); 909 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 512)); 910 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 508, 513)); 911 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 508, 511)); 912 913 bitmap_clear (s); 914 bitmap_set_range (s, 512, 64); 915 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 0, 511)); 916 ASSERT_FALSE (bitmap_bit_in_range_p_checking (s, 512 + 64, 1023)); 917 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512, 512)); 918 ASSERT_TRUE (bitmap_bit_in_range_p_checking (s, 512 + 63, 512 + 63)); 919 sbitmap_free (s); 920 } 921 922 /* Verify bitmap_bit_in_range_p functions for sbitmap. */ 923 924 static void 925 test_bit_in_range () 926 { 927 sbitmap s = sbitmap_alloc (1024); 928 bitmap_clear (s); 929 930 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023)); 931 bitmap_set_bit (s, 100); 932 933 ASSERT_FALSE (bitmap_bit_in_range_p (s, 512, 1023)); 934 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 99)); 935 ASSERT_FALSE (bitmap_bit_in_range_p (s, 101, 1023)); 936 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 100)); 937 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 100)); 938 ASSERT_TRUE (bitmap_bit_in_range_p (s, 100, 100)); 939 ASSERT_TRUE (bitmap_bit_p (s, 100)); 940 941 sbitmap_free (s); 942 943 s = sbitmap_alloc (64); 944 bitmap_clear (s); 945 bitmap_set_bit (s, 63); 946 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); 947 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 63)); 948 ASSERT_TRUE (bitmap_bit_in_range_p (s, 63, 63)); 949 ASSERT_TRUE (bitmap_bit_p (s, 63)); 950 sbitmap_free (s); 951 952 s = sbitmap_alloc (1024); 953 bitmap_clear (s); 954 bitmap_set_bit (s, 128); 955 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 127)); 956 ASSERT_FALSE (bitmap_bit_in_range_p (s, 129, 1023)); 957 958 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 128)); 959 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 128)); 960 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 255)); 961 ASSERT_TRUE (bitmap_bit_in_range_p (s, 128, 254)); 962 ASSERT_TRUE (bitmap_bit_p (s, 128)); 963 964 bitmap_clear (s); 965 bitmap_set_bit (s, 8); 966 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 8)); 967 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 12)); 968 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 63)); 969 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 127)); 970 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 512)); 971 ASSERT_TRUE (bitmap_bit_in_range_p (s, 8, 8)); 972 ASSERT_TRUE (bitmap_bit_p (s, 8)); 973 974 bitmap_clear (s); 975 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 0)); 976 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 8)); 977 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 63)); 978 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 63)); 979 ASSERT_FALSE (bitmap_bit_in_range_p (s, 0, 256)); 980 981 bitmap_set_bit (s, 0); 982 bitmap_set_bit (s, 16); 983 bitmap_set_bit (s, 32); 984 bitmap_set_bit (s, 48); 985 bitmap_set_bit (s, 64); 986 ASSERT_TRUE (bitmap_bit_in_range_p (s, 0, 0)); 987 ASSERT_TRUE (bitmap_bit_in_range_p (s, 1, 16)); 988 ASSERT_TRUE (bitmap_bit_in_range_p (s, 48, 63)); 989 ASSERT_TRUE (bitmap_bit_in_range_p (s, 64, 64)); 990 ASSERT_FALSE (bitmap_bit_in_range_p (s, 1, 15)); 991 ASSERT_FALSE (bitmap_bit_in_range_p (s, 17, 31)); 992 ASSERT_FALSE (bitmap_bit_in_range_p (s, 49, 63)); 993 ASSERT_FALSE (bitmap_bit_in_range_p (s, 65, 1023)); 994 sbitmap_free (s); 995 } 996 997 /* Run all of the selftests within this file. */ 998 999 void 1000 sbitmap_c_tests () 1001 { 1002 test_set_range (); 1003 test_bit_in_range (); 1004 } 1005 1006 } // namespace selftest 1007 #endif /* CHECKING_P */ 1008