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 #define __bitset_mask(_s, n)                                            \
  38         (1L << ((__bitset_words((_s)) == 1) ?                           \
  39             (__size_t)(n) : ((n) % _BITSET_BITS)))
  40
  41 #define __bitset_word(_s, n)                                            \
  42         ((__bitset_words((_s)) == 1) ? 0 : ((n) / _BITSET_BITS))
  43
  44 #define BIT_CLR(_s, n, p)                                               \
  45         ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
  46
  47 #define BIT_COPY(_s, f, t)      (void)(*(t) = *(f))
  48
  49 #define BIT_ISSET(_s, n, p)                                             \
  50         ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
  51
  52 #define BIT_SET(_s, n, p)                                               \
  53         ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
  54
  55 #define BIT_ZERO(_s, p) do {                                            \
  56         __size_t __i;                                                   \
  57         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  58                 (p)->__bits[__i] = 0L;                                  \
  59 } while (0)
  60
  61 #define BIT_FILL(_s, p) do {                                            \
  62         __size_t __i;                                                   \
  63         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  64                 (p)->__bits[__i] = -1L;                                 \
  65 } while (0)
  66
  67 #define BIT_SETOF(_s, n, p) do {                                        \
  68         BIT_ZERO(_s, p);                                                \
  69         (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n));   \
  70 } while (0)
  71
  72 /* Is p empty. */
  73 #define BIT_EMPTY(_s, p) __extension__ ({                               \
  74         __size_t __i;                                                   \
  75         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  76                 if ((p)->__bits[__i])                                   \
  77                         break;                                          \
  78         __i == __bitset_words((_s));                                    \
  79 })
  80
  81 /* Is p full set. */
  82 #define BIT_ISFULLSET(_s, p) __extension__ ({                           \
  83         __size_t __i;                                                   \
  84         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  85                 if ((p)->__bits[__i] != (long)-1)                       \
  86                         break;                                          \
  87         __i == __bitset_words((_s));                                    \
  88 })
  89
  90 /* Is c a subset of p. */
  91 #define BIT_SUBSET(_s, p, c) __extension__ ({                           \
  92         __size_t __i;                                                   \
  93         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  94                 if (((c)->__bits[__i] &                                 \
  95                     (p)->__bits[__i]) !=                                \
  96                     (c)->__bits[__i])                                   \
  97                         break;                                          \
  98         __i == __bitset_words((_s));                                    \
  99 })
 100
 101 /* Are there any common bits between b & c? */
 102 #define BIT_OVERLAP(_s, p, c) __extension__ ({                          \
 103         __size_t __i;                                                   \
 104         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 105                 if (((c)->__bits[__i] &                                 \
 106                     (p)->__bits[__i]) != 0)                             \
 107                         break;                                          \
 108         __i != __bitset_words((_s));                                    \
 109 })
 110
 111 /* Compare two sets, returns 0 if equal 1 otherwise. */
 112 #define BIT_CMP(_s, p, c) __extension__ ({                              \
 113         __size_t __i;                                                   \
 114         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 115                 if (((c)->__bits[__i] !=                                \
 116                     (p)->__bits[__i]))                                  \
 117                         break;                                          \
 118         __i != __bitset_words((_s));                                    \
 119 })
 120
 121 #define BIT_OR(_s, d, s) do {                                           \
 122         __size_t __i;                                                   \
 123         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 124                 (d)->__bits[__i] |= (s)->__bits[__i];                   \
 125 } while (0)
 126
 127 #define BIT_OR2(_s, d, s1, s2) do {                                     \
 128         __size_t __i;                                                   \
 129         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 130                 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
 131 } while (0)
 132
 133 #define BIT_AND(_s, d, s) do {                                          \
 134         __size_t __i;                                                   \
 135         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 136                 (d)->__bits[__i] &= (s)->__bits[__i];                   \
 137 } while (0)
 138
 139 #define BIT_AND2(_s, d, s1, s2) do {                                    \
 140         __size_t __i;                                                   \
 141         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 142                 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
 143 } while (0)
 144
 145 #define BIT_NAND(_s, d, s) do {                                         \
 146         __size_t __i;                                                   \
 147         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 148                 (d)->__bits[__i] &= ~(s)->__bits[__i];                  \
 149 } while (0)
 150
 151 #define BIT_NAND2(_s, d, s1, s2) do {                                   \
 152         __size_t __i;                                                   \
 153         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 154                 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
 155 } while (0)
 156
 157 #define BIT_XOR(_s, d, s) do {                                          \
 158         __size_t __i;                                                   \
 159         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 160                 (d)->__bits[__i] ^= (s)->__bits[__i];                   \
 161 } while (0)
 162
 163 #define BIT_XOR2(_s, d, s1, s2) do {                                    \
 164         __size_t __i;                                                   \
 165         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 166                 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
 167 } while (0)
 168
 169 #define BIT_CLR_ATOMIC(_s, n, p)                                        \
 170         atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)],           \
 171             __bitset_mask((_s), n))
 172
 173 #define BIT_SET_ATOMIC(_s, n, p)                                        \
 174         atomic_set_long(&(p)->__bits[__bitset_word(_s, n)],             \
 175             __bitset_mask((_s), n))
 176
 177 #define BIT_SET_ATOMIC_ACQ(_s, n, p)                                    \
 178         atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)],         \
 179             __bitset_mask((_s), n))
 180
 181 /* Convenience functions catering special cases. */
 182 #define BIT_AND_ATOMIC(_s, d, s) do {                                   \
 183         __size_t __i;                                                   \
 184         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 185                 atomic_clear_long(&(d)->__bits[__i],                    \
 186                     ~(s)->__bits[__i]);                                 \
 187 } while (0)
 188
 189 #define BIT_OR_ATOMIC(_s, d, s) do {                                    \
 190         __size_t __i;                                                   \
 191         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 192                 atomic_set_long(&(d)->__bits[__i],                      \
 193                     (s)->__bits[__i]);                                  \
 194 } while (0)
 195
 196 #define BIT_COPY_STORE_REL(_s, f, t) do {                               \
 197         __size_t __i;                                                   \
 198         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 199                 atomic_store_rel_long(&(t)->__bits[__i],                \
 200                     (f)->__bits[__i]);                                  \
 201 } while (0)
 202
 203 #define BIT_FFS(_s, p) __extension__ ({                                 \
 204         __size_t __i;                                                   \
 205         int __bit;                                                      \
 206                                                                         \
 207         __bit = 0;                                                      \
 208         for (__i = 0; __i < __bitset_words((_s)); __i++) {              \
 209                 if ((p)->__bits[__i] != 0) {                            \
 210                         __bit = ffsl((p)->__bits[__i]);                 \
 211                         __bit += __i * _BITSET_BITS;                    \
 212                         break;                                          \
 213                 }                                                       \
 214         }                                                               \
 215         __bit;                                                          \
 216 })
 217
 218 #define BIT_FLS(_s, p) __extension__ ({                                 \
 219         __size_t __i;                                                   \
 220         int __bit;                                                      \
 221                                                                         \
 222         __bit = 0;                                                      \
 223         for (__i = __bitset_words((_s)); __i > 0; __i--) {              \
 224                 if ((p)->__bits[__i - 1] != 0) {                        \
 225                         __bit = flsl((p)->__bits[__i - 1]);             \
 226                         __bit += (__i - 1) * _BITSET_BITS;              \
 227                         break;                                          \
 228                 }                                                       \
 229         }                                                               \
 230         __bit;                                                          \
 231 })
 232
 233 #define BIT_COUNT(_s, p) __extension__ ({                               \
 234         __size_t __i;                                                   \
 235         int __count;                                                    \
 236                                                                         \
 237         __count = 0;                                                    \
 238         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 239                 __count += __bitcountl((p)->__bits[__i]);               \
 240         __count;                                                        \
 241 })
 242
 243 #define BITSET_T_INITIALIZER(x)                                         \
 244         { .__bits = { x } }
 245
 246 #define BITSET_FSET(n)                                                  \
 247         [ 0 ... ((n) - 1) ] = (-1L)
 248
 249 /*
 250  * Dynamically allocate a bitset.
 251  */
 252 #define BITSET_ALLOC(_s, mt, mf)                                        \
 253         malloc(__bitset_words(_s) * sizeof(long), mt, (mf))
 254
 255 #endif /* !_SYS_BITSET_H_ */