gcc/sbitmap.c

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