libstdc++
|
00001 // TR2 <dynamic_bitset> -*- C++ -*- 00002 00003 // Copyright (C) 2009-2014 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 * @defgroup Global I/O operators for bitsets. 00199 * @{ 00200 * @brief Global I/O operators for bitsets. 00201 * 00202 * Direct I/O between streams and bitsets is supported. Output is 00203 * straightforward. Input will skip whitespace and only accept '0' 00204 * and '1' characters. The %dynamic_bitset will grow as necessary 00205 * to hold the string of bits. 00206 */ 00207 template<typename _CharT, typename _Traits, 00208 typename _WordT, typename _Alloc> 00209 std::basic_istream<_CharT, _Traits>& 00210 operator>>(std::basic_istream<_CharT, _Traits>& __is, 00211 dynamic_bitset<_WordT, _Alloc>& __x) 00212 { 00213 typedef typename _Traits::char_type char_type; 00214 typedef std::basic_istream<_CharT, _Traits> __istream_type; 00215 typedef typename __istream_type::ios_base __ios_base; 00216 00217 std::basic_string<_CharT, _Traits> __tmp; 00218 __tmp.reserve(__x.size()); 00219 00220 const char_type __zero = __is.widen('0'); 00221 const char_type __one = __is.widen('1'); 00222 00223 typename __ios_base::iostate __state = __ios_base::goodbit; 00224 typename __istream_type::sentry __sentry(__is); 00225 if (__sentry) 00226 { 00227 __try 00228 { 00229 while (1) 00230 { 00231 static typename _Traits::int_type __eof = _Traits::eof(); 00232 00233 typename _Traits::int_type __c1 = __is.rdbuf()->sbumpc(); 00234 if (_Traits::eq_int_type(__c1, __eof)) 00235 { 00236 __state |= __ios_base::eofbit; 00237 break; 00238 } 00239 else 00240 { 00241 const char_type __c2 = _Traits::to_char_type(__c1); 00242 if (_Traits::eq(__c2, __zero)) 00243 __tmp.push_back(__zero); 00244 else if (_Traits::eq(__c2, __one)) 00245 __tmp.push_back(__one); 00246 else if (_Traits:: 00247 eq_int_type(__is.rdbuf()->sputbackc(__c2), 00248 __eof)) 00249 { 00250 __state |= __ios_base::failbit; 00251 break; 00252 } 00253 else 00254 break; 00255 } 00256 } 00257 } 00258 __catch(__cxxabiv1::__forced_unwind&) 00259 { 00260 __is._M_setstate(__ios_base::badbit); 00261 __throw_exception_again; 00262 } 00263 __catch(...) 00264 { __is._M_setstate(__ios_base::badbit); } 00265 } 00266 00267 __x.resize(__tmp.size()); 00268 00269 if (__tmp.empty() && __x.size()) 00270 __state |= __ios_base::failbit; 00271 else 00272 __x._M_copy_from_string(__tmp, static_cast<size_t>(0), __x.size(), 00273 __zero, __one); 00274 if (__state) 00275 __is.setstate(__state); 00276 return __is; 00277 } 00278 /** 00279 * @} 00280 */ 00281 00282 _GLIBCXX_END_NAMESPACE_VERSION 00283 } // tr2 00284 } // std 00285 00286 #endif /* _GLIBCXX_TR2_DYNAMIC_BITSET_TCC */