1 | // <bitset> -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2021 Free Software Foundation, Inc. |
4 | // |
5 | // This file is part of the GNU ISO C++ Library. This library is free |
6 | // software; you can redistribute it and/or modify it under the |
7 | // terms of the GNU General Public License as published by the |
8 | // Free Software Foundation; either version 3, or (at your option) |
9 | // any later version. |
10 | |
11 | // This library is distributed in the hope that it will be useful, |
12 | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
13 | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
14 | // GNU General Public License for more details. |
15 | |
16 | // Under Section 7 of GPL version 3, you are granted additional |
17 | // permissions described in the GCC Runtime Library Exception, version |
18 | // 3.1, as published by the Free Software Foundation. |
19 | |
20 | // You should have received a copy of the GNU General Public License and |
21 | // a copy of the GCC Runtime Library Exception along with this program; |
22 | // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see |
23 | // <http://www.gnu.org/licenses/>. |
24 | |
25 | /* |
26 | * Copyright (c) 1998 |
27 | * Silicon Graphics Computer Systems, Inc. |
28 | * |
29 | * Permission to use, copy, modify, distribute and sell this software |
30 | * and its documentation for any purpose is hereby granted without fee, |
31 | * provided that the above copyright notice appear in all copies and |
32 | * that both that copyright notice and this permission notice appear |
33 | * in supporting documentation. Silicon Graphics makes no |
34 | * representations about the suitability of this software for any |
35 | * purpose. It is provided "as is" without express or implied warranty. |
36 | */ |
37 | |
38 | /** @file include/bitset |
39 | * This is a Standard C++ Library header. |
40 | */ |
41 | |
42 | #ifndef _GLIBCXX_BITSET |
43 | #define _GLIBCXX_BITSET 1 |
44 | |
45 | #pragma GCC system_header |
46 | |
47 | #include <string> |
48 | #include <bits/functexcept.h> // For invalid_argument, out_of_range, |
49 | // overflow_error |
50 | #include <iosfwd> |
51 | #include <bits/cxxabi_forced.h> |
52 | |
53 | #if __cplusplus >= 201103L |
54 | # include <bits/functional_hash.h> |
55 | #endif |
56 | |
57 | #define _GLIBCXX_BITSET_BITS_PER_WORD (__CHAR_BIT__ * __SIZEOF_LONG__) |
58 | #define _GLIBCXX_BITSET_WORDS(__n) \ |
59 | ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \ |
60 | ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1)) |
61 | |
62 | #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__) |
63 | |
64 | namespace std _GLIBCXX_VISIBILITY(default) |
65 | { |
66 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
67 | |
68 | /** |
69 | * Base class, general case. It is a class invariant that _Nw will be |
70 | * nonnegative. |
71 | * |
72 | * See documentation for bitset. |
73 | */ |
74 | template<size_t _Nw> |
75 | struct _Base_bitset |
76 | { |
77 | typedef unsigned long _WordT; |
78 | |
79 | /// 0 is the least significant word. |
80 | _WordT _M_w[_Nw]; |
81 | |
82 | _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT |
83 | : _M_w() { } |
84 | |
85 | #if __cplusplus >= 201103L |
86 | constexpr _Base_bitset(unsigned long long __val) noexcept |
87 | : _M_w{ _WordT(__val) |
88 | #if __SIZEOF_LONG_LONG__ > __SIZEOF_LONG__ |
89 | , _WordT(__val >> _GLIBCXX_BITSET_BITS_PER_WORD) |
90 | #endif |
91 | } { } |
92 | #else |
93 | _Base_bitset(unsigned long __val) |
94 | : _M_w() |
95 | { _M_w[0] = __val; } |
96 | #endif |
97 | |
98 | static _GLIBCXX_CONSTEXPR size_t |
99 | _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT |
100 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
101 | |
102 | static _GLIBCXX_CONSTEXPR size_t |
103 | _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT |
104 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
105 | |
106 | static _GLIBCXX_CONSTEXPR size_t |
107 | _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT |
108 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
109 | |
110 | static _GLIBCXX_CONSTEXPR _WordT |
111 | _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT |
112 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } |
113 | |
114 | _WordT& |
115 | _M_getword(size_t __pos) _GLIBCXX_NOEXCEPT |
116 | { return _M_w[_S_whichword(__pos)]; } |
117 | |
118 | _GLIBCXX_CONSTEXPR _WordT |
119 | _M_getword(size_t __pos) const _GLIBCXX_NOEXCEPT |
120 | { return _M_w[_S_whichword(__pos)]; } |
121 | |
122 | #if __cplusplus >= 201103L |
123 | const _WordT* |
124 | _M_getdata() const noexcept |
125 | { return _M_w; } |
126 | #endif |
127 | |
128 | _WordT& |
129 | _M_hiword() _GLIBCXX_NOEXCEPT |
130 | { return _M_w[_Nw - 1]; } |
131 | |
132 | _GLIBCXX_CONSTEXPR _WordT |
133 | _M_hiword() const _GLIBCXX_NOEXCEPT |
134 | { return _M_w[_Nw - 1]; } |
135 | |
136 | void |
137 | _M_do_and(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT |
138 | { |
139 | for (size_t __i = 0; __i < _Nw; __i++) |
140 | _M_w[__i] &= __x._M_w[__i]; |
141 | } |
142 | |
143 | void |
144 | _M_do_or(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT |
145 | { |
146 | for (size_t __i = 0; __i < _Nw; __i++) |
147 | _M_w[__i] |= __x._M_w[__i]; |
148 | } |
149 | |
150 | void |
151 | _M_do_xor(const _Base_bitset<_Nw>& __x) _GLIBCXX_NOEXCEPT |
152 | { |
153 | for (size_t __i = 0; __i < _Nw; __i++) |
154 | _M_w[__i] ^= __x._M_w[__i]; |
155 | } |
156 | |
157 | void |
158 | _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT; |
159 | |
160 | void |
161 | _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT; |
162 | |
163 | void |
164 | _M_do_flip() _GLIBCXX_NOEXCEPT |
165 | { |
166 | for (size_t __i = 0; __i < _Nw; __i++) |
167 | _M_w[__i] = ~_M_w[__i]; |
168 | } |
169 | |
170 | void |
171 | _M_do_set() _GLIBCXX_NOEXCEPT |
172 | { |
173 | for (size_t __i = 0; __i < _Nw; __i++) |
174 | _M_w[__i] = ~static_cast<_WordT>(0); |
175 | } |
176 | |
177 | void |
178 | _M_do_reset() _GLIBCXX_NOEXCEPT |
179 | { __builtin_memset(_M_w, 0, _Nw * sizeof(_WordT)); } |
180 | |
181 | bool |
182 | _M_is_equal(const _Base_bitset<_Nw>& __x) const _GLIBCXX_NOEXCEPT |
183 | { |
184 | for (size_t __i = 0; __i < _Nw; ++__i) |
185 | if (_M_w[__i] != __x._M_w[__i]) |
186 | return false; |
187 | return true; |
188 | } |
189 | |
190 | template<size_t _Nb> |
191 | bool |
192 | _M_are_all() const _GLIBCXX_NOEXCEPT |
193 | { |
194 | for (size_t __i = 0; __i < _Nw - 1; __i++) |
195 | if (_M_w[__i] != ~static_cast<_WordT>(0)) |
196 | return false; |
197 | return _M_hiword() == (~static_cast<_WordT>(0) |
198 | >> (_Nw * _GLIBCXX_BITSET_BITS_PER_WORD |
199 | - _Nb)); |
200 | } |
201 | |
202 | bool |
203 | _M_is_any() const _GLIBCXX_NOEXCEPT |
204 | { |
205 | for (size_t __i = 0; __i < _Nw; __i++) |
206 | if (_M_w[__i] != static_cast<_WordT>(0)) |
207 | return true; |
208 | return false; |
209 | } |
210 | |
211 | size_t |
212 | _M_do_count() const _GLIBCXX_NOEXCEPT |
213 | { |
214 | size_t __result = 0; |
215 | for (size_t __i = 0; __i < _Nw; __i++) |
216 | __result += __builtin_popcountl(_M_w[__i]); |
217 | return __result; |
218 | } |
219 | |
220 | unsigned long |
221 | _M_do_to_ulong() const; |
222 | |
223 | #if __cplusplus >= 201103L |
224 | unsigned long long |
225 | _M_do_to_ullong() const; |
226 | #endif |
227 | |
228 | // find first "on" bit |
229 | size_t |
230 | _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT; |
231 | |
232 | // find the next "on" bit that follows "prev" |
233 | size_t |
234 | _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT; |
235 | }; |
236 | |
237 | // Definitions of non-inline functions from _Base_bitset. |
238 | template<size_t _Nw> |
239 | void |
240 | _Base_bitset<_Nw>::_M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT |
241 | { |
242 | if (__builtin_expect(__shift != 0, 1)) |
243 | { |
244 | const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; |
245 | const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; |
246 | |
247 | if (__offset == 0) |
248 | for (size_t __n = _Nw - 1; __n >= __wshift; --__n) |
249 | _M_w[__n] = _M_w[__n - __wshift]; |
250 | else |
251 | { |
252 | const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD |
253 | - __offset); |
254 | for (size_t __n = _Nw - 1; __n > __wshift; --__n) |
255 | _M_w[__n] = ((_M_w[__n - __wshift] << __offset) |
256 | | (_M_w[__n - __wshift - 1] >> __sub_offset)); |
257 | _M_w[__wshift] = _M_w[0] << __offset; |
258 | } |
259 | |
260 | std::fill(_M_w + 0, _M_w + __wshift, static_cast<_WordT>(0)); |
261 | } |
262 | } |
263 | |
264 | template<size_t _Nw> |
265 | void |
266 | _Base_bitset<_Nw>::_M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT |
267 | { |
268 | if (__builtin_expect(__shift != 0, 1)) |
269 | { |
270 | const size_t __wshift = __shift / _GLIBCXX_BITSET_BITS_PER_WORD; |
271 | const size_t __offset = __shift % _GLIBCXX_BITSET_BITS_PER_WORD; |
272 | const size_t __limit = _Nw - __wshift - 1; |
273 | |
274 | if (__offset == 0) |
275 | for (size_t __n = 0; __n <= __limit; ++__n) |
276 | _M_w[__n] = _M_w[__n + __wshift]; |
277 | else |
278 | { |
279 | const size_t __sub_offset = (_GLIBCXX_BITSET_BITS_PER_WORD |
280 | - __offset); |
281 | for (size_t __n = 0; __n < __limit; ++__n) |
282 | _M_w[__n] = ((_M_w[__n + __wshift] >> __offset) |
283 | | (_M_w[__n + __wshift + 1] << __sub_offset)); |
284 | _M_w[__limit] = _M_w[_Nw-1] >> __offset; |
285 | } |
286 | |
287 | std::fill(_M_w + __limit + 1, _M_w + _Nw, static_cast<_WordT>(0)); |
288 | } |
289 | } |
290 | |
291 | template<size_t _Nw> |
292 | unsigned long |
293 | _Base_bitset<_Nw>::_M_do_to_ulong() const |
294 | { |
295 | for (size_t __i = 1; __i < _Nw; ++__i) |
296 | if (_M_w[__i]) |
297 | __throw_overflow_error(__N("_Base_bitset::_M_do_to_ulong" )); |
298 | return _M_w[0]; |
299 | } |
300 | |
301 | #if __cplusplus >= 201103L |
302 | template<size_t _Nw> |
303 | unsigned long long |
304 | _Base_bitset<_Nw>::_M_do_to_ullong() const |
305 | { |
306 | const bool __dw = sizeof(unsigned long long) > sizeof(unsigned long); |
307 | for (size_t __i = 1 + __dw; __i < _Nw; ++__i) |
308 | if (_M_w[__i]) |
309 | __throw_overflow_error(__N("_Base_bitset::_M_do_to_ullong" )); |
310 | |
311 | if (__dw) |
312 | return _M_w[0] + (static_cast<unsigned long long>(_M_w[1]) |
313 | << _GLIBCXX_BITSET_BITS_PER_WORD); |
314 | return _M_w[0]; |
315 | } |
316 | #endif |
317 | |
318 | template<size_t _Nw> |
319 | size_t |
320 | _Base_bitset<_Nw>:: |
321 | _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT |
322 | { |
323 | for (size_t __i = 0; __i < _Nw; __i++) |
324 | { |
325 | _WordT __thisword = _M_w[__i]; |
326 | if (__thisword != static_cast<_WordT>(0)) |
327 | return (__i * _GLIBCXX_BITSET_BITS_PER_WORD |
328 | + __builtin_ctzl(__thisword)); |
329 | } |
330 | // not found, so return an indication of failure. |
331 | return __not_found; |
332 | } |
333 | |
334 | template<size_t _Nw> |
335 | size_t |
336 | _Base_bitset<_Nw>:: |
337 | _M_do_find_next(size_t __prev, size_t __not_found) const _GLIBCXX_NOEXCEPT |
338 | { |
339 | // make bound inclusive |
340 | ++__prev; |
341 | |
342 | // check out of bounds |
343 | if (__prev >= _Nw * _GLIBCXX_BITSET_BITS_PER_WORD) |
344 | return __not_found; |
345 | |
346 | // search first word |
347 | size_t __i = _S_whichword(pos: __prev); |
348 | _WordT __thisword = _M_w[__i]; |
349 | |
350 | // mask off bits below bound |
351 | __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(pos: __prev); |
352 | |
353 | if (__thisword != static_cast<_WordT>(0)) |
354 | return (__i * _GLIBCXX_BITSET_BITS_PER_WORD |
355 | + __builtin_ctzl(__thisword)); |
356 | |
357 | // check subsequent words |
358 | __i++; |
359 | for (; __i < _Nw; __i++) |
360 | { |
361 | __thisword = _M_w[__i]; |
362 | if (__thisword != static_cast<_WordT>(0)) |
363 | return (__i * _GLIBCXX_BITSET_BITS_PER_WORD |
364 | + __builtin_ctzl(__thisword)); |
365 | } |
366 | // not found, so return an indication of failure. |
367 | return __not_found; |
368 | } // end _M_do_find_next |
369 | |
370 | /** |
371 | * Base class, specialization for a single word. |
372 | * |
373 | * See documentation for bitset. |
374 | */ |
375 | template<> |
376 | struct _Base_bitset<1> |
377 | { |
378 | typedef unsigned long _WordT; |
379 | _WordT _M_w; |
380 | |
381 | _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT |
382 | : _M_w(0) |
383 | { } |
384 | |
385 | #if __cplusplus >= 201103L |
386 | constexpr _Base_bitset(unsigned long long __val) noexcept |
387 | #else |
388 | _Base_bitset(unsigned long __val) |
389 | #endif |
390 | : _M_w(__val) |
391 | { } |
392 | |
393 | static _GLIBCXX_CONSTEXPR size_t |
394 | _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT |
395 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
396 | |
397 | static _GLIBCXX_CONSTEXPR size_t |
398 | _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT |
399 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
400 | |
401 | static _GLIBCXX_CONSTEXPR size_t |
402 | _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT |
403 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
404 | |
405 | static _GLIBCXX_CONSTEXPR _WordT |
406 | _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT |
407 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } |
408 | |
409 | _WordT& |
410 | _M_getword(size_t) _GLIBCXX_NOEXCEPT |
411 | { return _M_w; } |
412 | |
413 | _GLIBCXX_CONSTEXPR _WordT |
414 | _M_getword(size_t) const _GLIBCXX_NOEXCEPT |
415 | { return _M_w; } |
416 | |
417 | #if __cplusplus >= 201103L |
418 | const _WordT* |
419 | _M_getdata() const noexcept |
420 | { return &_M_w; } |
421 | #endif |
422 | |
423 | _WordT& |
424 | _M_hiword() _GLIBCXX_NOEXCEPT |
425 | { return _M_w; } |
426 | |
427 | _GLIBCXX_CONSTEXPR _WordT |
428 | _M_hiword() const _GLIBCXX_NOEXCEPT |
429 | { return _M_w; } |
430 | |
431 | void |
432 | _M_do_and(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT |
433 | { _M_w &= __x._M_w; } |
434 | |
435 | void |
436 | _M_do_or(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT |
437 | { _M_w |= __x._M_w; } |
438 | |
439 | void |
440 | _M_do_xor(const _Base_bitset<1>& __x) _GLIBCXX_NOEXCEPT |
441 | { _M_w ^= __x._M_w; } |
442 | |
443 | void |
444 | _M_do_left_shift(size_t __shift) _GLIBCXX_NOEXCEPT |
445 | { _M_w <<= __shift; } |
446 | |
447 | void |
448 | _M_do_right_shift(size_t __shift) _GLIBCXX_NOEXCEPT |
449 | { _M_w >>= __shift; } |
450 | |
451 | void |
452 | _M_do_flip() _GLIBCXX_NOEXCEPT |
453 | { _M_w = ~_M_w; } |
454 | |
455 | void |
456 | _M_do_set() _GLIBCXX_NOEXCEPT |
457 | { _M_w = ~static_cast<_WordT>(0); } |
458 | |
459 | void |
460 | _M_do_reset() _GLIBCXX_NOEXCEPT |
461 | { _M_w = 0; } |
462 | |
463 | bool |
464 | _M_is_equal(const _Base_bitset<1>& __x) const _GLIBCXX_NOEXCEPT |
465 | { return _M_w == __x._M_w; } |
466 | |
467 | template<size_t _Nb> |
468 | bool |
469 | _M_are_all() const _GLIBCXX_NOEXCEPT |
470 | { return _M_w == (~static_cast<_WordT>(0) |
471 | >> (_GLIBCXX_BITSET_BITS_PER_WORD - _Nb)); } |
472 | |
473 | bool |
474 | _M_is_any() const _GLIBCXX_NOEXCEPT |
475 | { return _M_w != 0; } |
476 | |
477 | size_t |
478 | _M_do_count() const _GLIBCXX_NOEXCEPT |
479 | { return __builtin_popcountl(_M_w); } |
480 | |
481 | unsigned long |
482 | _M_do_to_ulong() const _GLIBCXX_NOEXCEPT |
483 | { return _M_w; } |
484 | |
485 | #if __cplusplus >= 201103L |
486 | unsigned long long |
487 | _M_do_to_ullong() const noexcept |
488 | { return _M_w; } |
489 | #endif |
490 | |
491 | size_t |
492 | _M_do_find_first(size_t __not_found) const _GLIBCXX_NOEXCEPT |
493 | { |
494 | if (_M_w != 0) |
495 | return __builtin_ctzl(_M_w); |
496 | else |
497 | return __not_found; |
498 | } |
499 | |
500 | // find the next "on" bit that follows "prev" |
501 | size_t |
502 | _M_do_find_next(size_t __prev, size_t __not_found) const |
503 | _GLIBCXX_NOEXCEPT |
504 | { |
505 | ++__prev; |
506 | if (__prev >= ((size_t) _GLIBCXX_BITSET_BITS_PER_WORD)) |
507 | return __not_found; |
508 | |
509 | _WordT __x = _M_w >> __prev; |
510 | if (__x != 0) |
511 | return __builtin_ctzl(__x) + __prev; |
512 | else |
513 | return __not_found; |
514 | } |
515 | }; |
516 | |
517 | /** |
518 | * Base class, specialization for no storage (zero-length %bitset). |
519 | * |
520 | * See documentation for bitset. |
521 | */ |
522 | template<> |
523 | struct _Base_bitset<0> |
524 | { |
525 | typedef unsigned long _WordT; |
526 | |
527 | _GLIBCXX_CONSTEXPR _Base_bitset() _GLIBCXX_NOEXCEPT |
528 | { } |
529 | |
530 | #if __cplusplus >= 201103L |
531 | constexpr _Base_bitset(unsigned long long) noexcept |
532 | #else |
533 | _Base_bitset(unsigned long) |
534 | #endif |
535 | { } |
536 | |
537 | static _GLIBCXX_CONSTEXPR size_t |
538 | _S_whichword(size_t __pos) _GLIBCXX_NOEXCEPT |
539 | { return __pos / _GLIBCXX_BITSET_BITS_PER_WORD; } |
540 | |
541 | static _GLIBCXX_CONSTEXPR size_t |
542 | _S_whichbyte(size_t __pos) _GLIBCXX_NOEXCEPT |
543 | { return (__pos % _GLIBCXX_BITSET_BITS_PER_WORD) / __CHAR_BIT__; } |
544 | |
545 | static _GLIBCXX_CONSTEXPR size_t |
546 | _S_whichbit(size_t __pos) _GLIBCXX_NOEXCEPT |
547 | { return __pos % _GLIBCXX_BITSET_BITS_PER_WORD; } |
548 | |
549 | static _GLIBCXX_CONSTEXPR _WordT |
550 | _S_maskbit(size_t __pos) _GLIBCXX_NOEXCEPT |
551 | { return (static_cast<_WordT>(1)) << _S_whichbit(__pos); } |
552 | |
553 | // This would normally give access to the data. The bounds-checking |
554 | // in the bitset class will prevent the user from getting this far, |
555 | // but (1) it must still return an lvalue to compile, and (2) the |
556 | // user might call _Unchecked_set directly, in which case this /needs/ |
557 | // to fail. Let's not penalize zero-length users unless they actually |
558 | // make an unchecked call; all the memory ugliness is therefore |
559 | // localized to this single should-never-get-this-far function. |
560 | _WordT& |
561 | _M_getword(size_t) _GLIBCXX_NOEXCEPT |
562 | { |
563 | __throw_out_of_range(__N("_Base_bitset::_M_getword" )); |
564 | return *new _WordT; |
565 | } |
566 | |
567 | _GLIBCXX_CONSTEXPR _WordT |
568 | _M_getword(size_t) const _GLIBCXX_NOEXCEPT |
569 | { return 0; } |
570 | |
571 | _GLIBCXX_CONSTEXPR _WordT |
572 | _M_hiword() const _GLIBCXX_NOEXCEPT |
573 | { return 0; } |
574 | |
575 | void |
576 | _M_do_and(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT |
577 | { } |
578 | |
579 | void |
580 | _M_do_or(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT |
581 | { } |
582 | |
583 | void |
584 | _M_do_xor(const _Base_bitset<0>&) _GLIBCXX_NOEXCEPT |
585 | { } |
586 | |
587 | void |
588 | _M_do_left_shift(size_t) _GLIBCXX_NOEXCEPT |
589 | { } |
590 | |
591 | void |
592 | _M_do_right_shift(size_t) _GLIBCXX_NOEXCEPT |
593 | { } |
594 | |
595 | void |
596 | _M_do_flip() _GLIBCXX_NOEXCEPT |
597 | { } |
598 | |
599 | void |
600 | _M_do_set() _GLIBCXX_NOEXCEPT |
601 | { } |
602 | |
603 | void |
604 | _M_do_reset() _GLIBCXX_NOEXCEPT |
605 | { } |
606 | |
607 | // Are all empty bitsets equal to each other? Are they equal to |
608 | // themselves? How to compare a thing which has no state? What is |
609 | // the sound of one zero-length bitset clapping? |
610 | bool |
611 | _M_is_equal(const _Base_bitset<0>&) const _GLIBCXX_NOEXCEPT |
612 | { return true; } |
613 | |
614 | template<size_t _Nb> |
615 | bool |
616 | _M_are_all() const _GLIBCXX_NOEXCEPT |
617 | { return true; } |
618 | |
619 | bool |
620 | _M_is_any() const _GLIBCXX_NOEXCEPT |
621 | { return false; } |
622 | |
623 | size_t |
624 | _M_do_count() const _GLIBCXX_NOEXCEPT |
625 | { return 0; } |
626 | |
627 | unsigned long |
628 | _M_do_to_ulong() const _GLIBCXX_NOEXCEPT |
629 | { return 0; } |
630 | |
631 | #if __cplusplus >= 201103L |
632 | unsigned long long |
633 | _M_do_to_ullong() const noexcept |
634 | { return 0; } |
635 | #endif |
636 | |
637 | // Normally "not found" is the size, but that could also be |
638 | // misinterpreted as an index in this corner case. Oh well. |
639 | size_t |
640 | _M_do_find_first(size_t) const _GLIBCXX_NOEXCEPT |
641 | { return 0; } |
642 | |
643 | size_t |
644 | _M_do_find_next(size_t, size_t) const _GLIBCXX_NOEXCEPT |
645 | { return 0; } |
646 | }; |
647 | |
648 | |
649 | // Helper class to zero out the unused high-order bits in the highest word. |
650 | template<size_t _Extrabits> |
651 | struct _Sanitize |
652 | { |
653 | typedef unsigned long _WordT; |
654 | |
655 | static void |
656 | _S_do_sanitize(_WordT& __val) _GLIBCXX_NOEXCEPT |
657 | { __val &= ~((~static_cast<_WordT>(0)) << _Extrabits); } |
658 | }; |
659 | |
660 | template<> |
661 | struct _Sanitize<0> |
662 | { |
663 | typedef unsigned long _WordT; |
664 | |
665 | static void |
666 | _S_do_sanitize(_WordT) _GLIBCXX_NOEXCEPT { } |
667 | }; |
668 | |
669 | #if __cplusplus >= 201103L |
670 | template<size_t _Nb, bool = (_Nb < _GLIBCXX_BITSET_BITS_PER_ULL)> |
671 | struct _Sanitize_val |
672 | { |
673 | static constexpr unsigned long long |
674 | _S_do_sanitize_val(unsigned long long __val) |
675 | { return __val; } |
676 | }; |
677 | |
678 | template<size_t _Nb> |
679 | struct _Sanitize_val<_Nb, true> |
680 | { |
681 | static constexpr unsigned long long |
682 | _S_do_sanitize_val(unsigned long long __val) |
683 | { return __val & ~((~static_cast<unsigned long long>(0)) << _Nb); } |
684 | }; |
685 | #endif |
686 | |
687 | /** |
688 | * @brief The %bitset class represents a @e fixed-size sequence of bits. |
689 | * @ingroup utilities |
690 | * |
691 | * (Note that %bitset does @e not meet the formal requirements of a |
692 | * <a href="tables.html#65">container</a>. Mainly, it lacks iterators.) |
693 | * |
694 | * The template argument, @a Nb, may be any non-negative number, |
695 | * specifying the number of bits (e.g., "0", "12", "1024*1024"). |
696 | * |
697 | * In the general unoptimized case, storage is allocated in word-sized |
698 | * blocks. Let B be the number of bits in a word, then (Nb+(B-1))/B |
699 | * words will be used for storage. B - Nb%B bits are unused. (They are |
700 | * the high-order bits in the highest word.) It is a class invariant |
701 | * that those unused bits are always zero. |
702 | * |
703 | * If you think of %bitset as <em>a simple array of bits</em>, be |
704 | * aware that your mental picture is reversed: a %bitset behaves |
705 | * the same way as bits in integers do, with the bit at index 0 in |
706 | * the <em>least significant / right-hand</em> position, and the bit at |
707 | * index Nb-1 in the <em>most significant / left-hand</em> position. |
708 | * Thus, unlike other containers, a %bitset's index <em>counts from |
709 | * right to left</em>, to put it very loosely. |
710 | * |
711 | * This behavior is preserved when translating to and from strings. For |
712 | * example, the first line of the following program probably prints |
713 | * <em>b('a') is 0001100001</em> on a modern ASCII system. |
714 | * |
715 | * @code |
716 | * #include <bitset> |
717 | * #include <iostream> |
718 | * #include <sstream> |
719 | * |
720 | * using namespace std; |
721 | * |
722 | * int main() |
723 | * { |
724 | * long a = 'a'; |
725 | * bitset<10> b(a); |
726 | * |
727 | * cout << "b('a') is " << b << endl; |
728 | * |
729 | * ostringstream s; |
730 | * s << b; |
731 | * string str = s.str(); |
732 | * cout << "index 3 in the string is " << str[3] << " but\n" |
733 | * << "index 3 in the bitset is " << b[3] << endl; |
734 | * } |
735 | * @endcode |
736 | * |
737 | * Also see: |
738 | * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html |
739 | * for a description of extensions. |
740 | * |
741 | * Most of the actual code isn't contained in %bitset<> itself, but in the |
742 | * base class _Base_bitset. The base class works with whole words, not with |
743 | * individual bits. This allows us to specialize _Base_bitset for the |
744 | * important special case where the %bitset is only a single word. |
745 | * |
746 | * Extra confusion can result due to the fact that the storage for |
747 | * _Base_bitset @e is a regular array, and is indexed as such. This is |
748 | * carefully encapsulated. |
749 | */ |
750 | template<size_t _Nb> |
751 | class bitset |
752 | : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> |
753 | { |
754 | private: |
755 | typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; |
756 | typedef unsigned long _WordT; |
757 | |
758 | template<class _CharT, class _Traits, class _Alloc> |
759 | void |
760 | _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s, |
761 | size_t __position) const |
762 | { |
763 | if (__position > __s.size()) |
764 | __throw_out_of_range_fmt(__N("bitset::bitset: __position " |
765 | "(which is %zu) > __s.size() " |
766 | "(which is %zu)" ), |
767 | __position, __s.size()); |
768 | } |
769 | |
770 | void _M_check(size_t __position, const char *__s) const |
771 | { |
772 | if (__position >= _Nb) |
773 | __throw_out_of_range_fmt(__N("%s: __position (which is %zu) " |
774 | ">= _Nb (which is %zu)" ), |
775 | __s, __position, _Nb); |
776 | } |
777 | |
778 | void |
779 | _M_do_sanitize() _GLIBCXX_NOEXCEPT |
780 | { |
781 | typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; |
782 | __sanitize_type::_S_do_sanitize(this->_M_hiword()); |
783 | } |
784 | |
785 | #if __cplusplus >= 201103L |
786 | friend struct std::hash<bitset>; |
787 | #endif |
788 | |
789 | public: |
790 | /** |
791 | * This encapsulates the concept of a single bit. An instance of this |
792 | * class is a proxy for an actual bit; this way the individual bit |
793 | * operations are done as faster word-size bitwise instructions. |
794 | * |
795 | * Most users will never need to use this class directly; conversions |
796 | * to and from bool are automatic and should be transparent. Overloaded |
797 | * operators help to preserve the illusion. |
798 | * |
799 | * (On a typical system, this <em>bit %reference</em> is 64 |
800 | * times the size of an actual bit. Ha.) |
801 | */ |
802 | class reference |
803 | { |
804 | friend class bitset; |
805 | |
806 | _WordT* _M_wp; |
807 | size_t _M_bpos; |
808 | |
809 | // left undefined |
810 | reference(); |
811 | |
812 | public: |
813 | reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT |
814 | { |
815 | _M_wp = &__b._M_getword(__pos); |
816 | _M_bpos = _Base::_S_whichbit(__pos); |
817 | } |
818 | |
819 | #if __cplusplus >= 201103L |
820 | reference(const reference&) = default; |
821 | #endif |
822 | |
823 | ~reference() _GLIBCXX_NOEXCEPT |
824 | { } |
825 | |
826 | // For b[i] = __x; |
827 | reference& |
828 | operator=(bool __x) _GLIBCXX_NOEXCEPT |
829 | { |
830 | if (__x) |
831 | *_M_wp |= _Base::_S_maskbit(_M_bpos); |
832 | else |
833 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); |
834 | return *this; |
835 | } |
836 | |
837 | // For b[i] = b[__j]; |
838 | reference& |
839 | operator=(const reference& __j) _GLIBCXX_NOEXCEPT |
840 | { |
841 | if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) |
842 | *_M_wp |= _Base::_S_maskbit(_M_bpos); |
843 | else |
844 | *_M_wp &= ~_Base::_S_maskbit(_M_bpos); |
845 | return *this; |
846 | } |
847 | |
848 | // Flips the bit |
849 | bool |
850 | operator~() const _GLIBCXX_NOEXCEPT |
851 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } |
852 | |
853 | // For __x = b[i]; |
854 | operator bool() const _GLIBCXX_NOEXCEPT |
855 | { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } |
856 | |
857 | // For b[i].flip(); |
858 | reference& |
859 | flip() _GLIBCXX_NOEXCEPT |
860 | { |
861 | *_M_wp ^= _Base::_S_maskbit(_M_bpos); |
862 | return *this; |
863 | } |
864 | }; |
865 | friend class reference; |
866 | |
867 | // 23.3.5.1 constructors: |
868 | /// All bits set to zero. |
869 | _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT |
870 | { } |
871 | |
872 | /// Initial bits bitwise-copied from a single word (others set to zero). |
873 | #if __cplusplus >= 201103L |
874 | constexpr bitset(unsigned long long __val) noexcept |
875 | : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } |
876 | #else |
877 | bitset(unsigned long __val) |
878 | : _Base(__val) |
879 | { _M_do_sanitize(); } |
880 | #endif |
881 | |
882 | /** |
883 | * Use a subset of a string. |
884 | * @param __s A string of @a 0 and @a 1 characters. |
885 | * @param __position Index of the first character in @a __s to use; |
886 | * defaults to zero. |
887 | * @throw std::out_of_range If @a pos is bigger the size of @a __s. |
888 | * @throw std::invalid_argument If a character appears in the string |
889 | * which is neither @a 0 nor @a 1. |
890 | */ |
891 | template<class _CharT, class _Traits, class _Alloc> |
892 | explicit |
893 | bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, |
894 | size_t __position = 0) |
895 | : _Base() |
896 | { |
897 | _M_check_initial_position(__s, __position); |
898 | _M_copy_from_string(__s, __position, |
899 | std::basic_string<_CharT, _Traits, _Alloc>::npos, |
900 | _CharT('0'), _CharT('1')); |
901 | } |
902 | |
903 | /** |
904 | * Use a subset of a string. |
905 | * @param __s A string of @a 0 and @a 1 characters. |
906 | * @param __position Index of the first character in @a __s to use. |
907 | * @param __n The number of characters to copy. |
908 | * @throw std::out_of_range If @a __position is bigger the size |
909 | * of @a __s. |
910 | * @throw std::invalid_argument If a character appears in the string |
911 | * which is neither @a 0 nor @a 1. |
912 | */ |
913 | template<class _CharT, class _Traits, class _Alloc> |
914 | bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, |
915 | size_t __position, size_t __n) |
916 | : _Base() |
917 | { |
918 | _M_check_initial_position(__s, __position); |
919 | _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); |
920 | } |
921 | |
922 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
923 | // 396. what are characters zero and one. |
924 | template<class _CharT, class _Traits, class _Alloc> |
925 | bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, |
926 | size_t __position, size_t __n, |
927 | _CharT __zero, _CharT __one = _CharT('1')) |
928 | : _Base() |
929 | { |
930 | _M_check_initial_position(__s, __position); |
931 | _M_copy_from_string(__s, __position, __n, __zero, __one); |
932 | } |
933 | |
934 | #if __cplusplus >= 201103L |
935 | /** |
936 | * Construct from a character %array. |
937 | * @param __str An %array of characters @a zero and @a one. |
938 | * @param __n The number of characters to use. |
939 | * @param __zero The character corresponding to the value 0. |
940 | * @param __one The character corresponding to the value 1. |
941 | * @throw std::invalid_argument If a character appears in the string |
942 | * which is neither @a __zero nor @a __one. |
943 | */ |
944 | template<typename _CharT> |
945 | explicit |
946 | bitset(const _CharT* __str, |
947 | typename std::basic_string<_CharT>::size_type __n |
948 | = std::basic_string<_CharT>::npos, |
949 | _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) |
950 | : _Base() |
951 | { |
952 | if (!__str) |
953 | __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)" )); |
954 | |
955 | if (__n == std::basic_string<_CharT>::npos) |
956 | __n = std::char_traits<_CharT>::length(__str); |
957 | _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0, |
958 | __n, __zero, |
959 | __one); |
960 | } |
961 | #endif |
962 | |
963 | // 23.3.5.2 bitset operations: |
964 | ///@{ |
965 | /** |
966 | * Operations on bitsets. |
967 | * @param __rhs A same-sized bitset. |
968 | * |
969 | * These should be self-explanatory. |
970 | */ |
971 | bitset<_Nb>& |
972 | operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT |
973 | { |
974 | this->_M_do_and(__rhs); |
975 | return *this; |
976 | } |
977 | |
978 | bitset<_Nb>& |
979 | operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT |
980 | { |
981 | this->_M_do_or(__rhs); |
982 | return *this; |
983 | } |
984 | |
985 | bitset<_Nb>& |
986 | operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT |
987 | { |
988 | this->_M_do_xor(__rhs); |
989 | return *this; |
990 | } |
991 | ///@} |
992 | |
993 | ///@{ |
994 | /** |
995 | * Operations on bitsets. |
996 | * @param __position The number of places to shift. |
997 | * |
998 | * These should be self-explanatory. |
999 | */ |
1000 | bitset<_Nb>& |
1001 | operator<<=(size_t __position) _GLIBCXX_NOEXCEPT |
1002 | { |
1003 | if (__builtin_expect(__position < _Nb, 1)) |
1004 | { |
1005 | this->_M_do_left_shift(__position); |
1006 | this->_M_do_sanitize(); |
1007 | } |
1008 | else |
1009 | this->_M_do_reset(); |
1010 | return *this; |
1011 | } |
1012 | |
1013 | bitset<_Nb>& |
1014 | operator>>=(size_t __position) _GLIBCXX_NOEXCEPT |
1015 | { |
1016 | if (__builtin_expect(__position < _Nb, 1)) |
1017 | { |
1018 | this->_M_do_right_shift(__position); |
1019 | this->_M_do_sanitize(); |
1020 | } |
1021 | else |
1022 | this->_M_do_reset(); |
1023 | return *this; |
1024 | } |
1025 | ///@} |
1026 | |
1027 | ///@{ |
1028 | /** |
1029 | * These versions of single-bit set, reset, flip, and test are |
1030 | * extensions from the SGI version. They do no range checking. |
1031 | * @ingroup SGIextensions |
1032 | */ |
1033 | bitset<_Nb>& |
1034 | _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT |
1035 | { |
1036 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); |
1037 | return *this; |
1038 | } |
1039 | |
1040 | bitset<_Nb>& |
1041 | _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT |
1042 | { |
1043 | if (__val) |
1044 | this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); |
1045 | else |
1046 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); |
1047 | return *this; |
1048 | } |
1049 | |
1050 | bitset<_Nb>& |
1051 | _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT |
1052 | { |
1053 | this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); |
1054 | return *this; |
1055 | } |
1056 | |
1057 | bitset<_Nb>& |
1058 | _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT |
1059 | { |
1060 | this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); |
1061 | return *this; |
1062 | } |
1063 | |
1064 | _GLIBCXX_CONSTEXPR bool |
1065 | _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT |
1066 | { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) |
1067 | != static_cast<_WordT>(0)); } |
1068 | ///@} |
1069 | |
1070 | // Set, reset, and flip. |
1071 | /** |
1072 | * @brief Sets every bit to true. |
1073 | */ |
1074 | bitset<_Nb>& |
1075 | set() _GLIBCXX_NOEXCEPT |
1076 | { |
1077 | this->_M_do_set(); |
1078 | this->_M_do_sanitize(); |
1079 | return *this; |
1080 | } |
1081 | |
1082 | /** |
1083 | * @brief Sets a given bit to a particular value. |
1084 | * @param __position The index of the bit. |
1085 | * @param __val Either true or false, defaults to true. |
1086 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
1087 | */ |
1088 | bitset<_Nb>& |
1089 | set(size_t __position, bool __val = true) |
1090 | { |
1091 | this->_M_check(__position, __N("bitset::set" )); |
1092 | return _Unchecked_set(__position, __val); |
1093 | } |
1094 | |
1095 | /** |
1096 | * @brief Sets every bit to false. |
1097 | */ |
1098 | bitset<_Nb>& |
1099 | reset() _GLIBCXX_NOEXCEPT |
1100 | { |
1101 | this->_M_do_reset(); |
1102 | return *this; |
1103 | } |
1104 | |
1105 | /** |
1106 | * @brief Sets a given bit to false. |
1107 | * @param __position The index of the bit. |
1108 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
1109 | * |
1110 | * Same as writing @c set(pos,false). |
1111 | */ |
1112 | bitset<_Nb>& |
1113 | reset(size_t __position) |
1114 | { |
1115 | this->_M_check(__position, __N("bitset::reset" )); |
1116 | return _Unchecked_reset(pos: __position); |
1117 | } |
1118 | |
1119 | /** |
1120 | * @brief Toggles every bit to its opposite value. |
1121 | */ |
1122 | bitset<_Nb>& |
1123 | flip() _GLIBCXX_NOEXCEPT |
1124 | { |
1125 | this->_M_do_flip(); |
1126 | this->_M_do_sanitize(); |
1127 | return *this; |
1128 | } |
1129 | |
1130 | /** |
1131 | * @brief Toggles a given bit to its opposite value. |
1132 | * @param __position The index of the bit. |
1133 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
1134 | */ |
1135 | bitset<_Nb>& |
1136 | flip(size_t __position) |
1137 | { |
1138 | this->_M_check(__position, __N("bitset::flip" )); |
1139 | return _Unchecked_flip(pos: __position); |
1140 | } |
1141 | |
1142 | /// See the no-argument flip(). |
1143 | bitset<_Nb> |
1144 | operator~() const _GLIBCXX_NOEXCEPT |
1145 | { return bitset<_Nb>(*this).flip(); } |
1146 | |
1147 | ///@{ |
1148 | /** |
1149 | * @brief Array-indexing support. |
1150 | * @param __position Index into the %bitset. |
1151 | * @return A bool for a <em>const %bitset</em>. For non-const |
1152 | * bitsets, an instance of the reference proxy class. |
1153 | * @note These operators do no range checking and throw no exceptions, |
1154 | * as required by DR 11 to the standard. |
1155 | * |
1156 | * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already |
1157 | * resolves DR 11 (items 1 and 2), but does not do the range-checking |
1158 | * required by that DR's resolution. -pme |
1159 | * The DR has since been changed: range-checking is a precondition |
1160 | * (users' responsibility), and these functions must not throw. -pme |
1161 | */ |
1162 | reference |
1163 | operator[](size_t __position) |
1164 | { return reference(*this, __position); } |
1165 | |
1166 | _GLIBCXX_CONSTEXPR bool |
1167 | operator[](size_t __position) const |
1168 | { return _Unchecked_test(pos: __position); } |
1169 | ///@} |
1170 | |
1171 | /** |
1172 | * @brief Returns a numerical interpretation of the %bitset. |
1173 | * @return The integral equivalent of the bits. |
1174 | * @throw std::overflow_error If there are too many bits to be |
1175 | * represented in an @c unsigned @c long. |
1176 | */ |
1177 | unsigned long |
1178 | to_ulong() const |
1179 | { return this->_M_do_to_ulong(); } |
1180 | |
1181 | #if __cplusplus >= 201103L |
1182 | unsigned long long |
1183 | to_ullong() const |
1184 | { return this->_M_do_to_ullong(); } |
1185 | #endif |
1186 | |
1187 | /** |
1188 | * @brief Returns a character interpretation of the %bitset. |
1189 | * @return The string equivalent of the bits. |
1190 | * |
1191 | * Note the ordering of the bits: decreasing character positions |
1192 | * correspond to increasing bit positions (see the main class notes for |
1193 | * an example). |
1194 | */ |
1195 | template<class _CharT, class _Traits, class _Alloc> |
1196 | std::basic_string<_CharT, _Traits, _Alloc> |
1197 | to_string() const |
1198 | { |
1199 | std::basic_string<_CharT, _Traits, _Alloc> __result; |
1200 | _M_copy_to_string(__result, _CharT('0'), _CharT('1')); |
1201 | return __result; |
1202 | } |
1203 | |
1204 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1205 | // 396. what are characters zero and one. |
1206 | template<class _CharT, class _Traits, class _Alloc> |
1207 | std::basic_string<_CharT, _Traits, _Alloc> |
1208 | to_string(_CharT __zero, _CharT __one = _CharT('1')) const |
1209 | { |
1210 | std::basic_string<_CharT, _Traits, _Alloc> __result; |
1211 | _M_copy_to_string(__result, __zero, __one); |
1212 | return __result; |
1213 | } |
1214 | |
1215 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1216 | // 434. bitset::to_string() hard to use. |
1217 | template<class _CharT, class _Traits> |
1218 | std::basic_string<_CharT, _Traits, std::allocator<_CharT> > |
1219 | to_string() const |
1220 | { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } |
1221 | |
1222 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1223 | // 853. to_string needs updating with zero and one. |
1224 | template<class _CharT, class _Traits> |
1225 | std::basic_string<_CharT, _Traits, std::allocator<_CharT> > |
1226 | to_string(_CharT __zero, _CharT __one = _CharT('1')) const |
1227 | { return to_string<_CharT, _Traits, |
1228 | std::allocator<_CharT> >(__zero, __one); } |
1229 | |
1230 | template<class _CharT> |
1231 | std::basic_string<_CharT, std::char_traits<_CharT>, |
1232 | std::allocator<_CharT> > |
1233 | to_string() const |
1234 | { |
1235 | return to_string<_CharT, std::char_traits<_CharT>, |
1236 | std::allocator<_CharT> >(); |
1237 | } |
1238 | |
1239 | template<class _CharT> |
1240 | std::basic_string<_CharT, std::char_traits<_CharT>, |
1241 | std::allocator<_CharT> > |
1242 | to_string(_CharT __zero, _CharT __one = _CharT('1')) const |
1243 | { |
1244 | return to_string<_CharT, std::char_traits<_CharT>, |
1245 | std::allocator<_CharT> >(__zero, __one); |
1246 | } |
1247 | |
1248 | std::basic_string<char, std::char_traits<char>, std::allocator<char> > |
1249 | to_string() const |
1250 | { |
1251 | return to_string<char, std::char_traits<char>, |
1252 | std::allocator<char> >(); |
1253 | } |
1254 | |
1255 | std::basic_string<char, std::char_traits<char>, std::allocator<char> > |
1256 | to_string(char __zero, char __one = '1') const |
1257 | { |
1258 | return to_string<char, std::char_traits<char>, |
1259 | std::allocator<char> >(__zero, __one); |
1260 | } |
1261 | |
1262 | // Helper functions for string operations. |
1263 | template<class _CharT, class _Traits> |
1264 | void |
1265 | _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, |
1266 | _CharT, _CharT); |
1267 | |
1268 | template<class _CharT, class _Traits, class _Alloc> |
1269 | void |
1270 | _M_copy_from_string(const std::basic_string<_CharT, |
1271 | _Traits, _Alloc>& __s, size_t __pos, size_t __n, |
1272 | _CharT __zero, _CharT __one) |
1273 | { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, |
1274 | __zero, __one); } |
1275 | |
1276 | template<class _CharT, class _Traits, class _Alloc> |
1277 | void |
1278 | _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, |
1279 | _CharT, _CharT) const; |
1280 | |
1281 | // NB: Backward compat. |
1282 | template<class _CharT, class _Traits, class _Alloc> |
1283 | void |
1284 | _M_copy_from_string(const std::basic_string<_CharT, |
1285 | _Traits, _Alloc>& __s, size_t __pos, size_t __n) |
1286 | { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } |
1287 | |
1288 | template<class _CharT, class _Traits, class _Alloc> |
1289 | void |
1290 | _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const |
1291 | { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } |
1292 | |
1293 | /// Returns the number of bits which are set. |
1294 | size_t |
1295 | count() const _GLIBCXX_NOEXCEPT |
1296 | { return this->_M_do_count(); } |
1297 | |
1298 | /// Returns the total number of bits. |
1299 | _GLIBCXX_CONSTEXPR size_t |
1300 | size() const _GLIBCXX_NOEXCEPT |
1301 | { return _Nb; } |
1302 | |
1303 | ///@{ |
1304 | /// These comparisons for equality/inequality are, well, @e bitwise. |
1305 | bool |
1306 | operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT |
1307 | { return this->_M_is_equal(__rhs); } |
1308 | |
1309 | #if __cpp_impl_three_way_comparison < 201907L |
1310 | bool |
1311 | operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT |
1312 | { return !this->_M_is_equal(__rhs); } |
1313 | #endif |
1314 | ///@} |
1315 | |
1316 | /** |
1317 | * @brief Tests the value of a bit. |
1318 | * @param __position The index of a bit. |
1319 | * @return The value at @a pos. |
1320 | * @throw std::out_of_range If @a pos is bigger the size of the %set. |
1321 | */ |
1322 | bool |
1323 | test(size_t __position) const |
1324 | { |
1325 | this->_M_check(__position, __N("bitset::test" )); |
1326 | return _Unchecked_test(pos: __position); |
1327 | } |
1328 | |
1329 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1330 | // DR 693. std::bitset::all() missing. |
1331 | /** |
1332 | * @brief Tests whether all the bits are on. |
1333 | * @return True if all the bits are set. |
1334 | */ |
1335 | bool |
1336 | all() const _GLIBCXX_NOEXCEPT |
1337 | { return this->template _M_are_all<_Nb>(); } |
1338 | |
1339 | /** |
1340 | * @brief Tests whether any of the bits are on. |
1341 | * @return True if at least one bit is set. |
1342 | */ |
1343 | bool |
1344 | any() const _GLIBCXX_NOEXCEPT |
1345 | { return this->_M_is_any(); } |
1346 | |
1347 | /** |
1348 | * @brief Tests whether any of the bits are on. |
1349 | * @return True if none of the bits are set. |
1350 | */ |
1351 | bool |
1352 | none() const _GLIBCXX_NOEXCEPT |
1353 | { return !this->_M_is_any(); } |
1354 | |
1355 | ///@{ |
1356 | /// Self-explanatory. |
1357 | bitset<_Nb> |
1358 | operator<<(size_t __position) const _GLIBCXX_NOEXCEPT |
1359 | { return bitset<_Nb>(*this) <<= __position; } |
1360 | |
1361 | bitset<_Nb> |
1362 | operator>>(size_t __position) const _GLIBCXX_NOEXCEPT |
1363 | { return bitset<_Nb>(*this) >>= __position; } |
1364 | ///@} |
1365 | |
1366 | /** |
1367 | * @brief Finds the index of the first "on" bit. |
1368 | * @return The index of the first bit set, or size() if not found. |
1369 | * @ingroup SGIextensions |
1370 | * @sa _Find_next |
1371 | */ |
1372 | size_t |
1373 | _Find_first() const _GLIBCXX_NOEXCEPT |
1374 | { return this->_M_do_find_first(_Nb); } |
1375 | |
1376 | /** |
1377 | * @brief Finds the index of the next "on" bit after prev. |
1378 | * @return The index of the next bit set, or size() if not found. |
1379 | * @param __prev Where to start searching. |
1380 | * @ingroup SGIextensions |
1381 | * @sa _Find_first |
1382 | */ |
1383 | size_t |
1384 | _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT |
1385 | { return this->_M_do_find_next(__prev, _Nb); } |
1386 | }; |
1387 | |
1388 | // Definitions of non-inline member functions. |
1389 | template<size_t _Nb> |
1390 | template<class _CharT, class _Traits> |
1391 | void |
1392 | bitset<_Nb>:: |
1393 | _M_copy_from_ptr(const _CharT* __s, size_t __len, |
1394 | size_t __pos, size_t __n, _CharT __zero, _CharT __one) |
1395 | { |
1396 | reset(); |
1397 | const size_t __nbits = std::min(a: _Nb, b: std::min(a: __n, b: size_t(__len - __pos))); |
1398 | for (size_t __i = __nbits; __i > 0; --__i) |
1399 | { |
1400 | const _CharT __c = __s[__pos + __nbits - __i]; |
1401 | if (_Traits::eq(__c, __zero)) |
1402 | ; |
1403 | else if (_Traits::eq(__c, __one)) |
1404 | _Unchecked_set(__i - 1); |
1405 | else |
1406 | __throw_invalid_argument(__N("bitset::_M_copy_from_ptr" )); |
1407 | } |
1408 | } |
1409 | |
1410 | template<size_t _Nb> |
1411 | template<class _CharT, class _Traits, class _Alloc> |
1412 | void |
1413 | bitset<_Nb>:: |
1414 | _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, |
1415 | _CharT __zero, _CharT __one) const |
1416 | { |
1417 | __s.assign(_Nb, __zero); |
1418 | for (size_t __i = _Nb; __i > 0; --__i) |
1419 | if (_Unchecked_test(pos: __i - 1)) |
1420 | _Traits::assign(__s[_Nb - __i], __one); |
1421 | } |
1422 | |
1423 | // 23.3.5.3 bitset operations: |
1424 | ///@{ |
1425 | /** |
1426 | * @brief Global bitwise operations on bitsets. |
1427 | * @param __x A bitset. |
1428 | * @param __y A bitset of the same size as @a __x. |
1429 | * @return A new bitset. |
1430 | * |
1431 | * These should be self-explanatory. |
1432 | */ |
1433 | template<size_t _Nb> |
1434 | inline bitset<_Nb> |
1435 | operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT |
1436 | { |
1437 | bitset<_Nb> __result(__x); |
1438 | __result &= __y; |
1439 | return __result; |
1440 | } |
1441 | |
1442 | template<size_t _Nb> |
1443 | inline bitset<_Nb> |
1444 | operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT |
1445 | { |
1446 | bitset<_Nb> __result(__x); |
1447 | __result |= __y; |
1448 | return __result; |
1449 | } |
1450 | |
1451 | template <size_t _Nb> |
1452 | inline bitset<_Nb> |
1453 | operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT |
1454 | { |
1455 | bitset<_Nb> __result(__x); |
1456 | __result ^= __y; |
1457 | return __result; |
1458 | } |
1459 | ///@} |
1460 | |
1461 | ///@{ |
1462 | /** |
1463 | * @brief Global I/O operators for bitsets. |
1464 | * |
1465 | * Direct I/O between streams and bitsets is supported. Output is |
1466 | * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 |
1467 | * characters, and will only extract as many digits as the %bitset will |
1468 | * hold. |
1469 | */ |
1470 | template<class _CharT, class _Traits, size_t _Nb> |
1471 | std::basic_istream<_CharT, _Traits>& |
1472 | operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) |
1473 | { |
1474 | typedef typename _Traits::char_type char_type; |
1475 | typedef std::basic_istream<_CharT, _Traits> __istream_type; |
1476 | typedef typename __istream_type::ios_base __ios_base; |
1477 | |
1478 | std::basic_string<_CharT, _Traits> __tmp; |
1479 | __tmp.reserve(_Nb); |
1480 | |
1481 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1482 | // 303. Bitset input operator underspecified |
1483 | const char_type __zero = __is.widen('0'); |
1484 | const char_type __one = __is.widen('1'); |
1485 | |
1486 | typename __ios_base::iostate __state = __ios_base::goodbit; |
1487 | typename __istream_type::sentry __sentry(__is); |
1488 | if (__sentry) |
1489 | { |
1490 | __try |
1491 | { |
1492 | for (size_t __i = _Nb; __i > 0; --__i) |
1493 | { |
1494 | static typename _Traits::int_type __eof = _Traits::eof(); |
1495 | |
1496 | typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); |
1497 | if (_Traits::eq_int_type(__c1, __eof)) |
1498 | { |
1499 | __state |= __ios_base::eofbit; |
1500 | break; |
1501 | } |
1502 | else |
1503 | { |
1504 | const char_type __c2 = _Traits::to_char_type(__c1); |
1505 | if (_Traits::eq(__c2, __zero)) |
1506 | __tmp.push_back(__zero); |
1507 | else if (_Traits::eq(__c2, __one)) |
1508 | __tmp.push_back(__one); |
1509 | else if (_Traits:: |
1510 | eq_int_type(__is.rdbuf()->sputbackc(__c2), |
1511 | __eof)) |
1512 | { |
1513 | __state |= __ios_base::failbit; |
1514 | break; |
1515 | } |
1516 | } |
1517 | } |
1518 | } |
1519 | __catch(__cxxabiv1::__forced_unwind&) |
1520 | { |
1521 | __is._M_setstate(__ios_base::badbit); |
1522 | __throw_exception_again; |
1523 | } |
1524 | __catch(...) |
1525 | { __is._M_setstate(__ios_base::badbit); } |
1526 | } |
1527 | |
1528 | if (__tmp.empty() && _Nb) |
1529 | __state |= __ios_base::failbit; |
1530 | else |
1531 | __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, |
1532 | __zero, __one); |
1533 | if (__state) |
1534 | __is.setstate(__state); |
1535 | return __is; |
1536 | } |
1537 | |
1538 | template <class _CharT, class _Traits, size_t _Nb> |
1539 | std::basic_ostream<_CharT, _Traits>& |
1540 | operator<<(std::basic_ostream<_CharT, _Traits>& __os, |
1541 | const bitset<_Nb>& __x) |
1542 | { |
1543 | std::basic_string<_CharT, _Traits> __tmp; |
1544 | |
1545 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
1546 | // 396. what are characters zero and one. |
1547 | const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); |
1548 | __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); |
1549 | return __os << __tmp; |
1550 | } |
1551 | ///@} |
1552 | |
1553 | _GLIBCXX_END_NAMESPACE_CONTAINER |
1554 | } // namespace std |
1555 | |
1556 | #undef _GLIBCXX_BITSET_WORDS |
1557 | #undef _GLIBCXX_BITSET_BITS_PER_WORD |
1558 | #undef _GLIBCXX_BITSET_BITS_PER_ULL |
1559 | |
1560 | #if __cplusplus >= 201103L |
1561 | |
1562 | namespace std _GLIBCXX_VISIBILITY(default) |
1563 | { |
1564 | _GLIBCXX_BEGIN_NAMESPACE_VERSION |
1565 | |
1566 | // DR 1182. |
1567 | /// std::hash specialization for bitset. |
1568 | template<size_t _Nb> |
1569 | struct hash<_GLIBCXX_STD_C::bitset<_Nb>> |
1570 | : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> |
1571 | { |
1572 | size_t |
1573 | operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept |
1574 | { |
1575 | const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; |
1576 | return std::_Hash_impl::hash(__b._M_getdata(), __clength); |
1577 | } |
1578 | }; |
1579 | |
1580 | template<> |
1581 | struct hash<_GLIBCXX_STD_C::bitset<0>> |
1582 | : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> |
1583 | { |
1584 | size_t |
1585 | operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept |
1586 | { return 0; } |
1587 | }; |
1588 | |
1589 | _GLIBCXX_END_NAMESPACE_VERSION |
1590 | } // namespace |
1591 | |
1592 | #endif // C++11 |
1593 | |
1594 | #ifdef _GLIBCXX_DEBUG |
1595 | # include <debug/bitset> |
1596 | #endif |
1597 | |
1598 | #endif /* _GLIBCXX_BITSET */ |
1599 | |