FreeBSD/Linux Kernel Cross Reference
sys/sys/bitset.h
1 /*-
2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
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 * $FreeBSD$
32 */
33
34 #ifndef _SYS_BITSET_H_
35 #define _SYS_BITSET_H_
36
37 /*
38 * Whether expr is both constant and true. Result is itself constant.
39 * Used to enable optimizations for sets with a known small size.
40 */
41 #define __constexpr_cond(expr) (__builtin_constant_p((expr)) && (expr))
42
43 #define __bitset_mask(_s, n) \
44 (1UL << (__constexpr_cond(__bitset_words((_s)) == 1) ? \
45 (__size_t)(n) : ((n) % _BITSET_BITS)))
46
47 #define __bitset_word(_s, n) \
48 (__constexpr_cond(__bitset_words((_s)) == 1) ? \
49 0 : ((n) / _BITSET_BITS))
50
51 #define __BIT_CLR(_s, n, p) \
52 ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
53
54 #define __BIT_COPY(_s, f, t) (void)(*(t) = *(f))
55
56 #define __BIT_ISSET(_s, n, p) \
57 ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
58
59 #define __BIT_SET(_s, n, p) \
60 ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
61
62 #define __BIT_ZERO(_s, p) do { \
63 __size_t __i; \
64 for (__i = 0; __i < __bitset_words((_s)); __i++) \
65 (p)->__bits[__i] = 0L; \
66 } while (0)
67
68 #define __BIT_FILL(_s, p) do { \
69 __size_t __i; \
70 for (__i = 0; __i < __bitset_words((_s)); __i++) \
71 (p)->__bits[__i] = -1L; \
72 } while (0)
73
74 #define __BIT_SETOF(_s, n, p) do { \
75 __BIT_ZERO(_s, p); \
76 (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \
77 } while (0)
78
79 /* Is p empty. */
80 #define __BIT_EMPTY(_s, p) __extension__ ({ \
81 __size_t __i; \
82 for (__i = 0; __i < __bitset_words((_s)); __i++) \
83 if ((p)->__bits[__i]) \
84 break; \
85 __i == __bitset_words((_s)); \
86 })
87
88 /* Is p full set. */
89 #define __BIT_ISFULLSET(_s, p) __extension__ ({ \
90 __size_t __i; \
91 for (__i = 0; __i < __bitset_words((_s)); __i++) \
92 if ((p)->__bits[__i] != (long)-1) \
93 break; \
94 __i == __bitset_words((_s)); \
95 })
96
97 /* Is c a subset of p. */
98 #define __BIT_SUBSET(_s, p, c) __extension__ ({ \
99 __size_t __i; \
100 for (__i = 0; __i < __bitset_words((_s)); __i++) \
101 if (((c)->__bits[__i] & \
102 (p)->__bits[__i]) != \
103 (c)->__bits[__i]) \
104 break; \
105 __i == __bitset_words((_s)); \
106 })
107
108 /* Are there any common bits between b & c? */
109 #define __BIT_OVERLAP(_s, p, c) __extension__ ({ \
110 __size_t __i; \
111 for (__i = 0; __i < __bitset_words((_s)); __i++) \
112 if (((c)->__bits[__i] & \
113 (p)->__bits[__i]) != 0) \
114 break; \
115 __i != __bitset_words((_s)); \
116 })
117
118 /* Compare two sets, returns 0 if equal 1 otherwise. */
119 #define __BIT_CMP(_s, p, c) __extension__ ({ \
120 __size_t __i; \
121 for (__i = 0; __i < __bitset_words((_s)); __i++) \
122 if (((c)->__bits[__i] != \
123 (p)->__bits[__i])) \
124 break; \
125 __i != __bitset_words((_s)); \
126 })
127
128 #define __BIT_OR(_s, d, s) do { \
129 __size_t __i; \
130 for (__i = 0; __i < __bitset_words((_s)); __i++) \
131 (d)->__bits[__i] |= (s)->__bits[__i]; \
132 } while (0)
133
134 #define __BIT_OR2(_s, d, s1, s2) do { \
135 __size_t __i; \
136 for (__i = 0; __i < __bitset_words((_s)); __i++) \
137 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
138 } while (0)
139
140 #define __BIT_AND(_s, d, s) do { \
141 __size_t __i; \
142 for (__i = 0; __i < __bitset_words((_s)); __i++) \
143 (d)->__bits[__i] &= (s)->__bits[__i]; \
144 } while (0)
145
146 #define __BIT_AND2(_s, d, s1, s2) do { \
147 __size_t __i; \
148 for (__i = 0; __i < __bitset_words((_s)); __i++) \
149 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
150 } while (0)
151
152 #define __BIT_ANDNOT(_s, d, s) do { \
153 __size_t __i; \
154 for (__i = 0; __i < __bitset_words((_s)); __i++) \
155 (d)->__bits[__i] &= ~(s)->__bits[__i]; \
156 } while (0)
157
158 #define __BIT_ANDNOT2(_s, d, s1, s2) do { \
159 __size_t __i; \
160 for (__i = 0; __i < __bitset_words((_s)); __i++) \
161 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
162 } while (0)
163
164 #define __BIT_XOR(_s, d, s) do { \
165 __size_t __i; \
166 for (__i = 0; __i < __bitset_words((_s)); __i++) \
167 (d)->__bits[__i] ^= (s)->__bits[__i]; \
168 } while (0)
169
170 #define __BIT_XOR2(_s, d, s1, s2) do { \
171 __size_t __i; \
172 for (__i = 0; __i < __bitset_words((_s)); __i++) \
173 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
174 } while (0)
175
176 /*
177 * Note, the atomic(9) API is not consistent between clear/set and
178 * testandclear/testandset in whether the value argument is a mask
179 * or a bit index.
180 */
181
182 #define __BIT_CLR_ATOMIC(_s, n, p) \
183 atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \
184 __bitset_mask((_s), n))
185
186 #define __BIT_SET_ATOMIC(_s, n, p) \
187 atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \
188 __bitset_mask((_s), n))
189
190 #define __BIT_SET_ATOMIC_ACQ(_s, n, p) \
191 atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \
192 __bitset_mask((_s), n))
193
194 #define __BIT_TEST_CLR_ATOMIC(_s, n, p) \
195 (atomic_testandclear_long( \
196 &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
197
198 #define __BIT_TEST_SET_ATOMIC(_s, n, p) \
199 (atomic_testandset_long( \
200 &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
201
202 /* Convenience functions catering special cases. */
203 #define __BIT_AND_ATOMIC(_s, d, s) do { \
204 __size_t __i; \
205 for (__i = 0; __i < __bitset_words((_s)); __i++) \
206 atomic_clear_long(&(d)->__bits[__i], \
207 ~(s)->__bits[__i]); \
208 } while (0)
209
210 #define __BIT_OR_ATOMIC(_s, d, s) do { \
211 __size_t __i; \
212 for (__i = 0; __i < __bitset_words((_s)); __i++) \
213 atomic_set_long(&(d)->__bits[__i], \
214 (s)->__bits[__i]); \
215 } while (0)
216
217 #define __BIT_COPY_STORE_REL(_s, f, t) do { \
218 __size_t __i; \
219 for (__i = 0; __i < __bitset_words((_s)); __i++) \
220 atomic_store_rel_long(&(t)->__bits[__i], \
221 (f)->__bits[__i]); \
222 } while (0)
223
224 /*
225 * Note that `start` and the returned value from __BIT_FFS_AT are
226 * 1-based bit indices.
227 */
228 #define __BIT_FFS_AT(_s, p, start) __extension__ ({ \
229 __size_t __i; \
230 long __bit, __mask; \
231 \
232 __mask = ~0UL << ((start) % _BITSET_BITS); \
233 __bit = 0; \
234 for (__i = __bitset_word((_s), (start)); \
235 __i < __bitset_words((_s)); \
236 __i++) { \
237 if (((p)->__bits[__i] & __mask) != 0) { \
238 __bit = ffsl((p)->__bits[__i] & __mask); \
239 __bit += __i * _BITSET_BITS; \
240 break; \
241 } \
242 __mask = ~0UL; \
243 } \
244 __bit; \
245 })
246
247 #define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0)
248
249 #define __BIT_FLS(_s, p) __extension__ ({ \
250 __size_t __i; \
251 long __bit; \
252 \
253 __bit = 0; \
254 for (__i = __bitset_words((_s)); __i > 0; __i--) { \
255 if ((p)->__bits[__i - 1] != 0) { \
256 __bit = flsl((p)->__bits[__i - 1]); \
257 __bit += (__i - 1) * _BITSET_BITS; \
258 break; \
259 } \
260 } \
261 __bit; \
262 })
263
264 #define __BIT_COUNT(_s, p) __extension__ ({ \
265 __size_t __i; \
266 long __count; \
267 \
268 __count = 0; \
269 for (__i = 0; __i < __bitset_words((_s)); __i++) \
270 __count += __bitcountl((p)->__bits[__i]); \
271 __count; \
272 })
273
274 #define __BIT_FOREACH_ADVANCE(_s, i, p, op) __extension__ ({ \
275 int __found; \
276 for (;;) { \
277 if (__bits != 0) { \
278 int __bit = ffsl(__bits) - 1; \
279 __bits &= ~(1ul << __bit); \
280 (i) = __i * _BITSET_BITS + __bit; \
281 __found = 1; \
282 break; \
283 } \
284 if (++__i == __bitset_words(_s)) { \
285 __found = 0; \
286 break; \
287 } \
288 __bits = op((p)->__bits[__i]); \
289 } \
290 __found != 0; \
291 })
292
293 /*
294 * Non-destructively loop over all set or clear bits in the set.
295 */
296 #define __BIT_FOREACH(_s, i, p, op) \
297 for (long __i = -1, __bits = 0; \
298 __BIT_FOREACH_ADVANCE(_s, i, p, op); )
299
300 #define __BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH(_s, i, p, )
301 #define __BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH(_s, i, p, ~)
302
303 #define __BITSET_T_INITIALIZER(x) \
304 { .__bits = { x } }
305
306 #define __BITSET_FSET(n) \
307 [ 0 ... ((n) - 1) ] = (-1L)
308
309 #define __BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long))
310
311 #if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET)
312 /*
313 * Dynamically allocate a bitset.
314 */
315 #define BIT_AND(_s, d, s) __BIT_AND(_s, d, s)
316 #define BIT_AND2(_s, d, s1, s2) __BIT_AND2(_s, d, s1, s2)
317 #define BIT_ANDNOT(_s, d, s) __BIT_ANDNOT(_s, d, s)
318 #define BIT_ANDNOT2(_s, d, s1, s2) __BIT_ANDNOT2(_s, d, s1, s2)
319 #define BIT_AND_ATOMIC(_s, d, s) __BIT_AND_ATOMIC(_s, d, s)
320 #define BIT_CLR(_s, n, p) __BIT_CLR(_s, n, p)
321 #define BIT_CLR_ATOMIC(_s, n, p) __BIT_CLR_ATOMIC(_s, n, p)
322 #define BIT_CMP(_s, p, c) __BIT_CMP(_s, p, c)
323 #define BIT_COPY(_s, f, t) __BIT_COPY(_s, f, t)
324 #define BIT_COPY_STORE_REL(_s, f, t) __BIT_COPY_STORE_REL(_s, f, t)
325 #define BIT_COUNT(_s, p) __BIT_COUNT(_s, p)
326 #define BIT_EMPTY(_s, p) __BIT_EMPTY(_s, p)
327 #define BIT_FFS(_s, p) __BIT_FFS(_s, p)
328 #define BIT_FFS_AT(_s, p, start) __BIT_FFS_AT(_s, p, start)
329 #define BIT_FILL(_s, p) __BIT_FILL(_s, p)
330 #define BIT_FLS(_s, p) __BIT_FLS(_s, p)
331 #define BIT_FOREACH(_s, i, p, op) __BIT_FOREACH(_s, i, p, op)
332 #define BIT_FOREACH_ADVANCE(_s, i, p, op) __BIT_FOREACH_ADVANCE(_s, i, p, op)
333 #define BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH_ISCLR(_s, i, p)
334 #define BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH_ISSET(_s, i, p)
335 #define BIT_ISFULLSET(_s, p) __BIT_ISFULLSET(_s, p)
336 #define BIT_ISSET(_s, n, p) __BIT_ISSET(_s, n, p)
337 #define BIT_OR(_s, d, s) __BIT_OR(_s, d, s)
338 #define BIT_OR2(_s, d, s1, s2) __BIT_OR2(_s, d, s1, s2)
339 #define BIT_OR_ATOMIC(_s, d, s) __BIT_OR_ATOMIC(_s, d, s)
340 #define BIT_OVERLAP(_s, p, c) __BIT_OVERLAP(_s, p, c)
341 #define BIT_SET(_s, n, p) __BIT_SET(_s, n, p)
342 #define BIT_SETOF(_s, n, p) __BIT_SETOF(_s, n, p)
343 #define BIT_SET_ATOMIC(_s, n, p) __BIT_SET_ATOMIC(_s, n, p)
344 #define BIT_SET_ATOMIC_ACQ(_s, n, p) __BIT_SET_ATOMIC_ACQ(_s, n, p)
345 #define BIT_SUBSET(_s, p, c) __BIT_SUBSET(_s, p, c)
346 #define BIT_TEST_CLR_ATOMIC(_s, n, p) __BIT_TEST_CLR_ATOMIC(_s, n, p)
347 #define BIT_TEST_SET_ATOMIC(_s, n, p) __BIT_TEST_SET_ATOMIC(_s, n, p)
348 #define BIT_XOR(_s, d, s) __BIT_XOR(_s, d, s)
349 #define BIT_XOR2(_s, d, s1, s2) __BIT_XOR2(_s, d, s1, s2)
350 #define BIT_ZERO(_s, p) __BIT_ZERO(_s, p)
351
352 #if defined(_KERNEL)
353 #define BITSET_ALLOC(_s, mt, mf) malloc(__BITSET_SIZE((_s)), mt, (mf))
354 #define BITSET_FREE(p, mt) free(p, mt)
355 #endif /* _KERNEL */
356
357 #define BITSET_FSET(n) __BITSET_FSET(n)
358 #define BITSET_SIZE(_s) __BITSET_SIZE(_s)
359 #define BITSET_T_INITIALIZER(x) __BITSET_T_INITIALIZER(x)
360 #endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */
361
362 #endif /* !_SYS_BITSET_H_ */
Cache object: b25f9221ffbe832dfdab61d79ac48aec
|