sys/sys/bitset.h

   1 /*-
   2  * Copyright (c) 2008, Jeffrey Roberson <jeff@freebsd.org>
   3  * All rights reserved.
   4  *
   5  * Copyright (c) 2008 Nokia Corporation
   6  * All rights reserved.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice unmodified, this list of conditions, and the following
  13  *    disclaimer.
  14  * 2. Redistributions in binary form must reproduce the above copyright
  15  *    notice, this list of conditions and the following disclaimer in the
  16  *    documentation and/or other materials provided with the distribution.
  17  *
  18  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR
  19  * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  20  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED.
  21  * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT,
  22  * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  23  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  24  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  25  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  26  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF
  27  * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  28  *
  29  * $FreeBSD$
  30  */
  31
  32 #ifndef _SYS_BITSET_H_
  33 #define _SYS_BITSET_H_
  34
  35 #define __bitset_mask(_s, n)                                            \
  36         (1L << ((__bitset_words((_s)) == 1) ?                           \
  37             (__size_t)(n) : ((n) % _BITSET_BITS)))
  38
  39 #define __bitset_word(_s, n)                                            \
  40         ((__bitset_words((_s)) == 1) ? 0 : ((n) / _BITSET_BITS))
  41
  42 #define BIT_CLR(_s, n, p)                                               \
  43         ((p)->__bits[__bitset_word(_s, n)] &= ~__bitset_mask((_s), (n)))
  44
  45 #define BIT_COPY(_s, f, t)      (void)(*(t) = *(f))
  46
  47 #define BIT_ISSET(_s, n, p)                                             \
  48         ((((p)->__bits[__bitset_word(_s, n)] & __bitset_mask((_s), (n))) != 0))
  49
  50 #define BIT_SET(_s, n, p)                                               \
  51         ((p)->__bits[__bitset_word(_s, n)] |= __bitset_mask((_s), (n)))
  52
  53 #define BIT_ZERO(_s, p) do {                                            \
  54         __size_t __i;                                                   \
  55         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  56                 (p)->__bits[__i] = 0L;                                  \
  57 } while (0)
  58
  59 #define BIT_FILL(_s, p) do {                                            \
  60         __size_t __i;                                                   \
  61         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  62                 (p)->__bits[__i] = -1L;                                 \
  63 } while (0)
  64
  65 #define BIT_SETOF(_s, n, p) do {                                        \
  66         BIT_ZERO(_s, p);                                                \
  67         (p)->__bits[__bitset_word(_s, n)] = __bitset_mask((_s), (n));   \
  68 } while (0)
  69
  70 /* Is p empty. */
  71 #define BIT_EMPTY(_s, p) __extension__ ({                               \
  72         __size_t __i;                                                   \
  73         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  74                 if ((p)->__bits[__i])                                   \
  75                         break;                                          \
  76         __i == __bitset_words((_s));                                    \
  77 })
  78
  79 /* Is p full set. */
  80 #define BIT_ISFULLSET(_s, p) __extension__ ({                           \
  81         __size_t __i;                                                   \
  82         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  83                 if ((p)->__bits[__i] != (long)-1)                       \
  84                         break;                                          \
  85         __i == __bitset_words((_s));                                    \
  86 })
  87
  88 /* Is c a subset of p. */
  89 #define BIT_SUBSET(_s, p, c) __extension__ ({                           \
  90         __size_t __i;                                                   \
  91         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
  92                 if (((c)->__bits[__i] &                                 \
  93                     (p)->__bits[__i]) !=                                \
  94                     (c)->__bits[__i])                                   \
  95                         break;                                          \
  96         __i == __bitset_words((_s));                                    \
  97 })
  98
  99 /* Are there any common bits between b & c? */
 100 #define BIT_OVERLAP(_s, p, c) __extension__ ({                          \
 101         __size_t __i;                                                   \
 102         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 103                 if (((c)->__bits[__i] &                                 \
 104                     (p)->__bits[__i]) != 0)                             \
 105                         break;                                          \
 106         __i != __bitset_words((_s));                                    \
 107 })
 108
 109 /* Compare two sets, returns 0 if equal 1 otherwise. */
 110 #define BIT_CMP(_s, p, c) __extension__ ({                              \
 111         __size_t __i;                                                   \
 112         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 113                 if (((c)->__bits[__i] !=                                \
 114                     (p)->__bits[__i]))                                  \
 115                         break;                                          \
 116         __i != __bitset_words((_s));                                    \
 117 })
 118
 119 #define BIT_OR(_s, d, s) do {                                           \
 120         __size_t __i;                                                   \
 121         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 122                 (d)->__bits[__i] |= (s)->__bits[__i];                   \
 123 } while (0)
 124
 125 #define BIT_OR2(_s, d, s1, s2) do {                                     \
 126         __size_t __i;                                                   \
 127         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 128                 (d)->__bits[__i] = (s1)->__bits[__i] | (s2)->__bits[__i];\
 129 } while (0)
 130
 131 #define BIT_AND(_s, d, s) do {                                          \
 132         __size_t __i;                                                   \
 133         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 134                 (d)->__bits[__i] &= (s)->__bits[__i];                   \
 135 } while (0)
 136
 137 #define BIT_AND2(_s, d, s1, s2) do {                                    \
 138         __size_t __i;                                                   \
 139         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 140                 (d)->__bits[__i] = (s1)->__bits[__i] & (s2)->__bits[__i];\
 141 } while (0)
 142
 143 #define BIT_NAND(_s, d, s) do {                                         \
 144         __size_t __i;                                                   \
 145         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 146                 (d)->__bits[__i] &= ~(s)->__bits[__i];                  \
 147 } while (0)
 148
 149 #define BIT_NAND2(_s, d, s1, s2) do {                                   \
 150         __size_t __i;                                                   \
 151         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 152                 (d)->__bits[__i] = (s1)->__bits[__i] & ~(s2)->__bits[__i];\
 153 } while (0)
 154
 155 #define BIT_XOR(_s, d, s) do {                                          \
 156         __size_t __i;                                                   \
 157         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 158                 (d)->__bits[__i] ^= (s)->__bits[__i];                   \
 159 } while (0)
 160
 161 #define BIT_XOR2(_s, d, s1, s2) do {                                    \
 162         __size_t __i;                                                   \
 163         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 164                 (d)->__bits[__i] = (s1)->__bits[__i] ^ (s2)->__bits[__i];\
 165 } while (0)
 166
 167 #define BIT_CLR_ATOMIC(_s, n, p)                                        \
 168         atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)],           \
 169             __bitset_mask((_s), n))
 170
 171 #define BIT_SET_ATOMIC(_s, n, p)                                        \
 172         atomic_set_long(&(p)->__bits[__bitset_word(_s, n)],             \
 173             __bitset_mask((_s), n))
 174
 175 #define BIT_SET_ATOMIC_ACQ(_s, n, p)                                    \
 176         atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)],         \
 177             __bitset_mask((_s), n))
 178
 179 /* Convenience functions catering special cases. */
 180 #define BIT_AND_ATOMIC(_s, d, s) do {                                   \
 181         __size_t __i;                                                   \
 182         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 183                 atomic_clear_long(&(d)->__bits[__i],                    \
 184                     ~(s)->__bits[__i]);                                 \
 185 } while (0)
 186
 187 #define BIT_OR_ATOMIC(_s, d, s) do {                                    \
 188         __size_t __i;                                                   \
 189         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 190                 atomic_set_long(&(d)->__bits[__i],                      \
 191                     (s)->__bits[__i]);                                  \
 192 } while (0)
 193
 194 #define BIT_COPY_STORE_REL(_s, f, t) do {                               \
 195         __size_t __i;                                                   \
 196         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 197                 atomic_store_rel_long(&(t)->__bits[__i],                \
 198                     (f)->__bits[__i]);                                  \
 199 } while (0)
 200
 201 #define BIT_FFS(_s, p) __extension__ ({                                 \
 202         __size_t __i;                                                   \
 203         int __bit;                                                      \
 204                                                                         \
 205         __bit = 0;                                                      \
 206         for (__i = 0; __i < __bitset_words((_s)); __i++) {              \
 207                 if ((p)->__bits[__i] != 0) {                            \
 208                         __bit = ffsl((p)->__bits[__i]);                 \
 209                         __bit += __i * _BITSET_BITS;                    \
 210                         break;                                          \
 211                 }                                                       \
 212         }                                                               \
 213         __bit;                                                          \
 214 })
 215
 216 #define BIT_FLS(_s, p) __extension__ ({                                 \
 217         __size_t __i;                                                   \
 218         int __bit;                                                      \
 219                                                                         \
 220         __bit = 0;                                                      \
 221         for (__i = __bitset_words((_s)); __i > 0; __i--) {              \
 222                 if ((p)->__bits[__i - 1] != 0) {                        \
 223                         __bit = flsl((p)->__bits[__i - 1]);             \
 224                         __bit += (__i - 1) * _BITSET_BITS;              \
 225                         break;                                          \
 226                 }                                                       \
 227         }                                                               \
 228         __bit;                                                          \
 229 })
 230
 231 #define BIT_COUNT(_s, p) __extension__ ({                               \
 232         __size_t __i;                                                   \
 233         int __count;                                                    \
 234                                                                         \
 235         __count = 0;                                                    \
 236         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 237                 __count += __bitcountl((p)->__bits[__i]);               \
 238         __count;                                                        \
 239 })
 240
 241 #define BITSET_T_INITIALIZER(x)                                         \
 242         { .__bits = { x } }
 243
 244 #define BITSET_FSET(n)                                                  \
 245         [ 0 ... ((n) - 1) ] = (-1L)
 246
 247 /*
 248  * Dynamically allocate a bitset.
 249  */
 250 #define BITSET_ALLOC(_s, mt, mf)                                        \
 251         malloc(__bitset_words(_s) * sizeof(long), mt, (mf))
 252
 253 #endif /* !_SYS_BITSET_H_ */