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