1// <bitset> -*- C++ -*- 2 3// Copyright (C) 2001-2018 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('a') is 0001100001</em> on a modern ASCII system. 714 * 715 * @code 716 * #include <bitset> 717 * #include <iostream> 718 * #include <sstream> 719 * 720 * using namespace std; 721 * 722 * int main() 723 * { 724 * long a = 'a'; 725 * bitset<10> b(a); 726 * 727 * cout << "b('a') is " << b << endl; 728 * 729 * ostringstream s; 730 * s << b; 731 * string str = s.str(); 732 * cout << "index 3 in the string is " << str[3] << " but\n" 733 * << "index 3 in the bitset is " << b[3] << endl; 734 * } 735 * @endcode 736 * 737 * Also see: 738 * https://gcc.gnu.org/onlinedocs/libstdc++/manual/ext_containers.html 739 * for a description of extensions. 740 * 741 * Most of the actual code isn't contained in %bitset<> itself, but in the 742 * base class _Base_bitset. The base class works with whole words, not with 743 * individual bits. This allows us to specialize _Base_bitset for the 744 * important special case where the %bitset is only a single word. 745 * 746 * Extra confusion can result due to the fact that the storage for 747 * _Base_bitset @e is a regular array, and is indexed as such. This is 748 * carefully encapsulated. 749 */ 750 template<size_t _Nb> 751 class bitset 752 : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> 753 { 754 private: 755 typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base; 756 typedef unsigned long _WordT; 757 758 template<class _CharT, class _Traits, class _Alloc> 759 void 760 _M_check_initial_position(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 761 size_t __position) const 762 { 763 if (__position > __s.size()) 764 __throw_out_of_range_fmt(__N("bitset::bitset: __position " 765 "(which is %zu) > __s.size() " 766 "(which is %zu)"), 767 __position, __s.size()); 768 } 769 770 void _M_check(size_t __position, const char *__s) const 771 { 772 if (__position >= _Nb) 773 __throw_out_of_range_fmt(__N("%s: __position (which is %zu) " 774 ">= _Nb (which is %zu)"), 775 __s, __position, _Nb); 776 } 777 778 void 779 _M_do_sanitize() _GLIBCXX_NOEXCEPT 780 { 781 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; 782 __sanitize_type::_S_do_sanitize(this->_M_hiword()); 783 } 784 785#if __cplusplus >= 201103L 786 friend struct std::hash<bitset>; 787#endif 788 789 public: 790 /** 791 * This encapsulates the concept of a single bit. An instance of this 792 * class is a proxy for an actual bit; this way the individual bit 793 * operations are done as faster word-size bitwise instructions. 794 * 795 * Most users will never need to use this class directly; conversions 796 * to and from bool are automatic and should be transparent. Overloaded 797 * operators help to preserve the illusion. 798 * 799 * (On a typical system, this <em>bit %reference</em> is 64 800 * times the size of an actual bit. Ha.) 801 */ 802 class reference 803 { 804 friend class bitset; 805 806 _WordT* _M_wp; 807 size_t _M_bpos; 808 809 // left undefined 810 reference(); 811 812 public: 813 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT 814 { 815 _M_wp = &__b._M_getword(__pos); 816 _M_bpos = _Base::_S_whichbit(__pos); 817 } 818 819 ~reference() _GLIBCXX_NOEXCEPT 820 { } 821 822 // For b[i] = __x; 823 reference& 824 operator=(bool __x) _GLIBCXX_NOEXCEPT 825 { 826 if (__x) 827 *_M_wp |= _Base::_S_maskbit(_M_bpos); 828 else 829 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 830 return *this; 831 } 832 833 // For b[i] = b[__j]; 834 reference& 835 operator=(const reference& __j) _GLIBCXX_NOEXCEPT 836 { 837 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 838 *_M_wp |= _Base::_S_maskbit(_M_bpos); 839 else 840 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 841 return *this; 842 } 843 844 // Flips the bit 845 bool 846 operator~() const _GLIBCXX_NOEXCEPT 847 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 848 849 // For __x = b[i]; 850 operator bool() const _GLIBCXX_NOEXCEPT 851 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 852 853 // For b[i].flip(); 854 reference& 855 flip() _GLIBCXX_NOEXCEPT 856 { 857 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 858 return *this; 859 } 860 }; 861 friend class reference; 862 863 // 23.3.5.1 constructors: 864 /// All bits set to zero. 865 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT 866 { } 867 868 /// Initial bits bitwise-copied from a single word (others set to zero). 869#if __cplusplus >= 201103L 870 constexpr bitset(unsigned long long __val) noexcept 871 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } 872#else 873 bitset(unsigned long __val) 874 : _Base(__val) 875 { _M_do_sanitize(); } 876#endif 877 878 /** 879 * Use a subset of a string. 880 * @param __s A string of @a 0 and @a 1 characters. 881 * @param __position Index of the first character in @a __s to use; 882 * defaults to zero. 883 * @throw std::out_of_range If @a pos is bigger the size of @a __s. 884 * @throw std::invalid_argument If a character appears in the string 885 * which is neither @a 0 nor @a 1. 886 */ 887 template<class _CharT, class _Traits, class _Alloc> 888 explicit 889 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 890 size_t __position = 0) 891 : _Base() 892 { 893 _M_check_initial_position(__s, __position); 894 _M_copy_from_string(__s, __position, 895 std::basic_string<_CharT, _Traits, _Alloc>::npos, 896 _CharT('0'), _CharT('1')); 897 } 898 899 /** 900 * Use a subset of a string. 901 * @param __s A string of @a 0 and @a 1 characters. 902 * @param __position Index of the first character in @a __s to use. 903 * @param __n The number of characters to copy. 904 * @throw std::out_of_range If @a __position is bigger the size 905 * of @a __s. 906 * @throw std::invalid_argument If a character appears in the string 907 * which is neither @a 0 nor @a 1. 908 */ 909 template<class _CharT, class _Traits, class _Alloc> 910 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 911 size_t __position, size_t __n) 912 : _Base() 913 { 914 _M_check_initial_position(__s, __position); 915 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 916 } 917 918 // _GLIBCXX_RESOLVE_LIB_DEFECTS 919 // 396. what are characters zero and one. 920 template<class _CharT, class _Traits, class _Alloc> 921 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 922 size_t __position, size_t __n, 923 _CharT __zero, _CharT __one = _CharT('1')) 924 : _Base() 925 { 926 _M_check_initial_position(__s, __position); 927 _M_copy_from_string(__s, __position, __n, __zero, __one); 928 } 929 930#if __cplusplus >= 201103L 931 /** 932 * Construct from a character %array. 933 * @param __str An %array of characters @a zero and @a one. 934 * @param __n The number of characters to use. 935 * @param __zero The character corresponding to the value 0. 936 * @param __one The character corresponding to the value 1. 937 * @throw std::invalid_argument If a character appears in the string 938 * which is neither @a __zero nor @a __one. 939 */ 940 template<typename _CharT> 941 explicit 942 bitset(const _CharT* __str, 943 typename std::basic_string<_CharT>::size_type __n 944 = std::basic_string<_CharT>::npos, 945 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) 946 : _Base() 947 { 948 if (!__str) 949 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)")); 950 951 if (__n == std::basic_string<_CharT>::npos) 952 __n = std::char_traits<_CharT>::length(__str); 953 _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0, 954 __n, __zero, 955 __one); 956 } 957#endif 958 959 // 23.3.5.2 bitset operations: 960 //@{ 961 /** 962 * Operations on bitsets. 963 * @param __rhs A same-sized bitset. 964 * 965 * These should be self-explanatory. 966 */ 967 bitset<_Nb>& 968 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 969 { 970 this->_M_do_and(__rhs); 971 return *this; 972 } 973 974 bitset<_Nb>& 975 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 976 { 977 this->_M_do_or(__rhs); 978 return *this; 979 } 980 981 bitset<_Nb>& 982 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 983 { 984 this->_M_do_xor(__rhs); 985 return *this; 986 } 987 //@} 988 989 //@{ 990 /** 991 * Operations on bitsets. 992 * @param __position The number of places to shift. 993 * 994 * These should be self-explanatory. 995 */ 996 bitset<_Nb>& 997 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT 998 { 999 if (__builtin_expect(__position < _Nb, 1)) 1000 { 1001 this->_M_do_left_shift(__position); 1002 this->_M_do_sanitize(); 1003 } 1004 else 1005 this->_M_do_reset(); 1006 return *this; 1007 } 1008 1009 bitset<_Nb>& 1010 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT 1011 { 1012 if (__builtin_expect(__position < _Nb, 1)) 1013 { 1014 this->_M_do_right_shift(__position); 1015 this->_M_do_sanitize(); 1016 } 1017 else 1018 this->_M_do_reset(); 1019 return *this; 1020 } 1021 //@} 1022 1023 //@{ 1024 /** 1025 * These versions of single-bit set, reset, flip, and test are 1026 * extensions from the SGI version. They do no range checking. 1027 * @ingroup SGIextensions 1028 */ 1029 bitset<_Nb>& 1030 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT 1031 { 1032 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1033 return *this; 1034 } 1035 1036 bitset<_Nb>& 1037 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT 1038 { 1039 if (__val) 1040 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1041 else 1042 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1043 return *this; 1044 } 1045 1046 bitset<_Nb>& 1047 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT 1048 { 1049 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1050 return *this; 1051 } 1052 1053 bitset<_Nb>& 1054 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT 1055 { 1056 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 1057 return *this; 1058 } 1059 1060 _GLIBCXX_CONSTEXPR bool 1061 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT 1062 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 1063 != static_cast<_WordT>(0)); } 1064 //@} 1065 1066 // Set, reset, and flip. 1067 /** 1068 * @brief Sets every bit to true. 1069 */ 1070 bitset<_Nb>& 1071 set() _GLIBCXX_NOEXCEPT 1072 { 1073 this->_M_do_set(); 1074 this->_M_do_sanitize(); 1075 return *this; 1076 } 1077 1078 /** 1079 * @brief Sets a given bit to a particular value. 1080 * @param __position The index of the bit. 1081 * @param __val Either true or false, defaults to true. 1082 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1083 */ 1084 bitset<_Nb>& 1085 set(size_t __position, bool __val = true) 1086 { 1087 this->_M_check(__position, __N("bitset::set")); 1088 return _Unchecked_set(__position, __val); 1089 } 1090 1091 /** 1092 * @brief Sets every bit to false. 1093 */ 1094 bitset<_Nb>& 1095 reset() _GLIBCXX_NOEXCEPT 1096 { 1097 this->_M_do_reset(); 1098 return *this; 1099 } 1100 1101 /** 1102 * @brief Sets a given bit to false. 1103 * @param __position The index of the bit. 1104 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1105 * 1106 * Same as writing @c set(pos,false). 1107 */ 1108 bitset<_Nb>& 1109 reset(size_t __position) 1110 { 1111 this->_M_check(__position, __N("bitset::reset")); 1112 return _Unchecked_reset(__position); 1113 } 1114 1115 /** 1116 * @brief Toggles every bit to its opposite value. 1117 */ 1118 bitset<_Nb>& 1119 flip() _GLIBCXX_NOEXCEPT 1120 { 1121 this->_M_do_flip(); 1122 this->_M_do_sanitize(); 1123 return *this; 1124 } 1125 1126 /** 1127 * @brief Toggles a given bit to its opposite value. 1128 * @param __position The index of the bit. 1129 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1130 */ 1131 bitset<_Nb>& 1132 flip(size_t __position) 1133 { 1134 this->_M_check(__position, __N("bitset::flip")); 1135 return _Unchecked_flip(__position); 1136 } 1137 1138 /// See the no-argument flip(). 1139 bitset<_Nb> 1140 operator~() const _GLIBCXX_NOEXCEPT 1141 { return bitset<_Nb>(*this).flip(); } 1142 1143 //@{ 1144 /** 1145 * @brief Array-indexing support. 1146 * @param __position Index into the %bitset. 1147 * @return A bool for a <em>const %bitset</em>. For non-const 1148 * bitsets, an instance of the reference proxy class. 1149 * @note These operators do no range checking and throw no exceptions, 1150 * as required by DR 11 to the standard. 1151 * 1152 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 1153 * resolves DR 11 (items 1 and 2), but does not do the range-checking 1154 * required by that DR's resolution. -pme 1155 * The DR has since been changed: range-checking is a precondition 1156 * (users' responsibility), and these functions must not throw. -pme 1157 */ 1158 reference 1159 operator[](size_t __position) 1160 { return reference(*this, __position); } 1161 1162 _GLIBCXX_CONSTEXPR bool 1163 operator[](size_t __position) const 1164 { return _Unchecked_test(__position); } 1165 //@} 1166 1167 /** 1168 * @brief Returns a numerical interpretation of the %bitset. 1169 * @return The integral equivalent of the bits. 1170 * @throw std::overflow_error If there are too many bits to be 1171 * represented in an @c unsigned @c long. 1172 */ 1173 unsigned long 1174 to_ulong() const 1175 { return this->_M_do_to_ulong(); } 1176 1177#if __cplusplus >= 201103L 1178 unsigned long long 1179 to_ullong() const 1180 { return this->_M_do_to_ullong(); } 1181#endif 1182 1183 /** 1184 * @brief Returns a character interpretation of the %bitset. 1185 * @return The string equivalent of the bits. 1186 * 1187 * Note the ordering of the bits: decreasing character positions 1188 * correspond to increasing bit positions (see the main class notes for 1189 * an example). 1190 */ 1191 template<class _CharT, class _Traits, class _Alloc> 1192 std::basic_string<_CharT, _Traits, _Alloc> 1193 to_string() const 1194 { 1195 std::basic_string<_CharT, _Traits, _Alloc> __result; 1196 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 1197 return __result; 1198 } 1199 1200 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1201 // 396. what are characters zero and one. 1202 template<class _CharT, class _Traits, class _Alloc> 1203 std::basic_string<_CharT, _Traits, _Alloc> 1204 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1205 { 1206 std::basic_string<_CharT, _Traits, _Alloc> __result; 1207 _M_copy_to_string(__result, __zero, __one); 1208 return __result; 1209 } 1210 1211 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1212 // 434. bitset::to_string() hard to use. 1213 template<class _CharT, class _Traits> 1214 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1215 to_string() const 1216 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 1217 1218 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1219 // 853. to_string needs updating with zero and one. 1220 template<class _CharT, class _Traits> 1221 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1222 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1223 { return to_string<_CharT, _Traits, 1224 std::allocator<_CharT> >(__zero, __one); } 1225 1226 template<class _CharT> 1227 std::basic_string<_CharT, std::char_traits<_CharT>, 1228 std::allocator<_CharT> > 1229 to_string() const 1230 { 1231 return to_string<_CharT, std::char_traits<_CharT>, 1232 std::allocator<_CharT> >(); 1233 } 1234 1235 template<class _CharT> 1236 std::basic_string<_CharT, std::char_traits<_CharT>, 1237 std::allocator<_CharT> > 1238 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1239 { 1240 return to_string<_CharT, std::char_traits<_CharT>, 1241 std::allocator<_CharT> >(__zero, __one); 1242 } 1243 1244 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1245 to_string() const 1246 { 1247 return to_string<char, std::char_traits<char>, 1248 std::allocator<char> >(); 1249 } 1250 1251 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1252 to_string(char __zero, char __one = '1') const 1253 { 1254 return to_string<char, std::char_traits<char>, 1255 std::allocator<char> >(__zero, __one); 1256 } 1257 1258 // Helper functions for string operations. 1259 template<class _CharT, class _Traits> 1260 void 1261 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1262 _CharT, _CharT); 1263 1264 template<class _CharT, class _Traits, class _Alloc> 1265 void 1266 _M_copy_from_string(const std::basic_string<_CharT, 1267 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 1268 _CharT __zero, _CharT __one) 1269 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 1270 __zero, __one); } 1271 1272 template<class _CharT, class _Traits, class _Alloc> 1273 void 1274 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 1275 _CharT, _CharT) const; 1276 1277 // NB: Backward compat. 1278 template<class _CharT, class _Traits, class _Alloc> 1279 void 1280 _M_copy_from_string(const std::basic_string<_CharT, 1281 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 1282 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 1283 1284 template<class _CharT, class _Traits, class _Alloc> 1285 void 1286 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 1287 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 1288 1289 /// Returns the number of bits which are set. 1290 size_t 1291 count() const _GLIBCXX_NOEXCEPT 1292 { return this->_M_do_count(); } 1293 1294 /// Returns the total number of bits. 1295 _GLIBCXX_CONSTEXPR size_t 1296 size() const _GLIBCXX_NOEXCEPT 1297 { return _Nb; } 1298 1299 //@{ 1300 /// These comparisons for equality/inequality are, well, @e bitwise. 1301 bool 1302 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1303 { return this->_M_is_equal(__rhs); } 1304 1305 bool 1306 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1307 { return !this->_M_is_equal(__rhs); } 1308 //@} 1309 1310 /** 1311 * @brief Tests the value of a bit. 1312 * @param __position The index of a bit. 1313 * @return The value at @a pos. 1314 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1315 */ 1316 bool 1317 test(size_t __position) const 1318 { 1319 this->_M_check(__position, __N("bitset::test")); 1320 return _Unchecked_test(__position); 1321 } 1322 1323 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1324 // DR 693. std::bitset::all() missing. 1325 /** 1326 * @brief Tests whether all the bits are on. 1327 * @return True if all the bits are set. 1328 */ 1329 bool 1330 all() const _GLIBCXX_NOEXCEPT 1331 { return this->template _M_are_all<_Nb>(); } 1332 1333 /** 1334 * @brief Tests whether any of the bits are on. 1335 * @return True if at least one bit is set. 1336 */ 1337 bool 1338 any() const _GLIBCXX_NOEXCEPT 1339 { return this->_M_is_any(); } 1340 1341 /** 1342 * @brief Tests whether any of the bits are on. 1343 * @return True if none of the bits are set. 1344 */ 1345 bool 1346 none() const _GLIBCXX_NOEXCEPT 1347 { return !this->_M_is_any(); } 1348 1349 //@{ 1350 /// Self-explanatory. 1351 bitset<_Nb> 1352 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT 1353 { return bitset<_Nb>(*this) <<= __position; } 1354 1355 bitset<_Nb> 1356 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT 1357 { return bitset<_Nb>(*this) >>= __position; } 1358 //@} 1359 1360 /** 1361 * @brief Finds the index of the first "on" bit. 1362 * @return The index of the first bit set, or size() if not found. 1363 * @ingroup SGIextensions 1364 * @sa _Find_next 1365 */ 1366 size_t 1367 _Find_first() const _GLIBCXX_NOEXCEPT 1368 { return this->_M_do_find_first(_Nb); } 1369 1370 /** 1371 * @brief Finds the index of the next "on" bit after prev. 1372 * @return The index of the next bit set, or size() if not found. 1373 * @param __prev Where to start searching. 1374 * @ingroup SGIextensions 1375 * @sa _Find_first 1376 */ 1377 size_t 1378 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT 1379 { return this->_M_do_find_next(__prev, _Nb); } 1380 }; 1381 1382 // Definitions of non-inline member functions. 1383 template<size_t _Nb> 1384 template<class _CharT, class _Traits> 1385 void 1386 bitset<_Nb>:: 1387 _M_copy_from_ptr(const _CharT* __s, size_t __len, 1388 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 1389 { 1390 reset(); 1391 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos))); 1392 for (size_t __i = __nbits; __i > 0; --__i) 1393 { 1394 const _CharT __c = __s[__pos + __nbits - __i]; 1395 if (_Traits::eq(__c, __zero)) 1396 ; 1397 else if (_Traits::eq(__c, __one)) 1398 _Unchecked_set(__i - 1); 1399 else 1400 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 1401 } 1402 } 1403 1404 template<size_t _Nb> 1405 template<class _CharT, class _Traits, class _Alloc> 1406 void 1407 bitset<_Nb>:: 1408 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 1409 _CharT __zero, _CharT __one) const 1410 { 1411 __s.assign(_Nb, __zero); 1412 for (size_t __i = _Nb; __i > 0; --__i) 1413 if (_Unchecked_test(__i - 1)) 1414 _Traits::assign(__s[_Nb - __i], __one); 1415 } 1416 1417 // 23.3.5.3 bitset operations: 1418 //@{ 1419 /** 1420 * @brief Global bitwise operations on bitsets. 1421 * @param __x A bitset. 1422 * @param __y A bitset of the same size as @a __x. 1423 * @return A new bitset. 1424 * 1425 * These should be self-explanatory. 1426 */ 1427 template<size_t _Nb> 1428 inline bitset<_Nb> 1429 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1430 { 1431 bitset<_Nb> __result(__x); 1432 __result &= __y; 1433 return __result; 1434 } 1435 1436 template<size_t _Nb> 1437 inline bitset<_Nb> 1438 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1439 { 1440 bitset<_Nb> __result(__x); 1441 __result |= __y; 1442 return __result; 1443 } 1444 1445 template <size_t _Nb> 1446 inline bitset<_Nb> 1447 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1448 { 1449 bitset<_Nb> __result(__x); 1450 __result ^= __y; 1451 return __result; 1452 } 1453 //@} 1454 1455 //@{ 1456 /** 1457 * @brief Global I/O operators for bitsets. 1458 * 1459 * Direct I/O between streams and bitsets is supported. Output is 1460 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 1461 * characters, and will only extract as many digits as the %bitset will 1462 * hold. 1463 */ 1464 template<class _CharT, class _Traits, size_t _Nb> 1465 std::basic_istream<_CharT, _Traits>& 1466 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1467 { 1468 typedef typename _Traits::char_type char_type; 1469 typedef std::basic_istream<_CharT, _Traits> __istream_type; 1470 typedef typename __istream_type::ios_base __ios_base; 1471 1472 std::basic_string<_CharT, _Traits> __tmp; 1473 __tmp.reserve(_Nb); 1474 1475 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1476 // 303. Bitset input operator underspecified 1477 const char_type __zero = __is.widen('0'); 1478 const char_type __one = __is.widen('1'); 1479 1480 typename __ios_base::iostate __state = __ios_base::goodbit; 1481 typename __istream_type::sentry __sentry(__is); 1482 if (__sentry) 1483 { 1484 __try 1485 { 1486 for (size_t __i = _Nb; __i > 0; --__i) 1487 { 1488 static typename _Traits::int_type __eof = _Traits::eof(); 1489 1490 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 1491 if (_Traits::eq_int_type(__c1, __eof)) 1492 { 1493 __state |= __ios_base::eofbit; 1494 break; 1495 } 1496 else 1497 { 1498 const char_type __c2 = _Traits::to_char_type(__c1); 1499 if (_Traits::eq(__c2, __zero)) 1500 __tmp.push_back(__zero); 1501 else if (_Traits::eq(__c2, __one)) 1502 __tmp.push_back(__one); 1503 else if (_Traits:: 1504 eq_int_type(__is.rdbuf()->sputbackc(__c2), 1505 __eof)) 1506 { 1507 __state |= __ios_base::failbit; 1508 break; 1509 } 1510 } 1511 } 1512 } 1513 __catch(__cxxabiv1::__forced_unwind&) 1514 { 1515 __is._M_setstate(__ios_base::badbit); 1516 __throw_exception_again; 1517 } 1518 __catch(...) 1519 { __is._M_setstate(__ios_base::badbit); } 1520 } 1521 1522 if (__tmp.empty() && _Nb) 1523 __state |= __ios_base::failbit; 1524 else 1525 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 1526 __zero, __one); 1527 if (__state) 1528 __is.setstate(__state); 1529 return __is; 1530 } 1531 1532 template <class _CharT, class _Traits, size_t _Nb> 1533 std::basic_ostream<_CharT, _Traits>& 1534 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1535 const bitset<_Nb>& __x) 1536 { 1537 std::basic_string<_CharT, _Traits> __tmp; 1538 1539 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1540 // 396. what are characters zero and one. 1541 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 1542 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1543 return __os << __tmp; 1544 } 1545 //@} 1546 1547_GLIBCXX_END_NAMESPACE_CONTAINER 1548} // namespace std 1549 1550#undef _GLIBCXX_BITSET_WORDS 1551#undef _GLIBCXX_BITSET_BITS_PER_WORD 1552#undef _GLIBCXX_BITSET_BITS_PER_ULL 1553 1554#if __cplusplus >= 201103L 1555 1556namespace std _GLIBCXX_VISIBILITY(default) 1557{ 1558_GLIBCXX_BEGIN_NAMESPACE_VERSION 1559 1560 // DR 1182. 1561 /// std::hash specialization for bitset. 1562 template<size_t _Nb> 1563 struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 1564 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 1565 { 1566 size_t 1567 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 1568 { 1569 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 1570 return std::_Hash_impl::hash(__b._M_getdata(), __clength); 1571 } 1572 }; 1573 1574 template<> 1575 struct hash<_GLIBCXX_STD_C::bitset<0>> 1576 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> 1577 { 1578 size_t 1579 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept 1580 { return 0; } 1581 }; 1582 1583_GLIBCXX_END_NAMESPACE_VERSION 1584} // namespace 1585 1586#endif // C++11 1587 1588#ifdef _GLIBCXX_DEBUG 1589# include <debug/bitset> 1590#endif 1591 1592#ifdef _GLIBCXX_PROFILE 1593# include <profile/bitset> 1594#endif 1595 1596#endif /* _GLIBCXX_BITSET */ 1597