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