2 * SPDX-License-Identifier: BSD-2-Clause-FreeBSD
4 * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
7 * Copyright (c) 2008 Nokia Corporation
10 * Redistribution and use in source and binary forms, with or without
11 * modification, are permitted provided that the following conditions
13 * 1. Redistributions of source code must retain the above copyright
14 * notice unmodified, this list of conditions, and the following
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.
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.
34 #ifndef _SYS_BITSET_H_
35 #define _SYS_BITSET_H_
38 * Whether expr is both constant and true. Result is itself constant.
39 * Used to enable optimizations for sets with a known small size.
41 #define __constexpr_cond(expr) (__builtin_constant_p((expr)) && (expr))
43 #define __bitset_mask(_s, n) \
44 (1UL << (__constexpr_cond(__bitset_words((_s)) == 1) ? \
45 (__size_t)(n) : ((n) % _BITSET_BITS)))
47 #define __bitset_word(_s, n) \
48 (__constexpr_cond(__bitset_words((_s)) == 1) ? \
49 0 : ((n) / _BITSET_BITS))
51 #define BIT_CLR(_s, n, p) \
52 ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
54 #define BIT_COPY(_s, f, t) (void)(*(t) = *(f))
56 #define BIT_ISSET(_s, n, p) \
57 ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
59 #define BIT_SET(_s, n, p) \
60 ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
62 #define BIT_ZERO(_s, p) do { \
64 for (__i = 0; __i < __bitset_words((_s)); __i++) \
65 (p)->__bits[__i] = 0L; \
68 #define BIT_FILL(_s, p) do { \
70 for (__i = 0; __i < __bitset_words((_s)); __i++) \
71 (p)->__bits[__i] = -1L; \
74 #define BIT_SETOF(_s, n, p) do { \
76 (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \
80 #define BIT_EMPTY(_s, p) __extension__ ({ \
82 for (__i = 0; __i < __bitset_words((_s)); __i++) \
83 if ((p)->__bits[__i]) \
85 __i == __bitset_words((_s)); \
89 #define BIT_ISFULLSET(_s, p) __extension__ ({ \
91 for (__i = 0; __i < __bitset_words((_s)); __i++) \
92 if ((p)->__bits[__i] != (long)-1) \
94 __i == __bitset_words((_s)); \
97 /* Is c a subset of p. */
98 #define BIT_SUBSET(_s, p, c) __extension__ ({ \
100 for (__i = 0; __i < __bitset_words((_s)); __i++) \
101 if (((c)->__bits[__i] & \
102 (p)->__bits[__i]) != \
105 __i == __bitset_words((_s)); \
108 /* Are there any common bits between b & c? */
109 #define BIT_OVERLAP(_s, p, c) __extension__ ({ \
111 for (__i = 0; __i < __bitset_words((_s)); __i++) \
112 if (((c)->__bits[__i] & \
113 (p)->__bits[__i]) != 0) \
115 __i != __bitset_words((_s)); \
118 /* Compare two sets, returns 0 if equal 1 otherwise. */
119 #define BIT_CMP(_s, p, c) __extension__ ({ \
121 for (__i = 0; __i < __bitset_words((_s)); __i++) \
122 if (((c)->__bits[__i] != \
125 __i != __bitset_words((_s)); \
128 #define BIT_OR(_s, d, s) do { \
130 for (__i = 0; __i < __bitset_words((_s)); __i++) \
131 (d)->__bits[__i] |= (s)->__bits[__i]; \
134 #define BIT_OR2(_s, d, s1, s2) do { \
136 for (__i = 0; __i < __bitset_words((_s)); __i++) \
137 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
140 #define BIT_AND(_s, d, s) do { \
142 for (__i = 0; __i < __bitset_words((_s)); __i++) \
143 (d)->__bits[__i] &= (s)->__bits[__i]; \
146 #define BIT_AND2(_s, d, s1, s2) do { \
148 for (__i = 0; __i < __bitset_words((_s)); __i++) \
149 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
152 #define BIT_ANDNOT(_s, d, s) do { \
154 for (__i = 0; __i < __bitset_words((_s)); __i++) \
155 (d)->__bits[__i] &= ~(s)->__bits[__i]; \
158 #define BIT_ANDNOT2(_s, d, s1, s2) do { \
160 for (__i = 0; __i < __bitset_words((_s)); __i++) \
161 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
164 #define BIT_XOR(_s, d, s) do { \
166 for (__i = 0; __i < __bitset_words((_s)); __i++) \
167 (d)->__bits[__i] ^= (s)->__bits[__i]; \
170 #define BIT_XOR2(_s, d, s1, s2) do { \
172 for (__i = 0; __i < __bitset_words((_s)); __i++) \
173 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
176 #define BIT_CLR_ATOMIC(_s, n, p) \
177 atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \
178 __bitset_mask((_s), n))
180 #define BIT_SET_ATOMIC(_s, n, p) \
181 atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \
182 __bitset_mask((_s), n))
184 #define BIT_SET_ATOMIC_ACQ(_s, n, p) \
185 atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \
186 __bitset_mask((_s), n))
188 /* Convenience functions catering special cases. */
189 #define BIT_AND_ATOMIC(_s, d, s) do { \
191 for (__i = 0; __i < __bitset_words((_s)); __i++) \
192 atomic_clear_long(&(d)->__bits[__i], \
193 ~(s)->__bits[__i]); \
196 #define BIT_OR_ATOMIC(_s, d, s) do { \
198 for (__i = 0; __i < __bitset_words((_s)); __i++) \
199 atomic_set_long(&(d)->__bits[__i], \
203 #define BIT_COPY_STORE_REL(_s, f, t) do { \
205 for (__i = 0; __i < __bitset_words((_s)); __i++) \
206 atomic_store_rel_long(&(t)->__bits[__i], \
211 * Note that `start` and the returned value from BIT_FFS_AT are
212 * 1-based bit indices.
214 #define BIT_FFS_AT(_s, p, start) __extension__ ({ \
216 long __bit, __mask; \
218 __mask = ~0UL << ((start) % _BITSET_BITS); \
220 for (__i = __bitset_word((_s), (start)); \
221 __i < __bitset_words((_s)); \
223 if (((p)->__bits[__i] & __mask) != 0) { \
224 __bit = ffsl((p)->__bits[__i] & __mask); \
225 __bit += __i * _BITSET_BITS; \
233 #define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 0)
235 #define BIT_FLS(_s, p) __extension__ ({ \
240 for (__i = __bitset_words((_s)); __i > 0; __i--) { \
241 if ((p)->__bits[__i - 1] != 0) { \
242 __bit = flsl((p)->__bits[__i - 1]); \
243 __bit += (__i - 1) * _BITSET_BITS; \
250 #define BIT_COUNT(_s, p) __extension__ ({ \
255 for (__i = 0; __i < __bitset_words((_s)); __i++) \
256 __count += __bitcountl((p)->__bits[__i]); \
260 #define BITSET_T_INITIALIZER(x) \
263 #define BITSET_FSET(n) \
264 [ 0 ... ((n) - 1) ] = (-1L)
266 #define BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long))
269 * Dynamically allocate a bitset.
271 #define BITSET_ALLOC(_s, mt, mf) malloc(BITSET_SIZE((_s)), mt, (mf))
273 #endif /* !_SYS_BITSET_H_ */