basic_string.tcc

00001 // Components for manipulating sequences of characters -*- C++ -*- 00002 00003 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 00004 // Free Software Foundation, Inc. 00005 // 00006 // This file is part of the GNU ISO C++ Library. This library is free 00007 // software; you can redistribute it and/or modify it under the 00008 // terms of the GNU General Public License as published by the 00009 // Free Software Foundation; either version 2, or (at your option) 00010 // any later version. 00011 00012 // This library is distributed in the hope that it will be useful, 00013 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00015 // GNU General Public License for more details. 00016 00017 // You should have received a copy of the GNU General Public License along 00018 // with this library; see the file COPYING. If not, write to the Free 00019 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00020 // USA. 00021 00022 // As a special exception, you may use this file as part of a free software 00023 // library without restriction. Specifically, if other files instantiate 00024 // templates or use macros or inline functions from this file, or you compile 00025 // this file and link it with other files to produce an executable, this 00026 // file does not by itself cause the resulting executable to be covered by 00027 // the GNU General Public License. This exception does not however 00028 // invalidate any other reasons why the executable file might be covered by 00029 // the GNU General Public License. 00030 00031 // 00032 // ISO C++ 14882: 21 Strings library 00033 // 00034 00035 // This file is included by <string>. It is not meant to be included 00036 // separately. 00037 00038 // Written by Jason Merrill based upon the specification by Takanori Adachi 00039 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 00040 00041 #ifndef _CPP_BITS_STRING_TCC 00042 #define _CPP_BITS_STRING_TCC 1 00043 00044 #pragma GCC system_header 00045 00046 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))/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>::_S_empty_rep_storage[ 00067 (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)]; 00068 00069 // NB: This is the special case for Input Iterators, used in 00070 // istreambuf_iterators, etc. 00071 // Input Iterators have a cost structure very different from 00072 // pointers, calling for a different coding style. 00073 template<typename _CharT, typename _Traits, typename _Alloc> 00074 template<typename _InIter> 00075 _CharT* 00076 basic_string<_CharT, _Traits, _Alloc>:: 00077 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 00078 input_iterator_tag) 00079 { 00080 if (__beg == __end && __a == _Alloc()) 00081 return _S_empty_rep()._M_refcopy(); 00082 // Avoid reallocation for common case. 00083 _CharT __buf[100]; 00084 size_type __i = 0; 00085 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT)) 00086 { 00087 __buf[__i++] = *__beg; 00088 ++__beg; 00089 } 00090 _Rep* __r = _Rep::_S_create(__i, __a); 00091 traits_type::copy(__r->_M_refdata(), __buf, __i); 00092 __r->_M_length = __i; 00093 try 00094 { 00095 // NB: this loop looks precisely this way because 00096 // it avoids comparing __beg != __end any more 00097 // than strictly necessary; != might be expensive! 00098 for (;;) 00099 { 00100 _CharT* __p = __r->_M_refdata() + __r->_M_length; 00101 _CharT* __last = __r->_M_refdata() + __r->_M_capacity; 00102 for (;;) 00103 { 00104 if (__beg == __end) 00105 { 00106 __r->_M_length = __p - __r->_M_refdata(); 00107 *__p = _Rep::_S_terminal; // grrr. 00108 return __r->_M_refdata(); 00109 } 00110 if (__p == __last) 00111 break; 00112 *__p++ = *__beg; 00113 ++__beg; 00114 } 00115 // Allocate more space. 00116 size_type __len = __p - __r->_M_refdata(); 00117 _Rep* __another = _Rep::_S_create(__len + 1, __a); 00118 traits_type::copy(__another->_M_refdata(), 00119 __r->_M_refdata(), __len); 00120 __r->_M_destroy(__a); 00121 __r = __another; 00122 __r->_M_length = __len; 00123 } 00124 } 00125 catch(...) 00126 { 00127 __r->_M_destroy(__a); 00128 __throw_exception_again; 00129 } 00130 return 0; 00131 } 00132 00133 template<typename _CharT, typename _Traits, typename _Alloc> 00134 template <class _InIter> 00135 _CharT* 00136 basic_string<_CharT, _Traits, _Alloc>:: 00137 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 00138 forward_iterator_tag) 00139 { 00140 if (__beg == __end && __a == _Alloc()) 00141 return _S_empty_rep()._M_refcopy(); 00142 00143 // NB: Not required, but considered best practice. 00144 if (__builtin_expect(__beg == _InIter(), 0)) 00145 __throw_logic_error("attempt to create string with null pointer"); 00146 00147 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 00148 00149 // Check for out_of_range and length_error exceptions. 00150 _Rep* __r = _Rep::_S_create(__dnew, __a); 00151 try 00152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 00153 catch(...) 00154 { 00155 __r->_M_destroy(__a); 00156 __throw_exception_again; 00157 } 00158 __r->_M_length = __dnew; 00159 00160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr. 00161 return __r->_M_refdata(); 00162 } 00163 00164 template<typename _CharT, typename _Traits, typename _Alloc> 00165 _CharT* 00166 basic_string<_CharT, _Traits, _Alloc>:: 00167 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 00168 { 00169 if (__n == 0 && __a == _Alloc()) 00170 return _S_empty_rep()._M_refcopy(); 00171 00172 // Check for out_of_range and length_error exceptions. 00173 _Rep* __r = _Rep::_S_create(__n, __a); 00174 try 00175 { 00176 if (__n) 00177 traits_type::assign(__r->_M_refdata(), __n, __c); 00178 } 00179 catch(...) 00180 { 00181 __r->_M_destroy(__a); 00182 __throw_exception_again; 00183 } 00184 __r->_M_length = __n; 00185 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr 00186 return __r->_M_refdata(); 00187 } 00188 00189 template<typename _CharT, typename _Traits, typename _Alloc> 00190 basic_string<_CharT, _Traits, _Alloc>:: 00191 basic_string(const basic_string& __str) 00192 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()), 00193 __str.get_allocator()) 00194 { } 00195 00196 template<typename _CharT, typename _Traits, typename _Alloc> 00197 basic_string<_CharT, _Traits, _Alloc>:: 00198 basic_string(const _Alloc& __a) 00199 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 00200 { } 00201 00202 template<typename _CharT, typename _Traits, typename _Alloc> 00203 basic_string<_CharT, _Traits, _Alloc>:: 00204 basic_string(const basic_string& __str, size_type __pos, size_type __n) 00205 : _M_dataplus(_S_construct(__str._M_check(__pos), 00206 __str._M_fold(__pos, __n), _Alloc()), _Alloc()) 00207 { } 00208 00209 template<typename _CharT, typename _Traits, typename _Alloc> 00210 basic_string<_CharT, _Traits, _Alloc>:: 00211 basic_string(const basic_string& __str, size_type __pos, 00212 size_type __n, const _Alloc& __a) 00213 : _M_dataplus(_S_construct(__str._M_check(__pos), 00214 __str._M_fold(__pos, __n), __a), __a) 00215 { } 00216 00217 template<typename _CharT, typename _Traits, typename _Alloc> 00218 basic_string<_CharT, _Traits, _Alloc>:: 00219 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 00220 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 00221 { } 00222 00223 template<typename _CharT, typename _Traits, typename _Alloc> 00224 basic_string<_CharT, _Traits, _Alloc>:: 00225 basic_string(const _CharT* __s, const _Alloc& __a) 00226 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 00227 __s + npos, __a), __a) 00228 { } 00229 00230 template<typename _CharT, typename _Traits, typename _Alloc> 00231 basic_string<_CharT, _Traits, _Alloc>:: 00232 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 00233 : _M_dataplus(_S_construct(__n, __c, __a), __a) 00234 { } 00235 00236 template<typename _CharT, typename _Traits, typename _Alloc> 00237 template<typename _InputIter> 00238 basic_string<_CharT, _Traits, _Alloc>:: 00239 basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a) 00240 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 00241 { } 00242 00243 template<typename _CharT, typename _Traits, typename _Alloc> 00244 basic_string<_CharT, _Traits, _Alloc>& 00245 basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str) 00246 { 00247 if (_M_rep() != __str._M_rep()) 00248 { 00249 // XXX MT 00250 allocator_type __a = this->get_allocator(); 00251 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 00252 _M_rep()->_M_dispose(__a); 00253 _M_data(__tmp); 00254 } 00255 return *this; 00256 } 00257 00258 template<typename _CharT, typename _Traits, typename _Alloc> 00259 basic_string<_CharT, _Traits, _Alloc>& 00260 basic_string<_CharT, _Traits, _Alloc>:: 00261 assign(const basic_string& __str, size_type __pos, size_type __n) 00262 { 00263 const size_type __strsize = __str.size(); 00264 if (__pos > __strsize) 00265 __throw_out_of_range("basic_string::assign"); 00266 const bool __testn = __n < __strsize - __pos; 00267 const size_type __newsize = __testn ? __n : __strsize - __pos; 00268 return this->assign(__str._M_data() + __pos, __newsize); 00269 } 00270 00271 template<typename _CharT, typename _Traits, typename _Alloc> 00272 basic_string<_CharT, _Traits, _Alloc>& 00273 basic_string<_CharT, _Traits, _Alloc>:: 00274 assign(const _CharT* __s, size_type __n) 00275 { 00276 if (__n > this->max_size()) 00277 __throw_length_error("basic_string::assign"); 00278 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 00279 || less<const _CharT*>()(_M_data() + this->size(), __s)) 00280 return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n); 00281 else 00282 { 00283 // Work in-place 00284 const size_type __pos = __s - _M_data(); 00285 if (__pos >= __n) 00286 traits_type::copy(_M_data(), __s, __n); 00287 else if (__pos) 00288 traits_type::move(_M_data(), __s, __n); 00289 _M_rep()->_M_length = __n; 00290 _M_data()[__n] = _Rep::_S_terminal; // grr. 00291 return *this; 00292 } 00293 } 00294 00295 template<typename _CharT, typename _Traits, typename _Alloc> 00296 basic_string<_CharT, _Traits, _Alloc>& 00297 basic_string<_CharT, _Traits, _Alloc>:: 00298 insert(size_type __pos1, const basic_string& __str, 00299 size_type __pos2, size_type __n) 00300 { 00301 const size_type __strsize = __str.size(); 00302 if (__pos2 > __strsize) 00303 __throw_out_of_range("basic_string::insert"); 00304 const bool __testn = __n < __strsize - __pos2; 00305 const size_type __newsize = __testn ? __n : __strsize - __pos2; 00306 return this->insert(__pos1, __str._M_data() + __pos2, __newsize); 00307 } 00308 00309 template<typename _CharT, typename _Traits, typename _Alloc> 00310 basic_string<_CharT, _Traits, _Alloc>& 00311 basic_string<_CharT, _Traits, _Alloc>:: 00312 insert(size_type __pos, const _CharT* __s, size_type __n) 00313 { 00314 const size_type __size = this->size(); 00315 if (__pos > __size) 00316 __throw_out_of_range("basic_string::insert"); 00317 if (__size > this->max_size() - __n) 00318 __throw_length_error("basic_string::insert"); 00319 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 00320 || less<const _CharT*>()(_M_data() + __size, __s)) 00321 return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos, 00322 __s, __s + __n); 00323 else 00324 { 00325 // Work in-place. If _M_mutate reallocates the string, __s 00326 // does not point anymore to valid data, therefore we save its 00327 // offset, then we restore it. 00328 const size_type __off = __s - _M_data(); 00329 _M_mutate(__pos, 0, __n); 00330 __s = _M_data() + __off; 00331 _CharT* __p = _M_data() + __pos; 00332 if (__s + __n <= __p) 00333 traits_type::copy(__p, __s, __n); 00334 else if (__s >= __p) 00335 traits_type::copy(__p, __s + __n, __n); 00336 else 00337 { 00338 traits_type::copy(__p, __s, __p - __s); 00339 traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s)); 00340 } 00341 return *this; 00342 } 00343 } 00344 00345 template<typename _CharT, typename _Traits, typename _Alloc> 00346 basic_string<_CharT, _Traits, _Alloc>& 00347 basic_string<_CharT, _Traits, _Alloc>:: 00348 replace(size_type __pos, size_type __n1, const _CharT* __s, 00349 size_type __n2) 00350 { 00351 const size_type __size = this->size(); 00352 if (__pos > __size) 00353 __throw_out_of_range("basic_string::replace"); 00354 const bool __testn1 = __n1 < __size - __pos; 00355 const size_type __foldn1 = __testn1 ? __n1 : __size - __pos; 00356 if (__size - __foldn1 > this->max_size() - __n2) 00357 __throw_length_error("basic_string::replace"); 00358 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 00359 || less<const _CharT*>()(_M_data() + __size, __s)) 00360 return _M_replace_safe(_M_ibegin() + __pos, 00361 _M_ibegin() + __pos + __foldn1, __s, __s + __n2); 00362 // Todo: optimized in-place replace. 00363 else 00364 return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1, 00365 __s, __s + __n2, 00366 typename iterator_traits<const _CharT*>::iterator_category()); 00367 } 00368 00369 template<typename _CharT, typename _Traits, typename _Alloc> 00370 void 00371 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00372 _M_destroy(const _Alloc& __a) throw () 00373 { 00374 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT); 00375 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 00376 } 00377 00378 template<typename _CharT, typename _Traits, typename _Alloc> 00379 void 00380 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard() 00381 { 00382 if (_M_rep()->_M_is_shared()) 00383 _M_mutate(0, 0, 0); 00384 _M_rep()->_M_set_leaked(); 00385 } 00386 00387 // _M_mutate and, below, _M_clone, include, in the same form, an exponential 00388 // growth policy, necessary to meet amortized linear time requirements of 00389 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00390 // The policy is active for allocations requiring an amount of memory above 00391 // system pagesize. This is consistent with the requirements of the standard: 00392 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 00393 template<typename _CharT, typename _Traits, typename _Alloc> 00394 void 00395 basic_string<_CharT, _Traits, _Alloc>:: 00396 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 00397 { 00398 size_type __old_size = this->size(); 00399 const size_type __new_size = __old_size + __len2 - __len1; 00400 const _CharT* __src = _M_data() + __pos + __len1; 00401 const size_type __how_much = __old_size - __pos - __len1; 00402 00403 if (_M_rep()->_M_is_shared() || __new_size > capacity()) 00404 { 00405 // Must reallocate. 00406 allocator_type __a = get_allocator(); 00407 // See below (_S_create) for the meaning and value of these 00408 // constants. 00409 const size_type __pagesize = 4096; 00410 const size_type __malloc_header_size = 4 * sizeof (void*); 00411 // The biggest string which fits in a memory page 00412 const size_type __page_capacity = (__pagesize - __malloc_header_size 00413 - sizeof(_Rep) - sizeof(_CharT)) 00414 / sizeof(_CharT); 00415 _Rep* __r; 00416 if (__new_size > capacity() && __new_size > __page_capacity) 00417 // Growing exponentially. 00418 __r = _Rep::_S_create(__new_size > 2*capacity() ? 00419 __new_size : 2*capacity(), __a); 00420 else 00421 __r = _Rep::_S_create(__new_size, __a); 00422 try 00423 { 00424 if (__pos) 00425 traits_type::copy(__r->_M_refdata(), _M_data(), __pos); 00426 if (__how_much) 00427 traits_type::copy(__r->_M_refdata() + __pos + __len2, 00428 __src, __how_much); 00429 } 00430 catch(...) 00431 { 00432 __r->_M_dispose(get_allocator()); 00433 __throw_exception_again; 00434 } 00435 _M_rep()->_M_dispose(__a); 00436 _M_data(__r->_M_refdata()); 00437 } 00438 else if (__how_much && __len1 != __len2) 00439 { 00440 // Work in-place 00441 traits_type::move(_M_data() + __pos + __len2, __src, __how_much); 00442 } 00443 _M_rep()->_M_set_sharable(); 00444 _M_rep()->_M_length = __new_size; 00445 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4) 00446 // You cannot leave those LWG people alone for a second. 00447 } 00448 00449 template<typename _CharT, typename _Traits, typename _Alloc> 00450 void 00451 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res) 00452 { 00453 if (__res > this->capacity() || _M_rep()->_M_is_shared()) 00454 { 00455 if (__res > this->max_size()) 00456 __throw_length_error("basic_string::reserve"); 00457 // Make sure we don't shrink below the current size 00458 if (__res < this->size()) 00459 __res = this->size(); 00460 allocator_type __a = get_allocator(); 00461 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 00462 _M_rep()->_M_dispose(__a); 00463 _M_data(__tmp); 00464 } 00465 } 00466 00467 template<typename _CharT, typename _Traits, typename _Alloc> 00468 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s) 00469 { 00470 if (_M_rep()->_M_is_leaked()) 00471 _M_rep()->_M_set_sharable(); 00472 if (__s._M_rep()->_M_is_leaked()) 00473 __s._M_rep()->_M_set_sharable(); 00474 if (this->get_allocator() == __s.get_allocator()) 00475 { 00476 _CharT* __tmp = _M_data(); 00477 _M_data(__s._M_data()); 00478 __s._M_data(__tmp); 00479 } 00480 // The code below can usually be optimized away. 00481 else 00482 { 00483 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator()); 00484 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 00485 this->get_allocator()); 00486 *this = __tmp2; 00487 __s = __tmp1; 00488 } 00489 } 00490 00491 template<typename _CharT, typename _Traits, typename _Alloc> 00492 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 00493 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00494 _S_create(size_t __capacity, const _Alloc& __alloc) 00495 { 00496 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00497 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS 00498 // 83. String::npos vs. string::max_size() 00499 if (__capacity > _S_max_size) 00500 #else 00501 if (__capacity == npos) 00502 #endif 00503 __throw_length_error("basic_string::_S_create"); 00504 00505 // NB: Need an array of char_type[__capacity], plus a 00506 // terminating null char_type() element, plus enough for the 00507 // _Rep data structure. Whew. Seemingly so needy, yet so elemental. 00508 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00509 00510 // The standard places no restriction on allocating more memory 00511 // than is strictly needed within this layer at the moment or as 00512 // requested by an explicit application call to reserve(). Many 00513 // malloc implementations perform quite poorly when an 00514 // application attempts to allocate memory in a stepwise fashion 00515 // growing each allocation size by only 1 char. Additionally, 00516 // it makes little sense to allocate less linear memory than the 00517 // natural blocking size of the malloc implementation. 00518 // Unfortunately, we would need a somewhat low-level calculation 00519 // with tuned parameters to get this perfect for any particular 00520 // malloc implementation. Fortunately, generalizations about 00521 // common features seen among implementations seems to suffice. 00522 00523 // __pagesize need not match the actual VM page size for good 00524 // results in practice, thus we pick a common value on the low 00525 // side. __malloc_header_size is an estimate of the amount of 00526 // overhead per memory allocation (in practice seen N * sizeof 00527 // (void*) where N is 0, 2 or 4). According to folklore, 00528 // picking this value on the high side is better than 00529 // low-balling it (especially when this algorithm is used with 00530 // malloc implementations that allocate memory blocks rounded up 00531 // to a size which is a power of 2). 00532 const size_t __pagesize = 4096; // must be 2^i * __subpagesize 00533 const size_t __subpagesize = 128; // should be >> __malloc_header_size 00534 const size_t __malloc_header_size = 4 * sizeof (void*); 00535 if ((__size + __malloc_header_size) > __pagesize) 00536 { 00537 size_t __extra = 00538 (__pagesize - ((__size + __malloc_header_size) % __pagesize)) 00539 % __pagesize; 00540 __capacity += __extra / sizeof(_CharT); 00541 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00542 } 00543 else if (__size > __subpagesize) 00544 { 00545 size_t __extra = 00546 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize)) 00547 % __subpagesize; 00548 __capacity += __extra / sizeof(_CharT); 00549 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 00550 } 00551 00552 // NB: Might throw, but no worries about a leak, mate: _Rep() 00553 // does not throw. 00554 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 00555 _Rep *__p = new (__place) _Rep; 00556 __p->_M_capacity = __capacity; 00557 __p->_M_set_sharable(); // One reference. 00558 __p->_M_length = 0; 00559 return __p; 00560 } 00561 00562 template<typename _CharT, typename _Traits, typename _Alloc> 00563 _CharT* 00564 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 00565 _M_clone(const _Alloc& __alloc, size_type __res) 00566 { 00567 // Requested capacity of the clone. 00568 const size_type __requested_cap = _M_length + __res; 00569 // See above (_S_create) for the meaning and value of these constants. 00570 const size_type __pagesize = 4096; 00571 const size_type __malloc_header_size = 4 * sizeof (void*); 00572 // The biggest string which fits in a memory page. 00573 const size_type __page_capacity = 00574 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT)) 00575 / sizeof(_CharT); 00576 _Rep* __r; 00577 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity) 00578 // Growing exponentially. 00579 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ? 00580 __requested_cap : 2*_M_capacity, __alloc); 00581 else 00582 __r = _Rep::_S_create(__requested_cap, __alloc); 00583 00584 if (_M_length) 00585 { 00586 try 00587 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); } 00588 catch(...) 00589 { 00590 __r->_M_destroy(__alloc); 00591 __throw_exception_again; 00592 } 00593 } 00594 __r->_M_length = _M_length; 00595 __r->_M_refdata()[_M_length] = _Rep::_S_terminal; 00596 return __r->_M_refdata(); 00597 } 00598 00599 template<typename _CharT, typename _Traits, typename _Alloc> 00600 void 00601 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c) 00602 { 00603 if (__n > max_size()) 00604 __throw_length_error("basic_string::resize"); 00605 size_type __size = this->size(); 00606 if (__size < __n) 00607 this->append(__n - __size, __c); 00608 else if (__n < __size) 00609 this->erase(__n); 00610 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 00611 } 00612 00613 // This is the general replace helper, which currently gets instantiated both 00614 // for input iterators and reverse iterators. It buffers internally and then 00615 // calls _M_replace_safe. 00616 template<typename _CharT, typename _Traits, typename _Alloc> 00617 template<typename _InputIter> 00618 basic_string<_CharT, _Traits, _Alloc>& 00619 basic_string<_CharT, _Traits, _Alloc>:: 00620 _M_replace(iterator __i1, iterator __i2, _InputIter __k1, 00621 _InputIter __k2, input_iterator_tag) 00622 { 00623 // Save concerned source string data in a temporary. 00624 basic_string __s(__k1, __k2); 00625 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend()); 00626 } 00627 00628 // This is a special replace helper, which does not buffer internally 00629 // and can be used in "safe" situations involving forward iterators, 00630 // i.e., when source and destination ranges are known to not overlap. 00631 template<typename _CharT, typename _Traits, typename _Alloc> 00632 template<typename _ForwardIter> 00633 basic_string<_CharT, _Traits, _Alloc>& 00634 basic_string<_CharT, _Traits, _Alloc>:: 00635 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1, 00636 _ForwardIter __k2) 00637 { 00638 size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2)); 00639 size_type __dold = __i2 - __i1; 00640 size_type __dmax = this->max_size(); 00641 00642 if (__dmax <= __dnew) 00643 __throw_length_error("basic_string::_M_replace"); 00644 size_type __off = __i1 - _M_ibegin(); 00645 _M_mutate(__off, __dold, __dnew); 00646 00647 // Invalidated __i1, __i2 00648 if (__dnew) 00649 _S_copy_chars(_M_data() + __off, __k1, __k2); 00650 00651 return *this; 00652 } 00653 00654 template<typename _CharT, typename _Traits, typename _Alloc> 00655 basic_string<_CharT, _Traits, _Alloc>& 00656 basic_string<_CharT, _Traits, _Alloc>:: 00657 replace(size_type __pos1, size_type __n1, const basic_string& __str, 00658 size_type __pos2, size_type __n2) 00659 { 00660 const size_type __strsize = __str.size(); 00661 if (__pos2 > __strsize) 00662 __throw_out_of_range("basic_string::replace"); 00663 const bool __testn2 = __n2 < __strsize - __pos2; 00664 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2; 00665 return this->replace(__pos1, __n1, 00666 __str._M_data() + __pos2, __foldn2); 00667 } 00668 00669 template<typename _CharT, typename _Traits, typename _Alloc> 00670 basic_string<_CharT, _Traits, _Alloc>& 00671 basic_string<_CharT, _Traits, _Alloc>:: 00672 append(const basic_string& __str) 00673 { 00674 // Iff appending itself, string needs to pre-reserve the 00675 // correct size so that _M_mutate does not clobber the 00676 // iterators formed here. 00677 size_type __size = __str.size(); 00678 size_type __len = __size + this->size(); 00679 if (__len > this->capacity()) 00680 this->reserve(__len); 00681 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(), 00682 __str._M_iend()); 00683 } 00684 00685 template<typename _CharT, typename _Traits, typename _Alloc> 00686 basic_string<_CharT, _Traits, _Alloc>& 00687 basic_string<_CharT, _Traits, _Alloc>:: 00688 append(const basic_string& __str, size_type __pos, size_type __n) 00689 { 00690 // Iff appending itself, string needs to pre-reserve the 00691 // correct size so that _M_mutate does not clobber the 00692 // iterators formed here. 00693 size_type __len = std::min(size_type(__str.size() - __pos), 00694 __n) + this->size(); 00695 if (__len > this->capacity()) 00696 this->reserve(__len); 00697 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos), 00698 __str._M_fold(__pos, __n)); 00699 } 00700 00701 template<typename _CharT, typename _Traits, typename _Alloc> 00702 basic_string<_CharT, _Traits, _Alloc>& 00703 basic_string<_CharT, _Traits, _Alloc>:: 00704 append(const _CharT* __s, size_type __n) 00705 { 00706 size_type __len = __n + this->size(); 00707 if (__len > this->capacity()) 00708 this->reserve(__len); 00709 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n); 00710 } 00711 00712 template<typename _CharT, typename _Traits, typename _Alloc> 00713 basic_string<_CharT, _Traits, _Alloc>& 00714 basic_string<_CharT, _Traits, _Alloc>:: 00715 append(size_type __n, _CharT __c) 00716 { 00717 size_type __len = __n + this->size(); 00718 if (__len > this->capacity()) 00719 this->reserve(__len); 00720 return this->replace(_M_iend(), _M_iend(), __n, __c); 00721 } 00722 00723 template<typename _CharT, typename _Traits, typename _Alloc> 00724 basic_string<_CharT, _Traits, _Alloc> 00725 operator+(const _CharT* __lhs, 00726 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00727 { 00728 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00729 typedef typename __string_type::size_type __size_type; 00730 __size_type __len = _Traits::length(__lhs); 00731 __string_type __str; 00732 __str.reserve(__len + __rhs.size()); 00733 __str.append(__lhs, __lhs + __len); 00734 __str.append(__rhs); 00735 return __str; 00736 } 00737 00738 template<typename _CharT, typename _Traits, typename _Alloc> 00739 basic_string<_CharT, _Traits, _Alloc> 00740 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 00741 { 00742 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 00743 typedef typename __string_type::size_type __size_type; 00744 __string_type __str; 00745 __size_type __len = __rhs.size(); 00746 __str.reserve(__len + 1); 00747 __str.append(__size_type(1), __lhs); 00748 __str.append(__rhs); 00749 return __str; 00750 } 00751 00752 template<typename _CharT, typename _Traits, typename _Alloc> 00753 basic_string<_CharT, _Traits, _Alloc>& 00754 basic_string<_CharT, _Traits, _Alloc>:: 00755 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c) 00756 { 00757 size_type __n1 = __i2 - __i1; 00758 size_type __off1 = __i1 - _M_ibegin(); 00759 if (max_size() - (this->size() - __n1) <= __n2) 00760 __throw_length_error("basic_string::replace"); 00761 _M_mutate (__off1, __n1, __n2); 00762 // Invalidated __i1, __i2 00763 if (__n2) 00764 traits_type::assign(_M_data() + __off1, __n2, __c); 00765 return *this; 00766 } 00767 00768 template<typename _CharT, typename _Traits, typename _Alloc> 00769 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00770 basic_string<_CharT, _Traits, _Alloc>:: 00771 copy(_CharT* __s, size_type __n, size_type __pos) const 00772 { 00773 if (__pos > this->size()) 00774 __throw_out_of_range("basic_string::copy"); 00775 00776 if (__n > this->size() - __pos) 00777 __n = this->size() - __pos; 00778 00779 traits_type::copy(__s, _M_data() + __pos, __n); 00780 // 21.3.5.7 par 3: do not append null. (good.) 00781 return __n; 00782 } 00783 00784 template<typename _CharT, typename _Traits, typename _Alloc> 00785 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00786 basic_string<_CharT, _Traits, _Alloc>:: 00787 find(const _CharT* __s, size_type __pos, size_type __n) const 00788 { 00789 size_type __size = this->size(); 00790 size_t __xpos = __pos; 00791 const _CharT* __data = _M_data(); 00792 for (; __xpos + __n <= __size; ++__xpos) 00793 if (traits_type::compare(__data + __xpos, __s, __n) == 0) 00794 return __xpos; 00795 return npos; 00796 } 00797 00798 template<typename _CharT, typename _Traits, typename _Alloc> 00799 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00800 basic_string<_CharT, _Traits, _Alloc>:: 00801 find(_CharT __c, size_type __pos) const 00802 { 00803 size_type __size = this->size(); 00804 size_type __ret = npos; 00805 if (__pos < __size) 00806 { 00807 const _CharT* __data = _M_data(); 00808 size_type __n = __size - __pos; 00809 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 00810 if (__p) 00811 __ret = __p - __data; 00812 } 00813 return __ret; 00814 } 00815 00816 00817 template<typename _CharT, typename _Traits, typename _Alloc> 00818 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00819 basic_string<_CharT, _Traits, _Alloc>:: 00820 rfind(const _CharT* __s, size_type __pos, size_type __n) const 00821 { 00822 size_type __size = this->size(); 00823 if (__n <= __size) 00824 { 00825 __pos = std::min(size_type(__size - __n), __pos); 00826 const _CharT* __data = _M_data(); 00827 do 00828 { 00829 if (traits_type::compare(__data + __pos, __s, __n) == 0) 00830 return __pos; 00831 } 00832 while (__pos-- > 0); 00833 } 00834 return npos; 00835 } 00836 00837 template<typename _CharT, typename _Traits, typename _Alloc> 00838 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00839 basic_string<_CharT, _Traits, _Alloc>:: 00840 rfind(_CharT __c, size_type __pos) const 00841 { 00842 size_type __size = this->size(); 00843 if (__size) 00844 { 00845 size_t __xpos = __size - 1; 00846 if (__xpos > __pos) 00847 __xpos = __pos; 00848 00849 for (++__xpos; __xpos-- > 0; ) 00850 if (traits_type::eq(_M_data()[__xpos], __c)) 00851 return __xpos; 00852 } 00853 return npos; 00854 } 00855 00856 template<typename _CharT, typename _Traits, typename _Alloc> 00857 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00858 basic_string<_CharT, _Traits, _Alloc>:: 00859 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 00860 { 00861 for (; __n && __pos < this->size(); ++__pos) 00862 { 00863 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 00864 if (__p) 00865 return __pos; 00866 } 00867 return npos; 00868 } 00869 00870 template<typename _CharT, typename _Traits, typename _Alloc> 00871 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00872 basic_string<_CharT, _Traits, _Alloc>:: 00873 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 00874 { 00875 size_type __size = this->size(); 00876 if (__size && __n) 00877 { 00878 if (--__size > __pos) 00879 __size = __pos; 00880 do 00881 { 00882 if (traits_type::find(__s, __n, _M_data()[__size])) 00883 return __size; 00884 } 00885 while (__size-- != 0); 00886 } 00887 return npos; 00888 } 00889 00890 template<typename _CharT, typename _Traits, typename _Alloc> 00891 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00892 basic_string<_CharT, _Traits, _Alloc>:: 00893 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00894 { 00895 size_t __xpos = __pos; 00896 for (; __xpos < this->size(); ++__xpos) 00897 if (!traits_type::find(__s, __n, _M_data()[__xpos])) 00898 return __xpos; 00899 return npos; 00900 } 00901 00902 template<typename _CharT, typename _Traits, typename _Alloc> 00903 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00904 basic_string<_CharT, _Traits, _Alloc>:: 00905 find_first_not_of(_CharT __c, size_type __pos) const 00906 { 00907 size_t __xpos = __pos; 00908 for (; __xpos < this->size(); ++__xpos) 00909 if (!traits_type::eq(_M_data()[__xpos], __c)) 00910 return __xpos; 00911 return npos; 00912 } 00913 00914 template<typename _CharT, typename _Traits, typename _Alloc> 00915 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00916 basic_string<_CharT, _Traits, _Alloc>:: 00917 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 00918 { 00919 size_type __size = this->size(); 00920 if (__size) 00921 { 00922 if (--__size > __pos) 00923 __size = __pos; 00924 do 00925 { 00926 if (!traits_type::find(__s, __n, _M_data()[__size])) 00927 return __size; 00928 } 00929 while (__size--); 00930 } 00931 return npos; 00932 } 00933 00934 template<typename _CharT, typename _Traits, typename _Alloc> 00935 typename basic_string<_CharT, _Traits, _Alloc>::size_type 00936 basic_string<_CharT, _Traits, _Alloc>:: 00937 find_last_not_of(_CharT __c, size_type __pos) const 00938 { 00939 size_type __size = this->size(); 00940 if (__size) 00941 { 00942 if (--__size > __pos) 00943 __size = __pos; 00944 do 00945 { 00946 if (!traits_type::eq(_M_data()[__size], __c)) 00947 return __size; 00948 } 00949 while (__size--); 00950 } 00951 return npos; 00952 } 00953 00954 template<typename _CharT, typename _Traits, typename _Alloc> 00955 int 00956 basic_string<_CharT, _Traits, _Alloc>:: 00957 compare(size_type __pos, size_type __n, const basic_string& __str) const 00958 { 00959 size_type __size = this->size(); 00960 size_type __osize = __str.size(); 00961 if (__pos > __size) 00962 __throw_out_of_range("basic_string::compare"); 00963 00964 size_type __rsize= std::min(size_type(__size - __pos), __n); 00965 size_type __len = std::min(__rsize, __osize); 00966 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 00967 if (!__r) 00968 __r = __rsize - __osize; 00969 return __r; 00970 } 00971 00972 template<typename _CharT, typename _Traits, typename _Alloc> 00973 int 00974 basic_string<_CharT, _Traits, _Alloc>:: 00975 compare(size_type __pos1, size_type __n1, const basic_string& __str, 00976 size_type __pos2, size_type __n2) const 00977 { 00978 size_type __size = this->size(); 00979 size_type __osize = __str.size(); 00980 if (__pos1 > __size || __pos2 > __osize) 00981 __throw_out_of_range("basic_string::compare"); 00982 00983 size_type __rsize = std::min(size_type(__size - __pos1), __n1); 00984 size_type __rosize = std::min(size_type(__osize - __pos2), __n2); 00985 size_type __len = std::min(__rsize, __rosize); 00986 int __r = traits_type::compare(_M_data() + __pos1, 00987 __str.data() + __pos2, __len); 00988 if (!__r) 00989 __r = __rsize - __rosize; 00990 return __r; 00991 } 00992 00993 00994 template<typename _CharT, typename _Traits, typename _Alloc> 00995 int 00996 basic_string<_CharT, _Traits, _Alloc>:: 00997 compare(const _CharT* __s) const 00998 { 00999 size_type __size = this->size(); 01000 size_type __osize = traits_type::length(__s); 01001 size_type __len = std::min(__size, __osize); 01002 int __r = traits_type::compare(_M_data(), __s, __len); 01003 if (!__r) 01004 __r = __size - __osize; 01005 return __r; 01006 } 01007 01008 01009 template<typename _CharT, typename _Traits, typename _Alloc> 01010 int 01011 basic_string <_CharT, _Traits, _Alloc>:: 01012 compare(size_type __pos, size_type __n1, const _CharT* __s) const 01013 { 01014 size_type __size = this->size(); 01015 if (__pos > __size) 01016 __throw_out_of_range("basic_string::compare"); 01017 01018 size_type __osize = traits_type::length(__s); 01019 size_type __rsize = std::min(size_type(__size - __pos), __n1); 01020 size_type __len = std::min(__rsize, __osize); 01021 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01022 if (!__r) 01023 __r = __rsize - __osize; 01024 return __r; 01025 } 01026 01027 template<typename _CharT, typename _Traits, typename _Alloc> 01028 int 01029 basic_string <_CharT, _Traits, _Alloc>:: 01030 compare(size_type __pos, size_type __n1, const _CharT* __s, 01031 size_type __n2) const 01032 { 01033 size_type __size = this->size(); 01034 if (__pos > __size) 01035 __throw_out_of_range("basic_string::compare"); 01036 01037 size_type __rsize = std::min(size_type(__size - __pos), __n1); 01038 size_type __len = std::min(__rsize, __n2); 01039 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 01040 if (!__r) 01041 __r = __rsize - __n2; 01042 return __r; 01043 } 01044 01045 template <class _CharT, class _Traits, class _Alloc> 01046 void 01047 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str, 01048 _CharT* __buf, typename _Alloc::size_type __bufsiz) 01049 { 01050 typedef typename _Alloc::size_type size_type; 01051 size_type __strsize = __str.size(); 01052 size_type __bytes = std::min(__strsize, __bufsiz - 1); 01053 _Traits::copy(__buf, __str.data(), __bytes); 01054 __buf[__bytes] = _CharT(); 01055 } 01056 01057 // Inhibit implicit instantiations for required instantiations, 01058 // which are defined via explicit instantiations elsewhere. 01059 // NB: This syntax is a GNU extension. 01060 #if _GLIBCPP_EXTERN_TEMPLATE 01061 extern template class basic_string<char>; 01062 extern template 01063 basic_istream<char>& 01064 operator>>(basic_istream<char>&, string&); 01065 extern template 01066 basic_ostream<char>& 01067 operator<<(basic_ostream<char>&, const string&); 01068 extern template 01069 basic_istream<char>& 01070 getline(basic_istream<char>&, string&, char); 01071 extern template 01072 basic_istream<char>& 01073 getline(basic_istream<char>&, string&); 01074 01075 #ifdef _GLIBCPP_USE_WCHAR_T 01076 extern template class basic_string<wchar_t>; 01077 extern template 01078 basic_istream<wchar_t>& 01079 operator>>(basic_istream<wchar_t>&, wstring&); 01080 extern template 01081 basic_ostream<wchar_t>& 01082 operator<<(basic_ostream<wchar_t>&, const wstring&); 01083 extern template 01084 basic_istream<wchar_t>& 01085 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 01086 extern template 01087 basic_istream<wchar_t>& 01088 getline(basic_istream<wchar_t>&, wstring&); 01089 #endif 01090 #endif 01091 } // namespace std 01092 01093 #endif

Generated on Wed Aug 4 21:43:08 2004 for libstdc++-v3 Source by doxygen 1.3.8