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