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