1// <bitset> -*- C++ -*-
2
3// Copyright (C) 2001-2019 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
64namespace 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(__prev);
348 _WordT __thisword = _M_w[__i];
349
350 // mask off bits below bound
351 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__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(&apos;a&apos;) 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(__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(__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(__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 bool
1310 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
1311 { return !this->_M_is_equal(__rhs); }
1312 //@}
1313
1314 /**
1315 * @brief Tests the value of a bit.
1316 * @param __position The index of a bit.
1317 * @return The value at @a pos.
1318 * @throw std::out_of_range If @a pos is bigger the size of the %set.
1319 */
1320 bool
1321 test(size_t __position) const
1322 {
1323 this->_M_check(__position, __N("bitset::test"));
1324 return _Unchecked_test(__position);
1325 }
1326
1327 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1328 // DR 693. std::bitset::all() missing.
1329 /**
1330 * @brief Tests whether all the bits are on.
1331 * @return True if all the bits are set.
1332 */
1333 bool
1334 all() const _GLIBCXX_NOEXCEPT
1335 { return this->template _M_are_all<_Nb>(); }
1336
1337 /**
1338 * @brief Tests whether any of the bits are on.
1339 * @return True if at least one bit is set.
1340 */
1341 bool
1342 any() const _GLIBCXX_NOEXCEPT
1343 { return this->_M_is_any(); }
1344
1345 /**
1346 * @brief Tests whether any of the bits are on.
1347 * @return True if none of the bits are set.
1348 */
1349 bool
1350 none() const _GLIBCXX_NOEXCEPT
1351 { return !this->_M_is_any(); }
1352
1353 //@{
1354 /// Self-explanatory.
1355 bitset<_Nb>
1356 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
1357 { return bitset<_Nb>(*this) <<= __position; }
1358
1359 bitset<_Nb>
1360 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
1361 { return bitset<_Nb>(*this) >>= __position; }
1362 //@}
1363
1364 /**
1365 * @brief Finds the index of the first "on" bit.
1366 * @return The index of the first bit set, or size() if not found.
1367 * @ingroup SGIextensions
1368 * @sa _Find_next
1369 */
1370 size_t
1371 _Find_first() const _GLIBCXX_NOEXCEPT
1372 { return this->_M_do_find_first(_Nb); }
1373
1374 /**
1375 * @brief Finds the index of the next "on" bit after prev.
1376 * @return The index of the next bit set, or size() if not found.
1377 * @param __prev Where to start searching.
1378 * @ingroup SGIextensions
1379 * @sa _Find_first
1380 */
1381 size_t
1382 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
1383 { return this->_M_do_find_next(__prev, _Nb); }
1384 };
1385
1386 // Definitions of non-inline member functions.
1387 template<size_t _Nb>
1388 template<class _CharT, class _Traits>
1389 void
1390 bitset<_Nb>::
1391 _M_copy_from_ptr(const _CharT* __s, size_t __len,
1392 size_t __pos, size_t __n, _CharT __zero, _CharT __one)
1393 {
1394 reset();
1395 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
1396 for (size_t __i = __nbits; __i > 0; --__i)
1397 {
1398 const _CharT __c = __s[__pos + __nbits - __i];
1399 if (_Traits::eq(__c, __zero))
1400 ;
1401 else if (_Traits::eq(__c, __one))
1402 _Unchecked_set(__i - 1);
1403 else
1404 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
1405 }
1406 }
1407
1408 template<size_t _Nb>
1409 template<class _CharT, class _Traits, class _Alloc>
1410 void
1411 bitset<_Nb>::
1412 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
1413 _CharT __zero, _CharT __one) const
1414 {
1415 __s.assign(_Nb, __zero);
1416 for (size_t __i = _Nb; __i > 0; --__i)
1417 if (_Unchecked_test(__i - 1))
1418 _Traits::assign(__s[_Nb - __i], __one);
1419 }
1420
1421 // 23.3.5.3 bitset operations:
1422 //@{
1423 /**
1424 * @brief Global bitwise operations on bitsets.
1425 * @param __x A bitset.
1426 * @param __y A bitset of the same size as @a __x.
1427 * @return A new bitset.
1428 *
1429 * These should be self-explanatory.
1430 */
1431 template<size_t _Nb>
1432 inline bitset<_Nb>
1433 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1434 {
1435 bitset<_Nb> __result(__x);
1436 __result &= __y;
1437 return __result;
1438 }
1439
1440 template<size_t _Nb>
1441 inline bitset<_Nb>
1442 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1443 {
1444 bitset<_Nb> __result(__x);
1445 __result |= __y;
1446 return __result;
1447 }
1448
1449 template <size_t _Nb>
1450 inline bitset<_Nb>
1451 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
1452 {
1453 bitset<_Nb> __result(__x);
1454 __result ^= __y;
1455 return __result;
1456 }
1457 //@}
1458
1459 //@{
1460 /**
1461 * @brief Global I/O operators for bitsets.
1462 *
1463 * Direct I/O between streams and bitsets is supported. Output is
1464 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1
1465 * characters, and will only extract as many digits as the %bitset will
1466 * hold.
1467 */
1468 template<class _CharT, class _Traits, size_t _Nb>
1469 std::basic_istream<_CharT, _Traits>&
1470 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
1471 {
1472 typedef typename _Traits::char_type char_type;
1473 typedef std::basic_istream<_CharT, _Traits> __istream_type;
1474 typedef typename __istream_type::ios_base __ios_base;
1475
1476 std::basic_string<_CharT, _Traits> __tmp;
1477 __tmp.reserve(_Nb);
1478
1479 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1480 // 303. Bitset input operator underspecified
1481 const char_type __zero = __is.widen('0');
1482 const char_type __one = __is.widen('1');
1483
1484 typename __ios_base::iostate __state = __ios_base::goodbit;
1485 typename __istream_type::sentry __sentry(__is);
1486 if (__sentry)
1487 {
1488 __try
1489 {
1490 for (size_t __i = _Nb; __i > 0; --__i)
1491 {
1492 static typename _Traits::int_type __eof = _Traits::eof();
1493
1494 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
1495 if (_Traits::eq_int_type(__c1, __eof))
1496 {
1497 __state |= __ios_base::eofbit;
1498 break;
1499 }
1500 else
1501 {
1502 const char_type __c2 = _Traits::to_char_type(__c1);
1503 if (_Traits::eq(__c2, __zero))
1504 __tmp.push_back(__zero);
1505 else if (_Traits::eq(__c2, __one))
1506 __tmp.push_back(__one);
1507 else if (_Traits::
1508 eq_int_type(__is.rdbuf()->sputbackc(__c2),
1509 __eof))
1510 {
1511 __state |= __ios_base::failbit;
1512 break;
1513 }
1514 }
1515 }
1516 }
1517 __catch(__cxxabiv1::__forced_unwind&)
1518 {
1519 __is._M_setstate(__ios_base::badbit);
1520 __throw_exception_again;
1521 }
1522 __catch(...)
1523 { __is._M_setstate(__ios_base::badbit); }
1524 }
1525
1526 if (__tmp.empty() && _Nb)
1527 __state |= __ios_base::failbit;
1528 else
1529 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
1530 __zero, __one);
1531 if (__state)
1532 __is.setstate(__state);
1533 return __is;
1534 }
1535
1536 template <class _CharT, class _Traits, size_t _Nb>
1537 std::basic_ostream<_CharT, _Traits>&
1538 operator<<(std::basic_ostream<_CharT, _Traits>& __os,
1539 const bitset<_Nb>& __x)
1540 {
1541 std::basic_string<_CharT, _Traits> __tmp;
1542
1543 // _GLIBCXX_RESOLVE_LIB_DEFECTS
1544 // 396. what are characters zero and one.
1545 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
1546 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
1547 return __os << __tmp;
1548 }
1549 //@}
1550
1551_GLIBCXX_END_NAMESPACE_CONTAINER
1552} // namespace std
1553
1554#undef _GLIBCXX_BITSET_WORDS
1555#undef _GLIBCXX_BITSET_BITS_PER_WORD
1556#undef _GLIBCXX_BITSET_BITS_PER_ULL
1557
1558#if __cplusplus >= 201103L
1559
1560namespace std _GLIBCXX_VISIBILITY(default)
1561{
1562_GLIBCXX_BEGIN_NAMESPACE_VERSION
1563
1564 // DR 1182.
1565 /// std::hash specialization for bitset.
1566 template<size_t _Nb>
1567 struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
1568 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
1569 {
1570 size_t
1571 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
1572 {
1573 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
1574 return std::_Hash_impl::hash(__b._M_getdata(), __clength);
1575 }
1576 };
1577
1578 template<>
1579 struct hash<_GLIBCXX_STD_C::bitset<0>>
1580 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
1581 {
1582 size_t
1583 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
1584 { return 0; }
1585 };
1586
1587_GLIBCXX_END_NAMESPACE_VERSION
1588} // namespace
1589
1590#endif // C++11
1591
1592#ifdef _GLIBCXX_DEBUG
1593# include <debug/bitset>
1594#endif
1595
1596#ifdef _GLIBCXX_PROFILE
1597# include <profile/bitset>
1598#endif
1599
1600#endif /* _GLIBCXX_BITSET */
1601