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