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