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