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

/* Simple bitmaps.
   Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008, 2010
   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

/* It's not clear yet whether using bitmap.[ch] will be a win.
   It should be straightforward to convert so for now we keep things simple
   while more important issues are dealt with.  */

#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT

/* Can't use SBITMAP_ELT_BITS in this macro because it contains a
   cast.  There is no perfect macro in GCC to test against.  This
   suffices for roughly 99% of the hosts we run on, and the rest
   don't have 256 bit integers.  */
#if HOST_BITS_PER_WIDEST_FAST_INT > 255
#error Need to increase size of datatype used for popcount
#endif

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))

/* Test if bit number bitno in the bitmap is set.  */
#define TEST_BIT(BITMAP, BITNO) \
((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)

/* Set bit number BITNO in the sbitmap MAP.  Updates population count
   if this bitmap has one.  */

static inline void
SET_BIT (sbitmap map, unsigned int bitno)
{
  if (map->popcount)
    {
      bool oldbit;
      oldbit = TEST_BIT (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.  Updates population
   count if this bitmap has one.  */

static inline void
RESET_BIT (sbitmap map,  unsigned int bitno)
{
  if (map->popcount)
    {
      bool oldbit;
      oldbit = TEST_BIT (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)

#define sbitmap_free(MAP)		(free((MAP)->popcount), free((MAP)))
#define sbitmap_vector_free(VEC)	free(VEC)

extern void dump_sbitmap (FILE *, const_sbitmap);
extern void dump_sbitmap_file (FILE *, const_sbitmap);
extern void dump_sbitmap_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 sbitmap_copy (sbitmap, const_sbitmap);
extern void sbitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
extern int sbitmap_equal (const_sbitmap, const_sbitmap);
extern bool sbitmap_empty_p (const_sbitmap);
extern bool sbitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
extern void sbitmap_zero (sbitmap);
extern void sbitmap_ones (sbitmap);
extern void sbitmap_vector_zero (sbitmap *, unsigned int);
extern void sbitmap_vector_ones (sbitmap *, unsigned int);

extern void sbitmap_union_of_diff (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern void sbitmap_difference (sbitmap, const_sbitmap, const_sbitmap);
extern void sbitmap_not (sbitmap, const_sbitmap);
extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_any_common_bits (const_sbitmap, const_sbitmap);
extern void sbitmap_a_and_b (sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_and_b_cg (sbitmap, const_sbitmap, const_sbitmap);
extern void sbitmap_a_or_b (sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_or_b_cg (sbitmap, const_sbitmap, const_sbitmap);
extern void sbitmap_a_xor_b (sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_xor_b_cg (sbitmap, const_sbitmap, const_sbitmap);
extern bool sbitmap_a_subset_b_p (const_sbitmap, const_sbitmap);

extern int sbitmap_first_set_bit (const_sbitmap);
extern int sbitmap_last_set_bit (const_sbitmap);

extern void debug_sbitmap (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.
d652f226	2	Copyright (C) 1999, 2000, 2002, 2003, 2004, 2006, 2007, 2008, 2010
6fb5fa3c	3	Free Software Foundation, Inc.
5f6c11d6	4
1322177d	5	This file is part of GCC.
5f6c11d6	6
1322177d LB	7	GCC is free software; you can redistribute it and/or modify it under
1322177d LB	8	the terms of the GNU General Public License as published by the Free
9dcd6f09	9	Software Foundation; either version 3, or (at your option) any later
1322177d	10	version.
5f6c11d6	11
1322177d LB	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.
5f6c11d6 RH	16
5f6c11d6 RH	17	You should have received a copy of the GNU General Public License
9dcd6f09 NC	18	along with GCC; see the file COPYING3. If not see
9dcd6f09 NC	19	<http://www.gnu.org/licenses/>. */
5f6c11d6	20
88657302	21	#ifndef GCC_SBITMAP_H
46c5ad27	22	#define GCC_SBITMAP_H
4dc9341c	23
5f6c11d6 RH	24	/* It's not clear yet whether using bitmap.[ch] will be a win.
	25	It should be straightforward to convert so for now we keep things simple
	26	while more important issues are dealt with. */
	27
99fa8911 AP	28	#define SBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
99fa8911 AP	29	#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
5f6c11d6	30
97508a6b DB	31	/* Can't use SBITMAP_ELT_BITS in this macro because it contains a
	32	cast. There is no perfect macro in GCC to test against. This
	33	suffices for roughly 99% of the hosts we run on, and the rest
	34	don't have 256 bit integers. */
	35	#if HOST_BITS_PER_WIDEST_FAST_INT > 255
	36	#error Need to increase size of datatype used for popcount
	37	#endif
	38
7a8cba34	39	struct simple_bitmap_def
08158df3	40	{
97508a6b	41	unsigned char popcount; / Population count. */
08158df3 RK	42	unsigned int n_bits; /* Number of bits. */
08158df3 RK	43	unsigned int size; /* Size in elements. */
08158df3	44	SBITMAP_ELT_TYPE elms[1]; /* The elements. */
7a8cba34	45	};
5f6c11d6	46
5f6c11d6	47	/* Return the set size needed for N elements. */
08158df3	48	#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
97508a6b	49	#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
5f6c11d6	50
08158df3 RK	51	/* Test if bit number bitno in the bitmap is set. */
	52	#define TEST_BIT(BITMAP, BITNO) \
	53	((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)
5f6c11d6	54
97508a6b DB	55	/* Set bit number BITNO in the sbitmap MAP. Updates population count
	56	if this bitmap has one. */
	57
	58	static inline void
	59	SET_BIT (sbitmap map, unsigned int bitno)
	60	{
	61	if (map->popcount)
	62	{
	63	bool oldbit;
	64	oldbit = TEST_BIT (map, bitno);
	65	if (!oldbit)
	66	map->popcount[bitno / SBITMAP_ELT_BITS]++;
	67	}
	68	map->elms[bitno / SBITMAP_ELT_BITS]
	69	\|= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
	70	}
	71
	72
	73
	74	/* Reset bit number BITNO in the sbitmap MAP. Updates population
	75	count if this bitmap has one. */
	76
	77	static inline void
	78	RESET_BIT (sbitmap map, unsigned int bitno)
	79	{
	80	if (map->popcount)
	81	{
	82	bool oldbit;
	83	oldbit = TEST_BIT (map, bitno);
	84	if (oldbit)
	85	map->popcount[bitno / SBITMAP_ELT_BITS]--;
	86	}
	87	map->elms[bitno / SBITMAP_ELT_BITS]
	88	&= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
	89	}
5f6c11d6	90
b6e7e9af KH	91	/* The iterator for sbitmap. */
	92	typedef struct {
	93	/* The pointer to the first word of the bitmap. */
be5b01f3	94	const SBITMAP_ELT_TYPE *ptr;
b6e7e9af KH	95
	96	/* The size of the bitmap. */
	97	unsigned int size;
	98
	99	/* The current word index. */
	100	unsigned int word_num;
	101
108267cd	102	/* The current bit index (not modulo SBITMAP_ELT_BITS). */
b6e7e9af KH	103	unsigned int bit_num;
	104
	105	/* The words currently visited. */
	106	SBITMAP_ELT_TYPE word;
	107	} sbitmap_iterator;
	108
	109	/* Initialize the iterator I with sbitmap BMP and the initial index
	110	MIN. */
	111
	112	static inline void
be5b01f3	113	sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
b6e7e9af KH	114	{
b6e7e9af KH	115	i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
108267cd	116	i->bit_num = min;
b6e7e9af KH	117	i->size = bmp->size;
	118	i->ptr = bmp->elms;
	119
	120	if (i->word_num >= i->size)
	121	i->word = 0;
	122	else
108267cd KH	123	i->word = (i->ptr[i->word_num]
108267cd KH	124	>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
b6e7e9af KH	125	}
	126
	127	/* Return true if we have more bits to visit, in which case *N is set
	128	to the index of the bit to be visited. Otherwise, return
	129	false. */
	130
	131	static inline bool
	132	sbitmap_iter_cond (sbitmap_iterator i, unsigned int n)
	133	{
	134	/* Skip words that are zeros. */
	135	for (; i->word == 0; i->word = i->ptr[i->word_num])
	136	{
	137	i->word_num++;
	138
	139	/* If we have reached the end, break. */
	140	if (i->word_num >= i->size)
	141	return false;
	142
	143	i->bit_num = i->word_num * SBITMAP_ELT_BITS;
	144	}
	145
	146	/* Skip bits that are zero. */
	147	for (; (i->word & 1) == 0; i->word >>= 1)
	148	i->bit_num++;
	149
	150	*n = i->bit_num;
	151
	152	return true;
	153	}
	154
	155	/* Advance to the next bit. */
	156
	157	static inline void
	158	sbitmap_iter_next (sbitmap_iterator *i)
	159	{
	160	i->word >>= 1;
	161	i->bit_num++;
	162	}
	163
	164	/* Loop over all elements of SBITMAP, starting with MIN. In each
	165	iteration, N is set to the index of the bit being visited. ITER is
	166	an instance of sbitmap_iterator used to iterate the bitmap. */
	167
	168	#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
	169	for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
	170	sbitmap_iter_cond (&(ITER), &(N)); \
	171	sbitmap_iter_next (&(ITER)))
5f6c11d6	172
ed8d2920 MM	173	#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
	174	do { \
	175	unsigned int word_num_; \
	176	unsigned int bit_num_; \
	177	unsigned int size_ = (SBITMAP)->size; \
	178	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
	179	\
	180	for (word_num_ = size_; word_num_ > 0; word_num_--) \
	181	{ \
	182	SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
	183	\
	184	if (word_ != 0) \
	185	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
	186	{ \
	187	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
	188	\
	189	if ((word_ & _mask) != 0) \
	190	{ \
	191	word_ &= ~ _mask; \
	192	(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
	193	CODE; \
	194	if (word_ == 0) \
	195	break; \
	196	} \
	197	} \
	198	} \
	199	} while (0)
	200
97508a6b	201	#define sbitmap_free(MAP) (free((MAP)->popcount), free((MAP)))
08158df3	202	#define sbitmap_vector_free(VEC) free(VEC)
5f6c11d6	203
be5b01f3 KG	204	extern void dump_sbitmap (FILE *, const_sbitmap);
be5b01f3 KG	205	extern void dump_sbitmap_file (FILE *, const_sbitmap);
46c5ad27 AJ	206	extern void dump_sbitmap_vector (FILE , const char , const char , sbitmap ,
	207	int);
	208	extern sbitmap sbitmap_alloc (unsigned int);
97508a6b	209	extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
46c5ad27 AJ	210	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
46c5ad27 AJ	211	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
be5b01f3 KG	212	extern void sbitmap_copy (sbitmap, const_sbitmap);
	213	extern void sbitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
	214	extern int sbitmap_equal (const_sbitmap, const_sbitmap);
	215	extern bool sbitmap_empty_p (const_sbitmap);
b60db1ba	216	extern bool sbitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
46c5ad27 AJ	217	extern void sbitmap_zero (sbitmap);
	218	extern void sbitmap_ones (sbitmap);
	219	extern void sbitmap_vector_zero (sbitmap *, unsigned int);
	220	extern void sbitmap_vector_ones (sbitmap *, unsigned int);
	221
be5b01f3 KG	222	extern void sbitmap_union_of_diff (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	223	extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	224	extern void sbitmap_difference (sbitmap, const_sbitmap, const_sbitmap);
	225	extern void sbitmap_not (sbitmap, const_sbitmap);
	226	extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	227	extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	228	extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	229	extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	230	extern bool sbitmap_any_common_bits (const_sbitmap, const_sbitmap);
	231	extern void sbitmap_a_and_b (sbitmap, const_sbitmap, const_sbitmap);
	232	extern bool sbitmap_a_and_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	233	extern void sbitmap_a_or_b (sbitmap, const_sbitmap, const_sbitmap);
	234	extern bool sbitmap_a_or_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	235	extern void sbitmap_a_xor_b (sbitmap, const_sbitmap, const_sbitmap);
	236	extern bool sbitmap_a_xor_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	237	extern bool sbitmap_a_subset_b_p (const_sbitmap, const_sbitmap);
	238
	239	extern int sbitmap_first_set_bit (const_sbitmap);
	240	extern int sbitmap_last_set_bit (const_sbitmap);
46c5ad27	241
be5b01f3	242	extern void debug_sbitmap (const_sbitmap);
6de9cd9a	243	extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
3c2c4f22	244	extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
be5b01f3	245	extern void sbitmap_verify_popcount (const_sbitmap);
88657302	246	#endif /* ! GCC_SBITMAP_H */