src/util/bitfield.h

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