1 // Components for manipulating sequences of characters -*- C++ -*- 2 3 // Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003 4 // Free Software Foundation, Inc. 5 // 6 // This file is part of the GNU ISO C++ Library. This library is free 7 // software; you can redistribute it and/or modify it under the 8 // terms of the GNU General Public License as published by the 9 // Free Software Foundation; either version 2, or (at your option) 10 // any later version. 11 12 // This library is distributed in the hope that it will be useful, 13 // but WITHOUT ANY WARRANTY; without even the implied warranty of 14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 // GNU General Public License for more details. 16 17 // You should have received a copy of the GNU General Public License along 18 // with this library; see the file COPYING. If not, write to the Free 19 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 20 // USA. 21 22 // As a special exception, you may use this file as part of a free software 23 // library without restriction. Specifically, if other files instantiate 24 // templates or use macros or inline functions from this file, or you compile 25 // this file and link it with other files to produce an executable, this 26 // file does not by itself cause the resulting executable to be covered by 27 // the GNU General Public License. This exception does not however 28 // invalidate any other reasons why the executable file might be covered by 29 // the GNU General Public License. 30 31 // 32 // ISO C++ 14882: 21 Strings library 33 // 34 35 // This file is included by <string>. It is not meant to be included 36 // separately. 37 38 // Written by Jason Merrill based upon the specification by Takanori Adachi 39 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 40 41 #ifndef _CPP_BITS_STRING_TCC 42 #define _CPP_BITS_STRING_TCC 1 43 44 #pragma GCC system_header 45 46 namespace std 47 { 48 template<typename _CharT, typename _Traits, typename _Alloc> 49 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 50 basic_string<_CharT, _Traits, _Alloc>:: 51 _Rep::_S_max_size = (((npos - sizeof(_Rep))/sizeof(_CharT)) - 1) / 4; 52 53 template<typename _CharT, typename _Traits, typename _Alloc> 54 const _CharT 55 basic_string<_CharT, _Traits, _Alloc>:: 56 _Rep::_S_terminal = _CharT(); 57 58 template<typename _CharT, typename _Traits, typename _Alloc> 59 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 60 basic_string<_CharT, _Traits, _Alloc>::npos; 61 62 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 63 // at static init time (before static ctors are run). 64 template<typename _CharT, typename _Traits, typename _Alloc> 65 typename basic_string<_CharT, _Traits, _Alloc>::size_type 66 basic_string<_CharT, _Traits, _Alloc>::_S_empty_rep_storage[ 67 (sizeof(_Rep) + sizeof(_CharT) + sizeof(size_type) - 1)/sizeof(size_type)]; 68 69 // NB: This is the special case for Input Iterators, used in 70 // istreambuf_iterators, etc. 71 // Input Iterators have a cost structure very different from 72 // pointers, calling for a different coding style. 73 template<typename _CharT, typename _Traits, typename _Alloc> 74 template<typename _InIter> 75 _CharT* 76 basic_string<_CharT, _Traits, _Alloc>:: _S_construct(_InIter __beg,_InIter __end,const _Alloc & __a,input_iterator_tag)77 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 78 input_iterator_tag) 79 { 80 if (__beg == __end && __a == _Alloc()) 81 return _S_empty_rep()._M_refcopy(); 82 // Avoid reallocation for common case. 83 _CharT __buf[100]; 84 size_type __i = 0; 85 while (__beg != __end && __i < sizeof(__buf) / sizeof(_CharT)) 86 { 87 __buf[__i++] = *__beg; 88 ++__beg; 89 } 90 _Rep* __r = _Rep::_S_create(__i, __a); 91 traits_type::copy(__r->_M_refdata(), __buf, __i); 92 __r->_M_length = __i; 93 try 94 { 95 // NB: this loop looks precisely this way because 96 // it avoids comparing __beg != __end any more 97 // than strictly necessary; != might be expensive! 98 for (;;) 99 { 100 _CharT* __p = __r->_M_refdata() + __r->_M_length; 101 _CharT* __last = __r->_M_refdata() + __r->_M_capacity; 102 for (;;) 103 { 104 if (__beg == __end) 105 { 106 __r->_M_length = __p - __r->_M_refdata(); 107 *__p = _Rep::_S_terminal; // grrr. 108 return __r->_M_refdata(); 109 } 110 if (__p == __last) 111 break; 112 *__p++ = *__beg; 113 ++__beg; 114 } 115 // Allocate more space. 116 size_type __len = __p - __r->_M_refdata(); 117 _Rep* __another = _Rep::_S_create(__len + 1, __a); 118 traits_type::copy(__another->_M_refdata(), 119 __r->_M_refdata(), __len); 120 __r->_M_destroy(__a); 121 __r = __another; 122 __r->_M_length = __len; 123 } 124 } 125 catch(...) 126 { 127 __r->_M_destroy(__a); 128 __throw_exception_again; 129 } 130 return 0; 131 } 132 133 template<typename _CharT, typename _Traits, typename _Alloc> 134 template <class _InIter> 135 _CharT* 136 basic_string<_CharT, _Traits, _Alloc>:: _S_construct(_InIter __beg,_InIter __end,const _Alloc & __a,forward_iterator_tag)137 _S_construct(_InIter __beg, _InIter __end, const _Alloc& __a, 138 forward_iterator_tag) 139 { 140 if (__beg == __end && __a == _Alloc()) 141 return _S_empty_rep()._M_refcopy(); 142 143 // NB: Not required, but considered best practice. 144 if (__builtin_expect(__beg == _InIter(), 0)) 145 __throw_logic_error("attempt to create string with null pointer"); 146 147 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 148 149 // Check for out_of_range and length_error exceptions. 150 _Rep* __r = _Rep::_S_create(__dnew, __a); 151 try 152 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 153 catch(...) 154 { 155 __r->_M_destroy(__a); 156 __throw_exception_again; 157 } 158 __r->_M_length = __dnew; 159 160 __r->_M_refdata()[__dnew] = _Rep::_S_terminal; // grrr. 161 return __r->_M_refdata(); 162 } 163 164 template<typename _CharT, typename _Traits, typename _Alloc> 165 _CharT* 166 basic_string<_CharT, _Traits, _Alloc>:: 167 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 168 { 169 if (__n == 0 && __a == _Alloc()) 170 return _S_empty_rep()._M_refcopy(); 171 172 // Check for out_of_range and length_error exceptions. 173 _Rep* __r = _Rep::_S_create(__n, __a); 174 try 175 { 176 if (__n) 177 traits_type::assign(__r->_M_refdata(), __n, __c); 178 } 179 catch(...) 180 { 181 __r->_M_destroy(__a); 182 __throw_exception_again; 183 } 184 __r->_M_length = __n; 185 __r->_M_refdata()[__n] = _Rep::_S_terminal; // grrr 186 return __r->_M_refdata(); 187 } 188 189 template<typename _CharT, typename _Traits, typename _Alloc> 190 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const basic_string & __str)191 basic_string(const basic_string& __str) 192 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(), __str.get_allocator()), 193 __str.get_allocator()) 194 { } 195 196 template<typename _CharT, typename _Traits, typename _Alloc> 197 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const _Alloc & __a)198 basic_string(const _Alloc& __a) 199 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 200 { } 201 202 template<typename _CharT, typename _Traits, typename _Alloc> 203 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const basic_string & __str,size_type __pos,size_type __n)204 basic_string(const basic_string& __str, size_type __pos, size_type __n) 205 : _M_dataplus(_S_construct(__str._M_check(__pos), 206 __str._M_fold(__pos, __n), _Alloc()), _Alloc()) 207 { } 208 209 template<typename _CharT, typename _Traits, typename _Alloc> 210 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const basic_string & __str,size_type __pos,size_type __n,const _Alloc & __a)211 basic_string(const basic_string& __str, size_type __pos, 212 size_type __n, const _Alloc& __a) 213 : _M_dataplus(_S_construct(__str._M_check(__pos), 214 __str._M_fold(__pos, __n), __a), __a) 215 { } 216 217 template<typename _CharT, typename _Traits, typename _Alloc> 218 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const _CharT * __s,size_type __n,const _Alloc & __a)219 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 220 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 221 { } 222 223 template<typename _CharT, typename _Traits, typename _Alloc> 224 basic_string<_CharT, _Traits, _Alloc>:: basic_string(const _CharT * __s,const _Alloc & __a)225 basic_string(const _CharT* __s, const _Alloc& __a) 226 : _M_dataplus(_S_construct(__s, __s ? __s + traits_type::length(__s) : 227 __s + npos, __a), __a) 228 { } 229 230 template<typename _CharT, typename _Traits, typename _Alloc> 231 basic_string<_CharT, _Traits, _Alloc>:: basic_string(size_type __n,_CharT __c,const _Alloc & __a)232 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 233 : _M_dataplus(_S_construct(__n, __c, __a), __a) 234 { } 235 236 template<typename _CharT, typename _Traits, typename _Alloc> 237 template<typename _InputIter> 238 basic_string<_CharT, _Traits, _Alloc>:: basic_string(_InputIter __beg,_InputIter __end,const _Alloc & __a)239 basic_string(_InputIter __beg, _InputIter __end, const _Alloc& __a) 240 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 241 { } 242 243 template<typename _CharT, typename _Traits, typename _Alloc> 244 basic_string<_CharT, _Traits, _Alloc>& assign(const basic_string & __str)245 basic_string<_CharT, _Traits, _Alloc>::assign(const basic_string& __str) 246 { 247 if (_M_rep() != __str._M_rep()) 248 { 249 // XXX MT 250 allocator_type __a = this->get_allocator(); 251 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 252 _M_rep()->_M_dispose(__a); 253 _M_data(__tmp); 254 } 255 return *this; 256 } 257 258 template<typename _CharT, typename _Traits, typename _Alloc> 259 basic_string<_CharT, _Traits, _Alloc>& 260 basic_string<_CharT, _Traits, _Alloc>:: assign(const basic_string & __str,size_type __pos,size_type __n)261 assign(const basic_string& __str, size_type __pos, size_type __n) 262 { 263 const size_type __strsize = __str.size(); 264 if (__pos > __strsize) 265 __throw_out_of_range("basic_string::assign"); 266 const bool __testn = __n < __strsize - __pos; 267 const size_type __newsize = __testn ? __n : __strsize - __pos; 268 return this->assign(__str._M_data() + __pos, __newsize); 269 } 270 271 template<typename _CharT, typename _Traits, typename _Alloc> 272 basic_string<_CharT, _Traits, _Alloc>& 273 basic_string<_CharT, _Traits, _Alloc>:: assign(const _CharT * __s,size_type __n)274 assign(const _CharT* __s, size_type __n) 275 { 276 if (__n > this->max_size()) 277 __throw_length_error("basic_string::assign"); 278 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 279 || less<const _CharT*>()(_M_data() + this->size(), __s)) 280 return _M_replace_safe(_M_ibegin(), _M_iend(), __s, __s + __n); 281 else 282 { 283 // Work in-place 284 const size_type __pos = __s - _M_data(); 285 if (__pos >= __n) 286 traits_type::copy(_M_data(), __s, __n); 287 else if (__pos) 288 traits_type::move(_M_data(), __s, __n); 289 _M_rep()->_M_length = __n; 290 _M_data()[__n] = _Rep::_S_terminal; // grr. 291 return *this; 292 } 293 } 294 295 template<typename _CharT, typename _Traits, typename _Alloc> 296 basic_string<_CharT, _Traits, _Alloc>& 297 basic_string<_CharT, _Traits, _Alloc>:: insert(size_type __pos1,const basic_string & __str,size_type __pos2,size_type __n)298 insert(size_type __pos1, const basic_string& __str, 299 size_type __pos2, size_type __n) 300 { 301 const size_type __strsize = __str.size(); 302 if (__pos2 > __strsize) 303 __throw_out_of_range("basic_string::insert"); 304 const bool __testn = __n < __strsize - __pos2; 305 const size_type __newsize = __testn ? __n : __strsize - __pos2; 306 return this->insert(__pos1, __str._M_data() + __pos2, __newsize); 307 } 308 309 template<typename _CharT, typename _Traits, typename _Alloc> 310 basic_string<_CharT, _Traits, _Alloc>& 311 basic_string<_CharT, _Traits, _Alloc>:: insert(size_type __pos,const _CharT * __s,size_type __n)312 insert(size_type __pos, const _CharT* __s, size_type __n) 313 { 314 const size_type __size = this->size(); 315 if (__pos > __size) 316 __throw_out_of_range("basic_string::insert"); 317 if (__size > this->max_size() - __n) 318 __throw_length_error("basic_string::insert"); 319 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 320 || less<const _CharT*>()(_M_data() + __size, __s)) 321 return _M_replace_safe(_M_ibegin() + __pos, _M_ibegin() + __pos, 322 __s, __s + __n); 323 else 324 { 325 // Work in-place. If _M_mutate reallocates the string, __s 326 // does not point anymore to valid data, therefore we save its 327 // offset, then we restore it. 328 const size_type __off = __s - _M_data(); 329 _M_mutate(__pos, 0, __n); 330 __s = _M_data() + __off; 331 _CharT* __p = _M_data() + __pos; 332 if (__s + __n <= __p) 333 traits_type::copy(__p, __s, __n); 334 else if (__s >= __p) 335 traits_type::copy(__p, __s + __n, __n); 336 else 337 { 338 traits_type::copy(__p, __s, __p - __s); 339 traits_type::copy(__p + (__p-__s), __p + __n, __n - (__p-__s)); 340 } 341 return *this; 342 } 343 } 344 345 template<typename _CharT, typename _Traits, typename _Alloc> 346 basic_string<_CharT, _Traits, _Alloc>& 347 basic_string<_CharT, _Traits, _Alloc>:: replace(size_type __pos,size_type __n1,const _CharT * __s,size_type __n2)348 replace(size_type __pos, size_type __n1, const _CharT* __s, 349 size_type __n2) 350 { 351 const size_type __size = this->size(); 352 if (__pos > __size) 353 __throw_out_of_range("basic_string::replace"); 354 const bool __testn1 = __n1 < __size - __pos; 355 const size_type __foldn1 = __testn1 ? __n1 : __size - __pos; 356 if (__size - __foldn1 > this->max_size() - __n2) 357 __throw_length_error("basic_string::replace"); 358 if (_M_rep()->_M_is_shared() || less<const _CharT*>()(__s, _M_data()) 359 || less<const _CharT*>()(_M_data() + __size, __s)) 360 return _M_replace_safe(_M_ibegin() + __pos, 361 _M_ibegin() + __pos + __foldn1, __s, __s + __n2); 362 // Todo: optimized in-place replace. 363 else 364 return _M_replace(_M_ibegin() + __pos, _M_ibegin() + __pos + __foldn1, 365 __s, __s + __n2, 366 typename iterator_traits<const _CharT*>::iterator_category()); 367 } 368 369 template<typename _CharT, typename _Traits, typename _Alloc> 370 void 371 basic_string<_CharT, _Traits, _Alloc>::_Rep:: _M_destroy(const _Alloc & __a)372 _M_destroy(const _Alloc& __a) throw () 373 { 374 size_type __size = sizeof(_Rep) + (_M_capacity + 1) * sizeof(_CharT); 375 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 376 } 377 378 template<typename _CharT, typename _Traits, typename _Alloc> 379 void _M_leak_hard()380 basic_string<_CharT, _Traits, _Alloc>::_M_leak_hard() 381 { 382 if (_M_rep()->_M_is_shared()) 383 _M_mutate(0, 0, 0); 384 _M_rep()->_M_set_leaked(); 385 } 386 387 // _M_mutate and, below, _M_clone, include, in the same form, an exponential 388 // growth policy, necessary to meet amortized linear time requirements of 389 // the library: see http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 390 // The policy is active for allocations requiring an amount of memory above 391 // system pagesize. This is consistent with the requirements of the standard: 392 // see, f.i., http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 393 template<typename _CharT, typename _Traits, typename _Alloc> 394 void 395 basic_string<_CharT, _Traits, _Alloc>:: _M_mutate(size_type __pos,size_type __len1,size_type __len2)396 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 397 { 398 size_type __old_size = this->size(); 399 const size_type __new_size = __old_size + __len2 - __len1; 400 const _CharT* __src = _M_data() + __pos + __len1; 401 const size_type __how_much = __old_size - __pos - __len1; 402 403 if (_M_rep()->_M_is_shared() || __new_size > capacity()) 404 { 405 // Must reallocate. 406 allocator_type __a = get_allocator(); 407 // See below (_S_create) for the meaning and value of these 408 // constants. 409 const size_type __pagesize = 4096; 410 const size_type __malloc_header_size = 4 * sizeof (void*); 411 // The biggest string which fits in a memory page 412 const size_type __page_capacity = (__pagesize - __malloc_header_size 413 - sizeof(_Rep) - sizeof(_CharT)) 414 / sizeof(_CharT); 415 _Rep* __r; 416 if (__new_size > capacity() && __new_size > __page_capacity) 417 // Growing exponentially. 418 __r = _Rep::_S_create(__new_size > 2*capacity() ? 419 __new_size : 2*capacity(), __a); 420 else 421 __r = _Rep::_S_create(__new_size, __a); 422 try 423 { 424 if (__pos) 425 traits_type::copy(__r->_M_refdata(), _M_data(), __pos); 426 if (__how_much) 427 traits_type::copy(__r->_M_refdata() + __pos + __len2, 428 __src, __how_much); 429 } 430 catch(...) 431 { 432 __r->_M_dispose(get_allocator()); 433 __throw_exception_again; 434 } 435 _M_rep()->_M_dispose(__a); 436 _M_data(__r->_M_refdata()); 437 } 438 else if (__how_much && __len1 != __len2) 439 { 440 // Work in-place 441 traits_type::move(_M_data() + __pos + __len2, __src, __how_much); 442 } 443 _M_rep()->_M_set_sharable(); 444 _M_rep()->_M_length = __new_size; 445 _M_data()[__new_size] = _Rep::_S_terminal; // grrr. (per 21.3.4) 446 // You cannot leave those LWG people alone for a second. 447 } 448 449 template<typename _CharT, typename _Traits, typename _Alloc> 450 void reserve(size_type __res)451 basic_string<_CharT, _Traits, _Alloc>::reserve(size_type __res) 452 { 453 if (__res > this->capacity() || _M_rep()->_M_is_shared()) 454 { 455 if (__res > this->max_size()) 456 __throw_length_error("basic_string::reserve"); 457 // Make sure we don't shrink below the current size 458 if (__res < this->size()) 459 __res = this->size(); 460 allocator_type __a = get_allocator(); 461 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 462 _M_rep()->_M_dispose(__a); 463 _M_data(__tmp); 464 } 465 } 466 467 template<typename _CharT, typename _Traits, typename _Alloc> swap(basic_string & __s)468 void basic_string<_CharT, _Traits, _Alloc>::swap(basic_string& __s) 469 { 470 if (_M_rep()->_M_is_leaked()) 471 _M_rep()->_M_set_sharable(); 472 if (__s._M_rep()->_M_is_leaked()) 473 __s._M_rep()->_M_set_sharable(); 474 if (this->get_allocator() == __s.get_allocator()) 475 { 476 _CharT* __tmp = _M_data(); 477 _M_data(__s._M_data()); 478 __s._M_data(__tmp); 479 } 480 // The code below can usually be optimized away. 481 else 482 { 483 basic_string __tmp1(_M_ibegin(), _M_iend(), __s.get_allocator()); 484 basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 485 this->get_allocator()); 486 *this = __tmp2; 487 __s = __tmp1; 488 } 489 } 490 491 template<typename _CharT, typename _Traits, typename _Alloc> 492 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 493 basic_string<_CharT, _Traits, _Alloc>::_Rep:: _S_create(size_t __capacity,const _Alloc & __alloc)494 _S_create(size_t __capacity, const _Alloc& __alloc) 495 { 496 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 497 #ifdef _GLIBCPP_RESOLVE_LIB_DEFECTS 498 // 83. String::npos vs. string::max_size() 499 if (__capacity > _S_max_size) 500 #else 501 if (__capacity == npos) 502 #endif 503 __throw_length_error("basic_string::_S_create"); 504 505 // NB: Need an array of char_type[__capacity], plus a 506 // terminating null char_type() element, plus enough for the 507 // _Rep data structure. Whew. Seemingly so needy, yet so elemental. 508 size_t __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 509 510 // The standard places no restriction on allocating more memory 511 // than is strictly needed within this layer at the moment or as 512 // requested by an explicit application call to reserve(). Many 513 // malloc implementations perform quite poorly when an 514 // application attempts to allocate memory in a stepwise fashion 515 // growing each allocation size by only 1 char. Additionally, 516 // it makes little sense to allocate less linear memory than the 517 // natural blocking size of the malloc implementation. 518 // Unfortunately, we would need a somewhat low-level calculation 519 // with tuned parameters to get this perfect for any particular 520 // malloc implementation. Fortunately, generalizations about 521 // common features seen among implementations seems to suffice. 522 523 // __pagesize need not match the actual VM page size for good 524 // results in practice, thus we pick a common value on the low 525 // side. __malloc_header_size is an estimate of the amount of 526 // overhead per memory allocation (in practice seen N * sizeof 527 // (void*) where N is 0, 2 or 4). According to folklore, 528 // picking this value on the high side is better than 529 // low-balling it (especially when this algorithm is used with 530 // malloc implementations that allocate memory blocks rounded up 531 // to a size which is a power of 2). 532 const size_t __pagesize = 4096; // must be 2^i * __subpagesize 533 const size_t __subpagesize = 128; // should be >> __malloc_header_size 534 const size_t __malloc_header_size = 4 * sizeof (void*); 535 if ((__size + __malloc_header_size) > __pagesize) 536 { 537 size_t __extra = 538 (__pagesize - ((__size + __malloc_header_size) % __pagesize)) 539 % __pagesize; 540 __capacity += __extra / sizeof(_CharT); 541 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 542 } 543 else if (__size > __subpagesize) 544 { 545 size_t __extra = 546 (__subpagesize - ((__size + __malloc_header_size) % __subpagesize)) 547 % __subpagesize; 548 __capacity += __extra / sizeof(_CharT); 549 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 550 } 551 552 // NB: Might throw, but no worries about a leak, mate: _Rep() 553 // does not throw. 554 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 555 _Rep *__p = new (__place) _Rep; 556 __p->_M_capacity = __capacity; 557 __p->_M_set_sharable(); // One reference. 558 __p->_M_length = 0; 559 return __p; 560 } 561 562 template<typename _CharT, typename _Traits, typename _Alloc> 563 _CharT* 564 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 565 _M_clone(const _Alloc& __alloc, size_type __res) 566 { 567 // Requested capacity of the clone. 568 const size_type __requested_cap = _M_length + __res; 569 // See above (_S_create) for the meaning and value of these constants. 570 const size_type __pagesize = 4096; 571 const size_type __malloc_header_size = 4 * sizeof (void*); 572 // The biggest string which fits in a memory page. 573 const size_type __page_capacity = 574 (__pagesize - __malloc_header_size - sizeof(_Rep) - sizeof(_CharT)) 575 / sizeof(_CharT); 576 _Rep* __r; 577 if (__requested_cap > _M_capacity && __requested_cap > __page_capacity) 578 // Growing exponentially. 579 __r = _Rep::_S_create(__requested_cap > 2*_M_capacity ? 580 __requested_cap : 2*_M_capacity, __alloc); 581 else 582 __r = _Rep::_S_create(__requested_cap, __alloc); 583 584 if (_M_length) 585 { 586 try 587 { traits_type::copy(__r->_M_refdata(), _M_refdata(), _M_length); } 588 catch(...) 589 { 590 __r->_M_destroy(__alloc); 591 __throw_exception_again; 592 } 593 } 594 __r->_M_length = _M_length; 595 __r->_M_refdata()[_M_length] = _Rep::_S_terminal; 596 return __r->_M_refdata(); 597 } 598 599 template<typename _CharT, typename _Traits, typename _Alloc> 600 void resize(size_type __n,_CharT __c)601 basic_string<_CharT, _Traits, _Alloc>::resize(size_type __n, _CharT __c) 602 { 603 if (__n > max_size()) 604 __throw_length_error("basic_string::resize"); 605 size_type __size = this->size(); 606 if (__size < __n) 607 this->append(__n - __size, __c); 608 else if (__n < __size) 609 this->erase(__n); 610 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 611 } 612 613 // This is the general replace helper, which currently gets instantiated both 614 // for input iterators and reverse iterators. It buffers internally and then 615 // calls _M_replace_safe. 616 template<typename _CharT, typename _Traits, typename _Alloc> 617 template<typename _InputIter> 618 basic_string<_CharT, _Traits, _Alloc>& 619 basic_string<_CharT, _Traits, _Alloc>:: _M_replace(iterator __i1,iterator __i2,_InputIter __k1,_InputIter __k2,input_iterator_tag)620 _M_replace(iterator __i1, iterator __i2, _InputIter __k1, 621 _InputIter __k2, input_iterator_tag) 622 { 623 // Save concerned source string data in a temporary. 624 basic_string __s(__k1, __k2); 625 return _M_replace_safe(__i1, __i2, __s._M_ibegin(), __s._M_iend()); 626 } 627 628 // This is a special replace helper, which does not buffer internally 629 // and can be used in "safe" situations involving forward iterators, 630 // i.e., when source and destination ranges are known to not overlap. 631 template<typename _CharT, typename _Traits, typename _Alloc> 632 template<typename _ForwardIter> 633 basic_string<_CharT, _Traits, _Alloc>& 634 basic_string<_CharT, _Traits, _Alloc>:: _M_replace_safe(iterator __i1,iterator __i2,_ForwardIter __k1,_ForwardIter __k2)635 _M_replace_safe(iterator __i1, iterator __i2, _ForwardIter __k1, 636 _ForwardIter __k2) 637 { 638 size_type __dnew = static_cast<size_type>(std::distance(__k1, __k2)); 639 size_type __dold = __i2 - __i1; 640 size_type __dmax = this->max_size(); 641 642 if (__dmax <= __dnew) 643 __throw_length_error("basic_string::_M_replace"); 644 size_type __off = __i1 - _M_ibegin(); 645 _M_mutate(__off, __dold, __dnew); 646 647 // Invalidated __i1, __i2 648 if (__dnew) 649 _S_copy_chars(_M_data() + __off, __k1, __k2); 650 651 return *this; 652 } 653 654 template<typename _CharT, typename _Traits, typename _Alloc> 655 basic_string<_CharT, _Traits, _Alloc>& 656 basic_string<_CharT, _Traits, _Alloc>:: replace(size_type __pos1,size_type __n1,const basic_string & __str,size_type __pos2,size_type __n2)657 replace(size_type __pos1, size_type __n1, const basic_string& __str, 658 size_type __pos2, size_type __n2) 659 { 660 const size_type __strsize = __str.size(); 661 if (__pos2 > __strsize) 662 __throw_out_of_range("basic_string::replace"); 663 const bool __testn2 = __n2 < __strsize - __pos2; 664 const size_type __foldn2 = __testn2 ? __n2 : __strsize - __pos2; 665 return this->replace(__pos1, __n1, 666 __str._M_data() + __pos2, __foldn2); 667 } 668 669 template<typename _CharT, typename _Traits, typename _Alloc> 670 basic_string<_CharT, _Traits, _Alloc>& 671 basic_string<_CharT, _Traits, _Alloc>:: append(const basic_string & __str)672 append(const basic_string& __str) 673 { 674 // Iff appending itself, string needs to pre-reserve the 675 // correct size so that _M_mutate does not clobber the 676 // iterators formed here. 677 size_type __size = __str.size(); 678 size_type __len = __size + this->size(); 679 if (__len > this->capacity()) 680 this->reserve(__len); 681 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_ibegin(), 682 __str._M_iend()); 683 } 684 685 template<typename _CharT, typename _Traits, typename _Alloc> 686 basic_string<_CharT, _Traits, _Alloc>& 687 basic_string<_CharT, _Traits, _Alloc>:: append(const basic_string & __str,size_type __pos,size_type __n)688 append(const basic_string& __str, size_type __pos, size_type __n) 689 { 690 // Iff appending itself, string needs to pre-reserve the 691 // correct size so that _M_mutate does not clobber the 692 // iterators formed here. 693 size_type __len = std::min(size_type(__str.size() - __pos), 694 __n) + this->size(); 695 if (__len > this->capacity()) 696 this->reserve(__len); 697 return _M_replace_safe(_M_iend(), _M_iend(), __str._M_check(__pos), 698 __str._M_fold(__pos, __n)); 699 } 700 701 template<typename _CharT, typename _Traits, typename _Alloc> 702 basic_string<_CharT, _Traits, _Alloc>& 703 basic_string<_CharT, _Traits, _Alloc>:: append(const _CharT * __s,size_type __n)704 append(const _CharT* __s, size_type __n) 705 { 706 size_type __len = __n + this->size(); 707 if (__len > this->capacity()) 708 this->reserve(__len); 709 return _M_replace_safe(_M_iend(), _M_iend(), __s, __s + __n); 710 } 711 712 template<typename _CharT, typename _Traits, typename _Alloc> 713 basic_string<_CharT, _Traits, _Alloc>& 714 basic_string<_CharT, _Traits, _Alloc>:: append(size_type __n,_CharT __c)715 append(size_type __n, _CharT __c) 716 { 717 size_type __len = __n + this->size(); 718 if (__len > this->capacity()) 719 this->reserve(__len); 720 return this->replace(_M_iend(), _M_iend(), __n, __c); 721 } 722 723 template<typename _CharT, typename _Traits, typename _Alloc> 724 basic_string<_CharT, _Traits, _Alloc> operator +(const _CharT * __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)725 operator+(const _CharT* __lhs, 726 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 727 { 728 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 729 typedef typename __string_type::size_type __size_type; 730 __size_type __len = _Traits::length(__lhs); 731 __string_type __str; 732 __str.reserve(__len + __rhs.size()); 733 __str.append(__lhs, __lhs + __len); 734 __str.append(__rhs); 735 return __str; 736 } 737 738 template<typename _CharT, typename _Traits, typename _Alloc> 739 basic_string<_CharT, _Traits, _Alloc> operator +(_CharT __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)740 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 741 { 742 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 743 typedef typename __string_type::size_type __size_type; 744 __string_type __str; 745 __size_type __len = __rhs.size(); 746 __str.reserve(__len + 1); 747 __str.append(__size_type(1), __lhs); 748 __str.append(__rhs); 749 return __str; 750 } 751 752 template<typename _CharT, typename _Traits, typename _Alloc> 753 basic_string<_CharT, _Traits, _Alloc>& 754 basic_string<_CharT, _Traits, _Alloc>:: replace(iterator __i1,iterator __i2,size_type __n2,_CharT __c)755 replace(iterator __i1, iterator __i2, size_type __n2, _CharT __c) 756 { 757 size_type __n1 = __i2 - __i1; 758 size_type __off1 = __i1 - _M_ibegin(); 759 if (max_size() - (this->size() - __n1) <= __n2) 760 __throw_length_error("basic_string::replace"); 761 _M_mutate (__off1, __n1, __n2); 762 // Invalidated __i1, __i2 763 if (__n2) 764 traits_type::assign(_M_data() + __off1, __n2, __c); 765 return *this; 766 } 767 768 template<typename _CharT, typename _Traits, typename _Alloc> 769 typename basic_string<_CharT, _Traits, _Alloc>::size_type 770 basic_string<_CharT, _Traits, _Alloc>:: copy(_CharT * __s,size_type __n,size_type __pos) const771 copy(_CharT* __s, size_type __n, size_type __pos) const 772 { 773 if (__pos > this->size()) 774 __throw_out_of_range("basic_string::copy"); 775 776 if (__n > this->size() - __pos) 777 __n = this->size() - __pos; 778 779 traits_type::copy(__s, _M_data() + __pos, __n); 780 // 21.3.5.7 par 3: do not append null. (good.) 781 return __n; 782 } 783 784 template<typename _CharT, typename _Traits, typename _Alloc> 785 typename basic_string<_CharT, _Traits, _Alloc>::size_type 786 basic_string<_CharT, _Traits, _Alloc>:: find(const _CharT * __s,size_type __pos,size_type __n) const787 find(const _CharT* __s, size_type __pos, size_type __n) const 788 { 789 size_type __size = this->size(); 790 size_t __xpos = __pos; 791 const _CharT* __data = _M_data(); 792 for (; __xpos + __n <= __size; ++__xpos) 793 if (traits_type::compare(__data + __xpos, __s, __n) == 0) 794 return __xpos; 795 return npos; 796 } 797 798 template<typename _CharT, typename _Traits, typename _Alloc> 799 typename basic_string<_CharT, _Traits, _Alloc>::size_type 800 basic_string<_CharT, _Traits, _Alloc>:: find(_CharT __c,size_type __pos) const801 find(_CharT __c, size_type __pos) const 802 { 803 size_type __size = this->size(); 804 size_type __ret = npos; 805 if (__pos < __size) 806 { 807 const _CharT* __data = _M_data(); 808 size_type __n = __size - __pos; 809 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 810 if (__p) 811 __ret = __p - __data; 812 } 813 return __ret; 814 } 815 816 817 template<typename _CharT, typename _Traits, typename _Alloc> 818 typename basic_string<_CharT, _Traits, _Alloc>::size_type 819 basic_string<_CharT, _Traits, _Alloc>:: rfind(const _CharT * __s,size_type __pos,size_type __n) const820 rfind(const _CharT* __s, size_type __pos, size_type __n) const 821 { 822 size_type __size = this->size(); 823 if (__n <= __size) 824 { 825 __pos = std::min(size_type(__size - __n), __pos); 826 const _CharT* __data = _M_data(); 827 do 828 { 829 if (traits_type::compare(__data + __pos, __s, __n) == 0) 830 return __pos; 831 } 832 while (__pos-- > 0); 833 } 834 return npos; 835 } 836 837 template<typename _CharT, typename _Traits, typename _Alloc> 838 typename basic_string<_CharT, _Traits, _Alloc>::size_type 839 basic_string<_CharT, _Traits, _Alloc>:: rfind(_CharT __c,size_type __pos) const840 rfind(_CharT __c, size_type __pos) const 841 { 842 size_type __size = this->size(); 843 if (__size) 844 { 845 size_t __xpos = __size - 1; 846 if (__xpos > __pos) 847 __xpos = __pos; 848 849 for (++__xpos; __xpos-- > 0; ) 850 if (traits_type::eq(_M_data()[__xpos], __c)) 851 return __xpos; 852 } 853 return npos; 854 } 855 856 template<typename _CharT, typename _Traits, typename _Alloc> 857 typename basic_string<_CharT, _Traits, _Alloc>::size_type 858 basic_string<_CharT, _Traits, _Alloc>:: find_first_of(const _CharT * __s,size_type __pos,size_type __n) const859 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 860 { 861 for (; __n && __pos < this->size(); ++__pos) 862 { 863 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 864 if (__p) 865 return __pos; 866 } 867 return npos; 868 } 869 870 template<typename _CharT, typename _Traits, typename _Alloc> 871 typename basic_string<_CharT, _Traits, _Alloc>::size_type 872 basic_string<_CharT, _Traits, _Alloc>:: find_last_of(const _CharT * __s,size_type __pos,size_type __n) const873 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 874 { 875 size_type __size = this->size(); 876 if (__size && __n) 877 { 878 if (--__size > __pos) 879 __size = __pos; 880 do 881 { 882 if (traits_type::find(__s, __n, _M_data()[__size])) 883 return __size; 884 } 885 while (__size-- != 0); 886 } 887 return npos; 888 } 889 890 template<typename _CharT, typename _Traits, typename _Alloc> 891 typename basic_string<_CharT, _Traits, _Alloc>::size_type 892 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(const _CharT * __s,size_type __pos,size_type __n) const893 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 894 { 895 size_t __xpos = __pos; 896 for (; __xpos < this->size(); ++__xpos) 897 if (!traits_type::find(__s, __n, _M_data()[__xpos])) 898 return __xpos; 899 return npos; 900 } 901 902 template<typename _CharT, typename _Traits, typename _Alloc> 903 typename basic_string<_CharT, _Traits, _Alloc>::size_type 904 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(_CharT __c,size_type __pos) const905 find_first_not_of(_CharT __c, size_type __pos) const 906 { 907 size_t __xpos = __pos; 908 for (; __xpos < this->size(); ++__xpos) 909 if (!traits_type::eq(_M_data()[__xpos], __c)) 910 return __xpos; 911 return npos; 912 } 913 914 template<typename _CharT, typename _Traits, typename _Alloc> 915 typename basic_string<_CharT, _Traits, _Alloc>::size_type 916 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(const _CharT * __s,size_type __pos,size_type __n) const917 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 918 { 919 size_type __size = this->size(); 920 if (__size) 921 { 922 if (--__size > __pos) 923 __size = __pos; 924 do 925 { 926 if (!traits_type::find(__s, __n, _M_data()[__size])) 927 return __size; 928 } 929 while (__size--); 930 } 931 return npos; 932 } 933 934 template<typename _CharT, typename _Traits, typename _Alloc> 935 typename basic_string<_CharT, _Traits, _Alloc>::size_type 936 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(_CharT __c,size_type __pos) const937 find_last_not_of(_CharT __c, size_type __pos) const 938 { 939 size_type __size = this->size(); 940 if (__size) 941 { 942 if (--__size > __pos) 943 __size = __pos; 944 do 945 { 946 if (!traits_type::eq(_M_data()[__size], __c)) 947 return __size; 948 } 949 while (__size--); 950 } 951 return npos; 952 } 953 954 template<typename _CharT, typename _Traits, typename _Alloc> 955 int 956 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n,const basic_string & __str) const957 compare(size_type __pos, size_type __n, const basic_string& __str) const 958 { 959 size_type __size = this->size(); 960 size_type __osize = __str.size(); 961 if (__pos > __size) 962 __throw_out_of_range("basic_string::compare"); 963 964 size_type __rsize= std::min(size_type(__size - __pos), __n); 965 size_type __len = std::min(__rsize, __osize); 966 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 967 if (!__r) 968 __r = __rsize - __osize; 969 return __r; 970 } 971 972 template<typename _CharT, typename _Traits, typename _Alloc> 973 int 974 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos1,size_type __n1,const basic_string & __str,size_type __pos2,size_type __n2) const975 compare(size_type __pos1, size_type __n1, const basic_string& __str, 976 size_type __pos2, size_type __n2) const 977 { 978 size_type __size = this->size(); 979 size_type __osize = __str.size(); 980 if (__pos1 > __size || __pos2 > __osize) 981 __throw_out_of_range("basic_string::compare"); 982 983 size_type __rsize = std::min(size_type(__size - __pos1), __n1); 984 size_type __rosize = std::min(size_type(__osize - __pos2), __n2); 985 size_type __len = std::min(__rsize, __rosize); 986 int __r = traits_type::compare(_M_data() + __pos1, 987 __str.data() + __pos2, __len); 988 if (!__r) 989 __r = __rsize - __rosize; 990 return __r; 991 } 992 993 994 template<typename _CharT, typename _Traits, typename _Alloc> 995 int 996 basic_string<_CharT, _Traits, _Alloc>:: compare(const _CharT * __s) const997 compare(const _CharT* __s) const 998 { 999 size_type __size = this->size(); 1000 size_type __osize = traits_type::length(__s); 1001 size_type __len = std::min(__size, __osize); 1002 int __r = traits_type::compare(_M_data(), __s, __len); 1003 if (!__r) 1004 __r = __size - __osize; 1005 return __r; 1006 } 1007 1008 1009 template<typename _CharT, typename _Traits, typename _Alloc> 1010 int 1011 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s) const1012 compare(size_type __pos, size_type __n1, const _CharT* __s) const 1013 { 1014 size_type __size = this->size(); 1015 if (__pos > __size) 1016 __throw_out_of_range("basic_string::compare"); 1017 1018 size_type __osize = traits_type::length(__s); 1019 size_type __rsize = std::min(size_type(__size - __pos), __n1); 1020 size_type __len = std::min(__rsize, __osize); 1021 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1022 if (!__r) 1023 __r = __rsize - __osize; 1024 return __r; 1025 } 1026 1027 template<typename _CharT, typename _Traits, typename _Alloc> 1028 int 1029 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s,size_type __n2) const1030 compare(size_type __pos, size_type __n1, const _CharT* __s, 1031 size_type __n2) const 1032 { 1033 size_type __size = this->size(); 1034 if (__pos > __size) 1035 __throw_out_of_range("basic_string::compare"); 1036 1037 size_type __rsize = std::min(size_type(__size - __pos), __n1); 1038 size_type __len = std::min(__rsize, __n2); 1039 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1040 if (!__r) 1041 __r = __rsize - __n2; 1042 return __r; 1043 } 1044 1045 template <class _CharT, class _Traits, class _Alloc> 1046 void _S_string_copy(const basic_string<_CharT,_Traits,_Alloc> & __str,_CharT * __buf,typename _Alloc::size_type __bufsiz)1047 _S_string_copy(const basic_string<_CharT, _Traits, _Alloc>& __str, 1048 _CharT* __buf, typename _Alloc::size_type __bufsiz) 1049 { 1050 typedef typename _Alloc::size_type size_type; 1051 size_type __strsize = __str.size(); 1052 size_type __bytes = std::min(__strsize, __bufsiz - 1); 1053 _Traits::copy(__buf, __str.data(), __bytes); 1054 __buf[__bytes] = _CharT(); 1055 } 1056 1057 // Inhibit implicit instantiations for required instantiations, 1058 // which are defined via explicit instantiations elsewhere. 1059 // NB: This syntax is a GNU extension. 1060 #if defined(_GLIBCPP_EXTERN_TEMPLATE) 1061 extern template class basic_string<char>; 1062 extern template 1063 basic_istream<char>& 1064 operator>>(basic_istream<char>&, string&); 1065 extern template 1066 basic_ostream<char>& 1067 operator<<(basic_ostream<char>&, const string&); 1068 extern template 1069 basic_istream<char>& 1070 getline(basic_istream<char>&, string&, char); 1071 extern template 1072 basic_istream<char>& 1073 getline(basic_istream<char>&, string&); 1074 1075 #if defined(_GLIBCPP_USE_WCHAR_T) || defined(_GLIBCPP_USE_TYPE_WCHAR_T) 1076 extern template class basic_string<wchar_t>; 1077 extern template 1078 basic_istream<wchar_t>& 1079 operator>>(basic_istream<wchar_t>&, wstring&); 1080 extern template 1081 basic_ostream<wchar_t>& 1082 operator<<(basic_ostream<wchar_t>&, const wstring&); 1083 extern template 1084 basic_istream<wchar_t>& 1085 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 1086 extern template 1087 basic_istream<wchar_t>& 1088 getline(basic_istream<wchar_t>&, wstring&); 1089 #endif 1090 #endif 1091 } // namespace std 1092 1093 #endif 1094