gcc/sbitmap.c

   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 */