bitstring.h Source File

00001 /*
00002  * Copyright (c) 1989, 1993
00003  *      The Regents of the University of California.  All rights reserved.
00004  *
00005  * This code is derived from software contributed to Berkeley by
00006  * Paul Vixie.
00007  *
00008  * Redistribution and use in source and binary forms, with or without
00009  * modification, are permitted provided that the following conditions
00010  * are met:
00011  * 1. Redistributions of source code must retain the above copyright
00012  *    notice, this list of conditions and the following disclaimer.
00013  * 2. Redistributions in binary form must reproduce the above copyright
00014  *    notice, this list of conditions and the following disclaimer in the
00015  *    documentation and/or other materials provided with the distribution.
00016  * 3. All advertising materials mentioning features or use of this software
00017  *    must display the following acknowledgement:
00018  *      This product includes software developed by the University of
00019  *      California, Berkeley and its contributors.
00020  * 4. Neither the name of the University nor the names of its contributors
00021  *    may be used to endorse or promote products derived from this software
00022  *    without specific prior written permission.
00023  *
00024  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
00025  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
00026  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
00027  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
00028  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
00029  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
00030  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
00031  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
00032  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
00033  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
00034  * SUCH DAMAGE.
00035  *
00036  * $FreeBSD: src/sys/sys/bitstring.h,v 1.3 2003/06/13 19:40:13 phk Exp $
00037  */
00038 
00039 #ifndef _SYS_BITSTRING_H_
00040 #define _SYS_BITSTRING_H_
00041 
00042 typedef unsigned char bitstr_t;
00043 
00044 /* internal macros */
00045                                 /* byte of the bitstring bit is in */
00046 #define _bit_byte(bit) \
00047         ((bit) >> 3)
00048 
00049                                 /* mask for the bit within its byte */
00050 #define _bit_mask(bit) \
00051         (1 << ((bit)&0x7))
00052 
00053 /* external macros */
00054                                 /* bytes in a bitstring of nbits bits */
00055 #define bitstr_size(nbits) \
00056         (((nbits) + 7) >> 3)
00057 
00058                                 /* allocate a bitstring */
00059 #define bit_alloc(nbits) \
00060         (bitstr_t *)calloc((size_t)bitstr_size(nbits), sizeof(bitstr_t))
00061 
00062                                 /* allocate a bitstring on the stack */
00063 #define bit_decl(name, nbits) \
00064         ((name)[bitstr_size(nbits)])
00065 
00066                                 /* is bit N of bitstring name set? */
00067 #define bit_test(name, bit) \
00068         ((name)[_bit_byte(bit)] & _bit_mask(bit))
00069 
00070                                 /* set bit N of bitstring name */
00071 #define bit_set(name, bit) \
00072         ((name)[_bit_byte(bit)] |= _bit_mask(bit))
00073 
00074                                 /* clear bit N of bitstring name */
00075 #define bit_clear(name, bit) \
00076         ((name)[_bit_byte(bit)] &= ~_bit_mask(bit))
00077 
00078                                 /* clear bits start ... stop in bitstring */
00079 #define bit_nclear(name, start, stop) do { \
00080         register bitstr_t *_name = (name); \
00081         register int _start = (start), _stop = (stop); \
00082         register int _startbyte = _bit_byte(_start); \
00083         register int _stopbyte = _bit_byte(_stop); \
00084         if (_startbyte == _stopbyte) { \
00085                 _name[_startbyte] &= ((0xff >> (8 - (_start&0x7))) | \
00086                                       (0xff << ((_stop&0x7) + 1))); \
00087         } else { \
00088                 _name[_startbyte] &= 0xff >> (8 - (_start&0x7)); \
00089                 while (++_startbyte < _stopbyte) \
00090                         _name[_startbyte] = 0; \
00091                 _name[_stopbyte] &= 0xff << ((_stop&0x7) + 1); \
00092         } \
00093 } while (0)
00094 
00095                                 /* set bits start ... stop in bitstring */
00096 #define bit_nset(name, start, stop) do { \
00097         register bitstr_t *_name = (name); \
00098         register int _start = (start), _stop = (stop); \
00099         register int _startbyte = _bit_byte(_start); \
00100         register int _stopbyte = _bit_byte(_stop); \
00101         if (_startbyte == _stopbyte) { \
00102                 _name[_startbyte] |= ((0xff << (_start&0x7)) & \
00103                                     (0xff >> (7 - (_stop&0x7)))); \
00104         } else { \
00105                 _name[_startbyte] |= 0xff << ((_start)&0x7); \
00106                 while (++_startbyte < _stopbyte) \
00107                         _name[_startbyte] = 0xff; \
00108                 _name[_stopbyte] |= 0xff >> (7 - (_stop&0x7)); \
00109         } \
00110 } while (0)
00111 
00112                                 /* find first bit clear in name */
00113 #define bit_ffc(name, nbits, value) do { \
00114         register bitstr_t *_name = (name); \
00115         register int _byte, _nbits = (nbits); \
00116         register int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
00117         if (_nbits > 0) \
00118                 for (_byte = 0; _byte <= _stopbyte; ++_byte) \
00119                         if (_name[_byte] != 0xff) { \
00120                                 bitstr_t _lb; \
00121                                 _value = _byte << 3; \
00122                                 for (_lb = _name[_byte]; (_lb&0x1); \
00123                                     ++_value, _lb >>= 1); \
00124                                 break; \
00125                         } \
00126         if (_value >= nbits) \
00127                 _value = -1; \
00128         *(value) = _value; \
00129 } while (0)
00130 
00131                                 /* find first bit set in name */
00132 #define bit_ffs(name, nbits, value) do { \
00133         register bitstr_t *_name = (name); \
00134         register int _byte, _nbits = (nbits); \
00135         register int _stopbyte = _bit_byte(_nbits - 1), _value = -1; \
00136         if (_nbits > 0) \
00137                 for (_byte = 0; _byte <= _stopbyte; ++_byte) \
00138                         if (_name[_byte]) { \
00139                                 bitstr_t _lb; \
00140                                 _value = _byte << 3; \
00141                                 for (_lb = _name[_byte]; !(_lb&0x1); \
00142                                     ++_value, _lb >>= 1); \
00143                                 break; \
00144                         } \
00145         if (_value >= nbits) \
00146                 _value = -1; \
00147         *(value) = _value; \
00148 } while (0)
00149 
00150 #endif /* !_SYS_BITSTRING_H_ */