libstdc++
dynamic_bitset.tcc
1 // TR2 <dynamic_bitset> -*- C++ -*-
2 
3 // Copyright (C) 2009-2014 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  * @defgroup Global I/O operators for bitsets.
199  * @{
200  * @brief Global I/O operators for bitsets.
201  *
202  * Direct I/O between streams and bitsets is supported. Output is
203  * straightforward. Input will skip whitespace and only accept '0'
204  * and '1' characters. The %dynamic_bitset will grow as necessary
205  * to hold the string of bits.
206  */
207  template<typename _CharT, typename _Traits,
208  typename _WordT, typename _Alloc>
209  std::basic_istream<_CharT, _Traits>&
210  operator>>(std::basic_istream<_CharT, _Traits>& __is,
211  dynamic_bitset<_WordT, _Alloc>& __x)
212  {
213  typedef typename _Traits::char_type char_type;
214  typedef std::basic_istream<_CharT, _Traits> __istream_type;
215  typedef typename __istream_type::ios_base __ios_base;
216 
217  std::basic_string<_CharT, _Traits> __tmp;
218  __tmp.reserve(__x.size());
219 
220  const char_type __zero = __is.widen('0');
221  const char_type __one = __is.widen('1');
222 
223  typename __ios_base::iostate __state = __ios_base::goodbit;
224  typename __istream_type::sentry __sentry(__is);
225  if (__sentry)
226  {
227  __try
228  {
229  while (1)
230  {
231  static typename _Traits::int_type __eof = _Traits::eof();
232 
233  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
234  if (_Traits::eq_int_type(__c1, __eof))
235  {
236  __state |= __ios_base::eofbit;
237  break;
238  }
239  else
240  {
241  const char_type __c2 = _Traits::to_char_type(__c1);
242  if (_Traits::eq(__c2, __zero))
243  __tmp.push_back(__zero);
244  else if (_Traits::eq(__c2, __one))
245  __tmp.push_back(__one);
246  else if (_Traits::
247  eq_int_type(__is.rdbuf()->sputbackc(__c2),
248  __eof))
249  {
250  __state |= __ios_base::failbit;
251  break;
252  }
253  else
254  break;
255  }
256  }
257  }
258  __catch(__cxxabiv1::__forced_unwind&)
259  {
260  __is._M_setstate(__ios_base::badbit);
261  __throw_exception_again;
262  }
263  __catch(...)
264  { __is._M_setstate(__ios_base::badbit); }
265  }
266 
267  __x.resize(__tmp.size());
268 
269  if (__tmp.empty() && __x.size())
270  __state |= __ios_base::failbit;
271  else
272  __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
273  __zero, __one);
274  if (__state)
275  __is.setstate(__state);
276  return __is;
277  }
278  /**
279  * @}
280  */
281 
282 _GLIBCXX_END_NAMESPACE_VERSION
283 } // tr2
284 } // std
285 
286 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */