1/*-
2 * SPDX-License-Identifier: BSD-2-Clause
3 *
4 * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
5 * All rights reserved.
6 *
7 * Copyright (c) 2008 Nokia Corporation
8 * All rights reserved.
9 *
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
12 * are met:
13 * 1. Redistributions of source code must retain the above copyright
14 * notice unmodified, this list of conditions, and the following
15 * disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 * notice, this list of conditions and the following disclaimer in the
18 * documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
21 * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
23 * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
24 * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
25 * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
29 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#ifndef _SYS_BITSET_H_
33#define _SYS_BITSET_H_
34
35/*
36 * Whether expr is both constant and true. Result is itself constant.
37 * Used to enable optimizations for sets with a known small size.
38 */
39#define __constexpr_cond(expr) (__builtin_constant_p((expr)) && (expr))
40
41#define __bitset_mask(_s, n) \
42 (1UL << (__constexpr_cond(__bitset_words((_s)) == 1) ? \
43 (__size_t)(n) : ((n) % _BITSET_BITS)))
44
45#define __bitset_word(_s, n) \
46 (__constexpr_cond(__bitset_words((_s)) == 1) ? \
47 0 : ((n) / _BITSET_BITS))
48
49#define __BIT_CLR(_s, n, p) \
50 ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
51
52#define __BIT_COPY(_s, f, t) (void)(*(t) = *(f))
53
54#define __BIT_ISSET(_s, n, p) \
55 ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
56
57#define __BIT_SET(_s, n, p) \
58 ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
59
60#define __BIT_ZERO(_s, p) do { \
61 __size_t __i; \
62 for (__i = 0; __i < __bitset_words((_s)); __i++) \
63 (p)->__bits[__i] = 0L; \
64} while (0)
65
66#define __BIT_FILL(_s, p) do { \
67 __size_t __i; \
68 for (__i = 0; __i < __bitset_words((_s)); __i++) \
69 (p)->__bits[__i] = -1L; \
70} while (0)
71
72#define __BIT_SETOF(_s, n, p) do { \
73 __BIT_ZERO(_s, p); \
74 (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \
75} while (0)
76
77/* Is p empty. */
78#define __BIT_EMPTY(_s, p) __extension__ ({ \
79 __size_t __i; \
80 for (__i = 0; __i < __bitset_words((_s)); __i++) \
81 if ((p)->__bits[__i]) \
82 break; \
83 __i == __bitset_words((_s)); \
84})
85
86/* Is p full set. */
87#define __BIT_ISFULLSET(_s, p) __extension__ ({ \
88 __size_t __i; \
89 for (__i = 0; __i < __bitset_words((_s)); __i++) \
90 if ((p)->__bits[__i] != (long)-1) \
91 break; \
92 __i == __bitset_words((_s)); \
93})
94
95/* Is c a subset of p. */
96#define __BIT_SUBSET(_s, p, c) __extension__ ({ \
97 __size_t __i; \
98 for (__i = 0; __i < __bitset_words((_s)); __i++) \
99 if (((c)->__bits[__i] & \
100 (p)->__bits[__i]) != \
101 (c)->__bits[__i]) \
102 break; \
103 __i == __bitset_words((_s)); \
104})
105
106/* Are there any common bits between b & c? */
107#define __BIT_OVERLAP(_s, p, c) __extension__ ({ \
108 __size_t __i; \
109 for (__i = 0; __i < __bitset_words((_s)); __i++) \
110 if (((c)->__bits[__i] & \
111 (p)->__bits[__i]) != 0) \
112 break; \
113 __i != __bitset_words((_s)); \
114})
115
116/* Compare two sets, returns 0 if equal 1 otherwise. */
117#define __BIT_CMP(_s, p, c) __extension__ ({ \
118 __size_t __i; \
119 for (__i = 0; __i < __bitset_words((_s)); __i++) \
120 if (((c)->__bits[__i] != \
121 (p)->__bits[__i])) \
122 break; \
123 __i != __bitset_words((_s)); \
124})
125
126#define __BIT_OR(_s, d, s) do { \
127 __size_t __i; \
128 for (__i = 0; __i < __bitset_words((_s)); __i++) \
129 (d)->__bits[__i] |= (s)->__bits[__i]; \
130} while (0)
131
132#define __BIT_OR2(_s, d, s1, s2) do { \
133 __size_t __i; \
134 for (__i = 0; __i < __bitset_words((_s)); __i++) \
135 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
136} while (0)
137
138#define __BIT_ORNOT(_s, d, s) do { \
139 __size_t __i; \
140 for (__i = 0; __i < __bitset_words((_s)); __i++) \
141 (d)->__bits[__i] |= ~(s)->__bits[__i]; \
142} while (0)
143
144#define __BIT_ORNOT2(_s, d, s1, s2) do { \
145 __size_t __i; \
146 for (__i = 0; __i < __bitset_words((_s)); __i++) \
147 (d)->__bits[__i] = (s1)->__bits[__i] | ~(s2)->__bits[__i];\
148} while (0)
149
150#define __BIT_AND(_s, d, s) do { \
151 __size_t __i; \
152 for (__i = 0; __i < __bitset_words((_s)); __i++) \
153 (d)->__bits[__i] &= (s)->__bits[__i]; \
154} while (0)
155
156#define __BIT_AND2(_s, d, s1, s2) do { \
157 __size_t __i; \
158 for (__i = 0; __i < __bitset_words((_s)); __i++) \
159 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
160} while (0)
161
162#define __BIT_ANDNOT(_s, d, s) do { \
163 __size_t __i; \
164 for (__i = 0; __i < __bitset_words((_s)); __i++) \
165 (d)->__bits[__i] &= ~(s)->__bits[__i]; \
166} while (0)
167
168#define __BIT_ANDNOT2(_s, d, s1, s2) do { \
169 __size_t __i; \
170 for (__i = 0; __i < __bitset_words((_s)); __i++) \
171 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
172} while (0)
173
174#define __BIT_XOR(_s, d, s) do { \
175 __size_t __i; \
176 for (__i = 0; __i < __bitset_words((_s)); __i++) \
177 (d)->__bits[__i] ^= (s)->__bits[__i]; \
178} while (0)
179
180#define __BIT_XOR2(_s, d, s1, s2) do { \
181 __size_t __i; \
182 for (__i = 0; __i < __bitset_words((_s)); __i++) \
183 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
184} while (0)
185
186/*
187 * Note, the atomic(9) API is not consistent between clear/set and
188 * testandclear/testandset in whether the value argument is a mask
189 * or a bit index.
190 */
191
192#define __BIT_CLR_ATOMIC(_s, n, p) \
193 atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \
194 __bitset_mask((_s), n))
195
196#define __BIT_SET_ATOMIC(_s, n, p) \
197 atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \
198 __bitset_mask((_s), n))
199
200#define __BIT_SET_ATOMIC_ACQ(_s, n, p) \
201 atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \
202 __bitset_mask((_s), n))
203
204#define __BIT_TEST_CLR_ATOMIC(_s, n, p) \
205 (atomic_testandclear_long( \
206 &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
207
208#define __BIT_TEST_SET_ATOMIC(_s, n, p) \
209 (atomic_testandset_long( \
210 &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
211
212/* Convenience functions catering special cases. */
213#define __BIT_AND_ATOMIC(_s, d, s) do { \
214 __size_t __i; \
215 for (__i = 0; __i < __bitset_words((_s)); __i++) \
216 atomic_clear_long(&(d)->__bits[__i], \
217 ~(s)->__bits[__i]); \
218} while (0)
219
220#define __BIT_OR_ATOMIC(_s, d, s) do { \
221 __size_t __i; \
222 for (__i = 0; __i < __bitset_words((_s)); __i++) \
223 atomic_set_long(&(d)->__bits[__i], \
224 (s)->__bits[__i]); \
225} while (0)
226
227#define __BIT_COPY_STORE_REL(_s, f, t) do { \
228 __size_t __i; \
229 for (__i = 0; __i < __bitset_words((_s)); __i++) \
230 atomic_store_rel_long(&(t)->__bits[__i], \
231 (f)->__bits[__i]); \
232} while (0)
233
234/*
235 * 'start' is a 0-based bit index. By contrast, and as for ffs(), the returned
236 * index is 1-based, 0 being reserved to indicate that no bits are set.
237 */
238#define __BIT_FFS_AT(_s, p, start) __extension__ ({ \
239 __size_t __i; \
240 long __bit, __mask; \
241 \
242 __mask = ~0UL << ((start) % _BITSET_BITS); \
243 __bit = 0; \
244 for (__i = __bitset_word((_s), (start)); \
245 __i < __bitset_words((_s)); \
246 __i++) { \
247 if (((p)->__bits[__i] & __mask) != 0) { \
248 __bit = ffsl((p)->__bits[__i] & __mask); \
249 __bit += __i * _BITSET_BITS; \
250 break; \
251 } \
252 __mask = ~0UL; \
253 } \
254 __bit; \
255})
256
257#define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0)
258
259#define __BIT_FLS(_s, p) __extension__ ({ \
260 __size_t __i; \
261 long __bit; \
262 \
263 __bit = 0; \
264 for (__i = __bitset_words((_s)); __i > 0; __i--) { \
265 if ((p)->__bits[__i - 1] != 0) { \
266 __bit = flsl((p)->__bits[__i - 1]); \
267 __bit += (__i - 1) * _BITSET_BITS; \
268 break; \
269 } \
270 } \
271 __bit; \
272})
273
274#define __BIT_COUNT(_s, p) __extension__ ({ \
275 __size_t __i; \
276 long __count; \
277 \
278 __count = 0; \
279 for (__i = 0; __i < __bitset_words((_s)); __i++) \
280 __count += __bitcountl((p)->__bits[__i]); \
281 __count; \
282})
283
284#define __BIT_FOREACH_ADVANCE(_s, i, p, op) __extension__ ({ \
285 int __found; \
286 for (;;) { \
287 if (__bits != 0) { \
288 int __bit = ffsl(__bits) - 1; \
289 __bits &= ~(1ul << __bit); \
290 (i) = __i * _BITSET_BITS + __bit; \
291 __found = 1; \
292 break; \
293 } \
294 if (++__i == __bitset_words(_s)) { \
295 __found = 0; \
296 break; \
297 } \
298 __bits = op((p)->__bits[__i]); \
299 } \
300 __found != 0; \
301})
302
303/*
304 * Non-destructively loop over all set or clear bits in the set.
305 */
306#define __BIT_FOREACH(_s, i, p, op) \
307 for (long __i = -1, __bits = 0; \
308 __BIT_FOREACH_ADVANCE(_s, i, p, op); )
309
310#define __BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH(_s, i, p, )
311#define __BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH(_s, i, p, ~)
312
313#define __BITSET_T_INITIALIZER(x) \
314 { .__bits = { x } }
315
316#define __BITSET_FSET(n) \
317 [ 0 ... ((n) - 1) ] = (-1L)
318
319#define __BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long))
320
321#if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET)
322#define BIT_AND(_s, d, s) __BIT_AND(_s, d, s)
323#define BIT_AND2(_s, d, s1, s2) __BIT_AND2(_s, d, s1, s2)
324#define BIT_ANDNOT(_s, d, s) __BIT_ANDNOT(_s, d, s)
325#define BIT_ANDNOT2(_s, d, s1, s2) __BIT_ANDNOT2(_s, d, s1, s2)
326#define BIT_AND_ATOMIC(_s, d, s) __BIT_AND_ATOMIC(_s, d, s)
327#define BIT_CLR(_s, n, p) __BIT_CLR(_s, n, p)
328#define BIT_CLR_ATOMIC(_s, n, p) __BIT_CLR_ATOMIC(_s, n, p)
329#define BIT_CMP(_s, p, c) __BIT_CMP(_s, p, c)
330#define BIT_COPY(_s, f, t) __BIT_COPY(_s, f, t)
331#define BIT_COPY_STORE_REL(_s, f, t) __BIT_COPY_STORE_REL(_s, f, t)
332#define BIT_COUNT(_s, p) __BIT_COUNT(_s, p)
333#define BIT_EMPTY(_s, p) __BIT_EMPTY(_s, p)
334#define BIT_FFS(_s, p) __BIT_FFS(_s, p)
335#define BIT_FFS_AT(_s, p, start) __BIT_FFS_AT(_s, p, start)
336#define BIT_FILL(_s, p) __BIT_FILL(_s, p)
337#define BIT_FLS(_s, p) __BIT_FLS(_s, p)
338#define BIT_FOREACH(_s, i, p, op) __BIT_FOREACH(_s, i, p, op)
339#define BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH_ISCLR(_s, i, p)
340#define BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH_ISSET(_s, i, p)
341#define BIT_ISFULLSET(_s, p) __BIT_ISFULLSET(_s, p)
342#define BIT_ISSET(_s, n, p) __BIT_ISSET(_s, n, p)
343#define BIT_OR(_s, d, s) __BIT_OR(_s, d, s)
344#define BIT_OR2(_s, d, s1, s2) __BIT_OR2(_s, d, s1, s2)
345#define BIT_ORNOT(_s, d, s) __BIT_ORNOT(_s, d, s)
346#define BIT_ORNOT2(_s, d, s1, s2) __BIT_ORNOT2(_s, d, s1, s2)
347#define BIT_OR_ATOMIC(_s, d, s) __BIT_OR_ATOMIC(_s, d, s)
348#define BIT_OVERLAP(_s, p, c) __BIT_OVERLAP(_s, p, c)
349#define BIT_SET(_s, n, p) __BIT_SET(_s, n, p)
350#define BIT_SETOF(_s, n, p) __BIT_SETOF(_s, n, p)
351#define BIT_SET_ATOMIC(_s, n, p) __BIT_SET_ATOMIC(_s, n, p)
352#define BIT_SET_ATOMIC_ACQ(_s, n, p) __BIT_SET_ATOMIC_ACQ(_s, n, p)
353#define BIT_SUBSET(_s, p, c) __BIT_SUBSET(_s, p, c)
354#define BIT_TEST_CLR_ATOMIC(_s, n, p) __BIT_TEST_CLR_ATOMIC(_s, n, p)
355#define BIT_TEST_SET_ATOMIC(_s, n, p) __BIT_TEST_SET_ATOMIC(_s, n, p)
356#define BIT_XOR(_s, d, s) __BIT_XOR(_s, d, s)
357#define BIT_XOR2(_s, d, s1, s2) __BIT_XOR2(_s, d, s1, s2)
358#define BIT_ZERO(_s, p) __BIT_ZERO(_s, p)
359
360#if defined(_KERNEL)
361/*
362 * Dynamically allocate a bitset.
363 */
364#define BITSET_ALLOC(_s, mt, mf) malloc(__BITSET_SIZE((_s)), mt, (mf))
365#define BITSET_FREE(p, mt) free(p, mt)
366#endif /* _KERNEL */
367
368#define BITSET_FSET(n) __BITSET_FSET(n)
369#define BITSET_SIZE(_s) __BITSET_SIZE(_s)
370#define BITSET_T_INITIALIZER(x) __BITSET_T_INITIALIZER(x)
371#endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */
372
373#endif /* !_SYS_BITSET_H_ */