[bison.git] / lib / bitset.h

/* Generic bitsets.

   Copyright (C) 2002, 2003, 2004, 2009, 2010 Free Software
   Foundation, Inc.

   Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).

   This program 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 of the License, or
   (at your option) any later version.

   This program 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 this program.  If not, see <http://www.gnu.org/licenses/>.  */

#ifndef _BITSET_H
#define _BITSET_H

/* This file is the public interface to the bitset abstract data type.
   Only use the functions and macros defined in this file.  */

#include "bbitset.h"
#include "obstack.h"
#include <stdio.h>

#if USE_UNLOCKED_IO
# include "unlocked-io.h"
#endif

/* Attributes used to select a bitset implementation.  */
enum bitset_attr {BITSET_FIXED = 1,    /* Bitset size fixed.  */
		  BITSET_VARIABLE = 2, /* Bitset size variable.  */
		  BITSET_DENSE = 4,    /* Bitset dense.  */
		  BITSET_SPARSE = 8,   /* Bitset sparse.  */
		  BITSET_FRUGAL = 16,  /* Prefer most compact.  */
		  BITSET_GREEDY = 32}; /* Prefer fastest at memory expense.  */

typedef unsigned int bitset_attrs;

/* The contents of the union should be considered to be private.
   While I would like to make this union opaque, it needs to be
   visible for the inline bit set/test functions, and for delegation
   to the proper implementation.  */
union bitset_union
{
  /* This must be the first member of every other structure that is a
     member of this union.  */
  struct bbitset_struct b;	        /* Base bitset data.  */

  struct abitset_struct
  {
    struct bbitset_struct b;
    bitset_word words[1];		/* The array of bits.  */
  } a;

  struct ebitset_struct
  {
    struct bbitset_struct b;
    bitset_windex size;			/* Number of elements.  */
    struct ebitset_elt_struct **elts;	/* Expanding array of ptrs to elts.  */
  } e;

  struct lbitset_struct
  {
    struct bbitset_struct b;
    struct lbitset_elt_struct *head;	/* First element in linked list.  */
    struct lbitset_elt_struct *tail;	/* Last element in linked list.  */
  } l;

  struct bitset_stats_struct
  {
    struct bbitset_struct b;
    bitset bset;
  } s;

  struct vbitset_struct
  {
    struct bbitset_struct b;
    bitset_windex size;			/* Allocated size of array.  */
  } v;

};


/* The contents of this structure should be considered private.
   It is used for iterating over set bits.  */
typedef struct
{
  bitset_bindex list[BITSET_LIST_SIZE];
  bitset_bindex next;
  bitset_bindex num;
  bitset_bindex i;
} bitset_iterator;


/* Return bytes required for bitset of desired type and size.  */
extern size_t bitset_bytes (enum bitset_type, bitset_bindex);

/* Initialise a bitset with desired type and size.  */
extern bitset bitset_init (bitset, bitset_bindex, enum bitset_type);

/* Select an implementation type based on the desired bitset size
   and attributes.  */
extern enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);

/* Create a bitset of desired type and size.  The bitset is zeroed.  */
extern bitset bitset_alloc (bitset_bindex, enum bitset_type);

/* Free bitset.  */
extern void bitset_free (bitset);

/* Create a bitset of desired type and size using an obstack.  The
   bitset is zeroed.  */
extern bitset bitset_obstack_alloc (struct obstack *bobstack,
				    bitset_bindex, enum bitset_type);

/* Free bitset allocated on obstack.  */
extern void bitset_obstack_free (bitset);

/* Create a bitset of desired size and attributes.  The bitset is zeroed.  */
extern bitset bitset_create (bitset_bindex, bitset_attrs);

/* Return bitset type.  */
extern enum bitset_type bitset_type_get (bitset);

/* Return bitset type name.  */
extern const char *bitset_type_name_get (bitset);


/* Set bit BITNO in bitset BSET.  */
static inline void
bitset_set (bitset bset, bitset_bindex bitno)
{
  bitset_windex windex = bitno / BITSET_WORD_BITS;
  bitset_windex offset = windex - bset->b.cindex;

  if (offset < bset->b.csize)
    bset->b.cdata[offset] |= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
  else
    BITSET_SET_ (bset, bitno);
}


/* Reset bit BITNO in bitset BSET.  */
static inline void
bitset_reset (bitset bset, bitset_bindex bitno)
{
  bitset_windex windex = bitno / BITSET_WORD_BITS;
  bitset_windex offset = windex - bset->b.cindex;

  if (offset < bset->b.csize)
    bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
  else
    BITSET_RESET_ (bset, bitno);
}


/* Test bit BITNO in bitset BSET.  */
static inline bool
bitset_test (bitset bset, bitset_bindex bitno)
{
  bitset_windex windex = bitno / BITSET_WORD_BITS;
  bitset_windex offset = windex - bset->b.cindex;

  if (offset < bset->b.csize)
    return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
  else
    return BITSET_TEST_ (bset, bitno);
}


/* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)

/* Return size in bits of bitset SRC.  */
#define bitset_size(SRC) BITSET_SIZE_ (SRC)

/* Change size of bitset.  */
extern void bitset_resize (bitset, bitset_bindex);

/* Return number of bits set in bitset SRC.  */
#define bitset_count(SRC) BITSET_COUNT_ (SRC)


/* Return SRC == 0.  */
#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)

/* DST = ~0.  */
#define bitset_ones(DST) BITSET_ONES_ (DST)

/* DST = 0.  */
#define bitset_zero(DST) BITSET_ZERO_ (DST)


/* DST = SRC.  */
#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)

/* Return DST & SRC == 0.  */
#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)

/* Return DST == SRC.  */
#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)

/* DST = ~SRC.  */
#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)

/* Return DST == DST | SRC.  */
#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)


/* DST = SRC1 & SRC2.  */
#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)

/* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)

/* DST = SRC1 & ~SRC2.  */
#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)

/* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)

/* DST = SRC1 | SRC2.  */
#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)

/* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)

/* DST = SRC1 ^ SRC2.  */
#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)

/* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)


/* DST = (SRC1 & SRC2) | SRC3.  */
#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
 BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)

/* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
   DST != (SRC1 & SRC2) | SRC3.  */
#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
 BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)

/* DST = (SRC1 & ~SRC2) | SRC3.  */
#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
 BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)

/* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
   DST != (SRC1 & ~SRC2) | SRC3.  */
#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
 BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)

/* DST = (SRC1 | SRC2) & SRC3.  */
#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
 BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)

/* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
   DST != (SRC1 | SRC2) & SRC3.  */
#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
 BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)

/* Find list of up to NUM bits set in BSET starting from and including
   *NEXT.  Return with actual number of bits found and with *NEXT
   indicating where search stopped.  */
#define bitset_list(BSET, LIST, NUM, NEXT) \
 BITSET_LIST_ (BSET, LIST, NUM, NEXT)

/* Find reverse list of up to NUM bits set in BSET starting from and
   including NEXT.  Return with actual number of bits found and with
   *NEXT indicating where search stopped.  */
#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
 BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)

/* Return true if both bitsets are of the same type and size.  */
extern bool bitset_compatible_p (bitset bset1, bitset bset2);

/* Find next set bit from the given bit index.  */
extern bitset_bindex bitset_next (bitset, bitset_bindex);

/* Find previous set bit from the given bit index.  */
extern bitset_bindex bitset_prev (bitset, bitset_bindex);

/* Find first set bit.  */
extern bitset_bindex bitset_first (bitset);

/* Find last set bit.  */
extern bitset_bindex bitset_last (bitset);

/* Return nonzero if this is the only set bit.  */
extern bool bitset_only_set_p (bitset, bitset_bindex);

/* Dump bitset.  */
extern void bitset_dump (FILE *, bitset);

/* Loop over all elements of BSET, starting with MIN, setting INDEX
   to the index of each set bit.  For example, the following will print
   the bits set in a bitset:

   bitset_bindex i;
   bitset_iterator iter;

   BITSET_FOR_EACH (iter, src, i, 0)
   {
      printf ("%lu ", (unsigned long int) i);
   };
*/
#define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN)				      \
  for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;			      \
       (ITER.num == BITSET_LIST_SIZE)					      \
       && (ITER.num = bitset_list (BSET, ITER.list,			      \
				   BITSET_LIST_SIZE, &ITER.next));)	      \
    for (ITER.i = 0;							      \
	 ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);		      \
	 ITER.i++)


/* Loop over all elements of BSET, in reverse order starting with
   MIN, setting INDEX to the index of each set bit.  For example, the
   following will print the bits set in a bitset in reverse order:

   bitset_bindex i;
   bitset_iterator iter;

   BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
   {
      printf ("%lu ", (unsigned long int) i);
   };
*/
#define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN)			      \
  for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE;			      \
       (ITER.num == BITSET_LIST_SIZE)					      \
       && (ITER.num = bitset_list_reverse (BSET, ITER.list,		      \
					   BITSET_LIST_SIZE, &ITER.next));)   \
    for (ITER.i = 0;							      \
	 ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1);		      \
	 ITER.i++)


/* Define set operations in terms of logical operations.  */

#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)

#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)

#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)

/* Symmetrical difference.  */
#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)

/* Union of difference.  */
#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
  bitset_andn_or (DST, SRC1, SRC2, SRC3)
#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
  bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)


/* Release any memory tied up with bitsets.  */
extern void bitset_release_memory (void);

/* Enable bitset stats gathering.  */
extern void bitset_stats_enable (void);

/* Disable bitset stats gathering.  */
extern void bitset_stats_disable (void);

/* Read bitset stats file of accummulated stats.  */
void bitset_stats_read (const char *file_name);

/* Write bitset stats file of accummulated stats.  */
void bitset_stats_write (const char *file_name);

/* Dump bitset stats.  */
extern void bitset_stats_dump (FILE *);

/* Function to debug bitset from debugger.  */
extern void debug_bitset (bitset);

/* Function to debug bitset stats from debugger.  */
extern void debug_bitset_stats (void);

#endif /* _BITSET_H  */
Commit	Line	Data
7086e707	1	/* Generic bitsets.
7d424de1 PE	2
	3	Copyright (C) 2002, 2003, 2004, 2009, 2010 Free Software
	4	Foundation, Inc.
	5
7086e707 AD	6	Contributed by Michael Hayes (m.hayes@elec.canterbury.ac.nz).
7086e707 AD	7
f16b0819 PE	8	This program is free software: you can redistribute it and/or modify
	9	it under the terms of the GNU General Public License as published by
	10	the Free Software Foundation, either version 3 of the License, or
	11	(at your option) any later version.
	12
	13	This program is distributed in the hope that it will be useful,
	14	but WITHOUT ANY WARRANTY; without even the implied warranty of
	15	MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
	16	GNU General Public License for more details.
	17
	18	You should have received a copy of the GNU General Public License
	19	along with this program. If not, see <http://www.gnu.org/licenses/>. */
7086e707 AD	20
7086e707 AD	21	#ifndef _BITSET_H
04af9e52	22	#define _BITSET_H
7086e707	23
ef017502 AD	24	/* This file is the public interface to the bitset abstract data type.
ef017502 AD	25	Only use the functions and macros defined in this file. */
7086e707	26
ef017502	27	#include "bbitset.h"
7086e707 AD	28	#include "obstack.h"
7086e707 AD	29	#include <stdio.h>
7086e707	30
fb9c0b33 PE	31	#if USE_UNLOCKED_IO
	32	# include "unlocked-io.h"
	33	#endif
	34
ef017502	35	/* Attributes used to select a bitset implementation. */
7086e707 AD	36	enum bitset_attr {BITSET_FIXED = 1, /* Bitset size fixed. */
	37	BITSET_VARIABLE = 2, /* Bitset size variable. */
	38	BITSET_DENSE = 4, /* Bitset dense. */
	39	BITSET_SPARSE = 8, /* Bitset sparse. */
	40	BITSET_FRUGAL = 16, /* Prefer most compact. */
6aa452a6	41	BITSET_GREEDY = 32}; /* Prefer fastest at memory expense. */
7086e707 AD	42
	43	typedef unsigned int bitset_attrs;
	44
47c8386f PE	45	/* The contents of the union should be considered to be private.
	46	While I would like to make this union opaque, it needs to be
	47	visible for the inline bit set/test functions, and for delegation
	48	to the proper implementation. */
	49	union bitset_union
7086e707	50	{
47c8386f PE	51	/* This must be the first member of every other structure that is a
47c8386f PE	52	member of this union. */
144c1e76	53	struct bbitset_struct b; /* Base bitset data. */
47c8386f PE	54
	55	struct abitset_struct
	56	{
	57	struct bbitset_struct b;
47c8386f PE	58	bitset_word words[1]; /* The array of bits. */
	59	} a;
	60
	61	struct ebitset_struct
	62	{
	63	struct bbitset_struct b;
	64	bitset_windex size; /* Number of elements. */
	65	struct ebitset_elt_struct *elts; / Expanding array of ptrs to elts. */
	66	} e;
	67
	68	struct lbitset_struct
	69	{
	70	struct bbitset_struct b;
	71	struct lbitset_elt_struct head; / First element in linked list. */
	72	struct lbitset_elt_struct tail; / Last element in linked list. */
	73	} l;
	74
	75	struct bitset_stats_struct
	76	{
	77	struct bbitset_struct b;
	78	bitset bset;
	79	} s;
144c1e76 PE	80
	81	struct vbitset_struct
	82	{
	83	struct bbitset_struct b;
	84	bitset_windex size; /* Allocated size of array. */
	85	} v;
	86
7086e707 AD	87	};
7086e707 AD	88
613f5e1a AD	89
	90	/* The contents of this structure should be considered private.
	91	It is used for iterating over set bits. */
	92	typedef struct
	93	{
	94	bitset_bindex list[BITSET_LIST_SIZE];
	95	bitset_bindex next;
808a5918 PE	96	bitset_bindex num;
808a5918 PE	97	bitset_bindex i;
613f5e1a AD	98	} bitset_iterator;
	99
	100
7086e707	101	/* Return bytes required for bitset of desired type and size. */
7d7d6663	102	extern size_t bitset_bytes (enum bitset_type, bitset_bindex);
7086e707 AD	103
7086e707 AD	104	/* Initialise a bitset with desired type and size. */
7d7d6663	105	extern bitset bitset_init (bitset, bitset_bindex, enum bitset_type);
7086e707	106
ef017502 AD	107	/* Select an implementation type based on the desired bitset size
ef017502 AD	108	and attributes. */
7d7d6663	109	extern enum bitset_type bitset_type_choose (bitset_bindex, bitset_attrs);
7086e707	110
ef017502	111	/* Create a bitset of desired type and size. The bitset is zeroed. */
7d7d6663	112	extern bitset bitset_alloc (bitset_bindex, enum bitset_type);
7086e707 AD	113
7086e707 AD	114	/* Free bitset. */
7d7d6663	115	extern void bitset_free (bitset);
7086e707	116
ef017502 AD	117	/* Create a bitset of desired type and size using an obstack. The
ef017502 AD	118	bitset is zeroed. */
7d7d6663 PE	119	extern bitset bitset_obstack_alloc (struct obstack *bobstack,
7d7d6663 PE	120	bitset_bindex, enum bitset_type);
7086e707 AD	121
7086e707 AD	122	/* Free bitset allocated on obstack. */
7d7d6663	123	extern void bitset_obstack_free (bitset);
7086e707	124
ef017502	125	/* Create a bitset of desired size and attributes. The bitset is zeroed. */
7d7d6663	126	extern bitset bitset_create (bitset_bindex, bitset_attrs);
7086e707	127
613f5e1a	128	/* Return bitset type. */
7d7d6663	129	extern enum bitset_type bitset_type_get (bitset);
613f5e1a	130
6aa452a6	131	/* Return bitset type name. */
7d7d6663	132	extern const char *bitset_type_name_get (bitset);
6aa452a6	133
7086e707 AD	134
7086e707 AD	135	/* Set bit BITNO in bitset BSET. */
04af9e52 PE	136	static inline void
04af9e52 PE	137	bitset_set (bitset bset, bitset_bindex bitno)
7086e707	138	{
dbba6a3b PE	139	bitset_windex windex = bitno / BITSET_WORD_BITS;
dbba6a3b PE	140	bitset_windex offset = windex - bset->b.cindex;
04af9e52	141
ef017502	142	if (offset < bset->b.csize)
e601ff27	143	bset->b.cdata[offset] \|= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	144	else
ef017502	145	BITSET_SET_ (bset, bitno);
7086e707 AD	146	}
	147
	148
	149	/* Reset bit BITNO in bitset BSET. */
04af9e52 PE	150	static inline void
04af9e52 PE	151	bitset_reset (bitset bset, bitset_bindex bitno)
7086e707	152	{
dbba6a3b PE	153	bitset_windex windex = bitno / BITSET_WORD_BITS;
dbba6a3b PE	154	bitset_windex offset = windex - bset->b.cindex;
04af9e52	155
ef017502	156	if (offset < bset->b.csize)
e601ff27	157	bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	158	else
ef017502	159	BITSET_RESET_ (bset, bitno);
7086e707 AD	160	}
	161
	162
	163	/* Test bit BITNO in bitset BSET. */
d0829076	164	static inline bool
04af9e52	165	bitset_test (bitset bset, bitset_bindex bitno)
7086e707	166	{
dbba6a3b PE	167	bitset_windex windex = bitno / BITSET_WORD_BITS;
dbba6a3b PE	168	bitset_windex offset = windex - bset->b.cindex;
04af9e52	169
ef017502 AD	170	if (offset < bset->b.csize)
ef017502 AD	171	return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
7086e707	172	else
ef017502	173	return BITSET_TEST_ (bset, bitno);
7086e707	174	}
7086e707	175
7086e707	176
345cea78	177	/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
6aa452a6	178	#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
345cea78	179
6aa452a6 AD	180	/* Return size in bits of bitset SRC. */
	181	#define bitset_size(SRC) BITSET_SIZE_ (SRC)
	182
144c1e76	183	/* Change size of bitset. */
7d7d6663	184	extern void bitset_resize (bitset, bitset_bindex);
144c1e76	185
6aa452a6 AD	186	/* Return number of bits set in bitset SRC. */
	187	#define bitset_count(SRC) BITSET_COUNT_ (SRC)
	188
	189
	190	/* Return SRC == 0. */
	191	#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
7086e707 AD	192
7086e707 AD	193	/* DST = ~0. */
6aa452a6	194	#define bitset_ones(DST) BITSET_ONES_ (DST)
7086e707	195
6aa452a6 AD	196	/* DST = 0. */
6aa452a6 AD	197	#define bitset_zero(DST) BITSET_ZERO_ (DST)
7086e707	198
7086e707	199
6aa452a6 AD	200
	201	/* DST = SRC. */
	202	#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
7086e707	203
ef017502	204	/* Return DST & SRC == 0. */
6aa452a6	205	#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
ef017502	206
6aa452a6 AD	207	/* Return DST == SRC. */
6aa452a6 AD	208	#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
7086e707 AD	209
7086e707 AD	210	/* DST = ~SRC. */
6aa452a6 AD	211	#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
	212
	213	/* Return DST == DST \| SRC. */
	214	#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
7086e707	215
6aa452a6 AD	216
	217
	218	/* DST = SRC1 & SRC2. */
	219	#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
7086e707 AD	220
7086e707 AD	221	/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
6aa452a6	222	#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
7086e707	223
6aa452a6 AD	224	/* DST = SRC1 & ~SRC2. */
6aa452a6 AD	225	#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
7086e707 AD	226
7086e707 AD	227	/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
6aa452a6	228	#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
7086e707	229
6aa452a6 AD	230	/* DST = SRC1 \| SRC2. */
	231	#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
	232
	233	/* DST = SRC1 \| SRC2. Return non-zero if DST != SRC1 \| SRC2. */
	234	#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
	235
	236	/* DST = SRC1 ^ SRC2. */
	237	#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
	238
	239	/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
	240	#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
	241
	242
	243
	244	/* DST = (SRC1 & SRC2) \| SRC3. */
	245	#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
	246	BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
7086e707 AD	247
	248	/* DST = (SRC1 & SRC2) \| SRC3. Return non-zero if
	249	DST != (SRC1 & SRC2) \| SRC3. */
6aa452a6 AD	250	#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
	251	BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
	252
	253	/* DST = (SRC1 & ~SRC2) \| SRC3. */
	254	#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
	255	BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
7086e707 AD	256
	257	/* DST = (SRC1 & ~SRC2) \| SRC3. Return non-zero if
	258	DST != (SRC1 & ~SRC2) \| SRC3. */
6aa452a6 AD	259	#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
6aa452a6 AD	260	BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
7086e707	261
6aa452a6 AD	262	/* DST = (SRC1 \| SRC2) & SRC3. */
	263	#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
	264	BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
7086e707	265
6aa452a6 AD	266	/* DST = (SRC1 \| SRC2) & SRC3. Return non-zero if
	267	DST != (SRC1 \| SRC2) & SRC3. */
	268	#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
	269	BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
345cea78	270
04af9e52	271	/* Find list of up to NUM bits set in BSET starting from and including
7086e707 AD	272	NEXT. Return with actual number of bits found and with NEXT
7086e707 AD	273	indicating where search stopped. */
7086e707	274	#define bitset_list(BSET, LIST, NUM, NEXT) \
04af9e52	275	BITSET_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	276
	277	/* Find reverse list of up to NUM bits set in BSET starting from and
	278	including NEXT. Return with actual number of bits found and with
	279	NEXT indicating where search stopped. /
6aa452a6	280	#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
04af9e52	281	BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
6aa452a6	282
144c1e76	283	/* Return true if both bitsets are of the same type and size. */
fa8db4ba	284	extern bool bitset_compatible_p (bitset bset1, bitset bset2);
7086e707	285
144c1e76	286	/* Find next set bit from the given bit index. */
7d7d6663	287	extern bitset_bindex bitset_next (bitset, bitset_bindex);
47c8386f	288
144c1e76	289	/* Find previous set bit from the given bit index. */
7d7d6663	290	extern bitset_bindex bitset_prev (bitset, bitset_bindex);
47c8386f	291
7086e707	292	/* Find first set bit. */
7d7d6663	293	extern bitset_bindex bitset_first (bitset);
7086e707 AD	294
7086e707 AD	295	/* Find last set bit. */
7d7d6663	296	extern bitset_bindex bitset_last (bitset);
7086e707	297
47c8386f	298	/* Return nonzero if this is the only set bit. */
7d7d6663	299	extern bool bitset_only_set_p (bitset, bitset_bindex);
47c8386f	300
7086e707	301	/* Dump bitset. */
7d7d6663	302	extern void bitset_dump (FILE *, bitset);
7086e707	303
144c1e76	304	/* Loop over all elements of BSET, starting with MIN, setting INDEX
6aa452a6 AD	305	to the index of each set bit. For example, the following will print
	306	the bits set in a bitset:
	307
fa8db4ba	308	bitset_bindex i;
6aa452a6 AD	309	bitset_iterator iter;
6aa452a6 AD	310
fa8db4ba	311	BITSET_FOR_EACH (iter, src, i, 0)
6aa452a6	312	{
fa8db4ba	313	printf ("%lu ", (unsigned long int) i);
6aa452a6 AD	314	};
6aa452a6 AD	315	*/
144c1e76	316	#define BITSET_FOR_EACH(ITER, BSET, INDEX, MIN) \
613f5e1a	317	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
04098407 PE	318	(ITER.num == BITSET_LIST_SIZE) \
04098407 PE	319	&& (ITER.num = bitset_list (BSET, ITER.list, \
04af9e52	320	BITSET_LIST_SIZE, &ITER.next));) \
2175bfbd	321	for (ITER.i = 0; \
144c1e76	322	ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
2175bfbd	323	ITER.i++)
7086e707 AD	324
	325
	326	/* Loop over all elements of BSET, in reverse order starting with
fa8db4ba	327	MIN, setting INDEX to the index of each set bit. For example, the
6aa452a6 AD	328	following will print the bits set in a bitset in reverse order:
6aa452a6 AD	329
fa8db4ba	330	bitset_bindex i;
6aa452a6 AD	331	bitset_iterator iter;
6aa452a6 AD	332
fa8db4ba	333	BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
6aa452a6	334	{
fa8db4ba	335	printf ("%lu ", (unsigned long int) i);
6aa452a6 AD	336	};
6aa452a6 AD	337	*/
144c1e76	338	#define BITSET_FOR_EACH_REVERSE(ITER, BSET, INDEX, MIN) \
613f5e1a	339	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
04098407	340	(ITER.num == BITSET_LIST_SIZE) \
613f5e1a	341	&& (ITER.num = bitset_list_reverse (BSET, ITER.list, \
144c1e76	342	BITSET_LIST_SIZE, &ITER.next));) \
2175bfbd	343	for (ITER.i = 0; \
144c1e76	344	ITER.i < ITER.num && ((INDEX) = ITER.list[ITER.i], 1); \
2175bfbd	345	ITER.i++)
7086e707 AD	346
7086e707 AD	347
ef017502	348	/* Define set operations in terms of logical operations. */
7086e707	349
04af9e52 PE	350	#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
04af9e52 PE	351	#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
7086e707	352
04af9e52 PE	353	#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
04af9e52 PE	354	#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
7086e707	355
04af9e52 PE	356	#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
04af9e52 PE	357	#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
7086e707	358
6aa452a6	359	/* Symmetrical difference. */
04af9e52 PE	360	#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
04af9e52 PE	361	#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
6aa452a6 AD	362
6aa452a6 AD	363	/* Union of difference. */
7086e707	364	#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
04af9e52	365	bitset_andn_or (DST, SRC1, SRC2, SRC3)
6aa452a6	366	#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
04af9e52	367	bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
6aa452a6	368
ef017502	369
7086e707	370	/* Release any memory tied up with bitsets. */
7d7d6663	371	extern void bitset_release_memory (void);
7086e707	372
613f5e1a	373	/* Enable bitset stats gathering. */
7d7d6663	374	extern void bitset_stats_enable (void);
613f5e1a AD	375
613f5e1a AD	376	/* Disable bitset stats gathering. */
7d7d6663	377	extern void bitset_stats_disable (void);
613f5e1a AD	378
613f5e1a AD	379	/* Read bitset stats file of accummulated stats. */
48b16bbc	380	void bitset_stats_read (const char *file_name);
613f5e1a AD	381
613f5e1a AD	382	/* Write bitset stats file of accummulated stats. */
48b16bbc	383	void bitset_stats_write (const char *file_name);
7086e707 AD	384
7086e707 AD	385	/* Dump bitset stats. */
7d7d6663	386	extern void bitset_stats_dump (FILE *);
7086e707 AD	387
7086e707 AD	388	/* Function to debug bitset from debugger. */
7d7d6663	389	extern void debug_bitset (bitset);
7086e707 AD	390
7086e707 AD	391	/* Function to debug bitset stats from debugger. */
7d7d6663	392	extern void debug_bitset_stats (void);
7086e707	393
7086e707	394	#endif /* _BITSET_H */