[bison.git] / lib / bitset.h

/* Generic bitsets.

   Copyright (C) 2002-2004, 2009-2012 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 3 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, see <http://www.gnu.org/licenses/>.  */

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