include/bitstring.h

   1 /*      $NetBSD: bitstring.h,v 1.9 2010/05/06 18:54:22 christos Exp $   */
   2
   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  *      @(#)bitstring.h 8.1 (Berkeley) 7/19/93
  35  */
  36
  37 #ifndef _BITSTRING_H_
  38 #define _BITSTRING_H_
  39
  40 /* modified for SV/AT and bitstring bugfix by M.R.Murphy, 11oct91
  41  * bitstr_size changed gratuitously, but shorter
  42  * bit_alloc   spelling error fixed
  43  * the following were efficient, but didn't work, they've been made to
  44  * work, but are no longer as efficient :-)
  45  * bit_nclear, bit_nset, bit_ffc, bit_ffs
  46  */
  47 /*
  48  * The comment above may or may not bear any resemblance to reality.
  49  * This code has been maintained in a confusing way, with little
  50  * information available on the provenance of much of it. "At least it
  51  * works."
  52  *  /s/ Perry E. Metzger, 2 Feb 98
  53  */
  54 typedef unsigned char bitstr_t;
  55
  56 /* internal macros */
  57                                 /* byte of the bitstring bit is in */
  58 #define _bit_byte(bit) \
  59         (uint32_t)((bit) >> 3)
  60
  61                                 /* mask for the bit within its byte */
  62 #define _bit_mask(bit) \
  63         (uint32_t)((1 << (uint32_t)((bit)&0x7)))
  64
  65 /* external macros */
  66                                 /* bytes in a bitstring of nbits bits */
  67 #define bitstr_size(nbits) \
  68         (size_t)((uint32_t)((nbits) + 7) >> 3)
  69
  70                                 /* allocate a bitstring */
  71 #define bit_alloc(nbits) \
  72         calloc(bitstr_size(nbits), sizeof(bitstr_t))
  73
  74                                 /* allocate a bitstring on the stack */
  75 #define bit_decl(name, nbits) \
  76         ((name)[bitstr_size(nbits)])
  77
  78                                 /* is bit N of bitstring name set? */
  79 #define bit_test(name, bit) \
  80         /*LINTED bitwise on signed*/((name)[_bit_byte(bit)] & _bit_mask(bit))
  81
  82                                 /* set bit N of bitstring name */
  83 #define bit_set(name, bit) \
  84         /*LINTED bitwise on signed*/((name)[_bit_byte(bit)] |= _bit_mask(bit))
  85
  86                                 /* clear bit N of bitstring name */
  87 #define bit_clear(name, bit) \
  88         /*LINTED bitwise on signed*/((name)[_bit_byte(bit)] &= ~_bit_mask(bit))
  89
  90                                 /* clear bits start ... stop in bitstring */
  91 #define bit_nclear(name, start, stop) do { \
  92         bitstr_t *_name = name; \
  93         int _start = start, _stop = stop; \
  94         while (_start <= _stop) { \
  95                 bit_clear(_name, _start); \
  96                 _start++; \
  97         } \
  98 } while(/*CONSTCOND*/0)
  99
 100                                 /* set bits start ... stop in bitstring */
 101 #define bit_nset(name, start, stop) do { \
 102         bitstr_t *_name = name; \
 103         int _start = start, _stop = stop; \
 104         while (_start <= _stop) { \
 105                 bit_set(_name, _start); \
 106                 _start++; \
 107         } \
 108 } while(/*CONSTCOND*/0)
 109
 110                                 /* find first bit clear in name */
 111 #define bit_ffc(name, nbits, value) do { \
 112         bitstr_t *_name = name; \
 113         int _bit, _nbits = nbits, _value = -1; \
 114         for (_bit = 0; _bit < _nbits; ++_bit) \
 115                 if (!bit_test(_name, _bit)) { \
 116                         _value = _bit; \
 117                         break; \
 118                 } \
 119         *(value) = _value; \
 120 } while(/*CONSTCOND*/0)
 121
 122                                 /* find first bit set in name */
 123 #define bit_ffs(name, nbits, value) do { \
 124         bitstr_t *_name = name; \
 125         int _bit, _nbits = nbits, _value = -1; \
 126         for (_bit = 0; _bit < _nbits; ++_bit) \
 127                 if (bit_test(_name, _bit)) { \
 128                         _value = _bit; \
 129                         break; \
 130                 } \
 131         *(value) = _value; \
 132 } while(/*CONSTCOND*/0)
 133
 134 #endif /* !_BITSTRING_H_ */