gcc/sbitmap.c

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