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