[thirdparty/gcc.git] / gcc / sbitmap.h

/* Simple bitmaps.
   Copyright (C) 1999-2012  Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY
WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
for more details.

You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING3.  If not see
<http://www.gnu.org/licenses/>.  */

#ifndef GCC_SBITMAP_H
#define GCC_SBITMAP_H

/* Implementation of sets using simple bitmap vectors.

   This set representation is suitable for non-sparse sets with a known
   (a priori) universe.  The set is represented as a simple array of the
   host's fastest unsigned integer.  For a given member I in the set:
     - the element for I will be at sbitmap[I / (bits per element)]
     - the position for I within element is I % (bits per element)

   This representation is very space-efficient for large non-sparse sets
   with random access patterns.

   The following operations can be performed in O(1) time:

     * set_size			: SBITMAP_SIZE
     * member_p			: bitmap_bit_p
     * add_member		: bitmap_set_bit
     * remove_member		: bitmap_clear_bit

   Most other operations on this set representation are O(U) where U is
   the size of the set universe:

     * clear			: bitmap_clear
     * cardinality		: sbitmap_popcount
     * choose_one		: bitmap_first_set_bit /
				  bitmap_last_set_bit
     * forall			: EXECUTE_IF_SET_IN_SBITMAP
     * set_copy			: bitmap_copy / bitmap_copy_n
     * set_intersection		: bitmap_and
     * set_union		: bitmap_ior
     * set_difference		: bitmap_and_compl
     * set_disjuction		: (not implemented)
     * set_compare		: bitmap_equal_p

   Some operations on 3 sets that occur frequently in in data flow problems
   are also implemented:

      * A | (B & C)		: bitmap_or_and
      * A | (B & ~C)		: bitmap_ior_and_compl
      * A & (B | C)		: bitmap_and_or

   Most of the set functions have two variants: One that returns non-zero
   if members were added or removed from the target set, and one that just
   performs the operation without feedback.  The former operations are a
   bit more expensive but the result can often be used to avoid iterations
   on other sets.

   Allocating a bitmap is done with sbitmap_alloc, and resizing is
   performed with sbitmap_resize.

   The storage requirements for simple bitmap sets is O(U) where U is the
   size of the set universe (colloquially the number of bits in the bitmap).

   This set representation works well for relatively small data flow problems
   (there are special routines for that, see sbitmap_vector_*).  The set
   operations can be vectorized and there is almost no computating overhead,
   so that even sparse simple bitmap sets outperform dedicated sparse set
   representations like linked-list bitmaps.  For larger problems, the size
   overhead of simple bitmap sets gets too high and other set representations
   have to be used.  */

#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT

struct simple_bitmap_def
{
  unsigned char *popcount;      /* Population count.  */
  unsigned int n_bits;		/* Number of bits.  */
  unsigned int size;		/* Size in elements.  */
  SBITMAP_ELT_TYPE elms[1];	/* The elements.  */
};

/* Return the set size needed for N elements.  */
#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))

/* Return the number of bits in BITMAP.  */
#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)

/* Test if bit number bitno in the bitmap is set.  */
static inline SBITMAP_ELT_TYPE
bitmap_bit_p (const_sbitmap map, int bitno)
{
  size_t i = bitno / SBITMAP_ELT_BITS;
  unsigned int s = bitno % SBITMAP_ELT_BITS;
  return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
}

/* Set bit number BITNO in the sbitmap MAP.  */

static inline void
bitmap_set_bit (sbitmap map, int bitno)
{
  gcc_checking_assert (! map->popcount);
  map->elms[bitno / SBITMAP_ELT_BITS]
    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
}

/* Like bitmap_set_bit, but updates population count.  */

static inline void
bitmap_set_bit_with_popcount (sbitmap map, int bitno)
{
  bool oldbit;
  gcc_checking_assert (map->popcount);
  oldbit = bitmap_bit_p (map, bitno);
  if (!oldbit)
    map->popcount[bitno / SBITMAP_ELT_BITS]++;
  map->elms[bitno / SBITMAP_ELT_BITS]
    |= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
}

/* Reset bit number BITNO in the sbitmap MAP.  */

static inline void
bitmap_clear_bit (sbitmap map, int bitno)
{
  gcc_checking_assert (! map->popcount);
  map->elms[bitno / SBITMAP_ELT_BITS]
    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
}

/* Like bitmap_clear_bit, but updates population count.  */

static inline void
bitmap_clear_bit_with_popcount (sbitmap map, int bitno)
{
  bool oldbit;
  gcc_checking_assert (map->popcount);
  oldbit = bitmap_bit_p (map, bitno);
  if (oldbit)
    map->popcount[bitno / SBITMAP_ELT_BITS]--;
  map->elms[bitno / SBITMAP_ELT_BITS]
    &= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
}

/* The iterator for sbitmap.  */
typedef struct {
  /* The pointer to the first word of the bitmap.  */
  const SBITMAP_ELT_TYPE *ptr;

  /* The size of the bitmap.  */
  unsigned int size;

  /* The current word index.  */
  unsigned int word_num;

  /* The current bit index (not modulo SBITMAP_ELT_BITS).  */
  unsigned int bit_num;

  /* The words currently visited.  */
  SBITMAP_ELT_TYPE word;
} sbitmap_iterator;

/* Initialize the iterator I with sbitmap BMP and the initial index
   MIN.  */

static inline void
sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
{
  i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
  i->bit_num = min;
  i->size = bmp->size;
  i->ptr = bmp->elms;

  if (i->word_num >= i->size)
    i->word = 0;
  else
    i->word = (i->ptr[i->word_num]
	       >> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
}

/* Return true if we have more bits to visit, in which case *N is set
   to the index of the bit to be visited.  Otherwise, return
   false.  */

static inline bool
sbitmap_iter_cond (sbitmap_iterator *i, unsigned int *n)
{
  /* Skip words that are zeros.  */
  for (; i->word == 0; i->word = i->ptr[i->word_num])
    {
      i->word_num++;

      /* If we have reached the end, break.  */
      if (i->word_num >= i->size)
	return false;

      i->bit_num = i->word_num * SBITMAP_ELT_BITS;
    }

  /* Skip bits that are zero.  */
  for (; (i->word & 1) == 0; i->word >>= 1)
    i->bit_num++;

  *n = i->bit_num;

  return true;
}

/* Advance to the next bit.  */

static inline void
sbitmap_iter_next (sbitmap_iterator *i)
{
  i->word >>= 1;
  i->bit_num++;
}

/* Loop over all elements of SBITMAP, starting with MIN.  In each
   iteration, N is set to the index of the bit being visited.  ITER is
   an instance of sbitmap_iterator used to iterate the bitmap.  */

#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER)	\
  for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN));		\
       sbitmap_iter_cond (&(ITER), &(N));			\
       sbitmap_iter_next (&(ITER)))

#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE)			\
do {									\
  unsigned int word_num_;						\
  unsigned int bit_num_;						\
  unsigned int size_ = (SBITMAP)->size;					\
  SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms;				\
									\
  for (word_num_ = size_; word_num_ > 0; word_num_--)			\
    {									\
      SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1];			\
									\
      if (word_ != 0)							\
	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--)	\
	  {								\
	    SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
									\
	    if ((word_ & _mask) != 0)					\
	      {								\
		word_ &= ~ _mask;					\
		(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
		CODE;							\
		if (word_ == 0)						\
		  break;						\
	      }								\
	  }								\
    }									\
} while (0)

inline void sbitmap_free (sbitmap map)
{
  free (map->popcount);
  free (map);
}

inline void sbitmap_vector_free (sbitmap * vec)
{
  free (vec);
}

extern void dump_bitmap (FILE *, const_sbitmap);
extern void dump_bitmap_file (FILE *, const_sbitmap);
extern void dump_bitmap_vector (FILE *, const char *, const char *, sbitmap *,
				 int);
extern sbitmap sbitmap_alloc (unsigned int);
extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
extern void bitmap_copy (sbitmap, const_sbitmap);
extern void bitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
extern bool bitmap_empty_p (const_sbitmap);
extern bool bitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
extern void bitmap_clear (sbitmap);
extern void bitmap_ones (sbitmap);
extern void bitmap_vector_clear (sbitmap *, unsigned int);
extern void bitmap_vector_ones (sbitmap *, unsigned int);

extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
				      const_sbitmap, const_sbitmap);
extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
extern void bitmap_not (sbitmap, const_sbitmap);
extern bool bitmap_or_and (sbitmap, const_sbitmap,
				     const_sbitmap, const_sbitmap);
extern bool bitmap_and_or (sbitmap, const_sbitmap,
				     const_sbitmap, const_sbitmap);
extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);

extern int bitmap_first_set_bit (const_sbitmap);
extern int bitmap_last_set_bit (const_sbitmap);

extern void debug_bitmap (const_sbitmap);
extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
extern void sbitmap_verify_popcount (const_sbitmap);
#endif /* ! GCC_SBITMAP_H */
Commit	Line	Data
5f6c11d6	1	/* Simple bitmaps.
0263463d	2	Copyright (C) 1999-2012 Free Software Foundation, Inc.
5f6c11d6	3
1322177d	4	This file is part of GCC.
5f6c11d6	5
1322177d LB	6	GCC is free software; you can redistribute it and/or modify it under
1322177d LB	7	the terms of the GNU General Public License as published by the Free
9dcd6f09	8	Software Foundation; either version 3, or (at your option) any later
1322177d	9	version.
5f6c11d6	10
1322177d LB	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.
5f6c11d6 RH	15
5f6c11d6 RH	16	You should have received a copy of the GNU General Public License
9dcd6f09 NC	17	along with GCC; see the file COPYING3. If not see
9dcd6f09 NC	18	<http://www.gnu.org/licenses/>. */
5f6c11d6	19
88657302	20	#ifndef GCC_SBITMAP_H
46c5ad27	21	#define GCC_SBITMAP_H
4dc9341c	22
0263463d SB	23	/* Implementation of sets using simple bitmap vectors.
	24
	25	This set representation is suitable for non-sparse sets with a known
	26	(a priori) universe. The set is represented as a simple array of the
	27	host's fastest unsigned integer. For a given member I in the set:
	28	- the element for I will be at sbitmap[I / (bits per element)]
	29	- the position for I within element is I % (bits per element)
	30
	31	This representation is very space-efficient for large non-sparse sets
	32	with random access patterns.
	33
	34	The following operations can be performed in O(1) time:
	35
	36	* set_size : SBITMAP_SIZE
d7c028c0 LC	37	* member_p : bitmap_bit_p
	38	* add_member : bitmap_set_bit
	39	* remove_member : bitmap_clear_bit
0263463d SB	40
	41	Most other operations on this set representation are O(U) where U is
	42	the size of the set universe:
	43
f61e445a	44	* clear : bitmap_clear
0263463d	45	* cardinality : sbitmap_popcount
f61e445a LC	46	* choose_one : bitmap_first_set_bit /
f61e445a LC	47	bitmap_last_set_bit
0263463d	48	* forall : EXECUTE_IF_SET_IN_SBITMAP
f61e445a LC	49	* set_copy : bitmap_copy / bitmap_copy_n
	50	* set_intersection : bitmap_and
	51	* set_union : bitmap_ior
	52	* set_difference : bitmap_and_compl
0263463d	53	* set_disjuction : (not implemented)
f61e445a	54	* set_compare : bitmap_equal_p
0263463d SB	55
	56	Some operations on 3 sets that occur frequently in in data flow problems
	57	are also implemented:
	58
f61e445a LC	59	* A \| (B & C) : bitmap_or_and
	60	* A \| (B & ~C) : bitmap_ior_and_compl
	61	* A & (B \| C) : bitmap_and_or
0263463d SB	62
	63	Most of the set functions have two variants: One that returns non-zero
	64	if members were added or removed from the target set, and one that just
	65	performs the operation without feedback. The former operations are a
	66	bit more expensive but the result can often be used to avoid iterations
	67	on other sets.
	68
	69	Allocating a bitmap is done with sbitmap_alloc, and resizing is
	70	performed with sbitmap_resize.
	71
	72	The storage requirements for simple bitmap sets is O(U) where U is the
	73	size of the set universe (colloquially the number of bits in the bitmap).
	74
	75	This set representation works well for relatively small data flow problems
	76	(there are special routines for that, see sbitmap_vector_*). The set
	77	operations can be vectorized and there is almost no computating overhead,
	78	so that even sparse simple bitmap sets outperform dedicated sparse set
	79	representations like linked-list bitmaps. For larger problems, the size
	80	overhead of simple bitmap sets gets too high and other set representations
	81	have to be used. */
5f6c11d6	82
7aa6d18a	83	#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
99fa8911	84	#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
5f6c11d6	85
7a8cba34	86	struct simple_bitmap_def
08158df3	87	{
97508a6b	88	unsigned char popcount; / Population count. */
08158df3 RK	89	unsigned int n_bits; /* Number of bits. */
08158df3 RK	90	unsigned int size; /* Size in elements. */
08158df3	91	SBITMAP_ELT_TYPE elms[1]; /* The elements. */
7a8cba34	92	};
5f6c11d6	93
5f6c11d6	94	/* Return the set size needed for N elements. */
08158df3	95	#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
97508a6b	96	#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
5f6c11d6	97
0263463d SB	98	/* Return the number of bits in BITMAP. */
	99	#define SBITMAP_SIZE(BITMAP) ((BITMAP)->n_bits)
	100
08158df3	101	/* Test if bit number bitno in the bitmap is set. */
0263463d	102	static inline SBITMAP_ELT_TYPE
d7c028c0	103	bitmap_bit_p (const_sbitmap map, int bitno)
0263463d SB	104	{
	105	size_t i = bitno / SBITMAP_ELT_BITS;
	106	unsigned int s = bitno % SBITMAP_ELT_BITS;
	107	return (map->elms[i] >> s) & (SBITMAP_ELT_TYPE) 1;
	108	}
5f6c11d6	109
0263463d	110	/* Set bit number BITNO in the sbitmap MAP. */
97508a6b DB	111
97508a6b DB	112	static inline void
d7c028c0	113	bitmap_set_bit (sbitmap map, int bitno)
97508a6b	114	{
0263463d	115	gcc_checking_assert (! map->popcount);
97508a6b DB	116	map->elms[bitno / SBITMAP_ELT_BITS]
	117	\|= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
	118	}
	119
d7c028c0	120	/* Like bitmap_set_bit, but updates population count. */
97508a6b	121
0263463d	122	static inline void
d7c028c0	123	bitmap_set_bit_with_popcount (sbitmap map, int bitno)
0263463d SB	124	{
	125	bool oldbit;
	126	gcc_checking_assert (map->popcount);
d7c028c0	127	oldbit = bitmap_bit_p (map, bitno);
0263463d SB	128	if (!oldbit)
	129	map->popcount[bitno / SBITMAP_ELT_BITS]++;
	130	map->elms[bitno / SBITMAP_ELT_BITS]
	131	\|= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
	132	}
97508a6b	133
0263463d	134	/* Reset bit number BITNO in the sbitmap MAP. */
97508a6b DB	135
97508a6b DB	136	static inline void
d7c028c0	137	bitmap_clear_bit (sbitmap map, int bitno)
97508a6b	138	{
0263463d SB	139	gcc_checking_assert (! map->popcount);
	140	map->elms[bitno / SBITMAP_ELT_BITS]
	141	&= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
	142	}
	143
d7c028c0	144	/* Like bitmap_clear_bit, but updates population count. */
0263463d SB	145
0263463d SB	146	static inline void
d7c028c0	147	bitmap_clear_bit_with_popcount (sbitmap map, int bitno)
0263463d SB	148	{
	149	bool oldbit;
	150	gcc_checking_assert (map->popcount);
d7c028c0	151	oldbit = bitmap_bit_p (map, bitno);
0263463d SB	152	if (oldbit)
0263463d SB	153	map->popcount[bitno / SBITMAP_ELT_BITS]--;
97508a6b DB	154	map->elms[bitno / SBITMAP_ELT_BITS]
	155	&= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
	156	}
5f6c11d6	157
b6e7e9af KH	158	/* The iterator for sbitmap. */
	159	typedef struct {
	160	/* The pointer to the first word of the bitmap. */
be5b01f3	161	const SBITMAP_ELT_TYPE *ptr;
b6e7e9af KH	162
	163	/* The size of the bitmap. */
	164	unsigned int size;
	165
	166	/* The current word index. */
	167	unsigned int word_num;
	168
108267cd	169	/* The current bit index (not modulo SBITMAP_ELT_BITS). */
b6e7e9af KH	170	unsigned int bit_num;
	171
	172	/* The words currently visited. */
	173	SBITMAP_ELT_TYPE word;
	174	} sbitmap_iterator;
	175
	176	/* Initialize the iterator I with sbitmap BMP and the initial index
	177	MIN. */
	178
	179	static inline void
be5b01f3	180	sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
b6e7e9af KH	181	{
b6e7e9af KH	182	i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
108267cd	183	i->bit_num = min;
b6e7e9af KH	184	i->size = bmp->size;
	185	i->ptr = bmp->elms;
	186
	187	if (i->word_num >= i->size)
	188	i->word = 0;
	189	else
108267cd KH	190	i->word = (i->ptr[i->word_num]
108267cd KH	191	>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
b6e7e9af KH	192	}
	193
	194	/* Return true if we have more bits to visit, in which case *N is set
	195	to the index of the bit to be visited. Otherwise, return
	196	false. */
	197
	198	static inline bool
	199	sbitmap_iter_cond (sbitmap_iterator i, unsigned int n)
	200	{
	201	/* Skip words that are zeros. */
	202	for (; i->word == 0; i->word = i->ptr[i->word_num])
	203	{
	204	i->word_num++;
	205
	206	/* If we have reached the end, break. */
	207	if (i->word_num >= i->size)
	208	return false;
	209
	210	i->bit_num = i->word_num * SBITMAP_ELT_BITS;
	211	}
	212
	213	/* Skip bits that are zero. */
	214	for (; (i->word & 1) == 0; i->word >>= 1)
	215	i->bit_num++;
	216
	217	*n = i->bit_num;
	218
	219	return true;
	220	}
	221
	222	/* Advance to the next bit. */
	223
	224	static inline void
	225	sbitmap_iter_next (sbitmap_iterator *i)
	226	{
	227	i->word >>= 1;
	228	i->bit_num++;
	229	}
	230
	231	/* Loop over all elements of SBITMAP, starting with MIN. In each
	232	iteration, N is set to the index of the bit being visited. ITER is
	233	an instance of sbitmap_iterator used to iterate the bitmap. */
	234
	235	#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
	236	for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
	237	sbitmap_iter_cond (&(ITER), &(N)); \
	238	sbitmap_iter_next (&(ITER)))
5f6c11d6	239
ed8d2920 MM	240	#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
	241	do { \
	242	unsigned int word_num_; \
	243	unsigned int bit_num_; \
	244	unsigned int size_ = (SBITMAP)->size; \
	245	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
	246	\
	247	for (word_num_ = size_; word_num_ > 0; word_num_--) \
	248	{ \
	249	SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
	250	\
	251	if (word_ != 0) \
	252	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
	253	{ \
	254	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
	255	\
	256	if ((word_ & _mask) != 0) \
	257	{ \
	258	word_ &= ~ _mask; \
	259	(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
	260	CODE; \
	261	if (word_ == 0) \
	262	break; \
	263	} \
	264	} \
	265	} \
	266	} while (0)
	267
f61e445a LC	268	inline void sbitmap_free (sbitmap map)
	269	{
	270	free (map->popcount);
	271	free (map);
	272	}
5f6c11d6	273
f61e445a LC	274	inline void sbitmap_vector_free (sbitmap * vec)
	275	{
	276	free (vec);
	277	}
	278
	279	extern void dump_bitmap (FILE *, const_sbitmap);
	280	extern void dump_bitmap_file (FILE *, const_sbitmap);
	281	extern void dump_bitmap_vector (FILE , const char , const char , sbitmap ,
46c5ad27 AJ	282	int);
46c5ad27 AJ	283	extern sbitmap sbitmap_alloc (unsigned int);
97508a6b	284	extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
46c5ad27 AJ	285	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
46c5ad27 AJ	286	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
f61e445a LC	287	extern void bitmap_copy (sbitmap, const_sbitmap);
	288	extern void bitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
	289	extern int bitmap_equal_p (const_sbitmap, const_sbitmap);
	290	extern bool bitmap_empty_p (const_sbitmap);
	291	extern bool bitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
	292	extern void bitmap_clear (sbitmap);
	293	extern void bitmap_ones (sbitmap);
	294	extern void bitmap_vector_clear (sbitmap *, unsigned int);
	295	extern void bitmap_vector_ones (sbitmap *, unsigned int);
	296
	297	extern bool bitmap_ior_and_compl (sbitmap, const_sbitmap,
0263463d	298	const_sbitmap, const_sbitmap);
f61e445a LC	299	extern void bitmap_and_compl (sbitmap, const_sbitmap, const_sbitmap);
	300	extern void bitmap_not (sbitmap, const_sbitmap);
	301	extern bool bitmap_or_and (sbitmap, const_sbitmap,
0263463d	302	const_sbitmap, const_sbitmap);
f61e445a	303	extern bool bitmap_and_or (sbitmap, const_sbitmap,
0263463d	304	const_sbitmap, const_sbitmap);
f61e445a LC	305	extern bool bitmap_intersect_p (const_sbitmap, const_sbitmap);
	306	extern bool bitmap_and (sbitmap, const_sbitmap, const_sbitmap);
	307	extern bool bitmap_ior (sbitmap, const_sbitmap, const_sbitmap);
	308	extern bool bitmap_xor (sbitmap, const_sbitmap, const_sbitmap);
	309	extern bool bitmap_subset_p (const_sbitmap, const_sbitmap);
	310
	311	extern int bitmap_first_set_bit (const_sbitmap);
	312	extern int bitmap_last_set_bit (const_sbitmap);
	313
	314	extern void debug_bitmap (const_sbitmap);
6de9cd9a	315	extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
3c2c4f22	316	extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
be5b01f3	317	extern void sbitmap_verify_popcount (const_sbitmap);
88657302	318	#endif /* ! GCC_SBITMAP_H */