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

  struct abitset_struct
  {
    struct bbitset_struct b;
    bitset_bindex n_bits;		/* Number of bits.  */
    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;
};


/* 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] &=					\
       ~((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)  \
  ? ((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 next set bit.  */
extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));

/* Find previous set bit.  */
extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));

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

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

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

/* 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
47c8386f PE	39	/* The contents of the union should be considered to be private.
	40	While I would like to make this union opaque, it needs to be
	41	visible for the inline bit set/test functions, and for delegation
	42	to the proper implementation. */
	43	union bitset_union
7086e707	44	{
47c8386f PE	45	/* This must be the first member of every other structure that is a
47c8386f PE	46	member of this union. */
ef017502	47	struct bbitset_struct b;
47c8386f PE	48
	49	struct abitset_struct
	50	{
	51	struct bbitset_struct b;
	52	bitset_bindex n_bits; /* Number of bits. */
	53	bitset_word words[1]; /* The array of bits. */
	54	} a;
	55
	56	struct ebitset_struct
	57	{
	58	struct bbitset_struct b;
	59	bitset_windex size; /* Number of elements. */
	60	struct ebitset_elt_struct *elts; / Expanding array of ptrs to elts. */
	61	} e;
	62
	63	struct lbitset_struct
	64	{
	65	struct bbitset_struct b;
	66	struct lbitset_elt_struct head; / First element in linked list. */
	67	struct lbitset_elt_struct tail; / Last element in linked list. */
	68	} l;
	69
	70	struct bitset_stats_struct
	71	{
	72	struct bbitset_struct b;
	73	bitset bset;
	74	} s;
7086e707 AD	75	};
7086e707 AD	76
613f5e1a AD	77
	78	/* The contents of this structure should be considered private.
	79	It is used for iterating over set bits. */
	80	typedef struct
	81	{
	82	bitset_bindex list[BITSET_LIST_SIZE];
	83	bitset_bindex next;
808a5918 PE	84	bitset_bindex num;
808a5918 PE	85	bitset_bindex i;
613f5e1a AD	86	} bitset_iterator;
	87
	88
7086e707	89	/* Return bytes required for bitset of desired type and size. */
47c8386f	90	extern size_t bitset_bytes PARAMS ((enum_bitset_type, bitset_bindex));
7086e707 AD	91
7086e707 AD	92	/* Initialise a bitset with desired type and size. */
47c8386f	93	extern bitset bitset_init PARAMS ((bitset, bitset_bindex, enum_bitset_type));
7086e707	94
ef017502 AD	95	/* Select an implementation type based on the desired bitset size
ef017502 AD	96	and attributes. */
7086e707 AD	97	extern enum bitset_type bitset_type_choose PARAMS ((bitset_bindex,
	98	bitset_attrs));
	99
ef017502	100	/* Create a bitset of desired type and size. The bitset is zeroed. */
47c8386f	101	extern bitset bitset_alloc PARAMS ((bitset_bindex, enum_bitset_type));
7086e707 AD	102
	103	/* Free bitset. */
	104	extern void bitset_free PARAMS ((bitset));
	105
ef017502 AD	106	/* Create a bitset of desired type and size using an obstack. The
ef017502 AD	107	bitset is zeroed. */
7086e707	108	extern bitset bitset_obstack_alloc PARAMS ((struct obstack *bobstack,
47c8386f	109	bitset_bindex, enum_bitset_type));
7086e707 AD	110
	111	/* Free bitset allocated on obstack. */
	112	extern void bitset_obstack_free PARAMS ((bitset));
	113
ef017502	114	/* Create a bitset of desired size and attributes. The bitset is zeroed. */
7086e707 AD	115	extern bitset bitset_create PARAMS ((bitset_bindex, bitset_attrs));
7086e707 AD	116
613f5e1a AD	117	/* Return bitset type. */
	118	extern enum bitset_type bitset_type_get PARAMS ((bitset));
	119
6aa452a6 AD	120	/* Return bitset type name. */
	121	extern const char *bitset_type_name_get PARAMS ((bitset));
	122
613f5e1a	123	#if BITSET_INLINE
7086e707 AD	124	static inline void bitset_set PARAMS ((bitset, bitset_bindex));
	125	static inline void bitset_reset PARAMS ((bitset, bitset_bindex));
	126	static inline int bitset_test PARAMS ((bitset, bitset_bindex));
	127
	128	/* Set bit BITNO in bitset BSET. */
	129	static inline void bitset_set (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	136	if (offset < bset->b.csize)
e601ff27	137	bset->b.cdata[offset] \|= ((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	138	else
ef017502	139	BITSET_SET_ (bset, bitno);
7086e707 AD	140	}
	141
	142
	143	/* Reset bit BITNO in bitset BSET. */
	144	static inline void bitset_reset (bset, bitno)
	145	bitset bset;
	146	bitset_bindex bitno;
	147	{
	148	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	149	bitset_windex offset = index - bset->b.cindex;
613f5e1a	150
ef017502	151	if (offset < bset->b.csize)
e601ff27	152	bset->b.cdata[offset] &= ~((bitset_word) 1 << (bitno % BITSET_WORD_BITS));
7086e707	153	else
ef017502	154	BITSET_RESET_ (bset, bitno);
7086e707 AD	155	}
	156
	157
	158	/* Test bit BITNO in bitset BSET. */
	159	static inline int bitset_test (bset, bitno)
	160	bitset bset;
	161	bitset_bindex bitno;
	162	{
	163	bitset_windex index = bitno / BITSET_WORD_BITS;
ef017502	164	bitset_windex offset = index - bset->b.cindex;
613f5e1a	165
ef017502 AD	166	if (offset < bset->b.csize)
ef017502 AD	167	return (bset->b.cdata[offset] >> (bitno % BITSET_WORD_BITS)) & 1;
7086e707	168	else
ef017502	169	return BITSET_TEST_ (bset, bitno);
7086e707 AD	170	}
	171	#endif
	172
613f5e1a	173	#if ! BITSET_INLINE
7086e707 AD	174
	175	/* Set bit BITNO in bitset BSET. */
	176	#define bitset_set(bset, bitno) \
	177	do \
	178	{ \
	179	bitset_bindex _bitno = (bitno); \
	180	bitset_windex _index = _bitno / BITSET_WORD_BITS; \
ef017502	181	bitset_windex _offset = _index - (bset)->b.cindex; \
7086e707	182	\
ef017502	183	if (_offset < (bset)->b.csize) \
e601ff27 PE	184	(bset)->b.cdata[_offset] \|= \
e601ff27 PE	185	((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	186	else \
ef017502	187	BITSET_SET_ ((bset), _bitno); \
7086e707 AD	188	} while (0)
	189
	190
	191	/* Reset bit BITNO in bitset BSET. */
	192	#define bitset_reset(bset, bitno) \
	193	do \
	194	{ \
	195	bitset_bindex _bitno = (bitno); \
	196	bitset_windex _index = _bitno / BITSET_WORD_BITS; \
ef017502	197	bitset_windex _offset = _index - (bset)->b.cindex; \
7086e707	198	\
6aa452a6	199	if (_offset < (bset)->b.csize) \
0f9cd74f PE	200	(bset)->b.cdata[_offset] &= \
0f9cd74f PE	201	~((bitset_word) 1 << (_bitno % BITSET_WORD_BITS)); \
7086e707	202	else \
ef017502	203	BITSET_RESET_ ((bset), _bitno); \
7086e707 AD	204	} while (0)
	205
	206
	207	/* Test bit BITNO in bitset BSET. */
	208	#define bitset_test(bset, bitno) \
6aa452a6 AD	209	(((((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex) < (bset)->b.csize) \
	210	? ((bset)->b.cdata[(((bitno) / BITSET_WORD_BITS) - (bset)->b.cindex)] \
	211	>> ((bitno) % BITSET_WORD_BITS)) & 1 \
	212	: (unsigned int) BITSET_TEST_ ((bset), (bitno)))
7086e707 AD	213	#endif
7086e707 AD	214
7086e707	215
345cea78	216	/* Toggle bit BITNO in bitset BSET and return non-zero if now set. */
6aa452a6	217	#define bitset_toggle(bset, bitno) BITSET_TOGGLE_ (bset, bitno)
345cea78	218
6aa452a6 AD	219	/* Return size in bits of bitset SRC. */
	220	#define bitset_size(SRC) BITSET_SIZE_ (SRC)
	221
	222	/* Return number of bits set in bitset SRC. */
	223	#define bitset_count(SRC) BITSET_COUNT_ (SRC)
	224
	225
	226	/* Return SRC == 0. */
	227	#define bitset_empty_p(SRC) BITSET_EMPTY_P_ (SRC)
7086e707 AD	228
7086e707 AD	229	/* DST = ~0. */
6aa452a6	230	#define bitset_ones(DST) BITSET_ONES_ (DST)
7086e707	231
6aa452a6 AD	232	/* DST = 0. */
6aa452a6 AD	233	#define bitset_zero(DST) BITSET_ZERO_ (DST)
7086e707	234
7086e707	235
6aa452a6 AD	236
	237	/* DST = SRC. */
	238	#define bitset_copy(DST, SRC) BITSET_COPY_ (DST, SRC)
7086e707	239
ef017502	240	/* Return DST & SRC == 0. */
6aa452a6	241	#define bitset_disjoint_p(DST, SRC) BITSET_DISJOINT_P_ (DST, SRC)
ef017502	242
6aa452a6 AD	243	/* Return DST == SRC. */
6aa452a6 AD	244	#define bitset_equal_p(DST, SRC) BITSET_EQUAL_P_ (DST, SRC)
7086e707 AD	245
7086e707 AD	246	/* DST = ~SRC. */
6aa452a6 AD	247	#define bitset_not(DST, SRC) BITSET_NOT_ (DST, SRC)
	248
	249	/* Return DST == DST \| SRC. */
	250	#define bitset_subset_p(DST, SRC) BITSET_SUBSET_P_ (DST, SRC)
7086e707	251
6aa452a6 AD	252
	253
	254	/* DST = SRC1 & SRC2. */
	255	#define bitset_and(DST, SRC1, SRC2) BITSET_AND_ (DST, SRC1, SRC2)
7086e707 AD	256
7086e707 AD	257	/* DST = SRC1 & SRC2. Return non-zero if DST != SRC1 & SRC2. */
6aa452a6	258	#define bitset_and_cmp(DST, SRC1, SRC2) BITSET_AND_CMP_ (DST, SRC1, SRC2)
7086e707	259
6aa452a6 AD	260	/* DST = SRC1 & ~SRC2. */
6aa452a6 AD	261	#define bitset_andn(DST, SRC1, SRC2) BITSET_ANDN_ (DST, SRC1, SRC2)
7086e707 AD	262
7086e707 AD	263	/* DST = SRC1 & ~SRC2. Return non-zero if DST != SRC1 & ~SRC2. */
6aa452a6	264	#define bitset_andn_cmp(DST, SRC1, SRC2) BITSET_ANDN_CMP_ (DST, SRC1, SRC2)
7086e707	265
6aa452a6 AD	266	/* DST = SRC1 \| SRC2. */
	267	#define bitset_or(DST, SRC1, SRC2) BITSET_OR_ (DST, SRC1, SRC2)
	268
	269	/* DST = SRC1 \| SRC2. Return non-zero if DST != SRC1 \| SRC2. */
	270	#define bitset_or_cmp(DST, SRC1, SRC2) BITSET_OR_CMP_ (DST, SRC1, SRC2)
	271
	272	/* DST = SRC1 ^ SRC2. */
	273	#define bitset_xor(DST, SRC1, SRC2) BITSET_XOR_ (DST, SRC1, SRC2)
	274
	275	/* DST = SRC1 ^ SRC2. Return non-zero if DST != SRC1 ^ SRC2. */
	276	#define bitset_xor_cmp(DST, SRC1, SRC2) BITSET_XOR_CMP_ (DST, SRC1, SRC2)
	277
	278
	279
	280	/* DST = (SRC1 & SRC2) \| SRC3. */
	281	#define bitset_and_or(DST, SRC1, SRC2, SRC3) \
	282	BITSET_AND_OR_ (DST, SRC1, SRC2, SRC3)
7086e707 AD	283
	284	/* DST = (SRC1 & SRC2) \| SRC3. Return non-zero if
	285	DST != (SRC1 & SRC2) \| SRC3. */
6aa452a6 AD	286	#define bitset_and_or_cmp(DST, SRC1, SRC2, SRC3) \
	287	BITSET_AND_OR_CMP_ (DST, SRC1, SRC2, SRC3)
	288
	289	/* DST = (SRC1 & ~SRC2) \| SRC3. */
	290	#define bitset_andn_or(DST, SRC1, SRC2, SRC3) \
	291	BITSET_ANDN_OR_ (DST, SRC1, SRC2, SRC3)
7086e707 AD	292
	293	/* DST = (SRC1 & ~SRC2) \| SRC3. Return non-zero if
	294	DST != (SRC1 & ~SRC2) \| SRC3. */
6aa452a6 AD	295	#define bitset_andn_or_cmp(DST, SRC1, SRC2, SRC3) \
6aa452a6 AD	296	BITSET_ANDN_OR_CMP_ (DST, SRC1, SRC2, SRC3)
7086e707	297
6aa452a6 AD	298	/* DST = (SRC1 \| SRC2) & SRC3. */
	299	#define bitset_or_and(DST, SRC1, SRC2, SRC3)\
	300	BITSET_OR_AND_ (DST, SRC1, SRC2, SRC3)
7086e707	301
6aa452a6 AD	302	/* DST = (SRC1 \| SRC2) & SRC3. Return non-zero if
	303	DST != (SRC1 \| SRC2) & SRC3. */
	304	#define bitset_or_and_cmp(DST, SRC1, SRC2, SRC3)\
	305	BITSET_OR_AND_CMP_ (DST, SRC1, SRC2, SRC3)
345cea78	306
613f5e1a	307	/* Find list of up to NUM bits set in BSET starting from and including
7086e707 AD	308	NEXT. Return with actual number of bits found and with NEXT
7086e707 AD	309	indicating where search stopped. */
7086e707	310	#define bitset_list(BSET, LIST, NUM, NEXT) \
6aa452a6	311	BITSET_LIST_ (BSET, LIST, NUM, NEXT)
7086e707 AD	312
	313	/* Find reverse list of up to NUM bits set in BSET starting from and
	314	including NEXT. Return with actual number of bits found and with
	315	NEXT indicating where search stopped. /
6aa452a6 AD	316	#define bitset_list_reverse(BSET, LIST, NUM, NEXT) \
	317	BITSET_LIST_REVERSE_ (BSET, LIST, NUM, NEXT)
	318
7086e707	319
47c8386f PE	320	/* Find next set bit. */
	321	extern bitset_bindex bitset_next PARAMS ((bitset, bitset_bindex));
	322
	323	/* Find previous set bit. */
	324	extern bitset_bindex bitset_prev PARAMS ((bitset, bitset_bindex));
	325
7086e707	326	/* Find first set bit. */
808a5918	327	extern bitset_bindex bitset_first PARAMS ((bitset));
7086e707 AD	328
7086e707 AD	329	/* Find last set bit. */
808a5918	330	extern bitset_bindex bitset_last PARAMS ((bitset));
7086e707	331
47c8386f PE	332	/* Return nonzero if this is the only set bit. */
	333	extern int bitset_only_set_p PARAMS ((bitset, bitset_bindex));
	334
7086e707 AD	335	/* Dump bitset. */
	336	extern void bitset_dump PARAMS ((FILE *, bitset));
	337
613f5e1a	338	/* Loop over all elements of BSET, starting with MIN, setting BIT
6aa452a6 AD	339	to the index of each set bit. For example, the following will print
	340	the bits set in a bitset:
	341
	342	bitset_bindex i;
	343	bitset_iterator iter;
	344
	345	bitset_zero (dst);
	346	BITSET_FOR_EACH (iter, src, i, 0)
	347	{
	348	printf ("%ld ", i);
	349	};
	350	*/
613f5e1a AD	351	#define BITSET_FOR_EACH(ITER, BSET, BIT, MIN) \
	352	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
	353	(ITER.num == BITSET_LIST_SIZE) \
	354	&& (ITER.num = bitset_list (BSET, ITER.list, \
	355	BITSET_LIST_SIZE, &ITER.next));) \
	356	for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
7086e707 AD	357
	358
	359	/* Loop over all elements of BSET, in reverse order starting with
6aa452a6 AD	360	MIN, setting BIT to the index of each set bit. For example, the
	361	following will print the bits set in a bitset in reverse order:
	362
	363	bitset_bindex i;
	364	bitset_iterator iter;
	365
	366	bitset_zero (dst);
	367	BITSET_FOR_EACH_REVERSE (iter, src, i, 0)
	368	{
	369	printf ("%ld ", i);
	370	};
	371	*/
613f5e1a AD	372	#define BITSET_FOR_EACH_REVERSE(ITER, BSET, BIT, MIN) \
	373	for (ITER.next = (MIN), ITER.num = BITSET_LIST_SIZE; \
	374	(ITER.num == BITSET_LIST_SIZE) \
	375	&& (ITER.num = bitset_list_reverse (BSET, ITER.list, \
	376	BITSET_LIST_SIZE, &ITER.next));) \
	377	for (ITER.i = 0; (BIT) = ITER.list[ITER.i], ITER.i < ITER.num; ITER.i++)
7086e707 AD	378
7086e707 AD	379
ef017502	380	/* Define set operations in terms of logical operations. */
7086e707	381
6aa452a6 AD	382	#define bitset_diff(DST, SRC1, SRC2) bitset_andn (DST, SRC1, SRC2)
6aa452a6 AD	383	#define bitset_diff_cmp(DST, SRC1, SRC2) bitset_andn_cmp (DST, SRC1, SRC2)
7086e707	384
6aa452a6 AD	385	#define bitset_intersection(DST, SRC1, SRC2) bitset_and (DST, SRC1, SRC2)
6aa452a6 AD	386	#define bitset_intersection_cmp(DST, SRC1, SRC2) bitset_and_cmp (DST, SRC1, SRC2)
7086e707	387
6aa452a6 AD	388	#define bitset_union(DST, SRC1, SRC2) bitset_or (DST, SRC1, SRC2)
6aa452a6 AD	389	#define bitset_union_cmp(DST, SRC1, SRC2) bitset_or_cmp (DST, SRC1, SRC2)
7086e707	390
6aa452a6 AD	391	/* Symmetrical difference. */
	392	#define bitset_symdiff(DST, SRC1, SRC2) bitset_xor (DST, SRC1, SRC2)
	393	#define bitset_symdiff_cmp(DST, SRC1, SRC2) bitset_xor_cmp (DST, SRC1, SRC2)
	394
	395	/* Union of difference. */
7086e707	396	#define bitset_diff_union(DST, SRC1, SRC2, SRC3) \
613f5e1a	397	bitset_andn_or (DST, SRC1, SRC2, SRC3)
6aa452a6 AD	398	#define bitset_diff_union_cmp(DST, SRC1, SRC2, SRC3) \
	399	bitset_andn_or_cmp (DST, SRC1, SRC2, SRC3)
	400
ef017502	401
7086e707 AD	402
	403	/* Release any memory tied up with bitsets. */
	404	extern void bitset_release_memory PARAMS ((void));
	405
613f5e1a AD	406	/* Enable bitset stats gathering. */
	407	extern void bitset_stats_enable PARAMS ((void));
	408
	409	/* Disable bitset stats gathering. */
	410	extern void bitset_stats_disable PARAMS ((void));
	411
	412	/* Read bitset stats file of accummulated stats. */
	413	void bitset_stats_read PARAMS ((const char *filename));
	414
	415	/* Write bitset stats file of accummulated stats. */
	416	void bitset_stats_write PARAMS ((const char *filename));
7086e707 AD	417
	418	/* Dump bitset stats. */
	419	extern void bitset_stats_dump PARAMS ((FILE *));
	420
	421	/* Function to debug bitset from debugger. */
	422	extern void debug_bitset PARAMS ((bitset));
	423
	424	/* Function to debug bitset stats from debugger. */
	425	extern void debug_bitset_stats PARAMS ((void));
	426
7086e707	427	#endif /* _BITSET_H */
613f5e1a	428