libstdc++
|
00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 00004 // 2006, 2007, 2008, 2009 00005 // Free Software Foundation, Inc. 00006 // 00007 // This file is part of the GNU ISO C++ Library. This library is free 00008 // software; you can redistribute it and/or modify it under the 00009 // terms of the GNU General Public License as published by the 00010 // Free Software Foundation; either version 3, or (at your option) 00011 // any later version. 00012 00013 // This library is distributed in the hope that it will be useful, 00014 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00015 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00016 // GNU General Public License for more details. 00017 00018 // Under Section 7 of GPL version 3, you are granted additional 00019 // permissions described in the GCC Runtime Library Exception, version 00020 // 3.1, as published by the Free Software Foundation. 00021 00022 // You should have received a copy of the GNU General Public License and 00023 // a copy of the GCC Runtime Library Exception along with this program; 00024 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00025 // <http://www.gnu.org/licenses/>. 00026 00027 /** @file basic_string.tcc 00028 * This is an internal header file, included by other library headers. 00029 * You should not attempt to use it directly. 00030 */ 00031 00032 // 00033 // ISO C++ 14882: 21 Strings library 00034 // 00035 00036 // Written by Jason Merrill based upon the specification by Takanori Adachi 00037 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 00038 00039 #ifndef _BASIC_STRING_TCC 00040 #define _BASIC_STRING_TCC 1 00041 00042 #pragma GCC system_header 00043 00044 #include <cxxabi-forced.h> 00045 00046 _GLIBCXX_BEGIN_NAMESPACE(std) 00047 00048 template<typename _CharT, typename _Traits, typename _Alloc> 00049 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00050 basic_string<_CharT, _Traits, _Alloc>:: 00051 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 00052 00053 template<typename _CharT, typename _Traits, typename _Alloc> 00054 const _CharT 00055 basic_string<_CharT, _Traits, _Alloc>:: 00056 _Rep::_S_terminal = _CharT(); 00057 00058 template<typename _CharT, typename _Traits, typename _Alloc> 00059 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 00060 basic_string<_CharT, _Traits, _Alloc>::npos; 00061 00062 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 00063 // at static init time (before static ctors are run). 00064 template<typename _CharT, typename _Traits, typename _Alloc> 00065 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00066 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 00067 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 00068 sizeof(size_type)]; 00069 00070 // NB: This is the special case for Input Iterators, used in 00071 // istreambuf_iterators, etc. 00072 // Input Iterators have a cost structure very different from 00073 // pointers, calling for a different coding style. 00074 template<typename _CharT, typename _Traits, typename _Alloc> 00075 template<typename _InIterator> 00076 _CharT* 00077 basic_string<_CharT, _Traits, _Alloc>:: 00078 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00079 input_iterator_tag) 00080 { 00081 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 00082 if (__beg == __end && __a == _Alloc()) 00083 return _S_empty_rep()._M_refdata(); 00084 #endif 00085 // Avoid reallocation for common case. 00086 _CharT __buf[128]; 00087 size_type __len = 0; 00088 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 00089 { 00090 __buf[__len++] = *__beg; 00091 ++__beg; 00092 } 00093 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 00094 _M_copy(__r->_M_refdata(), __buf, __len); 00095 __try 00096 { 00097 while (__beg != __end) 00098 { 00099 if (__len == __r->_M_capacity) 00100 { 00101 // Allocate more space. 00102 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 00103 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 00104 __r->_M_destroy(__a); 00105 __r = __another; 00106 } 00107 __r->_M_refdata()[__len++] = *__beg; 00108 ++__beg; 00109 } 00110 } 00111 __catch(...) 00112 { 00113 __r->_M_destroy(__a); 00114 __throw_exception_again; 00115 } 00116 __r->_M_set_length_and_sharable(__len); 00117 return __r->_M_refdata(); 00118 } 00119 00120 template<typename _CharT, typename _Traits, typename _Alloc> 00121 template <typename _InIterator> 00122 _CharT* 00123 basic_string<_CharT, _Traits, _Alloc>:: 00124 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 00125 forward_iterator_tag) 00126 { 00127 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 00128 if (__beg == __end && __a == _Alloc()) 00129 return _S_empty_rep()._M_refdata(); 00130 #endif 00131 // NB: Not required, but considered best practice. 00132 if (__builtin_expect(__gnu_cxx::__is_null_pointer(__beg) 00133 && __beg != __end, 0)) 00134 __throw_logic_error(__N("basic_string::_S_construct NULL not valid")); 00135 00136 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 00137 __end)); 00138 // Check for out_of_range and length_error exceptions. 00139 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 00140 __try 00141 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 00142 __catch(...) 00143 { 00144 __r->_M_destroy(__a); 00145 __throw_exception_again; 00146 } 00147 __r->_M_set_length_and_sharable(__dnew); 00148 return __r->_M_refdata(); 00149 } 00150 00151 template<typename _CharT, typename _Traits, typename _Alloc> 00152 _CharT* 00153 basic_string<_CharT, _Traits, _Alloc>:: 00154 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 00155 { 00156 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 00157 if (__n == 0 && __a == _Alloc()) 00158 return _S_empty_rep()._M_refdata(); 00159 #endif 00160 // Check for out_of_range and length_error exceptions. 00161 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 00162 if (__n) 00163 _M_assign(__r->_M_refdata(), __n, __c); 00164 00165 __r->_M_set_length_and_sharable(__n); 00166 return __r->_M_refdata(); 00167 } 00168 00169 template<typename _CharT, typename _Traits, typename _Alloc> 00170 basic_string<_CharT, _Traits, _Alloc>:: 00171 basic_string(const basic_string& __str) 00172 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 00173 __str.get_allocator()), 00174 __str.get_allocator()) 00175 { } 00176 00177 template<typename _CharT, typename _Traits, typename _Alloc> 00178 basic_string<_CharT, _Traits, _Alloc>:: 00179 basic_string(const _Alloc& __a) 00180 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 00181 { } 00182 00183 template<typename _CharT, typename _Traits, typename _Alloc> 00184 basic_string<_CharT, _Traits, _Alloc>:: 00185 basic_string(const basic_string& __str, size_type __pos, size_type __n) 00186 : _M_dataplus(_S_construct(__str._M_data() 00187 + __str._M_check(__pos, 00188 "basic_string::basic_string"), 00189 __str._M_data() + __str._M_limit(__pos, __n) 00190 + __pos, _Alloc()), _Alloc()) 00191 { } 00192 00193 template<typename _CharT, typename _Traits, typename _Alloc> 00194 basic_string<_CharT, _Traits, _Alloc>:: 00195 basic_string(const basic_string& __str, size_type __pos, 00196 size_type __n, const _Alloc& __a) 00197 : _M_dataplus(_S_construct(__str._M_data() 00198 + __str._M_check(__pos, 00199 "basic_string::basic_string"), 00200 __str._M_data() + __str._M_limit(__pos, __n) 00201 + __pos, __a), __a) 00202 { } 00203 00204 // TBD: DPG annotate 00205 template<typename _CharT, typename _Traits, typename _Alloc> 00206 basic_string<_CharT, _Traits, _Alloc>:: 00207 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00208 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00209 { } 00210 00211 // TBD: DPG annotate 00212 template<typename _CharT, typename _Traits, typename _Alloc> 00213 basic_string<_CharT, _Traits, _Alloc>:: 00214 basic_string(const _CharT* __s, const _Alloc& __a) 00215 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00216 __s + npos, __a), __a) 00217 { } 00218 00219 template<typename _CharT, typename _Traits, typename _Alloc> 00220 basic_string<_CharT, _Traits, _Alloc>:: 00221 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00222 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00223 { } 00224 00225 // TBD: DPG annotate 00226 template<typename _CharT, typename _Traits, typename _Alloc> 00227 template<typename _InputIterator> 00228 basic_string<_CharT, _Traits, _Alloc>:: 00229 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 00230 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00231 { } 00232 00233 #ifdef __GXX_EXPERIMENTAL_CXX0X__ 00234 template<typename _CharT, typename _Traits, typename _Alloc> 00235 basic_string<_CharT, _Traits, _Alloc>:: 00236 basic_string(initializer_list<_CharT> __l, const _Alloc& __a) 00237 : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a) 00238 { } 00239 #endif 00240 00241 template<typename _CharT, typename _Traits, typename _Alloc> 00242 basic_string<_CharT, _Traits, _Alloc>& 00243 basic_string<_CharT, _Traits, _Alloc>:: 00244 assign(const basic_string& __str) 00245 { 00246 if (_M_rep() != __str._M_rep()) 00247 { 00248 // XXX MT 00249 const allocator_type __a = this->get_allocator(); 00250 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00251 _M_rep()->_M_dispose(__a); 00252 _M_data(__tmp); 00253 } 00254 return *this; 00255 } 00256 00257 template<typename _CharT, typename _Traits, typename _Alloc> 00258 basic_string<_CharT, _Traits, _Alloc>& 00259 basic_string<_CharT, _Traits, _Alloc>:: 00260 assign(const _CharT* __s, size_type __n) 00261 { 00262 __glibcxx_requires_string_len(__s, __n); 00263 _M_check_length(this->size(), __n, "basic_string::assign"); 00264 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00265 return _M_replace_safe(size_type(0), this->size(), __s, __n); 00266 else 00267 { 00268 // Work in-place. 00269 const size_type __pos = __s - _M_data(); 00270 if (__pos >= __n) 00271 _M_copy(_M_data(), __s, __n); 00272 else if (__pos) 00273 _M_move(_M_data(), __s, __n); 00274 _M_rep()->_M_set_length_and_sharable(__n); 00275 return *this; 00276 } 00277 } 00278 00279 template<typename _CharT, typename _Traits, typename _Alloc> 00280 basic_string<_CharT, _Traits, _Alloc>& 00281 basic_string<_CharT, _Traits, _Alloc>:: 00282 append(size_type __n, _CharT __c) 00283 { 00284 if (__n) 00285 { 00286 _M_check_length(size_type(0), __n, "basic_string::append"); 00287 const size_type __len = __n + this->size(); 00288 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00289 this->reserve(__len); 00290 _M_assign(_M_data() + this->size(), __n, __c); 00291 _M_rep()->_M_set_length_and_sharable(__len); 00292 } 00293 return *this; 00294 } 00295 00296 template<typename _CharT, typename _Traits, typename _Alloc> 00297 basic_string<_CharT, _Traits, _Alloc>& 00298 basic_string<_CharT, _Traits, _Alloc>:: 00299 append(const _CharT* __s, size_type __n) 00300 { 00301 __glibcxx_requires_string_len(__s, __n); 00302 if (__n) 00303 { 00304 _M_check_length(size_type(0), __n, "basic_string::append"); 00305 const size_type __len = __n + this->size(); 00306 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00307 { 00308 if (_M_disjunct(__s)) 00309 this->reserve(__len); 00310 else 00311 { 00312 const size_type __off = __s - _M_data(); 00313 this->reserve(__len); 00314 __s = _M_data() + __off; 00315 } 00316 } 00317 _M_copy(_M_data() + this->size(), __s, __n); 00318 _M_rep()->_M_set_length_and_sharable(__len); 00319 } 00320 return *this; 00321 } 00322 00323 template<typename _CharT, typename _Traits, typename _Alloc> 00324 basic_string<_CharT, _Traits, _Alloc>& 00325 basic_string<_CharT, _Traits, _Alloc>:: 00326 append(const basic_string& __str) 00327 { 00328 const size_type __size = __str.size(); 00329 if (__size) 00330 { 00331 const size_type __len = __size + this->size(); 00332 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00333 this->reserve(__len); 00334 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 00335 _M_rep()->_M_set_length_and_sharable(__len); 00336 } 00337 return *this; 00338 } 00339 00340 template<typename _CharT, typename _Traits, typename _Alloc> 00341 basic_string<_CharT, _Traits, _Alloc>& 00342 basic_string<_CharT, _Traits, _Alloc>:: 00343 append(const basic_string& __str, size_type __pos, size_type __n) 00344 { 00345 __str._M_check(__pos, "basic_string::append"); 00346 __n = __str._M_limit(__pos, __n); 00347 if (__n) 00348 { 00349 const size_type __len = __n + this->size(); 00350 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 00351 this->reserve(__len); 00352 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 00353 _M_rep()->_M_set_length_and_sharable(__len); 00354 } 00355 return *this; 00356 } 00357 00358 template<typename _CharT, typename _Traits, typename _Alloc> 00359 basic_string<_CharT, _Traits, _Alloc>& 00360 basic_string<_CharT, _Traits, _Alloc>:: 00361 insert(size_type __pos, const _CharT* __s, size_type __n) 00362 { 00363 __glibcxx_requires_string_len(__s, __n); 00364 _M_check(__pos, "basic_string::insert"); 00365 _M_check_length(size_type(0), __n, "basic_string::insert"); 00366 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00367 return _M_replace_safe(__pos, size_type(0), __s, __n); 00368 else 00369 { 00370 // Work in-place. 00371 const size_type __off = __s - _M_data(); 00372 _M_mutate(__pos, 0, __n); 00373 __s = _M_data() + __off; 00374 _CharT* __p = _M_data() + __pos; 00375 if (__s + __n <= __p) 00376 _M_copy(__p, __s, __n); 00377 else if (__s >= __p) 00378 _M_copy(__p, __s + __n, __n); 00379 else 00380 { 00381 const size_type __nleft = __p - __s; 00382 _M_copy(__p, __s, __nleft); 00383 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 00384 } 00385 return *this; 00386 } 00387 } 00388 00389 template<typename _CharT, typename _Traits, typename _Alloc> 00390 typename basic_string<_CharT, _Traits, _Alloc>::iterator 00391 basic_string<_CharT, _Traits, _Alloc>:: 00392 erase(iterator __first, iterator __last) 00393 { 00394 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 00395 && __last <= _M_iend()); 00396 00397 // NB: This isn't just an optimization (bail out early when 00398 // there is nothing to do, really), it's also a correctness 00399 // issue vs MT, see libstdc++/40518. 00400 const size_type __size = __last - __first; 00401 if (__size) 00402 { 00403 const size_type __pos = __first - _M_ibegin(); 00404 _M_mutate(__pos, __size, size_type(0)); 00405 _M_rep()->_M_set_leaked(); 00406 return iterator(_M_data() + __pos); 00407 } 00408 else 00409 return __first; 00410 } 00411 00412 template<typename _CharT, typename _Traits, typename _Alloc> 00413 basic_string<_CharT, _Traits, _Alloc>& 00414 basic_string<_CharT, _Traits, _Alloc>:: 00415 replace(size_type __pos, size_type __n1, const _CharT* __s, 00416 size_type __n2) 00417 { 00418 __glibcxx_requires_string_len(__s, __n2); 00419 _M_check(__pos, "basic_string::replace"); 00420 __n1 = _M_limit(__pos, __n1); 00421 _M_check_length(__n1, __n2, "basic_string::replace"); 00422 bool __left; 00423 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 00424 return _M_replace_safe(__pos, __n1, __s, __n2); 00425 else if ((__left = __s + __n2 <= _M_data() + __pos) 00426 || _M_data() + __pos + __n1 <= __s) 00427 { 00428 // Work in-place: non-overlapping case. 00429 size_type __off = __s - _M_data(); 00430 __left ? __off : (__off += __n2 - __n1); 00431 _M_mutate(__pos, __n1, __n2); 00432 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 00433 return *this; 00434 } 00435 else 00436 { 00437 // Todo: overlapping case. 00438 const basic_string __tmp(__s, __n2); 00439 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 00440 } 00441 } 00442 00443 template<typename _CharT, typename _Traits, typename _Alloc> 00444 void 00445 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00446 _M_destroy(const _Alloc& __a) throw () 00447 { 00448 const size_type __size = sizeof(_Rep_base) + 00449 (this->_M_capacity + 1) * sizeof(_CharT); 00450 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00451 } 00452 00453 template<typename _CharT, typename _Traits, typename _Alloc> 00454 void 00455 basic_string<_CharT, _Traits, _Alloc>:: 00456 _M_leak_hard() 00457 { 00458 #ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 00459 if (_M_rep() == &_S_empty_rep()) 00460 return; 00461 #endif 00462 if (_M_rep()->_M_is_shared()) 00463 _M_mutate(0, 0, 0); 00464 _M_rep()->_M_set_leaked(); 00465 } 00466 00467 template<typename _CharT, typename _Traits, typename _Alloc> 00468 void 00469 basic_string<_CharT, _Traits, _Alloc>:: 00470 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00471 { 00472 const size_type __old_size = this->size(); 00473 const size_type __new_size = __old_size + __len2 - __len1; 00474 const size_type __how_much = __old_size - __pos - __len1; 00475 00476 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 00477 { 00478 // Must reallocate. 00479 const allocator_type __a = get_allocator(); 00480 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 00481 00482 if (__pos) 00483 _M_copy(__r->_M_refdata(), _M_data(), __pos); 00484 if (__how_much) 00485 _M_copy(__r->_M_refdata() + __pos + __len2, 00486 _M_data() + __pos + __len1, __how_much); 00487 00488 _M_rep()->_M_dispose(__a); 00489 _M_data(__r->_M_refdata()); 00490 } 00491 else if (__how_much && __len1 != __len2) 00492 { 00493 // Work in-place. 00494 _M_move(_M_data() + __pos + __len2, 00495 _M_data() + __pos + __len1, __how_much); 00496 } 00497 _M_rep()->_M_set_length_and_sharable(__new_size); 00498 } 00499 00500 template<typename _CharT, typename _Traits, typename _Alloc> 00501 void 00502 basic_string<_CharT, _Traits, _Alloc>:: 00503 reserve(size_type __res) 00504 { 00505 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 00506 { 00507 // Make sure we don't shrink below the current size 00508 if (__res < this->size()) 00509 __res = this->size(); 00510 const allocator_type __a = get_allocator(); 00511 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00512 _M_rep()->_M_dispose(__a); 00513 _M_data(__tmp); 00514 } 00515 } 00516 00517 template<typename _CharT, typename _Traits, typename _Alloc> 00518 void 00519 basic_string<_CharT, _Traits, _Alloc>:: 00520 swap(basic_string& __s) 00521 { 00522 if (_M_rep()->_M_is_leaked()) 00523 _M_rep()->_M_set_sharable(); 00524 if (__s._M_rep()->_M_is_leaked()) 00525 __s._M_rep()->_M_set_sharable(); 00526 if (this->get_allocator() == __s.get_allocator()) 00527 { 00528 _CharT* __tmp = _M_data(); 00529 _M_data(__s._M_data()); 00530 __s._M_data(__tmp); 00531 } 00532 // The code below can usually be optimized away. 00533 else 00534 { 00535 const basic_string __tmp1(_M_ibegin(), _M_iend(), 00536 __s.get_allocator()); 00537 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00538 this->get_allocator()); 00539 *this = __tmp2; 00540 __s = __tmp1; 00541 } 00542 } 00543 00544 template<typename _CharT, typename _Traits, typename _Alloc> 00545 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00546 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00547 _S_create(size_type __capacity, size_type __old_capacity, 00548 const _Alloc& __alloc) 00549 { 00550 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00551 // 83. String::npos vs. string::max_size() 00552 if (__capacity > _S_max_size) 00553 __throw_length_error(__N("basic_string::_S_create")); 00554 00555 // The standard places no restriction on allocating more memory 00556 // than is strictly needed within this layer at the moment or as 00557 // requested by an explicit application call to reserve(). 00558 00559 // Many malloc implementations perform quite poorly when an 00560 // application attempts to allocate memory in a stepwise fashion 00561 // growing each allocation size by only 1 char. Additionally, 00562 // it makes little sense to allocate less linear memory than the 00563 // natural blocking size of the malloc implementation. 00564 // Unfortunately, we would need a somewhat low-level calculation 00565 // with tuned parameters to get this perfect for any particular 00566 // malloc implementation. Fortunately, generalizations about 00567 // common features seen among implementations seems to suffice. 00568 00569 // __pagesize need not match the actual VM page size for good 00570 // results in practice, thus we pick a common value on the low 00571 // side. __malloc_header_size is an estimate of the amount of 00572 // overhead per memory allocation (in practice seen N * sizeof 00573 // (void*) where N is 0, 2 or 4). According to folklore, 00574 // picking this value on the high side is better than 00575 // low-balling it (especially when this algorithm is used with 00576 // malloc implementations that allocate memory blocks rounded up 00577 // to a size which is a power of 2). 00578 const size_type __pagesize = 4096; 00579 const size_type __malloc_header_size = 4 * sizeof(void*); 00580 00581 // The below implements an exponential growth policy, necessary to 00582 // meet amortized linear time requirements of the library: see 00583 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00584 // It's active for allocations requiring an amount of memory above 00585 // system pagesize. This is consistent with the requirements of the 00586 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 00587 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 00588 __capacity = 2 * __old_capacity; 00589 00590 // NB: Need an array of char_type[__capacity], plus a terminating 00591 // null char_type() element, plus enough for the _Rep data structure. 00592 // Whew. Seemingly so needy, yet so elemental. 00593 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00594 00595 const size_type __adj_size = __size + __malloc_header_size; 00596 if (__adj_size > __pagesize && __capacity > __old_capacity) 00597 { 00598 const size_type __extra = __pagesize - __adj_size % __pagesize; 00599 __capacity += __extra / sizeof(_CharT); 00600 // Never allocate a string bigger than _S_max_size. 00601 if (__capacity > _S_max_size) 00602 __capacity = _S_max_size; 00603 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00604 } 00605 00606 // NB: Might throw, but no worries about a leak, mate: _Rep() 00607 // does not throw. 00608 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 00609 _Rep *__p = new (__place) _Rep; 00610 __p->_M_capacity = __capacity; 00611 // ABI compatibility - 3.4.x set in _S_create both 00612 // _M_refcount and _M_length. All callers of _S_create 00613 // in basic_string.tcc then set just _M_length. 00614 // In 4.0.x and later both _M_refcount and _M_length 00615 // are initialized in the callers, unfortunately we can 00616 // have 3.4.x compiled code with _S_create callers inlined 00617 // calling 4.0.x+ _S_create. 00618 __p->_M_set_sharable(); 00619 return __p; 00620 } 00621 00622 template<typename _CharT, typename _Traits, typename _Alloc> 00623 _CharT* 00624 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00625 _M_clone(const _Alloc& __alloc, size_type __res) 00626 { 00627 // Requested capacity of the clone. 00628 const size_type __requested_cap = this->_M_length + __res; 00629 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 00630 __alloc); 00631 if (this->_M_length) 00632 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 00633 00634 __r->_M_set_length_and_sharable(this->_M_length); 00635 return __r->_M_refdata(); 00636 } 00637 00638 template<typename _CharT, typename _Traits, typename _Alloc> 00639 void 00640 basic_string<_CharT, _Traits, _Alloc>:: 00641 resize(size_type __n, _CharT __c) 00642 { 00643 const size_type __size = this->size(); 00644 _M_check_length(__size, __n, "basic_string::resize"); 00645 if (__size < __n) 00646 this->append(__n - __size, __c); 00647 else if (__n < __size) 00648 this->erase(__n); 00649 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 00650 } 00651 00652 template<typename _CharT, typename _Traits, typename _Alloc> 00653 template<typename _InputIterator> 00654 basic_string<_CharT, _Traits, _Alloc>& 00655 basic_string<_CharT, _Traits, _Alloc>:: 00656 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 00657 _InputIterator __k2, __false_type) 00658 { 00659 const basic_string __s(__k1, __k2); 00660 const size_type __n1 = __i2 - __i1; 00661 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 00662 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 00663 __s.size()); 00664 } 00665 00666 template<typename _CharT, typename _Traits, typename _Alloc> 00667 basic_string<_CharT, _Traits, _Alloc>& 00668 basic_string<_CharT, _Traits, _Alloc>:: 00669 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 00670 _CharT __c) 00671 { 00672 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 00673 _M_mutate(__pos1, __n1, __n2); 00674 if (__n2) 00675 _M_assign(_M_data() + __pos1, __n2, __c); 00676 return *this; 00677 } 00678 00679 template<typename _CharT, typename _Traits, typename _Alloc> 00680 basic_string<_CharT, _Traits, _Alloc>& 00681 basic_string<_CharT, _Traits, _Alloc>:: 00682 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 00683 size_type __n2) 00684 { 00685 _M_mutate(__pos1, __n1, __n2); 00686 if (__n2) 00687 _M_copy(_M_data() + __pos1, __s, __n2); 00688 return *this; 00689 } 00690 00691 template<typename _CharT, typename _Traits, typename _Alloc> 00692 basic_string<_CharT, _Traits, _Alloc> 00693 operator+(const _CharT* __lhs, 00694 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00695 { 00696 __glibcxx_requires_string(__lhs); 00697 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00698 typedef typename __string_type::size_type __size_type; 00699 const __size_type __len = _Traits::length(__lhs); 00700 __string_type __str; 00701 __str.reserve(__len + __rhs.size()); 00702 __str.append(__lhs, __len); 00703 __str.append(__rhs); 00704 return __str; 00705 } 00706 00707 template<typename _CharT, typename _Traits, typename _Alloc> 00708 basic_string<_CharT, _Traits, _Alloc> 00709 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00710 { 00711 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00712 typedef typename __string_type::size_type __size_type; 00713 __string_type __str; 00714 const __size_type __len = __rhs.size(); 00715 __str.reserve(__len + 1); 00716 __str.append(__size_type(1), __lhs); 00717 __str.append(__rhs); 00718 return __str; 00719 } 00720 00721 template<typename _CharT, typename _Traits, typename _Alloc> 00722 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00723 basic_string<_CharT, _Traits, _Alloc>:: 00724 copy(_CharT* __s, size_type __n, size_type __pos) const 00725 { 00726 _M_check(__pos, "basic_string::copy"); 00727 __n = _M_limit(__pos, __n); 00728 __glibcxx_requires_string_len(__s, __n); 00729 if (__n) 00730 _M_copy(__s, _M_data() + __pos, __n); 00731 // 21.3.5.7 par 3: do not append null. (good.) 00732 return __n; 00733 } 00734 00735 template<typename _CharT, typename _Traits, typename _Alloc> 00736 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00737 basic_string<_CharT, _Traits, _Alloc>:: 00738 find(const _CharT* __s, size_type __pos, size_type __n) const 00739 { 00740 __glibcxx_requires_string_len(__s, __n); 00741 const size_type __size = this->size(); 00742 const _CharT* __data = _M_data(); 00743 00744 if (__n == 0) 00745 return __pos <= __size ? __pos : npos; 00746 00747 if (__n <= __size) 00748 { 00749 for (; __pos <= __size - __n; ++__pos) 00750 if (traits_type::eq(__data[__pos], __s[0]) 00751 && traits_type::compare(__data + __pos + 1, 00752 __s + 1, __n - 1) == 0) 00753 return __pos; 00754 } 00755 return npos; 00756 } 00757 00758 template<typename _CharT, typename _Traits, typename _Alloc> 00759 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00760 basic_string<_CharT, _Traits, _Alloc>:: 00761 find(_CharT __c, size_type __pos) const 00762 { 00763 size_type __ret = npos; 00764 const size_type __size = this->size(); 00765 if (__pos < __size) 00766 { 00767 const _CharT* __data = _M_data(); 00768 const size_type __n = __size - __pos; 00769 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 00770 if (__p) 00771 __ret = __p - __data; 00772 } 00773 return __ret; 00774 } 00775 00776 template<typename _CharT, typename _Traits, typename _Alloc> 00777 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00778 basic_string<_CharT, _Traits, _Alloc>:: 00779 rfind(const _CharT* __s, size_type __pos, size_type __n) const 00780 { 00781 __glibcxx_requires_string_len(__s, __n); 00782 const size_type __size = this->size(); 00783 if (__n <= __size) 00784 { 00785 __pos = std::min(size_type(__size - __n), __pos); 00786 const _CharT* __data = _M_data(); 00787 do 00788 { 00789 if (traits_type::compare(__data + __pos, __s, __n) == 0) 00790 return __pos; 00791 } 00792 while (__pos-- > 0); 00793 } 00794 return npos; 00795 } 00796 00797 template<typename _CharT, typename _Traits, typename _Alloc> 00798 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00799 basic_string<_CharT, _Traits, _Alloc>:: 00800 rfind(_CharT __c, size_type __pos) const 00801 { 00802 size_type __size = this->size(); 00803 if (__size) 00804 { 00805 if (--__size > __pos) 00806 __size = __pos; 00807 for (++__size; __size-- > 0; ) 00808 if (traits_type::eq(_M_data()[__size], __c)) 00809 return __size; 00810 } 00811 return npos; 00812 } 00813 00814 template<typename _CharT, typename _Traits, typename _Alloc> 00815 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00816 basic_string<_CharT, _Traits, _Alloc>:: 00817 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 00818 { 00819 __glibcxx_requires_string_len(__s, __n); 00820 for (; __n && __pos < this->size(); ++__pos) 00821 { 00822 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 00823 if (__p) 00824 return __pos; 00825 } 00826 return npos; 00827 } 00828 00829 template<typename _CharT, typename _Traits, typename _Alloc> 00830 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00831 basic_string<_CharT, _Traits, _Alloc>:: 00832 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 00833 { 00834 __glibcxx_requires_string_len(__s, __n); 00835 size_type __size = this->size(); 00836 if (__size && __n) 00837 { 00838 if (--__size > __pos) 00839 __size = __pos; 00840 do 00841 { 00842 if (traits_type::find(__s, __n, _M_data()[__size])) 00843 return __size; 00844 } 00845 while (__size-- != 0); 00846 } 00847 return npos; 00848 } 00849 00850 template<typename _CharT, typename _Traits, typename _Alloc> 00851 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00852 basic_string<_CharT, _Traits, _Alloc>:: 00853 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00854 { 00855 __glibcxx_requires_string_len(__s, __n); 00856 for (; __pos < this->size(); ++__pos) 00857 if (!traits_type::find(__s, __n, _M_data()[__pos])) 00858 return __pos; 00859 return npos; 00860 } 00861 00862 template<typename _CharT, typename _Traits, typename _Alloc> 00863 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00864 basic_string<_CharT, _Traits, _Alloc>:: 00865 find_first_not_of(_CharT __c, size_type __pos) const 00866 { 00867 for (; __pos < this->size(); ++__pos) 00868 if (!traits_type::eq(_M_data()[__pos], __c)) 00869 return __pos; 00870 return npos; 00871 } 00872 00873 template<typename _CharT, typename _Traits, typename _Alloc> 00874 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00875 basic_string<_CharT, _Traits, _Alloc>:: 00876 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00877 { 00878 __glibcxx_requires_string_len(__s, __n); 00879 size_type __size = this->size(); 00880 if (__size) 00881 { 00882 if (--__size > __pos) 00883 __size = __pos; 00884 do 00885 { 00886 if (!traits_type::find(__s, __n, _M_data()[__size])) 00887 return __size; 00888 } 00889 while (__size--); 00890 } 00891 return npos; 00892 } 00893 00894 template<typename _CharT, typename _Traits, typename _Alloc> 00895 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00896 basic_string<_CharT, _Traits, _Alloc>:: 00897 find_last_not_of(_CharT __c, size_type __pos) const 00898 { 00899 size_type __size = this->size(); 00900 if (__size) 00901 { 00902 if (--__size > __pos) 00903 __size = __pos; 00904 do 00905 { 00906 if (!traits_type::eq(_M_data()[__size], __c)) 00907 return __size; 00908 } 00909 while (__size--); 00910 } 00911 return npos; 00912 } 00913 00914 template<typename _CharT, typename _Traits, typename _Alloc> 00915 int 00916 basic_string<_CharT, _Traits, _Alloc>:: 00917 compare(size_type __pos, size_type __n, const basic_string& __str) const 00918 { 00919 _M_check(__pos, "basic_string::compare"); 00920 __n = _M_limit(__pos, __n); 00921 const size_type __osize = __str.size(); 00922 const size_type __len = std::min(__n, __osize); 00923 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 00924 if (!__r) 00925 __r = _S_compare(__n, __osize); 00926 return __r; 00927 } 00928 00929 template<typename _CharT, typename _Traits, typename _Alloc> 00930 int 00931 basic_string<_CharT, _Traits, _Alloc>:: 00932 compare(size_type __pos1, size_type __n1, const basic_string& __str, 00933 size_type __pos2, size_type __n2) const 00934 { 00935 _M_check(__pos1, "basic_string::compare"); 00936 __str._M_check(__pos2, "basic_string::compare"); 00937 __n1 = _M_limit(__pos1, __n1); 00938 __n2 = __str._M_limit(__pos2, __n2); 00939 const size_type __len = std::min(__n1, __n2); 00940 int __r = traits_type::compare(_M_data() + __pos1, 00941 __str.data() + __pos2, __len); 00942 if (!__r) 00943 __r = _S_compare(__n1, __n2); 00944 return __r; 00945 } 00946 00947 template<typename _CharT, typename _Traits, typename _Alloc> 00948 int 00949 basic_string<_CharT, _Traits, _Alloc>:: 00950 compare(const _CharT* __s) const 00951 { 00952 __glibcxx_requires_string(__s); 00953 const size_type __size = this->size(); 00954 const size_type __osize = traits_type::length(__s); 00955 const size_type __len = std::min(__size, __osize); 00956 int __r = traits_type::compare(_M_data(), __s, __len); 00957 if (!__r) 00958 __r = _S_compare(__size, __osize); 00959 return __r; 00960 } 00961 00962 template<typename _CharT, typename _Traits, typename _Alloc> 00963 int 00964 basic_string <_CharT, _Traits, _Alloc>:: 00965 compare(size_type __pos, size_type __n1, const _CharT* __s) const 00966 { 00967 __glibcxx_requires_string(__s); 00968 _M_check(__pos, "basic_string::compare"); 00969 __n1 = _M_limit(__pos, __n1); 00970 const size_type __osize = traits_type::length(__s); 00971 const size_type __len = std::min(__n1, __osize); 00972 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 00973 if (!__r) 00974 __r = _S_compare(__n1, __osize); 00975 return __r; 00976 } 00977 00978 template<typename _CharT, typename _Traits, typename _Alloc> 00979 int 00980 basic_string <_CharT, _Traits, _Alloc>:: 00981 compare(size_type __pos, size_type __n1, const _CharT* __s, 00982 size_type __n2) const 00983 { 00984 __glibcxx_requires_string_len(__s, __n2); 00985 _M_check(__pos, "basic_string::compare"); 00986 __n1 = _M_limit(__pos, __n1); 00987 const size_type __len = std::min(__n1, __n2); 00988 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 00989 if (!__r) 00990 __r = _S_compare(__n1, __n2); 00991 return __r; 00992 } 00993 00994 // 21.3.7.9 basic_string::getline and operators 00995 template<typename _CharT, typename _Traits, typename _Alloc> 00996 basic_istream<_CharT, _Traits>& 00997 operator>>(basic_istream<_CharT, _Traits>& __in, 00998 basic_string<_CharT, _Traits, _Alloc>& __str) 00999 { 01000 typedef basic_istream<_CharT, _Traits> __istream_type; 01001 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01002 typedef typename __istream_type::ios_base __ios_base; 01003 typedef typename __istream_type::int_type __int_type; 01004 typedef typename __string_type::size_type __size_type; 01005 typedef ctype<_CharT> __ctype_type; 01006 typedef typename __ctype_type::ctype_base __ctype_base; 01007 01008 __size_type __extracted = 0; 01009 typename __ios_base::iostate __err = __ios_base::goodbit; 01010 typename __istream_type::sentry __cerb(__in, false); 01011 if (__cerb) 01012 { 01013 __try 01014 { 01015 // Avoid reallocation for common case. 01016 __str.erase(); 01017 _CharT __buf[128]; 01018 __size_type __len = 0; 01019 const streamsize __w = __in.width(); 01020 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 01021 : __str.max_size(); 01022 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 01023 const __int_type __eof = _Traits::eof(); 01024 __int_type __c = __in.rdbuf()->sgetc(); 01025 01026 while (__extracted < __n 01027 && !_Traits::eq_int_type(__c, __eof) 01028 && !__ct.is(__ctype_base::space, 01029 _Traits::to_char_type(__c))) 01030 { 01031 if (__len == sizeof(__buf) / sizeof(_CharT)) 01032 { 01033 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 01034 __len = 0; 01035 } 01036 __buf[__len++] = _Traits::to_char_type(__c); 01037 ++__extracted; 01038 __c = __in.rdbuf()->snextc(); 01039 } 01040 __str.append(__buf, __len); 01041 01042 if (_Traits::eq_int_type(__c, __eof)) 01043 __err |= __ios_base::eofbit; 01044 __in.width(0); 01045 } 01046 __catch(__cxxabiv1::__forced_unwind&) 01047 { 01048 __in._M_setstate(__ios_base::badbit); 01049 __throw_exception_again; 01050 } 01051 __catch(...) 01052 { 01053 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01054 // 91. Description of operator>> and getline() for string<> 01055 // might cause endless loop 01056 __in._M_setstate(__ios_base::badbit); 01057 } 01058 } 01059 // 211. operator>>(istream&, string&) doesn't set failbit 01060 if (!__extracted) 01061 __err |= __ios_base::failbit; 01062 if (__err) 01063 __in.setstate(__err); 01064 return __in; 01065 } 01066 01067 template<typename _CharT, typename _Traits, typename _Alloc> 01068 basic_istream<_CharT, _Traits>& 01069 getline(basic_istream<_CharT, _Traits>& __in, 01070 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 01071 { 01072 typedef basic_istream<_CharT, _Traits> __istream_type; 01073 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 01074 typedef typename __istream_type::ios_base __ios_base; 01075 typedef typename __istream_type::int_type __int_type; 01076 typedef typename __string_type::size_type __size_type; 01077 01078 __size_type __extracted = 0; 01079 const __size_type __n = __str.max_size(); 01080 typename __ios_base::iostate __err = __ios_base::goodbit; 01081 typename __istream_type::sentry __cerb(__in, true); 01082 if (__cerb) 01083 { 01084 __try 01085 { 01086 __str.erase(); 01087 const __int_type __idelim = _Traits::to_int_type(__delim); 01088 const __int_type __eof = _Traits::eof(); 01089 __int_type __c = __in.rdbuf()->sgetc(); 01090 01091 while (__extracted < __n 01092 && !_Traits::eq_int_type(__c, __eof) 01093 && !_Traits::eq_int_type(__c, __idelim)) 01094 { 01095 __str += _Traits::to_char_type(__c); 01096 ++__extracted; 01097 __c = __in.rdbuf()->snextc(); 01098 } 01099 01100 if (_Traits::eq_int_type(__c, __eof)) 01101 __err |= __ios_base::eofbit; 01102 else if (_Traits::eq_int_type(__c, __idelim)) 01103 { 01104 ++__extracted; 01105 __in.rdbuf()->sbumpc(); 01106 } 01107 else 01108 __err |= __ios_base::failbit; 01109 } 01110 __catch(__cxxabiv1::__forced_unwind&) 01111 { 01112 __in._M_setstate(__ios_base::badbit); 01113 __throw_exception_again; 01114 } 01115 __catch(...) 01116 { 01117 // _GLIBCXX_RESOLVE_LIB_DEFECTS 01118 // 91. Description of operator>> and getline() for string<> 01119 // might cause endless loop 01120 __in._M_setstate(__ios_base::badbit); 01121 } 01122 } 01123 if (!__extracted) 01124 __err |= __ios_base::failbit; 01125 if (__err) 01126 __in.setstate(__err); 01127 return __in; 01128 } 01129 01130 // Inhibit implicit instantiations for required instantiations, 01131 // which are defined via explicit instantiations elsewhere. 01132 // NB: This syntax is a GNU extension. 01133 #if _GLIBCXX_EXTERN_TEMPLATE > 0 01134 extern template class basic_string<char>; 01135 extern template 01136 basic_istream<char>& 01137 operator>>(basic_istream<char>&, string&); 01138 extern template 01139 basic_ostream<char>& 01140 operator<<(basic_ostream<char>&, const string&); 01141 extern template 01142 basic_istream<char>& 01143 getline(basic_istream<char>&, string&, char); 01144 extern template 01145 basic_istream<char>& 01146 getline(basic_istream<char>&, string&); 01147 01148 #ifdef _GLIBCXX_USE_WCHAR_T 01149 extern template class basic_string<wchar_t>; 01150 extern template 01151 basic_istream<wchar_t>& 01152 operator>>(basic_istream<wchar_t>&, wstring&); 01153 extern template 01154 basic_ostream<wchar_t>& 01155 operator<<(basic_ostream<wchar_t>&, const wstring&); 01156 extern template 01157 basic_istream<wchar_t>& 01158 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 01159 extern template 01160 basic_istream<wchar_t>& 01161 getline(basic_istream<wchar_t>&, wstring&); 01162 #endif 01163 #endif 01164 01165 _GLIBCXX_END_NAMESPACE 01166 01167 #endif