diff --git a/sys/sys/bitset.h b/sys/sys/bitset.h index 2b26e8bcdbf9..d7e0b4cd7e41 100644 --- a/sys/sys/bitset.h +++ b/sys/sys/bitset.h @@ -1,374 +1,373 @@ /*- * SPDX-License-Identifier: BSD-2-Clause * * Copyright (c) 2008, Jeffrey Roberson * All rights reserved. * * Copyright (c) 2008 Nokia Corporation * All rights reserved. * * Redistribution and use in source and binary forms, with or without * modification, are permitted provided that the following conditions * are met: * 1. Redistributions of source code must retain the above copyright * notice unmodified, this list of conditions, and the following * disclaimer. * 2. Redistributions in binary form must reproduce the above copyright * notice, this list of conditions and the following disclaimer in the * documentation and/or other materials provided with the distribution. * * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. */ #ifndef _SYS_BITSET_H_ #define _SYS_BITSET_H_ /* * Whether expr is both constant and true. Result is itself constant. * Used to enable optimizations for sets with a known small size. */ #define __constexpr_cond(expr) (__builtin_constant_p((expr)) && (expr)) #define __bitset_mask(_s, n) \ (1UL << (__constexpr_cond(__bitset_words((_s)) == 1) ? \ (__size_t)(n) : ((n) % _BITSET_BITS))) #define __bitset_word(_s, n) \ (__constexpr_cond(__bitset_words((_s)) == 1) ? \ 0 : ((n) / _BITSET_BITS)) #define __BIT_CLR(_s, n, p) \ ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n))) #define __BIT_COPY(_s, f, t) (void)(*(t) = *(f)) #define __BIT_ISSET(_s, n, p) \ ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0)) #define __BIT_SET(_s, n, p) \ ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n))) #define __BIT_ZERO(_s, p) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (p)->__bits[__i] = 0L; \ } while (0) #define __BIT_FILL(_s, p) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (p)->__bits[__i] = -1L; \ } while (0) #define __BIT_SETOF(_s, n, p) do { \ __BIT_ZERO(_s, p); \ (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n)); \ } while (0) /* Is p empty. */ #define __BIT_EMPTY(_s, p) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if ((p)->__bits[__i]) \ break; \ __i == __bitset_words((_s)); \ }) /* Is p full set. */ #define __BIT_ISFULLSET(_s, p) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if ((p)->__bits[__i] != (long)-1) \ break; \ __i == __bitset_words((_s)); \ }) /* Is c a subset of p. */ #define __BIT_SUBSET(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] & \ (p)->__bits[__i]) != \ (c)->__bits[__i]) \ break; \ __i == __bitset_words((_s)); \ }) /* Are there any common bits between b & c? */ #define __BIT_OVERLAP(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] & \ (p)->__bits[__i]) != 0) \ break; \ __i != __bitset_words((_s)); \ }) /* Compare two sets, returns 0 if equal 1 otherwise. */ #define __BIT_CMP(_s, p, c) __extension__ ({ \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ if (((c)->__bits[__i] != \ (p)->__bits[__i])) \ break; \ __i != __bitset_words((_s)); \ }) #define __BIT_OR(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] |= (s)->__bits[__i]; \ } while (0) #define __BIT_OR2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\ } while (0) #define __BIT_ORNOT(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] |= ~(s)->__bits[__i]; \ } while (0) #define __BIT_ORNOT2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] | ~(s2)->__bits[__i];\ } while (0) #define __BIT_AND(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] &= (s)->__bits[__i]; \ } while (0) #define __BIT_AND2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\ } while (0) #define __BIT_ANDNOT(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] &= ~(s)->__bits[__i]; \ } while (0) #define __BIT_ANDNOT2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\ } while (0) #define __BIT_XOR(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] ^= (s)->__bits[__i]; \ } while (0) #define __BIT_XOR2(_s, d, s1, s2) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\ } while (0) /* * Note, the atomic(9) API is not consistent between clear/set and * testandclear/testandset in whether the value argument is a mask * or a bit index. */ #define __BIT_CLR_ATOMIC(_s, n, p) \ atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) #define __BIT_SET_ATOMIC(_s, n, p) \ atomic_set_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) #define __BIT_SET_ATOMIC_ACQ(_s, n, p) \ atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)], \ __bitset_mask((_s), n)) #define __BIT_TEST_CLR_ATOMIC(_s, n, p) \ (atomic_testandclear_long( \ &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0) #define __BIT_TEST_SET_ATOMIC(_s, n, p) \ (atomic_testandset_long( \ &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0) /* Convenience functions catering special cases. */ #define __BIT_AND_ATOMIC(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_clear_long(&(d)->__bits[__i], \ ~(s)->__bits[__i]); \ } while (0) #define __BIT_OR_ATOMIC(_s, d, s) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_set_long(&(d)->__bits[__i], \ (s)->__bits[__i]); \ } while (0) #define __BIT_COPY_STORE_REL(_s, f, t) do { \ __size_t __i; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ atomic_store_rel_long(&(t)->__bits[__i], \ (f)->__bits[__i]); \ } while (0) /* - * 'start' and 'end' are 0-based bit (runtime) indices. Note that, as for ffs(), - * the returned index is 1-based, 0 being reserved to indicate that no bits are - * set. + * 'start' is a 0-based bit index. By contrast, and as for ffs(), the returned + * index is 1-based, 0 being reserved to indicate that no bits are set. */ #define __BIT_FFS_AT(_s, p, start) __extension__ ({ \ __size_t __i; \ long __bit, __mask; \ \ __mask = ~0UL << ((start) % _BITSET_BITS); \ __bit = 0; \ for (__i = __bitset_word((_s), (start)); \ __i < __bitset_words((_s)); \ __i++) { \ if (((p)->__bits[__i] & __mask) != 0) { \ __bit = ffsl((p)->__bits[__i] & __mask); \ __bit += __i * _BITSET_BITS; \ break; \ } \ __mask = ~0UL; \ } \ __bit; \ }) #define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0) #define __BIT_FLS(_s, p) __extension__ ({ \ __size_t __i; \ long __bit; \ \ __bit = 0; \ for (__i = __bitset_words((_s)); __i > 0; __i--) { \ if ((p)->__bits[__i - 1] != 0) { \ __bit = flsl((p)->__bits[__i - 1]); \ __bit += (__i - 1) * _BITSET_BITS; \ break; \ } \ } \ __bit; \ }) #define __BIT_COUNT(_s, p) __extension__ ({ \ __size_t __i; \ long __count; \ \ __count = 0; \ for (__i = 0; __i < __bitset_words((_s)); __i++) \ __count += __bitcountl((p)->__bits[__i]); \ __count; \ }) #define __BIT_FOREACH_ADVANCE(_s, i, p, op) __extension__ ({ \ int __found; \ for (;;) { \ if (__bits != 0) { \ int __bit = ffsl(__bits) - 1; \ __bits &= ~(1ul << __bit); \ (i) = __i * _BITSET_BITS + __bit; \ __found = 1; \ break; \ } \ if (++__i == __bitset_words(_s)) { \ __found = 0; \ break; \ } \ __bits = op((p)->__bits[__i]); \ } \ __found != 0; \ }) /* * Non-destructively loop over all set or clear bits in the set. */ #define __BIT_FOREACH(_s, i, p, op) \ for (long __i = -1, __bits = 0; \ __BIT_FOREACH_ADVANCE(_s, i, p, op); ) #define __BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH(_s, i, p, ) #define __BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH(_s, i, p, ~) #define __BITSET_T_INITIALIZER(x) \ { .__bits = { x } } #define __BITSET_FSET(n) \ [ 0 ... ((n) - 1) ] = (-1L) #define __BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long)) #if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) #define BIT_AND(_s, d, s) __BIT_AND(_s, d, s) #define BIT_AND2(_s, d, s1, s2) __BIT_AND2(_s, d, s1, s2) #define BIT_ANDNOT(_s, d, s) __BIT_ANDNOT(_s, d, s) #define BIT_ANDNOT2(_s, d, s1, s2) __BIT_ANDNOT2(_s, d, s1, s2) #define BIT_AND_ATOMIC(_s, d, s) __BIT_AND_ATOMIC(_s, d, s) #define BIT_CLR(_s, n, p) __BIT_CLR(_s, n, p) #define BIT_CLR_ATOMIC(_s, n, p) __BIT_CLR_ATOMIC(_s, n, p) #define BIT_CMP(_s, p, c) __BIT_CMP(_s, p, c) #define BIT_COPY(_s, f, t) __BIT_COPY(_s, f, t) #define BIT_COPY_STORE_REL(_s, f, t) __BIT_COPY_STORE_REL(_s, f, t) #define BIT_COUNT(_s, p) __BIT_COUNT(_s, p) #define BIT_EMPTY(_s, p) __BIT_EMPTY(_s, p) #define BIT_FFS(_s, p) __BIT_FFS(_s, p) #define BIT_FFS_AT(_s, p, start) __BIT_FFS_AT(_s, p, start) #define BIT_FILL(_s, p) __BIT_FILL(_s, p) #define BIT_FLS(_s, p) __BIT_FLS(_s, p) #define BIT_FOREACH(_s, i, p, op) __BIT_FOREACH(_s, i, p, op) #define BIT_FOREACH_ISCLR(_s, i, p) __BIT_FOREACH_ISCLR(_s, i, p) #define BIT_FOREACH_ISSET(_s, i, p) __BIT_FOREACH_ISSET(_s, i, p) #define BIT_ISFULLSET(_s, p) __BIT_ISFULLSET(_s, p) #define BIT_ISSET(_s, n, p) __BIT_ISSET(_s, n, p) #define BIT_OR(_s, d, s) __BIT_OR(_s, d, s) #define BIT_OR2(_s, d, s1, s2) __BIT_OR2(_s, d, s1, s2) #define BIT_ORNOT(_s, d, s) __BIT_ORNOT(_s, d, s) #define BIT_ORNOT2(_s, d, s1, s2) __BIT_ORNOT2(_s, d, s1, s2) #define BIT_OR_ATOMIC(_s, d, s) __BIT_OR_ATOMIC(_s, d, s) #define BIT_OVERLAP(_s, p, c) __BIT_OVERLAP(_s, p, c) #define BIT_SET(_s, n, p) __BIT_SET(_s, n, p) #define BIT_SETOF(_s, n, p) __BIT_SETOF(_s, n, p) #define BIT_SET_ATOMIC(_s, n, p) __BIT_SET_ATOMIC(_s, n, p) #define BIT_SET_ATOMIC_ACQ(_s, n, p) __BIT_SET_ATOMIC_ACQ(_s, n, p) #define BIT_SUBSET(_s, p, c) __BIT_SUBSET(_s, p, c) #define BIT_TEST_CLR_ATOMIC(_s, n, p) __BIT_TEST_CLR_ATOMIC(_s, n, p) #define BIT_TEST_SET_ATOMIC(_s, n, p) __BIT_TEST_SET_ATOMIC(_s, n, p) #define BIT_XOR(_s, d, s) __BIT_XOR(_s, d, s) #define BIT_XOR2(_s, d, s1, s2) __BIT_XOR2(_s, d, s1, s2) #define BIT_ZERO(_s, p) __BIT_ZERO(_s, p) #if defined(_KERNEL) /* * Dynamically allocate a bitset. */ #define BITSET_ALLOC(_s, mt, mf) malloc(__BITSET_SIZE((_s)), mt, (mf)) #define BITSET_FREE(p, mt) free(p, mt) #endif /* _KERNEL */ #define BITSET_FSET(n) __BITSET_FSET(n) #define BITSET_SIZE(_s) __BITSET_SIZE(_s) #define BITSET_T_INITIALIZER(x) __BITSET_T_INITIALIZER(x) #endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */ #endif /* !_SYS_BITSET_H_ */