1 // TR2 <dynamic_bitset> -*- C++ -*-
2 
3 // Copyright (C) 2009-2017 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 #pragma GCC system_header
34 
35 namespace std _GLIBCXX_VISIBILITY(default)
36 {
37 namespace tr2
38 {
39 _GLIBCXX_BEGIN_NAMESPACE_VERSION
40 
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
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 _CharT, typename _Traits>
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 
276 _GLIBCXX_END_NAMESPACE_VERSION
277 } // tr2
278 } // std
279 
280 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */
281