sys/sys/bitstring.h

   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  * 3. 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  * $FreeBSD: src/include/bitstring.h,v 1.1.1.1.14.1 2000/10/30 11:21:04 dwmalone Exp $
  33  */
  34
  35 #ifndef _SYS_BITSTRING_H_
  36 #define _SYS_BITSTRING_H_
  37
  38 typedef unsigned char bitstr_t;
  39
  40 /* internal macros */
  41                                 /* byte of the bitstring bit is in */
  42 #define _bit_byte(bit) \
  43         ((bit) >> 3)
  44
  45                                 /* mask for the bit within its byte */
  46 #define _bit_mask(bit) \
  47         (1 << ((bit)&0x7))
  48
  49 /* external macros */
  50                                 /* bytes in a bitstring of nbits bits */
  51 #define bitstr_size(nbits) \
  52         (((nbits) + 7) >> 3)
  53
  54                                 /* allocate a bitstring */
  55 #define bit_alloc(nbits) \
  56         (bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t))
  57
  58                                 /* allocate a bitstring on the stack */
  59 #define bit_decl(name, nbits) \
  60         ((name)[bitstr_size(nbits)])
  61
  62                                 /* is bit N of bitstring name set? */
  63 #define bit_test(name, bit) \
  64         ((name)[_bit_byte(bit)] & _bit_mask(bit))
  65
  66                                 /* set bit N of bitstring name */
  67 #define bit_set(name, bit) \
  68         ((name)[_bit_byte(bit)] |= _bit_mask(bit))
  69
  70                                 /* clear bit N of bitstring name */
  71 #define bit_clear(name, bit) \
  72         ((name)[_bit_byte(bit)] &= ~_bit_mask(bit))
  73
  74                                 /* clear bits start ... stop in bitstring */
  75 #define bit_nclear(name, start, stop) do { \
  76         bitstr_t *_name = (name); \
  77         int _start = (start), _stop = (stop); \
  78         int _startbyte = _bit_byte(_start); \
  79         int _stopbyte = _bit_byte(_stop); \
  80         if (_startbyte == _stopbyte) { \
  81                 _name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \
  82                                       (0xff << ((_stop&0x7) + 1))); \
  83         } else { \
  84                 _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \
  85                 while (++_startbyte < _stopbyte) \
  86                         _name[_startbyte] = 0; \
  87                 _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \
  88         } \
  89 } while (0)
  90
  91                                 /* set bits start ... stop in bitstring */
  92 #define bit_nset(name, start, stop) do { \
  93         bitstr_t *_name = (name); \
  94         int _start = (start), _stop = (stop); \
  95         int _startbyte = _bit_byte(_start); \
  96         int _stopbyte = _bit_byte(_stop); \
  97         if (_startbyte == _stopbyte) { \
  98                 _name[_startbyte] |= ((0xff << (_start&0x7)) & \
  99                                     (0xff >> (7 - (_stop&0x7)))); \
 100         } else { \
 101                 _name[_startbyte] |= 0xff << ((_start)&0x7); \
 102                 while (++_startbyte < _stopbyte) \
 103                         _name[_startbyte] = 0xff; \
 104                 _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \
 105         } \
 106 } while (0)
 107
 108                                 /* find first bit clear in name */
 109 #define bit_ffc(name, nbits, value) do { \
 110         bitstr_t *_name = (name); \
 111         int _byte, _nbits = (nbits); \
 112         int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
 113         if (_nbits > 0) \
 114                 for (_byte = 0; _byte <= _stopbyte; ++_byte) \
 115                         if (_name[_byte] != 0xff) { \
 116                                 bitstr_t _lb; \
 117                                 _value = _byte << 3; \
 118                                 for (_lb = _name[_byte]; (_lb&0x1); \
 119                                     ++_value, _lb >>= 1); \
 120                                 break; \
 121                         } \
 122         if (_value >= nbits) \
 123                 _value = -1; \
 124         *(value) = _value; \
 125 } while (0)
 126
 127                                 /* find first bit set in name */
 128 #define bit_ffs(name, nbits, value) do { \
 129         bitstr_t *_name = (name); \
 130         int _byte, _nbits = (nbits); \
 131         int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
 132         if (_nbits > 0) \
 133                 for (_byte = 0; _byte <= _stopbyte; ++_byte) \
 134                         if (_name[_byte]) { \
 135                                 bitstr_t _lb; \
 136                                 _value = _byte << 3; \
 137                                 for (_lb = _name[_byte]; !(_lb&0x1); \
 138                                     ++_value, _lb >>= 1); \
 139                                 break; \
 140                         } \
 141         if (_value >= nbits) \
 142                 _value = -1; \
 143         *(value) = _value; \
 144 } while (0)
 145
 146                                 /* find last bit set in name */
 147 #define bit_fls(name, nbits, value) do { \
 148         bitstr_t *_name = (name); \
 149         int _byte, _nbits = (nbits); \
 150         int _startbyte = _bit_byte(_nbits - 1), _value = -1; \
 151         if (_nbits > 0) \
 152                 for (_byte = _startbyte; _byte >= 0; --_byte) \
 153                         if (_name[_byte]) { \
 154                                 bitstr_t _lb; \
 155                                 _value = _byte << 3; \
 156                                 for (_lb = _name[_byte]; _lb != 0x1; \
 157                                     ++_value, _lb >>= 1); \
 158                                 break; \
 159                         } \
 160         if (_value >= nbits) \
 161                 _value = -1; \
 162         *(value) = _value; \
 163 } while (0)
 164
 165                                 /* find clear range of length len */
 166 #define bit_nsearch(name, nbits, value, len) do { \
 167         bitstr_t *_name = (name); \
 168         int _nbits = (nbits); \
 169         int *_value = (value); \
 170         int _len = (len); \
 171         int _bit, _bit0 = -1; \
 172         int _tmplen = _len; \
 173         int _match = 0; \
 174         *(_value) = -1; \
 175         for (_bit = 0; _bit < _nbits && _tmplen > 0; _bit++) { \
 176                 if (_match == 0) { \
 177                         if (bit_test((_name), _bit) == 0) { \
 178                                 _match = 1; \
 179                                 _tmplen--; \
 180                                 _bit0 = _bit; \
 181                         } \
 182                 } else { \
 183                         if (bit_test((_name), _bit) == 0) { \
 184                                 _tmplen--; \
 185                         } else { \
 186                                 _match = 0; \
 187                                 _tmplen = _len; \
 188                         } \
 189                 } \
 190         } \
 191         if (_tmplen == 0) \
 192                 *(_value) = _bit0; \
 193 } while (0)
 194
 195 #endif /* !_SYS_BITSTRING_H_ */