source: mainline/uspace/lib/cpp/include/__bits/adt/bitset.hpp@ 34b2f54d

Last change on this file since 34b2f54d was b57ba05, checked in by Jiří Zárevúcky <zarevucky.jiri@…>, 3 years ago

Update headers in C++ files
  • Property mode set to 100644
File size: 13.1 KB
Line 
1/*
2 * SPDX-FileCopyrightText: 2018 Jaroslav Jindrak
3 *
4 * SPDX-License-Identifier: BSD-3-Clause
5 */
6
7#ifndef LIBCPP_BITS_ADT_BITSET
8#define LIBCPP_BITS_ADT_BITSET
9
10#include <iosfwd>
11#include <string>
12
13namespace std
14{
15 /**
16 * 20.6, class template bitset:
17 */
18
19 template<size_t N>
20 class bitset
21 {
22 public:
23 class reference
24 {
25 friend class bitset;
26
27 public:
28 ~reference() noexcept = default;
29
30 reference& operator=(bool val) noexcept
31 {
32 if (val)
33 data_ |= mask_;
34 else
35 data_ &= ~mask_;
36 }
37
38 reference& operator=(const reference& other) noexcept
39 {
40 if (other)
41 data_ |= mask_;
42 else
43 data_ &= ~mask_;
44 }
45
46 bool operator~() const noexcept
47 {
48 return data_ & mask_;
49 }
50
51 operator bool() const noexcept
52 {
53 return data_ & mask_;
54 }
55
56 reference& flip() noexcept
57 {
58 data_ ^= mask_;
59
60 return *this;
61 }
62
63 private:
64 reference() noexcept = delete;
65
66 using data_type = typename bitset::data_type;
67
68 data_type& data_;
69 data_type mask_;
70
71 reference(data_type& data, size_t idx)
72 : data_{data}, mask_{bitset::one_ << idx}
73 { /* DUMMY BODY */ }
74 };
75
76 /**
77 * 20.6.1, constructors:
78 */
79
80 constexpr bitset() noexcept
81 {
82 init_(zero_);
83 }
84
85 constexpr bitset(unsigned long long val) noexcept
86 {
87 init_(val);
88 }
89
90 template<class Char, class Traits, class Allocator>
91 explicit bitset(
92 const basic_string<Char, Traits, Allocator>& str,
93 typename basic_string<Char, Traits, Allocator>::size_type pos = 0,
94 typename basic_string<Char, Traits, Allocator>::size_type n =
95 basic_string<Char, Traits, Allocator>::npos,
96 Char zero = Char('0'), Char one = Char('1')
97 )
98 {
99 // TODO: throw out_of_range if pos > str.size()
100
101 init_(zero_);
102 auto len = n < (str.size() - pos) ? n : (str.size() - pos);
103 len = len < N ? len : N;
104
105 for (size_t i = 0, j = pos + len - 1; i < len; ++i, --j)
106 {
107 if (Traits::eq(str[j], zero))
108 set(i, false);
109 else if (Traits::eq(str[j], one))
110 set(i, true);
111 // TODO: else throw invalid_argument
112 }
113 }
114
115 template<class Char>
116 explicit bitset(
117 const Char* str,
118 typename basic_string<Char>::size_type n = basic_string<Char>::npos,
119 Char zero = Char('0'), Char one = Char('1')
120 )
121 : bitset{
122 n == basic_string<Char>::npos ? basic_string<Char>{str} : basic_string<Char>{str, n},
123 0, n, zero, one
124 }
125 { /* DUMMY BODY */ }
126
127 /**
128 * 20.6.2, bitset operations:
129 */
130
131 bitset<N>& operator&=(const bitset<N>& rhs) noexcept
132 {
133 for (size_t i = 0; i < data_size_; ++i)
134 data_[i] &= rhs.data_[i];
135
136 return *this;
137 }
138
139 bitset<N>& operator|=(const bitset<N>& rhs) noexcept
140 {
141 for (size_t i = 0; i < data_size_; ++i)
142 data_[i] |= rhs.data_[i];
143
144 return *this;
145 }
146
147 bitset<N>& operator^=(const bitset<N>& rhs) noexcept
148 {
149 for (size_t i = 0; i < data_size_; ++i)
150 data_[i] ^= rhs.data_[i];
151
152 return *this;
153 }
154
155 bitset<N>& operator<<=(size_t pos) noexcept
156 {
157 for (size_t i = N; i > 1; --i)
158 {
159 if (i < pos)
160 set(i - 1, false);
161 else
162 set(i - 1, test(i - 1 - pos));
163 }
164
165 return *this;
166 }
167
168 bitset<N>& operator>>=(size_t pos) noexcept
169 {
170 for (size_t i = 0; i < N; ++i)
171 {
172 if (pos >= N - i)
173 set(i, false);
174 else
175 set(i, test(i + pos));
176 }
177
178 return *this;
179 }
180
181 bitset<N>& set() noexcept
182 {
183 for (size_t i = 0; i < N; ++i)
184 set(i);
185
186 return *this;
187 }
188
189 bitset<N>& set(size_t pos, bool val = true)
190 {
191 // TODO: throw out_of_range if pos > N
192 set_bit_(get_data_idx_(pos), get_bit_idx_(pos), val);
193
194 return *this;
195 }
196
197 bitset<N>& reset() noexcept
198 {
199 for (size_t i = 0; i < N; ++i)
200 reset(i);
201
202 return *this;
203 }
204
205 bitset<N>& reset(size_t pos)
206 {
207 set_bit_(get_data_idx_(pos), get_bit_idx_(pos), false);
208
209 return *this;
210 }
211
212 bitset<N> operator~() const noexcept
213 {
214 bitset<N> res{*this};
215
216 return res.flip();
217 }
218
219 bitset<N>& flip() noexcept
220 {
221 for (size_t i = 0; i < N; ++i)
222 flip(i);
223
224 return *this;
225 }
226
227 bitset<N>& flip(size_t pos)
228 {
229 return set(pos, !test(pos));
230 }
231
232 constexpr bool operator[](size_t pos) const
233 {
234 /**
235 * Note: The standard doesn't mention any exception
236 * here being thrown at any time, so we shouldn't
237 * use test().
238 */
239 return get_bit_(data_[get_data_idx_(pos)], get_bit_idx_(pos));
240 }
241
242 reference operator[](size_t pos)
243 {
244 return reference{data_[get_data_idx_(pos)], get_bit_idx_(pos)};
245 }
246
247 unsigned long to_ulong() const
248 {
249 // TODO: throw overflow_error if N > bits in ulong
250 return static_cast<unsigned long>(data_[0]);
251 }
252
253 unsigned long long to_ullong() const
254 {
255 // TODO: throw overflow_error if N > bits_in_data_type_
256 return data_[0];
257 }
258
259 template<
260 class Char = char,
261 class Traits = char_traits<Char>,
262 class Allocator = allocator<Char>
263 >
264 basic_string<Char, Traits, Allocator> to_string(Char zero = Char('0'),
265 Char one = Char('1')) const
266 {
267 basic_string<Char, Traits, Allocator> res{};
268 res.reserve(N);
269 for (size_t i = N; i > 0; --i)
270 {
271 if (test(i - 1))
272 res.push_back(one);
273 else
274 res.push_back(zero);
275 }
276
277 return res;
278 }
279
280 size_t count() const noexcept
281 {
282 size_t res{};
283 for (size_t i = 0; i < N; ++i)
284 {
285 if (test(i))
286 ++res;
287 }
288
289 return res;
290 }
291
292 constexpr size_t size() const noexcept
293 {
294 return N;
295 }
296
297 bool operator==(const bitset<N>& rhs) const noexcept
298 {
299 for (size_t i = 0; i < data_size_; ++i)
300 {
301 if (data_[i] != rhs.data_[i])
302 return false;
303 }
304
305 return true;
306 }
307
308 bool operator!=(const bitset<N>& rhs) const noexcept
309 {
310 return !(*this == rhs);
311 }
312
313 bool test(size_t pos) const
314 {
315 // TODO: throw out of range if pos > N
316 return get_bit_(data_[get_data_idx_(pos)], get_bit_idx_(pos));
317 }
318
319 bool all() const noexcept
320 {
321 return count() == size();
322 }
323
324 bool any() const noexcept
325 {
326 return count() != 0;
327 }
328
329 bool none() const noexcept
330 {
331 return count() == 0;
332 }
333
334 bitset<N> operator<<(size_t pos) const noexcept
335 {
336 return bitset<N>{*this} <<= pos;
337 }
338
339 bitset<N> operator>>(size_t pos) const noexcept
340 {
341 return bitset<N>{*this} >>= pos;
342 }
343
344 private:
345 /**
346 * While this might be a bit more wasteful
347 * than using unsigned or unsigned long,
348 * it will make parts of out code easier
349 * to read.
350 */
351 using data_type = unsigned long long;
352
353 static constexpr size_t bits_in_data_type_ = sizeof(data_type) * 8;
354 static constexpr size_t data_size_ = N / bits_in_data_type_ + 1;
355
356 /**
357 * These are useful for masks, if we use literals
358 * then forgetting to add ULL or changing the data
359 * type could result in wrong indices being computed.
360 */
361 static constexpr data_type zero_ = data_type{0};
362 static constexpr data_type one_ = data_type{1};
363
364 data_type data_[data_size_];
365
366 void init_(data_type val)
367 {
368 data_type mask{~zero_};
369 if (N < bits_in_data_type_)
370 mask >>= N;
371 data_[0] = val & mask;
372
373 for (size_t i = 1; i < data_size_; ++i)
374 data_[i] = data_type{};
375 }
376
377 size_t get_data_idx_(size_t pos) const
378 {
379 return pos / bits_in_data_type_;
380 }
381
382 size_t get_bit_idx_(size_t pos) const
383 {
384 return pos % bits_in_data_type_;
385 }
386
387 bool get_bit_(data_type data, size_t bit_idx) const
388 {
389 return data & (one_ << bit_idx);
390 }
391
392 void set_bit_(size_t data_idx, size_t bit_idx, bool val)
393 {
394 if (val)
395 data_[data_idx] |= (one_ << bit_idx);
396 else
397 data_[data_idx] &= ~(one_ << bit_idx);
398 }
399 };
400
401 /**
402 * 20.6.3 hash support:
403 */
404
405 template<class T>
406 struct hash;
407
408 template<size_t N>
409 struct hash<bitset<N>>
410 {
411 size_t operator()(const bitset<N>& set) const noexcept
412 {
413 return hash<unsigned long long>{}(set.to_ullong());
414 }
415
416 using argument_type = bitset<N>;
417 using result_type = size_t;
418 };
419
420 /**
421 * 20.6.4, bitset operators:
422 */
423
424 template<size_t N>
425 bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
426 {
427 return bitset<N>{lhs} &= rhs;
428 }
429
430 template<size_t N>
431 bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
432 {
433 return bitset<N>{lhs} |= rhs;
434 }
435
436 template<size_t N>
437 bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
438 {
439 return bitset<N>{lhs} ^= rhs;
440 }
441
442 template<class Char, class Traits, size_t N>
443 basic_istream<Char, Traits>&
444 operator>>(basic_istream<Char, Traits>& is, bitset<N>& set)
445 {
446 size_t i{};
447 Char c{};
448 Char zero{is.widen('0')};
449 Char one{is.widen('1')};
450
451 basic_string<Char, Traits> str{};
452 while (i < N)
453 {
454 if (is.eof())
455 break;
456
457 is.get(c);
458
459 if (!Traits::eq(c, one) && !Traits::eq(c, zero))
460 {
461 is.putback(c);
462 break;
463 }
464
465 str.push_back(c);
466 ++i;
467 }
468
469 if (i == 0)
470 is.setstate(ios_base::failbit);
471
472 set = bitset<N>{str};
473
474 return is;
475 }
476
477 template<class Char, class Traits, size_t N>
478 basic_ostream<Char, Traits>&
479 operator<<(basic_ostream<Char, Traits>& os, const bitset<N>& set)
480 {
481 return os << set.template to_string<Char, Traits, allocator<Char>>(
482 use_facet<ctype<Char>>(os.getloc()).widen('0'),
483 use_facet<ctype<Char>>(os.getloc()).widen('1')
484 );
485 }
486}
487
488#endif
Note: See TracBrowser for help on using the repository browser.