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