The Design and Implementation of the FreeBSD Operating System, Second Edition
Now available: The Design and Implementation of the FreeBSD Operating System (Second Edition)


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]

FreeBSD/Linux Kernel Cross Reference
sys/sys/bitset.h

Version: -  FREEBSD  -  FREEBSD-13-STABLE  -  FREEBSD-13-0  -  FREEBSD-12-STABLE  -  FREEBSD-12-0  -  FREEBSD-11-STABLE  -  FREEBSD-11-0  -  FREEBSD-10-STABLE  -  FREEBSD-10-0  -  FREEBSD-9-STABLE  -  FREEBSD-9-0  -  FREEBSD-8-STABLE  -  FREEBSD-8-0  -  FREEBSD-7-STABLE  -  FREEBSD-7-0  -  FREEBSD-6-STABLE  -  FREEBSD-6-0  -  FREEBSD-5-STABLE  -  FREEBSD-5-0  -  FREEBSD-4-STABLE  -  FREEBSD-3-STABLE  -  FREEBSD22  -  l41  -  OPENBSD  -  linux-2.6  -  MK84  -  PLAN9  -  xnu-8792 
SearchContext: -  none  -  3  -  10 

    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         (1UL << ((__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_ */

Cache object: f917a8656776355250b1386169764470


[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]


This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.