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  * SPDX-License-Identifier: BSD-3-Clause
    3  *
    4  * Copyright (c) 1989, 1993
    5  *      The Regents of the University of California.  All rights reserved.
    6  *
    7  * This code is derived from software contributed to Berkeley by
    8  * Paul Vixie.
    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, this list of conditions and the following disclaimer.
   15  * 2. Redistributions in binary form must reproduce the above copyright
   16  *    notice, this list of conditions and the following disclaimer in the
   17  *    documentation and/or other materials provided with the distribution.
   18  * 3. Neither the name of the University nor the names of its contributors
   19  *    may be used to endorse or promote products derived from this software
   20  *    without specific prior written permission.
   21  *
   22  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
   23  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
   24  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
   25  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
   26  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   27  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   28  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   29  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
   30  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
   31  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
   32  * SUCH DAMAGE.
   33  *
   34  * Copyright (c) 2014 Spectra Logic Corporation
   35  * All rights reserved.
   36  *
   37  * Redistribution and use in source and binary forms, with or without
   38  * modification, are permitted provided that the following conditions
   39  * are met:
   40  * 1. Redistributions of source code must retain the above copyright
   41  *    notice, this list of conditions, and the following disclaimer,
   42  *    without modification.
   43  * 2. Redistributions in binary form must reproduce at minimum a disclaimer
   44  *    substantially similar to the "NO WARRANTY" disclaimer below
   45  *    ("Disclaimer") and any redistribution must be conditioned upon
   46  *    including a substantially similar Disclaimer requirement for further
   47  *    binary redistribution.
   48  *
   49  * NO WARRANTY
   50  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
   51  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
   52  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR
   53  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
   54  * HOLDERS OR CONTRIBUTORS BE LIABLE FOR SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
   55  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
   56  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
   57  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
   58  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING
   59  * IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
   60  * POSSIBILITY OF SUCH DAMAGES.
   61  *
   62  * $FreeBSD$
   63  */
   64 #ifndef _SYS_BITSTRING_H_
   65 #define _SYS_BITSTRING_H_
   66 
   67 #ifdef _KERNEL
   68 #include <sys/libkern.h>
   69 #include <sys/malloc.h>
   70 #endif
   71 
   72 #include <sys/types.h>
   73 
   74 typedef unsigned long bitstr_t;
   75 
   76 /*---------------------- Private Implementation Details ----------------------*/
   77 #define _BITSTR_MASK (~0UL)
   78 #define _BITSTR_BITS (sizeof(bitstr_t) * 8)
   79 
   80 #ifdef roundup2
   81 #define        _bit_roundup2 roundup2
   82 #else
   83 #define        _bit_roundup2(x, y)        (((x)+((y)-1))&(~((y)-1))) /* if y is powers of two */
   84 #endif
   85 
   86 /* bitstr_t in bit string containing the bit. */
   87 static inline int
   88 _bit_idx(int _bit)
   89 {
   90         return (_bit / _BITSTR_BITS);
   91 }
   92 
   93 /* bit number within bitstr_t at _bit_idx(_bit). */
   94 static inline int
   95 _bit_offset(int _bit)
   96 {
   97         return (_bit % _BITSTR_BITS);
   98 }
   99 
  100 /* Mask for the bit within its long. */
  101 static inline bitstr_t
  102 _bit_mask(int _bit)
  103 {
  104         return (1UL << _bit_offset(_bit));
  105 }
  106 
  107 static inline bitstr_t
  108 _bit_make_mask(int _start, int _stop)
  109 {
  110         return ((_BITSTR_MASK << _bit_offset(_start)) &
  111             (_BITSTR_MASK >> (_BITSTR_BITS - _bit_offset(_stop) - 1)));
  112 }
  113 
  114 /*----------------------------- Public Interface -----------------------------*/
  115 /* Number of bytes allocated for a bit string of nbits bits */
  116 #define bitstr_size(_nbits) (_bit_roundup2(_nbits, _BITSTR_BITS) / 8)
  117 
  118 /* Allocate a bit string initialized with no bits set. */
  119 #ifdef _KERNEL
  120 static inline bitstr_t *
  121 bit_alloc(int _nbits, struct malloc_type *type, int flags)
  122 {
  123         return ((bitstr_t *)malloc(bitstr_size(_nbits), type, flags | M_ZERO));
  124 }
  125 #else
  126 static inline bitstr_t *
  127 bit_alloc(int _nbits)
  128 {
  129         return ((bitstr_t *)calloc(bitstr_size(_nbits), 1));
  130 }
  131 #endif
  132 
  133 /* Allocate a bit string on the stack */
  134 #define bit_decl(name, nbits) \
  135         ((name)[bitstr_size(nbits) / sizeof(bitstr_t)])
  136 
  137 /* Is bit N of bit string set? */
  138 static inline int
  139 bit_test(const bitstr_t *_bitstr, int _bit)
  140 {
  141         return ((_bitstr[_bit_idx(_bit)] & _bit_mask(_bit)) != 0);
  142 }
  143 
  144 /* Set bit N of bit string. */
  145 static inline void
  146 bit_set(bitstr_t *_bitstr, int _bit)
  147 {
  148         _bitstr[_bit_idx(_bit)] |= _bit_mask(_bit);
  149 }
  150 
  151 /* clear bit N of bit string name */
  152 static inline void
  153 bit_clear(bitstr_t *_bitstr, int _bit)
  154 {
  155         _bitstr[_bit_idx(_bit)] &= ~_bit_mask(_bit);
  156 }
  157 
  158 /* Are bits in [start ... stop] in bit string all 0 or all 1? */
  159 static inline int
  160 bit_ntest(const bitstr_t *_bitstr, int _start, int _stop, int _match)
  161 {
  162         const bitstr_t *_stopbitstr;
  163         bitstr_t _mask;
  164 
  165         _mask = (_match == 0) ? 0 : _BITSTR_MASK;
  166         _stopbitstr = _bitstr + _bit_idx(_stop);
  167         _bitstr += _bit_idx(_start);
  168 
  169         if (_bitstr == _stopbitstr)
  170                 return (0 == ((*_bitstr ^ _mask) &
  171                     _bit_make_mask(_start, _stop)));
  172         if (_bit_offset(_start) != 0 &&
  173             0 != ((*_bitstr++ ^ _mask) &
  174             _bit_make_mask(_start, _BITSTR_BITS - 1)))
  175                 return (0);
  176         if (_bit_offset(_stop) == _BITSTR_BITS - 1)
  177                 ++_stopbitstr;
  178         while (_bitstr < _stopbitstr) {
  179                 if (*_bitstr++ != _mask)
  180                         return (0);
  181         }
  182         return (_bit_offset(_stop) == _BITSTR_BITS - 1 ||
  183             0 == ((*_stopbitstr ^ _mask) & _bit_make_mask(0, _stop)));
  184 }
  185 
  186 /* Set bits start ... stop inclusive in bit string. */
  187 static inline void
  188 bit_nset(bitstr_t *_bitstr, int _start, int _stop)
  189 {
  190         bitstr_t *_stopbitstr;
  191 
  192         _stopbitstr = _bitstr + _bit_idx(_stop);
  193         _bitstr += _bit_idx(_start);
  194 
  195         if (_bitstr == _stopbitstr) {
  196                 *_bitstr |= _bit_make_mask(_start, _stop);
  197         } else {
  198                 if (_bit_offset(_start) != 0)
  199                         *_bitstr++ |= _bit_make_mask(_start, _BITSTR_BITS - 1);
  200                 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
  201                         ++_stopbitstr;
  202                 while (_bitstr < _stopbitstr)
  203                         *_bitstr++ = _BITSTR_MASK;
  204                 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
  205                         *_stopbitstr |= _bit_make_mask(0, _stop);
  206         }
  207 }
  208 
  209 /* Clear bits start ... stop inclusive in bit string. */
  210 static inline void
  211 bit_nclear(bitstr_t *_bitstr, int _start, int _stop)
  212 {
  213         bitstr_t *_stopbitstr;
  214 
  215         _stopbitstr = _bitstr + _bit_idx(_stop);
  216         _bitstr += _bit_idx(_start);
  217 
  218         if (_bitstr == _stopbitstr) {
  219                 *_bitstr &= ~_bit_make_mask(_start, _stop);
  220         } else {
  221                 if (_bit_offset(_start) != 0)
  222                         *_bitstr++ &= ~_bit_make_mask(_start, _BITSTR_BITS - 1);
  223                 if (_bit_offset(_stop) == _BITSTR_BITS - 1)
  224                         ++_stopbitstr;
  225                 while (_bitstr < _stopbitstr)
  226                         *_bitstr++ = 0;
  227                 if (_bit_offset(_stop) != _BITSTR_BITS - 1)
  228                         *_stopbitstr &= ~_bit_make_mask(0, _stop);
  229         }
  230 }
  231 
  232 /* Find the first '_match'-bit in bit string at or after bit start. */
  233 static inline void
  234 bit_ff_at(bitstr_t *_bitstr, int _start, int _nbits, int _match,
  235     int *_result)
  236 {
  237         bitstr_t *_curbitstr;
  238         bitstr_t *_stopbitstr;
  239         bitstr_t _mask;
  240         bitstr_t _test;
  241         int _value;
  242 
  243         if (_start >= _nbits || _nbits <= 0) {
  244                 *_result = -1;
  245                 return;
  246         }
  247 
  248         _curbitstr = _bitstr + _bit_idx(_start);
  249         _stopbitstr = _bitstr + _bit_idx(_nbits - 1);
  250         _mask = _match ? 0 : _BITSTR_MASK;
  251 
  252         _test = _mask ^ *_curbitstr;
  253         if (_bit_offset(_start) != 0)
  254                 _test &= _bit_make_mask(_start, _BITSTR_BITS - 1);
  255         while (_test == 0 && _curbitstr < _stopbitstr)
  256                 _test = _mask ^ *(++_curbitstr);
  257 
  258         _value = ((_curbitstr - _bitstr) * _BITSTR_BITS) + ffsl(_test) - 1;
  259         if (_test == 0 ||
  260             (_bit_offset(_nbits) != 0 && _value >= _nbits))
  261                 _value = -1;
  262         *_result = _value;
  263 }
  264 
  265 /* Find the first bit set in bit string at or after bit start. */
  266 static inline void
  267 bit_ffs_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  268 {
  269         bit_ff_at(_bitstr, _start, _nbits, 1, _result);
  270 }
  271 
  272 /* Find the first bit clear in bit string at or after bit start. */
  273 static inline void
  274 bit_ffc_at(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  275 {
  276         bit_ff_at(_bitstr, _start, _nbits, 0, _result);
  277 }
  278 
  279 /* Find the first bit set in bit string. */
  280 static inline void
  281 bit_ffs(bitstr_t *_bitstr, int _nbits, int *_result)
  282 {
  283         bit_ffs_at(_bitstr, /*start*/0, _nbits, _result);
  284 }
  285 
  286 /* Find the first bit clear in bit string. */
  287 static inline void
  288 bit_ffc(bitstr_t *_bitstr, int _nbits, int *_result)
  289 {
  290         bit_ffc_at(_bitstr, /*start*/0, _nbits, _result);
  291 }
  292 
  293 /* Find contiguous sequence of at least size '_match'-bits at or after start */
  294 static inline void
  295 bit_ff_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
  296     int _match, int *_result)
  297 {
  298         bitstr_t *_curbitstr, _mask, _test;
  299         int _value, _last, _shft, _maxshft;
  300 
  301         if (_start + _size > _nbits || _nbits <= 0) {
  302                 *_result = -1;
  303                 return;
  304         }
  305 
  306         _mask = _match ? _BITSTR_MASK : 0;
  307         _maxshft = _bit_idx(_size - 1) == 0 ? _size : (int)_BITSTR_BITS;
  308         _value = _start;
  309         _curbitstr = _bitstr + _bit_idx(_start);
  310         _test = ~(_BITSTR_MASK << _bit_offset(_start));
  311         for (_last = _size - 1, _test |= _mask ^ *_curbitstr;
  312             !(_bit_idx(_last) == 0 &&
  313             (_test & _bit_make_mask(0, _last)) == 0);
  314             _last -= _BITSTR_BITS, _test = _mask ^ *++_curbitstr) {
  315                 if (_test == 0)
  316                         continue;
  317                 /* Shrink-left every 0-area in _test by maxshft-1 bits. */
  318                 for (_shft = _maxshft; _shft > 1 && (_test & (_test + 1)) != 0;
  319                      _shft = (_shft + 1) / 2)
  320                         _test |= _test >> _shft / 2;
  321                 /* Find the start of the first 0-area in _test. */
  322                 _last = ffsl(~(_test >> 1));
  323                 _value = (_curbitstr - _bitstr) * _BITSTR_BITS + _last;
  324                 /* If there's insufficient space left, give up. */
  325                 if (_value + _size > _nbits) {
  326                         _value = -1;
  327                         break;
  328                 }
  329                 _last += _size - 1;
  330                 /* If a solution is contained in _test, success! */
  331                 if (_bit_idx(_last) == 0)
  332                         break;
  333                 /* A solution here needs bits from the next word. */
  334         }
  335         *_result = _value;
  336 }
  337 
  338 /* Find contiguous sequence of at least size set bits at or after start */
  339 static inline void
  340 bit_ffs_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
  341     int *_result)
  342 {
  343         bit_ff_area_at(_bitstr, _start, _nbits, _size, 1, _result);
  344 }
  345 
  346 /* Find contiguous sequence of at least size cleared bits at or after start */
  347 static inline void
  348 bit_ffc_area_at(bitstr_t *_bitstr, int _start, int _nbits, int _size,
  349     int *_result)
  350 {
  351         bit_ff_area_at(_bitstr, _start, _nbits, _size, 0, _result);
  352 }
  353 
  354 /* Find contiguous sequence of at least size set bits in bit string */
  355 static inline void
  356 bit_ffs_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
  357 {
  358         bit_ffs_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
  359 }
  360 
  361 /* Find contiguous sequence of at least size cleared bits in bit string */
  362 static inline void
  363 bit_ffc_area(bitstr_t *_bitstr, int _nbits, int _size, int *_result)
  364 {
  365         bit_ffc_area_at(_bitstr, /*start*/0, _nbits, _size, _result);
  366 }
  367 
  368 /* Count the number of bits set in a bitstr of size _nbits at or after _start */
  369 static inline void
  370 bit_count(bitstr_t *_bitstr, int _start, int _nbits, int *_result)
  371 {
  372         bitstr_t *_curbitstr, mask;
  373         int _value = 0, curbitstr_len;
  374 
  375         if (_start >= _nbits)
  376                 goto out;
  377 
  378         _curbitstr = _bitstr + _bit_idx(_start);
  379         _nbits -= _BITSTR_BITS * _bit_idx(_start);
  380         _start -= _BITSTR_BITS * _bit_idx(_start);
  381 
  382         if (_start > 0) {
  383                 curbitstr_len = (int)_BITSTR_BITS < _nbits ?
  384                                 (int)_BITSTR_BITS : _nbits;
  385                 mask = _bit_make_mask(_start, _bit_offset(curbitstr_len - 1));
  386                 _value += __bitcountl(*_curbitstr & mask);
  387                 _curbitstr++;
  388                 _nbits -= _BITSTR_BITS;
  389         }
  390         while (_nbits >= (int)_BITSTR_BITS) {
  391                 _value += __bitcountl(*_curbitstr);
  392                 _curbitstr++;
  393                 _nbits -= _BITSTR_BITS;
  394         }
  395         if (_nbits > 0) {
  396                 mask = _bit_make_mask(0, _bit_offset(_nbits - 1));
  397                 _value += __bitcountl(*_curbitstr & mask);
  398         }
  399 
  400 out:
  401         *_result = _value;
  402 }
  403 
  404 /* Traverse all set bits, assigning each location in turn to iter */
  405 #define bit_foreach_at(_bitstr, _start, _nbits, _iter)                  \
  406         for (bit_ffs_at((_bitstr), (_start), (_nbits), &(_iter));       \
  407              (_iter) != -1;                                             \
  408              bit_ffs_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
  409 #define bit_foreach(_bitstr, _nbits, _iter)                             \
  410         bit_foreach_at(_bitstr, /*start*/0, _nbits, _iter)
  411 
  412 /* Traverse all unset bits, assigning each location in turn to iter */
  413 #define bit_foreach_unset_at(_bitstr, _start, _nbits, _iter)            \
  414         for (bit_ffc_at((_bitstr), (_start), (_nbits), &(_iter));       \
  415              (_iter) != -1;                                             \
  416              bit_ffc_at((_bitstr), (_iter) + 1, (_nbits), &(_iter)))
  417 #define bit_foreach_unset(_bitstr, _nbits, _iter)                       \
  418         bit_foreach_unset_at(_bitstr, /*start*/0, _nbits, _iter)
  419 
  420 #endif  /* _SYS_BITSTRING_H_ */

Cache object: 7fb2b49372fe2cef50cd5642193d01cb


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