libstdc++
|
00001 // TR2 <dynamic_bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2009-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file tr2/dynamic_bitset.tcc 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{tr2/dynamic_bitset} 00028 */ 00029 00030 #ifndef _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 00031 #define _GLIBCXX_TR2_DYNAMIC_BITSET_TCC 1 00032 00033 #pragma GCC system_header 00034 00035 namespace std _GLIBCXX_VISIBILITY(default) 00036 { 00037 namespace tr2 00038 { 00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00040 00041 // Definitions of non-inline functions from __dynamic_bitset_base. 00042 template<typename _WordT, typename _Alloc> 00043 void 00044 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_left_shift(size_t __shift) 00045 { 00046 if (__builtin_expect(__shift != 0, 1)) 00047 { 00048 const size_t __wshift = __shift / _S_bits_per_block; 00049 const size_t __offset = __shift % _S_bits_per_block; 00050 00051 if (__offset == 0) 00052 for (size_t __n = this->_M_w.size() - 1; __n >= __wshift; --__n) 00053 this->_M_w[__n] = this->_M_w[__n - __wshift]; 00054 else 00055 { 00056 const size_t __sub_offset = _S_bits_per_block - __offset; 00057 for (size_t __n = _M_w.size() - 1; __n > __wshift; --__n) 00058 this->_M_w[__n] = ((this->_M_w[__n - __wshift] << __offset) 00059 | (this->_M_w[__n - __wshift - 1] >> __sub_offset)); 00060 this->_M_w[__wshift] = this->_M_w[0] << __offset; 00061 } 00062 00063 //// std::fill(this->_M_w.begin(), this->_M_w.begin() + __wshift, 00064 //// static_cast<_WordT>(0)); 00065 } 00066 } 00067 00068 template<typename _WordT, typename _Alloc> 00069 void 00070 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_right_shift(size_t __shift) 00071 { 00072 if (__builtin_expect(__shift != 0, 1)) 00073 { 00074 const size_t __wshift = __shift / _S_bits_per_block; 00075 const size_t __offset = __shift % _S_bits_per_block; 00076 const size_t __limit = this->_M_w.size() - __wshift - 1; 00077 00078 if (__offset == 0) 00079 for (size_t __n = 0; __n <= __limit; ++__n) 00080 this->_M_w[__n] = this->_M_w[__n + __wshift]; 00081 else 00082 { 00083 const size_t __sub_offset = (_S_bits_per_block 00084 - __offset); 00085 for (size_t __n = 0; __n < __limit; ++__n) 00086 this->_M_w[__n] = ((this->_M_w[__n + __wshift] >> __offset) 00087 | (this->_M_w[__n + __wshift + 1] << __sub_offset)); 00088 this->_M_w[__limit] = this->_M_w[_M_w.size()-1] >> __offset; 00089 } 00090 00091 ////std::fill(this->_M_w.begin() + __limit + 1, this->_M_w.end(), 00092 //// static_cast<_WordT>(0)); 00093 } 00094 } 00095 00096 template<typename _WordT, typename _Alloc> 00097 unsigned long 00098 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ulong() const 00099 { 00100 size_t __n = sizeof(unsigned long) / sizeof(block_type); 00101 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00102 if (this->_M_w[__i]) 00103 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ulong")); 00104 unsigned long __res = 0UL; 00105 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00106 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00107 return __res; 00108 } 00109 00110 template<typename _WordT, typename _Alloc> 00111 unsigned long long 00112 __dynamic_bitset_base<_WordT, _Alloc>::_M_do_to_ullong() const 00113 { 00114 size_t __n = sizeof(unsigned long long) / sizeof(block_type); 00115 for (size_t __i = __n; __i < this->_M_w.size(); ++__i) 00116 if (this->_M_w[__i]) 00117 __throw_overflow_error(__N("__dynamic_bitset_base::_M_do_to_ullong")); 00118 unsigned long long __res = 0ULL; 00119 for (size_t __i = 0; __i < __n && __i < this->_M_w.size(); ++__i) 00120 __res += this->_M_w[__i] << (__i * _S_bits_per_block); 00121 return __res; 00122 } 00123 00124 template<typename _WordT, typename _Alloc> 00125 size_t 00126 __dynamic_bitset_base<_WordT, _Alloc> 00127 ::_M_do_find_first(size_t __not_found) const 00128 { 00129 for (size_t __i = 0; __i < this->_M_w.size(); ++__i) 00130 { 00131 _WordT __thisword = this->_M_w[__i]; 00132 if (__thisword != static_cast<_WordT>(0)) 00133 return (__i * _S_bits_per_block 00134 + __builtin_ctzll(__thisword)); 00135 } 00136 // not found, so return an indication of failure. 00137 return __not_found; 00138 } 00139 00140 template<typename _WordT, typename _Alloc> 00141 size_t 00142 __dynamic_bitset_base<_WordT, _Alloc> 00143 ::_M_do_find_next(size_t __prev, size_t __not_found) const 00144 { 00145 // make bound inclusive 00146 ++__prev; 00147 00148 // check out of bounds 00149 if (__prev >= this->_M_w.size() * _S_bits_per_block) 00150 return __not_found; 00151 00152 // search first word 00153 size_t __i = _S_whichword(__prev); 00154 _WordT __thisword = this->_M_w[__i]; 00155 00156 // mask off bits below bound 00157 __thisword &= (~static_cast<_WordT>(0)) << _S_whichbit(__prev); 00158 00159 if (__thisword != static_cast<_WordT>(0)) 00160 return (__i * _S_bits_per_block 00161 + __builtin_ctzll(__thisword)); 00162 00163 // check subsequent words 00164 for (++__i; __i < this->_M_w.size(); ++__i) 00165 { 00166 __thisword = this->_M_w[__i]; 00167 if (__thisword != static_cast<_WordT>(0)) 00168 return (__i * _S_bits_per_block 00169 + __builtin_ctzll(__thisword)); 00170 } 00171 // not found, so return an indication of failure. 00172 return __not_found; 00173 } // end _M_do_find_next 00174 00175 // Definitions of non-inline member functions. 00176 template<typename _WordT, typename _Alloc> 00177 template<typename _CharT, typename _Traits> 00178 void 00179 dynamic_bitset<_WordT, _Alloc>:: 00180 _M_copy_from_ptr(const _CharT* __str, size_t __len, 00181 size_t __pos, size_t __n, _CharT __zero, _CharT __one) 00182 { 00183 reset(); 00184 const size_t __nbits = std::min(_M_Nb, std::min(__n, __len - __pos)); 00185 for (size_t __i = __nbits; __i > 0; --__i) 00186 { 00187 const _CharT __c = __str[__pos + __nbits - __i]; 00188 if (_Traits::eq(__c, __zero)) 00189 ; 00190 else if (_Traits::eq(__c, __one)) 00191 _M_unchecked_set(__i - 1); 00192 else 00193 __throw_invalid_argument(__N("dynamic_bitset::_M_copy_from_ptr")); 00194 } 00195 } 00196 00197 /** 00198 * @brief Stream input operator for dynamic_bitset. 00199 * @ingroup dynamic_bitset 00200 * 00201 * Input will skip whitespace and only accept '0' and '1' characters. 00202 * The %dynamic_bitset will grow as necessary to hold the string of bits. 00203 */ 00204 template<typename _CharT, typename _Traits, 00205 typename _WordT, typename _Alloc> 00206 std::basic_istream<_CharT, _Traits>& 00207 operator>>(std::basic_istream<_CharT, _Traits>& __is, 00208 dynamic_bitset<_WordT, _Alloc>& __x) 00209 { 00210 typedef typename _Traits::char_type char_type; 00211 typedef std::basic_istream<_CharT, _Traits> __istream_type; 00212 typedef typename __istream_type::ios_base __ios_base; 00213 00214 std::basic_string<_CharT, _Traits> __tmp; 00215 __tmp.reserve(__x.size()); 00216 00217 const char_type __zero = __is.widen('0'); 00218 const char_type __one = __is.widen('1'); 00219 00220 typename __ios_base::iostate __state = __ios_base::goodbit; 00221 typename __istream_type::sentry __sentry(__is); 00222 if (__sentry) 00223 { 00224 __try 00225 { 00226 while (1) 00227 { 00228 static typename _Traits::int_type __eof = _Traits::eof(); 00229 00230 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 00231 if (_Traits::eq_int_type(__c1, __eof)) 00232 { 00233 __state |= __ios_base::eofbit; 00234 break; 00235 } 00236 else 00237 { 00238 const char_type __c2 = _Traits::to_char_type(__c1); 00239 if (_Traits::eq(__c2, __zero)) 00240 __tmp.push_back(__zero); 00241 else if (_Traits::eq(__c2, __one)) 00242 __tmp.push_back(__one); 00243 else if (_Traits:: 00244 eq_int_type(__is.rdbuf()->sputbackc(__c2), 00245 __eof)) 00246 { 00247 __state |= __ios_base::failbit; 00248 break; 00249 } 00250 else 00251 break; 00252 } 00253 } 00254 } 00255 __catch(__cxxabiv1::__forced_unwind&) 00256 { 00257 __is._M_setstate(__ios_base::badbit); 00258 __throw_exception_again; 00259 } 00260 __catch(...) 00261 { __is._M_setstate(__ios_base::badbit); } 00262 } 00263 00264 __x.resize(__tmp.size()); 00265 00266 if (__tmp.empty() && __x.size()) 00267 __state |= __ios_base::failbit; 00268 else 00269 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(), 00270 __zero, __one); 00271 if (__state) 00272 __is.setstate(__state); 00273 return __is; 00274 } 00275 00276 _GLIBCXX_END_NAMESPACE_VERSION 00277 } // tr2 00278 } // std 00279 00280 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */