src/util/bitfield.h

   1 #ifndef EL__UTIL_BITFIELD_H
   2 #define EL__UTIL_BITFIELD_H
   3
   4 #include <string.h>
   5
   6 #include "util/memory.h"
   7
   8 /* Bitfield operations: */
   9
  10 /** A vector of bits.  The size is fixed at initialization time.  */
  11 struct bitfield {
  12         unsigned int bitsize;   /**< Number of bits in the bitfield. */
  13         unsigned char bits[1];  /**< Strawberry bitfields forever. */
  14 };
  15
  16 /** @relates bitfield */
  17 #define foreach_bitfield_set(bit, bitfield) \
  18         for ((bit) = 0; (bit) < (bitfield)->bitsize; (bit)++) \
  19                 if (test_bitfield_bit(bitfield, bit))
  20
  21 /** @relates bitfield */
  22 #define foreachback_bitfield_set(bit, bitfield) \
  23         for ((bit) = (bitfield)->bitsize; (bit) > 0;) \
  24                 if (test_bitfield_bit(bitfield, --bit))
  25
  26 /** @relates bitfield */
  27 #define foreach_bitfield_cleared(bit, bitfield) \
  28         for ((bit) = 0; (bit) < (bitfield)->bitsize; (bit)++) \
  29                 if (!test_bitfield_bit(bitfield, bit))
  30
  31 /* By shifting when getting the bit offset it is ensured that only one bit is
  32  * set in the resulting value. Idea from libbt by Kevin Smathers. */
  33 #define get_bitfield_bit_offset(bit)    ((size_t) (0x80 >> ((bit) % 8)))
  34 #define get_bitfield_byte_offset(bit)   ((size_t) ((bit) / 8))
  35 /* +7 to round up to nearest byte. */
  36 #define get_bitfield_byte_size(bits)    ((size_t) (((bits) + 7) / 8))
  37
  38 /** Allocate a bitfield containing @a bits number of bits.
  39  * @relates bitfield */
  40 static inline struct bitfield *
  41 init_bitfield(size_t bits)
  42 {
  43         size_t size = get_bitfield_byte_size(bits);
  44         struct bitfield *bitfield;
  45
  46         bitfield = mem_calloc(1, offsetof(struct bitfield, bits) + size);
  47         if (bitfield) bitfield->bitsize = bits;
  48
  49         return bitfield;
  50 }
  51
  52 /** Update @a bitfield with the @a bytesize bytes from the bit string
  53  * in @a bits.
  54  * @relates bitfield */
  55 static inline void
  56 copy_bitfield(struct bitfield *bitfield,
  57               const unsigned char *bits, unsigned int bytesize)
  58 {
  59         /* Only for exact size? */
  60         if (bytesize <= get_bitfield_byte_size(bitfield->bitsize))
  61                 memcpy(bitfield->bits, bits, bytesize);
  62 }
  63
  64 /** Test whether @a bit is set in the @a bitfield.
  65  * @relates bitfield */
  66 static inline int
  67 test_bitfield_bit(struct bitfield *bitfield, unsigned int bit)
  68 {
  69         size_t byte_offset, bit_offset;
  70
  71         if (bit >= bitfield->bitsize)
  72                 return 0;
  73
  74         byte_offset = get_bitfield_byte_offset(bit);
  75         bit_offset  = get_bitfield_bit_offset(bit);
  76
  77         return !!(bitfield->bits[byte_offset] & bit_offset);
  78 }
  79
  80 /** Set @a bit in the @a bitfield.
  81  * @relates bitfield */
  82 static inline void
  83 set_bitfield_bit(struct bitfield *bitfield, unsigned int bit)
  84 {
  85         size_t byte_offset, bit_offset;
  86
  87         if (bit >= bitfield->bitsize)
  88                 return;
  89
  90         byte_offset = get_bitfield_byte_offset(bit);
  91         bit_offset  = get_bitfield_bit_offset(bit);
  92
  93         bitfield->bits[byte_offset] |= bit_offset;
  94 }
  95
  96 /** Unset @a bit in the @a bitfield.
  97  * @relates bitfield */
  98 static inline void
  99 clear_bitfield_bit(struct bitfield *bitfield, unsigned int bit)
 100 {
 101         size_t byte_offset, bit_offset;
 102
 103         if (bit >= bitfield->bitsize)
 104                 return;
 105
 106         byte_offset = get_bitfield_byte_offset(bit);
 107         bit_offset  = get_bitfield_bit_offset(bit);
 108
 109         bitfield->bits[byte_offset] &= ~bit_offset;
 110 }
 111
 112 /** Count the set bits in @a bitfield.
 113  * @relates bitfield */
 114 static inline unsigned int
 115 get_bitfield_set_count(struct bitfield *bitfield)
 116 {
 117         unsigned int bit, count = 0;
 118
 119         foreach_bitfield_set (bit, bitfield)
 120                 count++;
 121
 122         return count;
 123 }
 124
 125 /** Count the unset bits in @a bitfield.
 126  * @relates bitfield */
 127 static inline unsigned int
 128 get_bitfield_cleared_count(struct bitfield *bitfield)
 129 {
 130         unsigned int bit, count = 0;
 131
 132         foreach_bitfield_cleared (bit, bitfield)
 133                 count++;
 134
 135         return count;
 136 }
 137
 138 /** Check whether all bits of @a bitfield are set.
 139  * @relates bitfield */
 140 static inline unsigned int
 141 bitfield_is_set(struct bitfield *bitfield)
 142 {
 143         unsigned int bit;
 144
 145         foreach_bitfield_cleared (bit, bitfield)
 146                 return 0;
 147
 148         return 1;
 149 }
 150
 151 /** Check whether all bits of @a bitfield are unset.
 152  * @relates bitfield */
 153 static inline unsigned int
 154 bitfield_is_cleared(struct bitfield *bitfield)
 155 {
 156         unsigned int bit;
 157
 158         foreach_bitfield_set (bit, bitfield)
 159                 return 0;
 160
 161         return 1;
 162 }
 163
 164 #endif