[bison.git] / lib / bitset.h

/* Generic bitsets.
   Copyright (C) 2002, 2003 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"

/* obstack.h tries to be portable to K&R compilers, but its
   __INT_TO_PTR macro generates diagnostics on compilers like Tru64 cc
   that define __STDC__ to 0 when not in strict ANSI mode.  The bitset
   code assumes C89 or later, so it can avoid these glitches by
   defining __INT_TO_PTR appropriately for C89 or later.  */
#ifndef __INT_TO_PTR
# define __INT_TO_PTR(P) ((void *) ((P) + (char *) 0))
#endif
#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;	        /* 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 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));


/* 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 PARAMS ((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 PARAMS ((bitset, bitset_bindex));

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