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 */ 287
