1/* Simple bitmaps. 2 Copyright (C) 1999-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify it under 7the terms of the GNU General Public License as published by the Free 8Software Foundation; either version 3, or (at your option) any later 9version. 10 11GCC is distributed in the hope that it will be useful, but WITHOUT ANY 12WARRANTY; without even the implied warranty of MERCHANTABILITY or 13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 14for more details. 15 16You should have received a copy of the GNU General Public License 17along 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 25/* This suffices for roughly 99% of the hosts we run on, and the rest 26 don't have 256 bit integers. */ 27#if SBITMAP_ELT_BITS > 255 28#error Need to increase size of datatype used for popcount 29#endif 30 31#if GCC_VERSION >= 3400 32# if SBITMAP_ELT_BITS == HOST_BITS_PER_LONG 33# define do_popcount(x) __builtin_popcountl (x) 34# elif SBITMAP_ELT_BITS == HOST_BITS_PER_LONGLONG 35# define do_popcount(x) __builtin_popcountll (x) 36# else 37# error "internal error: sbitmap.h and hwint.h are inconsistent" 38# endif 39#else 40static unsigned long sbitmap_elt_popcount (SBITMAP_ELT_TYPE); 41# define do_popcount(x) sbitmap_elt_popcount (x) 42#endif 43 44typedef SBITMAP_ELT_TYPE *sbitmap_ptr; 45typedef const SBITMAP_ELT_TYPE *const_sbitmap_ptr; 46 47/* Return the size in bytes of a bitmap MAP. */ 48 49static inline unsigned int sbitmap_size_bytes (const_sbitmap map) 50{ 51 return map->size * sizeof (SBITMAP_ELT_TYPE); 52} 53 54/* This macro controls debugging that is as expensive as the 55 operations it verifies. */ 56 57/* #define BITMAP_DEBUGGING */ 58#ifdef BITMAP_DEBUGGING 59 60/* Verify the population count of sbitmap A matches the cached value, 61 if there is a cached value. */ 62 63static void 64sbitmap_verify_popcount (const_sbitmap a) 65{ 66 unsigned ix; 67 unsigned int lastword; 68 69 if (!a->popcount) 70 return; 71 72 lastword = a->size; 73 for (ix = 0; ix < lastword; ix++) 74 gcc_assert (a->popcount[ix] == do_popcount (a->elms[ix])); 75} 76#endif 77 78/* Bitmap manipulation routines. */ 79 80/* Allocate a simple bitmap of N_ELMS bits. */ 81 82sbitmap 83sbitmap_alloc (unsigned int n_elms) 84{ 85 unsigned int bytes, size, amt; 86 sbitmap bmap; 87 88 size = SBITMAP_SET_SIZE (n_elms); 89 bytes = size * sizeof (SBITMAP_ELT_TYPE); 90 amt = (sizeof (struct simple_bitmap_def) 91 + bytes - sizeof (SBITMAP_ELT_TYPE)); 92 bmap = (sbitmap) xmalloc (amt); 93 bmap->n_bits = n_elms; 94 bmap->size = size; 95 bmap->popcount = NULL; 96 return bmap; 97} 98 99/* Allocate a simple bitmap of N_ELMS bits, and a popcount array. */ 100 101sbitmap 102sbitmap_alloc_with_popcount (unsigned int n_elms) 103{ 104 sbitmap const bmap = sbitmap_alloc (n_elms); 105 bmap->popcount = XNEWVEC (unsigned char, bmap->size); 106 return bmap; 107} 108 109/* Resize a simple bitmap BMAP to N_ELMS bits. If increasing the 110 size of BMAP, clear the new bits to zero if the DEF argument 111 is zero, and set them to one otherwise. */ 112 113sbitmap 114sbitmap_resize (sbitmap bmap, unsigned int n_elms, int def) 115{ 116 unsigned int bytes, size, amt; 117 unsigned int last_bit; 118 119 size = SBITMAP_SET_SIZE (n_elms); 120 bytes = size * sizeof (SBITMAP_ELT_TYPE); 121 if (bytes > sbitmap_size_bytes (bmap)) 122 { 123 amt = (sizeof (struct simple_bitmap_def) 124 + bytes - sizeof (SBITMAP_ELT_TYPE)); 125 bmap = (sbitmap) xrealloc (bmap, amt); 126 if (bmap->popcount) 127 bmap->popcount = XRESIZEVEC (unsigned char, bmap->popcount, size); 128 } 129 130 if (n_elms > bmap->n_bits) 131 { 132 if (def) 133 { 134 memset (bmap->elms + bmap->size, -1, 135 bytes - sbitmap_size_bytes (bmap)); 136 137 /* Set the new bits if the original last element. */ 138 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 139 if (last_bit) 140 bmap->elms[bmap->size - 1] 141 |= ~((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 142 143 /* Clear the unused bit in the new last element. */ 144 last_bit = n_elms % SBITMAP_ELT_BITS; 145 if (last_bit) 146 bmap->elms[size - 1] 147 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 148 } 149 else 150 { 151 memset (bmap->elms + bmap->size, 0, 152 bytes - sbitmap_size_bytes (bmap)); 153 if (bmap->popcount) 154 memset (bmap->popcount + bmap->size, 0, 155 (size * sizeof (unsigned char)) 156 - (bmap->size * sizeof (unsigned char))); 157 158 } 159 } 160 else if (n_elms < bmap->n_bits) 161 { 162 /* Clear the surplus bits in the last word. */ 163 last_bit = n_elms % SBITMAP_ELT_BITS; 164 if (last_bit) 165 { 166 bmap->elms[size - 1] 167 &= (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 168 if (bmap->popcount) 169 bmap->popcount[size - 1] = do_popcount (bmap->elms[size - 1]); 170 } 171 } 172 173 bmap->n_bits = n_elms; 174 bmap->size = size; 175 return bmap; 176} 177 178/* Re-allocate a simple bitmap of N_ELMS bits. New storage is uninitialized. */ 179 180sbitmap 181sbitmap_realloc (sbitmap src, unsigned int n_elms) 182{ 183 unsigned int bytes, size, amt; 184 sbitmap bmap; 185 186 size = SBITMAP_SET_SIZE (n_elms); 187 bytes = size * sizeof (SBITMAP_ELT_TYPE); 188 amt = (sizeof (struct simple_bitmap_def) 189 + bytes - sizeof (SBITMAP_ELT_TYPE)); 190 191 if (sbitmap_size_bytes (src) >= bytes) 192 { 193 src->n_bits = n_elms; 194 return src; 195 } 196 197 bmap = (sbitmap) xrealloc (src, amt); 198 bmap->n_bits = n_elms; 199 bmap->size = size; 200 return bmap; 201} 202 203/* Allocate a vector of N_VECS bitmaps of N_ELMS bits. */ 204 205sbitmap * 206sbitmap_vector_alloc (unsigned int n_vecs, unsigned int n_elms) 207{ 208 unsigned int i, bytes, offset, elm_bytes, size, amt, vector_bytes; 209 sbitmap *bitmap_vector; 210 211 size = SBITMAP_SET_SIZE (n_elms); 212 bytes = size * sizeof (SBITMAP_ELT_TYPE); 213 elm_bytes = (sizeof (struct simple_bitmap_def) 214 + bytes - sizeof (SBITMAP_ELT_TYPE)); 215 vector_bytes = n_vecs * sizeof (sbitmap *); 216 217 /* Round up `vector_bytes' to account for the alignment requirements 218 of an sbitmap. One could allocate the vector-table and set of sbitmaps 219 separately, but that requires maintaining two pointers or creating 220 a cover struct to hold both pointers (so our result is still just 221 one pointer). Neither is a bad idea, but this is simpler for now. */ 222 { 223 /* Based on DEFAULT_ALIGNMENT computation in obstack.c. */ 224 struct { char x; SBITMAP_ELT_TYPE y; } align; 225 int alignment = (char *) & align.y - & align.x; 226 vector_bytes = (vector_bytes + alignment - 1) & ~ (alignment - 1); 227 } 228 229 amt = vector_bytes + (n_vecs * elm_bytes); 230 bitmap_vector = (sbitmap *) xmalloc (amt); 231 232 for (i = 0, offset = vector_bytes; i < n_vecs; i++, offset += elm_bytes) 233 { 234 sbitmap b = (sbitmap) ((char *) bitmap_vector + offset); 235 236 bitmap_vector[i] = b; 237 b->n_bits = n_elms; 238 b->size = size; 239 b->popcount = NULL; 240 } 241 242 return bitmap_vector; 243} 244 245/* Copy sbitmap SRC to DST. */ 246 247void 248bitmap_copy (sbitmap dst, const_sbitmap src) 249{ 250 memcpy (dst->elms, src->elms, sizeof (SBITMAP_ELT_TYPE) * dst->size); 251 if (dst->popcount) 252 memcpy (dst->popcount, src->popcount, sizeof (unsigned char) * dst->size); 253} 254 255/* Determine if a == b. */ 256int 257bitmap_equal_p (const_sbitmap a, const_sbitmap b) 258{ 259 return !memcmp (a->elms, b->elms, sizeof (SBITMAP_ELT_TYPE) * a->size); 260} 261 262/* Return true if the bitmap is empty. */ 263 264bool 265bitmap_empty_p (const_sbitmap bmap) 266{ 267 unsigned int i; 268 for (i=0; i<bmap->size; i++) 269 if (bmap->elms[i]) 270 return false; 271 272 return true; 273} 274 275 276/* Zero all elements in a bitmap. */ 277 278void 279bitmap_clear (sbitmap bmap) 280{ 281 memset (bmap->elms, 0, sbitmap_size_bytes (bmap)); 282 if (bmap->popcount) 283 memset (bmap->popcount, 0, bmap->size * sizeof (unsigned char)); 284} 285 286/* Set all elements in a bitmap to ones. */ 287 288void 289bitmap_ones (sbitmap bmap) 290{ 291 unsigned int last_bit; 292 293 memset (bmap->elms, -1, sbitmap_size_bytes (bmap)); 294 if (bmap->popcount) 295 memset (bmap->popcount, -1, bmap->size * sizeof (unsigned char)); 296 297 last_bit = bmap->n_bits % SBITMAP_ELT_BITS; 298 if (last_bit) 299 { 300 bmap->elms[bmap->size - 1] 301 = (SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit); 302 if (bmap->popcount) 303 bmap->popcount[bmap->size - 1] 304 = do_popcount (bmap->elms[bmap->size - 1]); 305 } 306} 307 308/* Zero a vector of N_VECS bitmaps. */ 309 310void 311bitmap_vector_clear (sbitmap *bmap, unsigned int n_vecs) 312{ 313 unsigned int i; 314 315 for (i = 0; i < n_vecs; i++) 316 bitmap_clear (bmap[i]); 317} 318 319/* Set a vector of N_VECS bitmaps to ones. */ 320 321void 322bitmap_vector_ones (sbitmap *bmap, unsigned int n_vecs) 323{ 324 unsigned int i; 325 326 for (i = 0; i < n_vecs; i++) 327 bitmap_ones (bmap[i]); 328} 329 330/* Set DST to be A union (B - C). 331 DST = A | (B & ~C). 332 Returns true if any change is made. */ 333 334bool 335bitmap_ior_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 336{ 337 unsigned int i, n = dst->size; 338 sbitmap_ptr dstp = dst->elms; 339 const_sbitmap_ptr ap = a->elms; 340 const_sbitmap_ptr bp = b->elms; 341 const_sbitmap_ptr cp = c->elms; 342 SBITMAP_ELT_TYPE changed = 0; 343 344 gcc_assert (!dst->popcount); 345 346 for (i = 0; i < n; i++) 347 { 348 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & ~*cp++); 349 changed |= *dstp ^ tmp; 350 *dstp++ = tmp; 351 } 352 353 return changed != 0; 354} 355 356/* Set bitmap DST to the bitwise negation of the bitmap SRC. */ 357 358void 359bitmap_not (sbitmap dst, const_sbitmap src) 360{ 361 unsigned int i, n = dst->size; 362 sbitmap_ptr dstp = dst->elms; 363 const_sbitmap_ptr srcp = src->elms; 364 unsigned int last_bit; 365 366 gcc_assert (!dst->popcount); 367 368 for (i = 0; i < n; i++) 369 *dstp++ = ~*srcp++; 370 371 /* Zero all bits past n_bits, by ANDing dst with bitmap_ones. */ 372 last_bit = src->n_bits % SBITMAP_ELT_BITS; 373 if (last_bit) 374 dst->elms[n-1] = dst->elms[n-1] 375 & ((SBITMAP_ELT_TYPE)-1 >> (SBITMAP_ELT_BITS - last_bit)); 376} 377 378/* Set the bits in DST to be the difference between the bits 379 in A and the bits in B. i.e. dst = a & (~b). */ 380 381void 382bitmap_and_compl (sbitmap dst, const_sbitmap a, const_sbitmap b) 383{ 384 unsigned int i, dst_size = dst->size; 385 unsigned int min_size = dst->size; 386 sbitmap_ptr dstp = dst->elms; 387 const_sbitmap_ptr ap = a->elms; 388 const_sbitmap_ptr bp = b->elms; 389 390 gcc_assert (!dst->popcount); 391 392 /* A should be at least as large as DEST, to have a defined source. */ 393 gcc_assert (a->size >= dst_size); 394 /* If minuend is smaller, we simply pretend it to be zero bits, i.e. 395 only copy the subtrahend into dest. */ 396 if (b->size < min_size) 397 min_size = b->size; 398 for (i = 0; i < min_size; i++) 399 *dstp++ = *ap++ & (~*bp++); 400 /* Now fill the rest of dest from A, if B was too short. 401 This makes sense only when destination and A differ. */ 402 if (dst != a && i != dst_size) 403 for (; i < dst_size; i++) 404 *dstp++ = *ap++; 405} 406 407/* Return true if there are any bits set in A are also set in B. 408 Return false otherwise. */ 409 410bool 411bitmap_intersect_p (const_sbitmap a, const_sbitmap b) 412{ 413 const_sbitmap_ptr ap = a->elms; 414 const_sbitmap_ptr bp = b->elms; 415 unsigned int i, n; 416 417 n = MIN (a->size, b->size); 418 for (i = 0; i < n; i++) 419 if ((*ap++ & *bp++) != 0) 420 return true; 421 422 return false; 423} 424 425/* Set DST to be (A and B). 426 Return nonzero if any change is made. */ 427 428bool 429bitmap_and (sbitmap dst, const_sbitmap a, const_sbitmap b) 430{ 431 unsigned int i, n = dst->size; 432 sbitmap_ptr dstp = dst->elms; 433 const_sbitmap_ptr ap = a->elms; 434 const_sbitmap_ptr bp = b->elms; 435 bool has_popcount = dst->popcount != NULL; 436 unsigned char *popcountp = dst->popcount; 437 SBITMAP_ELT_TYPE changed = 0; 438 439 for (i = 0; i < n; i++) 440 { 441 const SBITMAP_ELT_TYPE tmp = *ap++ & *bp++; 442 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 443 if (has_popcount) 444 { 445 if (wordchanged) 446 *popcountp = do_popcount (tmp); 447 popcountp++; 448 } 449 *dstp++ = tmp; 450 changed |= wordchanged; 451 } 452#ifdef BITMAP_DEBUGGING 453 if (has_popcount) 454 sbitmap_verify_popcount (dst); 455#endif 456 return changed != 0; 457} 458 459/* Set DST to be (A xor B)). 460 Return nonzero if any change is made. */ 461 462bool 463bitmap_xor (sbitmap dst, const_sbitmap a, const_sbitmap b) 464{ 465 unsigned int i, n = dst->size; 466 sbitmap_ptr dstp = dst->elms; 467 const_sbitmap_ptr ap = a->elms; 468 const_sbitmap_ptr bp = b->elms; 469 bool has_popcount = dst->popcount != NULL; 470 unsigned char *popcountp = dst->popcount; 471 SBITMAP_ELT_TYPE changed = 0; 472 473 for (i = 0; i < n; i++) 474 { 475 const SBITMAP_ELT_TYPE tmp = *ap++ ^ *bp++; 476 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 477 if (has_popcount) 478 { 479 if (wordchanged) 480 *popcountp = do_popcount (tmp); 481 popcountp++; 482 } 483 *dstp++ = tmp; 484 changed |= wordchanged; 485 } 486#ifdef BITMAP_DEBUGGING 487 if (has_popcount) 488 sbitmap_verify_popcount (dst); 489#endif 490 return changed != 0; 491} 492 493/* Set DST to be (A or B)). 494 Return nonzero if any change is made. */ 495 496bool 497bitmap_ior (sbitmap dst, const_sbitmap a, const_sbitmap b) 498{ 499 unsigned int i, n = dst->size; 500 sbitmap_ptr dstp = dst->elms; 501 const_sbitmap_ptr ap = a->elms; 502 const_sbitmap_ptr bp = b->elms; 503 bool has_popcount = dst->popcount != NULL; 504 unsigned char *popcountp = dst->popcount; 505 SBITMAP_ELT_TYPE changed = 0; 506 507 for (i = 0; i < n; i++) 508 { 509 const SBITMAP_ELT_TYPE tmp = *ap++ | *bp++; 510 SBITMAP_ELT_TYPE wordchanged = *dstp ^ tmp; 511 if (has_popcount) 512 { 513 if (wordchanged) 514 *popcountp = do_popcount (tmp); 515 popcountp++; 516 } 517 *dstp++ = tmp; 518 changed |= wordchanged; 519 } 520#ifdef BITMAP_DEBUGGING 521 if (has_popcount) 522 sbitmap_verify_popcount (dst); 523#endif 524 return changed != 0; 525} 526 527/* Return nonzero if A is a subset of B. */ 528 529bool 530bitmap_subset_p (const_sbitmap a, const_sbitmap b) 531{ 532 unsigned int i, n = a->size; 533 const_sbitmap_ptr ap, bp; 534 535 for (ap = a->elms, bp = b->elms, i = 0; i < n; i++, ap++, bp++) 536 if ((*ap | *bp) != *bp) 537 return false; 538 539 return true; 540} 541 542/* Set DST to be (A or (B and C)). 543 Return nonzero if any change is made. */ 544 545bool 546bitmap_or_and (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 547{ 548 unsigned int i, n = dst->size; 549 sbitmap_ptr dstp = dst->elms; 550 const_sbitmap_ptr ap = a->elms; 551 const_sbitmap_ptr bp = b->elms; 552 const_sbitmap_ptr cp = c->elms; 553 SBITMAP_ELT_TYPE changed = 0; 554 555 gcc_assert (!dst->popcount); 556 557 for (i = 0; i < n; i++) 558 { 559 const SBITMAP_ELT_TYPE tmp = *ap++ | (*bp++ & *cp++); 560 changed |= *dstp ^ tmp; 561 *dstp++ = tmp; 562 } 563 564 return changed != 0; 565} 566 567/* Set DST to be (A and (B or C)). 568 Return nonzero if any change is made. */ 569 570bool 571bitmap_and_or (sbitmap dst, const_sbitmap a, const_sbitmap b, const_sbitmap c) 572{ 573 unsigned int i, n = dst->size; 574 sbitmap_ptr dstp = dst->elms; 575 const_sbitmap_ptr ap = a->elms; 576 const_sbitmap_ptr bp = b->elms; 577 const_sbitmap_ptr cp = c->elms; 578 SBITMAP_ELT_TYPE changed = 0; 579 580 gcc_assert (!dst->popcount); 581 582 for (i = 0; i < n; i++) 583 { 584 const SBITMAP_ELT_TYPE tmp = *ap++ & (*bp++ | *cp++); 585 changed |= *dstp ^ tmp; 586 *dstp++ = tmp; 587 } 588 589 return changed != 0; 590} 591 592/* Return number of first bit set in the bitmap, -1 if none. */ 593 594int 595bitmap_first_set_bit (const_sbitmap bmap) 596{ 597 unsigned int n = 0; 598 sbitmap_iterator sbi; 599 600 EXECUTE_IF_SET_IN_BITMAP (bmap, 0, n, sbi) 601 return n; 602 return -1; 603} 604 605/* Return number of last bit set in the bitmap, -1 if none. */ 606 607int 608bitmap_last_set_bit (const_sbitmap bmap) 609{ 610 int i; 611 const SBITMAP_ELT_TYPE *const ptr = bmap->elms; 612 613 for (i = bmap->size - 1; i >= 0; i--) 614 { 615 const SBITMAP_ELT_TYPE word = ptr[i]; 616 617 if (word != 0) 618 { 619 unsigned int index = (i + 1) * SBITMAP_ELT_BITS - 1; 620 SBITMAP_ELT_TYPE mask 621 = (SBITMAP_ELT_TYPE) 1 << (SBITMAP_ELT_BITS - 1); 622 623 while (1) 624 { 625 if ((word & mask) != 0) 626 return index; 627 628 mask >>= 1; 629 index--; 630 } 631 } 632 } 633 634 return -1; 635} 636 637void 638dump_bitmap (FILE *file, const_sbitmap bmap) 639{ 640 unsigned int i, n, j; 641 unsigned int set_size = bmap->size; 642 unsigned int total_bits = bmap->n_bits; 643 644 fprintf (file, " "); 645 for (i = n = 0; i < set_size && n < total_bits; i++) 646 for (j = 0; j < SBITMAP_ELT_BITS && n < total_bits; j++, n++) 647 { 648 if (n != 0 && n % 10 == 0) 649 fprintf (file, " "); 650 651 fprintf (file, "%d", 652 (bmap->elms[i] & ((SBITMAP_ELT_TYPE) 1 << j)) != 0); 653 } 654 655 fprintf (file, "\n"); 656} 657 658DEBUG_FUNCTION void 659debug_raw (simple_bitmap_def &ref) 660{ 661 dump_bitmap (stderr, &ref); 662} 663 664DEBUG_FUNCTION void 665debug_raw (simple_bitmap_def *ptr) 666{ 667 if (ptr) 668 debug_raw (*ptr); 669 else 670 fprintf (stderr, "<nil>\n"); 671} 672 673void 674dump_bitmap_file (FILE *file, const_sbitmap bmap) 675{ 676 unsigned int i, pos; 677 678 fprintf (file, "n_bits = %d, set = {", bmap->n_bits); 679 680 for (pos = 30, i = 0; i < bmap->n_bits; i++) 681 if (bitmap_bit_p (bmap, i)) 682 { 683 if (pos > 70) 684 { 685 fprintf (file, "\n "); 686 pos = 0; 687 } 688 689 fprintf (file, "%d ", i); 690 pos += 2 + (i >= 10) + (i >= 100) + (i >= 1000); 691 } 692 693 fprintf (file, "}\n"); 694} 695 696DEBUG_FUNCTION void 697debug_bitmap (const_sbitmap bmap) 698{ 699 dump_bitmap_file (stderr, bmap); 700} 701 702DEBUG_FUNCTION void 703debug (simple_bitmap_def &ref) 704{ 705 dump_bitmap_file (stderr, &ref); 706} 707 708DEBUG_FUNCTION void 709debug (simple_bitmap_def *ptr) 710{ 711 if (ptr) 712 debug (*ptr); 713 else 714 fprintf (stderr, "<nil>\n"); 715} 716 717void 718dump_bitmap_vector (FILE *file, const char *title, const char *subtitle, 719 sbitmap *bmaps, int n_maps) 720{ 721 int i; 722 723 fprintf (file, "%s\n", title); 724 for (i = 0; i < n_maps; i++) 725 { 726 fprintf (file, "%s %d\n", subtitle, i); 727 dump_bitmap (file, bmaps[i]); 728 } 729 730 fprintf (file, "\n"); 731} 732 733#if GCC_VERSION < 3400 734/* Table of number of set bits in a character, indexed by value of char. */ 735static const unsigned char popcount_table[] = 736{ 737 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, 738 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, 739 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, 740 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, 741 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, 742 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, 743 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, 744 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, 745}; 746 747/* Count the bits in an SBITMAP element A. */ 748 749static unsigned long 750sbitmap_elt_popcount (SBITMAP_ELT_TYPE a) 751{ 752 unsigned long ret = 0; 753 unsigned i; 754 755 if (a == 0) 756 return 0; 757 758 /* Just do this the table way for now */ 759 for (i = 0; i < SBITMAP_ELT_BITS; i += 8) 760 ret += popcount_table[(a >> i) & 0xff]; 761 return ret; 762} 763#endif 764