1// <bitset> -*- C++ -*- 2 3// Copyright (C) 2001-2013 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 void 756 _M_do_sanitize() _GLIBCXX_NOEXCEPT 757 { 758 typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type; 759 __sanitize_type::_S_do_sanitize(this->_M_hiword()); 760 } 761 762#if __cplusplus >= 201103L 763 template<typename> friend struct hash; 764#endif 765 766 public: 767 /** 768 * This encapsulates the concept of a single bit. An instance of this 769 * class is a proxy for an actual bit; this way the individual bit 770 * operations are done as faster word-size bitwise instructions. 771 * 772 * Most users will never need to use this class directly; conversions 773 * to and from bool are automatic and should be transparent. Overloaded 774 * operators help to preserve the illusion. 775 * 776 * (On a typical system, this <em>bit %reference</em> is 64 777 * times the size of an actual bit. Ha.) 778 */ 779 class reference 780 { 781 friend class bitset; 782 783 _WordT* _M_wp; 784 size_t _M_bpos; 785 786 // left undefined 787 reference(); 788 789 public: 790 reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT 791 { 792 _M_wp = &__b._M_getword(__pos); 793 _M_bpos = _Base::_S_whichbit(__pos); 794 } 795 796 ~reference() _GLIBCXX_NOEXCEPT 797 { } 798 799 // For b[i] = __x; 800 reference& 801 operator=(bool __x) _GLIBCXX_NOEXCEPT 802 { 803 if (__x) 804 *_M_wp |= _Base::_S_maskbit(_M_bpos); 805 else 806 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 807 return *this; 808 } 809 810 // For b[i] = b[__j]; 811 reference& 812 operator=(const reference& __j) _GLIBCXX_NOEXCEPT 813 { 814 if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos))) 815 *_M_wp |= _Base::_S_maskbit(_M_bpos); 816 else 817 *_M_wp &= ~_Base::_S_maskbit(_M_bpos); 818 return *this; 819 } 820 821 // Flips the bit 822 bool 823 operator~() const _GLIBCXX_NOEXCEPT 824 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; } 825 826 // For __x = b[i]; 827 operator bool() const _GLIBCXX_NOEXCEPT 828 { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; } 829 830 // For b[i].flip(); 831 reference& 832 flip() _GLIBCXX_NOEXCEPT 833 { 834 *_M_wp ^= _Base::_S_maskbit(_M_bpos); 835 return *this; 836 } 837 }; 838 friend class reference; 839 840 // 23.3.5.1 constructors: 841 /// All bits set to zero. 842 _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT 843 { } 844 845 /// Initial bits bitwise-copied from a single word (others set to zero). 846#if __cplusplus >= 201103L 847 constexpr bitset(unsigned long long __val) noexcept 848 : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { } 849#else 850 bitset(unsigned long __val) 851 : _Base(__val) 852 { _M_do_sanitize(); } 853#endif 854 855 /** 856 * Use a subset of a string. 857 * @param __s A string of @a 0 and @a 1 characters. 858 * @param __position Index of the first character in @a __s to use; 859 * defaults to zero. 860 * @throw std::out_of_range If @a pos is bigger the size of @a __s. 861 * @throw std::invalid_argument If a character appears in the string 862 * which is neither @a 0 nor @a 1. 863 */ 864 template<class _CharT, class _Traits, class _Alloc> 865 explicit 866 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 867 size_t __position = 0) 868 : _Base() 869 { 870 if (__position > __s.size()) 871 __throw_out_of_range(__N("bitset::bitset initial position " 872 "not valid")); 873 _M_copy_from_string(__s, __position, 874 std::basic_string<_CharT, _Traits, _Alloc>::npos, 875 _CharT('0'), _CharT('1')); 876 } 877 878 /** 879 * Use a subset of a string. 880 * @param __s A string of @a 0 and @a 1 characters. 881 * @param __position Index of the first character in @a __s to use. 882 * @param __n The number of characters to copy. 883 * @throw std::out_of_range If @a __position is bigger the size 884 * of @a __s. 885 * @throw std::invalid_argument If a character appears in the string 886 * which is neither @a 0 nor @a 1. 887 */ 888 template<class _CharT, class _Traits, class _Alloc> 889 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 890 size_t __position, size_t __n) 891 : _Base() 892 { 893 if (__position > __s.size()) 894 __throw_out_of_range(__N("bitset::bitset initial position " 895 "not valid")); 896 _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1')); 897 } 898 899 // _GLIBCXX_RESOLVE_LIB_DEFECTS 900 // 396. what are characters zero and one. 901 template<class _CharT, class _Traits, class _Alloc> 902 bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s, 903 size_t __position, size_t __n, 904 _CharT __zero, _CharT __one = _CharT('1')) 905 : _Base() 906 { 907 if (__position > __s.size()) 908 __throw_out_of_range(__N("bitset::bitset initial position " 909 "not valid")); 910 _M_copy_from_string(__s, __position, __n, __zero, __one); 911 } 912 913#if __cplusplus >= 201103L 914 /** 915 * Construct from a character %array. 916 * @param __str An %array of characters @a zero and @a one. 917 * @param __n The number of characters to use. 918 * @param __zero The character corresponding to the value 0. 919 * @param __one The character corresponding to the value 1. 920 * @throw std::invalid_argument If a character appears in the string 921 * which is neither @a __zero nor @a __one. 922 */ 923 template<typename _CharT> 924 explicit 925 bitset(const _CharT* __str, 926 typename std::basic_string<_CharT>::size_type __n 927 = std::basic_string<_CharT>::npos, 928 _CharT __zero = _CharT('0'), _CharT __one = _CharT('1')) 929 : _Base() 930 { 931 if (!__str) 932 __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)")); 933 934 if (__n == std::basic_string<_CharT>::npos) 935 __n = std::char_traits<_CharT>::length(__str); 936 _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0, 937 __n, __zero, 938 __one); 939 } 940#endif 941 942 // 23.3.5.2 bitset operations: 943 //@{ 944 /** 945 * Operations on bitsets. 946 * @param __rhs A same-sized bitset. 947 * 948 * These should be self-explanatory. 949 */ 950 bitset<_Nb>& 951 operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 952 { 953 this->_M_do_and(__rhs); 954 return *this; 955 } 956 957 bitset<_Nb>& 958 operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 959 { 960 this->_M_do_or(__rhs); 961 return *this; 962 } 963 964 bitset<_Nb>& 965 operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT 966 { 967 this->_M_do_xor(__rhs); 968 return *this; 969 } 970 //@} 971 972 //@{ 973 /** 974 * Operations on bitsets. 975 * @param __position The number of places to shift. 976 * 977 * These should be self-explanatory. 978 */ 979 bitset<_Nb>& 980 operator<<=(size_t __position) _GLIBCXX_NOEXCEPT 981 { 982 if (__builtin_expect(__position < _Nb, 1)) 983 { 984 this->_M_do_left_shift(__position); 985 this->_M_do_sanitize(); 986 } 987 else 988 this->_M_do_reset(); 989 return *this; 990 } 991 992 bitset<_Nb>& 993 operator>>=(size_t __position) _GLIBCXX_NOEXCEPT 994 { 995 if (__builtin_expect(__position < _Nb, 1)) 996 { 997 this->_M_do_right_shift(__position); 998 this->_M_do_sanitize(); 999 } 1000 else 1001 this->_M_do_reset(); 1002 return *this; 1003 } 1004 //@} 1005 1006 //@{ 1007 /** 1008 * These versions of single-bit set, reset, flip, and test are 1009 * extensions from the SGI version. They do no range checking. 1010 * @ingroup SGIextensions 1011 */ 1012 bitset<_Nb>& 1013 _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT 1014 { 1015 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1016 return *this; 1017 } 1018 1019 bitset<_Nb>& 1020 _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT 1021 { 1022 if (__val) 1023 this->_M_getword(__pos) |= _Base::_S_maskbit(__pos); 1024 else 1025 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1026 return *this; 1027 } 1028 1029 bitset<_Nb>& 1030 _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT 1031 { 1032 this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos); 1033 return *this; 1034 } 1035 1036 bitset<_Nb>& 1037 _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT 1038 { 1039 this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos); 1040 return *this; 1041 } 1042 1043 _GLIBCXX_CONSTEXPR bool 1044 _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT 1045 { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos)) 1046 != static_cast<_WordT>(0)); } 1047 //@} 1048 1049 // Set, reset, and flip. 1050 /** 1051 * @brief Sets every bit to true. 1052 */ 1053 bitset<_Nb>& 1054 set() _GLIBCXX_NOEXCEPT 1055 { 1056 this->_M_do_set(); 1057 this->_M_do_sanitize(); 1058 return *this; 1059 } 1060 1061 /** 1062 * @brief Sets a given bit to a particular value. 1063 * @param __position The index of the bit. 1064 * @param __val Either true or false, defaults to true. 1065 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1066 */ 1067 bitset<_Nb>& 1068 set(size_t __position, bool __val = true) 1069 { 1070 if (__position >= _Nb) 1071 __throw_out_of_range(__N("bitset::set")); 1072 return _Unchecked_set(__position, __val); 1073 } 1074 1075 /** 1076 * @brief Sets every bit to false. 1077 */ 1078 bitset<_Nb>& 1079 reset() _GLIBCXX_NOEXCEPT 1080 { 1081 this->_M_do_reset(); 1082 return *this; 1083 } 1084 1085 /** 1086 * @brief Sets a given bit to false. 1087 * @param __position The index of the bit. 1088 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1089 * 1090 * Same as writing @c set(pos,false). 1091 */ 1092 bitset<_Nb>& 1093 reset(size_t __position) 1094 { 1095 if (__position >= _Nb) 1096 __throw_out_of_range(__N("bitset::reset")); 1097 return _Unchecked_reset(__position); 1098 } 1099 1100 /** 1101 * @brief Toggles every bit to its opposite value. 1102 */ 1103 bitset<_Nb>& 1104 flip() _GLIBCXX_NOEXCEPT 1105 { 1106 this->_M_do_flip(); 1107 this->_M_do_sanitize(); 1108 return *this; 1109 } 1110 1111 /** 1112 * @brief Toggles a given bit to its opposite value. 1113 * @param __position The index of the bit. 1114 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1115 */ 1116 bitset<_Nb>& 1117 flip(size_t __position) 1118 { 1119 if (__position >= _Nb) 1120 __throw_out_of_range(__N("bitset::flip")); 1121 return _Unchecked_flip(__position); 1122 } 1123 1124 /// See the no-argument flip(). 1125 bitset<_Nb> 1126 operator~() const _GLIBCXX_NOEXCEPT 1127 { return bitset<_Nb>(*this).flip(); } 1128 1129 //@{ 1130 /** 1131 * @brief Array-indexing support. 1132 * @param __position Index into the %bitset. 1133 * @return A bool for a <em>const %bitset</em>. For non-const 1134 * bitsets, an instance of the reference proxy class. 1135 * @note These operators do no range checking and throw no exceptions, 1136 * as required by DR 11 to the standard. 1137 * 1138 * _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already 1139 * resolves DR 11 (items 1 and 2), but does not do the range-checking 1140 * required by that DR's resolution. -pme 1141 * The DR has since been changed: range-checking is a precondition 1142 * (users' responsibility), and these functions must not throw. -pme 1143 */ 1144 reference 1145 operator[](size_t __position) 1146 { return reference(*this, __position); } 1147 1148 _GLIBCXX_CONSTEXPR bool 1149 operator[](size_t __position) const 1150 { return _Unchecked_test(__position); } 1151 //@} 1152 1153 /** 1154 * @brief Returns a numerical interpretation of the %bitset. 1155 * @return The integral equivalent of the bits. 1156 * @throw std::overflow_error If there are too many bits to be 1157 * represented in an @c unsigned @c long. 1158 */ 1159 unsigned long 1160 to_ulong() const 1161 { return this->_M_do_to_ulong(); } 1162 1163#if __cplusplus >= 201103L 1164 unsigned long long 1165 to_ullong() const 1166 { return this->_M_do_to_ullong(); } 1167#endif 1168 1169 /** 1170 * @brief Returns a character interpretation of the %bitset. 1171 * @return The string equivalent of the bits. 1172 * 1173 * Note the ordering of the bits: decreasing character positions 1174 * correspond to increasing bit positions (see the main class notes for 1175 * an example). 1176 */ 1177 template<class _CharT, class _Traits, class _Alloc> 1178 std::basic_string<_CharT, _Traits, _Alloc> 1179 to_string() const 1180 { 1181 std::basic_string<_CharT, _Traits, _Alloc> __result; 1182 _M_copy_to_string(__result, _CharT('0'), _CharT('1')); 1183 return __result; 1184 } 1185 1186 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1187 // 396. what are characters zero and one. 1188 template<class _CharT, class _Traits, class _Alloc> 1189 std::basic_string<_CharT, _Traits, _Alloc> 1190 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1191 { 1192 std::basic_string<_CharT, _Traits, _Alloc> __result; 1193 _M_copy_to_string(__result, __zero, __one); 1194 return __result; 1195 } 1196 1197 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1198 // 434. bitset::to_string() hard to use. 1199 template<class _CharT, class _Traits> 1200 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1201 to_string() const 1202 { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); } 1203 1204 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1205 // 853. to_string needs updating with zero and one. 1206 template<class _CharT, class _Traits> 1207 std::basic_string<_CharT, _Traits, std::allocator<_CharT> > 1208 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1209 { return to_string<_CharT, _Traits, 1210 std::allocator<_CharT> >(__zero, __one); } 1211 1212 template<class _CharT> 1213 std::basic_string<_CharT, std::char_traits<_CharT>, 1214 std::allocator<_CharT> > 1215 to_string() const 1216 { 1217 return to_string<_CharT, std::char_traits<_CharT>, 1218 std::allocator<_CharT> >(); 1219 } 1220 1221 template<class _CharT> 1222 std::basic_string<_CharT, std::char_traits<_CharT>, 1223 std::allocator<_CharT> > 1224 to_string(_CharT __zero, _CharT __one = _CharT('1')) const 1225 { 1226 return to_string<_CharT, std::char_traits<_CharT>, 1227 std::allocator<_CharT> >(__zero, __one); 1228 } 1229 1230 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1231 to_string() const 1232 { 1233 return to_string<char, std::char_traits<char>, 1234 std::allocator<char> >(); 1235 } 1236 1237 std::basic_string<char, std::char_traits<char>, std::allocator<char> > 1238 to_string(char __zero, char __one = '1') const 1239 { 1240 return to_string<char, std::char_traits<char>, 1241 std::allocator<char> >(__zero, __one); 1242 } 1243 1244 // Helper functions for string operations. 1245 template<class _CharT, class _Traits> 1246 void 1247 _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t, 1248 _CharT, _CharT); 1249 1250 template<class _CharT, class _Traits, class _Alloc> 1251 void 1252 _M_copy_from_string(const std::basic_string<_CharT, 1253 _Traits, _Alloc>& __s, size_t __pos, size_t __n, 1254 _CharT __zero, _CharT __one) 1255 { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n, 1256 __zero, __one); } 1257 1258 template<class _CharT, class _Traits, class _Alloc> 1259 void 1260 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&, 1261 _CharT, _CharT) const; 1262 1263 // NB: Backward compat. 1264 template<class _CharT, class _Traits, class _Alloc> 1265 void 1266 _M_copy_from_string(const std::basic_string<_CharT, 1267 _Traits, _Alloc>& __s, size_t __pos, size_t __n) 1268 { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); } 1269 1270 template<class _CharT, class _Traits, class _Alloc> 1271 void 1272 _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const 1273 { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); } 1274 1275 /// Returns the number of bits which are set. 1276 size_t 1277 count() const _GLIBCXX_NOEXCEPT 1278 { return this->_M_do_count(); } 1279 1280 /// Returns the total number of bits. 1281 _GLIBCXX_CONSTEXPR size_t 1282 size() const _GLIBCXX_NOEXCEPT 1283 { return _Nb; } 1284 1285 //@{ 1286 /// These comparisons for equality/inequality are, well, @e bitwise. 1287 bool 1288 operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1289 { return this->_M_is_equal(__rhs); } 1290 1291 bool 1292 operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT 1293 { return !this->_M_is_equal(__rhs); } 1294 //@} 1295 1296 /** 1297 * @brief Tests the value of a bit. 1298 * @param __position The index of a bit. 1299 * @return The value at @a pos. 1300 * @throw std::out_of_range If @a pos is bigger the size of the %set. 1301 */ 1302 bool 1303 test(size_t __position) const 1304 { 1305 if (__position >= _Nb) 1306 __throw_out_of_range(__N("bitset::test")); 1307 return _Unchecked_test(__position); 1308 } 1309 1310 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1311 // DR 693. std::bitset::all() missing. 1312 /** 1313 * @brief Tests whether all the bits are on. 1314 * @return True if all the bits are set. 1315 */ 1316 bool 1317 all() const _GLIBCXX_NOEXCEPT 1318 { return this->template _M_are_all<_Nb>(); } 1319 1320 /** 1321 * @brief Tests whether any of the bits are on. 1322 * @return True if at least one bit is set. 1323 */ 1324 bool 1325 any() const _GLIBCXX_NOEXCEPT 1326 { return this->_M_is_any(); } 1327 1328 /** 1329 * @brief Tests whether any of the bits are on. 1330 * @return True if none of the bits are set. 1331 */ 1332 bool 1333 none() const _GLIBCXX_NOEXCEPT 1334 { return !this->_M_is_any(); } 1335 1336 //@{ 1337 /// Self-explanatory. 1338 bitset<_Nb> 1339 operator<<(size_t __position) const _GLIBCXX_NOEXCEPT 1340 { return bitset<_Nb>(*this) <<= __position; } 1341 1342 bitset<_Nb> 1343 operator>>(size_t __position) const _GLIBCXX_NOEXCEPT 1344 { return bitset<_Nb>(*this) >>= __position; } 1345 //@} 1346 1347 /** 1348 * @brief Finds the index of the first "on" bit. 1349 * @return The index of the first bit set, or size() if not found. 1350 * @ingroup SGIextensions 1351 * @sa _Find_next 1352 */ 1353 size_t 1354 _Find_first() const _GLIBCXX_NOEXCEPT 1355 { return this->_M_do_find_first(_Nb); } 1356 1357 /** 1358 * @brief Finds the index of the next "on" bit after prev. 1359 * @return The index of the next bit set, or size() if not found. 1360 * @param __prev Where to start searching. 1361 * @ingroup SGIextensions 1362 * @sa _Find_first 1363 */ 1364 size_t 1365 _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT 1366 { return this->_M_do_find_next(__prev, _Nb); } 1367 }; 1368 1369 // Definitions of non-inline member functions. 1370 template<size_t _Nb> 1371 template<class _CharT, class _Traits> 1372 void 1373 bitset<_Nb>:: 1374 _M_copy_from_ptr(const _CharT* __s, size_t __len, 1375 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 1376 { 1377 reset(); 1378 const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos))); 1379 for (size_t __i = __nbits; __i > 0; --__i) 1380 { 1381 const _CharT __c = __s[__pos + __nbits - __i]; 1382 if (_Traits::eq(__c, __zero)) 1383 ; 1384 else if (_Traits::eq(__c, __one)) 1385 _Unchecked_set(__i - 1); 1386 else 1387 __throw_invalid_argument(__N("bitset::_M_copy_from_ptr")); 1388 } 1389 } 1390 1391 template<size_t _Nb> 1392 template<class _CharT, class _Traits, class _Alloc> 1393 void 1394 bitset<_Nb>:: 1395 _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s, 1396 _CharT __zero, _CharT __one) const 1397 { 1398 __s.assign(_Nb, __zero); 1399 for (size_t __i = _Nb; __i > 0; --__i) 1400 if (_Unchecked_test(__i - 1)) 1401 _Traits::assign(__s[_Nb - __i], __one); 1402 } 1403 1404 // 23.3.5.3 bitset operations: 1405 //@{ 1406 /** 1407 * @brief Global bitwise operations on bitsets. 1408 * @param __x A bitset. 1409 * @param __y A bitset of the same size as @a __x. 1410 * @return A new bitset. 1411 * 1412 * These should be self-explanatory. 1413 */ 1414 template<size_t _Nb> 1415 inline bitset<_Nb> 1416 operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1417 { 1418 bitset<_Nb> __result(__x); 1419 __result &= __y; 1420 return __result; 1421 } 1422 1423 template<size_t _Nb> 1424 inline bitset<_Nb> 1425 operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1426 { 1427 bitset<_Nb> __result(__x); 1428 __result |= __y; 1429 return __result; 1430 } 1431 1432 template <size_t _Nb> 1433 inline bitset<_Nb> 1434 operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT 1435 { 1436 bitset<_Nb> __result(__x); 1437 __result ^= __y; 1438 return __result; 1439 } 1440 //@} 1441 1442 //@{ 1443 /** 1444 * @brief Global I/O operators for bitsets. 1445 * 1446 * Direct I/O between streams and bitsets is supported. Output is 1447 * straightforward. Input will skip whitespace, only accept @a 0 and @a 1 1448 * characters, and will only extract as many digits as the %bitset will 1449 * hold. 1450 */ 1451 template<class _CharT, class _Traits, size_t _Nb> 1452 std::basic_istream<_CharT, _Traits>& 1453 operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x) 1454 { 1455 typedef typename _Traits::char_type char_type; 1456 typedef std::basic_istream<_CharT, _Traits> __istream_type; 1457 typedef typename __istream_type::ios_base __ios_base; 1458 1459 std::basic_string<_CharT, _Traits> __tmp; 1460 __tmp.reserve(_Nb); 1461 1462 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1463 // 303. Bitset input operator underspecified 1464 const char_type __zero = __is.widen('0'); 1465 const char_type __one = __is.widen('1'); 1466 1467 typename __ios_base::iostate __state = __ios_base::goodbit; 1468 typename __istream_type::sentry __sentry(__is); 1469 if (__sentry) 1470 { 1471 __try 1472 { 1473 for (size_t __i = _Nb; __i > 0; --__i) 1474 { 1475 static typename _Traits::int_type __eof = _Traits::eof(); 1476 1477 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 1478 if (_Traits::eq_int_type(__c1, __eof)) 1479 { 1480 __state |= __ios_base::eofbit; 1481 break; 1482 } 1483 else 1484 { 1485 const char_type __c2 = _Traits::to_char_type(__c1); 1486 if (_Traits::eq(__c2, __zero)) 1487 __tmp.push_back(__zero); 1488 else if (_Traits::eq(__c2, __one)) 1489 __tmp.push_back(__one); 1490 else if (_Traits:: 1491 eq_int_type(__is.rdbuf()->sputbackc(__c2), 1492 __eof)) 1493 { 1494 __state |= __ios_base::failbit; 1495 break; 1496 } 1497 } 1498 } 1499 } 1500 __catch(__cxxabiv1::__forced_unwind&) 1501 { 1502 __is._M_setstate(__ios_base::badbit); 1503 __throw_exception_again; 1504 } 1505 __catch(...) 1506 { __is._M_setstate(__ios_base::badbit); } 1507 } 1508 1509 if (__tmp.empty() && _Nb) 1510 __state |= __ios_base::failbit; 1511 else 1512 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb, 1513 __zero, __one); 1514 if (__state) 1515 __is.setstate(__state); 1516 return __is; 1517 } 1518 1519 template <class _CharT, class _Traits, size_t _Nb> 1520 std::basic_ostream<_CharT, _Traits>& 1521 operator<<(std::basic_ostream<_CharT, _Traits>& __os, 1522 const bitset<_Nb>& __x) 1523 { 1524 std::basic_string<_CharT, _Traits> __tmp; 1525 1526 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1527 // 396. what are characters zero and one. 1528 const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc()); 1529 __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1')); 1530 return __os << __tmp; 1531 } 1532 //@} 1533 1534_GLIBCXX_END_NAMESPACE_CONTAINER 1535} // namespace std 1536 1537#undef _GLIBCXX_BITSET_WORDS 1538#undef _GLIBCXX_BITSET_BITS_PER_WORD 1539#undef _GLIBCXX_BITSET_BITS_PER_ULL 1540 1541#if __cplusplus >= 201103L 1542 1543#include <bits/functional_hash.h> 1544 1545namespace std _GLIBCXX_VISIBILITY(default) 1546{ 1547_GLIBCXX_BEGIN_NAMESPACE_VERSION 1548 1549 // DR 1182. 1550 /// std::hash specialization for bitset. 1551 template<size_t _Nb> 1552 struct hash<_GLIBCXX_STD_C::bitset<_Nb>> 1553 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>> 1554 { 1555 size_t 1556 operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept 1557 { 1558 const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__; 1559 return std::_Hash_impl::hash(__b._M_getdata(), __clength); 1560 } 1561 }; 1562 1563 template<> 1564 struct hash<_GLIBCXX_STD_C::bitset<0>> 1565 : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>> 1566 { 1567 size_t 1568 operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept 1569 { return 0; } 1570 }; 1571 1572_GLIBCXX_END_NAMESPACE_VERSION 1573} // namespace 1574 1575#endif // C++11 1576 1577#ifdef _GLIBCXX_DEBUG 1578# include <debug/bitset> 1579#endif 1580 1581#ifdef _GLIBCXX_PROFILE 1582# include <profile/bitset> 1583#endif 1584 1585#endif /* _GLIBCXX_BITSET */ 1586