1 /* bitset.h - bitset decls
2  *
3  ****************************************************************
4  * Copyright (C) 1998, 2000 Thomas Lord
5  *
6  * See the file "COPYING" for further information about
7  * the copyright and warranty status of this work.
8  */
9 
10 
11 
12 #include "hackerlab/os/limits.h"
13 #include "hackerlab/mem/alloc-limits.h"
14 
15 
16 #ifndef INCLUDE__BITSETS__BITSET_H
17 #define INCLUDE__BITSETS__BITSET_H
18 
19 /************************************************************************
20  *(h2 "Bitset Types and Macros")
21  *
22  */
23 
24 /*(c bit_t :category type)
25  * typedef long bit_t;
26  *
27  * Values of type `bit_t' represent a bit address within
28  * a bitset.  The address of the first bit is 0.
29  *
30  * `bit_t' is a signed integer type.  Some functions which return a
31  * bit address use the value -1 to indicate `no such bit'.
32  *
33  */
34 typedef long bit_t;		/* A bit address. */
35 
36 /*end-insert
37  */
38 
39 /*(c bitset_subset :category type)
40  * typedef unsigned long bitset_subset;
41  *
42  * A fragment of a bitset.  A bitset is an array of these.
43  */
44 typedef unsigned long bitset_subset;
45 
46 /*(c bitset :category type)
47  * typedef bitset_subset * bitset;
48  *
49  * A packed array of bits.
50  */
51 typedef bitset_subset * bitset;
52 
53 
54 /*c bits_per_subset :category macro)
55  * #define bits_per_subset	(8 * sizeof (bitset_subset))
56  *
57  * The number of bits in one value of type `subset'.  The
58  * implementation presumes that `sizeof (bitset_subset)' is a power of two.
59  */
60 #if ULONG_MAX == 0xffffffffUL
61 #define bits_per_subset		(32)
62 #elif ULONG_MAX == ((0xffffffffUL << 32) + 0xffffffffUL)
63 #define bits_per_subset		(64)
64 #else
65 #error "odd ULONG_MAX in bitset.h"
66 #endif
67 
68 /*c bitset_subset_mask :category macro)
69  * #define bitset_subset_mask		(bits_per_subset - 1)
70  *
71  * A bitmask useful for finding the bit position within a subset
72  * of a bitset element.
73  */
74 #define bitset_subset_mask		(bits_per_subset - 1)
75 
76 /*(c bitset_which_subset :category macro)
77  * #define bitset_which_subset(N)  ((N) / bits_per_subset)
78  *
79  * A macro useful for finding the subset index within a bitset of a
80  * particular bitset element.  The subset containing bit `N' bit
81  * bitset `B' is:
82  *
83  * 	B[bitset_which_subset(N)]
84  */
85 #define bitset_which_subset(N)  ((N) / bits_per_subset)
86 
87 
88 /*(c bitset_subset_offset :category macro)
89  * #define bitset_subset_offset(N) \
90  *	  (((N) / bits_per_subset) * bits_per_subset)
91  *
92  * A macro useful for finding a subset offset within a bitset of the
93  * subset containing a bitset element.  Bit 0 (the low order bit) of
94  * the subset containing bit `N' is the bit whose bit address is
95  * `bitset_subset_offset(N)'.
96  */
97 #define bitset_subset_offset(N)  (((N) / bits_per_subset) * bits_per_subset)
98 
99 /*(c bitset_which_bit :category macro)
100  * #define bitset_which_bit(N)  ((N) & bitset_subset_mask)
101  *
102  * The bit number of a bitset index within its subset.
103  */
104 #define bitset_which_bit(N)  ((N) & bitset_subset_mask)
105 
106 
107 /*c bitset_bit_mask :category macro)
108  * #define bitset_bit_mask(N) \
109  *   ((~(bitset_subset)0L) >> (bits_per_subset - bitset_which_bit (N)))
110  *
111  * A bitmask for all bits up to (but not including) element `N' of the
112  * subset containing element `N'.
113  */
114 #define bitset_bit_mask(N)   ((~(bitset_subset)0L) >> (bits_per_subset - bitset_which_bit (N)))
115 
116 
117 /*(c bitset_numb_subsets :category macro)
118  * #define bitset_numb_subsets(N)
119  *
120  * As a function:
121  *
122  * 	bit_t bitset_numb_subsets (bit_t n);
123  *
124  * Return the number of values of type `subset' necessary to represent
125  * a bitset with `n' elements. Because this is a macro, it can be used
126  * in a declaration:
127  *
128  *	{
129  *	  // declare a bitset that can hold 12 elements:
130  *	  //
131  *	  bitset_subset options_set [bitset_numb_subsets(12)];
132  *	}
133  */
134 #define bitset_numb_subsets(n) (((n) + bits_per_subset - 1) / bits_per_subset)
135 
136 /*(c sizeof_bitset :category macro)
137  * #define sizeof_bitset(N)
138  *
139  * As a function:
140  *
141  * 	size_t sizeof_bitset (bit_t n);
142  *
143  * Return the size, in bytes, of a bitset large enough to
144  * hold `n' elements:
145  *
146  *	// allocate a bitset that can hold 12 elements:
147  *	//
148  *	options_set = (bitset)must_malloc (sizeof_bitset (12));
149  */
150 #define sizeof_bitset(n) (bitset_numb_subsets(n) * sizeof(bitset_subset))
151 
152 
153 
154 /* automatically generated __STDC__ prototypes */
155 extern bitset bitset_alloc (alloc_limits limits, bit_t size);
156 extern void bitset_free (alloc_limits limits, bitset a);
157 extern bitset bitset_dup (alloc_limits limits, bit_t size, bitset a);
158 extern bitset bitset_realloc (alloc_limits limits,
159                               bit_t new_size,
160                               bit_t old_size,
161                               bitset a);
162 extern int bitset_is_member (bitset b, bit_t n);
163 extern int bitset_is_equal (bit_t size, bitset a, bitset b);
164 extern int bitset_is_subset (bit_t size, bitset a, bitset b);
165 extern int bitset_is_empty (bit_t size, bitset a);
166 extern int bitset_is_empty_range (bitset a, bit_t from, bit_t to);
167 extern int bitset_is_full (bit_t size, bitset a);
168 extern int bitset_is_full_range (bitset a, bit_t from, bit_t to);
169 extern void bitset_adjoin (bitset b, bit_t n);
170 extern void bitset_remove (bitset b, bit_t n);
171 extern void bitset_toggle (bitset b, bit_t n);
172 extern void bitset_clear (bit_t size, bitset b);
173 extern void bitset_clear_range (bitset b, bit_t from, bit_t to);
174 extern void bitset_fill (bit_t size, bitset b);
175 extern void bitset_fill_range (bitset b, bit_t from, bit_t to);
176 extern void bitset_complement (bit_t size, bitset b);
177 extern void bitset_assign (bit_t size, bitset a, bitset b);
178 extern void bitset_union (bit_t size, bitset a, bitset b);
179 extern void bitset_intersection (bit_t size, bitset a, bitset b);
180 extern void bitset_difference (bit_t size, bitset a, bitset b);
181 extern void bitset_revdifference (bit_t size, bitset a, bitset b);
182 extern void bitset_xor (bit_t size, bitset a, bitset b);
183 extern bit_t bitset_population (bit_t size, bitset a);
184 extern bit_t bitset_population_range (bitset a, bit_t from, bit_t to);
185 extern bit_t bitset_ffs (bit_t size, bitset b);
186 extern bit_t bitset_ffs_range (bitset b, bit_t from, bit_t to);
187 extern bit_t bitset_ffc (bit_t size, bitset b);
188 extern bit_t bitset_ffc_range (bitset b, bit_t from, bit_t to);
189 #endif  /* INCLUDE__BITSETS__BITSET_H */
190