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