[bison.git] / lib / bitset.h

/* Generic bitsets.
   Copyright (C) 2002, 2003, 2004 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., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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>

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

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

typedef unsigned int bitset_attrs;

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

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

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

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

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

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

};


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


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

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

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

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

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

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

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

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

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

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


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

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


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

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


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

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


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

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

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

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


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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

   bitset_bindex i;
   bitset_iterator iter;

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


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

   bitset_bindex i;
   bitset_iterator iter;

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


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

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

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

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

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

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


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

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

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

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

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

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

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

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

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