1 /*
2 * bitset.h
3 * Plain old bitset data type.
4 *
5 * Copyright (C) 2001-2017 Cosmin Truta.
6 *
7 * This software is distributed under the zlib license.
8 * Please see the accompanying LICENSE file.
9 */
10
11 #ifndef OPNG_BITSET_H_
12 #define OPNG_BITSET_H_
13
14 #include <limits.h>
15 #include <stddef.h>
16
17
18 #ifdef __cplusplus
19 extern "C" {
20 #endif
21
22
23 /*
24 * The bitset type.
25 */
26 typedef unsigned int opng_bitset_t;
27
28
29 /*
30 * Bitset constants.
31 */
32 #define OPNG_BITSET_EMPTY 0U
33 #define OPNG_BITSET_FULL (~0U)
34
35
36 /*
37 * The size operator (not restricted to opng_bitset_t).
38 */
39 #define OPNG_BITSIZEOF(object) (sizeof(object) * CHAR_BIT)
40
41
42 /*
43 * Bitset element limits.
44 */
45 enum
46 {
47 OPNG_BITSET_ELT_MIN = 0,
48 OPNG_BITSET_ELT_MAX = (int)(OPNG_BITSIZEOF(opng_bitset_t) - 1)
49 };
50
51
52 /*
53 * Direct bitset access methods.
54 */
55 #ifdef __cplusplus
56
57 inline int
opng_bitset_test(opng_bitset_t set,int elt)58 opng_bitset_test(opng_bitset_t set, int elt)
59 {
60 return (set & (1U << elt)) != 0;
61 }
62
63 inline void
opng_bitset_set(opng_bitset_t * set,int elt)64 opng_bitset_set(opng_bitset_t *set, int elt)
65 {
66 *set |= (1U << elt);
67 }
68
69 inline void
opng_bitset_reset(opng_bitset_t * set,int elt)70 opng_bitset_reset(opng_bitset_t *set, int elt)
71 {
72 *set &= ~(1U << elt);
73 }
74
75 inline void
opng_bitset_flip(opng_bitset_t * set,int elt)76 opng_bitset_flip(opng_bitset_t *set, int elt)
77 {
78 *set ^= (1U << elt);
79 }
80
81 inline opng_bitset_t
opng_bitset__range__(int start_elt,int stop_elt)82 opng_bitset__range__(int start_elt, int stop_elt)
83 {
84 return ((1U << (stop_elt - start_elt) << 1) - 1) << start_elt;
85 }
86
87 inline int
opng_bitset_test_all_in_range(opng_bitset_t set,int start_elt,int stop_elt)88 opng_bitset_test_all_in_range(opng_bitset_t set, int start_elt, int stop_elt)
89 {
90 return (start_elt <= stop_elt) ?
91 ((~set & opng_bitset__range__(start_elt, stop_elt)) == 0) :
92 1;
93 }
94
95 inline int
opng_bitset_test_any_in_range(opng_bitset_t set,int start_elt,int stop_elt)96 opng_bitset_test_any_in_range(opng_bitset_t set, int start_elt, int stop_elt)
97 {
98 return (start_elt <= stop_elt) ?
99 ((set & opng_bitset__range__(start_elt, stop_elt)) != 0) :
100 0;
101 }
102
103 inline void
opng_bitset_set_range(opng_bitset_t * set,int start_elt,int stop_elt)104 opng_bitset_set_range(opng_bitset_t *set, int start_elt, int stop_elt)
105 {
106 if (start_elt <= stop_elt)
107 *set |= opng_bitset__range__(start_elt, stop_elt);
108 }
109
110 inline void
opng_bitset_reset_range(opng_bitset_t * set,int start_elt,int stop_elt)111 opng_bitset_reset_range(opng_bitset_t *set, int start_elt, int stop_elt)
112 {
113 if (start_elt <= stop_elt)
114 *set &= ~opng_bitset__range__(start_elt, stop_elt);
115 }
116
117 inline void
opng_bitset_flip_range(opng_bitset_t * set,int start_elt,int stop_elt)118 opng_bitset_flip_range(opng_bitset_t *set, int start_elt, int stop_elt)
119 {
120 if (start_elt <= stop_elt)
121 *set ^= opng_bitset__range__(start_elt, stop_elt);
122 }
123
124 #else /* !__cplusplus */
125
126 #define opng_bitset_test(set, elt) \
127 (((set) & (1U << (elt))) != 0)
128
129 #define opng_bitset_set(set, elt) \
130 (*(set) |= (1U << (elt)))
131
132 #define opng_bitset_reset(set, elt) \
133 (*(set) &= ~(1U << (elt)))
134
135 #define opng_bitset_flip(set, elt) \
136 (*(set) ^= (1U << (elt)))
137
138 #define opng_bitset__range__(start_elt, stop_elt) \
139 (((1U << ((stop_elt) - (start_elt)) << 1) - 1) << (start_elt))
140
141 #define opng_bitset_test_all_in_range(set, start_elt, stop_elt) \
142 (((start_elt) <= (stop_elt)) ? \
143 (~(set) & opng_bitset__range__(start_elt, stop_elt)) == 0 : \
144 1)
145
146 #define opng_bitset_test_any_in_range(set, start_elt, stop_elt) \
147 (((start_elt) <= (stop_elt)) ? \
148 ((set) & opng_bitset__range__(start_elt, stop_elt)) != 0 : \
149 0)
150
151 #define opng_bitset_set_range(set, start_elt, stop_elt) \
152 (*(set) |= ((start_elt) <= (stop_elt)) ? \
153 opng_bitset__range__(start_elt, stop_elt) : \
154 0U)
155
156 #define opng_bitset_reset_range(set, start_elt, stop_elt) \
157 (*(set) &= ((start_elt) <= (stop_elt)) ? \
158 ~opng_bitset__range__(start_elt, stop_elt) : \
159 ~0U)
160
161 #define opng_bitset_flip_range(set, start_elt, stop_elt) \
162 (*(set) ^= ((start_elt) <= (stop_elt)) ? \
163 opng_bitset__range__(start_elt, stop_elt) : \
164 0U)
165
166 #endif /* __cplusplus */
167
168
169 /*
170 * Counts the number of elements in a bitset.
171 *
172 * The function returns the number of bits set to 1.
173 */
174 unsigned int
175 opng_bitset_count(opng_bitset_t set);
176
177 /*
178 * Finds the first element in a bitset.
179 *
180 * The function returns the position of the first bit set to 1,
181 * or -1 if all bits are set to 0.
182 */
183 int
184 opng_bitset_find_first(opng_bitset_t set);
185
186 /*
187 * Finds the next element in a bitset.
188 *
189 * The function returns the position of the next bit set to 1,
190 * or -1 if all the following bits are set to 0.
191 */
192 int
193 opng_bitset_find_next(opng_bitset_t set, int elt);
194
195 /*
196 * Finds the last element in a bitset.
197 *
198 * The function returns the position of the last bit set to 1,
199 * or -1 if all bits are set to 0.
200 */
201 int
202 opng_bitset_find_last(opng_bitset_t set);
203
204 /*
205 * Finds the previous element in a bitset.
206 *
207 * The function returns the position of the previous bit set to 1,
208 * or -1 if all the preceding bits are set to 0.
209 */
210 int
211 opng_bitset_find_prev(opng_bitset_t set, int elt);
212
213 /*
214 * Parses a rangeset string and converts the result to a bitset.
215 *
216 * A rangeset string is an arbitrary sequence of non-negative integers ("N")
217 * and ranges ("M-N" or "M-"), represented in base 10, and separated by comma
218 * or semicolon characters. Whitespace is allowed around lexical elements,
219 * and is ignored.
220 *
221 * Here are a few examples, assuming the input mask is 0xffff:
222 * "" => 0000000000000000
223 * "0" => 0000000000000001
224 * "0,3,5-7" => 0000000011101001
225 * "0-3,5,7-" => 1111111110101111
226 * "7-,5" => 1111111110100000
227 * "7-7" => 0000000010000000
228 * "7-5" => 1111111111111111, range error
229 * "99" => 1111111111111111, range error
230 * "1-2-3" => 0000000000000000, invalid input error
231 *
232 * On success, the function sets the output value to the converted bitset.
233 * If the input is well-formed, but contains elements or ranges that are not
234 * representable within the given mask, the function sets errno to ERANGE,
235 * and sets the output value to BITSET_FULL.
236 * If the input is ill-formed, the function sets errno to EINVAL, and sets
237 * the output value to BITSET_EMPTY.
238 *
239 * The function returns 0 on success, or -1 on error.
240 */
241 int
242 opng_strparse_rangeset_to_bitset(opng_bitset_t *out_set,
243 const char *rangeset_str,
244 opng_bitset_t mask_set);
245
246 /*
247 * Formats a bitset using the rangeset string representation.
248 *
249 * The function returns the length of the rangeset string representation.
250 * Upon return, if the output buffer is large enough, it shall contain the
251 * rangeset string. Otherwise, the buffer shall remain intact.
252 */
253 size_t
254 opng_strformat_bitset_as_rangeset(char *out_buf,
255 size_t out_buf_size,
256 opng_bitset_t bitset);
257
258 /*
259 * TODO:
260 * opng_wcsparse_rangeset_to_bitset
261 * opng_wcsformat_bitset_as_rangeset
262 */
263
264
265 #ifdef __cplusplus
266 } /* extern "C" */
267 #endif
268
269
270 #endif /* OPNG_BITSET_H_ */
271