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_AND(_s, d, s) do {                                          \
 126         __size_t __i;                                                   \
 127         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 128                 (d)->__bits[__i] &= (s)->__bits[__i];                   \
 129 } while (0)
 130
 131 #define BIT_NAND(_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_CLR_ATOMIC(_s, n, p)                                        \
 138         atomic_clear_long(&(p)->__bits[__bitset_word(_s, n)],           \
 139             __bitset_mask((_s), n))
 140
 141 #define BIT_SET_ATOMIC(_s, n, p)                                        \
 142         atomic_set_long(&(p)->__bits[__bitset_word(_s, n)],             \
 143             __bitset_mask((_s), n))
 144
 145 #define BIT_SET_ATOMIC_ACQ(_s, n, p)                                    \
 146         atomic_set_acq_long(&(p)->__bits[__bitset_word(_s, n)],         \
 147             __bitset_mask((_s), n))
 148
 149 /* Convenience functions catering special cases. */
 150 #define BIT_AND_ATOMIC(_s, d, s) do {                                   \
 151         __size_t __i;                                                   \
 152         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 153                 atomic_clear_long(&(d)->__bits[__i],                    \
 154                     ~(s)->__bits[__i]);                                 \
 155 } while (0)
 156
 157 #define BIT_OR_ATOMIC(_s, d, s) do {                                    \
 158         __size_t __i;                                                   \
 159         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 160                 atomic_set_long(&(d)->__bits[__i],                      \
 161                     (s)->__bits[__i]);                                  \
 162 } while (0)
 163
 164 #define BIT_COPY_STORE_REL(_s, f, t) do {                               \
 165         __size_t __i;                                                   \
 166         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 167                 atomic_store_rel_long(&(t)->__bits[__i],                \
 168                     (f)->__bits[__i]);                                  \
 169 } while (0)
 170
 171 #define BIT_FFS(_s, p) __extension__ ({                                 \
 172         __size_t __i;                                                   \
 173         int __bit;                                                      \
 174                                                                         \
 175         __bit = 0;                                                      \
 176         for (__i = 0; __i < __bitset_words((_s)); __i++) {              \
 177                 if ((p)->__bits[__i] != 0) {                            \
 178                         __bit = ffsl((p)->__bits[__i]);                 \
 179                         __bit += __i * _BITSET_BITS;                    \
 180                         break;                                          \
 181                 }                                                       \
 182         }                                                               \
 183         __bit;                                                          \
 184 })
 185
 186 #define BIT_COUNT(_s, p) __extension__ ({                               \
 187         __size_t __i;                                                   \
 188         int __count;                                                    \
 189                                                                         \
 190         __count = 0;                                                    \
 191         for (__i = 0; __i < __bitset_words((_s)); __i++)                \
 192                 __count += __bitcountl((p)->__bits[__i]);               \
 193         __count;                                                        \
 194 })
 195
 196 #define BITSET_T_INITIALIZER(x)                                         \
 197         { .__bits = { x } }
 198
 199 #define BITSET_FSET(n)                                                  \
 200         [ 0 ... ((n) - 1) ] = (-1L)
 201
 202 /*
 203  * Dynamically allocate a bitset.
 204  */
 205 #define BITSET_ALLOC(_s, mt, mf)                                        \
 206         malloc(__bitset_words(_s) * sizeof(long), mt, (mf))
 207
 208 #endif /* !_SYS_BITSET_H_ */