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