[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;
};

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

#if BITSET_CACHE && 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] |= (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] &= ~(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_CACHE && ! 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] |= (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

#if ! BITSET_CACHE
/* Set bit BITNO in bitset SRC.  */
#define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO)

/* Reset bit BITNO in bitset SRC.  */
#define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO)

/* Return non-zero if bit BITNO in bitset SRC is set.  */
#define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, 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.  */
#if BITSET_STATS
extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
				bitset_bindex *));
#else
#define bitset_list(BSET, LIST, NUM, NEXT) \
BITSET_LIST_ (BSET, LIST, NUM, NEXT)
#endif

/* 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, executing CODE.  */
#define BITSET_EXECUTE(BSET, MIN, N, CODE)				\
do {									\
  bitset_bindex _list[BITSET_LIST_SIZE];				\
  bitset_bindex _next = (MIN);						\
  int _num;								\
    									\
  while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
    {									\
       int _i;								\
									\
       for (_i = 0; _i < _num; _i++)					\
	 {								\
	    (N) = _list[_i];						\
            CODE;							\
	 }								\
       if (_num < BITSET_LIST_SIZE)					\
         break;								\
    }									\
} while (0)


/* Loop over all elements of BSET, in reverse order starting with
   MIN, executing CODE.  */
#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE)			\
do {									\
  bitset_bindex _list[BITSET_LIST_SIZE];				\
  bitset_bindex _next = (MIN);						\
  int _num;								\
    									\
  while ((_num = bitset_reverse_list ((BSET), _list, 			\
                                      BITSET_LIST_SIZE, &_next)))	\
    {									\
       int _i;								\
									\
       for (_i = 0; _i < _num; _i++)					\
	 {								\
	    (N) = _list[_i];						\
            CODE;							\
	 }								\
       if (_num < BITSET_LIST_SIZE)					\
         break;								\
    }									\
} while (0)


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

/* Initialise bitset stats.  */
extern void bitset_stats_init PARAMS ((void));

/* 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
	20	#define _BITSET_H
	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
7086e707 AD	47	/* Return bytes required for bitset of desired type and size. */
	48	extern int bitset_bytes PARAMS ((enum bitset_type, bitset_bindex));
	49
	50	/* Initialise a bitset with desired type and size. */
	51	extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum bitset_type));
	52
ef017502 AD	53	/* Select an implementation type based on the desired bitset size
ef017502 AD	54	and attributes. */
7086e707 AD	55	extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
	56	bitset_attrs));
	57
ef017502	58	/* Create a bitset of desired type and size. The bitset is zeroed. */
7086e707 AD	59	extern bitset bitset_alloc PARAMS ((bitset_bindex, enum bitset_type));
	60
	61	/* Free bitset. */
	62	extern void bitset_free PARAMS ((bitset));
	63
ef017502 AD	64	/* Create a bitset of desired type and size using an obstack. The
ef017502 AD	65	bitset is zeroed. */
7086e707 AD	66	extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
	67	bitset_bindex, enum bitset_type));
	68
	69	/* Free bitset allocated on obstack. */
	70	extern void bitset_obstack_free PARAMS ((bitset));
	71
ef017502	72	/* Create a bitset of desired size and attributes. The bitset is zeroed. */
7086e707 AD	73	extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
	74
	75	/* Return size in bits of bitset SRC. */
	76	extern int bitset_size PARAMS ((bitset));
	77
ef017502 AD	78	/* Return number of bits set in bitset SRC. */
	79	extern int bitset_count PARAMS ((bitset));
	80
7086e707 AD	81	#if BITSET_CACHE && BITSET_INLINE
	82	static inline void bitset_set PARAMS ((bitset, bitset_bindex));
	83	static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
	84	static inline int bitset_test PARAMS ((bitset, bitset_bindex));
	85
	86	/* Set bit BITNO in bitset BSET. */
	87	static inline void bitset_set (bset, bitno)
	88	bitset bset;
	89	bitset_bindex bitno;
	90	{
	91	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	92	bitset_windex offset = index - bset->b.cindex;
7086e707	93
ef017502 AD	94	if (offset < bset->b.csize)
ef017502 AD	95	bset->b.cdata[offset] \|= (1 << (bitno % BITSET_WORD_BITS));
7086e707	96	else
ef017502	97	BITSET_SET_ (bset, bitno);
7086e707 AD	98	}
	99
	100
	101	/* Reset bit BITNO in bitset BSET. */
	102	static inline void bitset_reset (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;
7086e707	108
ef017502 AD	109	if (offset < bset->b.csize)
ef017502 AD	110	bset->b.cdata[offset] &= ~(1 << (bitno % BITSET_WORD_BITS));
7086e707	111	else
ef017502	112	BITSET_RESET_ (bset, bitno);
7086e707 AD	113	}
	114
	115
	116	/* Test bit BITNO in bitset BSET. */
	117	static inline int bitset_test (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;
7086e707	123
ef017502 AD	124	if (offset < bset->b.csize)
ef017502 AD	125	return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
7086e707	126	else
ef017502	127	return BITSET_TEST_ (bset, bitno);
7086e707 AD	128	}
	129	#endif
	130
	131	#if BITSET_CACHE && ! BITSET_INLINE
	132
	133	/* Set bit BITNO in bitset BSET. */
	134	#define bitset_set(bset, bitno) \
	135	do \
	136	{ \
	137	bitset_bindex _bitno = (bitno); \
	138	bitset_windex _index = _bitno / BITSET_WORD_BITS; \
ef017502	139	bitset_windex _offset = _index - (bset)->b.cindex; \
7086e707	140	\
ef017502 AD	141	if (_offset < (bset)->b.csize) \
ef017502 AD	142	(bset)->b.cdata[_offset] \|= (1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	143	else \
ef017502	144	BITSET_SET_ ((bset), _bitno); \
7086e707 AD	145	} while (0)
	146
	147
	148	/* Reset bit BITNO in bitset BSET. */
	149	#define bitset_reset(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 AD	156	if (_offset < (bset)->b.csize) \
ef017502 AD	157	(bset)->b.cdata[_offset] &= ~(1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	158	else \
ef017502	159	BITSET_RESET_ ((bset), _bitno); \
7086e707 AD	160	} while (0)
	161
	162
	163	/* Test bit BITNO in bitset BSET. */
	164	#define bitset_test(bset, bitno) \
ef017502 AD	165	(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
ef017502 AD	166	? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
7086e707	167	>> ((bitno) % BITSET_WORD_BITS)) & 1 \
ef017502	168	: (unsigned int) BITSET_TEST_ ((bset), (bitno)))
7086e707 AD	169	#endif
	170
	171	#if ! BITSET_CACHE
	172	/* Set bit BITNO in bitset SRC. */
ef017502	173	#define bitset_set(SRC, BITNO) BITSET_SET_ (SRC, BITNO)
7086e707 AD	174
7086e707 AD	175	/* Reset bit BITNO in bitset SRC. */
ef017502	176	#define bitset_reset(SRC, BITNO) BITSET_RESET_ (SRC, BITNO)
7086e707 AD	177
7086e707 AD	178	/* Return non-zero if bit BITNO in bitset SRC is set. */
ef017502	179	#define bitset_test(SRC, BITNO) BITSET_TEST_ (SRC, BITNO)
7086e707 AD	180	#endif
7086e707 AD	181
345cea78 AD	182	/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
	183	extern int bitset_toggle PARAMS ((bitset, bitset_bindex));
	184
7086e707 AD	185	/* DST = 0. */
	186	extern int bitset_zero PARAMS ((bitset));
	187
	188	/* DST = ~0. */
	189	extern int bitset_ones PARAMS ((bitset));
	190
	191	/* Return non-zero if all bits in bitset SRC are reset. */
	192	extern int bitset_empty_p PARAMS ((bitset));
	193
	194	/* Return DST == DST \| SRC. */
	195	extern int bitset_subset_p PARAMS ((bitset, bitset));
	196
	197	/* Return DST == SRC. */
	198	extern int bitset_equal_p PARAMS ((bitset, bitset));
	199
ef017502 AD	200	/* Return DST & SRC == 0. */
	201	extern int bitset_disjoint_p PARAMS ((bitset, bitset));
	202
7086e707 AD	203	/* DST == SRC. */
	204	extern int bitset_copy PARAMS ((bitset, bitset));
	205
	206	/* DST = ~SRC. */
	207	extern int bitset_not PARAMS ((bitset, bitset));
	208
	209	/* DST = SRC1 \| SRC2. Return non-zero if DST != SRC1 \| SRC2. */
	210	extern int bitset_or PARAMS ((bitset, bitset, bitset));
	211
	212	/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
	213	extern int bitset_and PARAMS ((bitset, bitset, bitset));
	214
	215	/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
	216	extern int bitset_xor PARAMS ((bitset, bitset, bitset));
	217
	218	/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
	219	extern int bitset_andn PARAMS ((bitset, bitset, bitset));
	220
7086e707 AD	221	/* DST = (SRC1 \| SRC2) & SRC3. Return non-zero if
	222	DST != (SRC1 \| SRC2) & SRC3. */
	223	extern int bitset_or_and PARAMS ((bitset, bitset, bitset, bitset));
	224
	225	/* DST = (SRC1 & SRC2) \| SRC3. Return non-zero if
	226	DST != (SRC1 & SRC2) \| SRC3. */
	227	extern int bitset_and_or PARAMS ((bitset, bitset, bitset, bitset));
	228
	229	/* DST = (SRC1 & ~SRC2) \| SRC3. Return non-zero if
	230	DST != (SRC1 & ~SRC2) \| SRC3. */
ef017502	231	extern int bitset_andn_or PARAMS ((bitset, bitset, bitset, bitset));
7086e707 AD	232
	233	/* Find next bit set in BSET starting from and including BITNO. */
	234	extern int bitset_next PARAMS ((bitset, bitset_bindex));
	235
	236	/* Find previous bit set in BSET starting from and including BITNO. */
	237	extern int bitset_prev PARAMS ((bitset, bitset_bindex));
	238
345cea78 AD	239	/* Return non-zero if BITNO in SRC is the only set bit. */
	240	extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
	241
7086e707 AD	242	/* Find list of up to NUM bits set in BSET starting from and including
	243	NEXT. Return with actual number of bits found and with NEXT
	244	indicating where search stopped. */
	245	#if BITSET_STATS
	246	extern int bitset_list PARAMS ((bitset, bitset_bindex *, bitset_bindex,
	247	bitset_bindex *));
	248	#else
	249	#define bitset_list(BSET, LIST, NUM, NEXT) \
ef017502	250	BITSET_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	251	#endif
	252
	253	/* Find reverse list of up to NUM bits set in BSET starting from and
	254	including NEXT. Return with actual number of bits found and with
	255	NEXT indicating where search stopped. /
	256	#define bitset_reverse_list(BSET, LIST, NUM, NEXT) \
ef017502	257	BITSET_REVERSE_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	258
	259	/* Find first set bit. */
	260	extern int bitset_first PARAMS ((bitset));
	261
	262	/* Find last set bit. */
	263	extern int bitset_last PARAMS ((bitset));
	264
	265	/* Dump bitset. */
	266	extern void bitset_dump PARAMS ((FILE *, bitset));
	267
	268	/* Loop over all elements of BSET, starting with MIN, executing CODE. */
	269	#define BITSET_EXECUTE(BSET, MIN, N, CODE) \
	270	do { \
	271	bitset_bindex _list[BITSET_LIST_SIZE]; \
	272	bitset_bindex _next = (MIN); \
	273	int _num; \
	274	\
	275	while ((_num = bitset_list ((BSET), _list, BITSET_LIST_SIZE, &_next)))\
	276	{ \
	277	int _i; \
	278	\
	279	for (_i = 0; _i < _num; _i++) \
	280	{ \
	281	(N) = _list[_i]; \
	282	CODE; \
	283	} \
	284	if (_num < BITSET_LIST_SIZE) \
	285	break; \
	286	} \
	287	} while (0)
	288
	289
	290	/* Loop over all elements of BSET, in reverse order starting with
	291	MIN, executing CODE. */
	292	#define BITSET_REVERSE_EXECUTE(BSET, MIN, N, CODE) \
	293	do { \
	294	bitset_bindex _list[BITSET_LIST_SIZE]; \
	295	bitset_bindex _next = (MIN); \
	296	int _num; \
	297	\
	298	while ((_num = bitset_reverse_list ((BSET), _list, \
	299	BITSET_LIST_SIZE, &_next))) \
	300	{ \
	301	int _i; \
	302	\
	303	for (_i = 0; _i < _num; _i++) \
	304	{ \
	305	(N) = _list[_i]; \
	306	CODE; \
	307	} \
	308	if (_num < BITSET_LIST_SIZE) \
	309	break; \
	310	} \
	311	} while (0)
	312
	313
ef017502	314	/* Define set operations in terms of logical operations. */
7086e707 AD	315
	316	#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
	317
	318	#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
	319
	320	#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
	321
	322	#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
ef017502 AD	323	bitset_andn_or (DST, SRC1, SRC2, SRC3)
ef017502 AD	324
7086e707 AD	325
	326	/* Release any memory tied up with bitsets. */
	327	extern void bitset_release_memory PARAMS ((void));
	328
	329	/* Initialise bitset stats. */
	330	extern void bitset_stats_init PARAMS ((void));
	331
	332	/* Dump bitset stats. */
	333	extern void bitset_stats_dump PARAMS ((FILE *));
	334
	335	/* Function to debug bitset from debugger. */
	336	extern void debug_bitset PARAMS ((bitset));
	337
	338	/* Function to debug bitset stats from debugger. */
	339	extern void debug_bitset_stats PARAMS ((void));
	340
7086e707	341	#endif /* _BITSET_H */