[bison.git] / lib / bitset.h

/* Generic bitsets.
   Copyright (C) 2002 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 2 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, write to the Free Software
Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

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

/* 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 structure should be considered to be private.
   While I would like to make this structure opaque, it needs to be
   visible for the inline bit set/test functions.  */
struct bitset_struct
{
  struct bbitset_struct b;
};


/* 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 PARAMS ((enum bitset_type, bitset_bindex));

/* Initialise a bitset with desired type and size.  */
extern bitset bitset_init PARAMS ((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 PARAMS ((bitset_bindex,
						    bitset_attrs));

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

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

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

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

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

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

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

#if BITSET_INLINE
static inline void bitset_set PARAMS ((bitset, bitset_bindex));
static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
static inline int bitset_test PARAMS ((bitset, bitset_bindex));

/* Set bit BITNO in bitset BSET.  */
static inline void bitset_set (bset, bitno)
    bitset bset;
    bitset_bindex bitno;
{
  bitset_windex index = bitno / BITSET_WORD_BITS;
  bitset_windex offset = index - 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 (bset, bitno)
    bitset bset;
    bitset_bindex bitno;
{
  bitset_windex index = bitno / BITSET_WORD_BITS;
  bitset_windex offset = index - 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 int bitset_test (bset, bitno)
    bitset bset;
    bitset_bindex bitno;
{
  bitset_windex index = bitno / BITSET_WORD_BITS;
  bitset_windex offset = index - bset->b.cindex;
  
  if (offset < bset->b.csize)
    return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
  else
    return BITSET_TEST_ (bset, bitno);
}
#endif

#if ! BITSET_INLINE

/* Set bit BITNO in bitset BSET.  */
#define bitset_set(bset, bitno)					\
do   								\
{    								\
  bitset_bindex _bitno = (bitno);				\
  bitset_windex _index = _bitno / BITSET_WORD_BITS; 		\
  bitset_windex _offset = _index - (bset)->b.cindex;		\
  								\
  if (_offset < (bset)->b.csize)					\
    (bset)->b.cdata[_offset] |=					\
      ((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); 	\
  else  							\
    BITSET_SET_ ((bset), _bitno);				\
} while (0)


/* Reset bit BITNO in bitset BSET.  */
#define bitset_reset(bset, bitno)				\
do   								\
{    								\
  bitset_bindex _bitno = (bitno);				\
  bitset_windex _index = _bitno / BITSET_WORD_BITS; 		\
  bitset_windex _offset = _index - (bset)->b.cindex;		\
  								\
  if (_offset < (bset)->b.csize)				\
    (bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); 	\
  else  							\
    BITSET_RESET_ ((bset), _bitno);				\
} while (0)


/* Test bit BITNO in bitset BSET.  */
#define bitset_test(bset, bitno) \
(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize)  \
  ? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
     >> ((bitno) % BITSET_WORD_BITS)) & 1 \
  : (unsigned int) BITSET_TEST_ ((bset), (bitno)))
#endif


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

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


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

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

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

/* Loop over all elements of BSET, starting with MIN, setting BIT
   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_zero (dst);
   BITSET_FOR_EACH (iter, src, i, 0)
   {
      printf ("%ld ", i);
   };
*/
#define BITSET_FOR_EACH(ITER, BSET, BIT, 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; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)


/* Loop over all elements of BSET, in reverse order starting with
   MIN,  setting BIT 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_zero (dst);
   BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
   {
      printf ("%ld ", i);
   };
*/
#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, 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; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; 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 PARAMS ((void));

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

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

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

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

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

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

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

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