lib/bitarray.h

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