#ifndef GCC_BITMAP_H
#define GCC_BITMAP_H
typedef unsigned long BITMAP_WORD;
#define nBITMAP_WORD_BITS (CHAR_BIT * SIZEOF_LONG)
#define BITMAP_WORD_BITS (unsigned) nBITMAP_WORD_BITS
#ifndef BITMAP_ELEMENT_WORDS
#define BITMAP_ELEMENT_WORDS ((128 + nBITMAP_WORD_BITS - 1) / nBITMAP_WORD_BITS)
#endif
#define BITMAP_ELEMENT_ALL_BITS \
((unsigned) (BITMAP_ELEMENT_WORDS * BITMAP_WORD_BITS))
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;
int using_obstack;
} bitmap_head;
typedef struct bitmap_head_def *bitmap;
enum bitmap_bits {
BITMAP_AND,
BITMAP_AND_COMPL,
BITMAP_IOR,
BITMAP_XOR,
BITMAP_IOR_COMPL
};
extern bitmap_element bitmap_zero_bits;
extern void bitmap_clear (bitmap);
extern void bitmap_copy (bitmap, bitmap);
extern int bitmap_equal_p (bitmap, bitmap);
extern int bitmap_operation (bitmap, bitmap, bitmap, enum bitmap_bits);
extern void bitmap_ior_and_compl (bitmap, bitmap, bitmap);
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 bitmap bitmap_initialize (bitmap head, int using_obstack);
extern void bitmap_release_memory (void);
#define dump_bitmap(file, bitmap) bitmap_print (file, bitmap, "", "\n")
#define bitmap_zero(a) bitmap_clear (a)
#define bitmap_a_or_b(a,b,c) bitmap_operation (a, b, c, BITMAP_IOR)
#define bitmap_a_and_b(a,b,c) bitmap_operation (a, b, c, BITMAP_AND)
extern int bitmap_union_of_diff (bitmap, bitmap, bitmap, bitmap);
extern int bitmap_first_set_bit (bitmap);
extern int bitmap_last_set_bit (bitmap);
#define BITMAP_OBSTACK_ALLOC(OBSTACK) \
bitmap_initialize (obstack_alloc (OBSTACK, sizeof (bitmap_head)), 1)
#define BITMAP_GGC_ALLOC() \
bitmap_initialize (NULL, 0)
#define BITMAP_XMALLOC() \
bitmap_initialize (xmalloc (sizeof (bitmap_head)), 1)
#define BITMAP_FREE(BITMAP) \
do { \
if (BITMAP) \
{ \
bitmap_clear (BITMAP); \
(BITMAP) = 0; \
} \
} while (0)
#define BITMAP_XFREE(BITMAP) \
do { \
if (BITMAP) \
{ \
bitmap_clear (BITMAP); \
free (BITMAP); \
(BITMAP) = 0; \
} \
} while (0)
#define BITMAP_INIT_ONCE()
typedef struct
{
bitmap_element *ptr1, *ptr2;
unsigned word;
unsigned word_bit;
unsigned bit;
BITMAP_WORD actual;
} bitmap_iterator;
static inline unsigned
bmp_iter_common_next_1 (bitmap_iterator *bi)
{
while (!(bi->actual & 1))
{
bi->actual >>= 1;
bi->bit++;
}
return bi->bit;
}
static inline unsigned
bmp_iter_single_next_1 (bitmap_iterator *bi)
{
if (bi->actual)
return bmp_iter_common_next_1 (bi);
bi->word++;
bi->word_bit += BITMAP_WORD_BITS;
while (1)
{
for (;
bi->word < BITMAP_ELEMENT_WORDS;
bi->word++, bi->word_bit += BITMAP_WORD_BITS)
{
bi->actual = bi->ptr1->bits[bi->word];
if (bi->actual)
{
bi->bit = bi->word_bit;
return bmp_iter_common_next_1 (bi);
}
}
bi->ptr1 = bi->ptr1->next;
if (!bi->ptr1)
return 0;
bi->word = 0;
bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
}
}
static inline unsigned
bmp_iter_single_init (bitmap_iterator *bi, bitmap bmp, unsigned min)
{
unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
for (bi->ptr1 = bmp->first;
bi->ptr1 && bi->ptr1->indx < indx;
bi->ptr1 = bi->ptr1->next)
continue;
if (!bi->ptr1)
{
bi->word = 0;
bi->bit = 0;
bi->word_bit = 0;
bi->actual = 0;
bi->ptr2 = NULL;
return 0;
}
if (bi->ptr1->indx == indx)
{
unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
bi->word = word_in_elt;
bi->word_bit = min - bit_in_word;
bi->bit = min;
bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
}
else
{
bi->word = 0;
bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_bit = bi->bit;
bi->actual = bi->ptr1->bits[0];
}
return bmp_iter_single_next_1 (bi);
}
static inline bool
bmp_iter_end_p (bitmap_iterator bi)
{
return bi.ptr1 == NULL;
}
static inline unsigned
bmp_iter_single_next (bitmap_iterator *bi)
{
bi->bit++;
bi->actual >>= 1;
return bmp_iter_single_next_1 (bi);
}
#define EXECUTE_IF_SET_IN_BITMAP(BITMAP, MIN, BITNUM, ITER) \
for ((BITNUM) = bmp_iter_single_init (&(ITER), (BITMAP), (MIN)); \
!bmp_iter_end_p (ITER); \
(BITNUM) = bmp_iter_single_next (&(ITER)))
static inline unsigned
bmp_iter_and_not_next_1 (bitmap_iterator *bi)
{
if (bi->actual)
return bmp_iter_common_next_1 (bi);
bi->word++;
bi->word_bit += BITMAP_WORD_BITS;
while (1)
{
bitmap_element *snd;
if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
snd = bi->ptr2;
else
snd = &bitmap_zero_bits;
for (;
bi->word < BITMAP_ELEMENT_WORDS;
bi->word++, bi->word_bit += BITMAP_WORD_BITS)
{
bi->actual = (bi->ptr1->bits[bi->word]
& ~snd->bits[bi->word]);
if (bi->actual)
{
bi->bit = bi->word_bit;
return bmp_iter_common_next_1 (bi);
}
}
bi->ptr1 = bi->ptr1->next;
if (!bi->ptr1)
return 0;
while (bi->ptr2
&& bi->ptr2->indx < bi->ptr1->indx)
bi->ptr2 = bi->ptr2->next;
bi->word = 0;
bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
}
}
static inline unsigned
bmp_iter_and_not_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
unsigned min)
{
unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
for (bi->ptr1 = bmp1->first;
bi->ptr1 && bi->ptr1->indx < indx;
bi->ptr1 = bi->ptr1->next)
continue;
if (!bi->ptr1)
{
bi->word = 0;
bi->bit = 0;
bi->word_bit = 0;
bi->actual = 0;
bi->ptr2 = NULL;
return 0;
}
for (bi->ptr2 = bmp2->first;
bi->ptr2 && bi->ptr2->indx < bi->ptr1->indx;
bi->ptr2 = bi->ptr2->next)
continue;
if (bi->ptr1->indx == indx)
{
unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
bi->word = word_in_elt;
bi->word_bit = min - bit_in_word;
bi->bit = min;
if (bi->ptr2 && bi->ptr2->indx == indx)
bi->actual = (bi->ptr1->bits[word_in_elt]
& ~bi->ptr2->bits[word_in_elt]) >> bit_in_word;
else
bi->actual = bi->ptr1->bits[word_in_elt] >> bit_in_word;
}
else
{
bi->word = 0;
bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_bit = bi->bit;
if (bi->ptr2 && bi->ptr2->indx == bi->ptr1->indx)
bi->actual = (bi->ptr1->bits[0] & ~bi->ptr2->bits[0]);
else
bi->actual = bi->ptr1->bits[0];
}
return bmp_iter_and_not_next_1 (bi);
}
static inline unsigned
bmp_iter_and_not_next (bitmap_iterator *bi)
{
bi->bit++;
bi->actual >>= 1;
return bmp_iter_and_not_next_1 (bi);
}
#define EXECUTE_IF_AND_COMPL_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER) \
for ((BITNUM) = bmp_iter_and_not_init (&(ITER), (BMP1), (BMP2), (MIN)); \
!bmp_iter_end_p (ITER); \
(BITNUM) = bmp_iter_and_not_next (&(ITER)))
static inline unsigned
bmp_iter_and_next_1 (bitmap_iterator *bi)
{
if (bi->actual)
return bmp_iter_common_next_1 (bi);
bi->word++;
bi->word_bit += BITMAP_WORD_BITS;
while (1)
{
for (;
bi->word < BITMAP_ELEMENT_WORDS;
bi->word++, bi->word_bit += BITMAP_WORD_BITS)
{
bi->actual = (bi->ptr1->bits[bi->word]
& bi->ptr2->bits[bi->word]);
if (bi->actual)
{
bi->bit = bi->word_bit;
return bmp_iter_common_next_1 (bi);
}
}
do
{
bi->ptr1 = bi->ptr1->next;
if (!bi->ptr1)
return 0;
while (bi->ptr2->indx < bi->ptr1->indx)
{
bi->ptr2 = bi->ptr2->next;
if (!bi->ptr2)
{
bi->ptr1 = NULL;
return 0;
}
}
}
while (bi->ptr1->indx != bi->ptr2->indx);
bi->word = 0;
bi->word_bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
}
}
static inline unsigned
bmp_iter_and_init (bitmap_iterator *bi, bitmap bmp1, bitmap bmp2,
unsigned min)
{
unsigned indx = min / BITMAP_ELEMENT_ALL_BITS;
for (bi->ptr1 = bmp1->first;
bi->ptr1 && bi->ptr1->indx < indx;
bi->ptr1 = bi->ptr1->next)
continue;
if (!bi->ptr1)
goto empty;
bi->ptr2 = bmp2->first;
if (!bi->ptr2)
goto empty;
while (1)
{
while (bi->ptr2->indx < bi->ptr1->indx)
{
bi->ptr2 = bi->ptr2->next;
if (!bi->ptr2)
goto empty;
}
if (bi->ptr1->indx == bi->ptr2->indx)
break;
bi->ptr1 = bi->ptr1->next;
if (!bi->ptr1)
goto empty;
}
if (bi->ptr1->indx == indx)
{
unsigned bit_in_elt = min - BITMAP_ELEMENT_ALL_BITS * indx;
unsigned word_in_elt = bit_in_elt / BITMAP_WORD_BITS;
unsigned bit_in_word = bit_in_elt % BITMAP_WORD_BITS;
bi->word = word_in_elt;
bi->word_bit = min - bit_in_word;
bi->bit = min;
bi->actual = (bi->ptr1->bits[word_in_elt]
& bi->ptr2->bits[word_in_elt]) >> bit_in_word;
}
else
{
bi->word = 0;
bi->bit = bi->ptr1->indx * BITMAP_ELEMENT_ALL_BITS;
bi->word_bit = bi->bit;
bi->actual = (bi->ptr1->bits[0] & bi->ptr2->bits[0]);
}
return bmp_iter_and_next_1 (bi);
empty:
bi->word = 0;
bi->bit = 0;
bi->word_bit = 0;
bi->actual = 0;
bi->ptr1 = NULL;
bi->ptr2 = NULL;
return 0;
}
static inline unsigned
bmp_iter_and_next (bitmap_iterator *bi)
{
bi->bit++;
bi->actual >>= 1;
return bmp_iter_and_next_1 (bi);
}
#define EXECUTE_IF_AND_IN_BITMAP(BMP1, BMP2, MIN, BITNUM, ITER) \
for ((BITNUM) = bmp_iter_and_init (&(ITER), (BMP1), (BMP2), (MIN)); \
!bmp_iter_end_p (ITER); \
(BITNUM) = bmp_iter_and_next (&(ITER)))
#endif