ucw/bitarray.h

   1 /*
   2  *      UCW Library -- Bit Array Operations
   3  *
   4  *      (c) 2003--2006 Martin Mares <mj@ucw.cz>
   5  *      (c) 2012 Pavel Charvat <pchar@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 #ifndef _UCW_BITARRAY_H
  12 #define _UCW_BITARRAY_H
  13
  14 #include <string.h>
  15
  16 typedef u32 *bitarray_t; // Must be initialized by bit_array_xmalloc(), bit_array_zero() or bit_array_set_all()
  17
  18 #define BIT_ARRAY_WORDS(n) (((n)+31)/32)
  19 #define BIT_ARRAY_BYTES(n) (4*BIT_ARRAY_WORDS(n))
  20 #define BIT_ARRAY(name,size) u32 name[BIT_ARRAY_WORDS(size)]
  21
  22 static inline bitarray_t
  23 bit_array_xmalloc(uns n)
  24 {
  25   return xmalloc(BIT_ARRAY_BYTES(n));
  26 }
  27
  28 bitarray_t bit_array_xrealloc(bitarray_t a, uns old_n, uns new_n);
  29
  30 static inline bitarray_t
  31 bit_array_xmalloc_zero(uns n)
  32 {
  33   return xmalloc_zero(BIT_ARRAY_BYTES(n));
  34 }
  35
  36 static inline void
  37 bit_array_zero(bitarray_t a, uns n)
  38 {
  39   bzero(a, BIT_ARRAY_BYTES(n));
  40 }
  41
  42 static inline void
  43 bit_array_set_all(bitarray_t a, uns n)
  44 {
  45   uns w = n / 32;
  46   memset(a, 255, w * 4);
  47   uns m = n & 31;
  48   if (m)
  49     a[w] = (1U << m) - 1;
  50 }
  51
  52 static inline void
  53 bit_array_set(bitarray_t a, uns i)
  54 {
  55   a[i/32] |= (1 << (i%32));
  56 }
  57
  58 static inline void
  59 bit_array_clear(bitarray_t a, uns i)
  60 {
  61   a[i/32] &= ~(1 << (i%32));
  62 }
  63
  64 static inline void
  65 bit_array_assign(bitarray_t a, uns i, uns x)
  66 {
  67   if (x)
  68     bit_array_set(a, i);
  69   else
  70     bit_array_clear(a, i);
  71 }
  72
  73 static inline uns
  74 bit_array_isset(bitarray_t a, uns i)
  75 {
  76   return a[i/32] & (1 << (i%32));
  77 }
  78
  79 static inline uns
  80 bit_array_get(bitarray_t a, uns i)
  81 {
  82   return !! bit_array_isset(a, i);
  83 }
  84
  85 static inline uns
  86 bit_array_test_and_set(bitarray_t a, uns i)
  87 {
  88   uns t = bit_array_isset(a, i);
  89   bit_array_set(a, i);
  90   return t;
  91 }
  92
  93 static inline uns
  94 bit_array_test_and_clear(bitarray_t a, uns i)
  95 {
  96   uns t = bit_array_isset(a, i);
  97   bit_array_clear(a, i);
  98   return t;
  99 }
 100
 101 uns bit_array_count_bits(bitarray_t a, uns n);
 102
 103 /* Iterate over all set bits */
 104 #define BIT_ARRAY_FISH_BITS_BEGIN(var,ary,size)                                 \
 105   for (uns var##_hi=0; var##_hi < BIT_ARRAY_WORDS(size); var##_hi++)            \
 106     {                                                                           \
 107       u32 var##_cur = ary[var##_hi];                                            \
 108       for (uns var = 32 * var##_hi; var##_cur; var++, var##_cur >>= 1)          \
 109         if (var##_cur & 1)                                                      \
 110           do
 111
 112 #define BIT_ARRAY_FISH_BITS_END                                                 \
 113           while (0);                                                            \
 114     }
 115
 116 #endif