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 *
init_bitfield(size_t bits)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
copy_bitfield(struct bitfield * bitfield,const unsigned char * bits,unsigned int bytesize)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
test_bitfield_bit(struct bitfield * bitfield,unsigned int bit)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
set_bitfield_bit(struct bitfield * bitfield,unsigned int bit)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
clear_bitfield_bit(struct bitfield * bitfield,unsigned int bit)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
get_bitfield_set_count(struct bitfield * bitfield)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
get_bitfield_cleared_count(struct bitfield * bitfield)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
bitfield_is_set(struct bitfield * bitfield)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
bitfield_is_cleared(struct bitfield * bitfield)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
147