source: mainline/uspace/lib/cpp/include/impl/bitset.hpp@ c075647a

lfn serial ticket/834-toolchain-update topic/msim-upgrade topic/simplify-dev-export
Last change on this file since c075647a was eaabd7d, checked in by Dzejrou <dzejrou@…>, 7 years ago

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