Subversion Repositories Kolibri OS

Rev

Go to most recent revision | Blame | Last modification | View Log | RSS feed

  1. // <bitset> -*- C++ -*-
  2.  
  3. // Copyright (C) 2001-2013 Free Software Foundation, Inc.
  4. //
  5. // This file is part of the GNU ISO C++ Library.  This library is free
  6. // software; you can redistribute it and/or modify it under the
  7. // terms of the GNU General Public License as published by the
  8. // Free Software Foundation; either version 3, or (at your option)
  9. // any later version.
  10.  
  11. // This library is distributed in the hope that it will be useful,
  12. // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14. // GNU General Public License for more details.
  15.  
  16. // Under Section 7 of GPL version 3, you are granted additional
  17. // permissions described in the GCC Runtime Library Exception, version
  18. // 3.1, as published by the Free Software Foundation.
  19.  
  20. // You should have received a copy of the GNU General Public License and
  21. // a copy of the GCC Runtime Library Exception along with this program;
  22. // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23. // <http://www.gnu.org/licenses/>.
  24.  
  25. /*
  26.  * Copyright (c) 1998
  27.  * Silicon Graphics Computer Systems, Inc.
  28.  *
  29.  * Permission to use, copy, modify, distribute and sell this software
  30.  * and its documentation for any purpose is hereby granted without fee,
  31.  * provided that the above copyright notice appear in all copies and
  32.  * that both that copyright notice and this permission notice appear
  33.  * in supporting documentation.  Silicon Graphics makes no
  34.  * representations about the suitability of this software for any
  35.  * purpose.  It is provided "as is" without express or implied warranty.
  36.  */
  37.  
  38. /** @file include/bitset
  39.  *  This is a Standard C++ Library header.
  40.  */
  41.  
  42. #ifndef _GLIBCXX_BITSET
  43. #define _GLIBCXX_BITSET 1
  44.  
  45. #pragma GCC system_header
  46.  
  47. #include <string>
  48. #include <bits/functexcept.h>   // For invalid_argument, out_of_range,
  49.                                 // overflow_error
  50. #include <iosfwd>
  51. #include <bits/cxxabi_forced.h>
  52.  
  53. #define _GLIBCXX_BITSET_BITS_PER_WORD  (__CHAR_BIT__ * __SIZEOF_LONG__)
  54. #define _GLIBCXX_BITSET_WORDS(__n) \
  55.   ((__n) / _GLIBCXX_BITSET_BITS_PER_WORD + \
  56.    ((__n) % _GLIBCXX_BITSET_BITS_PER_WORD == 0 ? 0 : 1))
  57.  
  58. #define _GLIBCXX_BITSET_BITS_PER_ULL (__CHAR_BIT__ * __SIZEOF_LONG_LONG__)
  59.  
  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.    *  The %bitset class represents a @e fixed-size sequence of bits.
  685.    *
  686.    *  @ingroup containers
  687.    *
  688.    *  (Note that %bitset does @e not meet the formal requirements of a
  689.    *  <a href="tables.html#65">container</a>.  Mainly, it lacks iterators.)
  690.    *
  691.    *  The template argument, @a Nb, may be any non-negative number,
  692.    *  specifying the number of bits (e.g., "0", "12", "1024*1024").
  693.    *
  694.    *  In the general unoptimized case, storage is allocated in word-sized
  695.    *  blocks.  Let B be the number of bits in a word, then (Nb+(B-1))/B
  696.    *  words will be used for storage.  B - Nb%B bits are unused.  (They are
  697.    *  the high-order bits in the highest word.)  It is a class invariant
  698.    *  that those unused bits are always zero.
  699.    *
  700.    *  If you think of %bitset as <em>a simple array of bits</em>, be
  701.    *  aware that your mental picture is reversed: a %bitset behaves
  702.    *  the same way as bits in integers do, with the bit at index 0 in
  703.    *  the <em>least significant / right-hand</em> position, and the bit at
  704.    *  index Nb-1 in the <em>most significant / left-hand</em> position.
  705.    *  Thus, unlike other containers, a %bitset's index <em>counts from
  706.    *  right to left</em>, to put it very loosely.
  707.    *
  708.    *  This behavior is preserved when translating to and from strings.  For
  709.    *  example, the first line of the following program probably prints
  710.    *  <em>b(&apos;a&apos;) is 0001100001</em> on a modern ASCII system.
  711.    *
  712.    *  @code
  713.    *     #include <bitset>
  714.    *     #include <iostream>
  715.    *     #include <sstream>
  716.    *
  717.    *     using namespace std;
  718.    *
  719.    *     int main()
  720.    *     {
  721.    *         long         a = 'a';
  722.    *         bitset<10>   b(a);
  723.    *
  724.    *         cout << "b('a') is " << b << endl;
  725.    *
  726.    *         ostringstream s;
  727.    *         s << b;
  728.    *         string  str = s.str();
  729.    *         cout << "index 3 in the string is " << str[3] << " but\n"
  730.    *              << "index 3 in the bitset is " << b[3] << endl;
  731.    *     }
  732.    *  @endcode
  733.    *
  734.    *  Also see:
  735.    *  http://gcc.gnu.org/onlinedocs/libstdc++/manual/bk01pt12ch33s02.html
  736.    *  for a description of extensions.
  737.    *
  738.    *  Most of the actual code isn't contained in %bitset<> itself, but in the
  739.    *  base class _Base_bitset.  The base class works with whole words, not with
  740.    *  individual bits.  This allows us to specialize _Base_bitset for the
  741.    *  important special case where the %bitset is only a single word.
  742.    *
  743.    *  Extra confusion can result due to the fact that the storage for
  744.    *  _Base_bitset @e is a regular array, and is indexed as such.  This is
  745.    *  carefully encapsulated.
  746.   */
  747.   template<size_t _Nb>
  748.     class bitset
  749.     : private _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)>
  750.     {
  751.     private:
  752.       typedef _Base_bitset<_GLIBCXX_BITSET_WORDS(_Nb)> _Base;
  753.       typedef unsigned long _WordT;
  754.  
  755.       void
  756.       _M_do_sanitize() _GLIBCXX_NOEXCEPT
  757.       {
  758.         typedef _Sanitize<_Nb % _GLIBCXX_BITSET_BITS_PER_WORD> __sanitize_type;
  759.         __sanitize_type::_S_do_sanitize(this->_M_hiword());
  760.       }
  761.  
  762. #if __cplusplus >= 201103L
  763.       template<typename> friend struct hash;
  764. #endif
  765.  
  766.     public:
  767.       /**
  768.        *  This encapsulates the concept of a single bit.  An instance of this
  769.        *  class is a proxy for an actual bit; this way the individual bit
  770.        *  operations are done as faster word-size bitwise instructions.
  771.        *
  772.        *  Most users will never need to use this class directly; conversions
  773.        *  to and from bool are automatic and should be transparent.  Overloaded
  774.        *  operators help to preserve the illusion.
  775.        *
  776.        *  (On a typical system, this <em>bit %reference</em> is 64
  777.        *  times the size of an actual bit.  Ha.)
  778.        */
  779.       class reference
  780.       {
  781.         friend class bitset;
  782.  
  783.         _WordT* _M_wp;
  784.         size_t  _M_bpos;
  785.        
  786.         // left undefined
  787.         reference();
  788.        
  789.       public:
  790.         reference(bitset& __b, size_t __pos) _GLIBCXX_NOEXCEPT
  791.         {
  792.           _M_wp = &__b._M_getword(__pos);
  793.           _M_bpos = _Base::_S_whichbit(__pos);
  794.         }
  795.  
  796.         ~reference() _GLIBCXX_NOEXCEPT
  797.         { }
  798.  
  799.         // For b[i] = __x;
  800.         reference&
  801.         operator=(bool __x) _GLIBCXX_NOEXCEPT
  802.         {
  803.           if (__x)
  804.             *_M_wp |= _Base::_S_maskbit(_M_bpos);
  805.           else
  806.             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
  807.           return *this;
  808.         }
  809.  
  810.         // For b[i] = b[__j];
  811.         reference&
  812.         operator=(const reference& __j) _GLIBCXX_NOEXCEPT
  813.         {
  814.           if ((*(__j._M_wp) & _Base::_S_maskbit(__j._M_bpos)))
  815.             *_M_wp |= _Base::_S_maskbit(_M_bpos);
  816.           else
  817.             *_M_wp &= ~_Base::_S_maskbit(_M_bpos);
  818.           return *this;
  819.         }
  820.  
  821.         // Flips the bit
  822.         bool
  823.         operator~() const _GLIBCXX_NOEXCEPT
  824.         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) == 0; }
  825.  
  826.         // For __x = b[i];
  827.         operator bool() const _GLIBCXX_NOEXCEPT
  828.         { return (*(_M_wp) & _Base::_S_maskbit(_M_bpos)) != 0; }
  829.  
  830.         // For b[i].flip();
  831.         reference&
  832.         flip() _GLIBCXX_NOEXCEPT
  833.         {
  834.           *_M_wp ^= _Base::_S_maskbit(_M_bpos);
  835.           return *this;
  836.         }
  837.       };
  838.       friend class reference;
  839.  
  840.       // 23.3.5.1 constructors:
  841.       /// All bits set to zero.
  842.       _GLIBCXX_CONSTEXPR bitset() _GLIBCXX_NOEXCEPT
  843.       { }
  844.  
  845.       /// Initial bits bitwise-copied from a single word (others set to zero).
  846. #if __cplusplus >= 201103L
  847.       constexpr bitset(unsigned long long __val) noexcept
  848.       : _Base(_Sanitize_val<_Nb>::_S_do_sanitize_val(__val)) { }
  849. #else
  850.       bitset(unsigned long __val)
  851.       : _Base(__val)
  852.       { _M_do_sanitize(); }
  853. #endif
  854.  
  855.       /**
  856.        *  Use a subset of a string.
  857.        *  @param  __s  A string of @a 0 and @a 1 characters.
  858.        *  @param  __position  Index of the first character in @a __s to use;
  859.        *                    defaults to zero.
  860.        *  @throw  std::out_of_range  If @a pos is bigger the size of @a __s.
  861.        *  @throw  std::invalid_argument  If a character appears in the string
  862.        *                                 which is neither @a 0 nor @a 1.
  863.        */
  864.       template<class _CharT, class _Traits, class _Alloc>
  865.         explicit
  866.         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
  867.                size_t __position = 0)
  868.         : _Base()
  869.         {
  870.           if (__position > __s.size())
  871.             __throw_out_of_range(__N("bitset::bitset initial position "
  872.                                      "not valid"));
  873.           _M_copy_from_string(__s, __position,
  874.                               std::basic_string<_CharT, _Traits, _Alloc>::npos,
  875.                               _CharT('0'), _CharT('1'));
  876.         }
  877.  
  878.       /**
  879.        *  Use a subset of a string.
  880.        *  @param  __s  A string of @a 0 and @a 1 characters.
  881.        *  @param  __position  Index of the first character in @a __s to use.
  882.        *  @param  __n    The number of characters to copy.
  883.        *  @throw std::out_of_range If @a __position is bigger the size
  884.        *  of @a __s.
  885.        *  @throw  std::invalid_argument  If a character appears in the string
  886.        *                                 which is neither @a 0 nor @a 1.
  887.        */
  888.       template<class _CharT, class _Traits, class _Alloc>
  889.         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
  890.                size_t __position, size_t __n)
  891.         : _Base()
  892.         {
  893.           if (__position > __s.size())
  894.             __throw_out_of_range(__N("bitset::bitset initial position "
  895.                                      "not valid"));
  896.           _M_copy_from_string(__s, __position, __n, _CharT('0'), _CharT('1'));
  897.         }
  898.  
  899.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  900.       // 396. what are characters zero and one.
  901.       template<class _CharT, class _Traits, class _Alloc>
  902.         bitset(const std::basic_string<_CharT, _Traits, _Alloc>& __s,
  903.                size_t __position, size_t __n,
  904.                _CharT __zero, _CharT __one = _CharT('1'))
  905.         : _Base()
  906.         {
  907.           if (__position > __s.size())
  908.             __throw_out_of_range(__N("bitset::bitset initial position "
  909.                                      "not valid"));
  910.           _M_copy_from_string(__s, __position, __n, __zero, __one);
  911.         }
  912.  
  913. #if __cplusplus >= 201103L
  914.       /**
  915.        *  Construct from a character %array.
  916.        *  @param  __str  An %array of characters @a zero and @a one.
  917.        *  @param  __n    The number of characters to use.
  918.        *  @param  __zero The character corresponding to the value 0.
  919.        *  @param  __one  The character corresponding to the value 1.
  920.        *  @throw  std::invalid_argument If a character appears in the string
  921.        *                                which is neither @a __zero nor @a __one.
  922.        */
  923.       template<typename _CharT>
  924.         explicit
  925.         bitset(const _CharT* __str,
  926.                typename std::basic_string<_CharT>::size_type __n
  927.                = std::basic_string<_CharT>::npos,
  928.                _CharT __zero = _CharT('0'), _CharT __one = _CharT('1'))
  929.         : _Base()
  930.         {
  931.           if (!__str)
  932.             __throw_logic_error(__N("bitset::bitset(const _CharT*, ...)"));
  933.  
  934.           if (__n == std::basic_string<_CharT>::npos)
  935.             __n = std::char_traits<_CharT>::length(__str);
  936.           _M_copy_from_ptr<_CharT, std::char_traits<_CharT>>(__str, __n, 0,
  937.                                                              __n, __zero,
  938.                                                              __one);
  939.         }
  940. #endif
  941.  
  942.       // 23.3.5.2 bitset operations:
  943.       //@{
  944.       /**
  945.        *  Operations on bitsets.
  946.        *  @param  __rhs  A same-sized bitset.
  947.        *
  948.        *  These should be self-explanatory.
  949.        */
  950.       bitset<_Nb>&
  951.       operator&=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
  952.       {
  953.         this->_M_do_and(__rhs);
  954.         return *this;
  955.       }
  956.  
  957.       bitset<_Nb>&
  958.       operator|=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
  959.       {
  960.         this->_M_do_or(__rhs);
  961.         return *this;
  962.       }
  963.  
  964.       bitset<_Nb>&
  965.       operator^=(const bitset<_Nb>& __rhs) _GLIBCXX_NOEXCEPT
  966.       {
  967.         this->_M_do_xor(__rhs);
  968.         return *this;
  969.       }
  970.       //@}
  971.      
  972.       //@{
  973.       /**
  974.        *  Operations on bitsets.
  975.        *  @param  __position  The number of places to shift.
  976.        *
  977.        *  These should be self-explanatory.
  978.        */
  979.       bitset<_Nb>&
  980.       operator<<=(size_t __position) _GLIBCXX_NOEXCEPT
  981.       {
  982.         if (__builtin_expect(__position < _Nb, 1))
  983.           {
  984.             this->_M_do_left_shift(__position);
  985.             this->_M_do_sanitize();
  986.           }
  987.         else
  988.           this->_M_do_reset();
  989.         return *this;
  990.       }
  991.  
  992.       bitset<_Nb>&
  993.       operator>>=(size_t __position) _GLIBCXX_NOEXCEPT
  994.       {
  995.         if (__builtin_expect(__position < _Nb, 1))
  996.           {
  997.             this->_M_do_right_shift(__position);
  998.             this->_M_do_sanitize();
  999.           }
  1000.         else
  1001.           this->_M_do_reset();
  1002.         return *this;
  1003.       }
  1004.       //@}
  1005.      
  1006.       //@{
  1007.       /**
  1008.        *  These versions of single-bit set, reset, flip, and test are
  1009.        *  extensions from the SGI version.  They do no range checking.
  1010.        *  @ingroup SGIextensions
  1011.        */
  1012.       bitset<_Nb>&
  1013.       _Unchecked_set(size_t __pos) _GLIBCXX_NOEXCEPT
  1014.       {
  1015.         this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
  1016.         return *this;
  1017.       }
  1018.  
  1019.       bitset<_Nb>&
  1020.       _Unchecked_set(size_t __pos, int __val) _GLIBCXX_NOEXCEPT
  1021.       {
  1022.         if (__val)
  1023.           this->_M_getword(__pos) |= _Base::_S_maskbit(__pos);
  1024.         else
  1025.           this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
  1026.         return *this;
  1027.       }
  1028.  
  1029.       bitset<_Nb>&
  1030.       _Unchecked_reset(size_t __pos) _GLIBCXX_NOEXCEPT
  1031.       {
  1032.         this->_M_getword(__pos) &= ~_Base::_S_maskbit(__pos);
  1033.         return *this;
  1034.       }
  1035.  
  1036.       bitset<_Nb>&
  1037.       _Unchecked_flip(size_t __pos) _GLIBCXX_NOEXCEPT
  1038.       {
  1039.         this->_M_getword(__pos) ^= _Base::_S_maskbit(__pos);
  1040.         return *this;
  1041.       }
  1042.  
  1043.       _GLIBCXX_CONSTEXPR bool
  1044.       _Unchecked_test(size_t __pos) const _GLIBCXX_NOEXCEPT
  1045.       { return ((this->_M_getword(__pos) & _Base::_S_maskbit(__pos))
  1046.                 != static_cast<_WordT>(0)); }
  1047.       //@}
  1048.      
  1049.       // Set, reset, and flip.
  1050.       /**
  1051.        *  @brief Sets every bit to true.
  1052.        */
  1053.       bitset<_Nb>&
  1054.       set() _GLIBCXX_NOEXCEPT
  1055.       {
  1056.         this->_M_do_set();
  1057.         this->_M_do_sanitize();
  1058.         return *this;
  1059.       }
  1060.  
  1061.       /**
  1062.        *  @brief Sets a given bit to a particular value.
  1063.        *  @param  __position  The index of the bit.
  1064.        *  @param  __val  Either true or false, defaults to true.
  1065.        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
  1066.        */
  1067.       bitset<_Nb>&
  1068.       set(size_t __position, bool __val = true)
  1069.       {
  1070.         if (__position >= _Nb)
  1071.           __throw_out_of_range(__N("bitset::set"));
  1072.         return _Unchecked_set(__position, __val);
  1073.       }
  1074.  
  1075.       /**
  1076.        *  @brief Sets every bit to false.
  1077.        */
  1078.       bitset<_Nb>&
  1079.       reset() _GLIBCXX_NOEXCEPT
  1080.       {
  1081.         this->_M_do_reset();
  1082.         return *this;
  1083.       }
  1084.  
  1085.       /**
  1086.        *  @brief Sets a given bit to false.
  1087.        *  @param  __position  The index of the bit.
  1088.        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
  1089.        *
  1090.        *  Same as writing @c set(pos,false).
  1091.        */
  1092.       bitset<_Nb>&
  1093.       reset(size_t __position)
  1094.       {
  1095.         if (__position >= _Nb)
  1096.           __throw_out_of_range(__N("bitset::reset"));
  1097.         return _Unchecked_reset(__position);
  1098.       }
  1099.      
  1100.       /**
  1101.        *  @brief Toggles every bit to its opposite value.
  1102.        */
  1103.       bitset<_Nb>&
  1104.       flip() _GLIBCXX_NOEXCEPT
  1105.       {
  1106.         this->_M_do_flip();
  1107.         this->_M_do_sanitize();
  1108.         return *this;
  1109.       }
  1110.  
  1111.       /**
  1112.        *  @brief Toggles a given bit to its opposite value.
  1113.        *  @param  __position  The index of the bit.
  1114.        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
  1115.        */
  1116.       bitset<_Nb>&
  1117.       flip(size_t __position)
  1118.       {
  1119.         if (__position >= _Nb)
  1120.           __throw_out_of_range(__N("bitset::flip"));
  1121.         return _Unchecked_flip(__position);
  1122.       }
  1123.      
  1124.       /// See the no-argument flip().
  1125.       bitset<_Nb>
  1126.       operator~() const _GLIBCXX_NOEXCEPT
  1127.       { return bitset<_Nb>(*this).flip(); }
  1128.  
  1129.       //@{
  1130.       /**
  1131.        *  @brief  Array-indexing support.
  1132.        *  @param  __position  Index into the %bitset.
  1133.        *  @return A bool for a <em>const %bitset</em>.  For non-const
  1134.        *           bitsets, an instance of the reference proxy class.
  1135.        *  @note  These operators do no range checking and throw no exceptions,
  1136.        *         as required by DR 11 to the standard.
  1137.        *
  1138.        *  _GLIBCXX_RESOLVE_LIB_DEFECTS Note that this implementation already
  1139.        *  resolves DR 11 (items 1 and 2), but does not do the range-checking
  1140.        *  required by that DR's resolution.  -pme
  1141.        *  The DR has since been changed:  range-checking is a precondition
  1142.        *  (users' responsibility), and these functions must not throw.  -pme
  1143.        */
  1144.       reference
  1145.       operator[](size_t __position)
  1146.       { return reference(*this, __position); }
  1147.  
  1148.       _GLIBCXX_CONSTEXPR bool
  1149.       operator[](size_t __position) const
  1150.       { return _Unchecked_test(__position); }
  1151.       //@}
  1152.      
  1153.       /**
  1154.        *  @brief Returns a numerical interpretation of the %bitset.
  1155.        *  @return  The integral equivalent of the bits.
  1156.        *  @throw  std::overflow_error  If there are too many bits to be
  1157.        *                               represented in an @c unsigned @c long.
  1158.        */
  1159.       unsigned long
  1160.       to_ulong() const
  1161.       { return this->_M_do_to_ulong(); }
  1162.  
  1163. #if __cplusplus >= 201103L
  1164.       unsigned long long
  1165.       to_ullong() const
  1166.       { return this->_M_do_to_ullong(); }
  1167. #endif
  1168.  
  1169.       /**
  1170.        *  @brief Returns a character interpretation of the %bitset.
  1171.        *  @return  The string equivalent of the bits.
  1172.        *
  1173.        *  Note the ordering of the bits:  decreasing character positions
  1174.        *  correspond to increasing bit positions (see the main class notes for
  1175.        *  an example).
  1176.        */
  1177.       template<class _CharT, class _Traits, class _Alloc>
  1178.         std::basic_string<_CharT, _Traits, _Alloc>
  1179.         to_string() const
  1180.         {
  1181.           std::basic_string<_CharT, _Traits, _Alloc> __result;
  1182.           _M_copy_to_string(__result, _CharT('0'), _CharT('1'));
  1183.           return __result;
  1184.         }
  1185.  
  1186.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1187.       // 396. what are characters zero and one.
  1188.       template<class _CharT, class _Traits, class _Alloc>
  1189.         std::basic_string<_CharT, _Traits, _Alloc>
  1190.         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
  1191.         {
  1192.           std::basic_string<_CharT, _Traits, _Alloc> __result;
  1193.           _M_copy_to_string(__result, __zero, __one);
  1194.           return __result;
  1195.         }
  1196.  
  1197.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1198.       // 434. bitset::to_string() hard to use.
  1199.       template<class _CharT, class _Traits>
  1200.         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
  1201.         to_string() const
  1202.         { return to_string<_CharT, _Traits, std::allocator<_CharT> >(); }
  1203.  
  1204.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1205.       // 853. to_string needs updating with zero and one.
  1206.       template<class _CharT, class _Traits>
  1207.         std::basic_string<_CharT, _Traits, std::allocator<_CharT> >
  1208.         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
  1209.         { return to_string<_CharT, _Traits,
  1210.                            std::allocator<_CharT> >(__zero, __one); }
  1211.  
  1212.       template<class _CharT>
  1213.         std::basic_string<_CharT, std::char_traits<_CharT>,
  1214.                           std::allocator<_CharT> >
  1215.         to_string() const
  1216.         {
  1217.           return to_string<_CharT, std::char_traits<_CharT>,
  1218.                            std::allocator<_CharT> >();
  1219.         }
  1220.  
  1221.       template<class _CharT>
  1222.         std::basic_string<_CharT, std::char_traits<_CharT>,
  1223.                           std::allocator<_CharT> >
  1224.         to_string(_CharT __zero, _CharT __one = _CharT('1')) const
  1225.         {
  1226.           return to_string<_CharT, std::char_traits<_CharT>,
  1227.                            std::allocator<_CharT> >(__zero, __one);
  1228.         }
  1229.  
  1230.       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
  1231.       to_string() const
  1232.       {
  1233.         return to_string<char, std::char_traits<char>,
  1234.                          std::allocator<char> >();
  1235.       }
  1236.  
  1237.       std::basic_string<char, std::char_traits<char>, std::allocator<char> >
  1238.       to_string(char __zero, char __one = '1') const
  1239.       {
  1240.         return to_string<char, std::char_traits<char>,
  1241.                          std::allocator<char> >(__zero, __one);
  1242.       }
  1243.  
  1244.       // Helper functions for string operations.
  1245.       template<class _CharT, class _Traits>
  1246.         void
  1247.         _M_copy_from_ptr(const _CharT*, size_t, size_t, size_t,
  1248.                          _CharT, _CharT);
  1249.  
  1250.       template<class _CharT, class _Traits, class _Alloc>
  1251.         void
  1252.         _M_copy_from_string(const std::basic_string<_CharT,
  1253.                             _Traits, _Alloc>& __s, size_t __pos, size_t __n,
  1254.                             _CharT __zero, _CharT __one)
  1255.         { _M_copy_from_ptr<_CharT, _Traits>(__s.data(), __s.size(), __pos, __n,
  1256.                                             __zero, __one); }
  1257.  
  1258.       template<class _CharT, class _Traits, class _Alloc>
  1259.         void
  1260.         _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>&,
  1261.                           _CharT, _CharT) const;
  1262.  
  1263.       // NB: Backward compat.
  1264.       template<class _CharT, class _Traits, class _Alloc>
  1265.         void
  1266.         _M_copy_from_string(const std::basic_string<_CharT,
  1267.                             _Traits, _Alloc>& __s, size_t __pos, size_t __n)
  1268.         { _M_copy_from_string(__s, __pos, __n, _CharT('0'), _CharT('1')); }
  1269.  
  1270.       template<class _CharT, class _Traits, class _Alloc>
  1271.         void
  1272.         _M_copy_to_string(std::basic_string<_CharT, _Traits,_Alloc>& __s) const
  1273.         { _M_copy_to_string(__s, _CharT('0'), _CharT('1')); }
  1274.  
  1275.       /// Returns the number of bits which are set.
  1276.       size_t
  1277.       count() const _GLIBCXX_NOEXCEPT
  1278.       { return this->_M_do_count(); }
  1279.  
  1280.       /// Returns the total number of bits.
  1281.       _GLIBCXX_CONSTEXPR size_t
  1282.       size() const _GLIBCXX_NOEXCEPT
  1283.       { return _Nb; }
  1284.  
  1285.       //@{
  1286.       /// These comparisons for equality/inequality are, well, @e bitwise.
  1287.       bool
  1288.       operator==(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
  1289.       { return this->_M_is_equal(__rhs); }
  1290.  
  1291.       bool
  1292.       operator!=(const bitset<_Nb>& __rhs) const _GLIBCXX_NOEXCEPT
  1293.       { return !this->_M_is_equal(__rhs); }
  1294.       //@}
  1295.      
  1296.       /**
  1297.        *  @brief Tests the value of a bit.
  1298.        *  @param  __position  The index of a bit.
  1299.        *  @return  The value at @a pos.
  1300.        *  @throw  std::out_of_range  If @a pos is bigger the size of the %set.
  1301.        */
  1302.       bool
  1303.       test(size_t __position) const
  1304.       {
  1305.         if (__position >= _Nb)
  1306.           __throw_out_of_range(__N("bitset::test"));
  1307.         return _Unchecked_test(__position);
  1308.       }
  1309.  
  1310.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1311.       // DR 693. std::bitset::all() missing.
  1312.       /**
  1313.        *  @brief Tests whether all the bits are on.
  1314.        *  @return  True if all the bits are set.
  1315.        */
  1316.       bool
  1317.       all() const _GLIBCXX_NOEXCEPT
  1318.       { return this->template _M_are_all<_Nb>(); }
  1319.  
  1320.       /**
  1321.        *  @brief Tests whether any of the bits are on.
  1322.        *  @return  True if at least one bit is set.
  1323.        */
  1324.       bool
  1325.       any() const _GLIBCXX_NOEXCEPT
  1326.       { return this->_M_is_any(); }
  1327.  
  1328.       /**
  1329.        *  @brief Tests whether any of the bits are on.
  1330.        *  @return  True if none of the bits are set.
  1331.        */
  1332.       bool
  1333.       none() const _GLIBCXX_NOEXCEPT
  1334.       { return !this->_M_is_any(); }
  1335.  
  1336.       //@{
  1337.       /// Self-explanatory.
  1338.       bitset<_Nb>
  1339.       operator<<(size_t __position) const _GLIBCXX_NOEXCEPT
  1340.       { return bitset<_Nb>(*this) <<= __position; }
  1341.  
  1342.       bitset<_Nb>
  1343.       operator>>(size_t __position) const _GLIBCXX_NOEXCEPT
  1344.       { return bitset<_Nb>(*this) >>= __position; }
  1345.       //@}
  1346.      
  1347.       /**
  1348.        *  @brief  Finds the index of the first "on" bit.
  1349.        *  @return  The index of the first bit set, or size() if not found.
  1350.        *  @ingroup SGIextensions
  1351.        *  @sa  _Find_next
  1352.        */
  1353.       size_t
  1354.       _Find_first() const _GLIBCXX_NOEXCEPT
  1355.       { return this->_M_do_find_first(_Nb); }
  1356.  
  1357.       /**
  1358.        *  @brief  Finds the index of the next "on" bit after prev.
  1359.        *  @return  The index of the next bit set, or size() if not found.
  1360.        *  @param  __prev  Where to start searching.
  1361.        *  @ingroup SGIextensions
  1362.        *  @sa  _Find_first
  1363.        */
  1364.       size_t
  1365.       _Find_next(size_t __prev) const _GLIBCXX_NOEXCEPT
  1366.       { return this->_M_do_find_next(__prev, _Nb); }
  1367.     };
  1368.  
  1369.   // Definitions of non-inline member functions.
  1370.   template<size_t _Nb>
  1371.     template<class _CharT, class _Traits>
  1372.       void
  1373.       bitset<_Nb>::
  1374.       _M_copy_from_ptr(const _CharT* __s, size_t __len,
  1375.                        size_t __pos, size_t __n, _CharT __zero, _CharT __one)
  1376.       {
  1377.         reset();
  1378.         const size_t __nbits = std::min(_Nb, std::min(__n, size_t(__len - __pos)));
  1379.         for (size_t __i = __nbits; __i > 0; --__i)
  1380.           {
  1381.             const _CharT __c = __s[__pos + __nbits - __i];
  1382.             if (_Traits::eq(__c, __zero))
  1383.               ;
  1384.             else if (_Traits::eq(__c, __one))
  1385.               _Unchecked_set(__i - 1);
  1386.             else
  1387.               __throw_invalid_argument(__N("bitset::_M_copy_from_ptr"));
  1388.           }
  1389.       }
  1390.  
  1391.   template<size_t _Nb>
  1392.     template<class _CharT, class _Traits, class _Alloc>
  1393.       void
  1394.       bitset<_Nb>::
  1395.       _M_copy_to_string(std::basic_string<_CharT, _Traits, _Alloc>& __s,
  1396.                         _CharT __zero, _CharT __one) const
  1397.       {
  1398.         __s.assign(_Nb, __zero);
  1399.         for (size_t __i = _Nb; __i > 0; --__i)
  1400.           if (_Unchecked_test(__i - 1))
  1401.             _Traits::assign(__s[_Nb - __i], __one);
  1402.       }
  1403.  
  1404.   // 23.3.5.3 bitset operations:
  1405.   //@{
  1406.   /**
  1407.    *  @brief  Global bitwise operations on bitsets.
  1408.    *  @param  __x  A bitset.
  1409.    *  @param  __y  A bitset of the same size as @a __x.
  1410.    *  @return  A new bitset.
  1411.    *
  1412.    *  These should be self-explanatory.
  1413.   */
  1414.   template<size_t _Nb>
  1415.     inline bitset<_Nb>
  1416.     operator&(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
  1417.     {
  1418.       bitset<_Nb> __result(__x);
  1419.       __result &= __y;
  1420.       return __result;
  1421.     }
  1422.  
  1423.   template<size_t _Nb>
  1424.     inline bitset<_Nb>
  1425.     operator|(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
  1426.     {
  1427.       bitset<_Nb> __result(__x);
  1428.       __result |= __y;
  1429.       return __result;
  1430.     }
  1431.  
  1432.   template <size_t _Nb>
  1433.     inline bitset<_Nb>
  1434.     operator^(const bitset<_Nb>& __x, const bitset<_Nb>& __y) _GLIBCXX_NOEXCEPT
  1435.     {
  1436.       bitset<_Nb> __result(__x);
  1437.       __result ^= __y;
  1438.       return __result;
  1439.     }
  1440.   //@}
  1441.  
  1442.   //@{
  1443.   /**
  1444.    *  @brief Global I/O operators for bitsets.
  1445.    *
  1446.    *  Direct I/O between streams and bitsets is supported.  Output is
  1447.    *  straightforward.  Input will skip whitespace, only accept @a 0 and @a 1
  1448.    *  characters, and will only extract as many digits as the %bitset will
  1449.    *  hold.
  1450.   */
  1451.   template<class _CharT, class _Traits, size_t _Nb>
  1452.     std::basic_istream<_CharT, _Traits>&
  1453.     operator>>(std::basic_istream<_CharT, _Traits>& __is, bitset<_Nb>& __x)
  1454.     {
  1455.       typedef typename _Traits::char_type          char_type;
  1456.       typedef std::basic_istream<_CharT, _Traits>  __istream_type;
  1457.       typedef typename __istream_type::ios_base    __ios_base;
  1458.  
  1459.       std::basic_string<_CharT, _Traits> __tmp;
  1460.       __tmp.reserve(_Nb);
  1461.  
  1462.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1463.       // 303. Bitset input operator underspecified
  1464.       const char_type __zero = __is.widen('0');
  1465.       const char_type __one = __is.widen('1');
  1466.  
  1467.       typename __ios_base::iostate __state = __ios_base::goodbit;
  1468.       typename __istream_type::sentry __sentry(__is);
  1469.       if (__sentry)
  1470.         {
  1471.           __try
  1472.             {
  1473.               for (size_t __i = _Nb; __i > 0; --__i)
  1474.                 {
  1475.                   static typename _Traits::int_type __eof = _Traits::eof();
  1476.                  
  1477.                   typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
  1478.                   if (_Traits::eq_int_type(__c1, __eof))
  1479.                     {
  1480.                       __state |= __ios_base::eofbit;
  1481.                       break;
  1482.                     }
  1483.                   else
  1484.                     {
  1485.                       const char_type __c2 = _Traits::to_char_type(__c1);
  1486.                       if (_Traits::eq(__c2, __zero))
  1487.                         __tmp.push_back(__zero);
  1488.                       else if (_Traits::eq(__c2, __one))
  1489.                         __tmp.push_back(__one);
  1490.                       else if (_Traits::
  1491.                                eq_int_type(__is.rdbuf()->sputbackc(__c2),
  1492.                                            __eof))
  1493.                         {
  1494.                           __state |= __ios_base::failbit;
  1495.                           break;
  1496.                         }
  1497.                     }
  1498.                 }
  1499.             }
  1500.           __catch(__cxxabiv1::__forced_unwind&)
  1501.             {
  1502.               __is._M_setstate(__ios_base::badbit);            
  1503.               __throw_exception_again;
  1504.             }
  1505.           __catch(...)
  1506.             { __is._M_setstate(__ios_base::badbit); }
  1507.         }
  1508.  
  1509.       if (__tmp.empty() && _Nb)
  1510.         __state |= __ios_base::failbit;
  1511.       else
  1512.         __x._M_copy_from_string(__tmp, static_cast<size_t>(0), _Nb,
  1513.                                 __zero, __one);
  1514.       if (__state)
  1515.         __is.setstate(__state);
  1516.       return __is;
  1517.     }
  1518.  
  1519.   template <class _CharT, class _Traits, size_t _Nb>
  1520.     std::basic_ostream<_CharT, _Traits>&
  1521.     operator<<(std::basic_ostream<_CharT, _Traits>& __os,
  1522.                const bitset<_Nb>& __x)
  1523.     {
  1524.       std::basic_string<_CharT, _Traits> __tmp;
  1525.  
  1526.       // _GLIBCXX_RESOLVE_LIB_DEFECTS
  1527.       // 396. what are characters zero and one.
  1528.       const ctype<_CharT>& __ct = use_facet<ctype<_CharT> >(__os.getloc());
  1529.       __x._M_copy_to_string(__tmp, __ct.widen('0'), __ct.widen('1'));
  1530.       return __os << __tmp;
  1531.     }
  1532.   //@}
  1533.  
  1534. _GLIBCXX_END_NAMESPACE_CONTAINER
  1535. } // namespace std
  1536.  
  1537. #undef _GLIBCXX_BITSET_WORDS
  1538. #undef _GLIBCXX_BITSET_BITS_PER_WORD
  1539. #undef _GLIBCXX_BITSET_BITS_PER_ULL
  1540.  
  1541. #if __cplusplus >= 201103L
  1542.  
  1543. #include <bits/functional_hash.h>
  1544.  
  1545. namespace std _GLIBCXX_VISIBILITY(default)
  1546. {
  1547. _GLIBCXX_BEGIN_NAMESPACE_VERSION
  1548.  
  1549.   // DR 1182.
  1550.   /// std::hash specialization for bitset.
  1551.   template<size_t _Nb>
  1552.     struct hash<_GLIBCXX_STD_C::bitset<_Nb>>
  1553.     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<_Nb>>
  1554.     {
  1555.       size_t
  1556.       operator()(const _GLIBCXX_STD_C::bitset<_Nb>& __b) const noexcept
  1557.       {
  1558.         const size_t __clength = (_Nb + __CHAR_BIT__ - 1) / __CHAR_BIT__;
  1559.         return std::_Hash_impl::hash(__b._M_getdata(), __clength);
  1560.       }
  1561.     };
  1562.  
  1563.   template<>
  1564.     struct hash<_GLIBCXX_STD_C::bitset<0>>
  1565.     : public __hash_base<size_t, _GLIBCXX_STD_C::bitset<0>>
  1566.     {
  1567.       size_t
  1568.       operator()(const _GLIBCXX_STD_C::bitset<0>&) const noexcept
  1569.       { return 0; }
  1570.     };
  1571.  
  1572. _GLIBCXX_END_NAMESPACE_VERSION
  1573. } // namespace
  1574.  
  1575. #endif // C++11
  1576.  
  1577. #ifdef _GLIBCXX_DEBUG
  1578. # include <debug/bitset>
  1579. #endif
  1580.  
  1581. #ifdef _GLIBCXX_PROFILE
  1582. # include <profile/bitset>
  1583. #endif
  1584.  
  1585. #endif /* _GLIBCXX_BITSET */
  1586.