gcc/bitmap.c

   1 /* Functions to support general ended bitmaps.
   2    Copyright (C) 1997, 1998, 1999, 2000, 2001, 2003
   3    Free Software Foundation, Inc.
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "rtl.h"
  27 #include "flags.h"
  28 #include "obstack.h"
  29 #include "ggc.h"
  30 #include "bitmap.h"
  31
  32 /* Obstack to allocate bitmap elements from.  */
  33 static struct obstack bitmap_obstack;
  34 static int bitmap_obstack_init = FALSE;
  35 \f
  36 #ifndef INLINE
  37 #ifndef __GNUC__
  38 #define INLINE
  39 #else
  40 #define INLINE __inline__
  41 #endif
  42 #endif
  43
  44 /* Global data */
  45 bitmap_element bitmap_zero_bits;        /* An element of all zero bits.  */
  46 static bitmap_element *bitmap_free;     /* Freelist of bitmap elements.  */
  47 static GTY((deletable (""))) bitmap_element *bitmap_ggc_free;
  48
  49 static void bitmap_elem_to_freelist     PARAMS ((bitmap, bitmap_element *));
  50 static void bitmap_element_free         PARAMS ((bitmap, bitmap_element *));
  51 static bitmap_element *bitmap_element_allocate PARAMS ((bitmap));
  52 static int bitmap_element_zerop         PARAMS ((bitmap_element *));
  53 static void bitmap_element_link         PARAMS ((bitmap, bitmap_element *));
  54 static bitmap_element *bitmap_find_bit  PARAMS ((bitmap, unsigned int));
  55 \f
  56 /* Add ELEM to the appropriate freelist.  */
  57 static INLINE void
  58 bitmap_elem_to_freelist (head, elt)
  59      bitmap head;
  60      bitmap_element *elt;
  61 {
  62   if (head->using_obstack)
  63     {
  64       elt->next = bitmap_free;
  65       bitmap_free = elt;
  66     }
  67   else
  68     {
  69       elt->next = bitmap_ggc_free;
  70       bitmap_ggc_free = elt;
  71     }
  72 }
  73
  74 /* Free a bitmap element.  Since these are allocated off the
  75    bitmap_obstack, "free" actually means "put onto the freelist".  */
  76
  77 static INLINE void
  78 bitmap_element_free (head, elt)
  79      bitmap head;
  80      bitmap_element *elt;
  81 {
  82   bitmap_element *next = elt->next;
  83   bitmap_element *prev = elt->prev;
  84
  85   if (prev)
  86     prev->next = next;
  87
  88   if (next)
  89     next->prev = prev;
  90
  91   if (head->first == elt)
  92     head->first = next;
  93
  94   /* Since the first thing we try is to insert before current,
  95      make current the next entry in preference to the previous.  */
  96   if (head->current == elt)
  97     {
  98       head->current = next != 0 ? next : prev;
  99       if (head->current)
 100         head->indx = head->current->indx;
 101     }
 102   bitmap_elem_to_freelist (head, elt);
 103 }
 104 \f
 105 /* Allocate a bitmap element.  The bits are cleared, but nothing else is.  */
 106
 107 static INLINE bitmap_element *
 108 bitmap_element_allocate (head)
 109      bitmap head;
 110 {
 111   bitmap_element *element;
 112
 113   if (head->using_obstack)
 114     {
 115       if (bitmap_free != 0)
 116         {
 117           element = bitmap_free;
 118           bitmap_free = element->next;
 119         }
 120       else
 121         {
 122           /* We can't use gcc_obstack_init to initialize the obstack since
 123              print-rtl.c now calls bitmap functions, and bitmap is linked
 124              into the gen* functions.  */
 125           if (!bitmap_obstack_init)
 126             {
 127               bitmap_obstack_init = TRUE;
 128
 129 #if !defined(__GNUC__) || (__GNUC__ < 2)
 130 #define __alignof__(type) 0
 131 #endif
 132
 133               obstack_specify_allocation (&bitmap_obstack, OBSTACK_CHUNK_SIZE,
 134                                           __alignof__ (bitmap_element),
 135                                           obstack_chunk_alloc,
 136                                           obstack_chunk_free);
 137             }
 138
 139           element = (bitmap_element *) obstack_alloc (&bitmap_obstack,
 140                                                       sizeof (bitmap_element));
 141         }
 142     }
 143   else
 144     {
 145       if (bitmap_ggc_free != NULL)
 146         {
 147           element = bitmap_ggc_free;
 148           bitmap_ggc_free = element->next;
 149         }
 150       else
 151         element = ggc_alloc (sizeof (bitmap_element));
 152     }
 153
 154   memset (element->bits, 0, sizeof (element->bits));
 155
 156   return element;
 157 }
 158
 159 /* Release any memory allocated by bitmaps.  */
 160
 161 void
 162 bitmap_release_memory ()
 163 {
 164   bitmap_free = 0;
 165   if (bitmap_obstack_init)
 166     {
 167       bitmap_obstack_init = FALSE;
 168       obstack_free (&bitmap_obstack, NULL);
 169     }
 170 }
 171
 172 /* Return nonzero if all bits in an element are zero.  */
 173
 174 static INLINE int
 175 bitmap_element_zerop (element)
 176      bitmap_element *element;
 177 {
 178 #if BITMAP_ELEMENT_WORDS == 2
 179   return (element->bits[0] | element->bits[1]) == 0;
 180 #else
 181   int i;
 182
 183   for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 184     if (element->bits[i] != 0)
 185       return 0;
 186
 187   return 1;
 188 #endif
 189 }
 190 \f
 191 /* Link the bitmap element into the current bitmap linked list.  */
 192
 193 static INLINE void
 194 bitmap_element_link (head, element)
 195      bitmap head;
 196      bitmap_element *element;
 197 {
 198   unsigned int indx = element->indx;
 199   bitmap_element *ptr;
 200
 201   /* If this is the first and only element, set it in.  */
 202   if (head->first == 0)
 203     {
 204       element->next = element->prev = 0;
 205       head->first = element;
 206     }
 207
 208   /* If this index is less than that of the current element, it goes someplace
 209      before the current element.  */
 210   else if (indx < head->indx)
 211     {
 212       for (ptr = head->current;
 213            ptr->prev != 0 && ptr->prev->indx > indx;
 214            ptr = ptr->prev)
 215         ;
 216
 217       if (ptr->prev)
 218         ptr->prev->next = element;
 219       else
 220         head->first = element;
 221
 222       element->prev = ptr->prev;
 223       element->next = ptr;
 224       ptr->prev = element;
 225     }
 226
 227   /* Otherwise, it must go someplace after the current element.  */
 228   else
 229     {
 230       for (ptr = head->current;
 231            ptr->next != 0 && ptr->next->indx < indx;
 232            ptr = ptr->next)
 233         ;
 234
 235       if (ptr->next)
 236         ptr->next->prev = element;
 237
 238       element->next = ptr->next;
 239       element->prev = ptr;
 240       ptr->next = element;
 241     }
 242
 243   /* Set up so this is the first element searched.  */
 244   head->current = element;
 245   head->indx = indx;
 246 }
 247 \f
 248 /* Clear a bitmap by freeing the linked list.  */
 249
 250 INLINE void
 251 bitmap_clear (head)
 252      bitmap head;
 253 {
 254   bitmap_element *element, *next;
 255
 256   for (element = head->first; element != 0; element = next)
 257     {
 258       next = element->next;
 259       bitmap_elem_to_freelist (head, element);
 260     }
 261
 262   head->first = head->current = 0;
 263 }
 264 \f
 265 /* Copy a bitmap to another bitmap.  */
 266
 267 void
 268 bitmap_copy (to, from)
 269      bitmap to;
 270      bitmap from;
 271 {
 272   bitmap_element *from_ptr, *to_ptr = 0;
 273 #if BITMAP_ELEMENT_WORDS != 2
 274   int i;
 275 #endif
 276
 277   bitmap_clear (to);
 278
 279   /* Copy elements in forward direction one at a time */
 280   for (from_ptr = from->first; from_ptr; from_ptr = from_ptr->next)
 281     {
 282       bitmap_element *to_elt = bitmap_element_allocate (to);
 283
 284       to_elt->indx = from_ptr->indx;
 285
 286 #if BITMAP_ELEMENT_WORDS == 2
 287       to_elt->bits[0] = from_ptr->bits[0];
 288       to_elt->bits[1] = from_ptr->bits[1];
 289 #else
 290       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 291         to_elt->bits[i] = from_ptr->bits[i];
 292 #endif
 293
 294       /* Here we have a special case of bitmap_element_link, for the case
 295          where we know the links are being entered in sequence.  */
 296       if (to_ptr == 0)
 297         {
 298           to->first = to->current = to_elt;
 299           to->indx = from_ptr->indx;
 300           to_elt->next = to_elt->prev = 0;
 301         }
 302       else
 303         {
 304           to_elt->prev = to_ptr;
 305           to_elt->next = 0;
 306           to_ptr->next = to_elt;
 307         }
 308
 309       to_ptr = to_elt;
 310     }
 311 }
 312 \f
 313 /* Find a bitmap element that would hold a bitmap's bit.
 314    Update the `current' field even if we can't find an element that
 315    would hold the bitmap's bit to make eventual allocation
 316    faster.  */
 317
 318 static INLINE bitmap_element *
 319 bitmap_find_bit (head, bit)
 320      bitmap head;
 321      unsigned int bit;
 322 {
 323   bitmap_element *element;
 324   unsigned int indx = bit / BITMAP_ELEMENT_ALL_BITS;
 325
 326   if (head->current == 0
 327       || head->indx == indx)
 328     return head->current;
 329
 330   if (head->indx > indx)
 331     for (element = head->current;
 332          element->prev != 0 && element->indx > indx;
 333          element = element->prev)
 334       ;
 335
 336   else
 337     for (element = head->current;
 338          element->next != 0 && element->indx < indx;
 339          element = element->next)
 340       ;
 341
 342   /* `element' is the nearest to the one we want.  If it's not the one we
 343      want, the one we want doesn't exist.  */
 344   head->current = element;
 345   head->indx = element->indx;
 346   if (element != 0 && element->indx != indx)
 347     element = 0;
 348
 349   return element;
 350 }
 351 \f
 352 /* Clear a single bit in a bitmap.  */
 353
 354 void
 355 bitmap_clear_bit (head, bit)
 356      bitmap head;
 357      int bit;
 358 {
 359   bitmap_element *ptr = bitmap_find_bit (head, bit);
 360
 361   if (ptr != 0)
 362     {
 363       unsigned bit_num  = bit % BITMAP_WORD_BITS;
 364       unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 365       ptr->bits[word_num] &= ~ (((BITMAP_WORD) 1) << bit_num);
 366
 367       /* If we cleared the entire word, free up the element */
 368       if (bitmap_element_zerop (ptr))
 369         bitmap_element_free (head, ptr);
 370     }
 371 }
 372
 373 /* Set a single bit in a bitmap.  */
 374
 375 void
 376 bitmap_set_bit (head, bit)
 377      bitmap head;
 378      int bit;
 379 {
 380   bitmap_element *ptr = bitmap_find_bit (head, bit);
 381   unsigned word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 382   unsigned bit_num  = bit % BITMAP_WORD_BITS;
 383   BITMAP_WORD bit_val = ((BITMAP_WORD) 1) << bit_num;
 384
 385   if (ptr == 0)
 386     {
 387       ptr = bitmap_element_allocate (head);
 388       ptr->indx = bit / BITMAP_ELEMENT_ALL_BITS;
 389       ptr->bits[word_num] = bit_val;
 390       bitmap_element_link (head, ptr);
 391     }
 392   else
 393     ptr->bits[word_num] |= bit_val;
 394 }
 395
 396 /* Return whether a bit is set within a bitmap.  */
 397
 398 int
 399 bitmap_bit_p (head, bit)
 400      bitmap head;
 401      int bit;
 402 {
 403   bitmap_element *ptr;
 404   unsigned bit_num;
 405   unsigned word_num;
 406
 407   ptr = bitmap_find_bit (head, bit);
 408   if (ptr == 0)
 409     return 0;
 410
 411   bit_num = bit % BITMAP_WORD_BITS;
 412   word_num = bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
 413
 414   return (ptr->bits[word_num] >> bit_num) & 1;
 415 }
 416 \f
 417 /* Return the bit number of the first set bit in the bitmap, or -1
 418    if the bitmap is empty.  */
 419
 420 int
 421 bitmap_first_set_bit (a)
 422      bitmap a;
 423 {
 424   bitmap_element *ptr = a->first;
 425   BITMAP_WORD word;
 426   unsigned word_num, bit_num;
 427
 428   if (ptr == NULL)
 429     return -1;
 430
 431 #if BITMAP_ELEMENT_WORDS == 2
 432   word_num = 0, word = ptr->bits[0];
 433   if (word == 0)
 434     word_num = 1, word = ptr->bits[1];
 435 #else
 436   for (word_num = 0; word_num < BITMAP_ELEMENT_WORDS; ++word_num)
 437     if ((word = ptr->bits[word_num]) != 0)
 438       break;
 439 #endif
 440
 441   /* Binary search for the first set bit.  */
 442   /* ??? It'd be nice to know if ffs or ffsl was available.  */
 443
 444   bit_num = 0;
 445   word = word & -word;
 446
 447 #if nBITMAP_WORD_BITS > 64
 448  #error "Fill out the table."
 449 #endif
 450 #if nBITMAP_WORD_BITS > 32
 451   if ((word & 0xffffffff) == 0)
 452     word >>= 32, bit_num += 32;
 453 #endif
 454   if ((word & 0xffff) == 0)
 455     word >>= 16, bit_num += 16;
 456   if ((word & 0xff) == 0)
 457     word >>= 8, bit_num += 8;
 458   if (word & 0xf0)
 459     bit_num += 4;
 460   if (word & 0xcc)
 461     bit_num += 2;
 462   if (word & 0xaa)
 463     bit_num += 1;
 464
 465   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 466           + word_num * BITMAP_WORD_BITS
 467           + bit_num);
 468 }
 469
 470 /* Return the bit number of the last set bit in the bitmap, or -1
 471    if the bitmap is empty.  */
 472
 473 int
 474 bitmap_last_set_bit (a)
 475      bitmap a;
 476 {
 477   bitmap_element *ptr = a->first;
 478   BITMAP_WORD word;
 479   unsigned word_num, bit_num;
 480
 481   if (ptr == NULL)
 482     return -1;
 483
 484   while (ptr->next != NULL)
 485     ptr = ptr->next;
 486
 487 #if BITMAP_ELEMENT_WORDS == 2
 488   word_num = 1, word = ptr->bits[1];
 489   if (word == 0)
 490     word_num = 0, word = ptr->bits[0];
 491 #else
 492   for (word_num = BITMAP_ELEMENT_WORDS; word_num-- > 0; )
 493     if ((word = ptr->bits[word_num]) != 0)
 494       break;
 495 #endif
 496
 497   /* Binary search for the last set bit.  */
 498
 499   bit_num = 0;
 500 #if nBITMAP_WORD_BITS > 64
 501  #error "Fill out the table."
 502 #endif
 503 #if nBITMAP_WORD_BITS > 32
 504   if (word & ~(BITMAP_WORD)0xffffffff)
 505     word >>= 32, bit_num += 32;
 506 #endif
 507   if (word & 0xffff0000)
 508     word >>= 16, bit_num += 16;
 509   if (word & 0xff00)
 510     word >>= 8, bit_num += 8;
 511   if (word & 0xf0)
 512     word >>= 4, bit_num += 4;
 513   if (word & 0xc)
 514     word >>= 2, bit_num += 2;
 515   if (word & 0x2)
 516     bit_num += 1;
 517
 518   return (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 519           + word_num * BITMAP_WORD_BITS
 520           + bit_num);
 521 }
 522 \f
 523 /* Store in bitmap TO the result of combining bitmap FROM1 and FROM2 using
 524    a specific bit manipulation.  Return true if TO changes.  */
 525
 526 int
 527 bitmap_operation (to, from1, from2, operation)
 528      bitmap to;
 529      bitmap from1;
 530      bitmap from2;
 531      enum bitmap_bits operation;
 532 {
 533 #define HIGHEST_INDEX (unsigned int) ~0
 534
 535   bitmap_element *from1_ptr = from1->first;
 536   bitmap_element *from2_ptr = from2->first;
 537   unsigned int indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 538   unsigned int indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 539   bitmap_element *to_ptr = to->first;
 540   bitmap_element *from1_tmp;
 541   bitmap_element *from2_tmp;
 542   bitmap_element *to_tmp;
 543   unsigned int indx;
 544   int changed = 0;
 545
 546 #if BITMAP_ELEMENT_WORDS == 2
 547 #define DOIT(OP)                                        \
 548   do {                                                  \
 549     BITMAP_WORD t0, t1, f10, f11, f20, f21;             \
 550     f10 = from1_tmp->bits[0];                           \
 551     f20 = from2_tmp->bits[0];                           \
 552     t0 = f10 OP f20;                                    \
 553     changed |= (t0 != to_tmp->bits[0]);                 \
 554     f11 = from1_tmp->bits[1];                           \
 555     f21 = from2_tmp->bits[1];                           \
 556     t1 = f11 OP f21;                                    \
 557     changed |= (t1 != to_tmp->bits[1]);                 \
 558     to_tmp->bits[0] = t0;                               \
 559     to_tmp->bits[1] = t1;                               \
 560   } while (0)
 561 #else
 562 #define DOIT(OP)                                        \
 563   do {                                                  \
 564     BITMAP_WORD t, f1, f2;                              \
 565     int i;                                              \
 566     for (i = 0; i < BITMAP_ELEMENT_WORDS; ++i)          \
 567       {                                                 \
 568         f1 = from1_tmp->bits[i];                        \
 569         f2 = from2_tmp->bits[i];                        \
 570         t = f1 OP f2;                                   \
 571         changed |= (t != to_tmp->bits[i]);              \
 572         to_tmp->bits[i] = t;                            \
 573       }                                                 \
 574   } while (0)
 575 #endif
 576
 577   to->first = to->current = 0;
 578
 579   while (from1_ptr != 0 || from2_ptr != 0)
 580     {
 581       /* Figure out whether we need to substitute zero elements for
 582          missing links.  */
 583       if (indx1 == indx2)
 584         {
 585           indx = indx1;
 586           from1_tmp = from1_ptr;
 587           from2_tmp = from2_ptr;
 588           from1_ptr = from1_ptr->next;
 589           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 590           from2_ptr = from2_ptr->next;
 591           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 592         }
 593       else if (indx1 < indx2)
 594         {
 595           indx = indx1;
 596           from1_tmp = from1_ptr;
 597           from2_tmp = &bitmap_zero_bits;
 598           from1_ptr = from1_ptr->next;
 599           indx1 = (from1_ptr) ? from1_ptr->indx : HIGHEST_INDEX;
 600         }
 601       else
 602         {
 603           indx = indx2;
 604           from1_tmp = &bitmap_zero_bits;
 605           from2_tmp = from2_ptr;
 606           from2_ptr = from2_ptr->next;
 607           indx2 = (from2_ptr) ? from2_ptr->indx : HIGHEST_INDEX;
 608         }
 609
 610       /* Find the appropriate element from TO.  Begin by discarding
 611          elements that we've skipped.  */
 612       while (to_ptr && to_ptr->indx < indx)
 613         {
 614           changed = 1;
 615           to_tmp = to_ptr;
 616           to_ptr = to_ptr->next;
 617           bitmap_elem_to_freelist (to, to_tmp);
 618         }
 619       if (to_ptr && to_ptr->indx == indx)
 620         {
 621           to_tmp = to_ptr;
 622           to_ptr = to_ptr->next;
 623         }
 624       else
 625         to_tmp = bitmap_element_allocate (to);
 626
 627       /* Do the operation, and if any bits are set, link it into the
 628          linked list.  */
 629       switch (operation)
 630         {
 631         default:
 632           abort ();
 633
 634         case BITMAP_AND:
 635           DOIT (&);
 636           break;
 637
 638         case BITMAP_AND_COMPL:
 639           DOIT (&~);
 640           break;
 641
 642         case BITMAP_IOR:
 643           DOIT (|);
 644           break;
 645         case BITMAP_IOR_COMPL:
 646           DOIT (|~);
 647           break;
 648         case BITMAP_XOR:
 649           DOIT (^);
 650           break;
 651         }
 652
 653       if (! bitmap_element_zerop (to_tmp))
 654         {
 655           to_tmp->indx = indx;
 656           bitmap_element_link (to, to_tmp);
 657         }
 658       else
 659         {
 660           bitmap_elem_to_freelist (to, to_tmp);
 661         }
 662     }
 663
 664   /* If we have elements of TO left over, free the lot.  */
 665   if (to_ptr)
 666     {
 667       changed = 1;
 668       for (to_tmp = to_ptr; to_tmp->next ; to_tmp = to_tmp->next)
 669         continue;
 670       if (to->using_obstack)
 671         {
 672           to_tmp->next = bitmap_free;
 673           bitmap_free = to_ptr;
 674         }
 675       else
 676         {
 677           to_tmp->next = bitmap_ggc_free;
 678           bitmap_ggc_free = to_ptr;
 679         }
 680     }
 681
 682 #undef DOIT
 683
 684   return changed;
 685 }
 686
 687 /* Return true if two bitmaps are identical.  */
 688
 689 int
 690 bitmap_equal_p (a, b)
 691      bitmap a;
 692      bitmap b;
 693 {
 694   bitmap_head c;
 695   int ret;
 696
 697   memset (&c, 0, sizeof (c));
 698   ret = ! bitmap_operation (&c, a, b, BITMAP_XOR);
 699   bitmap_clear (&c);
 700
 701   return ret;
 702 }
 703 \f
 704 /* Or into bitmap TO bitmap FROM1 and'ed with the complement of
 705    bitmap FROM2.  */
 706
 707 void
 708 bitmap_ior_and_compl (to, from1, from2)
 709      bitmap to;
 710      bitmap from1;
 711      bitmap from2;
 712 {
 713   bitmap_head tmp;
 714
 715   tmp.first = tmp.current = 0;
 716   tmp.using_obstack = 0;
 717
 718   bitmap_operation (&tmp, from1, from2, BITMAP_AND_COMPL);
 719   bitmap_operation (to, to, &tmp, BITMAP_IOR);
 720   bitmap_clear (&tmp);
 721 }
 722
 723 int
 724 bitmap_union_of_diff (dst, a, b, c)
 725      bitmap dst;
 726      bitmap a;
 727      bitmap b;
 728      bitmap c;
 729 {
 730   bitmap_head tmp;
 731   int changed;
 732
 733   tmp.first = tmp.current = 0;
 734   tmp.using_obstack = 0;
 735
 736   bitmap_operation (&tmp, b, c, BITMAP_AND_COMPL);
 737   changed = bitmap_operation (dst, &tmp, a, BITMAP_IOR);
 738   bitmap_clear (&tmp);
 739
 740   return changed;
 741 }
 742 \f
 743 /* Initialize a bitmap header.  */
 744
 745 bitmap
 746 bitmap_initialize (head, using_obstack)
 747      bitmap head;
 748      int using_obstack;
 749 {
 750   if (head == NULL && ! using_obstack)
 751     head = ggc_alloc (sizeof (*head));
 752
 753   head->first = head->current = 0;
 754   head->using_obstack = using_obstack;
 755
 756   return head;
 757 }
 758 \f
 759 /* Debugging function to print out the contents of a bitmap.  */
 760
 761 void
 762 debug_bitmap_file (file, head)
 763      FILE *file;
 764      bitmap head;
 765 {
 766   bitmap_element *ptr;
 767
 768   fprintf (file, "\nfirst = ");
 769   fprintf (file, HOST_PTR_PRINTF, (PTR) head->first);
 770   fprintf (file, " current = ");
 771   fprintf (file, HOST_PTR_PRINTF, (PTR) head->current);
 772   fprintf (file, " indx = %u\n", head->indx);
 773
 774   for (ptr = head->first; ptr; ptr = ptr->next)
 775     {
 776       unsigned int i, j, col = 26;
 777
 778       fprintf (file, "\t");
 779       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr);
 780       fprintf (file, " next = ");
 781       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->next);
 782       fprintf (file, " prev = ");
 783       fprintf (file, HOST_PTR_PRINTF, (PTR) ptr->prev);
 784       fprintf (file, " indx = %u\n\t\tbits = {", ptr->indx);
 785
 786       for (i = 0; i < BITMAP_ELEMENT_WORDS; i++)
 787         for (j = 0; j < BITMAP_WORD_BITS; j++)
 788           if ((ptr->bits[i] >> j) & 1)
 789             {
 790               if (col > 70)
 791                 {
 792                   fprintf (file, "\n\t\t\t");
 793                   col = 24;
 794                 }
 795
 796               fprintf (file, " %u", (ptr->indx * BITMAP_ELEMENT_ALL_BITS
 797                                      + i * BITMAP_WORD_BITS + j));
 798               col += 4;
 799             }
 800
 801       fprintf (file, " }\n");
 802     }
 803 }
 804
 805 /* Function to be called from the debugger to print the contents
 806    of a bitmap.  */
 807
 808 void
 809 debug_bitmap (head)
 810      bitmap head;
 811 {
 812   debug_bitmap_file (stdout, head);
 813 }
 814
 815 /* Function to print out the contents of a bitmap.  Unlike debug_bitmap_file,
 816    it does not print anything but the bits.  */
 817
 818 void
 819 bitmap_print (file, head, prefix, suffix)
 820      FILE *file;
 821      bitmap head;
 822      const char *prefix;
 823      const char *suffix;
 824 {
 825   const char *comma = "";
 826   int i;
 827
 828   fputs (prefix, file);
 829   EXECUTE_IF_SET_IN_BITMAP (head, 0, i,
 830                             {
 831                               fprintf (file, "%s%d", comma, i);
 832                               comma = ", ";
 833                             });
 834   fputs (suffix, file);
 835 }
 836
 837 #include "gt-bitmap.h"