libstdc++
dynamic_bitset.tcc
Go to the documentation of this file.
1 // TR2 <dynamic_bitset> -*- C++ -*-
2 
3 // Copyright (C) 2009-2024 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 _GLIBCXX_BEGIN_NAMESPACE_VERSION
38 
39 namespace tr2
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_n(this->_M_w.begin(), __wshift, _WordT(0));
64  }
65  }
66 
67  template<typename _WordT, typename _Alloc>
68  void
69  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift)
70  {
71  if (__builtin_expect(__shift != 0, 1))
72  {
73  const size_t __wshift = __shift / _S_bits_per_block;
74  const size_t __offset = __shift % _S_bits_per_block;
75  const size_t __limit = this->_M_w.size() - __wshift - 1;
76 
77  if (__offset == 0)
78  for (size_t __n = 0; __n <= __limit; ++__n)
79  this->_M_w[__n] = this->_M_w[__n + __wshift];
80  else
81  {
82  const size_t __sub_offset = (_S_bits_per_block
83  - __offset);
84  for (size_t __n = 0; __n < __limit; ++__n)
85  this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset)
86  | (this->_M_w[__n + __wshift + 1] << __sub_offset));
87  this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset;
88  }
89 
90  std::fill_n(this->_M_w.end() - __wshift, __wshift, _WordT(0));
91  }
92  }
93 
94  template<typename _WordT, typename _Alloc>
95  unsigned long
96  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const
97  {
98  size_t __n = sizeof(unsigned long) / sizeof(block_type);
99  for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
100  if (this->_M_w[__i])
101  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong"));
102  unsigned long __res = 0UL;
103  for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
104  __res += this->_M_w[__i] << (__i * _S_bits_per_block);
105  return __res;
106  }
107 
108  template<typename _WordT, typename _Alloc>
109  unsigned long long
110  __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const
111  {
112  size_t __n = sizeof(unsigned long long) / sizeof(block_type);
113  for (size_t __i = __n; __i < this->_M_w.size(); ++__i)
114  if (this->_M_w[__i])
115  __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong"));
116  unsigned long long __res = 0ULL;
117  for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i)
118  __res += this->_M_w[__i] << (__i * _S_bits_per_block);
119  return __res;
120  }
121 
122  template<typename _WordT, typename _Alloc>
123  size_t
124  __dynamic_bitset_base<_WordT, _Alloc>
125  ::_M_do_find_first(size_t __not_found) const
126  {
127  for (size_t __i = 0; __i < this->_M_w.size(); ++__i)
128  {
129  _WordT __thisword = this->_M_w[__i];
130  if (__thisword != static_cast<_WordT>(0))
131  return (__i * _S_bits_per_block
132  + __builtin_ctzll(__thisword));
133  }
134  // not found, so return an indication of failure.
135  return __not_found;
136  }
137 
138  template<typename _WordT, typename _Alloc>
139  size_t
140  __dynamic_bitset_base<_WordT, _Alloc>
141  ::_M_do_find_next(size_t __prev, size_t __not_found) const
142  {
143  // make bound inclusive
144  ++__prev;
145 
146  // check out of bounds
147  if (__prev >= this->_M_w.size() * _S_bits_per_block)
148  return __not_found;
149 
150  // search first word
151  size_t __i = _S_whichword(__prev);
152  _WordT __thisword = this->_M_w[__i];
153 
154  // mask off bits below bound
155  __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev);
156 
157  if (__thisword != static_cast<_WordT>(0))
158  return (__i * _S_bits_per_block
159  + __builtin_ctzll(__thisword));
160 
161  // check subsequent words
162  for (++__i; __i < this->_M_w.size(); ++__i)
163  {
164  __thisword = this->_M_w[__i];
165  if (__thisword != static_cast<_WordT>(0))
166  return (__i * _S_bits_per_block
167  + __builtin_ctzll(__thisword));
168  }
169  // not found, so return an indication of failure.
170  return __not_found;
171  } // end _M_do_find_next
172 
173  // Definitions of non-inline member functions.
174  template<typename _WordT, typename _Alloc>
175  template<typename _Traits, typename _CharT>
176  void
177  dynamic_bitset<_WordT, _Alloc>::
178  _M_copy_from_ptr(const _CharT* __str, size_t __len,
179  size_t __pos, size_t __n, _CharT __zero, _CharT __one)
180  {
181  reset();
182  const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos));
183  for (size_t __i = __nbits; __i > 0; --__i)
184  {
185  const _CharT __c = __str[__pos + __nbits - __i];
186  if (_Traits::eq(__c, __zero))
187  ;
188  else if (_Traits::eq(__c, __one))
189  _M_unchecked_set(__i - 1);
190  else
191  __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr"));
192  }
193  }
194 
195  /**
196  * @brief Stream input operator for dynamic_bitset.
197  * @ingroup dynamic_bitset
198  *
199  * Input will skip whitespace and only accept '0' and '1' characters.
200  * The %dynamic_bitset will grow as necessary to hold the string of bits.
201  */
202  template<typename _CharT, typename _Traits,
203  typename _WordT, typename _Alloc>
207  {
208  typedef typename _Traits::char_type char_type;
209  typedef std::basic_istream<_CharT, _Traits> __istream_type;
210  typedef typename __istream_type::ios_base __ios_base;
211 
213  __tmp.reserve(__x.size());
214 
215  const char_type __zero = __is.widen('0');
216  const char_type __one = __is.widen('1');
217 
218  typename __ios_base::iostate __state = __ios_base::goodbit;
219  typename __istream_type::sentry __sentry(__is);
220  if (__sentry)
221  {
222  __try
223  {
224  while (1)
225  {
226  static typename _Traits::int_type __eof = _Traits::eof();
227 
228  typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc();
229  if (_Traits::eq_int_type(__c1, __eof))
230  {
231  __state |= __ios_base::eofbit;
232  break;
233  }
234  else
235  {
236  const char_type __c2 = _Traits::to_char_type(__c1);
237  if (_Traits::eq(__c2, __zero))
238  __tmp.push_back(__zero);
239  else if (_Traits::eq(__c2, __one))
240  __tmp.push_back(__one);
241  else if (_Traits::
242  eq_int_type(__is.rdbuf()->sputbackc(__c2),
243  __eof))
244  {
245  __state |= __ios_base::failbit;
246  break;
247  }
248  else
249  break;
250  }
251  }
252  }
254  {
255  __is._M_setstate(__ios_base::badbit);
256  __throw_exception_again;
257  }
258  __catch(...)
259  { __is._M_setstate(__ios_base::badbit); }
260  }
261 
262  __x.resize(__tmp.size());
263 
264  if (__tmp.empty() && __x.size())
265  __state |= __ios_base::failbit;
266  else
267  __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(),
268  __zero, __one);
269  if (__state)
270  __is.setstate(__state);
271  return __is;
272  }
273 } // tr2
274 
275 _GLIBCXX_END_NAMESPACE_VERSION
276 } // std
277 
278 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:233
std::basic_istream< _CharT, _Traits > & operator>>(std::basic_istream< _CharT, _Traits > &__is, dynamic_bitset< _WordT, _Alloc > &__x)
Stream input operator for dynamic_bitset.
ISO C++ entities toplevel namespace is std.
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:325
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:161
char_type widen(char __c) const
Widens characters.
Definition: basic_ios.h:453
Template class basic_istream.
Definition: istream:61
Managing sequences of characters and character-like objects.
Definition: cow_string.h:109
void push_back(_CharT __c)
Append a single character.
Definition: cow_string.h:1374
void reserve(size_type __res_arg)
Attempt to preallocate enough memory for specified number of characters.
Definition: cow_string.h:3521
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
Definition: cow_string.h:908
bool empty() const noexcept
Definition: cow_string.h:1069
Thrown as part of forced unwinding.
Definition: cxxabi_forced.h:49
The dynamic_bitset class represents a sequence of bits.
Definition: dynamic_bitset:421
void resize(size_type __nbits, bool __value=false)
Resize the bitset.
Definition: dynamic_bitset:688
size_type size() const noexcept
Returns the total number of bits.
Definition: dynamic_bitset:994