sys/sys/bitset.h

   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_AND(_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_AND2(_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_ANDNOT(_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_ANDNOT2(_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_XOR(_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_XOR2(_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 /*
 175  * Note, the atomic(9) API is not consistent between clear/set and
 176  * testandclear/testandset in whether the value argument is a mask
 177  * or a bit index.
 178  */
 179
 180 #define __BIT_CLR_ATOMIC(_s, n, p)                                      \
 181         atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)],           \
 182             __bitset_mask((_s), n))
 183
 184 #define __BIT_SET_ATOMIC(_s, n, p)                                      \
 185         atomic_set_long(&(p)->__bits[__bitset_word(_s, n)],             \
 186             __bitset_mask((_s), n))
 187
 188 #define __BIT_SET_ATOMIC_ACQ(_s, n, p)                                  \
 189         atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)],         \
 190             __bitset_mask((_s), n))
 191
 192 #define __BIT_TEST_CLR_ATOMIC(_s, n, p)                                 \
 193         (atomic_testandclear_long(                                      \
 194             &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
 195
 196 #define __BIT_TEST_SET_ATOMIC(_s, n, p)                                 \
 197         (atomic_testandset_long(                                        \
 198             &(p)->__bits[__bitset_word((_s), (n))], (n)) != 0)
 199
 200 /* Convenience functions catering special cases. */
 201 #define __BIT_AND_ATOMIC(_s, d, s) do {                                 \
 202         __size_t __i;                                                   \
 203         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 204                 atomic_clear_long(&(d)->__bits[__i],                    \
 205                     ~(s)->__bits[__i]);                                 \
 206 } while (0)
 207
 208 #define __BIT_OR_ATOMIC(_s, d, s) do {                                  \
 209         __size_t __i;                                                   \
 210         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 211                 atomic_set_long(&(d)->__bits[__i],                      \
 212                     (s)->__bits[__i]);                                  \
 213 } while (0)
 214
 215 #define __BIT_COPY_STORE_REL(_s, f, t) do {                             \
 216         __size_t __i;                                                   \
 217         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 218                 atomic_store_rel_long(&(t)->__bits[__i],                \
 219                     (f)->__bits[__i]);                                  \
 220 } while (0)
 221
 222 /*
 223  * Note that `start` and the returned value from __BIT_FFS_AT are
 224  * 1-based bit indices.
 225  */
 226 #define __BIT_FFS_AT(_s, p, start) __extension__ ({                     \
 227         __size_t __i;                                                   \
 228         long __bit, __mask;                                             \
 229                                                                         \
 230         __mask = ~0UL << ((start) % _BITSET_BITS);                      \
 231         __bit = 0;                                                      \
 232         for (__i = __bitset_word((_s), (start));                        \
 233             __i < __bitset_words((_s));                                 \
 234             __i++) {                                                    \
 235                 if (((p)->__bits[__i] & __mask) != 0) {                 \
 236                         __bit = ffsl((p)->__bits[__i] & __mask);        \
 237                         __bit += __i * _BITSET_BITS;                    \
 238                         break;                                          \
 239                 }                                                       \
 240                 __mask = ~0UL;                                          \
 241         }                                                               \
 242         __bit;                                                          \
 243 })
 244
 245 #define __BIT_FFS(_s, p) __BIT_FFS_AT((_s), (p), 0)
 246
 247 #define __BIT_FLS(_s, p) __extension__ ({                               \
 248         __size_t __i;                                                   \
 249         long __bit;                                                     \
 250                                                                         \
 251         __bit = 0;                                                      \
 252         for (__i = __bitset_words((_s)); __i > 0; __i--) {              \
 253                 if ((p)->__bits[__i - 1] != 0) {                        \
 254                         __bit = flsl((p)->__bits[__i - 1]);             \
 255                         __bit += (__i - 1) * _BITSET_BITS;              \
 256                         break;                                          \
 257                 }                                                       \
 258         }                                                               \
 259         __bit;                                                          \
 260 })
 261
 262 #define __BIT_COUNT(_s, p) __extension__ ({                             \
 263         __size_t __i;                                                   \
 264         long __count;                                                   \
 265                                                                         \
 266         __count = 0;                                                    \
 267         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 268                 __count += __bitcountl((p)->__bits[__i]);               \
 269         __count;                                                        \
 270 })
 271
 272 #define __BIT_FOREACH_ADVANCE(_s, i, p, op) __extension__ ({            \
 273         int __found;                                                    \
 274         for (;;) {                                                      \
 275                 if (__bits != 0) {                                      \
 276                         int __bit = ffsl(__bits) - 1;                   \
 277                         __bits &= ~(1ul << __bit);                      \
 278                         (i) = __i * _BITSET_BITS + __bit;               \
 279                         __found = 1;                                    \
 280                         break;                                          \
 281                 }                                                       \
 282                 if (++__i == __bitset_words(_s)) {                      \
 283                         __found = 0;                                    \
 284                         break;                                          \
 285                 }                                                       \
 286                 __bits = op((p)->__bits[__i]);                          \
 287         }                                                               \
 288         __found != 0;                                                   \
 289 })
 290
 291 /*
 292  * Non-destructively loop over all set or clear bits in the set.
 293  */
 294 #define __BIT_FOREACH(_s, i, p, op)                                     \
 295         for (long __i = -1, __bits = 0;                                 \
 296             __BIT_FOREACH_ADVANCE(_s, i, p, op); )
 297
 298 #define __BIT_FOREACH_ISSET(_s, i, p)   __BIT_FOREACH(_s, i, p, )
 299 #define __BIT_FOREACH_ISCLR(_s, i, p)   __BIT_FOREACH(_s, i, p, ~)
 300
 301 #define __BITSET_T_INITIALIZER(x)                                       \
 302         { .__bits = { x } }
 303
 304 #define __BITSET_FSET(n)                                                \
 305         [ 0 ... ((n) - 1) ] = (-1L)
 306
 307 #define __BITSET_SIZE(_s)       (__bitset_words((_s)) * sizeof(long))
 308
 309 #if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET)
 310 #define BIT_AND(_s, d, s)                       __BIT_AND(_s, d, s)
 311 #define BIT_AND2(_s, d, s1, s2)                 __BIT_AND2(_s, d, s1, s2)
 312 #define BIT_ANDNOT(_s, d, s)                    __BIT_ANDNOT(_s, d, s)
 313 #define BIT_ANDNOT2(_s, d, s1, s2)              __BIT_ANDNOT2(_s, d, s1, s2)
 314 #define BIT_AND_ATOMIC(_s, d, s)                __BIT_AND_ATOMIC(_s, d, s)
 315 #define BIT_CLR(_s, n, p)                       __BIT_CLR(_s, n, p)
 316 #define BIT_CLR_ATOMIC(_s, n, p)                __BIT_CLR_ATOMIC(_s, n, p)
 317 #define BIT_CMP(_s, p, c)                       __BIT_CMP(_s, p, c)
 318 #define BIT_COPY(_s, f, t)                      __BIT_COPY(_s, f, t)
 319 #define BIT_COPY_STORE_REL(_s, f, t)            __BIT_COPY_STORE_REL(_s, f, t)
 320 #define BIT_COUNT(_s, p)                        __BIT_COUNT(_s, p)
 321 #define BIT_EMPTY(_s, p)                        __BIT_EMPTY(_s, p)
 322 #define BIT_FFS(_s, p)                          __BIT_FFS(_s, p)
 323 #define BIT_FFS_AT(_s, p, start)                __BIT_FFS_AT(_s, p, start)
 324 #define BIT_FILL(_s, p)                         __BIT_FILL(_s, p)
 325 #define BIT_FLS(_s, p)                          __BIT_FLS(_s, p)
 326 #define BIT_FOREACH(_s, i, p, op)               __BIT_FOREACH(_s, i, p, op)
 327 #define BIT_FOREACH_ISCLR(_s, i, p)             __BIT_FOREACH_ISCLR(_s, i, p)
 328 #define BIT_FOREACH_ISSET(_s, i, p)             __BIT_FOREACH_ISSET(_s, i, p)
 329 #define BIT_ISFULLSET(_s, p)                    __BIT_ISFULLSET(_s, p)
 330 #define BIT_ISSET(_s, n, p)                     __BIT_ISSET(_s, n, p)
 331 #define BIT_OR(_s, d, s)                        __BIT_OR(_s, d, s)
 332 #define BIT_OR2(_s, d, s1, s2)                  __BIT_OR2(_s, d, s1, s2)
 333 #define BIT_OR_ATOMIC(_s, d, s)                 __BIT_OR_ATOMIC(_s, d, s)
 334 #define BIT_OVERLAP(_s, p, c)                   __BIT_OVERLAP(_s, p, c)
 335 #define BIT_SET(_s, n, p)                       __BIT_SET(_s, n, p)
 336 #define BIT_SETOF(_s, n, p)                     __BIT_SETOF(_s, n, p)
 337 #define BIT_SET_ATOMIC(_s, n, p)                __BIT_SET_ATOMIC(_s, n, p)
 338 #define BIT_SET_ATOMIC_ACQ(_s, n, p)            __BIT_SET_ATOMIC_ACQ(_s, n, p)
 339 #define BIT_SUBSET(_s, p, c)                    __BIT_SUBSET(_s, p, c)
 340 #define BIT_TEST_CLR_ATOMIC(_s, n, p)           __BIT_TEST_CLR_ATOMIC(_s, n, p)
 341 #define BIT_TEST_SET_ATOMIC(_s, n, p)           __BIT_TEST_SET_ATOMIC(_s, n, p)
 342 #define BIT_XOR(_s, d, s)                       __BIT_XOR(_s, d, s)
 343 #define BIT_XOR2(_s, d, s1, s2)                 __BIT_XOR2(_s, d, s1, s2)
 344 #define BIT_ZERO(_s, p)                         __BIT_ZERO(_s, p)
 345
 346 #if defined(_KERNEL)
 347 /*
 348  * Dynamically allocate a bitset.
 349  */
 350 #define BITSET_ALLOC(_s, mt, mf)                malloc(__BITSET_SIZE((_s)), mt, (mf))
 351 #define BITSET_FREE(p, mt)                      free(p, mt)
 352 #endif /* _KERNEL */
 353
 354 #define BITSET_FSET(n)                          __BITSET_FSET(n)
 355 #define BITSET_SIZE(_s)                         __BITSET_SIZE(_s)
 356 #define BITSET_T_INITIALIZER(x)                 __BITSET_T_INITIALIZER(x)
 357 #endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */
 358
 359 #endif /* !_SYS_BITSET_H_ */