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 #define BIT_CLR_ATOMIC(_s, n, p)                                        \
 177         atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)],           \
 178             __bitset_mask((_s), n))
 179
 180 #define BIT_SET_ATOMIC(_s, n, p)                                        \
 181         atomic_set_long(&(p)->__bits[__bitset_word(_s, n)],             \
 182             __bitset_mask((_s), n))
 183
 184 #define BIT_SET_ATOMIC_ACQ(_s, n, p)                                    \
 185         atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)],         \
 186             __bitset_mask((_s), n))
 187
 188 /* Convenience functions catering special cases. */
 189 #define BIT_AND_ATOMIC(_s, d, s) do {                                   \
 190         __size_t __i;                                                   \
 191         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 192                 atomic_clear_long(&(d)->__bits[__i],                    \
 193                     ~(s)->__bits[__i]);                                 \
 194 } while (0)
 195
 196 #define BIT_OR_ATOMIC(_s, d, s) do {                                    \
 197         __size_t __i;                                                   \
 198         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 199                 atomic_set_long(&(d)->__bits[__i],                      \
 200                     (s)->__bits[__i]);                                  \
 201 } while (0)
 202
 203 #define BIT_COPY_STORE_REL(_s, f, t) do {                               \
 204         __size_t __i;                                                   \
 205         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 206                 atomic_store_rel_long(&(t)->__bits[__i],                \
 207                     (f)->__bits[__i]);                                  \
 208 } while (0)
 209
 210 /*
 211  * Note that `start` and the returned value from BIT_FFS_AT are
 212  * 1-based bit indices.
 213  */
 214 #define BIT_FFS_AT(_s, p, start) __extension__ ({                       \
 215         __size_t __i;                                                   \
 216         long __bit, __mask;                                             \
 217                                                                         \
 218         __mask = ~0UL << ((start) % _BITSET_BITS);                      \
 219         __bit = 0;                                                      \
 220         for (__i = __bitset_word((_s), (start));                        \
 221             __i < __bitset_words((_s));                                 \
 222             __i++) {                                                    \
 223                 if (((p)->__bits[__i] & __mask) != 0) {                 \
 224                         __bit = ffsl((p)->__bits[__i] & __mask);        \
 225                         __bit += __i * _BITSET_BITS;                    \
 226                         break;                                          \
 227                 }                                                       \
 228                 __mask = ~0UL;                                          \
 229         }                                                               \
 230         __bit;                                                          \
 231 })
 232
 233 #define BIT_FFS(_s, p) BIT_FFS_AT((_s), (p), 0)
 234
 235 #define BIT_FLS(_s, p) __extension__ ({                                 \
 236         __size_t __i;                                                   \
 237         long __bit;                                                     \
 238                                                                         \
 239         __bit = 0;                                                      \
 240         for (__i = __bitset_words((_s)); __i > 0; __i--) {              \
 241                 if ((p)->__bits[__i - 1] != 0) {                        \
 242                         __bit = flsl((p)->__bits[__i - 1]);             \
 243                         __bit += (__i - 1) * _BITSET_BITS;              \
 244                         break;                                          \
 245                 }                                                       \
 246         }                                                               \
 247         __bit;                                                          \
 248 })
 249
 250 #define BIT_COUNT(_s, p) __extension__ ({                               \
 251         __size_t __i;                                                   \
 252         long __count;                                                   \
 253                                                                         \
 254         __count = 0;                                                    \
 255         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 256                 __count += __bitcountl((p)->__bits[__i]);               \
 257         __count;                                                        \
 258 })
 259
 260 #define BITSET_T_INITIALIZER(x)                                         \
 261         { .__bits = { x } }
 262
 263 #define BITSET_FSET(n)                                                  \
 264         [ 0 ... ((n) - 1) ] = (-1L)
 265
 266 #define BITSET_SIZE(_s) (__bitset_words((_s)) * sizeof(long))
 267
 268 /*
 269  * Dynamically allocate a bitset.
 270  */
 271 #define BITSET_ALLOC(_s, mt, mf)        malloc(BITSET_SIZE((_s)), mt, (mf))
 272
 273 #endif /* !_SYS_BITSET_H_ */