lib/bitarray.h

   1 /*
   2  *      Bit Array Operations
   3  *
   4  *      (c) 2003 Martin Mares <mj@ucw.cz>
   5  *
   6  *      This software may be freely distributed and used according to the terms
   7  *      of the GNU Lesser General Public License.
   8  */
   9
  10 #include <string.h>
  11
  12 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
  13 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
  14
  15 static inline void
  16 bit_array_zero(u32 *a, uns n)
  17 {
  18   bzero(a, 4*BIT_ARRAY_WORDS(n));
  19 }
  20
  21 static inline void
  22 bit_array_set(u32 *a, uns i)
  23 {
  24   a[i/32] |= (1 << (i%32));
  25 }
  26
  27 static inline void
  28 bit_array_clear(u32 *a, uns i)
  29 {
  30   a[i/32] &= ~(1 << (i%32));
  31 }
  32
  33 static inline uns
  34 bit_array_isset(u32 *a, uns i)
  35 {
  36   return a[i/32] & (1 << (i%32));
  37 }
  38
  39 static inline uns
  40 bit_array_get(u32 *a, uns i)
  41 {
  42   return !! bit_array_isset(a, i);
  43 }
  44
  45 static inline uns
  46 bit_array_test_and_set(u32 *a, uns i)
  47 {
  48   uns t = bit_array_isset(a, i);
  49   bit_array_set(a, i);
  50   return t;
  51 }
  52
  53 static inline uns
  54 bit_array_test_and_clear(u32 *a, uns i)
  55 {
  56   uns t = bit_array_isset(a, i);
  57   bit_array_clear(a, i);
  58   return t;
  59 }
  60
  61 /* Iterate over all set bits, possibly destructively */
  62 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)                                 \
  63   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)            \
  64     for (uns var##_lo=0; ary[var##_hi]; var##_lo++)                             \
  65       if (ary[var##_hi] & (1 << var##_lo))                                      \
  66         {                                                                       \
  67           uns var = 32*var##_hi + var##_lo;                                     \
  68           ary[var##_hi] &= ~(1 << var##_lo);                                    \
  69           do
  70
  71 #define BIT_ARRAY_FISH_BITS_END                                                 \
  72           while (0);                                                            \
  73         }