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