150397Sobrien/* Functions to support general ended bitmaps. 2169689Skan Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 390075Sobrien Free Software Foundation, Inc. 450397Sobrien 590075SobrienThis file is part of GCC. 650397Sobrien 790075SobrienGCC is free software; you can redistribute it and/or modify it under 890075Sobrienthe terms of the GNU General Public License as published by the Free 990075SobrienSoftware Foundation; either version 2, or (at your option) any later 1090075Sobrienversion. 1150397Sobrien 1290075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1390075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1490075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1590075Sobrienfor more details. 1650397Sobrien 1750397SobrienYou should have received a copy of the GNU General Public License 1890075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 19169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 20169689Skan02110-1301, USA. */ 2150397Sobrien 2290075Sobrien#ifndef GCC_BITMAP_H 23117395Skan#define GCC_BITMAP_H 24169689Skan#include "hashtab.h" 2590075Sobrien 26117395Skan/* Fundamental storage type for bitmap. */ 27117395Skan 28117395Skantypedef unsigned long BITMAP_WORD; 29169689Skan/* BITMAP_WORD_BITS needs to be unsigned, but cannot contain casts as 30169689Skan it is used in preprocessor directives -- hence the 1u. */ 31169689Skan#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u) 32117395Skan 3350397Sobrien/* Number of words to use for each element in the linked list. */ 3450397Sobrien 3550397Sobrien#ifndef BITMAP_ELEMENT_WORDS 36169689Skan#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS) 3750397Sobrien#endif 3850397Sobrien 39169689Skan/* Number of bits in each actual element of a bitmap. */ 4050397Sobrien 41169689Skan#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS) 4250397Sobrien 43169689Skan/* Obstack for allocating bitmaps and elements from. */ 44169689Skantypedef struct bitmap_obstack GTY (()) 45169689Skan{ 46169689Skan struct bitmap_element_def *elements; 47169689Skan struct bitmap_head_def *heads; 48169689Skan struct obstack GTY ((skip)) obstack; 49169689Skan} bitmap_obstack; 50169689Skan 5150397Sobrien/* Bitmap set element. We use a linked list to hold only the bits that 5250397Sobrien are set. This allows for use to grow the bitset dynamically without 53169689Skan having to realloc and copy a giant bit array. 5450397Sobrien 55169689Skan The free list is implemented as a list of lists. There is one 56169689Skan outer list connected together by prev fields. Each element of that 57169689Skan outer is an inner list (that may consist only of the outer list 58169689Skan element) that are connected by the next fields. The prev pointer 59169689Skan is undefined for interior elements. This allows 60169689Skan bitmap_elt_clear_from to be implemented in unit time rather than 61169689Skan linear in the number of elements to be freed. */ 62169689Skan 63117395Skantypedef struct bitmap_element_def GTY(()) 6450397Sobrien{ 6590075Sobrien struct bitmap_element_def *next; /* Next element. */ 6690075Sobrien struct bitmap_element_def *prev; /* Previous element. */ 6790075Sobrien unsigned int indx; /* regno/BITMAP_ELEMENT_ALL_BITS. */ 68117395Skan BITMAP_WORD bits[BITMAP_ELEMENT_WORDS]; /* Bits that are set. */ 6950397Sobrien} bitmap_element; 7050397Sobrien 7150397Sobrien/* Head of bitmap linked list. */ 72117395Skantypedef struct bitmap_head_def GTY(()) { 7390075Sobrien bitmap_element *first; /* First element in linked list. */ 7490075Sobrien bitmap_element *current; /* Last element looked at. */ 7590075Sobrien unsigned int indx; /* Index of last element looked at. */ 76169689Skan bitmap_obstack *obstack; /* Obstack to allocate elements from. 77169689Skan If NULL, then use ggc_alloc. */ 78117395Skan} bitmap_head; 7990075Sobrien 8050397Sobrien 8150397Sobrien/* Global data */ 8290075Sobrienextern bitmap_element bitmap_zero_bits; /* Zero bitmap element */ 83169689Skanextern bitmap_obstack bitmap_default_obstack; /* Default bitmap obstack */ 8450397Sobrien 8550397Sobrien/* Clear a bitmap by freeing up the linked list. */ 86132718Skanextern void bitmap_clear (bitmap); 8750397Sobrien 8890075Sobrien/* Copy a bitmap to another bitmap. */ 89132718Skanextern void bitmap_copy (bitmap, bitmap); 9050397Sobrien 9190075Sobrien/* True if two bitmaps are identical. */ 92169689Skanextern bool bitmap_equal_p (bitmap, bitmap); 9390075Sobrien 94169689Skan/* True if the bitmaps intersect (their AND is non-empty). */ 95169689Skanextern bool bitmap_intersect_p (bitmap, bitmap); 9650397Sobrien 97169689Skan/* True if the complement of the second intersects the first (their 98169689Skan AND_COMPL is non-empty). */ 99169689Skanextern bool bitmap_intersect_compl_p (bitmap, bitmap); 10050397Sobrien 101169689Skan/* True if MAP is an empty bitmap. */ 102169689Skan#define bitmap_empty_p(MAP) (!(MAP)->first) 103169689Skan 104169689Skan/* Count the number of bits set in the bitmap. */ 105169689Skanextern unsigned long bitmap_count_bits (bitmap); 106169689Skan 107169689Skan/* Boolean operations on bitmaps. The _into variants are two operand 108169689Skan versions that modify the first source operand. The other variants 109169689Skan are three operand versions that to not destroy the source bitmaps. 110169689Skan The operations supported are &, & ~, |, ^. */ 111169689Skanextern void bitmap_and (bitmap, bitmap, bitmap); 112169689Skanextern void bitmap_and_into (bitmap, bitmap); 113169689Skanextern void bitmap_and_compl (bitmap, bitmap, bitmap); 114169689Skanextern bool bitmap_and_compl_into (bitmap, bitmap); 115169689Skan#define bitmap_compl_and(DST, A, B) bitmap_and_compl (DST, B, A) 116169689Skanextern void bitmap_compl_and_into (bitmap, bitmap); 117169689Skanextern void bitmap_clear_range (bitmap, unsigned int, unsigned int); 118169689Skanextern bool bitmap_ior (bitmap, bitmap, bitmap); 119169689Skanextern bool bitmap_ior_into (bitmap, bitmap); 120169689Skanextern void bitmap_xor (bitmap, bitmap, bitmap); 121169689Skanextern void bitmap_xor_into (bitmap, bitmap); 122169689Skan 123169689Skan/* DST = A | (B & ~C). Return true if DST changes. */ 124169689Skanextern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C); 125169689Skan/* A |= (B & ~C). Return true if A changes. */ 126169689Skanextern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C); 127169689Skan 12850397Sobrien/* Clear a single register in a register set. */ 129132718Skanextern void bitmap_clear_bit (bitmap, int); 13050397Sobrien 13150397Sobrien/* Set a single register in a register set. */ 132132718Skanextern void bitmap_set_bit (bitmap, int); 13350397Sobrien 13450397Sobrien/* Return true if a register is set in a register set. */ 135132718Skanextern int bitmap_bit_p (bitmap, int); 13650397Sobrien 13750397Sobrien/* Debug functions to print a bitmap linked list. */ 138132718Skanextern void debug_bitmap (bitmap); 139132718Skanextern void debug_bitmap_file (FILE *, bitmap); 14050397Sobrien 141132718Skan/* Print a bitmap. */ 142132718Skanextern void bitmap_print (FILE *, bitmap, const char *, const char *); 14350397Sobrien 144169689Skan/* Initialize and release a bitmap obstack. */ 145169689Skanextern void bitmap_obstack_initialize (bitmap_obstack *); 146169689Skanextern void bitmap_obstack_release (bitmap_obstack *); 14750397Sobrien 148169689Skan/* Initialize a bitmap header. OBSTACK indicates the bitmap obstack 149169689Skan to allocate from, NULL for GC'd bitmap. */ 15050397Sobrien 151169689Skanstatic inline void 152169689Skanbitmap_initialize (bitmap head, bitmap_obstack *obstack) 153169689Skan{ 154169689Skan head->first = head->current = NULL; 155169689Skan head->obstack = obstack; 156169689Skan} 157169689Skan 158169689Skan/* Allocate and free bitmaps from obstack, malloc and gc'd memory. */ 159169689Skanextern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack); 160169689Skanextern bitmap bitmap_gc_alloc (void); 161169689Skanextern void bitmap_obstack_free (bitmap); 162169689Skan 16390075Sobrien/* A few compatibility/functions macros for compatibility with sbitmaps */ 16490075Sobrien#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n") 16590075Sobrien#define bitmap_zero(a) bitmap_clear (a) 166169689Skanextern unsigned bitmap_first_set_bit (bitmap); 16750397Sobrien 168169689Skan/* Compute bitmap hash (for purposes of hashing etc.) */ 169169689Skanextern hashval_t bitmap_hash(bitmap); 17050397Sobrien 171169689Skan/* Allocate a bitmap from a bit obstack. */ 172169689Skan#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK) 173117395Skan 174169689Skan/* Allocate a gc'd bitmap. */ 175169689Skan#define BITMAP_GGC_ALLOC() bitmap_gc_alloc () 17650397Sobrien 17750397Sobrien/* Do any cleanup needed on a bitmap when it is no longer used. */ 17890075Sobrien#define BITMAP_FREE(BITMAP) \ 179169689Skan ((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL)) 18050397Sobrien 181169689Skan/* Iterator for bitmaps. */ 18290075Sobrien 183169689Skantypedef struct 184169689Skan{ 185169689Skan /* Pointer to the current bitmap element. */ 186169689Skan bitmap_element *elt1; 18750397Sobrien 188169689Skan /* Pointer to 2nd bitmap element when two are involved. */ 189169689Skan bitmap_element *elt2; 19050397Sobrien 191169689Skan /* Word within the current element. */ 192169689Skan unsigned word_no; 19350397Sobrien 194169689Skan /* Contents of the actually processed word. When finding next bit 195169689Skan it is shifted right, so that the actual bit is always the least 196169689Skan significant bit of ACTUAL. */ 197169689Skan BITMAP_WORD bits; 198169689Skan} bitmap_iterator; 19950397Sobrien 200169689Skan/* Initialize a single bitmap iterator. START_BIT is the first bit to 201169689Skan iterate from. */ 20250397Sobrien 203169689Skanstatic inline void 204169689Skanbmp_iter_set_init (bitmap_iterator *bi, bitmap map, 205169689Skan unsigned start_bit, unsigned *bit_no) 206169689Skan{ 207169689Skan bi->elt1 = map->first; 208169689Skan bi->elt2 = NULL; 20950397Sobrien 210169689Skan /* Advance elt1 until it is not before the block containing start_bit. */ 211169689Skan while (1) 212169689Skan { 213169689Skan if (!bi->elt1) 214169689Skan { 215169689Skan bi->elt1 = &bitmap_zero_bits; 216169689Skan break; 217169689Skan } 21890075Sobrien 219169689Skan if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 220169689Skan break; 221169689Skan bi->elt1 = bi->elt1->next; 222169689Skan } 223169689Skan 224169689Skan /* We might have gone past the start bit, so reinitialize it. */ 225169689Skan if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 226169689Skan start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 227169689Skan 228169689Skan /* Initialize for what is now start_bit. */ 229169689Skan bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 230169689Skan bi->bits = bi->elt1->bits[bi->word_no]; 231169689Skan bi->bits >>= start_bit % BITMAP_WORD_BITS; 232169689Skan 233169689Skan /* If this word is zero, we must make sure we're not pointing at the 234169689Skan first bit, otherwise our incrementing to the next word boundary 235169689Skan will fail. It won't matter if this increment moves us into the 236169689Skan next word. */ 237169689Skan start_bit += !bi->bits; 238169689Skan 239169689Skan *bit_no = start_bit; 240169689Skan} 241169689Skan 242169689Skan/* Initialize an iterator to iterate over the intersection of two 243169689Skan bitmaps. START_BIT is the bit to commence from. */ 244169689Skan 245169689Skanstatic inline void 246169689Skanbmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2, 247169689Skan unsigned start_bit, unsigned *bit_no) 248169689Skan{ 249169689Skan bi->elt1 = map1->first; 250169689Skan bi->elt2 = map2->first; 251169689Skan 252169689Skan /* Advance elt1 until it is not before the block containing 253169689Skan start_bit. */ 254169689Skan while (1) 255169689Skan { 256169689Skan if (!bi->elt1) 257169689Skan { 258169689Skan bi->elt2 = NULL; 259169689Skan break; 260169689Skan } 261169689Skan 262169689Skan if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 263169689Skan break; 264169689Skan bi->elt1 = bi->elt1->next; 265169689Skan } 266169689Skan 267169689Skan /* Advance elt2 until it is not before elt1. */ 268169689Skan while (1) 269169689Skan { 270169689Skan if (!bi->elt2) 271169689Skan { 272169689Skan bi->elt1 = bi->elt2 = &bitmap_zero_bits; 273169689Skan break; 274169689Skan } 275169689Skan 276169689Skan if (bi->elt2->indx >= bi->elt1->indx) 277169689Skan break; 278169689Skan bi->elt2 = bi->elt2->next; 279169689Skan } 280169689Skan 281169689Skan /* If we're at the same index, then we have some intersecting bits. */ 282169689Skan if (bi->elt1->indx == bi->elt2->indx) 283169689Skan { 284169689Skan /* We might have advanced beyond the start_bit, so reinitialize 285169689Skan for that. */ 286169689Skan if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 287169689Skan start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 288169689Skan 289169689Skan bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 290169689Skan bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 291169689Skan bi->bits >>= start_bit % BITMAP_WORD_BITS; 292169689Skan } 293169689Skan else 294169689Skan { 295169689Skan /* Otherwise we must immediately advance elt1, so initialize for 296169689Skan that. */ 297169689Skan bi->word_no = BITMAP_ELEMENT_WORDS - 1; 298169689Skan bi->bits = 0; 299169689Skan } 300169689Skan 301169689Skan /* If this word is zero, we must make sure we're not pointing at the 302169689Skan first bit, otherwise our incrementing to the next word boundary 303169689Skan will fail. It won't matter if this increment moves us into the 304169689Skan next word. */ 305169689Skan start_bit += !bi->bits; 306169689Skan 307169689Skan *bit_no = start_bit; 308169689Skan} 309169689Skan 310169689Skan/* Initialize an iterator to iterate over the bits in MAP1 & ~MAP2. 311169689Skan */ 312169689Skan 313169689Skanstatic inline void 314169689Skanbmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2, 315169689Skan unsigned start_bit, unsigned *bit_no) 316169689Skan{ 317169689Skan bi->elt1 = map1->first; 318169689Skan bi->elt2 = map2->first; 319169689Skan 320169689Skan /* Advance elt1 until it is not before the block containing start_bit. */ 321169689Skan while (1) 322169689Skan { 323169689Skan if (!bi->elt1) 324169689Skan { 325169689Skan bi->elt1 = &bitmap_zero_bits; 326169689Skan break; 327169689Skan } 328169689Skan 329169689Skan if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS) 330169689Skan break; 331169689Skan bi->elt1 = bi->elt1->next; 332169689Skan } 333169689Skan 334169689Skan /* Advance elt2 until it is not before elt1. */ 335169689Skan while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 336169689Skan bi->elt2 = bi->elt2->next; 337169689Skan 338169689Skan /* We might have advanced beyond the start_bit, so reinitialize for 339169689Skan that. */ 340169689Skan if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS) 341169689Skan start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 342169689Skan 343169689Skan bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS; 344169689Skan bi->bits = bi->elt1->bits[bi->word_no]; 345169689Skan if (bi->elt2 && bi->elt1->indx == bi->elt2->indx) 346169689Skan bi->bits &= ~bi->elt2->bits[bi->word_no]; 347169689Skan bi->bits >>= start_bit % BITMAP_WORD_BITS; 348169689Skan 349169689Skan /* If this word is zero, we must make sure we're not pointing at the 350169689Skan first bit, otherwise our incrementing to the next word boundary 351169689Skan will fail. It won't matter if this increment moves us into the 352169689Skan next word. */ 353169689Skan start_bit += !bi->bits; 354169689Skan 355169689Skan *bit_no = start_bit; 356169689Skan} 357169689Skan 358169689Skan/* Advance to the next bit in BI. We don't advance to the next 359169689Skan nonzero bit yet. */ 360169689Skan 361169689Skanstatic inline void 362169689Skanbmp_iter_next (bitmap_iterator *bi, unsigned *bit_no) 363169689Skan{ 364169689Skan bi->bits >>= 1; 365169689Skan *bit_no += 1; 366169689Skan} 367169689Skan 368169689Skan/* Advance to the next nonzero bit of a single bitmap, we will have 369169689Skan already advanced past the just iterated bit. Return true if there 370169689Skan is a bit to iterate. */ 371169689Skan 372169689Skanstatic inline bool 373169689Skanbmp_iter_set (bitmap_iterator *bi, unsigned *bit_no) 374169689Skan{ 375169689Skan /* If our current word is nonzero, it contains the bit we want. */ 376169689Skan if (bi->bits) 377169689Skan { 378169689Skan next_bit: 379169689Skan while (!(bi->bits & 1)) 380169689Skan { 381169689Skan bi->bits >>= 1; 382169689Skan *bit_no += 1; 383169689Skan } 384169689Skan return true; 385169689Skan } 386169689Skan 387169689Skan /* Round up to the word boundary. We might have just iterated past 388169689Skan the end of the last word, hence the -1. It is not possible for 389169689Skan bit_no to point at the beginning of the now last word. */ 390169689Skan *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 391169689Skan / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 392169689Skan bi->word_no++; 393169689Skan 394169689Skan while (1) 395169689Skan { 396169689Skan /* Find the next nonzero word in this elt. */ 397169689Skan while (bi->word_no != BITMAP_ELEMENT_WORDS) 398169689Skan { 399169689Skan bi->bits = bi->elt1->bits[bi->word_no]; 400169689Skan if (bi->bits) 401169689Skan goto next_bit; 402169689Skan *bit_no += BITMAP_WORD_BITS; 403169689Skan bi->word_no++; 404169689Skan } 405169689Skan 406169689Skan /* Advance to the next element. */ 407169689Skan bi->elt1 = bi->elt1->next; 408169689Skan if (!bi->elt1) 409169689Skan return false; 410169689Skan *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 411169689Skan bi->word_no = 0; 412169689Skan } 413169689Skan} 414169689Skan 415169689Skan/* Advance to the next nonzero bit of an intersecting pair of 416169689Skan bitmaps. We will have already advanced past the just iterated bit. 417169689Skan Return true if there is a bit to iterate. */ 418169689Skan 419169689Skanstatic inline bool 420169689Skanbmp_iter_and (bitmap_iterator *bi, unsigned *bit_no) 421169689Skan{ 422169689Skan /* If our current word is nonzero, it contains the bit we want. */ 423169689Skan if (bi->bits) 424169689Skan { 425169689Skan next_bit: 426169689Skan while (!(bi->bits & 1)) 427169689Skan { 428169689Skan bi->bits >>= 1; 429169689Skan *bit_no += 1; 430169689Skan } 431169689Skan return true; 432169689Skan } 433169689Skan 434169689Skan /* Round up to the word boundary. We might have just iterated past 435169689Skan the end of the last word, hence the -1. It is not possible for 436169689Skan bit_no to point at the beginning of the now last word. */ 437169689Skan *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 438169689Skan / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 439169689Skan bi->word_no++; 440169689Skan 441169689Skan while (1) 442169689Skan { 443169689Skan /* Find the next nonzero word in this elt. */ 444169689Skan while (bi->word_no != BITMAP_ELEMENT_WORDS) 445169689Skan { 446169689Skan bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no]; 447169689Skan if (bi->bits) 448169689Skan goto next_bit; 449169689Skan *bit_no += BITMAP_WORD_BITS; 450169689Skan bi->word_no++; 451169689Skan } 452169689Skan 453169689Skan /* Advance to the next identical element. */ 454169689Skan do 455169689Skan { 456169689Skan /* Advance elt1 while it is less than elt2. We always want 457169689Skan to advance one elt. */ 458169689Skan do 459169689Skan { 460169689Skan bi->elt1 = bi->elt1->next; 461169689Skan if (!bi->elt1) 462169689Skan return false; 463169689Skan } 464169689Skan while (bi->elt1->indx < bi->elt2->indx); 465169689Skan 466169689Skan /* Advance elt2 to be no less than elt1. This might not 467169689Skan advance. */ 468169689Skan while (bi->elt2->indx < bi->elt1->indx) 469169689Skan { 470169689Skan bi->elt2 = bi->elt2->next; 471169689Skan if (!bi->elt2) 472169689Skan return false; 473169689Skan } 474169689Skan } 475169689Skan while (bi->elt1->indx != bi->elt2->indx); 476169689Skan 477169689Skan *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 478169689Skan bi->word_no = 0; 479169689Skan } 480169689Skan} 481169689Skan 482169689Skan/* Advance to the next nonzero bit in the intersection of 483169689Skan complemented bitmaps. We will have already advanced past the just 484169689Skan iterated bit. */ 485169689Skan 486169689Skanstatic inline bool 487169689Skanbmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no) 488169689Skan{ 489169689Skan /* If our current word is nonzero, it contains the bit we want. */ 490169689Skan if (bi->bits) 491169689Skan { 492169689Skan next_bit: 493169689Skan while (!(bi->bits & 1)) 494169689Skan { 495169689Skan bi->bits >>= 1; 496169689Skan *bit_no += 1; 497169689Skan } 498169689Skan return true; 499169689Skan } 500169689Skan 501169689Skan /* Round up to the word boundary. We might have just iterated past 502169689Skan the end of the last word, hence the -1. It is not possible for 503169689Skan bit_no to point at the beginning of the now last word. */ 504169689Skan *bit_no = ((*bit_no + BITMAP_WORD_BITS - 1) 505169689Skan / BITMAP_WORD_BITS * BITMAP_WORD_BITS); 506169689Skan bi->word_no++; 507169689Skan 508169689Skan while (1) 509169689Skan { 510169689Skan /* Find the next nonzero word in this elt. */ 511169689Skan while (bi->word_no != BITMAP_ELEMENT_WORDS) 512169689Skan { 513169689Skan bi->bits = bi->elt1->bits[bi->word_no]; 514169689Skan if (bi->elt2 && bi->elt2->indx == bi->elt1->indx) 515169689Skan bi->bits &= ~bi->elt2->bits[bi->word_no]; 516169689Skan if (bi->bits) 517169689Skan goto next_bit; 518169689Skan *bit_no += BITMAP_WORD_BITS; 519169689Skan bi->word_no++; 520169689Skan } 521169689Skan 522169689Skan /* Advance to the next element of elt1. */ 523169689Skan bi->elt1 = bi->elt1->next; 524169689Skan if (!bi->elt1) 525169689Skan return false; 526169689Skan 527169689Skan /* Advance elt2 until it is no less than elt1. */ 528169689Skan while (bi->elt2 && bi->elt2->indx < bi->elt1->indx) 529169689Skan bi->elt2 = bi->elt2->next; 530169689Skan 531169689Skan *bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS; 532169689Skan bi->word_no = 0; 533169689Skan } 534169689Skan} 535169689Skan 536169689Skan/* Loop over all bits set in BITMAP, starting with MIN and setting 537169689Skan BITNUM to the bit number. ITER is a bitmap iterator. BITNUM 538169689Skan should be treated as a read-only variable as it contains loop 539169689Skan state. */ 540169689Skan 541169689Skan#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \ 542169689Skan for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \ 543169689Skan bmp_iter_set (&(ITER), &(BITNUM)); \ 544169689Skan bmp_iter_next (&(ITER), &(BITNUM))) 545169689Skan 546169689Skan/* Loop over all the bits set in BITMAP1 & BITMAP2, starting with MIN 547169689Skan and setting BITNUM to the bit number. ITER is a bitmap iterator. 548169689Skan BITNUM should be treated as a read-only variable as it contains 549169689Skan loop state. */ 550169689Skan 551169689Skan#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 552169689Skan for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 553169689Skan &(BITNUM)); \ 554169689Skan bmp_iter_and (&(ITER), &(BITNUM)); \ 555169689Skan bmp_iter_next (&(ITER), &(BITNUM))) 556169689Skan 557169689Skan/* Loop over all the bits set in BITMAP1 & ~BITMAP2, starting with MIN 558169689Skan and setting BITNUM to the bit number. ITER is a bitmap iterator. 559169689Skan BITNUM should be treated as a read-only variable as it contains 560169689Skan loop state. */ 561169689Skan 562169689Skan#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \ 563169689Skan for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \ 564169689Skan &(BITNUM)); \ 565169689Skan bmp_iter_and_compl (&(ITER), &(BITNUM)); \ 566169689Skan bmp_iter_next (&(ITER), &(BITNUM))) 567169689Skan 56890075Sobrien#endif /* GCC_BITMAP_H */ 569