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