[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.  */

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;
  int num;
  int i;
} bitset_iterator;


/* Return bytes required for bitset of desired type and size.  */
extern int 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 size in bits of bitset SRC.  */
extern int bitset_size PARAMS ((bitset));

/* Return number of bits set in bitset SRC.  */
extern int bitset_count PARAMS ((bitset));

/* Return bitset type.  */
extern enum bitset_type bitset_type_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] &=					\
      ~((bitset_word) 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) \
  ? (((int)							\
      ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
       >> ((bitno) % BITSET_WORD_BITS)))			\
     & 1)							\
  : BITSET_TEST_ ((bset), (bitno)))
#endif


/* Toggle bit BITNO in bitset BSET and return non-zero if now set.  */
extern int bitset_toggle PARAMS ((bitset, bitset_bindex));

/* DST = 0.  */
extern int bitset_zero PARAMS ((bitset));

/* DST = ~0.  */
extern int bitset_ones PARAMS ((bitset));

/* Return non-zero if all bits in bitset SRC are reset.  */
extern int bitset_empty_p PARAMS ((bitset));

/* Return DST == DST | SRC.  */
extern int bitset_subset_p PARAMS ((bitset, bitset));

/* Return DST == SRC.  */
extern int bitset_equal_p PARAMS ((bitset, bitset));

/* Return DST & SRC == 0.  */
extern int bitset_disjoint_p PARAMS ((bitset, bitset));

/* DST == SRC.  */
extern int bitset_copy PARAMS ((bitset, bitset));

/* DST = ~SRC.  */
extern int bitset_not PARAMS ((bitset, bitset));

/* DST = SRC1 | SRC2.  Return non-zero if DST != SRC1 | SRC2.  */
extern int bitset_or PARAMS ((bitset, bitset, bitset));

/* DST = SRC1 & SRC2.  Return non-zero if DST != SRC1 & SRC2.  */
extern int bitset_and PARAMS ((bitset, bitset, bitset));

/* DST = SRC1 ^ SRC2.  Return non-zero if DST != SRC1 ^ SRC2.  */
extern int bitset_xor PARAMS ((bitset, bitset, bitset));

/* DST = SRC1 & ~SRC2.  Return non-zero if DST != SRC1 & ~SRC2.  */
extern int bitset_andn PARAMS ((bitset, bitset, bitset));

/* DST = (SRC1 | SRC2) & SRC3.  Return non-zero if
   DST != (SRC1 | SRC2) & SRC3.  */
extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));

/* DST = (SRC1 & SRC2) | SRC3.  Return non-zero if
   DST != (SRC1 & SRC2) | SRC3.  */
extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));

/* DST = (SRC1 & ~SRC2) | SRC3.  Return non-zero if
   DST != (SRC1 & ~SRC2) | SRC3.  */
extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));

/* Find next bit set in BSET starting from and including BITNO.  */
extern int bitset_next PARAMS ((bitset, bitset_bindex));

/* Find previous bit set in BSET starting from and including BITNO.  */
extern int bitset_prev PARAMS ((bitset, bitset_bindex));

/* Return non-zero if BITNO in SRC is the only set bit.  */
extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));

/* 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_reverse_list(BSET, LIST, NUM, NEXT) \
BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT) 

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

/* Find last set bit.  */
extern int 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.  */
#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.  */
#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_intersection(DST, SRC1, SRC2)  bitset_and (DST, SRC1, SRC2) 

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

#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
  bitset_andn_or (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. */
	35	BITSET_GREEDY = 32}; /* Prefer fastest. */
	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;
	54	int num;
	55	int i;
	56	} bitset_iterator;
	57
	58
7086e707 AD	59	/* Return bytes required for bitset of desired type and size. */
	60	extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
	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));
	86
	87	/* Return size in bits of bitset SRC. */
	88	extern int bitset_size PARAMS ((bitset));
	89
ef017502 AD	90	/* Return number of bits set in bitset SRC. */
	91	extern int bitset_count PARAMS ((bitset));
	92
613f5e1a AD	93	/* Return bitset type. */
	94	extern enum bitset_type bitset_type_get PARAMS ((bitset));
	95
	96	#if BITSET_INLINE
7086e707 AD	97	static inline void bitset_set PARAMS ((bitset, bitset_bindex));
	98	static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
	99	static inline int bitset_test PARAMS ((bitset, bitset_bindex));
	100
	101	/* Set bit BITNO in bitset BSET. */
	102	static inline void bitset_set (bset, bitno)
	103	bitset bset;
	104	bitset_bindex bitno;
	105	{
	106	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	107	bitset_windex offset = index - bset->b.cindex;
613f5e1a	108
ef017502	109	if (offset < bset->b.csize)
e601ff27	110	bset->b.cdata[offset] \|= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	111	else
ef017502	112	BITSET_SET_ (bset, bitno);
7086e707 AD	113	}
	114
	115
	116	/* Reset bit BITNO in bitset BSET. */
	117	static inline void bitset_reset (bset, bitno)
	118	bitset bset;
	119	bitset_bindex bitno;
	120	{
	121	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	122	bitset_windex offset = index - bset->b.cindex;
613f5e1a	123
ef017502	124	if (offset < bset->b.csize)
e601ff27	125	bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	126	else
ef017502	127	BITSET_RESET_ (bset, bitno);
7086e707 AD	128	}
	129
	130
	131	/* Test bit BITNO in bitset BSET. */
	132	static inline int bitset_test (bset, bitno)
	133	bitset bset;
	134	bitset_bindex bitno;
	135	{
	136	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	137	bitset_windex offset = index - bset->b.cindex;
613f5e1a	138
ef017502 AD	139	if (offset < bset->b.csize)
ef017502 AD	140	return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
7086e707	141	else
ef017502	142	return BITSET_TEST_ (bset, bitno);
7086e707 AD	143	}
	144	#endif
	145
613f5e1a	146	#if ! BITSET_INLINE
7086e707 AD	147
	148	/* Set bit BITNO in bitset BSET. */
	149	#define bitset_set(bset, bitno) \
	150	do \
	151	{ \
	152	bitset_bindex _bitno = (bitno); \
	153	bitset_windex _index = _bitno / BITSET_WORD_BITS; \
ef017502	154	bitset_windex _offset = _index - (bset)->b.cindex; \
7086e707	155	\
ef017502	156	if (_offset < (bset)->b.csize) \
e601ff27 PE	157	(bset)->b.cdata[_offset] \|= \
e601ff27 PE	158	((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	159	else \
ef017502	160	BITSET_SET_ ((bset), _bitno); \
7086e707 AD	161	} while (0)
	162
	163
	164	/* Reset bit BITNO in bitset BSET. */
	165	#define bitset_reset(bset, bitno) \
	166	do \
	167	{ \
	168	bitset_bindex _bitno = (bitno); \
	169	bitset_windex _index = _bitno / BITSET_WORD_BITS; \
ef017502	170	bitset_windex _offset = _index - (bset)->b.cindex; \
7086e707	171	\
ef017502	172	if (_offset < (bset)->b.csize) \
e601ff27 PE	173	(bset)->b.cdata[_offset] &= \
e601ff27 PE	174	~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	175	else \
ef017502	176	BITSET_RESET_ ((bset), _bitno); \
7086e707 AD	177	} while (0)
	178
	179
	180	/* Test bit BITNO in bitset BSET. */
	181	#define bitset_test(bset, bitno) \
ef017502	182	(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
e601ff27 PE	183	? (((int) \
	184	((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
	185	>> ((bitno) % BITSET_WORD_BITS))) \
	186	& 1) \
	187	: BITSET_TEST_ ((bset), (bitno)))
7086e707 AD	188	#endif
7086e707 AD	189
7086e707	190
345cea78 AD	191	/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
	192	extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
	193
7086e707 AD	194	/* DST = 0. */
	195	extern int bitset_zero PARAMS ((bitset));
	196
	197	/* DST = ~0. */
	198	extern int bitset_ones PARAMS ((bitset));
	199
	200	/* Return non-zero if all bits in bitset SRC are reset. */
	201	extern int bitset_empty_p PARAMS ((bitset));
	202
	203	/* Return DST == DST \| SRC. */
	204	extern int bitset_subset_p PARAMS ((bitset, bitset));
	205
	206	/* Return DST == SRC. */
	207	extern int bitset_equal_p PARAMS ((bitset, bitset));
	208
ef017502 AD	209	/* Return DST & SRC == 0. */
	210	extern int bitset_disjoint_p PARAMS ((bitset, bitset));
	211
7086e707 AD	212	/* DST == SRC. */
	213	extern int bitset_copy PARAMS ((bitset, bitset));
	214
	215	/* DST = ~SRC. */
	216	extern int bitset_not PARAMS ((bitset, bitset));
	217
	218	/* DST = SRC1 \| SRC2. Return non-zero if DST != SRC1 \| SRC2. */
	219	extern int bitset_or PARAMS ((bitset, bitset, bitset));
	220
	221	/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
	222	extern int bitset_and PARAMS ((bitset, bitset, bitset));
	223
	224	/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
	225	extern int bitset_xor PARAMS ((bitset, bitset, bitset));
	226
	227	/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
	228	extern int bitset_andn PARAMS ((bitset, bitset, bitset));
	229
7086e707 AD	230	/* DST = (SRC1 \| SRC2) & SRC3. Return non-zero if
	231	DST != (SRC1 \| SRC2) & SRC3. */
	232	extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
	233
	234	/* DST = (SRC1 & SRC2) \| SRC3. Return non-zero if
	235	DST != (SRC1 & SRC2) \| SRC3. */
	236	extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
	237
	238	/* DST = (SRC1 & ~SRC2) \| SRC3. Return non-zero if
	239	DST != (SRC1 & ~SRC2) \| SRC3. */
ef017502	240	extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
7086e707 AD	241
	242	/* Find next bit set in BSET starting from and including BITNO. */
	243	extern int bitset_next PARAMS ((bitset, bitset_bindex));
	244
	245	/* Find previous bit set in BSET starting from and including BITNO. */
	246	extern int bitset_prev PARAMS ((bitset, bitset_bindex));
	247
345cea78 AD	248	/* Return non-zero if BITNO in SRC is the only set bit. */
	249	extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
	250
613f5e1a	251	/* Find list of up to NUM bits set in BSET starting from and including
7086e707 AD	252	NEXT. Return with actual number of bits found and with NEXT
7086e707 AD	253	indicating where search stopped. */
7086e707	254	#define bitset_list(BSET, LIST, NUM, NEXT) \
613f5e1a	255	BITSET_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	256
	257	/* Find reverse list of up to NUM bits set in BSET starting from and
	258	including NEXT. Return with actual number of bits found and with
	259	NEXT indicating where search stopped. /
	260	#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
613f5e1a	261	BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	262
	263	/* Find first set bit. */
	264	extern int bitset_first PARAMS ((bitset));
	265
	266	/* Find last set bit. */
	267	extern int bitset_last PARAMS ((bitset));
	268
	269	/* Dump bitset. */
	270	extern void bitset_dump PARAMS ((FILE *, bitset));
	271
613f5e1a AD	272	/* Loop over all elements of BSET, starting with MIN, setting BIT
	273	to the index of each set bit. */
	274	#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \
	275	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
	276	(ITER.num == BITSET_LIST_SIZE) \
	277	&& (ITER.num = bitset_list (BSET, ITER.list, \
	278	BITSET_LIST_SIZE, &ITER.next));) \
	279	for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
7086e707 AD	280
	281
	282	/* Loop over all elements of BSET, in reverse order starting with
613f5e1a AD	283	MIN, setting BIT to the index of each set bit. */
	284	#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \
	285	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
	286	(ITER.num == BITSET_LIST_SIZE) \
	287	&& (ITER.num = bitset_list_reverse (BSET, ITER.list, \
	288	BITSET_LIST_SIZE, &ITER.next));) \
	289	for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
7086e707 AD	290
7086e707 AD	291
ef017502	292	/* Define set operations in terms of logical operations. */
7086e707	293
613f5e1a	294	#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
7086e707	295
613f5e1a	296	#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
7086e707	297
613f5e1a	298	#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
7086e707 AD	299
7086e707 AD	300	#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
613f5e1a	301	bitset_andn_or (DST, SRC1, SRC2, SRC3)
ef017502	302
7086e707 AD	303
	304	/* Release any memory tied up with bitsets. */
	305	extern void bitset_release_memory PARAMS ((void));
	306
613f5e1a AD	307	/* Enable bitset stats gathering. */
	308	extern void bitset_stats_enable PARAMS ((void));
	309
	310	/* Disable bitset stats gathering. */
	311	extern void bitset_stats_disable PARAMS ((void));
	312
	313	/* Read bitset stats file of accummulated stats. */
	314	void bitset_stats_read PARAMS ((const char *filename));
	315
	316	/* Write bitset stats file of accummulated stats. */
	317	void bitset_stats_write PARAMS ((const char *filename));
7086e707 AD	318
	319	/* Dump bitset stats. */
	320	extern void bitset_stats_dump PARAMS ((FILE *));
	321
	322	/* Function to debug bitset from debugger. */
	323	extern void debug_bitset PARAMS ((bitset));
	324
	325	/* Function to debug bitset stats from debugger. */
	326	extern void debug_bitset_stats PARAMS ((void));
	327
7086e707	328	#endif /* _BITSET_H */
613f5e1a	329