source: mainline/uspace/lib/cpp/include/__bits/adt/bitset.hpp@ 113fb4f

Last change on this file since 113fb4f was a36c4aa, checked in by Martin Decky <martin@…>, 4 months ago

Switch to binutils 2.45 and GCC 15.2

This requires a few minor modifications and one temporary workaround,
but should be otherwise painless.

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