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 typedef u32 *bitarray_t;
  13 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
  14 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
  15
  16 static inline void
  17 bit_array_zero(bitarray_t a, uns n)
  18 {
  19   bzero(a, 4*BIT_ARRAY_WORDS(n));
  20 }
  21
  22 static inline void
  23 bit_array_set(bitarray_t a, uns i)
  24 {
  25   a[i/32] |= (1 << (i%32));
  26 }
  27
  28 static inline void
  29 bit_array_clear(bitarray_t a, uns i)
  30 {
  31   a[i/32] &= ~(1 << (i%32));
  32 }
  33
  34 static inline uns
  35 bit_array_isset(bitarray_t a, uns i)
  36 {
  37   return a[i/32] & (1 << (i%32));
  38 }
  39
  40 static inline uns
  41 bit_array_get(bitarray_t a, uns i)
  42 {
  43   return !! bit_array_isset(a, i);
  44 }
  45
  46 static inline uns
  47 bit_array_test_and_set(bitarray_t a, uns i)
  48 {
  49   uns t = bit_array_isset(a, i);
  50   bit_array_set(a, i);
  51   return t;
  52 }
  53
  54 static inline uns
  55 bit_array_test_and_clear(bitarray_t a, uns i)
  56 {
  57   uns t = bit_array_isset(a, i);
  58   bit_array_clear(a, i);
  59   return t;
  60 }
  61
  62 /* Iterate over all set bits, possibly destructively */
  63 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)                                 \
  64   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)            \
  65     for (uns var##_lo=0; ary[var##_hi]; var##_lo++)                             \
  66       if (ary[var##_hi] & (1 << var##_lo))                                      \
  67         {                                                                       \
  68           uns var = 32*var##_hi + var##_lo;                                     \
  69           ary[var##_hi] &= ~(1 << var##_lo);                                    \
  70           do
  71
  72 #define BIT_ARRAY_FISH_BITS_END                                                 \
  73           while (0);                                                            \
  74         }