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' and 'end' are 0-based bit (runtime) indices. Note that, as for ffs(), 236 * the returned index is 1-based, 0 being reserved to indicate that no bits are 237 * set. 238 */ 239 #define __BIT_FFS_AT(_s, p, start) __extension__ ({ \ 240 __size_t __i; \ 241 long __bit, __mask; \ 242 \ 243 __mask = ~0UL << ((start) % _BITSET_BITS); \ 244 __bit = 0; \ 245 for (__i = __bitset_word((_s), (start)); \ 246 __i < __bitset_words((_s)); \ 247 __i++) { \ 248 if (((p)->__bits[__i] & __mask) != 0) { \ 249 __bit = ffsl((p)->__bits[__i] & __mask); \ 250 __bit += __i * _BITSET_BITS; \ 251 break; \ 252 } \ 253 __mask = ~0UL; \ 254 } \ 255 __bit; \ 256 }) 257 258 #define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0) 259 260 #define __BIT_FLS(_s, p) __extension__ ({ \ 261 __size_t __i; \ 262 long __bit; \ 263 \ 264 __bit = 0; \ 265 for (__i = __bitset_words((_s)); __i > 0; __i--) { \ 266 if ((p)->__bits[__i - 1] != 0) { \ 267 __bit = flsl((p)->__bits[__i - 1]); \ 268 __bit += (__i - 1) * _BITSET_BITS; \ 269 break; \ 270 } \ 271 } \ 272 __bit; \ 273 }) 274 275 #define __BIT_COUNT(_s, p) __extension__ ({ \ 276 __size_t __i; \ 277 long __count; \ 278 \ 279 __count = 0; \ 280 for (__i = 0; __i < __bitset_words((_s)); __i++) \ 281 __count += __bitcountl((p)->__bits[__i]); \ 282 __count; \ 283 }) 284 285 #define __BIT_FOREACH_ADVANCE(_s, i, p, op) __extension__ ({ \ 286 int __found; \ 287 for (;;) { \ 288 if (__bits != 0) { \ 289 int __bit = ffsl(__bits) - 1; \ 290 __bits &= ~(1ul << __bit); \ 291 (i) = __i * _BITSET_BITS + __bit; \ 292 __found = 1; \ 293 break; \ 294 } \ 295 if (++__i == __bitset_words(_s)) { \ 296 __found = 0; \ 297 break; \ 298 } \ 299 __bits = op((p)->__bits[__i]); \ 300 } \ 301 __found != 0; \ 302 }) 303 304 /* 305 * Non-destructively loop over all set or clear bits in the set. 306 */ 307 #define __BIT_FOREACH(_s, i, p, op) \ 308 for (long __i = -1, __bits = 0; \ 309 __BIT_FOREACH_ADVANCE(_s, i, p, op); ) 310 311 #define __BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH(_s, i, p, ) 312 #define __BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH(_s, i, p, ~) 313 314 #define __BITSET_T_INITIALIZER(x) \ 315 { .__bits = { x } } 316 317 #define __BITSET_FSET(n) \ 318 [ 0 ... ((n) - 1) ] = (-1L) 319 320 #define __BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long)) 321 322 #if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) 323 #define BIT_AND(_s, d, s) __BIT_AND(_s, d, s) 324 #define BIT_AND2(_s, d, s1, s2) __BIT_AND2(_s, d, s1, s2) 325 #define BIT_ANDNOT(_s, d, s) __BIT_ANDNOT(_s, d, s) 326 #define BIT_ANDNOT2(_s, d, s1, s2) __BIT_ANDNOT2(_s, d, s1, s2) 327 #define BIT_AND_ATOMIC(_s, d, s) __BIT_AND_ATOMIC(_s, d, s) 328 #define BIT_CLR(_s, n, p) __BIT_CLR(_s, n, p) 329 #define BIT_CLR_ATOMIC(_s, n, p) __BIT_CLR_ATOMIC(_s, n, p) 330 #define BIT_CMP(_s, p, c) __BIT_CMP(_s, p, c) 331 #define BIT_COPY(_s, f, t) __BIT_COPY(_s, f, t) 332 #define BIT_COPY_STORE_REL(_s, f, t) __BIT_COPY_STORE_REL(_s, f, t) 333 #define BIT_COUNT(_s, p) __BIT_COUNT(_s, p) 334 #define BIT_EMPTY(_s, p) __BIT_EMPTY(_s, p) 335 #define BIT_FFS(_s, p) __BIT_FFS(_s, p) 336 #define BIT_FFS_AT(_s, p, start) __BIT_FFS_AT(_s, p, start) 337 #define BIT_FILL(_s, p) __BIT_FILL(_s, p) 338 #define BIT_FLS(_s, p) __BIT_FLS(_s, p) 339 #define BIT_FOREACH(_s, i, p, op) __BIT_FOREACH(_s, i, p, op) 340 #define BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH_ISCLR(_s, i, p) 341 #define BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH_ISSET(_s, i, p) 342 #define BIT_ISFULLSET(_s, p) __BIT_ISFULLSET(_s, p) 343 #define BIT_ISSET(_s, n, p) __BIT_ISSET(_s, n, p) 344 #define BIT_OR(_s, d, s) __BIT_OR(_s, d, s) 345 #define BIT_OR2(_s, d, s1, s2) __BIT_OR2(_s, d, s1, s2) 346 #define BIT_ORNOT(_s, d, s) __BIT_ORNOT(_s, d, s) 347 #define BIT_ORNOT2(_s, d, s1, s2) __BIT_ORNOT2(_s, d, s1, s2) 348 #define BIT_OR_ATOMIC(_s, d, s) __BIT_OR_ATOMIC(_s, d, s) 349 #define BIT_OVERLAP(_s, p, c) __BIT_OVERLAP(_s, p, c) 350 #define BIT_SET(_s, n, p) __BIT_SET(_s, n, p) 351 #define BIT_SETOF(_s, n, p) __BIT_SETOF(_s, n, p) 352 #define BIT_SET_ATOMIC(_s, n, p) __BIT_SET_ATOMIC(_s, n, p) 353 #define BIT_SET_ATOMIC_ACQ(_s, n, p) __BIT_SET_ATOMIC_ACQ(_s, n, p) 354 #define BIT_SUBSET(_s, p, c) __BIT_SUBSET(_s, p, c) 355 #define BIT_TEST_CLR_ATOMIC(_s, n, p) __BIT_TEST_CLR_ATOMIC(_s, n, p) 356 #define BIT_TEST_SET_ATOMIC(_s, n, p) __BIT_TEST_SET_ATOMIC(_s, n, p) 357 #define BIT_XOR(_s, d, s) __BIT_XOR(_s, d, s) 358 #define BIT_XOR2(_s, d, s1, s2) __BIT_XOR2(_s, d, s1, s2) 359 #define BIT_ZERO(_s, p) __BIT_ZERO(_s, p) 360 361 #if defined(_KERNEL) 362 /* 363 * Dynamically allocate a bitset. 364 */ 365 #define BITSET_ALLOC(_s, mt, mf) malloc(__BITSET_SIZE((_s)), mt, (mf)) 366 #define BITSET_FREE(p, mt) free(p, mt) 367 #endif /* _KERNEL */ 368 369 #define BITSET_FSET(n) __BITSET_FSET(n) 370 #define BITSET_SIZE(_s) __BITSET_SIZE(_s) 371 #define BITSET_T_INITIALIZER(x) __BITSET_T_INITIALIZER(x) 372 #endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */ 373 374 #endif /* !_SYS_BITSET_H_ */ 375