| 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 |
|
| 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(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> |
| 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 |
} // tr2 |
| 276 |
|
| 277 |
_GLIBCXX_END_NAMESPACE_VERSION |
| 278 |
} // std |
| 279 |
|
| 280 |
#endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */ |
