sys/sys/bitset.h

   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 #if defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET)
 312 /*
 313  * Dynamically allocate a bitset.
 314  */
 315 #define BIT_AND(_s, d, s)                       __BIT_AND(_s, d, s)
 316 #define BIT_AND2(_s, d, s1, s2)                 __BIT_AND2(_s, d, s1, s2)
 317 #define BIT_ANDNOT(_s, d, s)                    __BIT_ANDNOT(_s, d, s)
 318 #define BIT_ANDNOT2(_s, d, s1, s2)              __BIT_ANDNOT2(_s, d, s1, s2)
 319 #define BIT_AND_ATOMIC(_s, d, s)                __BIT_AND_ATOMIC(_s, d, s)
 320 #define BIT_CLR(_s, n, p)                       __BIT_CLR(_s, n, p)
 321 #define BIT_CLR_ATOMIC(_s, n, p)                __BIT_CLR_ATOMIC(_s, n, p)
 322 #define BIT_CMP(_s, p, c)                       __BIT_CMP(_s, p, c)
 323 #define BIT_COPY(_s, f, t)                      __BIT_COPY(_s, f, t)
 324 #define BIT_COPY_STORE_REL(_s, f, t)            __BIT_COPY_STORE_REL(_s, f, t)
 325 #define BIT_COUNT(_s, p)                        __BIT_COUNT(_s, p)
 326 #define BIT_EMPTY(_s, p)                        __BIT_EMPTY(_s, p)
 327 #define BIT_FFS(_s, p)                          __BIT_FFS(_s, p)
 328 #define BIT_FFS_AT(_s, p, start)                __BIT_FFS_AT(_s, p, start)
 329 #define BIT_FILL(_s, p)                         __BIT_FILL(_s, p)
 330 #define BIT_FLS(_s, p)                          __BIT_FLS(_s, p)
 331 #define BIT_FOREACH(_s, i, p, op)               __BIT_FOREACH(_s, i, p, op)
 332 #define BIT_FOREACH_ADVANCE(_s, i, p, op)       __BIT_FOREACH_ADVANCE(_s, i, p, op)
 333 #define BIT_FOREACH_ISCLR(_s, i, p)             __BIT_FOREACH_ISCLR(_s, i, p)
 334 #define BIT_FOREACH_ISSET(_s, i, p)             __BIT_FOREACH_ISSET(_s, i, p)
 335 #define BIT_ISFULLSET(_s, p)                    __BIT_ISFULLSET(_s, p)
 336 #define BIT_ISSET(_s, n, p)                     __BIT_ISSET(_s, n, p)
 337 #define BIT_OR(_s, d, s)                        __BIT_OR(_s, d, s)
 338 #define BIT_OR2(_s, d, s1, s2)                  __BIT_OR2(_s, d, s1, s2)
 339 #define BIT_OR_ATOMIC(_s, d, s)                 __BIT_OR_ATOMIC(_s, d, s)
 340 #define BIT_OVERLAP(_s, p, c)                   __BIT_OVERLAP(_s, p, c)
 341 #define BIT_SET(_s, n, p)                       __BIT_SET(_s, n, p)
 342 #define BIT_SETOF(_s, n, p)                     __BIT_SETOF(_s, n, p)
 343 #define BIT_SET_ATOMIC(_s, n, p)                __BIT_SET_ATOMIC(_s, n, p)
 344 #define BIT_SET_ATOMIC_ACQ(_s, n, p)            __BIT_SET_ATOMIC_ACQ(_s, n, p)
 345 #define BIT_SUBSET(_s, p, c)                    __BIT_SUBSET(_s, p, c)
 346 #define BIT_TEST_CLR_ATOMIC(_s, n, p)           __BIT_TEST_CLR_ATOMIC(_s, n, p)
 347 #define BIT_TEST_SET_ATOMIC(_s, n, p)           __BIT_TEST_SET_ATOMIC(_s, n, p)
 348 #define BIT_XOR(_s, d, s)                       __BIT_XOR(_s, d, s)
 349 #define BIT_XOR2(_s, d, s1, s2)                 __BIT_XOR2(_s, d, s1, s2)
 350 #define BIT_ZERO(_s, p)                         __BIT_ZERO(_s, p)
 351
 352 #if defined(_KERNEL)
 353 #define BITSET_ALLOC(_s, mt, mf)                malloc(__BITSET_SIZE((_s)), mt, (mf))
 354 #define BITSET_FREE(p, mt)                      free(p, mt)
 355 #endif /* _KERNEL */
 356
 357 #define BITSET_FSET(n)                          __BITSET_FSET(n)
 358 #define BITSET_SIZE(_s)                         __BITSET_SIZE(_s)
 359 #define BITSET_T_INITIALIZER(x)                 __BITSET_T_INITIALIZER(x)
 360 #endif /* defined(_KERNEL) || defined(_WANT_FREEBSD_BITSET) */
 361
 362 #endif /* !_SYS_BITSET_H_ */