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

/* 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
7aa6d18a	28	#define SBITMAP_ELT_BITS (HOST_BITS_PER_WIDEST_FAST_INT * 1u)
99fa8911	29	#define SBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
5f6c11d6	30
7a8cba34	31	struct simple_bitmap_def
08158df3	32	{
97508a6b	33	unsigned char popcount; / Population count. */
08158df3 RK	34	unsigned int n_bits; /* Number of bits. */
08158df3 RK	35	unsigned int size; /* Size in elements. */
08158df3	36	SBITMAP_ELT_TYPE elms[1]; /* The elements. */
7a8cba34	37	};
5f6c11d6	38
5f6c11d6	39	/* Return the set size needed for N elements. */
08158df3	40	#define SBITMAP_SET_SIZE(N) (((N) + SBITMAP_ELT_BITS - 1) / SBITMAP_ELT_BITS)
97508a6b	41	#define SBITMAP_SIZE_BYTES(BITMAP) ((BITMAP)->size * sizeof (SBITMAP_ELT_TYPE))
5f6c11d6	42
08158df3 RK	43	/* Test if bit number bitno in the bitmap is set. */
	44	#define TEST_BIT(BITMAP, BITNO) \
	45	((BITMAP)->elms [(BITNO) / SBITMAP_ELT_BITS] >> (BITNO) % SBITMAP_ELT_BITS & 1)
5f6c11d6	46
97508a6b DB	47	/* Set bit number BITNO in the sbitmap MAP. Updates population count
	48	if this bitmap has one. */
	49
	50	static inline void
	51	SET_BIT (sbitmap map, unsigned int bitno)
	52	{
	53	if (map->popcount)
	54	{
	55	bool oldbit;
	56	oldbit = TEST_BIT (map, bitno);
	57	if (!oldbit)
	58	map->popcount[bitno / SBITMAP_ELT_BITS]++;
	59	}
	60	map->elms[bitno / SBITMAP_ELT_BITS]
	61	\|= (SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS;
	62	}
	63
	64
	65
	66	/* Reset bit number BITNO in the sbitmap MAP. Updates population
	67	count if this bitmap has one. */
	68
	69	static inline void
	70	RESET_BIT (sbitmap map, unsigned int bitno)
	71	{
	72	if (map->popcount)
	73	{
	74	bool oldbit;
	75	oldbit = TEST_BIT (map, bitno);
	76	if (oldbit)
	77	map->popcount[bitno / SBITMAP_ELT_BITS]--;
	78	}
	79	map->elms[bitno / SBITMAP_ELT_BITS]
	80	&= ~((SBITMAP_ELT_TYPE) 1 << (bitno) % SBITMAP_ELT_BITS);
	81	}
5f6c11d6	82
b6e7e9af KH	83	/* The iterator for sbitmap. */
	84	typedef struct {
	85	/* The pointer to the first word of the bitmap. */
be5b01f3	86	const SBITMAP_ELT_TYPE *ptr;
b6e7e9af KH	87
	88	/* The size of the bitmap. */
	89	unsigned int size;
	90
	91	/* The current word index. */
	92	unsigned int word_num;
	93
108267cd	94	/* The current bit index (not modulo SBITMAP_ELT_BITS). */
b6e7e9af KH	95	unsigned int bit_num;
	96
	97	/* The words currently visited. */
	98	SBITMAP_ELT_TYPE word;
	99	} sbitmap_iterator;
	100
	101	/* Initialize the iterator I with sbitmap BMP and the initial index
	102	MIN. */
	103
	104	static inline void
be5b01f3	105	sbitmap_iter_init (sbitmap_iterator *i, const_sbitmap bmp, unsigned int min)
b6e7e9af KH	106	{
b6e7e9af KH	107	i->word_num = min / (unsigned int) SBITMAP_ELT_BITS;
108267cd	108	i->bit_num = min;
b6e7e9af KH	109	i->size = bmp->size;
	110	i->ptr = bmp->elms;
	111
	112	if (i->word_num >= i->size)
	113	i->word = 0;
	114	else
108267cd KH	115	i->word = (i->ptr[i->word_num]
108267cd KH	116	>> (i->bit_num % (unsigned int) SBITMAP_ELT_BITS));
b6e7e9af KH	117	}
	118
	119	/* Return true if we have more bits to visit, in which case *N is set
	120	to the index of the bit to be visited. Otherwise, return
	121	false. */
	122
	123	static inline bool
	124	sbitmap_iter_cond (sbitmap_iterator i, unsigned int n)
	125	{
	126	/* Skip words that are zeros. */
	127	for (; i->word == 0; i->word = i->ptr[i->word_num])
	128	{
	129	i->word_num++;
	130
	131	/* If we have reached the end, break. */
	132	if (i->word_num >= i->size)
	133	return false;
	134
	135	i->bit_num = i->word_num * SBITMAP_ELT_BITS;
	136	}
	137
	138	/* Skip bits that are zero. */
	139	for (; (i->word & 1) == 0; i->word >>= 1)
	140	i->bit_num++;
	141
	142	*n = i->bit_num;
	143
	144	return true;
	145	}
	146
	147	/* Advance to the next bit. */
	148
	149	static inline void
	150	sbitmap_iter_next (sbitmap_iterator *i)
	151	{
	152	i->word >>= 1;
	153	i->bit_num++;
	154	}
	155
	156	/* Loop over all elements of SBITMAP, starting with MIN. In each
	157	iteration, N is set to the index of the bit being visited. ITER is
	158	an instance of sbitmap_iterator used to iterate the bitmap. */
	159
	160	#define EXECUTE_IF_SET_IN_SBITMAP(SBITMAP, MIN, N, ITER) \
	161	for (sbitmap_iter_init (&(ITER), (SBITMAP), (MIN)); \
	162	sbitmap_iter_cond (&(ITER), &(N)); \
	163	sbitmap_iter_next (&(ITER)))
5f6c11d6	164
ed8d2920 MM	165	#define EXECUTE_IF_SET_IN_SBITMAP_REV(SBITMAP, N, CODE) \
	166	do { \
	167	unsigned int word_num_; \
	168	unsigned int bit_num_; \
	169	unsigned int size_ = (SBITMAP)->size; \
	170	SBITMAP_ELT_TYPE *ptr_ = (SBITMAP)->elms; \
	171	\
	172	for (word_num_ = size_; word_num_ > 0; word_num_--) \
	173	{ \
	174	SBITMAP_ELT_TYPE word_ = ptr_[word_num_ - 1]; \
	175	\
	176	if (word_ != 0) \
	177	for (bit_num_ = SBITMAP_ELT_BITS; bit_num_ > 0; bit_num_--) \
	178	{ \
	179	SBITMAP_ELT_TYPE _mask = (SBITMAP_ELT_TYPE)1 << (bit_num_ - 1);\
	180	\
	181	if ((word_ & _mask) != 0) \
	182	{ \
	183	word_ &= ~ _mask; \
	184	(N) = (word_num_ - 1) * SBITMAP_ELT_BITS + bit_num_ - 1;\
	185	CODE; \
	186	if (word_ == 0) \
	187	break; \
	188	} \
	189	} \
	190	} \
	191	} while (0)
	192
97508a6b	193	#define sbitmap_free(MAP) (free((MAP)->popcount), free((MAP)))
08158df3	194	#define sbitmap_vector_free(VEC) free(VEC)
5f6c11d6	195
be5b01f3 KG	196	extern void dump_sbitmap (FILE *, const_sbitmap);
be5b01f3 KG	197	extern void dump_sbitmap_file (FILE *, const_sbitmap);
46c5ad27 AJ	198	extern void dump_sbitmap_vector (FILE , const char , const char , sbitmap ,
	199	int);
	200	extern sbitmap sbitmap_alloc (unsigned int);
97508a6b	201	extern sbitmap sbitmap_alloc_with_popcount (unsigned int);
46c5ad27 AJ	202	extern sbitmap *sbitmap_vector_alloc (unsigned int, unsigned int);
46c5ad27 AJ	203	extern sbitmap sbitmap_resize (sbitmap, unsigned int, int);
be5b01f3 KG	204	extern void sbitmap_copy (sbitmap, const_sbitmap);
	205	extern void sbitmap_copy_n (sbitmap, const_sbitmap, unsigned int);
	206	extern int sbitmap_equal (const_sbitmap, const_sbitmap);
	207	extern bool sbitmap_empty_p (const_sbitmap);
b60db1ba	208	extern bool sbitmap_range_empty_p (const_sbitmap, unsigned int, unsigned int);
46c5ad27 AJ	209	extern void sbitmap_zero (sbitmap);
	210	extern void sbitmap_ones (sbitmap);
	211	extern void sbitmap_vector_zero (sbitmap *, unsigned int);
	212	extern void sbitmap_vector_ones (sbitmap *, unsigned int);
	213
be5b01f3 KG	214	extern void sbitmap_union_of_diff (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	215	extern bool sbitmap_union_of_diff_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	216	extern void sbitmap_difference (sbitmap, const_sbitmap, const_sbitmap);
	217	extern void sbitmap_not (sbitmap, const_sbitmap);
	218	extern void sbitmap_a_or_b_and_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	219	extern bool sbitmap_a_or_b_and_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	220	extern void sbitmap_a_and_b_or_c (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	221	extern bool sbitmap_a_and_b_or_c_cg (sbitmap, const_sbitmap, const_sbitmap, const_sbitmap);
	222	extern bool sbitmap_any_common_bits (const_sbitmap, const_sbitmap);
	223	extern void sbitmap_a_and_b (sbitmap, const_sbitmap, const_sbitmap);
	224	extern bool sbitmap_a_and_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	225	extern void sbitmap_a_or_b (sbitmap, const_sbitmap, const_sbitmap);
	226	extern bool sbitmap_a_or_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	227	extern void sbitmap_a_xor_b (sbitmap, const_sbitmap, const_sbitmap);
	228	extern bool sbitmap_a_xor_b_cg (sbitmap, const_sbitmap, const_sbitmap);
	229	extern bool sbitmap_a_subset_b_p (const_sbitmap, const_sbitmap);
	230
	231	extern int sbitmap_first_set_bit (const_sbitmap);
	232	extern int sbitmap_last_set_bit (const_sbitmap);
46c5ad27	233
be5b01f3	234	extern void debug_sbitmap (const_sbitmap);
6de9cd9a	235	extern sbitmap sbitmap_realloc (sbitmap, unsigned int);
3c2c4f22	236	extern unsigned long sbitmap_popcount (const_sbitmap, unsigned long);
be5b01f3	237	extern void sbitmap_verify_popcount (const_sbitmap);
88657302	238	#endif /* ! GCC_SBITMAP_H */