[thirdparty/gcc.git] / libstdc++-v3 / include / tr2 / dynamic_bitset.tcc

// TR2 <dynamic_bitset> -*- C++ -*-

// Copyright (C) 2009-2021 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 3, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.

// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
// <http://www.gnu.org/licenses/>.

/** @file tr2/dynamic_bitset.tcc
 *  This is an internal header file, included by other library headers.
 *  Do not attempt to use it directly. @headername{tr2/dynamic_bitset}
 */

#ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC
#define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1

#pragma GCC system_header

namespace std _GLIBCXX_VISIBILITY(default)
{
_GLIBCXX_BEGIN_NAMESPACE_VERSION

namespace tr2
{
  // Definitions of non-inline functions from __dynamic_bitset_base.
  template<typename _WordT, typename _Alloc>
    void
    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
    {
      if (__builtin_expect(__shift != 0, 1))
	{
	  const size_t __wshift = __shift / _S_bits_per_block;
	  const size_t __offset = __shift % _S_bits_per_block;

	  if (__offset == 0)
	    for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
	      this->_M_w[__n] = this->_M_w[__n - __wshift];
	  else
	    {
	      const size_t __sub_offset = _S_bits_per_block - __offset;
	      for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
		this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
			     | (this->_M_w[__n - __wshift - 1] >> __sub_offset));
	      this->_M_w[__wshift] = this->_M_w[0] << __offset;
	    }

	  //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
	  ////          static_cast<_WordT>(0));
	}
    }

  template<typename _WordT, typename _Alloc>
    void
    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
    {
      if (__builtin_expect(__shift != 0, 1))
	{
	  const size_t __wshift = __shift / _S_bits_per_block;
	  const size_t __offset = __shift % _S_bits_per_block;
	  const size_t __limit = this->_M_w.size() - __wshift - 1;

	  if (__offset == 0)
	    for (size_t __n = 0; __n <= __limit; ++__n)
	      this->_M_w[__n] = this->_M_w[__n + __wshift];
	  else
	    {
	      const size_t __sub_offset = (_S_bits_per_block
					   - __offset);
	      for (size_t __n = 0; __n < __limit; ++__n)
		this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
			     | (this->_M_w[__n + __wshift + 1] << __sub_offset));
	      this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
	    }

	  ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
	  ////          static_cast<_WordT>(0));
	}
    }

  template<typename _WordT, typename _Alloc>
    unsigned long
    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
    {
      size_t __n = sizeof(unsigned long) / sizeof(block_type);
      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
	if (this->_M_w[__i])
	  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
      unsigned long __res = 0UL;
      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
	__res += this->_M_w[__i] << (__i * _S_bits_per_block);
      return __res;
    }

  template<typename _WordT, typename _Alloc>
    unsigned long long
    __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
    {
      size_t __n = sizeof(unsigned long long) / sizeof(block_type);
      for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
	if (this->_M_w[__i])
	  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
      unsigned long long __res = 0ULL;
      for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
	__res += this->_M_w[__i] << (__i * _S_bits_per_block);
      return __res;
    }

  template<typename _WordT, typename _Alloc>
    size_t
    __dynamic_bitset_base<_WordT, _Alloc>
    ::_M_do_find_first(size_t __not_found) const
    {
      for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
	{
	  _WordT __thisword = this->_M_w[__i];
	  if (__thisword != static_cast<_WordT>(0))
	    return (__i * _S_bits_per_block
		    + __builtin_ctzll(__thisword));
	}
      // not found, so return an indication of failure.
      return __not_found;
    }

  template<typename _WordT, typename _Alloc>
    size_t
    __dynamic_bitset_base<_WordT, _Alloc>
    ::_M_do_find_next(size_t __prev, size_t __not_found) const
    {
      // make bound inclusive
      ++__prev;

      // check out of bounds
      if (__prev >= this->_M_w.size() * _S_bits_per_block)
	return __not_found;

      // search first word
      size_t __i = _S_whichword(__prev);
      _WordT __thisword = this->_M_w[__i];

      // mask off bits below bound
      __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);

      if (__thisword != static_cast<_WordT>(0))
	return (__i * _S_bits_per_block
		+ __builtin_ctzll(__thisword));

      // check subsequent words
      for (++__i; __i < this->_M_w.size(); ++__i)
	{
	  __thisword = this->_M_w[__i];
	  if (__thisword != static_cast<_WordT>(0))
	    return (__i * _S_bits_per_block
		    + __builtin_ctzll(__thisword));
	}
      // not found, so return an indication of failure.
      return __not_found;
    } // end _M_do_find_next

  // Definitions of non-inline member functions.
  template<typename _WordT, typename _Alloc>
    template<typename _Traits, typename _CharT>
      void
      dynamic_bitset<_WordT, _Alloc>::
      _M_copy_from_ptr(const _CharT* __str, size_t __len,
		       size_t __pos, size_t __n, _CharT __zero, _CharT __one)
      {
	reset();
	const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
	for (size_t __i = __nbits; __i > 0; --__i)
	  {
	    const _CharT __c = __str[__pos + __nbits - __i];
	    if (_Traits::eq(__c, __zero))
	      ;
	    else if (_Traits::eq(__c, __one))
	      _M_unchecked_set(__i - 1);
	    else
	      __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
	  }
      }

  /**
   *  @brief Stream input operator for dynamic_bitset.
   *  @ingroup dynamic_bitset
   *
   *  Input will skip whitespace and only accept '0' and '1' characters.
   *  The %dynamic_bitset will grow as necessary to hold the string of bits.
   */
  template<typename _CharT, typename _Traits,
	   typename _WordT, typename _Alloc>
    std::basic_istream<_CharT, _Traits>&
    operator>>(std::basic_istream<_CharT, _Traits>& __is,
	       dynamic_bitset<_WordT, _Alloc>& __x)
    {
      typedef typename _Traits::char_type          char_type;
      typedef std::basic_istream<_CharT, _Traits>  __istream_type;
      typedef typename __istream_type::ios_base    __ios_base;

      std::basic_string<_CharT, _Traits> __tmp;
      __tmp.reserve(__x.size());

      const char_type __zero = __is.widen('0');
      const char_type __one = __is.widen('1');

      typename __ios_base::iostate __state = __ios_base::goodbit;
      typename __istream_type::sentry __sentry(__is);
      if (__sentry)
	{
	  __try
	    {
	      while (1)
		{
		  static typename _Traits::int_type __eof = _Traits::eof();

		  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
		  if (_Traits::eq_int_type(__c1, __eof))
		    {
		      __state |= __ios_base::eofbit;
		      break;
		    }
		  else
		    {
		      const char_type __c2 = _Traits::to_char_type(__c1);
		      if (_Traits::eq(__c2, __zero))
			__tmp.push_back(__zero);
		      else if (_Traits::eq(__c2, __one))
			__tmp.push_back(__one);
		      else if (_Traits::
			       eq_int_type(__is.rdbuf()->sputbackc(__c2),
					   __eof))
			{
			  __state |= __ios_base::failbit;
			  break;
			}
		      else
			break;
		    }
		}
	    }
	  __catch(__cxxabiv1::__forced_unwind&)
	    {
	      __is._M_setstate(__ios_base::badbit);
	      __throw_exception_again;
	    }
	  __catch(...)
	    { __is._M_setstate(__ios_base::badbit); }
	}

      __x.resize(__tmp.size());

      if (__tmp.empty() && __x.size())
	__state |= __ios_base::failbit;
      else
	__x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
				__zero, __one);
      if (__state)
	__is.setstate(__state);
      return __is;
    }
} // tr2

_GLIBCXX_END_NAMESPACE_VERSION
} // std

#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */
Commit	Line	Data
6b8fe121 ESR	1	// TR2 <dynamic_bitset> -- C++ --
6b8fe121 ESR	2
99dee823	3	// Copyright (C) 2009-2021 Free Software Foundation, Inc.
6b8fe121 ESR	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	#pragma GCC system_header
	34
	35	namespace std _GLIBCXX_VISIBILITY(default)
	36	{
6b8fe121 ESR	37	_GLIBCXX_BEGIN_NAMESPACE_VERSION
6b8fe121 ESR	38
4a15d842 FD	39	namespace tr2
4a15d842 FD	40	{
6b8fe121 ESR	41	// Definitions of non-inline functions from __dynamic_bitset_base.
	42	template<typename _WordT, typename _Alloc>
	43	void
	44	__dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift)
	45	{
	46	if (__builtin_expect(__shift != 0, 1))
	47	{
	48	const size_t __wshift = __shift / _S_bits_per_block;
	49	const size_t __offset = __shift % _S_bits_per_block;
	50
	51	if (__offset == 0)
	52	for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n)
	53	this->_M_w[__n] = this->_M_w[__n - __wshift];
	54	else
	55	{
	56	const size_t __sub_offset = _S_bits_per_block - __offset;
	57	for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n)
	58	this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset)
	59	\| (this->_M_w[__n - __wshift - 1] >> __sub_offset));
	60	this->_M_w[__wshift] = this->_M_w[0] << __offset;
	61	}
	62
	63	//// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift,
	64	//// static_cast<_WordT>(0));
	65	}
	66	}
	67
	68	template<typename _WordT, typename _Alloc>
	69	void
	70	__dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
	71	{
	72	if (__builtin_expect(__shift != 0, 1))
	73	{
	74	const size_t __wshift = __shift / _S_bits_per_block;
	75	const size_t __offset = __shift % _S_bits_per_block;
	76	const size_t __limit = this->_M_w.size() - __wshift - 1;
	77
	78	if (__offset == 0)
	79	for (size_t __n = 0; __n <= __limit; ++__n)
	80	this->_M_w[__n] = this->_M_w[__n + __wshift];
	81	else
	82	{
	83	const size_t __sub_offset = (_S_bits_per_block
	84	- __offset);
	85	for (size_t __n = 0; __n < __limit; ++__n)
	86	this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
	87	\| (this->_M_w[__n + __wshift + 1] << __sub_offset));
	88	this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
	89	}
	90
	91	////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(),
	92	//// static_cast<_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
390dafb7	134	+ __builtin_ctzll(__thisword));
6b8fe121 ESR	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
390dafb7	161	+ __builtin_ctzll(__thisword));
6b8fe121 ESR	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
390dafb7	169	+ __builtin_ctzll(__thisword));
6b8fe121 ESR	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>
07758d90	177	template<typename _Traits, typename _CharT>
6b8fe121 ESR	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	/**
fb3bc977 JW	198	* @brief Stream input operator for dynamic_bitset.
fb3bc977 JW	199	* @ingroup dynamic_bitset
6b8fe121	200	*
fb3bc977 JW	201	* Input will skip whitespace and only accept '0' and '1' characters.
fb3bc977 JW	202	* The %dynamic_bitset will grow as necessary to hold the string of bits.
6b8fe121 ESR	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	}
4a15d842	275	} // tr2
6b8fe121 ESR	276
6b8fe121 ESR	277	_GLIBCXX_END_NAMESPACE_VERSION
6b8fe121 ESR	278	} // std
	279
	280	#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */