libstdc++-v3/include/std/bitset

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