libstdc++
|
00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997-2018 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 bits/basic_string.tcc 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{string} 00028 */ 00029 00030 // 00031 // ISO C++ 14882: 21 Strings library 00032 // 00033 00034 // Written by Jason Merrill based upon the specification by Takanori Adachi 00035 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 00036 // Non-reference-counted implementation written by Paolo Carlini and 00037 // updated by Jonathan Wakely for ISO-14882-2011. 00038 00039 #ifndef _BASIC_STRING_TCC 00040 #define _BASIC_STRING_TCC 1 00041 00042 #pragma GCC system_header 00043 00044 #include <bits/cxxabi_forced.h> 00045 00046 namespace std _GLIBCXX_VISIBILITY(default) 00047 { 00048 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00049 00050 #if _GLIBCXX_USE_CXX11_ABI 00051 00052 template<typename _CharT, typename _Traits, typename _Alloc> 00053 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00054 basic_string<_CharT, _Traits, _Alloc>::npos; 00055 00056 template<typename _CharT, typename _Traits, typename _Alloc> 00057 void 00058 basic_string<_CharT, _Traits, _Alloc>:: 00059 swap(basic_string& __s) _GLIBCXX_NOEXCEPT 00060 { 00061 if (this == &__s) 00062 return; 00063 00064 _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator()); 00065 00066 if (_M_is_local()) 00067 if (__s._M_is_local()) 00068 { 00069 if (length() && __s.length()) 00070 { 00071 _CharT __tmp_data[_S_local_capacity + 1]; 00072 traits_type::copy(__tmp_data, __s._M_local_buf, 00073 _S_local_capacity + 1); 00074 traits_type::copy(__s._M_local_buf, _M_local_buf, 00075 _S_local_capacity + 1); 00076 traits_type::copy(_M_local_buf, __tmp_data, 00077 _S_local_capacity + 1); 00078 } 00079 else if (__s.length()) 00080 { 00081 traits_type::copy(_M_local_buf, __s._M_local_buf, 00082 _S_local_capacity + 1); 00083 _M_length(__s.length()); 00084 __s._M_set_length(0); 00085 return; 00086 } 00087 else if (length()) 00088 { 00089 traits_type::copy(__s._M_local_buf, _M_local_buf, 00090 _S_local_capacity + 1); 00091 __s._M_length(length()); 00092 _M_set_length(0); 00093 return; 00094 } 00095 } 00096 else 00097 { 00098 const size_type __tmp_capacity = __s._M_allocated_capacity; 00099 traits_type::copy(__s._M_local_buf, _M_local_buf, 00100 _S_local_capacity + 1); 00101 _M_data(__s._M_data()); 00102 __s._M_data(__s._M_local_buf); 00103 _M_capacity(__tmp_capacity); 00104 } 00105 else 00106 { 00107 const size_type __tmp_capacity = _M_allocated_capacity; 00108 if (__s._M_is_local()) 00109 { 00110 traits_type::copy(_M_local_buf, __s._M_local_buf, 00111 _S_local_capacity + 1); 00112 __s._M_data(_M_data()); 00113 _M_data(_M_local_buf); 00114 } 00115 else 00116 { 00117 pointer __tmp_ptr = _M_data(); 00118 _M_data(__s._M_data()); 00119 __s._M_data(__tmp_ptr); 00120 _M_capacity(__s._M_allocated_capacity); 00121 } 00122 __s._M_capacity(__tmp_capacity); 00123 } 00124 00125 const size_type __tmp_length = length(); 00126 _M_length(__s.length()); 00127 __s._M_length(__tmp_length); 00128 } 00129 00130 template<typename _CharT, typename _Traits, typename _Alloc> 00131 typename basic_string<_CharT, _Traits, _Alloc>::pointer 00132 basic_string<_CharT, _Traits, _Alloc>:: 00133 _M_create(size_type& __capacity, size_type __old_capacity) 00134 { 00135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00136 // 83. String::npos vs. string::max_size() 00137 if (__capacity > max_size()) 00138 std::__throw_length_error(__N("basic_string::_M_create")); 00139 00140 // The below implements an exponential growth policy, necessary to 00141 // meet amortized linear time requirements of the library: see 00142 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00143 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 00144 { 00145 __capacity = 2 * __old_capacity; 00146 // Never allocate a string bigger than max_size. 00147 if (__capacity > max_size()) 00148 __capacity = max_size(); 00149 } 00150 00151 // NB: Need an array of char_type[__capacity], plus a terminating 00152 // null char_type() element. 00153 return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1); 00154 } 00155 00156 // NB: This is the special case for Input Iterators, used in 00157 // istreambuf_iterators, etc. 00158 // Input Iterators have a cost structure very different from 00159 // pointers, calling for a different coding style. 00160 template<typename _CharT, typename _Traits, typename _Alloc> 00161 template<typename _InIterator> 00162 void 00163 basic_string<_CharT, _Traits, _Alloc>:: 00164 _M_construct(_InIterator __beg, _InIterator __end, 00165 std::input_iterator_tag) 00166 { 00167 size_type __len = 0; 00168 size_type __capacity = size_type(_S_local_capacity); 00169 00170 while (__beg != __end && __len < __capacity) 00171 { 00172 _M_data()[__len++] = *__beg; 00173 ++__beg; 00174 } 00175 00176 __try 00177 { 00178 while (__beg != __end) 00179 { 00180 if (__len == __capacity) 00181 { 00182 // Allocate more space. 00183 __capacity = __len + 1; 00184 pointer __another = _M_create(__capacity, __len); 00185 this->_S_copy(__another, _M_data(), __len); 00186 _M_dispose(); 00187 _M_data(__another); 00188 _M_capacity(__capacity); 00189 } 00190 _M_data()[__len++] = *__beg; 00191 ++__beg; 00192 } 00193 } 00194 __catch(...) 00195 { 00196 _M_dispose(); 00197 __throw_exception_again; 00198 } 00199 00200 _M_set_length(__len); 00201 } 00202 00203 template<typename _CharT, typename _Traits, typename _Alloc> 00204 template<typename _InIterator> 00205 void 00206 basic_string<_CharT, _Traits, _Alloc>:: 00207 _M_construct(_InIterator __beg, _InIterator __end, 00208 std::forward_iterator_tag) 00209 { 00210 // NB: Not required, but considered best practice. 00211 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 00212 std::__throw_logic_error(__N("basic_string::" 00213 "_M_construct null not valid")); 00214 00215 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 00216 00217 if (__dnew > size_type(_S_local_capacity)) 00218 { 00219 _M_data(_M_create(__dnew, size_type(0))); 00220 _M_capacity(__dnew); 00221 } 00222 00223 // Check for out_of_range and length_error exceptions. 00224 __try 00225 { this->_S_copy_chars(_M_data(), __beg, __end); } 00226 __catch(...) 00227 { 00228 _M_dispose(); 00229 __throw_exception_again; 00230 } 00231 00232 _M_set_length(__dnew); 00233 } 00234 00235 template<typename _CharT, typename _Traits, typename _Alloc> 00236 void 00237 basic_string<_CharT, _Traits, _Alloc>:: 00238 _M_construct(size_type __n, _CharT __c) 00239 { 00240 if (__n > size_type(_S_local_capacity)) 00241 { 00242 _M_data(_M_create(__n, size_type(0))); 00243 _M_capacity(__n); 00244 } 00245 00246 if (__n) 00247 this->_S_assign(_M_data(), __n, __c); 00248 00249 _M_set_length(__n); 00250 } 00251 00252 template<typename _CharT, typename _Traits, typename _Alloc> 00253 void 00254 basic_string<_CharT, _Traits, _Alloc>:: 00255 _M_assign(const basic_string& __str) 00256 { 00257 if (this != &__str) 00258 { 00259 const size_type __rsize = __str.length(); 00260 const size_type __capacity = capacity(); 00261 00262 if (__rsize > __capacity) 00263 { 00264 size_type __new_capacity = __rsize; 00265 pointer __tmp = _M_create(__new_capacity, __capacity); 00266 _M_dispose(); 00267 _M_data(__tmp); 00268 _M_capacity(__new_capacity); 00269 } 00270 00271 if (__rsize) 00272 this->_S_copy(_M_data(), __str._M_data(), __rsize); 00273 00274 _M_set_length(__rsize); 00275 } 00276 } 00277 00278 template<typename _CharT, typename _Traits, typename _Alloc> 00279 void 00280 basic_string<_CharT, _Traits, _Alloc>:: 00281 reserve(size_type __res) 00282 { 00283 // Make sure we don't shrink below the current size. 00284 if (__res < length()) 00285 __res = length(); 00286 00287 const size_type __capacity = capacity(); 00288 if (__res != __capacity) 00289 { 00290 if (__res > __capacity 00291 || __res > size_type(_S_local_capacity)) 00292 { 00293 pointer __tmp = _M_create(__res, __capacity); 00294 this->_S_copy(__tmp, _M_data(), length() + 1); 00295 _M_dispose(); 00296 _M_data(__tmp); 00297 _M_capacity(__res); 00298 } 00299 else if (!_M_is_local()) 00300 { 00301 this->_S_copy(_M_local_data(), _M_data(), length() + 1); 00302 _M_destroy(__capacity); 00303 _M_data(_M_local_data()); 00304 } 00305 } 00306 } 00307 00308 template<typename _CharT, typename _Traits, typename _Alloc> 00309 void 00310 basic_string<_CharT, _Traits, _Alloc>:: 00311 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 00312 size_type __len2) 00313 { 00314 const size_type __how_much = length() - __pos - __len1; 00315 00316 size_type __new_capacity = length() + __len2 - __len1; 00317 pointer __r = _M_create(__new_capacity, capacity()); 00318 00319 if (__pos) 00320 this->_S_copy(__r, _M_data(), __pos); 00321 if (__s && __len2) 00322 this->_S_copy(__r + __pos, __s, __len2); 00323 if (__how_much) 00324 this->_S_copy(__r + __pos + __len2, 00325 _M_data() + __pos + __len1, __how_much); 00326 00327 _M_dispose(); 00328 _M_data(__r); 00329 _M_capacity(__new_capacity); 00330 } 00331 00332 template<typename _CharT, typename _Traits, typename _Alloc> 00333 void 00334 basic_string<_CharT, _Traits, _Alloc>:: 00335 _M_erase(size_type __pos, size_type __n) 00336 { 00337 const size_type __how_much = length() - __pos - __n; 00338 00339 if (__how_much && __n) 00340 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 00341 00342 _M_set_length(length() - __n); 00343 } 00344 00345 template<typename _CharT, typename _Traits, typename _Alloc> 00346 void 00347 basic_string<_CharT, _Traits, _Alloc>:: 00348 resize(size_type __n, _CharT __c) 00349 { 00350 const size_type __size = this->size(); 00351 if (__size < __n) 00352 this->append(__n - __size, __c); 00353 else if (__n < __size) 00354 this->_M_set_length(__n); 00355 } 00356 00357 template<typename _CharT, typename _Traits, typename _Alloc> 00358 basic_string<_CharT, _Traits, _Alloc>& 00359 basic_string<_CharT, _Traits, _Alloc>:: 00360 _M_append(const _CharT* __s, size_type __n) 00361 { 00362 const size_type __len = __n + this->size(); 00363 00364 if (__len <= this->capacity()) 00365 { 00366 if (__n) 00367 this->_S_copy(this->_M_data() + this->size(), __s, __n); 00368 } 00369 else 00370 this->_M_mutate(this->size(), size_type(0), __s, __n); 00371 00372 this->_M_set_length(__len); 00373 return *this; 00374 } 00375 00376 template<typename _CharT, typename _Traits, typename _Alloc> 00377 template<typename _InputIterator> 00378 basic_string<_CharT, _Traits, _Alloc>& 00379 basic_string<_CharT, _Traits, _Alloc>:: 00380 _M_replace_dispatch(const_iterator __i1, const_iterator __i2, 00381 _InputIterator __k1, _InputIterator __k2, 00382 std::__false_type) 00383 { 00384 const basic_string __s(__k1, __k2); 00385 const size_type __n1 = __i2 - __i1; 00386 return _M_replace(__i1 - begin(), __n1, __s._M_data(), 00387 __s.size()); 00388 } 00389 00390 template<typename _CharT, typename _Traits, typename _Alloc> 00391 basic_string<_CharT, _Traits, _Alloc>& 00392 basic_string<_CharT, _Traits, _Alloc>:: 00393 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 00394 _CharT __c) 00395 { 00396 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 00397 00398 const size_type __old_size = this->size(); 00399 const size_type __new_size = __old_size + __n2 - __n1; 00400 00401 if (__new_size <= this->capacity()) 00402 { 00403 pointer __p = this->_M_data() + __pos1; 00404 00405 const size_type __how_much = __old_size - __pos1 - __n1; 00406 if (__how_much && __n1 != __n2) 00407 this->_S_move(__p + __n2, __p + __n1, __how_much); 00408 } 00409 else 00410 this->_M_mutate(__pos1, __n1, 0, __n2); 00411 00412 if (__n2) 00413 this->_S_assign(this->_M_data() + __pos1, __n2, __c); 00414 00415 this->_M_set_length(__new_size); 00416 return *this; 00417 } 00418 00419 template<typename _CharT, typename _Traits, typename _Alloc> 00420 basic_string<_CharT, _Traits, _Alloc>& 00421 basic_string<_CharT, _Traits, _Alloc>:: 00422 _M_replace(size_type __pos, size_type __len1, const _CharT* __s, 00423 const size_type __len2) 00424 { 00425 _M_check_length(__len1, __len2, "basic_string::_M_replace"); 00426 00427 const size_type __old_size = this->size(); 00428 const size_type __new_size = __old_size + __len2 - __len1; 00429 00430 if (__new_size <= this->capacity()) 00431 { 00432 pointer __p = this->_M_data() + __pos; 00433 00434 const size_type __how_much = __old_size - __pos - __len1; 00435 if (_M_disjunct(__s)) 00436 { 00437 if (__how_much && __len1 != __len2) 00438 this->_S_move(__p + __len2, __p + __len1, __how_much); 00439 if (__len2) 00440 this->_S_copy(__p, __s, __len2); 00441 } 00442 else 00443 { 00444 // Work in-place. 00445 if (__len2 && __len2 <= __len1) 00446 this->_S_move(__p, __s, __len2); 00447 if (__how_much && __len1 != __len2) 00448 this->_S_move(__p + __len2, __p + __len1, __how_much); 00449 if (__len2 > __len1) 00450 { 00451 if (__s + __len2 <= __p + __len1) 00452 this->_S_move(__p, __s, __len2); 00453 else if (__s >= __p + __len1) 00454 this->_S_copy(__p, __s + __len2 - __len1, __len2); 00455 else 00456 { 00457 const size_type __nleft = (__p + __len1) - __s; 00458 this->_S_move(__p, __s, __nleft); 00459 this->_S_copy(__p + __nleft, __p + __len2, 00460 __len2 - __nleft); 00461 } 00462 } 00463 } 00464 } 00465 else 00466 this->_M_mutate(__pos, __len1, __s, __len2); 00467 00468 this->_M_set_length(__new_size); 00469 return *this; 00470 } 00471 00472 template<typename _CharT, typename _Traits, typename _Alloc> 00473 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00474 basic_string<_CharT, _Traits, _Alloc>:: 00475 copy(_CharT* __s, size_type __n, size_type __pos) const 00476 { 00477 _M_check(__pos, "basic_string::copy"); 00478 __n = _M_limit(__pos, __n); 00479 __glibcxx_requires_string_len(__s, __n); 00480 if (__n) 00481 _S_copy(__s, _M_data() + __pos, __n); 00482 // 21.3.5.7 par 3: do not append null. (good.) 00483 return __n; 00484 } 00485 00486 #else // !_GLIBCXX_USE_CXX11_ABI 00487 00488 template<typename _CharT, typename _Traits, typename _Alloc> 00489 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00490 basic_string<_CharT, _Traits, _Alloc>:: 00491 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 00492 00493 template<typename _CharT, typename _Traits, typename _Alloc> 00494 const _CharT 00495 basic_string<_CharT, _Traits, _Alloc>:: 00496 _Rep::_S_terminal = _CharT(); 00497 00498 template<typename _CharT, typename _Traits, typename _Alloc> 00499 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00500 basic_string<_CharT, _Traits, _Alloc>::npos; 00501 00502 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 00503 // at static init time (before static ctors are run). 00504 template<typename _CharT, typename _Traits, typename _Alloc> 00505 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00506 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 00507 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 00508 sizeof(size_type)]; 00509 00510 // NB: This is the special case for Input Iterators, used in 00511 // istreambuf_iterators, etc. 00512 // Input Iterators have a cost structure very different from 00513 // pointers, calling for a different coding style. 00514 template<typename _CharT, typename _Traits, typename _Alloc> 00515 template<typename _InIterator> 00516 _CharT* 00517 basic_string<_CharT, _Traits, _Alloc>:: 00518 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00519 input_iterator_tag) 00520 { 00521 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00522 if (__beg == __end && __a == _Alloc()) 00523 return _S_empty_rep()._M_refdata(); 00524 #endif 00525 // Avoid reallocation for common case. 00526 _CharT __buf[128]; 00527 size_type __len = 0; 00528 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 00529 { 00530 __buf[__len++] = *__beg; 00531 ++__beg; 00532 } 00533 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 00534 _M_copy(__r->_M_refdata(), __buf, __len); 00535 __try 00536 { 00537 while (__beg != __end) 00538 { 00539 if (__len == __r->_M_capacity) 00540 { 00541 // Allocate more space. 00542 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 00543 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 00544 __r->_M_destroy(__a); 00545 __r = __another; 00546 } 00547 __r->_M_refdata()[__len++] = *__beg; 00548 ++__beg; 00549 } 00550 } 00551 __catch(...) 00552 { 00553 __r->_M_destroy(__a); 00554 __throw_exception_again; 00555 } 00556 __r->_M_set_length_and_sharable(__len); 00557 return __r->_M_refdata(); 00558 } 00559 00560 template<typename _CharT, typename _Traits, typename _Alloc> 00561 template <typename _InIterator> 00562 _CharT* 00563 basic_string<_CharT, _Traits, _Alloc>:: 00564 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00565 forward_iterator_tag) 00566 { 00567 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00568 if (__beg == __end && __a == _Alloc()) 00569 return _S_empty_rep()._M_refdata(); 00570 #endif 00571 // NB: Not required, but considered best practice. 00572 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 00573 __throw_logic_error(__N("basic_string::_S_construct null not valid")); 00574 00575 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 00576 __end)); 00577 // Check for out_of_range and length_error exceptions. 00578 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 00579 __try 00580 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 00581 __catch(...) 00582 { 00583 __r->_M_destroy(__a); 00584 __throw_exception_again; 00585 } 00586 __r->_M_set_length_and_sharable(__dnew); 00587 return __r->_M_refdata(); 00588 } 00589 00590 template<typename _CharT, typename _Traits, typename _Alloc> 00591 _CharT* 00592 basic_string<_CharT, _Traits, _Alloc>:: 00593 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 00594 { 00595 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00596 if (__n == 0 && __a == _Alloc()) 00597 return _S_empty_rep()._M_refdata(); 00598 #endif 00599 // Check for out_of_range and length_error exceptions. 00600 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 00601 if (__n) 00602 _M_assign(__r->_M_refdata(), __n, __c); 00603 00604 __r->_M_set_length_and_sharable(__n); 00605 return __r->_M_refdata(); 00606 } 00607 00608 template<typename _CharT, typename _Traits, typename _Alloc> 00609 basic_string<_CharT, _Traits, _Alloc>:: 00610 basic_string(const basic_string& __str) 00611 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 00612 __str.get_allocator()), 00613 __str.get_allocator()) 00614 { } 00615 00616 template<typename _CharT, typename _Traits, typename _Alloc> 00617 basic_string<_CharT, _Traits, _Alloc>:: 00618 basic_string(const _Alloc& __a) 00619 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 00620 { } 00621 00622 template<typename _CharT, typename _Traits, typename _Alloc> 00623 basic_string<_CharT, _Traits, _Alloc>:: 00624 basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a) 00625 : _M_dataplus(_S_construct(__str._M_data() 00626 + __str._M_check(__pos, 00627 "basic_string::basic_string"), 00628 __str._M_data() + __str._M_limit(__pos, npos) 00629 + __pos, __a), __a) 00630 { } 00631 00632 template<typename _CharT, typename _Traits, typename _Alloc> 00633 basic_string<_CharT, _Traits, _Alloc>:: 00634 basic_string(const basic_string& __str, size_type __pos, size_type __n) 00635 : _M_dataplus(_S_construct(__str._M_data() 00636 + __str._M_check(__pos, 00637 "basic_string::basic_string"), 00638 __str._M_data() + __str._M_limit(__pos, __n) 00639 + __pos, _Alloc()), _Alloc()) 00640 { } 00641 00642 template<typename _CharT, typename _Traits, typename _Alloc> 00643 basic_string<_CharT, _Traits, _Alloc>:: 00644 basic_string(const basic_string& __str, size_type __pos, 00645 size_type __n, const _Alloc& __a) 00646 : _M_dataplus(_S_construct(__str._M_data() 00647 + __str._M_check(__pos, 00648 "basic_string::basic_string"), 00649 __str._M_data() + __str._M_limit(__pos, __n) 00650 + __pos, __a), __a) 00651 { } 00652 00653 // TBD: DPG annotate 00654 template<typename _CharT, typename _Traits, typename _Alloc> 00655 basic_string<_CharT, _Traits, _Alloc>:: 00656 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00657 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00658 { } 00659 00660 // TBD: DPG annotate 00661 template<typename _CharT, typename _Traits, typename _Alloc> 00662 basic_string<_CharT, _Traits, _Alloc>:: 00663 basic_string(const _CharT* __s, const _Alloc& __a) 00664 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00665 __s + npos, __a), __a) 00666 { } 00667 00668 template<typename _CharT, typename _Traits, typename _Alloc> 00669 basic_string<_CharT, _Traits, _Alloc>:: 00670 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00671 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00672 { } 00673 00674 // TBD: DPG annotate 00675 template<typename _CharT, typename _Traits, typename _Alloc> 00676 template<typename _InputIterator> 00677 basic_string<_CharT, _Traits, _Alloc>:: 00678 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 00679 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00680 { } 00681 00682 #if __cplusplus >= 201103L 00683 template<typename _CharT, typename _Traits, typename _Alloc> 00684 basic_string<_CharT, _Traits, _Alloc>:: 00685 basic_string(initializer_list<_CharT> __l, const _Alloc& __a) 00686 : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a) 00687 { } 00688 #endif 00689 00690 template<typename _CharT, typename _Traits, typename _Alloc> 00691 basic_string<_CharT, _Traits, _Alloc>& 00692 basic_string<_CharT, _Traits, _Alloc>:: 00693 assign(const basic_string& __str) 00694 { 00695 if (_M_rep() != __str._M_rep()) 00696 { 00697 // XXX MT 00698 const allocator_type __a = this->get_allocator(); 00699 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00700 _M_rep()->_M_dispose(__a); 00701 _M_data(__tmp); 00702 } 00703 return *this; 00704 } 00705 00706 template<typename _CharT, typename _Traits, typename _Alloc> 00707 basic_string<_CharT, _Traits, _Alloc>& 00708 basic_string<_CharT, _Traits, _Alloc>:: 00709 assign(const _CharT* __s, size_type __n) 00710 { 00711 __glibcxx_requires_string_len(__s, __n); 00712 _M_check_length(this->size(), __n, "basic_string::assign"); 00713 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00714 return _M_replace_safe(size_type(0), this->size(), __s, __n); 00715 else 00716 { 00717 // Work in-place. 00718 const size_type __pos = __s - _M_data(); 00719 if (__pos >= __n) 00720 _M_copy(_M_data(), __s, __n); 00721 else if (__pos) 00722 _M_move(_M_data(), __s, __n); 00723 _M_rep()->_M_set_length_and_sharable(__n); 00724 return *this; 00725 } 00726 } 00727 00728 template<typename _CharT, typename _Traits, typename _Alloc> 00729 basic_string<_CharT, _Traits, _Alloc>& 00730 basic_string<_CharT, _Traits, _Alloc>:: 00731 append(size_type __n, _CharT __c) 00732 { 00733 if (__n) 00734 { 00735 _M_check_length(size_type(0), __n, "basic_string::append"); 00736 const size_type __len = __n + this->size(); 00737 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00738 this->reserve(__len); 00739 _M_assign(_M_data() + this->size(), __n, __c); 00740 _M_rep()->_M_set_length_and_sharable(__len); 00741 } 00742 return *this; 00743 } 00744 00745 template<typename _CharT, typename _Traits, typename _Alloc> 00746 basic_string<_CharT, _Traits, _Alloc>& 00747 basic_string<_CharT, _Traits, _Alloc>:: 00748 append(const _CharT* __s, size_type __n) 00749 { 00750 __glibcxx_requires_string_len(__s, __n); 00751 if (__n) 00752 { 00753 _M_check_length(size_type(0), __n, "basic_string::append"); 00754 const size_type __len = __n + this->size(); 00755 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00756 { 00757 if (_M_disjunct(__s)) 00758 this->reserve(__len); 00759 else 00760 { 00761 const size_type __off = __s - _M_data(); 00762 this->reserve(__len); 00763 __s = _M_data() + __off; 00764 } 00765 } 00766 _M_copy(_M_data() + this->size(), __s, __n); 00767 _M_rep()->_M_set_length_and_sharable(__len); 00768 } 00769 return *this; 00770 } 00771 00772 template<typename _CharT, typename _Traits, typename _Alloc> 00773 basic_string<_CharT, _Traits, _Alloc>& 00774 basic_string<_CharT, _Traits, _Alloc>:: 00775 append(const basic_string& __str) 00776 { 00777 const size_type __size = __str.size(); 00778 if (__size) 00779 { 00780 const size_type __len = __size + this->size(); 00781 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00782 this->reserve(__len); 00783 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 00784 _M_rep()->_M_set_length_and_sharable(__len); 00785 } 00786 return *this; 00787 } 00788 00789 template<typename _CharT, typename _Traits, typename _Alloc> 00790 basic_string<_CharT, _Traits, _Alloc>& 00791 basic_string<_CharT, _Traits, _Alloc>:: 00792 append(const basic_string& __str, size_type __pos, size_type __n) 00793 { 00794 __str._M_check(__pos, "basic_string::append"); 00795 __n = __str._M_limit(__pos, __n); 00796 if (__n) 00797 { 00798 const size_type __len = __n + this->size(); 00799 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00800 this->reserve(__len); 00801 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 00802 _M_rep()->_M_set_length_and_sharable(__len); 00803 } 00804 return *this; 00805 } 00806 00807 template<typename _CharT, typename _Traits, typename _Alloc> 00808 basic_string<_CharT, _Traits, _Alloc>& 00809 basic_string<_CharT, _Traits, _Alloc>:: 00810 insert(size_type __pos, const _CharT* __s, size_type __n) 00811 { 00812 __glibcxx_requires_string_len(__s, __n); 00813 _M_check(__pos, "basic_string::insert"); 00814 _M_check_length(size_type(0), __n, "basic_string::insert"); 00815 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00816 return _M_replace_safe(__pos, size_type(0), __s, __n); 00817 else 00818 { 00819 // Work in-place. 00820 const size_type __off = __s - _M_data(); 00821 _M_mutate(__pos, 0, __n); 00822 __s = _M_data() + __off; 00823 _CharT* __p = _M_data() + __pos; 00824 if (__s + __n <= __p) 00825 _M_copy(__p, __s, __n); 00826 else if (__s >= __p) 00827 _M_copy(__p, __s + __n, __n); 00828 else 00829 { 00830 const size_type __nleft = __p - __s; 00831 _M_copy(__p, __s, __nleft); 00832 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 00833 } 00834 return *this; 00835 } 00836 } 00837 00838 template<typename _CharT, typename _Traits, typename _Alloc> 00839 typename basic_string<_CharT, _Traits, _Alloc>::iterator 00840 basic_string<_CharT, _Traits, _Alloc>:: 00841 erase(iterator __first, iterator __last) 00842 { 00843 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 00844 && __last <= _M_iend()); 00845 00846 // NB: This isn't just an optimization (bail out early when 00847 // there is nothing to do, really), it's also a correctness 00848 // issue vs MT, see libstdc++/40518. 00849 const size_type __size = __last - __first; 00850 if (__size) 00851 { 00852 const size_type __pos = __first - _M_ibegin(); 00853 _M_mutate(__pos, __size, size_type(0)); 00854 _M_rep()->_M_set_leaked(); 00855 return iterator(_M_data() + __pos); 00856 } 00857 else 00858 return __first; 00859 } 00860 00861 template<typename _CharT, typename _Traits, typename _Alloc> 00862 basic_string<_CharT, _Traits, _Alloc>& 00863 basic_string<_CharT, _Traits, _Alloc>:: 00864 replace(size_type __pos, size_type __n1, const _CharT* __s, 00865 size_type __n2) 00866 { 00867 __glibcxx_requires_string_len(__s, __n2); 00868 _M_check(__pos, "basic_string::replace"); 00869 __n1 = _M_limit(__pos, __n1); 00870 _M_check_length(__n1, __n2, "basic_string::replace"); 00871 bool __left; 00872 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00873 return _M_replace_safe(__pos, __n1, __s, __n2); 00874 else if ((__left = __s + __n2 <= _M_data() + __pos) 00875 || _M_data() + __pos + __n1 <= __s) 00876 { 00877 // Work in-place: non-overlapping case. 00878 size_type __off = __s - _M_data(); 00879 __left ? __off : (__off += __n2 - __n1); 00880 _M_mutate(__pos, __n1, __n2); 00881 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 00882 return *this; 00883 } 00884 else 00885 { 00886 // Todo: overlapping case. 00887 const basic_string __tmp(__s, __n2); 00888 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 00889 } 00890 } 00891 00892 template<typename _CharT, typename _Traits, typename _Alloc> 00893 void 00894 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00895 _M_destroy(const _Alloc& __a) throw () 00896 { 00897 const size_type __size = sizeof(_Rep_base) + 00898 (this->_M_capacity + 1) * sizeof(_CharT); 00899 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00900 } 00901 00902 template<typename _CharT, typename _Traits, typename _Alloc> 00903 void 00904 basic_string<_CharT, _Traits, _Alloc>:: 00905 _M_leak_hard() 00906 { 00907 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 00908 if (_M_rep() == &_S_empty_rep()) 00909 return; 00910 #endif 00911 if (_M_rep()->_M_is_shared()) 00912 _M_mutate(0, 0, 0); 00913 _M_rep()->_M_set_leaked(); 00914 } 00915 00916 template<typename _CharT, typename _Traits, typename _Alloc> 00917 void 00918 basic_string<_CharT, _Traits, _Alloc>:: 00919 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00920 { 00921 const size_type __old_size = this->size(); 00922 const size_type __new_size = __old_size + __len2 - __len1; 00923 const size_type __how_much = __old_size - __pos - __len1; 00924 00925 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 00926 { 00927 // Must reallocate. 00928 const allocator_type __a = get_allocator(); 00929 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 00930 00931 if (__pos) 00932 _M_copy(__r->_M_refdata(), _M_data(), __pos); 00933 if (__how_much) 00934 _M_copy(__r->_M_refdata() + __pos + __len2, 00935 _M_data() + __pos + __len1, __how_much); 00936 00937 _M_rep()->_M_dispose(__a); 00938 _M_data(__r->_M_refdata()); 00939 } 00940 else if (__how_much && __len1 != __len2) 00941 { 00942 // Work in-place. 00943 _M_move(_M_data() + __pos + __len2, 00944 _M_data() + __pos + __len1, __how_much); 00945 } 00946 _M_rep()->_M_set_length_and_sharable(__new_size); 00947 } 00948 00949 template<typename _CharT, typename _Traits, typename _Alloc> 00950 void 00951 basic_string<_CharT, _Traits, _Alloc>:: 00952 reserve(size_type __res) 00953 { 00954 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 00955 { 00956 // Make sure we don't shrink below the current size 00957 if (__res < this->size()) 00958 __res = this->size(); 00959 const allocator_type __a = get_allocator(); 00960 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00961 _M_rep()->_M_dispose(__a); 00962 _M_data(__tmp); 00963 } 00964 } 00965 00966 template<typename _CharT, typename _Traits, typename _Alloc> 00967 void 00968 basic_string<_CharT, _Traits, _Alloc>:: 00969 swap(basic_string& __s) 00970 { 00971 if (_M_rep()->_M_is_leaked()) 00972 _M_rep()->_M_set_sharable(); 00973 if (__s._M_rep()->_M_is_leaked()) 00974 __s._M_rep()->_M_set_sharable(); 00975 if (this->get_allocator() == __s.get_allocator()) 00976 { 00977 _CharT* __tmp = _M_data(); 00978 _M_data(__s._M_data()); 00979 __s._M_data(__tmp); 00980 } 00981 // The code below can usually be optimized away. 00982 else 00983 { 00984 const basic_string __tmp1(_M_ibegin(), _M_iend(), 00985 __s.get_allocator()); 00986 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00987 this->get_allocator()); 00988 *this = __tmp2; 00989 __s = __tmp1; 00990 } 00991 } 00992 00993 template<typename _CharT, typename _Traits, typename _Alloc> 00994 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00995 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00996 _S_create(size_type __capacity, size_type __old_capacity, 00997 const _Alloc& __alloc) 00998 { 00999 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01000 // 83. String::npos vs. string::max_size() 01001 if (__capacity > _S_max_size) 01002 __throw_length_error(__N("basic_string::_S_create")); 01003 01004 // The standard places no restriction on allocating more memory 01005 // than is strictly needed within this layer at the moment or as 01006 // requested by an explicit application call to reserve(). 01007 01008 // Many malloc implementations perform quite poorly when an 01009 // application attempts to allocate memory in a stepwise fashion 01010 // growing each allocation size by only 1 char. Additionally, 01011 // it makes little sense to allocate less linear memory than the 01012 // natural blocking size of the malloc implementation. 01013 // Unfortunately, we would need a somewhat low-level calculation 01014 // with tuned parameters to get this perfect for any particular 01015 // malloc implementation. Fortunately, generalizations about 01016 // common features seen among implementations seems to suffice. 01017 01018 // __pagesize need not match the actual VM page size for good 01019 // results in practice, thus we pick a common value on the low 01020 // side. __malloc_header_size is an estimate of the amount of 01021 // overhead per memory allocation (in practice seen N * sizeof 01022 // (void*) where N is 0, 2 or 4). According to folklore, 01023 // picking this value on the high side is better than 01024 // low-balling it (especially when this algorithm is used with 01025 // malloc implementations that allocate memory blocks rounded up 01026 // to a size which is a power of 2). 01027 const size_type __pagesize = 4096; 01028 const size_type __malloc_header_size = 4 * sizeof(void*); 01029 01030 // The below implements an exponential growth policy, necessary to 01031 // meet amortized linear time requirements of the library: see 01032 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 01033 // It's active for allocations requiring an amount of memory above 01034 // system pagesize. This is consistent with the requirements of the 01035 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 01036 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 01037 __capacity = 2 * __old_capacity; 01038 01039 // NB: Need an array of char_type[__capacity], plus a terminating 01040 // null char_type() element, plus enough for the _Rep data structure. 01041 // Whew. Seemingly so needy, yet so elemental. 01042 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01043 01044 const size_type __adj_size = __size + __malloc_header_size; 01045 if (__adj_size > __pagesize && __capacity > __old_capacity) 01046 { 01047 const size_type __extra = __pagesize - __adj_size % __pagesize; 01048 __capacity += __extra / sizeof(_CharT); 01049 // Never allocate a string bigger than _S_max_size. 01050 if (__capacity > _S_max_size) 01051 __capacity = _S_max_size; 01052 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 01053 } 01054 01055 // NB: Might throw, but no worries about a leak, mate: _Rep() 01056 // does not throw. 01057 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 01058 _Rep *__p = new (__place) _Rep; 01059 __p->_M_capacity = __capacity; 01060 // ABI compatibility - 3.4.x set in _S_create both 01061 // _M_refcount and _M_length. All callers of _S_create 01062 // in basic_string.tcc then set just _M_length. 01063 // In 4.0.x and later both _M_refcount and _M_length 01064 // are initialized in the callers, unfortunately we can 01065 // have 3.4.x compiled code with _S_create callers inlined 01066 // calling 4.0.x+ _S_create. 01067 __p->_M_set_sharable(); 01068 return __p; 01069 } 01070 01071 template<typename _CharT, typename _Traits, typename _Alloc> 01072 _CharT* 01073 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 01074 _M_clone(const _Alloc& __alloc, size_type __res) 01075 { 01076 // Requested capacity of the clone. 01077 const size_type __requested_cap = this->_M_length + __res; 01078 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 01079 __alloc); 01080 if (this->_M_length) 01081 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 01082 01083 __r->_M_set_length_and_sharable(this->_M_length); 01084 return __r->_M_refdata(); 01085 } 01086 01087 template<typename _CharT, typename _Traits, typename _Alloc> 01088 void 01089 basic_string<_CharT, _Traits, _Alloc>:: 01090 resize(size_type __n, _CharT __c) 01091 { 01092 const size_type __size = this->size(); 01093 _M_check_length(__size, __n, "basic_string::resize"); 01094 if (__size < __n) 01095 this->append(__n - __size, __c); 01096 else if (__n < __size) 01097 this->erase(__n); 01098 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 01099 } 01100 01101 template<typename _CharT, typename _Traits, typename _Alloc> 01102 template<typename _InputIterator> 01103 basic_string<_CharT, _Traits, _Alloc>& 01104 basic_string<_CharT, _Traits, _Alloc>:: 01105 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 01106 _InputIterator __k2, __false_type) 01107 { 01108 const basic_string __s(__k1, __k2); 01109 const size_type __n1 = __i2 - __i1; 01110 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 01111 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 01112 __s.size()); 01113 } 01114 01115 template<typename _CharT, typename _Traits, typename _Alloc> 01116 basic_string<_CharT, _Traits, _Alloc>& 01117 basic_string<_CharT, _Traits, _Alloc>:: 01118 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 01119 _CharT __c) 01120 { 01121 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 01122 _M_mutate(__pos1, __n1, __n2); 01123 if (__n2) 01124 _M_assign(_M_data() + __pos1, __n2, __c); 01125 return *this; 01126 } 01127 01128 template<typename _CharT, typename _Traits, typename _Alloc> 01129 basic_string<_CharT, _Traits, _Alloc>& 01130 basic_string<_CharT, _Traits, _Alloc>:: 01131 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 01132 size_type __n2) 01133 { 01134 _M_mutate(__pos1, __n1, __n2); 01135 if (__n2) 01136 _M_copy(_M_data() + __pos1, __s, __n2); 01137 return *this; 01138 } 01139 01140 template<typename _CharT, typename _Traits, typename _Alloc> 01141 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01142 basic_string<_CharT, _Traits, _Alloc>:: 01143 copy(_CharT* __s, size_type __n, size_type __pos) const 01144 { 01145 _M_check(__pos, "basic_string::copy"); 01146 __n = _M_limit(__pos, __n); 01147 __glibcxx_requires_string_len(__s, __n); 01148 if (__n) 01149 _M_copy(__s, _M_data() + __pos, __n); 01150 // 21.3.5.7 par 3: do not append null. (good.) 01151 return __n; 01152 } 01153 #endif // !_GLIBCXX_USE_CXX11_ABI 01154 01155 template<typename _CharT, typename _Traits, typename _Alloc> 01156 basic_string<_CharT, _Traits, _Alloc> 01157 operator+(const _CharT* __lhs, 01158 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01159 { 01160 __glibcxx_requires_string(__lhs); 01161 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01162 typedef typename __string_type::size_type __size_type; 01163 const __size_type __len = _Traits::length(__lhs); 01164 __string_type __str; 01165 __str.reserve(__len + __rhs.size()); 01166 __str.append(__lhs, __len); 01167 __str.append(__rhs); 01168 return __str; 01169 } 01170 01171 template<typename _CharT, typename _Traits, typename _Alloc> 01172 basic_string<_CharT, _Traits, _Alloc> 01173 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 01174 { 01175 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01176 typedef typename __string_type::size_type __size_type; 01177 __string_type __str; 01178 const __size_type __len = __rhs.size(); 01179 __str.reserve(__len + 1); 01180 __str.append(__size_type(1), __lhs); 01181 __str.append(__rhs); 01182 return __str; 01183 } 01184 01185 template<typename _CharT, typename _Traits, typename _Alloc> 01186 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01187 basic_string<_CharT, _Traits, _Alloc>:: 01188 find(const _CharT* __s, size_type __pos, size_type __n) const 01189 _GLIBCXX_NOEXCEPT 01190 { 01191 __glibcxx_requires_string_len(__s, __n); 01192 const size_type __size = this->size(); 01193 01194 if (__n == 0) 01195 return __pos <= __size ? __pos : npos; 01196 if (__pos >= __size) 01197 return npos; 01198 01199 const _CharT __elem0 = __s[0]; 01200 const _CharT* const __data = data(); 01201 const _CharT* __first = __data + __pos; 01202 const _CharT* const __last = __data + __size; 01203 size_type __len = __size - __pos; 01204 01205 while (__len >= __n) 01206 { 01207 // Find the first occurrence of __elem0: 01208 __first = traits_type::find(__first, __len - __n + 1, __elem0); 01209 if (!__first) 01210 return npos; 01211 // Compare the full strings from the first occurrence of __elem0. 01212 // We already know that __first[0] == __s[0] but compare them again 01213 // anyway because __s is probably aligned, which helps memcmp. 01214 if (traits_type::compare(__first, __s, __n) == 0) 01215 return __first - __data; 01216 __len = __last - ++__first; 01217 } 01218 return npos; 01219 } 01220 01221 template<typename _CharT, typename _Traits, typename _Alloc> 01222 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01223 basic_string<_CharT, _Traits, _Alloc>:: 01224 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01225 { 01226 size_type __ret = npos; 01227 const size_type __size = this->size(); 01228 if (__pos < __size) 01229 { 01230 const _CharT* __data = _M_data(); 01231 const size_type __n = __size - __pos; 01232 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 01233 if (__p) 01234 __ret = __p - __data; 01235 } 01236 return __ret; 01237 } 01238 01239 template<typename _CharT, typename _Traits, typename _Alloc> 01240 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01241 basic_string<_CharT, _Traits, _Alloc>:: 01242 rfind(const _CharT* __s, size_type __pos, size_type __n) const 01243 _GLIBCXX_NOEXCEPT 01244 { 01245 __glibcxx_requires_string_len(__s, __n); 01246 const size_type __size = this->size(); 01247 if (__n <= __size) 01248 { 01249 __pos = std::min(size_type(__size - __n), __pos); 01250 const _CharT* __data = _M_data(); 01251 do 01252 { 01253 if (traits_type::compare(__data + __pos, __s, __n) == 0) 01254 return __pos; 01255 } 01256 while (__pos-- > 0); 01257 } 01258 return npos; 01259 } 01260 01261 template<typename _CharT, typename _Traits, typename _Alloc> 01262 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01263 basic_string<_CharT, _Traits, _Alloc>:: 01264 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01265 { 01266 size_type __size = this->size(); 01267 if (__size) 01268 { 01269 if (--__size > __pos) 01270 __size = __pos; 01271 for (++__size; __size-- > 0; ) 01272 if (traits_type::eq(_M_data()[__size], __c)) 01273 return __size; 01274 } 01275 return npos; 01276 } 01277 01278 template<typename _CharT, typename _Traits, typename _Alloc> 01279 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01280 basic_string<_CharT, _Traits, _Alloc>:: 01281 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 01282 _GLIBCXX_NOEXCEPT 01283 { 01284 __glibcxx_requires_string_len(__s, __n); 01285 for (; __n && __pos < this->size(); ++__pos) 01286 { 01287 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 01288 if (__p) 01289 return __pos; 01290 } 01291 return npos; 01292 } 01293 01294 template<typename _CharT, typename _Traits, typename _Alloc> 01295 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01296 basic_string<_CharT, _Traits, _Alloc>:: 01297 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 01298 _GLIBCXX_NOEXCEPT 01299 { 01300 __glibcxx_requires_string_len(__s, __n); 01301 size_type __size = this->size(); 01302 if (__size && __n) 01303 { 01304 if (--__size > __pos) 01305 __size = __pos; 01306 do 01307 { 01308 if (traits_type::find(__s, __n, _M_data()[__size])) 01309 return __size; 01310 } 01311 while (__size-- != 0); 01312 } 01313 return npos; 01314 } 01315 01316 template<typename _CharT, typename _Traits, typename _Alloc> 01317 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01318 basic_string<_CharT, _Traits, _Alloc>:: 01319 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01320 _GLIBCXX_NOEXCEPT 01321 { 01322 __glibcxx_requires_string_len(__s, __n); 01323 for (; __pos < this->size(); ++__pos) 01324 if (!traits_type::find(__s, __n, _M_data()[__pos])) 01325 return __pos; 01326 return npos; 01327 } 01328 01329 template<typename _CharT, typename _Traits, typename _Alloc> 01330 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01331 basic_string<_CharT, _Traits, _Alloc>:: 01332 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01333 { 01334 for (; __pos < this->size(); ++__pos) 01335 if (!traits_type::eq(_M_data()[__pos], __c)) 01336 return __pos; 01337 return npos; 01338 } 01339 01340 template<typename _CharT, typename _Traits, typename _Alloc> 01341 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01342 basic_string<_CharT, _Traits, _Alloc>:: 01343 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 01344 _GLIBCXX_NOEXCEPT 01345 { 01346 __glibcxx_requires_string_len(__s, __n); 01347 size_type __size = this->size(); 01348 if (__size) 01349 { 01350 if (--__size > __pos) 01351 __size = __pos; 01352 do 01353 { 01354 if (!traits_type::find(__s, __n, _M_data()[__size])) 01355 return __size; 01356 } 01357 while (__size--); 01358 } 01359 return npos; 01360 } 01361 01362 template<typename _CharT, typename _Traits, typename _Alloc> 01363 typename basic_string<_CharT, _Traits, _Alloc>::size_type 01364 basic_string<_CharT, _Traits, _Alloc>:: 01365 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 01366 { 01367 size_type __size = this->size(); 01368 if (__size) 01369 { 01370 if (--__size > __pos) 01371 __size = __pos; 01372 do 01373 { 01374 if (!traits_type::eq(_M_data()[__size], __c)) 01375 return __size; 01376 } 01377 while (__size--); 01378 } 01379 return npos; 01380 } 01381 01382 template<typename _CharT, typename _Traits, typename _Alloc> 01383 int 01384 basic_string<_CharT, _Traits, _Alloc>:: 01385 compare(size_type __pos, size_type __n, const basic_string& __str) const 01386 { 01387 _M_check(__pos, "basic_string::compare"); 01388 __n = _M_limit(__pos, __n); 01389 const size_type __osize = __str.size(); 01390 const size_type __len = std::min(__n, __osize); 01391 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 01392 if (!__r) 01393 __r = _S_compare(__n, __osize); 01394 return __r; 01395 } 01396 01397 template<typename _CharT, typename _Traits, typename _Alloc> 01398 int 01399 basic_string<_CharT, _Traits, _Alloc>:: 01400 compare(size_type __pos1, size_type __n1, const basic_string& __str, 01401 size_type __pos2, size_type __n2) const 01402 { 01403 _M_check(__pos1, "basic_string::compare"); 01404 __str._M_check(__pos2, "basic_string::compare"); 01405 __n1 = _M_limit(__pos1, __n1); 01406 __n2 = __str._M_limit(__pos2, __n2); 01407 const size_type __len = std::min(__n1, __n2); 01408 int __r = traits_type::compare(_M_data() + __pos1, 01409 __str.data() + __pos2, __len); 01410 if (!__r) 01411 __r = _S_compare(__n1, __n2); 01412 return __r; 01413 } 01414 01415 template<typename _CharT, typename _Traits, typename _Alloc> 01416 int 01417 basic_string<_CharT, _Traits, _Alloc>:: 01418 compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT 01419 { 01420 __glibcxx_requires_string(__s); 01421 const size_type __size = this->size(); 01422 const size_type __osize = traits_type::length(__s); 01423 const size_type __len = std::min(__size, __osize); 01424 int __r = traits_type::compare(_M_data(), __s, __len); 01425 if (!__r) 01426 __r = _S_compare(__size, __osize); 01427 return __r; 01428 } 01429 01430 template<typename _CharT, typename _Traits, typename _Alloc> 01431 int 01432 basic_string <_CharT, _Traits, _Alloc>:: 01433 compare(size_type __pos, size_type __n1, const _CharT* __s) const 01434 { 01435 __glibcxx_requires_string(__s); 01436 _M_check(__pos, "basic_string::compare"); 01437 __n1 = _M_limit(__pos, __n1); 01438 const size_type __osize = traits_type::length(__s); 01439 const size_type __len = std::min(__n1, __osize); 01440 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01441 if (!__r) 01442 __r = _S_compare(__n1, __osize); 01443 return __r; 01444 } 01445 01446 template<typename _CharT, typename _Traits, typename _Alloc> 01447 int 01448 basic_string <_CharT, _Traits, _Alloc>:: 01449 compare(size_type __pos, size_type __n1, const _CharT* __s, 01450 size_type __n2) const 01451 { 01452 __glibcxx_requires_string_len(__s, __n2); 01453 _M_check(__pos, "basic_string::compare"); 01454 __n1 = _M_limit(__pos, __n1); 01455 const size_type __len = std::min(__n1, __n2); 01456 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01457 if (!__r) 01458 __r = _S_compare(__n1, __n2); 01459 return __r; 01460 } 01461 01462 // 21.3.7.9 basic_string::getline and operators 01463 template<typename _CharT, typename _Traits, typename _Alloc> 01464 basic_istream<_CharT, _Traits>& 01465 operator>>(basic_istream<_CharT, _Traits>& __in, 01466 basic_string<_CharT, _Traits, _Alloc>& __str) 01467 { 01468 typedef basic_istream<_CharT, _Traits> __istream_type; 01469 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01470 typedef typename __istream_type::ios_base __ios_base; 01471 typedef typename __istream_type::int_type __int_type; 01472 typedef typename __string_type::size_type __size_type; 01473 typedef ctype<_CharT> __ctype_type; 01474 typedef typename __ctype_type::ctype_base __ctype_base; 01475 01476 __size_type __extracted = 0; 01477 typename __ios_base::iostate __err = __ios_base::goodbit; 01478 typename __istream_type::sentry __cerb(__in, false); 01479 if (__cerb) 01480 { 01481 __try 01482 { 01483 // Avoid reallocation for common case. 01484 __str.erase(); 01485 _CharT __buf[128]; 01486 __size_type __len = 0; 01487 const streamsize __w = __in.width(); 01488 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 01489 : __str.max_size(); 01490 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 01491 const __int_type __eof = _Traits::eof(); 01492 __int_type __c = __in.rdbuf()->sgetc(); 01493 01494 while (__extracted < __n 01495 && !_Traits::eq_int_type(__c, __eof) 01496 && !__ct.is(__ctype_base::space, 01497 _Traits::to_char_type(__c))) 01498 { 01499 if (__len == sizeof(__buf) / sizeof(_CharT)) 01500 { 01501 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 01502 __len = 0; 01503 } 01504 __buf[__len++] = _Traits::to_char_type(__c); 01505 ++__extracted; 01506 __c = __in.rdbuf()->snextc(); 01507 } 01508 __str.append(__buf, __len); 01509 01510 if (_Traits::eq_int_type(__c, __eof)) 01511 __err |= __ios_base::eofbit; 01512 __in.width(0); 01513 } 01514 __catch(__cxxabiv1::__forced_unwind&) 01515 { 01516 __in._M_setstate(__ios_base::badbit); 01517 __throw_exception_again; 01518 } 01519 __catch(...) 01520 { 01521 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01522 // 91. Description of operator>> and getline() for string<> 01523 // might cause endless loop 01524 __in._M_setstate(__ios_base::badbit); 01525 } 01526 } 01527 // 211. operator>>(istream&, string&) doesn't set failbit 01528 if (!__extracted) 01529 __err |= __ios_base::failbit; 01530 if (__err) 01531 __in.setstate(__err); 01532 return __in; 01533 } 01534 01535 template<typename _CharT, typename _Traits, typename _Alloc> 01536 basic_istream<_CharT, _Traits>& 01537 getline(basic_istream<_CharT, _Traits>& __in, 01538 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 01539 { 01540 typedef basic_istream<_CharT, _Traits> __istream_type; 01541 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01542 typedef typename __istream_type::ios_base __ios_base; 01543 typedef typename __istream_type::int_type __int_type; 01544 typedef typename __string_type::size_type __size_type; 01545 01546 __size_type __extracted = 0; 01547 const __size_type __n = __str.max_size(); 01548 typename __ios_base::iostate __err = __ios_base::goodbit; 01549 typename __istream_type::sentry __cerb(__in, true); 01550 if (__cerb) 01551 { 01552 __try 01553 { 01554 __str.erase(); 01555 const __int_type __idelim = _Traits::to_int_type(__delim); 01556 const __int_type __eof = _Traits::eof(); 01557 __int_type __c = __in.rdbuf()->sgetc(); 01558 01559 while (__extracted < __n 01560 && !_Traits::eq_int_type(__c, __eof) 01561 && !_Traits::eq_int_type(__c, __idelim)) 01562 { 01563 __str += _Traits::to_char_type(__c); 01564 ++__extracted; 01565 __c = __in.rdbuf()->snextc(); 01566 } 01567 01568 if (_Traits::eq_int_type(__c, __eof)) 01569 __err |= __ios_base::eofbit; 01570 else if (_Traits::eq_int_type(__c, __idelim)) 01571 { 01572 ++__extracted; 01573 __in.rdbuf()->sbumpc(); 01574 } 01575 else 01576 __err |= __ios_base::failbit; 01577 } 01578 __catch(__cxxabiv1::__forced_unwind&) 01579 { 01580 __in._M_setstate(__ios_base::badbit); 01581 __throw_exception_again; 01582 } 01583 __catch(...) 01584 { 01585 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01586 // 91. Description of operator>> and getline() for string<> 01587 // might cause endless loop 01588 __in._M_setstate(__ios_base::badbit); 01589 } 01590 } 01591 if (!__extracted) 01592 __err |= __ios_base::failbit; 01593 if (__err) 01594 __in.setstate(__err); 01595 return __in; 01596 } 01597 01598 // Inhibit implicit instantiations for required instantiations, 01599 // which are defined via explicit instantiations elsewhere. 01600 #if _GLIBCXX_EXTERN_TEMPLATE 01601 // The explicit instantiations definitions in src/c++11/string-inst.cc 01602 // are compiled as C++14, so the new C++17 members aren't instantiated. 01603 // Until those definitions are compiled as C++17 suppress the declaration, 01604 // so C++17 code will implicitly instantiate std::string and std::wstring 01605 // as needed. 01606 # if __cplusplus <= 201402L && _GLIBCXX_EXTERN_TEMPLATE > 0 01607 extern template class basic_string<char>; 01608 # elif ! _GLIBCXX_USE_CXX11_ABI 01609 // Still need to prevent implicit instantiation of the COW empty rep, 01610 // to ensure the definition in libstdc++.so is unique (PR 86138). 01611 extern template basic_string<char>::size_type 01612 basic_string<char>::_Rep::_S_empty_rep_storage[]; 01613 # endif 01614 01615 extern template 01616 basic_istream<char>& 01617 operator>>(basic_istream<char>&, string&); 01618 extern template 01619 basic_ostream<char>& 01620 operator<<(basic_ostream<char>&, const string&); 01621 extern template 01622 basic_istream<char>& 01623 getline(basic_istream<char>&, string&, char); 01624 extern template 01625 basic_istream<char>& 01626 getline(basic_istream<char>&, string&); 01627 01628 #ifdef _GLIBCXX_USE_WCHAR_T 01629 # if __cplusplus <= 201402L && _GLIBCXX_EXTERN_TEMPLATE > 0 01630 extern template class basic_string<wchar_t>; 01631 # elif ! _GLIBCXX_USE_CXX11_ABI 01632 extern template basic_string<wchar_t>::size_type 01633 basic_string<wchar_t>::_Rep::_S_empty_rep_storage[]; 01634 # endif 01635 01636 extern template 01637 basic_istream<wchar_t>& 01638 operator>>(basic_istream<wchar_t>&, wstring&); 01639 extern template 01640 basic_ostream<wchar_t>& 01641 operator<<(basic_ostream<wchar_t>&, const wstring&); 01642 extern template 01643 basic_istream<wchar_t>& 01644 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 01645 extern template 01646 basic_istream<wchar_t>& 01647 getline(basic_istream<wchar_t>&, wstring&); 01648 #endif // _GLIBCXX_USE_WCHAR_T 01649 #endif // _GLIBCXX_EXTERN_TEMPLATE 01650 01651 _GLIBCXX_END_NAMESPACE_VERSION 01652 } // namespace std 01653 01654 #endif