Subversion Repositories Kolibri OS

Rev

Blame | Last modification | View Log | RSS feed

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