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 /* 312 * Dynamically allocate a bitset. 313 */ 314 #define BITSET_ALLOC(_s, mt, mf) malloc(BITSET_SIZE((_s)), mt, (mf)) 315 316 #endif /* !_SYS_BITSET_H_ */ 317