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

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

cpp: added bitset
  • 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'), Char one = Char('1')) const
287 {
288 basic_string<Char, Traits, Allocator> res{};
289 res.reserve(N);
290 for (size_t i = N; i > 0; --i)
291 {
292 if (test(i - 1))
293 res.push_back(one);
294 else
295 res.push_back(zero);
296 }
297
298 return res;
299 }
300
301 size_t count() const noexcept
302 {
303 size_t res{};
304 for (size_t i = 0; i < N; ++i)
305 {
306 if (test(i))
307 ++res;
308 }
309
310 return res;
311 }
312
313 constexpr size_t size() const noexcept
314 {
315 return N;
316 }
317
318 bool operator==(const bitset<N>& rhs) const noexcept
319 {
320 for (size_t i = 0; i < data_size_; ++i)
321 {
322 if (data_[i] != rhs.data_[i])
323 return false;
324 }
325
326 return true;
327 }
328
329 bool operator!=(const bitset<N>& rhs) const noexcept
330 {
331 return !(*this == rhs);
332 }
333
334 bool test(size_t pos) const
335 {
336 // TODO: throw out of range if pos > N
337 return get_bit_(data_[get_data_idx_(pos)], get_bit_idx_(pos));
338 }
339
340 bool all() const noexcept
341 {
342 return count() == size();
343 }
344
345 bool any() const noexcept
346 {
347 return count() != 0;
348 }
349
350 bool none() const noexcept
351 {
352 return count() == 0;
353 }
354
355 bitset<N> operator<<(size_t pos) const noexcept
356 {
357 return bitset<N>{*this} <<= pos;
358 }
359
360 bitset<N> operator>>(size_t pos) const noexcept
361 {
362 return bitset<N>{*this} >>= pos;
363 }
364
365 private:
366 /**
367 * While this might be a bit more wasteful
368 * than using unsigned or unsigned long,
369 * it will make parts of out code easier
370 * to read.
371 */
372 using data_type = unsigned long long;
373
374 static constexpr size_t bits_in_data_type_ = sizeof(data_type) * 8;
375 static constexpr size_t data_size_ = N / bits_in_data_type_ + 1;
376
377 /**
378 * These are useful for masks, if we use literals
379 * then forgetting to add ULL or changing the data
380 * type could result in wrong indices being computed.
381 */
382 static constexpr data_type zero_ = data_type{0};
383 static constexpr data_type one_ = data_type{1};
384
385 data_type data_[data_size_];
386
387 void init_(data_type val)
388 {
389 data_type mask{~zero_};
390 if (N < bits_in_data_type_)
391 mask >>= N;
392 data_[0] = val & mask;
393
394 for (size_t i = 1; i < data_size_; ++i)
395 data_[i] = data_type{};
396 }
397
398 size_t get_data_idx_(size_t pos) const
399 {
400 return pos / bits_in_data_type_;
401 }
402
403 size_t get_bit_idx_(size_t pos) const
404 {
405 return pos % bits_in_data_type_;
406 }
407
408 bool get_bit_(data_type data, size_t bit_idx) const
409 {
410 return data & (one_ << bit_idx);
411 }
412
413 void set_bit_(size_t data_idx, size_t bit_idx, bool val)
414 {
415 if (val)
416 data_[data_idx] |= (one_ << bit_idx);
417 else
418 data_[data_idx] &= ~(one_ << bit_idx);
419 }
420 };
421
422 /**
423 * 20.6.3 hash support:
424 */
425
426 template<class T>
427 struct hash;
428
429 template<size_t N>
430 struct hash<bitset<N>>
431 {
432 size_t operator()(const bitset<N>& set) const noexcept
433 {
434 return hash<unsigned long long>{}(set.to_ullong());
435 }
436
437 using argument_type = bitset<N>;
438 using result_type = size_t;
439 };
440
441 /**
442 * 20.6.4, bitset operators:
443 */
444
445 template<size_t N>
446 bitset<N> operator&(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
447 {
448 return bitset<N>{lhs} &= rhs;
449 }
450
451 template<size_t N>
452 bitset<N> operator|(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
453 {
454 return bitset<N>{lhs} |= rhs;
455 }
456
457 template<size_t N>
458 bitset<N> operator^(const bitset<N>& lhs, const bitset<N>& rhs) noexcept
459 {
460 return bitset<N>{lhs} ^= rhs;
461 }
462
463 template<class Char, class Traits, size_t N>
464 basic_istream<Char, Traits>&
465 operator>>(basic_istream<Char, Traits>& is, bitset<N>& set)
466 {
467 size_t i{};
468 Char c{};
469 Char zero{is.widen('0')};
470 Char one{is.widen('1')};
471
472 basic_string<Char, Traits> str{N};
473 while (i < N)
474 {
475 if (is.eof())
476 break;
477
478 is.get(c);
479
480 if (!Traits::eq(c, one) && !Traits::eq(c, zero))
481 {
482 is.putback(c);
483 break;
484 }
485
486 str.push_back(c);
487 }
488
489 if (i == 0)
490 is.setstate(ios_base::failbit);
491
492 set = bitset<N>{str};
493
494 return is;
495 }
496
497 template<class Char, class Traits, size_t N>
498 basic_ostream<Char, Traits>&
499 operator<<(basic_ostream<Char, Traits>& os, const bitset<N>& set)
500 {
501 return os << set.template to_string<Char, Traits, allocator<Char>>(
502 use_facet<ctype<Char>>(os.getloc()).widen('0'),
503 use_facet<ctype<Char>>(os.getloc()).widen('1')
504 );
505 }
506}
507
508#endif
Note: See TracBrowser for help on using the repository browser.