gcc/sbitmap.c

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