libstdc++
dynamic_bitset.tcc
Go to the documentation of this file.
1// TR2 <dynamic_bitset> -*- C++ -*-
2
3// Copyright (C) 2009-2021 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
35namespace std _GLIBCXX_VISIBILITY(default)
36{
37_GLIBCXX_BEGIN_NAMESPACE_VERSION
38
39namespace 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(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 _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>
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
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 }
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 */
constexpr const _Tp & min(const _Tp &, const _Tp &)
This does what you think it does.
Definition: stl_algobase.h:230
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.
void setstate(iostate __state)
Sets additional flags in the error state.
Definition: basic_ios.h:157
char_type widen(char __c) const
Widens characters.
Definition: basic_ios.h:449
basic_streambuf< _CharT, _Traits > * rdbuf() const
Accessing the underlying buffer.
Definition: basic_ios.h:321
Template class basic_istream.
Definition: istream:59
Managing sequences of characters and character-like objects.
void push_back(_CharT __c)
Append a single character.
void reserve(size_type __res_arg)
Attempt to preallocate enough memory for specified number of characters.
size_type size() const noexcept
Returns the number of characters in the string, not including any null-termination.
bool empty() const noexcept
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:997