#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
typedef unsigned long BITMAP_WORD;
#define BITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG * 1u)
#ifndef BITMAP_ELEMENT_WORDS
#define BITMAP_ELEMENT_WORDS ((128 + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
#endif
#define BITMAP_ELEMENT_ALL_BITS (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS)
typedef struct bitmap_obstack GTY (())
{
struct bitmap_element_def *elements;
struct bitmap_head_def *heads;
struct obstack GTY ((skip)) obstack;
} bitmap_obstack;
typedef struct bitmap_element_def GTY(())
{
struct bitmap_element_def *next;
struct bitmap_element_def *prev;
unsigned int indx;
BITMAP_WORD bits[BITMAP_ELEMENT_WORDS];
} bitmap_element;
typedef struct bitmap_head_def GTY(()) {
bitmap_element *first;
bitmap_element *current;
unsigned int indx;
bitmap_obstack *obstack;
} bitmap_head;
typedef struct bitmap_head_def *bitmap;
extern bitmap_element bitmap_zero_bits;
extern bitmap_obstack bitmap_default_obstack;
extern void bitmap_clear (bitmap);
extern void bitmap_copy (bitmap, bitmap);
extern bool bitmap_equal_p (bitmap, bitmap);
extern bool bitmap_intersect_p (bitmap, bitmap);
extern bool bitmap_intersect_compl_p (bitmap, bitmap);
#define bitmap_empty_p(MAP) (!(MAP)->first)
extern void bitmap_and (bitmap, bitmap, bitmap);
extern void bitmap_and_into (bitmap, bitmap);
extern void bitmap_and_compl (bitmap, bitmap, bitmap);
extern bool bitmap_and_compl_into (bitmap, bitmap);
extern bool bitmap_ior (bitmap, bitmap, bitmap);
extern bool bitmap_ior_into (bitmap, bitmap);
extern void bitmap_xor (bitmap, bitmap, bitmap);
extern void bitmap_xor_into (bitmap, bitmap);
extern bool bitmap_ior_and_compl (bitmap DST, bitmap A, bitmap B, bitmap C);
extern bool bitmap_ior_and_compl_into (bitmap DST, bitmap B, bitmap C);
extern void bitmap_clear_bit (bitmap, int);
extern void bitmap_set_bit (bitmap, int);
extern int bitmap_bit_p (bitmap, int);
extern void debug_bitmap (bitmap);
extern void debug_bitmap_file (FILE *, bitmap);
extern void bitmap_print (FILE *, bitmap, const char *, const char *);
extern void bitmap_obstack_initialize (bitmap_obstack *);
extern void bitmap_obstack_release (bitmap_obstack *);
static inline void
bitmap_initialize (bitmap head, bitmap_obstack *obstack)
{
head->first = head->current = NULL;
head->obstack = obstack;
}
extern bitmap bitmap_obstack_alloc (bitmap_obstack *obstack);
extern bitmap bitmap_gc_alloc (void);
extern void bitmap_obstack_free (bitmap);
#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
#define bitmap_zero(a) bitmap_clear (a)
extern unsigned bitmap_first_set_bit (bitmap);
#define BITMAP_ALLOC(OBSTACK) bitmap_obstack_alloc (OBSTACK)
#define BITMAP_GGC_ALLOC() bitmap_gc_alloc ()
#define BITMAP_FREE(BITMAP) \
((void)(bitmap_obstack_free (BITMAP), (BITMAP) = NULL))
typedef struct
{
bitmap_element *elt1;
bitmap_element *elt2;
unsigned word_no;
BITMAP_WORD bits;
} bitmap_iterator;
static inline void
bmp_iter_set_init (bitmap_iterator *bi, bitmap map,
unsigned start_bit, unsigned *bit_no)
{
bi->elt1 = map->first;
bi->elt2 = NULL;
while (1)
{
if (!bi->elt1)
{
bi->elt1 = &bitmap_zero_bits;
break;
}
if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
break;
bi->elt1 = bi->elt1->next;
}
if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
bi->bits = bi->elt1->bits[bi->word_no];
bi->bits >>= start_bit % BITMAP_WORD_BITS;
start_bit += !bi->bits;
*bit_no = start_bit;
}
static inline void
bmp_iter_and_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
unsigned start_bit, unsigned *bit_no)
{
bi->elt1 = map1->first;
bi->elt2 = map2->first;
while (1)
{
if (!bi->elt1)
{
bi->elt2 = NULL;
break;
}
if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
break;
bi->elt1 = bi->elt1->next;
}
while (1)
{
if (!bi->elt2)
{
bi->elt1 = bi->elt2 = &bitmap_zero_bits;
break;
}
if (bi->elt2->indx >= bi->elt1->indx)
break;
bi->elt2 = bi->elt2->next;
}
if (bi->elt1->indx == bi->elt2->indx)
{
if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
bi->bits >>= start_bit % BITMAP_WORD_BITS;
}
else
{
bi->word_no = BITMAP_ELEMENT_WORDS - 1;
bi->bits = 0;
}
start_bit += !bi->bits;
*bit_no = start_bit;
}
static inline void
bmp_iter_and_compl_init (bitmap_iterator *bi, bitmap map1, bitmap map2,
unsigned start_bit, unsigned *bit_no)
{
bi->elt1 = map1->first;
bi->elt2 = map2->first;
while (1)
{
if (!bi->elt1)
{
bi->elt1 = &bitmap_zero_bits;
break;
}
if (bi->elt1->indx >= start_bit / BITMAP_ELEMENT_ALL_BITS)
break;
bi->elt1 = bi->elt1->next;
}
while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
bi->elt2 = bi->elt2->next;
if (bi->elt1->indx != start_bit / BITMAP_ELEMENT_ALL_BITS)
start_bit = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = start_bit / BITMAP_WORD_BITS % BITMAP_ELEMENT_WORDS;
bi->bits = bi->elt1->bits[bi->word_no];
if (bi->elt2 && bi->elt1->indx == bi->elt2->indx)
bi->bits &= ~bi->elt2->bits[bi->word_no];
bi->bits >>= start_bit % BITMAP_WORD_BITS;
start_bit += !bi->bits;
*bit_no = start_bit;
}
static inline void
bmp_iter_next (bitmap_iterator *bi, unsigned *bit_no)
{
bi->bits >>= 1;
*bit_no += 1;
}
static inline bool
bmp_iter_set (bitmap_iterator *bi, unsigned *bit_no)
{
if (bi->bits)
{
next_bit:
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
return true;
}
*bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
/ BITMAP_WORD_BITS * BITMAP_WORD_BITS);
bi->word_no++;
while (1)
{
while (bi->word_no != BITMAP_ELEMENT_WORDS)
{
bi->bits = bi->elt1->bits[bi->word_no];
if (bi->bits)
goto next_bit;
*bit_no += BITMAP_WORD_BITS;
bi->word_no++;
}
bi->elt1 = bi->elt1->next;
if (!bi->elt1)
return false;
*bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = 0;
}
}
static inline bool
bmp_iter_and (bitmap_iterator *bi, unsigned *bit_no)
{
if (bi->bits)
{
next_bit:
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
return true;
}
*bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
/ BITMAP_WORD_BITS * BITMAP_WORD_BITS);
bi->word_no++;
while (1)
{
while (bi->word_no != BITMAP_ELEMENT_WORDS)
{
bi->bits = bi->elt1->bits[bi->word_no] & bi->elt2->bits[bi->word_no];
if (bi->bits)
goto next_bit;
*bit_no += BITMAP_WORD_BITS;
bi->word_no++;
}
do
{
do
{
bi->elt1 = bi->elt1->next;
if (!bi->elt1)
return false;
}
while (bi->elt1->indx < bi->elt2->indx);
while (bi->elt2->indx < bi->elt1->indx)
{
bi->elt2 = bi->elt2->next;
if (!bi->elt2)
return false;
}
}
while (bi->elt1->indx != bi->elt2->indx);
*bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = 0;
}
}
static inline bool
bmp_iter_and_compl (bitmap_iterator *bi, unsigned *bit_no)
{
if (bi->bits)
{
next_bit:
while (!(bi->bits & 1))
{
bi->bits >>= 1;
*bit_no += 1;
}
return true;
}
*bit_no = ((*bit_no + BITMAP_WORD_BITS - 1)
/ BITMAP_WORD_BITS * BITMAP_WORD_BITS);
bi->word_no++;
while (1)
{
while (bi->word_no != BITMAP_ELEMENT_WORDS)
{
bi->bits = bi->elt1->bits[bi->word_no];
if (bi->elt2 && bi->elt2->indx == bi->elt1->indx)
bi->bits &= ~bi->elt2->bits[bi->word_no];
if (bi->bits)
goto next_bit;
*bit_no += BITMAP_WORD_BITS;
bi->word_no++;
}
bi->elt1 = bi->elt1->next;
if (!bi->elt1)
return false;
while (bi->elt2 && bi->elt2->indx < bi->elt1->indx)
bi->elt2 = bi->elt2->next;
*bit_no = bi->elt1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_no = 0;
}
}
#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
for (bmp_iter_set_init (&(ITER), (BITMAP), (MIN), &(BITNUM)); \
bmp_iter_set (&(ITER), &(BITNUM)); \
bmp_iter_next (&(ITER), &(BITNUM)))
#define EXECUTE_IF_AND_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
for (bmp_iter_and_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
&(BITNUM)); \
bmp_iter_and (&(ITER), &(BITNUM)); \
bmp_iter_next (&(ITER), &(BITNUM)))
#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BITMAP1, BITMAP2, MIN, BITNUM, ITER) \
for (bmp_iter_and_compl_init (&(ITER), (BITMAP1), (BITMAP2), (MIN), \
&(BITNUM)); \
bmp_iter_and_compl (&(ITER), &(BITNUM)); \
bmp_iter_next (&(ITER), &(BITNUM)))
#define bitmap_empty_p(MAP) (!(MAP)->first)
#endif