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