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