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/bitstring.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  * Copyright (c) 1989, 1993
    3  *      The Regents of the University of California.  All rights reserved.
    4  *
    5  * This code is derived from software contributed to Berkeley by
    6  * Paul Vixie.
    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, this list of conditions and the following disclaimer.
   13  * 2. Redistributions in binary form must reproduce the above copyright
   14  *    notice, this list of conditions and the following disclaimer in the
   15  *    documentation and/or other materials provided with the distribution.
   16  * 4. Neither the name of the University nor the names of its contributors
   17  *    may be used to endorse or promote products derived from this software
   18  *    without specific prior written permission.
   19  *
   20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   30  * SUCH DAMAGE.
   31  *
   32  * Copyright (c) 2014 Spectra Logic Corporation
   33  * All rights reserved.
   34  *
   35  * Redistribution and use in source and binary forms, with or without
   36  * modification, are permitted provided that the following conditions
   37  * are met:
   38  * 1. Redistributions of source code must retain the above copyright
   39  *    notice, this list of conditions, and the following disclaimer,
   40  *    without modification.
   41  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
   42  *    substantially similar to the "NO WARRANTY" disclaimer below
   43  *    ("Disclaimer") and any redistribution must be conditioned upon
   44  *    including a substantially similar Disclaimer requirement for further
   45  *    binary redistribution.
   46  *
   47  * NO WARRANTY
   48  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   49  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   50  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
   51  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   52  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   53  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   54  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   55  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   56  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
   57  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   58  * POSSIBILITY OF SUCH DAMAGES.
   59  *
   60  * $FreeBSD: releng/11.1/sys/sys/bitstring.h 302180 2016-06-24 21:44:46Z asomers $
   61  */
   62 #ifndef _SYS_BITSTRING_H_
   63 #define _SYS_BITSTRING_H_
   64 
   65 #ifdef _KERNEL
   66 #include <sys/libkern.h>
   67 #include <sys/malloc.h>
   68 #endif
   69 
   70 #include <sys/types.h>
   71 
   72 typedef unsigned long bitstr_t;
   73 
   74 /*---------------------- Private Implementation Details ----------------------*/
   75 #define _BITSTR_MASK (~0UL)
   76 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
   77 
   78 #ifdef roundup2
   79 #define        _bit_roundup2 roundup2
   80 #else
   81 #define        _bit_roundup2(x, y)        (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
   82 #endif
   83 
   84 /* bitstr_t in bit string containing the bit. */
   85 static inline int
   86 _bit_idx(int _bit)
   87 {
   88         return (_bit / _BITSTR_BITS);
   89 }
   90 
   91 /* bit number within bitstr_t at _bit_idx(_bit). */
   92 static inline int
   93 _bit_offset(int _bit)
   94 {
   95         return (_bit % _BITSTR_BITS);
   96 }
   97 
   98 /* Mask for the bit within its long. */
   99 static inline bitstr_t
  100 _bit_mask(int _bit)
  101 {
  102         return (1UL << _bit_offset(_bit));
  103 }
  104 
  105 static inline bitstr_t
  106 _bit_make_mask(int _start, int _stop)
  107 {
  108         return ((_BITSTR_MASK << _bit_offset(_start)) &
  109             (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
  110 }
  111 
  112 /*----------------------------- Public Interface -----------------------------*/
  113 /* Number of bytes allocated for a bit string of nbits bits */
  114 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
  115 
  116 /* Allocate a bit string initialized with no bits set. */
  117 #ifdef _KERNEL
  118 static inline bitstr_t *
  119 bit_alloc(int _nbits, struct malloc_type *type, int flags)
  120 {
  121         return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
  122 }
  123 #else
  124 static inline bitstr_t *
  125 bit_alloc(int _nbits)
  126 {
  127         return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
  128 }
  129 #endif
  130 
  131 /* Allocate a bit string on the stack */
  132 #define bit_decl(name, nbits) \
  133         ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
  134 
  135 /* Is bit N of bit string set? */
  136 static inline int
  137 bit_test(const bitstr_t *_bitstr, int _bit)
  138 {
  139         return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
  140 }
  141 
  142 /* Set bit N of bit string. */
  143 static inline void
  144 bit_set(bitstr_t *_bitstr, int _bit)
  145 {
  146         _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
  147 }
  148 
  149 /* clear bit N of bit string name */
  150 static inline void
  151 bit_clear(bitstr_t *_bitstr, int _bit)
  152 {
  153         _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
  154 }
  155 
  156 /* Set bits start ... stop inclusive in bit string. */
  157 static inline void
  158 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
  159 {
  160         bitstr_t *_stopbitstr;
  161 
  162         _stopbitstr = _bitstr + _bit_idx(_stop);
  163         _bitstr += _bit_idx(_start);
  164 
  165         if (_bitstr == _stopbitstr) {
  166                 *_bitstr |= _bit_make_mask(_start, _stop);
  167         } else {
  168                 *_bitstr |= _bit_make_mask(_start, _BITSTR_BITS - 1);
  169                 while (++_bitstr < _stopbitstr)
  170                         *_bitstr = _BITSTR_MASK;
  171                 *_stopbitstr |= _bit_make_mask(0, _stop);
  172         }
  173 }
  174 
  175 /* Clear bits start ... stop inclusive in bit string. */
  176 static inline void
  177 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
  178 {
  179         bitstr_t *_stopbitstr;
  180 
  181         _stopbitstr = _bitstr + _bit_idx(_stop);
  182         _bitstr += _bit_idx(_start);
  183 
  184         if (_bitstr == _stopbitstr) {
  185                 *_bitstr &= ~_bit_make_mask(_start, _stop);
  186         } else {
  187                 *_bitstr &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
  188                 while (++_bitstr < _stopbitstr)
  189                         *_bitstr = 0;
  190                 *_stopbitstr &= ~_bit_make_mask(0, _stop);
  191         }
  192 }
  193 
  194 /* Find the first bit set in bit string at or after bit start. */
  195 static inline void
  196 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  197 {
  198         bitstr_t *_curbitstr;
  199         bitstr_t *_stopbitstr;
  200         bitstr_t _test;
  201         int _value, _offset;
  202 
  203         if (_nbits > 0) {
  204                 _curbitstr = _bitstr + _bit_idx(_start);
  205                 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
  206 
  207                 _test = *_curbitstr;
  208                 if (_bit_offset(_start) != 0)
  209                         _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
  210                 while (_test == 0 && _curbitstr < _stopbitstr)
  211                         _test = *(++_curbitstr);
  212 
  213                 _offset = ffsl(_test);
  214                 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
  215                 if (_offset == 0 || _value >= _nbits)
  216                         _value = -1;
  217         } else {
  218                 _value = -1;
  219         }
  220         *_result = _value;
  221 }
  222 
  223 /* Find the first bit clear in bit string at or after bit start. */
  224 static inline void
  225 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  226 {
  227         bitstr_t *_curbitstr;
  228         bitstr_t *_stopbitstr;
  229         bitstr_t _test;
  230         int _value, _offset;
  231 
  232         if (_nbits > 0) {
  233                 _curbitstr = _bitstr + _bit_idx(_start);
  234                 _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
  235 
  236                 _test = *_curbitstr;
  237                 if (_bit_offset(_start) != 0)
  238                         _test |= _bit_make_mask(0, _start - 1);
  239                 while (_test == _BITSTR_MASK && _curbitstr < _stopbitstr)
  240                         _test = *(++_curbitstr);
  241 
  242                 _offset = ffsl(~_test);
  243                 _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + _offset - 1;
  244                 if (_offset == 0 || _value >= _nbits)
  245                         _value = -1;
  246         } else {
  247                 _value = -1;
  248         }
  249         *_result = _value;
  250 }
  251 
  252 /* Find the first bit set in bit string. */
  253 static inline void
  254 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
  255 {
  256         bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
  257 }
  258 
  259 /* Find the first bit clear in bit string. */
  260 static inline void
  261 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
  262 {
  263         bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
  264 }
  265 
  266 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
  267 static inline void
  268 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  269 {
  270         bitstr_t *_curbitstr, mask;
  271         int _value = 0, curbitstr_len;
  272 
  273         if (_start >= _nbits)
  274                 goto out;
  275 
  276         _curbitstr = _bitstr + _bit_idx(_start);
  277         _nbits -= _BITSTR_BITS * _bit_idx(_start);
  278         _start -= _BITSTR_BITS * _bit_idx(_start);
  279 
  280         if (_start > 0) {
  281                 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
  282                                 (int)_BITSTR_BITS : _nbits;
  283                 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
  284                 _value += __bitcountl(*_curbitstr & mask);
  285                 _curbitstr++;
  286                 _nbits -= _BITSTR_BITS;
  287         }
  288         while (_nbits >= (int)_BITSTR_BITS) {
  289                 _value += __bitcountl(*_curbitstr);
  290                 _curbitstr++;
  291                 _nbits -= _BITSTR_BITS;
  292         }
  293         if (_nbits > 0) {
  294                 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
  295                 _value += __bitcountl(*_curbitstr & mask);
  296         }
  297 
  298 out:
  299         *_result = _value;
  300 }
  301 
  302 #endif  /* _SYS_BITSTRING_H_ */

Cache object: 417c983db0cb126ed708ecbfb37de4bf


[ 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.