Where Online Learning is simpler!

The C and C++ Include Header Files

cat -n /usr/include/c++/15/tr2/dynamic_bitset.tcc

     1	// TR2 <dynamic_bitset> -*- C++ -*-
     2	
     3	// Copyright (C) 2009-2025 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the
     7	// terms of the GNU General Public License as published by the
     8	// Free Software Foundation; either version 3, or (at your option)
     9	// any later version.
    10	
    11	// This library is distributed in the hope that it will be useful,
    12	// but WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    14	// GNU General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	/** @file tr2/dynamic_bitset.tcc
    26	 *  This is an internal header file, included by other library headers.
    27	 *  Do not attempt to use it directly. @headername{tr2/dynamic_bitset}
    28	 */
    29	
    30	#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC
    31	#define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1
    32	
    33	#ifdef _GLIBCXX_SYSHDR
    34	#pragma GCC system_header
    35	#endif
    36	
    37	namespace std _GLIBCXX_VISIBILITY(default)
    38	{
    39	_GLIBCXX_BEGIN_NAMESPACE_VERSION
    40	
    41	namespace tr2
    42	{
    43	  // Definitions of non-inline functions from __dynamic_bitset_base.
    44	  template<typename _WordT, typename _Alloc>
    45	    void
    46	    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
    47	    {
    48	      if (__builtin_expect(__shift != 0, 1))
    49		{
    50		  const size_t __wshift = __shift / _S_bits_per_block;
    51		  const size_t __offset = __shift % _S_bits_per_block;
    52	
    53		  if (__offset == 0)
    54		    for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
    55		      this->_M_w[__n] = this->_M_w[__n - __wshift];
    56		  else
    57		    {
    58		      const size_t __sub_offset = _S_bits_per_block - __offset;
    59		      for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
    60			this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
    61				     | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
    62		      this->_M_w[__wshift] = this->_M_w[0] << __offset;
    63		    }
    64	
    65		  std::fill_n(this->_M_w.begin(), __wshift, _WordT(0));
    66		}
    67	    }
    68	
    69	  template<typename _WordT, typename _Alloc>
    70	    void
    71	    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
    72	    {
    73	      if (__builtin_expect(__shift != 0, 1))
    74		{
    75		  const size_t __wshift = __shift / _S_bits_per_block;
    76		  const size_t __offset = __shift % _S_bits_per_block;
    77		  const size_t __limit = this->_M_w.size() - __wshift - 1;
    78	
    79		  if (__offset == 0)
    80		    for (size_t __n = 0; __n <= __limit; ++__n)
    81		      this->_M_w[__n] = this->_M_w[__n + __wshift];
    82		  else
    83		    {
    84		      const size_t __sub_offset = (_S_bits_per_block
    85						   - __offset);
    86		      for (size_t __n = 0; __n < __limit; ++__n)
    87			this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
    88				     | (this->_M_w[__n + __wshift + 1] << __sub_offset));
    89		      this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
    90		    }
    91	
    92		  std::fill_n(this->_M_w.end() - __wshift, __wshift, _WordT(0));
    93		}
    94	    }
    95	
    96	  template<typename _WordT, typename _Alloc>
    97	    unsigned long
    98	    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
    99	    {
   100	      size_t __n = sizeof(unsigned long) / sizeof(block_type);
   101	      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
   102		if (this->_M_w[__i])
   103		  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
   104	      unsigned long __res = 0UL;
   105	      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
   106		__res += this->_M_w[__i] << (__i * _S_bits_per_block);
   107	      return __res;
   108	    }
   109	
   110	  template<typename _WordT, typename _Alloc>
   111	    unsigned long long
   112	    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
   113	    {
   114	      size_t __n = sizeof(unsigned long long) / sizeof(block_type);
   115	      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
   116		if (this->_M_w[__i])
   117		  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
   118	      unsigned long long __res = 0ULL;
   119	      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
   120		__res += this->_M_w[__i] << (__i * _S_bits_per_block);
   121	      return __res;
   122	    }
   123	
   124	  template<typename _WordT, typename _Alloc>
   125	    size_t
   126	    __dynamic_bitset_base<_WordT, _Alloc>
   127	    ::_M_do_find_first(size_t __not_found) const
   128	    {
   129	      for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
   130		{
   131		  _WordT __thisword = this->_M_w[__i];
   132		  if (__thisword != static_cast<_WordT>(0))
   133		    return (__i * _S_bits_per_block
   134			    + __builtin_ctzll(__thisword));
   135		}
   136	      // not found, so return an indication of failure.
   137	      return __not_found;
   138	    }
   139	
   140	  template<typename _WordT, typename _Alloc>
   141	    size_t
   142	    __dynamic_bitset_base<_WordT, _Alloc>
   143	    ::_M_do_find_next(size_t __prev, size_t __not_found) const
   144	    {
   145	      // make bound inclusive
   146	      ++__prev;
   147	
   148	      // check out of bounds
   149	      if (__prev >= this->_M_w.size() * _S_bits_per_block)
   150		return __not_found;
   151	
   152	      // search first word
   153	      size_t __i = _S_whichword(__prev);
   154	      _WordT __thisword = this->_M_w[__i];
   155	
   156	      // mask off bits below bound
   157	      __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
   158	
   159	      if (__thisword != static_cast<_WordT>(0))
   160		return (__i * _S_bits_per_block
   161			+ __builtin_ctzll(__thisword));
   162	
   163	      // check subsequent words
   164	      for (++__i; __i < this->_M_w.size(); ++__i)
   165		{
   166		  __thisword = this->_M_w[__i];
   167		  if (__thisword != static_cast<_WordT>(0))
   168		    return (__i * _S_bits_per_block
   169			    + __builtin_ctzll(__thisword));
   170		}
   171	      // not found, so return an indication of failure.
   172	      return __not_found;
   173	    } // end _M_do_find_next
   174	
   175	  // Definitions of non-inline member functions.
   176	  template<typename _WordT, typename _Alloc>
   177	    template<typename _Traits, typename _CharT>
   178	      void
   179	      dynamic_bitset<_WordT, _Alloc>::
   180	      _M_copy_from_ptr(const _CharT* __str, size_t __len,
   181			       size_t __pos, size_t __n, _CharT __zero, _CharT __one)
   182	      {
   183		reset();
   184		const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
   185		for (size_t __i = __nbits; __i > 0; --__i)
   186		  {
   187		    const _CharT __c = __str[__pos + __nbits - __i];
   188		    if (_Traits::eq(__c, __zero))
   189		      ;
   190		    else if (_Traits::eq(__c, __one))
   191		      _M_unchecked_set(__i - 1);
   192		    else
   193		      __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
   194		  }
   195	      }
   196	
   197	  /**
   198	   *  @brief Stream input operator for dynamic_bitset.
   199	   *  @ingroup dynamic_bitset
   200	   *
   201	   *  Input will skip whitespace and only accept '0' and '1' characters.
   202	   *  The %dynamic_bitset will grow as necessary to hold the string of bits.
   203	   */
   204	  template<typename _CharT, typename _Traits,
   205		   typename _WordT, typename _Alloc>
   206	    std::basic_istream<_CharT, _Traits>&
   207	    operator>>(std::basic_istream<_CharT, _Traits>& __is,
   208		       dynamic_bitset<_WordT, _Alloc>& __x)
   209	    {
   210	      typedef typename _Traits::char_type          char_type;
   211	      typedef std::basic_istream<_CharT, _Traits>  __istream_type;
   212	      typedef typename __istream_type::ios_base    __ios_base;
   213	
   214	      std::basic_string<_CharT, _Traits> __tmp;
   215	      __tmp.reserve(__x.size());
   216	
   217	      const char_type __zero = __is.widen('0');
   218	      const char_type __one = __is.widen('1');
   219	
   220	      typename __ios_base::iostate __state = __ios_base::goodbit;
   221	      typename __istream_type::sentry __sentry(__is);
   222	      if (__sentry)
   223		{
   224		  __try
   225		    {
   226		      while (1)
   227			{
   228			  static typename _Traits::int_type __eof = _Traits::eof();
   229	
   230			  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
   231			  if (_Traits::eq_int_type(__c1, __eof))
   232			    {
   233			      __state |= __ios_base::eofbit;
   234			      break;
   235			    }
   236			  else
   237			    {
   238			      const char_type __c2 = _Traits::to_char_type(__c1);
   239			      if (_Traits::eq(__c2, __zero))
   240				__tmp.push_back(__zero);
   241			      else if (_Traits::eq(__c2, __one))
   242				__tmp.push_back(__one);
   243			      else if (_Traits::
   244				       eq_int_type(__is.rdbuf()->sputbackc(__c2),
   245						   __eof))
   246				{
   247				  __state |= __ios_base::failbit;
   248				  break;
   249				}
   250			      else
   251				break;
   252			    }
   253			}
   254		    }
   255		  __catch(__cxxabiv1::__forced_unwind&)
   256		    {
   257		      __is._M_setstate(__ios_base::badbit);
   258		      __throw_exception_again;
   259		    }
   260		  __catch(...)
   261		    { __is._M_setstate(__ios_base::badbit); }
   262		}
   263	
   264	      __x.resize(__tmp.size());
   265	
   266	      if (__tmp.empty() && __x.size())
   267		__state |= __ios_base::failbit;
   268	      else
   269		__x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
   270					__zero, __one);
   271	      if (__state)
   272		__is.setstate(__state);
   273	      return __is;
   274	    }
   275	} // tr2
   276	
   277	_GLIBCXX_END_NAMESPACE_VERSION
   278	} // std
   279	
   280	#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */