ucw/bitarray.h

   1 /*
   2  *      UCW Library -- Bit Array Operations
   3  *
   4  *      (c) 2003--2006 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 #ifndef _UCW_BITARRAY_H
  11 #define _UCW_BITARRAY_H
  12
  13 #include <string.h>
  14
  15 typedef u32 *bitarray_t;
  16 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
  17 #define BIT_ARRAY_BYTES(n) (4*BIT_ARRAY_WORDS(n))
  18 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
  19
  20 static inline bitarray_t
  21 bit_array_xmalloc(uns n)
  22 {
  23   return xmalloc(BIT_ARRAY_BYTES(n));
  24 }
  25
  26 static inline bitarray_t
  27 bit_array_xmalloc_zero(uns n)
  28 {
  29   return xmalloc_zero(BIT_ARRAY_BYTES(n));
  30 }
  31
  32 static inline void
  33 bit_array_zero(bitarray_t a, uns n)
  34 {
  35   bzero(a, BIT_ARRAY_BYTES(n));
  36 }
  37
  38 static inline void
  39 bit_array_set_all(bitarray_t a, uns n)
  40 {
  41   memset(a, 255, BIT_ARRAY_BYTES(n));
  42 }
  43
  44 static inline void
  45 bit_array_set(bitarray_t a, uns i)
  46 {
  47   a[i/32] |= (1 << (i%32));
  48 }
  49
  50 static inline void
  51 bit_array_clear(bitarray_t a, uns i)
  52 {
  53   a[i/32] &= ~(1 << (i%32));
  54 }
  55
  56 static inline void
  57 bit_array_assign(bitarray_t a, uns i, uns x)
  58 {
  59   if (x)
  60     bit_array_set(a, i);
  61   else
  62     bit_array_clear(a, i);
  63 }
  64
  65 static inline uns
  66 bit_array_isset(bitarray_t a, uns i)
  67 {
  68   return a[i/32] & (1 << (i%32));
  69 }
  70
  71 static inline uns
  72 bit_array_get(bitarray_t a, uns i)
  73 {
  74   return !! bit_array_isset(a, i);
  75 }
  76
  77 static inline uns
  78 bit_array_test_and_set(bitarray_t a, uns i)
  79 {
  80   uns t = bit_array_isset(a, i);
  81   bit_array_set(a, i);
  82   return t;
  83 }
  84
  85 static inline uns
  86 bit_array_test_and_clear(bitarray_t a, uns i)
  87 {
  88   uns t = bit_array_isset(a, i);
  89   bit_array_clear(a, i);
  90   return t;
  91 }
  92
  93 /* Iterate over all set bits, possibly destructively */
  94 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)                                 \
  95   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)            \
  96     for (uns var##_lo=0; ary[var##_hi]; var##_lo++)                             \
  97       if (ary[var##_hi] & (1 << var##_lo))                                      \
  98         {                                                                       \
  99           uns var = 32*var##_hi + var##_lo;                                     \
 100           ary[var##_hi] &= ~(1 << var##_lo);                                    \
 101           do
 102
 103 #define BIT_ARRAY_FISH_BITS_END                                                 \
 104           while (0);                                                            \
 105         }
 106
 107 #endif