NetBurner 3.5.6
PDF Version
nbfs_bit_list.h
1/*NB_REVISION*/
2
3/*NB_COPYRIGHT*/
4
5#ifndef __NBFS_BIT_LIST_H
6#define __NBFS_BIT_LIST_H
7
8#include <basictypes.h>
9
10#define __bit_list_words(__n) \
11 (((uint8_t)((__n) >> 5)) + ((uint8_t)((((__n) & 0x1f) == 0) ? 0 : 1)))
12
13#define do_forall(x,n,...) for (uint8_t x = 0; x < __bit_list_words((n)); x++) {__VA_ARGS__}
14
15template <uint16_t _nbits>
16class bit_list
17{
18 uint32_t bits[__bit_list_words(_nbits)];
19
20 static constexpr uint32_t
21 _whichword(uint8_t idx)
22 { return idx >> 5; }
23
24 static constexpr uint32_t
25 _whichbit(uint8_t idx)
26 { return idx & 0x1F; }
27
28 static constexpr uint32_t
29 _maskbit(uint8_t idx)
30 { return ((uint32_t)1UL) << _whichbit(idx); }
31
32 uint32_t &
33 _getword(uint8_t idx)
34 { return bits[_whichword(idx)]; }
35
36 constexpr uint32_t
37 _getword(uint8_t idx) const
38 { return bits[_whichword(idx)]; }
39
40 void _xor(const bit_list<_nbits>& rhs)
41 { do_forall(i, _nbits, bits[i] ^= rhs.bits[i];) }
42
43 void _and(const bit_list<_nbits>& rhs)
44 { do_forall(i, _nbits, bits[i] &= rhs.bits[i];) }
45
46 void _or(const bit_list<_nbits>& rhs)
47 { do_forall(i, _nbits, bits[i] |= rhs.bits[i];) }
48
49 bool _isequal(const bit_list<_nbits>& rhs)
50 { do_forall(i, _nbits, if (bits[i] != rhs.bit[i]) return false;) }
51
52
53public:
54 class bit_t {
55 uint32_t &_stor;
56 uint8_t pos;
57 bit_t(bit_list &list, uint8_t idx)
58 : _stor(list.bits[_whichword(idx)]), pos(_whichbit(idx))
59 { }
60 bit_t(uint32_t &word, uint8_t bitPos)
61 : _stor(word), pos(bitPos)
62 { }
63 public:
64 operator bool() { return _stor & bit_list::_maskbit(pos); }
65
66 bit_t& operator=(bool rhs)
67 {
68 if (rhs) { _stor |= bit_list::_maskbit(pos); }
69 else { _stor &= ~bit_list::_maskbit(pos); }
70
71 return *this;
72 }
73
74 bit_t& operator=(const bit_t& rhs)
75 {
76 if ((rhs._stor) & bit_list::_maskbit(rhs.pos))
77 _stor |= bit_list::_maskbit(pos);
78 else
79 _stor &= ~bit_list::_maskbit(pos);
80
81 return *this;
82 }
83 friend class bit_list;
84 };
85 friend class bit_t;
86
87 /***************************************************************************
88 * @class bit_list<>::iterator *
89 * @brief This is an iterator for walking the set bit positions of a *
90 * bit_list<>. *
91 **************************************************************************/
92 class iterator {
93 const bit_list *list; // bit_list that this iterator is for
94 uint8_t _wordIdx; // which storage word is active
95 uint8_t _bitPos; // which bit in that storage word is pointed to
96
97 public:
98 iterator()
99 : list(NULL), _wordIdx(__bit_list_words(_nbits)), _bitPos(0)
100 { }
101
102 iterator(const bit_list *_list)
103 : list(_list), _wordIdx(0), _bitPos(0)
104 { if (!(list->bits[_wordIdx] & 0x1)) operator++(); }
105
106 iterator(const bit_list *_list, uint8_t word, uint8_t bitPos)
107 : list(_list), _wordIdx(word), _bitPos(bitPos)
108 { }
109 iterator(const iterator &it)
110 : list(it.list), _wordIdx(it._wordIdx), _bitPos(it._bitPos)
111 { }
112
113 iterator & operator=(const iterator& rhs)
114 { list = rhs.list; _wordIdx = rhs._wordIdx; _bitPos = rhs._bitPos; return *this; }
115
116 iterator& operator++()
117 {
118 uint32_t wordVal, searchMask;
119
120 while ((_wordIdx + (_bitPos==31)) < __bit_list_words(_nbits))
121 {
122 if (_bitPos < 31)
123 {
124 searchMask = ~((0x2 << _bitPos) - 1);
125 wordVal = list->bits[_wordIdx] & searchMask;
126 }
127 else
128 {
129 _wordIdx++;
130 wordVal = list->bits[_wordIdx];
131 }
132 if (wordVal)
133 {
134 _bitPos = __builtin_ctz(wordVal);
135 return *this;
136 }
137 _bitPos = 31;
138 }
139 _wordIdx = __bit_list_words(_nbits);
140 _bitPos = 0;
141 // _wordIdx past end, give up
142
143 return *this;
144 }
145
146 iterator& operator--()
147 {
148 uint32_t wordVal, searchMask;
149 if (!(_wordIdx || _bitPos))
150 return *this;
151
152 do {
153 if (!_bitPos)
154 {
155 wordVal = list->bits[_wordIdx - 1] & 0xFFFFFFFF;
156 if (wordVal)
157 {
158 _wordIdx--;
159 _bitPos = (31-__builtin_clz(wordVal));
160 return *this;
161 }
162 }
163 else
164 {
165 searchMask = ((0x1 << _bitPos) - 1);
166 wordVal = list->bits[_wordIdx] & searchMask;
167 if (wordVal)
168 {
169 _bitPos = (31-__builtin_clz(wordVal));
170 return *this;
171 }
172
173 _bitPos = 0;
174 continue;
175 }
176 } while (_wordIdx--);
177 // _wordIdx past end, give up
178
179 _wordIdx = __bit_list_words(_nbits);
180 _bitPos = 0;
181 return *this;
182 }
183 iterator operator++(int) { iterator tmp(*this); operator++(); return tmp; }
184 iterator operator--(int) { iterator tmp(*this); operator--(); return tmp; }
185
186
187 bool operator==(const iterator &rhs) const
188 {
189 return ((list == rhs.list)
190 && (_wordIdx == rhs._wordIdx)
191 && (_bitPos == rhs._bitPos));
192 }
193
194 bool operator!=(const iterator &rhs) const
195 {
196 return !((list == rhs.list)
197 && (_wordIdx == rhs._wordIdx)
198 && (_bitPos == rhs._bitPos));
199 }
200
201 uint8_t operator*() { return (_wordIdx << 5) + _bitPos; }
202
203 friend class bit_list;
204 };
205 friend class iterator;
206
207 inline void clr_all()
208 {
209 for (int i = 0; i < __bit_list_words(_nbits); i++)
210 bits[i] = 0;
211 }
212 inline void set_all()
213 {
214 for (int i = 0; i < __bit_list_words(_nbits); i++)
215 bits[i] = 0xffffffff;
216 }
217 bool set(uint8_t bit, bool val = true)
218 {
219 uint32_t msk = 1 << (bit & 0x1f);
220 uint32_t *w = bits + (bit >> 5);
221
222 *w = (*w & ~msk) | (-val & msk);
223 return val;
224 }
225
226 bool clr(uint8_t bit)
227 { return set(bit, false); }
228
229 bool test(uint8_t bit) const
230 { return bits[_whichword(bit)] & _maskbit(bit); }
231
232 bit_list<_nbits> flip()
233 { do_forall(i, _nbits, bits[i] = ~bits[i];) return *this; }
234
235 uint16_t count() const
236 {
237 uint32_t _ret = 0;
238 do_forall(i, _nbits,
239 _ret += __builtin_popcount(bits[i]);
240 )
241 return (uint16_t) _ret;
242 }
243
244 bool all() const
245 { do_forall(i, _nbits, if (bits[i] != 0xFFFFFFFF) return false;) return true; }
246
247 bool any() const
248 { do_forall(i, _nbits, if (bits[i]) return true;) return false; }
249
250 bool none() const
251 { return !any(); }
252
253 /* C++ Operators */
254 bit_list<_nbits>
255 operator~() const
256 { return bit_list<_nbits>(*this).flip(); }
257
258 operator bool() const
259 { return any(); }
260
261 /* Assignments */
262 bit_list<_nbits> &
263 operator ^=(const bit_list<_nbits>& rhs)
264 {
265 _xor(rhs);
266 return *this;
267 }
268
269 bit_list<_nbits> &
270 operator &=(const bit_list<_nbits>& rhs)
271 {
272 _and(rhs);
273 return *this;
274 }
275
276 bit_list<_nbits> &
277 operator |=(const bit_list<_nbits>& rhs)
278 {
279 _or(rhs);
280 return *this;
281 }
282
283 /* Boolean Operators */
284 bool
285 operator==(const bit_list<_nbits>& rhs) const
286 { return isequal(rhs); }
287
288 bool
289 operator!=(const bit_list<_nbits>& rhs) const
290 { return !isequal(rhs); }
291
292 inline bit_t operator[](uint8_t bit)
293 { return bit_t(_getword(bit), _whichbit(bit)); }
294
295 inline bool operator[](uint8_t bit) const
296 { return test(bit); }
297
298 iterator begin() const
299 { return iterator(this); }
300
301 iterator end() const
302 { return iterator(this, __bit_list_words(_nbits), 0); }
303
304 iterator last() const
305 { return --end(); }
306
307 // We explicitly do not declare a default construct that would zero the list
308 // as doing so would prevent us from placing the class inside a union
309 //
310 bit_list<_nbits>() { clr_all(); }
311
312 bit_list(const bit_list& rhs)
313 { do_forall(i, _nbits, bits[i] = rhs.bits[i];) }
314
315 bit_list(uint32_t pattern)
316 { do_forall(i, _nbits, bits[i] = pattern;) }
317};
318
319#endif /* ----- #ifndef __NBFS_BIT_LIST_H ----- */