1// Components for manipulating sequences of characters -*- C++ -*- 2 3// Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 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/** @file basic_string.tcc 32 * This is an internal header file, included by other library headers. 33 * You should not attempt to use it directly. 34 */ 35 36// 37// ISO C++ 14882: 21 Strings library 38// 39 40// Written by Jason Merrill based upon the specification by Takanori Adachi 41// in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 42 43#ifndef _BASIC_STRING_TCC 44#define _BASIC_STRING_TCC 1 45 46#pragma GCC system_header 47 48namespace std 49{ 50 template<typename _Type> 51 inline bool 52 __is_null_pointer(_Type* __ptr) 53 { return __ptr == 0; } 54 55 template<typename _Type> 56 inline bool 57 __is_null_pointer(_Type) 58 { return false; } 59 60 template<typename _CharT, typename _Traits, typename _Alloc> 61 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 62 basic_string<_CharT, _Traits, _Alloc>:: 63 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 64 65 template<typename _CharT, typename _Traits, typename _Alloc> 66 const _CharT 67 basic_string<_CharT, _Traits, _Alloc>:: 68 _Rep::_S_terminal = _CharT(); 69 70 template<typename _CharT, typename _Traits, typename _Alloc> 71 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 72 basic_string<_CharT, _Traits, _Alloc>::npos; 73 74 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 75 // at static init time (before static ctors are run). 76 template<typename _CharT, typename _Traits, typename _Alloc> 77 typename basic_string<_CharT, _Traits, _Alloc>::size_type 78 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 79 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 80 sizeof(size_type)]; 81 82 // NB: This is the special case for Input Iterators, used in 83 // istreambuf_iterators, etc. 84 // Input Iterators have a cost structure very different from 85 // pointers, calling for a different coding style. 86 template<typename _CharT, typename _Traits, typename _Alloc> 87 template<typename _InIterator> 88 _CharT* 89 basic_string<_CharT, _Traits, _Alloc>:: 90 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 91 input_iterator_tag) 92 { 93#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 94 if (__beg == __end && __a == _Alloc()) 95 return _S_empty_rep()._M_refdata(); 96#endif 97 // Avoid reallocation for common case. 98 _CharT __buf[128]; 99 size_type __len = 0; 100 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 101 { 102 __buf[__len++] = *__beg; 103 ++__beg; 104 } 105 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 106 _M_copy(__r->_M_refdata(), __buf, __len); 107 try 108 { 109 while (__beg != __end) 110 { 111 if (__len == __r->_M_capacity) 112 { 113 // Allocate more space. 114 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 115 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 116 __r->_M_destroy(__a); 117 __r = __another; 118 } 119 __r->_M_refdata()[__len++] = *__beg; 120 ++__beg; 121 } 122 } 123 catch(...) 124 { 125 __r->_M_destroy(__a); 126 __throw_exception_again; 127 } 128 __r->_M_set_length_and_sharable(__len); 129 return __r->_M_refdata(); 130 } 131 132 template<typename _CharT, typename _Traits, typename _Alloc> 133 template <typename _InIterator> 134 _CharT* 135 basic_string<_CharT, _Traits, _Alloc>:: 136 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 137 forward_iterator_tag) 138 { 139#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 140 if (__beg == __end && __a == _Alloc()) 141 return _S_empty_rep()._M_refdata(); 142#endif 143 // NB: Not required, but considered best practice. 144 if (__builtin_expect(__is_null_pointer(__beg) && __beg != __end, 0)) 145 __throw_logic_error(__N("basic_string::_S_construct NULL not valid")); 146 147 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 148 __end)); 149 // Check for out_of_range and length_error exceptions. 150 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __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_set_length_and_sharable(__dnew); 159 return __r->_M_refdata(); 160 } 161 162 template<typename _CharT, typename _Traits, typename _Alloc> 163 _CharT* 164 basic_string<_CharT, _Traits, _Alloc>:: 165 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 166 { 167#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 168 if (__n == 0 && __a == _Alloc()) 169 return _S_empty_rep()._M_refdata(); 170#endif 171 // Check for out_of_range and length_error exceptions. 172 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 173 if (__n) 174 _M_assign(__r->_M_refdata(), __n, __c); 175 176 __r->_M_set_length_and_sharable(__n); 177 return __r->_M_refdata(); 178 } 179 180 template<typename _CharT, typename _Traits, typename _Alloc> 181 basic_string<_CharT, _Traits, _Alloc>:: 182 basic_string(const basic_string& __str) 183 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 184 __str.get_allocator()), 185 __str.get_allocator()) 186 { } 187 188 template<typename _CharT, typename _Traits, typename _Alloc> 189 basic_string<_CharT, _Traits, _Alloc>:: 190 basic_string(const _Alloc& __a) 191 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 192 { } 193 194 template<typename _CharT, typename _Traits, typename _Alloc> 195 basic_string<_CharT, _Traits, _Alloc>:: 196 basic_string(const basic_string& __str, size_type __pos, size_type __n) 197 : _M_dataplus(_S_construct(__str._M_data() 198 + __str._M_check(__pos, 199 "basic_string::basic_string"), 200 __str._M_data() + __str._M_limit(__pos, __n) 201 + __pos, _Alloc()), _Alloc()) 202 { } 203 204 template<typename _CharT, typename _Traits, typename _Alloc> 205 basic_string<_CharT, _Traits, _Alloc>:: 206 basic_string(const basic_string& __str, size_type __pos, 207 size_type __n, const _Alloc& __a) 208 : _M_dataplus(_S_construct(__str._M_data() 209 + __str._M_check(__pos, 210 "basic_string::basic_string"), 211 __str._M_data() + __str._M_limit(__pos, __n) 212 + __pos, __a), __a) 213 { } 214 215 // TBD: DPG annotate 216 template<typename _CharT, typename _Traits, typename _Alloc> 217 basic_string<_CharT, _Traits, _Alloc>:: 218 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 219 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 220 { } 221 222 // TBD: DPG annotate 223 template<typename _CharT, typename _Traits, typename _Alloc> 224 basic_string<_CharT, _Traits, _Alloc>:: 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>:: 232 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 233 : _M_dataplus(_S_construct(__n, __c, __a), __a) 234 { } 235 236 // TBD: DPG annotate 237 template<typename _CharT, typename _Traits, typename _Alloc> 238 template<typename _InputIterator> 239 basic_string<_CharT, _Traits, _Alloc>:: 240 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 241 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 242 { } 243 244 template<typename _CharT, typename _Traits, typename _Alloc> 245 basic_string<_CharT, _Traits, _Alloc>& 246 basic_string<_CharT, _Traits, _Alloc>:: 247 assign(const basic_string& __str) 248 { 249 if (_M_rep() != __str._M_rep()) 250 { 251 // XXX MT 252 const allocator_type __a = this->get_allocator(); 253 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 254 _M_rep()->_M_dispose(__a); 255 _M_data(__tmp); 256 } 257 return *this; 258 } 259 260 template<typename _CharT, typename _Traits, typename _Alloc> 261 basic_string<_CharT, _Traits, _Alloc>& 262 basic_string<_CharT, _Traits, _Alloc>:: 263 assign(const _CharT* __s, size_type __n) 264 { 265 __glibcxx_requires_string_len(__s, __n); 266 _M_check_length(this->size(), __n, "basic_string::assign"); 267 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 268 return _M_replace_safe(size_type(0), this->size(), __s, __n); 269 else 270 { 271 // Work in-place. 272 const size_type __pos = __s - _M_data(); 273 if (__pos >= __n) 274 _M_copy(_M_data(), __s, __n); 275 else if (__pos) 276 _M_move(_M_data(), __s, __n); 277 _M_rep()->_M_set_length_and_sharable(__n); 278 return *this; 279 } 280 } 281 282 template<typename _CharT, typename _Traits, typename _Alloc> 283 basic_string<_CharT, _Traits, _Alloc>& 284 basic_string<_CharT, _Traits, _Alloc>:: 285 append(size_type __n, _CharT __c) 286 { 287 if (__n) 288 { 289 _M_check_length(size_type(0), __n, "basic_string::append"); 290 const size_type __len = __n + this->size(); 291 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 292 this->reserve(__len); 293 _M_assign(_M_data() + this->size(), __n, __c); 294 _M_rep()->_M_set_length_and_sharable(__len); 295 } 296 return *this; 297 } 298 299 template<typename _CharT, typename _Traits, typename _Alloc> 300 basic_string<_CharT, _Traits, _Alloc>& 301 basic_string<_CharT, _Traits, _Alloc>:: 302 append(const _CharT* __s, size_type __n) 303 { 304 __glibcxx_requires_string_len(__s, __n); 305 if (__n) 306 { 307 _M_check_length(size_type(0), __n, "basic_string::append"); 308 const size_type __len = __n + this->size(); 309 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 310 { 311 if (_M_disjunct(__s)) 312 this->reserve(__len); 313 else 314 { 315 const size_type __off = __s - _M_data(); 316 this->reserve(__len); 317 __s = _M_data() + __off; 318 } 319 } 320 _M_copy(_M_data() + this->size(), __s, __n); 321 _M_rep()->_M_set_length_and_sharable(__len); 322 } 323 return *this; 324 } 325 326 template<typename _CharT, typename _Traits, typename _Alloc> 327 basic_string<_CharT, _Traits, _Alloc>& 328 basic_string<_CharT, _Traits, _Alloc>:: 329 append(const basic_string& __str) 330 { 331 const size_type __size = __str.size(); 332 if (__size) 333 { 334 const size_type __len = __size + this->size(); 335 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 336 this->reserve(__len); 337 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 338 _M_rep()->_M_set_length_and_sharable(__len); 339 } 340 return *this; 341 } 342 343 template<typename _CharT, typename _Traits, typename _Alloc> 344 basic_string<_CharT, _Traits, _Alloc>& 345 basic_string<_CharT, _Traits, _Alloc>:: 346 append(const basic_string& __str, size_type __pos, size_type __n) 347 { 348 __str._M_check(__pos, "basic_string::append"); 349 __n = __str._M_limit(__pos, __n); 350 if (__n) 351 { 352 const size_type __len = __n + this->size(); 353 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 354 this->reserve(__len); 355 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 356 _M_rep()->_M_set_length_and_sharable(__len); 357 } 358 return *this; 359 } 360 361 template<typename _CharT, typename _Traits, typename _Alloc> 362 basic_string<_CharT, _Traits, _Alloc>& 363 basic_string<_CharT, _Traits, _Alloc>:: 364 insert(size_type __pos, const _CharT* __s, size_type __n) 365 { 366 __glibcxx_requires_string_len(__s, __n); 367 _M_check(__pos, "basic_string::insert"); 368 _M_check_length(size_type(0), __n, "basic_string::insert"); 369 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 370 return _M_replace_safe(__pos, size_type(0), __s, __n); 371 else 372 { 373 // Work in-place. 374 const size_type __off = __s - _M_data(); 375 _M_mutate(__pos, 0, __n); 376 __s = _M_data() + __off; 377 _CharT* __p = _M_data() + __pos; 378 if (__s + __n <= __p) 379 _M_copy(__p, __s, __n); 380 else if (__s >= __p) 381 _M_copy(__p, __s + __n, __n); 382 else 383 { 384 const size_type __nleft = __p - __s; 385 _M_copy(__p, __s, __nleft); 386 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 387 } 388 return *this; 389 } 390 } 391 392 template<typename _CharT, typename _Traits, typename _Alloc> 393 basic_string<_CharT, _Traits, _Alloc>& 394 basic_string<_CharT, _Traits, _Alloc>:: 395 replace(size_type __pos, size_type __n1, const _CharT* __s, 396 size_type __n2) 397 { 398 __glibcxx_requires_string_len(__s, __n2); 399 _M_check(__pos, "basic_string::replace"); 400 __n1 = _M_limit(__pos, __n1); 401 _M_check_length(__n1, __n2, "basic_string::replace"); 402 bool __left; 403 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 404 return _M_replace_safe(__pos, __n1, __s, __n2); 405 else if ((__left = __s + __n2 <= _M_data() + __pos) 406 || _M_data() + __pos + __n1 <= __s) 407 { 408 // Work in-place: non-overlapping case. 409 size_type __off = __s - _M_data(); 410 __left ? __off : (__off += __n2 - __n1); 411 _M_mutate(__pos, __n1, __n2); 412 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 413 return *this; 414 } 415 else 416 { 417 // Todo: overlapping case. 418 const basic_string __tmp(__s, __n2); 419 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 420 } 421 } 422 423 template<typename _CharT, typename _Traits, typename _Alloc> 424 void 425 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 426 _M_destroy(const _Alloc& __a) throw () 427 { 428 const size_type __size = sizeof(_Rep_base) + 429 (this->_M_capacity + 1) * sizeof(_CharT); 430 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 431 } 432 433 template<typename _CharT, typename _Traits, typename _Alloc> 434 void 435 basic_string<_CharT, _Traits, _Alloc>:: 436 _M_leak_hard() 437 { 438#ifndef _GLIBCXX_FULLY_DYNAMIC_STRING 439 if (_M_rep() == &_S_empty_rep()) 440 return; 441#endif 442 if (_M_rep()->_M_is_shared()) 443 _M_mutate(0, 0, 0); 444 _M_rep()->_M_set_leaked(); 445 } 446 447 template<typename _CharT, typename _Traits, typename _Alloc> 448 void 449 basic_string<_CharT, _Traits, _Alloc>:: 450 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 451 { 452 const size_type __old_size = this->size(); 453 const size_type __new_size = __old_size + __len2 - __len1; 454 const size_type __how_much = __old_size - __pos - __len1; 455 456 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 457 { 458 // Must reallocate. 459 const allocator_type __a = get_allocator(); 460 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 461 462 if (__pos) 463 _M_copy(__r->_M_refdata(), _M_data(), __pos); 464 if (__how_much) 465 _M_copy(__r->_M_refdata() + __pos + __len2, 466 _M_data() + __pos + __len1, __how_much); 467 468 _M_rep()->_M_dispose(__a); 469 _M_data(__r->_M_refdata()); 470 } 471 else if (__how_much && __len1 != __len2) 472 { 473 // Work in-place. 474 _M_move(_M_data() + __pos + __len2, 475 _M_data() + __pos + __len1, __how_much); 476 } 477 _M_rep()->_M_set_length_and_sharable(__new_size); 478 } 479 480 template<typename _CharT, typename _Traits, typename _Alloc> 481 void 482 basic_string<_CharT, _Traits, _Alloc>:: 483 reserve(size_type __res) 484 { 485 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 486 { 487 // Make sure we don't shrink below the current size 488 if (__res < this->size()) 489 __res = this->size(); 490 const allocator_type __a = get_allocator(); 491 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 492 _M_rep()->_M_dispose(__a); 493 _M_data(__tmp); 494 } 495 } 496 497 template<typename _CharT, typename _Traits, typename _Alloc> 498 void 499 basic_string<_CharT, _Traits, _Alloc>:: 500 swap(basic_string& __s) 501 { 502 if (_M_rep()->_M_is_leaked()) 503 _M_rep()->_M_set_sharable(); 504 if (__s._M_rep()->_M_is_leaked()) 505 __s._M_rep()->_M_set_sharable(); 506 if (this->get_allocator() == __s.get_allocator()) 507 { 508 _CharT* __tmp = _M_data(); 509 _M_data(__s._M_data()); 510 __s._M_data(__tmp); 511 } 512 // The code below can usually be optimized away. 513 else 514 { 515 const basic_string __tmp1(_M_ibegin(), _M_iend(), 516 __s.get_allocator()); 517 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 518 this->get_allocator()); 519 *this = __tmp2; 520 __s = __tmp1; 521 } 522 } 523 524 template<typename _CharT, typename _Traits, typename _Alloc> 525 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 526 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 527 _S_create(size_type __capacity, size_type __old_capacity, 528 const _Alloc& __alloc) 529 { 530 // _GLIBCXX_RESOLVE_LIB_DEFECTS 531 // 83. String::npos vs. string::max_size() 532 if (__capacity > _S_max_size) 533 __throw_length_error(__N("basic_string::_S_create")); 534 535 // The standard places no restriction on allocating more memory 536 // than is strictly needed within this layer at the moment or as 537 // requested by an explicit application call to reserve(). 538 539 // Many malloc implementations perform quite poorly when an 540 // application attempts to allocate memory in a stepwise fashion 541 // growing each allocation size by only 1 char. Additionally, 542 // it makes little sense to allocate less linear memory than the 543 // natural blocking size of the malloc implementation. 544 // Unfortunately, we would need a somewhat low-level calculation 545 // with tuned parameters to get this perfect for any particular 546 // malloc implementation. Fortunately, generalizations about 547 // common features seen among implementations seems to suffice. 548 549 // __pagesize need not match the actual VM page size for good 550 // results in practice, thus we pick a common value on the low 551 // side. __malloc_header_size is an estimate of the amount of 552 // overhead per memory allocation (in practice seen N * sizeof 553 // (void*) where N is 0, 2 or 4). According to folklore, 554 // picking this value on the high side is better than 555 // low-balling it (especially when this algorithm is used with 556 // malloc implementations that allocate memory blocks rounded up 557 // to a size which is a power of 2). 558 const size_type __pagesize = 4096; 559 const size_type __malloc_header_size = 4 * sizeof(void*); 560 561 // The below implements an exponential growth policy, necessary to 562 // meet amortized linear time requirements of the library: see 563 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 564 // It's active for allocations requiring an amount of memory above 565 // system pagesize. This is consistent with the requirements of the 566 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 567 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 568 __capacity = 2 * __old_capacity; 569 570 // NB: Need an array of char_type[__capacity], plus a terminating 571 // null char_type() element, plus enough for the _Rep data structure. 572 // Whew. Seemingly so needy, yet so elemental. 573 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 574 575 const size_type __adj_size = __size + __malloc_header_size; 576 if (__adj_size > __pagesize && __capacity > __old_capacity) 577 { 578 const size_type __extra = __pagesize - __adj_size % __pagesize; 579 __capacity += __extra / sizeof(_CharT); 580 // Never allocate a string bigger than _S_max_size. 581 if (__capacity > _S_max_size) 582 __capacity = _S_max_size; 583 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 584 } 585 586 // NB: Might throw, but no worries about a leak, mate: _Rep() 587 // does not throw. 588 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 589 _Rep *__p = new (__place) _Rep; 590 __p->_M_capacity = __capacity; 591 // ABI compatibility - 3.4.x set in _S_create both 592 // _M_refcount and _M_length. All callers of _S_create 593 // in basic_string.tcc then set just _M_length. 594 // In 4.0.x and later both _M_refcount and _M_length 595 // are initialized in the callers, unfortunately we can 596 // have 3.4.x compiled code with _S_create callers inlined 597 // calling 4.0.x+ _S_create. 598 __p->_M_set_sharable(); 599 return __p; 600 } 601 602 template<typename _CharT, typename _Traits, typename _Alloc> 603 _CharT* 604 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 605 _M_clone(const _Alloc& __alloc, size_type __res) 606 { 607 // Requested capacity of the clone. 608 const size_type __requested_cap = this->_M_length + __res; 609 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 610 __alloc); 611 if (this->_M_length) 612 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 613 614 __r->_M_set_length_and_sharable(this->_M_length); 615 return __r->_M_refdata(); 616 } 617 618 template<typename _CharT, typename _Traits, typename _Alloc> 619 void 620 basic_string<_CharT, _Traits, _Alloc>:: 621 resize(size_type __n, _CharT __c) 622 { 623 const size_type __size = this->size(); 624 _M_check_length(__size, __n, "basic_string::resize"); 625 if (__size < __n) 626 this->append(__n - __size, __c); 627 else if (__n < __size) 628 this->erase(__n); 629 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 630 } 631 632 template<typename _CharT, typename _Traits, typename _Alloc> 633 template<typename _InputIterator> 634 basic_string<_CharT, _Traits, _Alloc>& 635 basic_string<_CharT, _Traits, _Alloc>:: 636 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 637 _InputIterator __k2, __false_type) 638 { 639 const basic_string __s(__k1, __k2); 640 const size_type __n1 = __i2 - __i1; 641 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 642 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 643 __s.size()); 644 } 645 646 template<typename _CharT, typename _Traits, typename _Alloc> 647 basic_string<_CharT, _Traits, _Alloc>& 648 basic_string<_CharT, _Traits, _Alloc>:: 649 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 650 _CharT __c) 651 { 652 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 653 _M_mutate(__pos1, __n1, __n2); 654 if (__n2) 655 _M_assign(_M_data() + __pos1, __n2, __c); 656 return *this; 657 } 658 659 template<typename _CharT, typename _Traits, typename _Alloc> 660 basic_string<_CharT, _Traits, _Alloc>& 661 basic_string<_CharT, _Traits, _Alloc>:: 662 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 663 size_type __n2) 664 { 665 _M_mutate(__pos1, __n1, __n2); 666 if (__n2) 667 _M_copy(_M_data() + __pos1, __s, __n2); 668 return *this; 669 } 670 671 template<typename _CharT, typename _Traits, typename _Alloc> 672 basic_string<_CharT, _Traits, _Alloc> 673 operator+(const _CharT* __lhs, 674 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 675 { 676 __glibcxx_requires_string(__lhs); 677 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 678 typedef typename __string_type::size_type __size_type; 679 const __size_type __len = _Traits::length(__lhs); 680 __string_type __str; 681 __str.reserve(__len + __rhs.size()); 682 __str.append(__lhs, __len); 683 __str.append(__rhs); 684 return __str; 685 } 686 687 template<typename _CharT, typename _Traits, typename _Alloc> 688 basic_string<_CharT, _Traits, _Alloc> 689 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 690 { 691 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 692 typedef typename __string_type::size_type __size_type; 693 __string_type __str; 694 const __size_type __len = __rhs.size(); 695 __str.reserve(__len + 1); 696 __str.append(__size_type(1), __lhs); 697 __str.append(__rhs); 698 return __str; 699 } 700 701 template<typename _CharT, typename _Traits, typename _Alloc> 702 typename basic_string<_CharT, _Traits, _Alloc>::size_type 703 basic_string<_CharT, _Traits, _Alloc>:: 704 copy(_CharT* __s, size_type __n, size_type __pos) const 705 { 706 _M_check(__pos, "basic_string::copy"); 707 __n = _M_limit(__pos, __n); 708 __glibcxx_requires_string_len(__s, __n); 709 if (__n) 710 _M_copy(__s, _M_data() + __pos, __n); 711 // 21.3.5.7 par 3: do not append null. (good.) 712 return __n; 713 } 714 715 template<typename _CharT, typename _Traits, typename _Alloc> 716 typename basic_string<_CharT, _Traits, _Alloc>::size_type 717 basic_string<_CharT, _Traits, _Alloc>:: 718 find(const _CharT* __s, size_type __pos, size_type __n) const 719 { 720 __glibcxx_requires_string_len(__s, __n); 721 size_type __ret = npos; 722 const size_type __size = this->size(); 723 if (__pos + __n <= __size) 724 { 725 const _CharT* __data = _M_data(); 726 const _CharT* __p = std::search(__data + __pos, __data + __size, 727 __s, __s + __n, traits_type::eq); 728 if (__p != __data + __size || __n == 0) 729 __ret = __p - __data; 730 } 731 return __ret; 732 } 733 734 template<typename _CharT, typename _Traits, typename _Alloc> 735 typename basic_string<_CharT, _Traits, _Alloc>::size_type 736 basic_string<_CharT, _Traits, _Alloc>:: 737 find(_CharT __c, size_type __pos) const 738 { 739 size_type __ret = npos; 740 const size_type __size = this->size(); 741 if (__pos < __size) 742 { 743 const _CharT* __data = _M_data(); 744 const size_type __n = __size - __pos; 745 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 746 if (__p) 747 __ret = __p - __data; 748 } 749 return __ret; 750 } 751 752 template<typename _CharT, typename _Traits, typename _Alloc> 753 typename basic_string<_CharT, _Traits, _Alloc>::size_type 754 basic_string<_CharT, _Traits, _Alloc>:: 755 rfind(const _CharT* __s, size_type __pos, size_type __n) const 756 { 757 __glibcxx_requires_string_len(__s, __n); 758 const size_type __size = this->size(); 759 if (__n <= __size) 760 { 761 __pos = std::min(size_type(__size - __n), __pos); 762 const _CharT* __data = _M_data(); 763 do 764 { 765 if (traits_type::compare(__data + __pos, __s, __n) == 0) 766 return __pos; 767 } 768 while (__pos-- > 0); 769 } 770 return npos; 771 } 772 773 template<typename _CharT, typename _Traits, typename _Alloc> 774 typename basic_string<_CharT, _Traits, _Alloc>::size_type 775 basic_string<_CharT, _Traits, _Alloc>:: 776 rfind(_CharT __c, size_type __pos) const 777 { 778 size_type __size = this->size(); 779 if (__size) 780 { 781 if (--__size > __pos) 782 __size = __pos; 783 for (++__size; __size-- > 0; ) 784 if (traits_type::eq(_M_data()[__size], __c)) 785 return __size; 786 } 787 return npos; 788 } 789 790 template<typename _CharT, typename _Traits, typename _Alloc> 791 typename basic_string<_CharT, _Traits, _Alloc>::size_type 792 basic_string<_CharT, _Traits, _Alloc>:: 793 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 794 { 795 __glibcxx_requires_string_len(__s, __n); 796 for (; __n && __pos < this->size(); ++__pos) 797 { 798 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 799 if (__p) 800 return __pos; 801 } 802 return npos; 803 } 804 805 template<typename _CharT, typename _Traits, typename _Alloc> 806 typename basic_string<_CharT, _Traits, _Alloc>::size_type 807 basic_string<_CharT, _Traits, _Alloc>:: 808 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 809 { 810 __glibcxx_requires_string_len(__s, __n); 811 size_type __size = this->size(); 812 if (__size && __n) 813 { 814 if (--__size > __pos) 815 __size = __pos; 816 do 817 { 818 if (traits_type::find(__s, __n, _M_data()[__size])) 819 return __size; 820 } 821 while (__size-- != 0); 822 } 823 return npos; 824 } 825 826 template<typename _CharT, typename _Traits, typename _Alloc> 827 typename basic_string<_CharT, _Traits, _Alloc>::size_type 828 basic_string<_CharT, _Traits, _Alloc>:: 829 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 830 { 831 __glibcxx_requires_string_len(__s, __n); 832 for (; __pos < this->size(); ++__pos) 833 if (!traits_type::find(__s, __n, _M_data()[__pos])) 834 return __pos; 835 return npos; 836 } 837 838 template<typename _CharT, typename _Traits, typename _Alloc> 839 typename basic_string<_CharT, _Traits, _Alloc>::size_type 840 basic_string<_CharT, _Traits, _Alloc>:: 841 find_first_not_of(_CharT __c, size_type __pos) const 842 { 843 for (; __pos < this->size(); ++__pos) 844 if (!traits_type::eq(_M_data()[__pos], __c)) 845 return __pos; 846 return npos; 847 } 848 849 template<typename _CharT, typename _Traits, typename _Alloc> 850 typename basic_string<_CharT, _Traits, _Alloc>::size_type 851 basic_string<_CharT, _Traits, _Alloc>:: 852 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 853 { 854 __glibcxx_requires_string_len(__s, __n); 855 size_type __size = this->size(); 856 if (__size) 857 { 858 if (--__size > __pos) 859 __size = __pos; 860 do 861 { 862 if (!traits_type::find(__s, __n, _M_data()[__size])) 863 return __size; 864 } 865 while (__size--); 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>:: 873 find_last_not_of(_CharT __c, size_type __pos) const 874 { 875 size_type __size = this->size(); 876 if (__size) 877 { 878 if (--__size > __pos) 879 __size = __pos; 880 do 881 { 882 if (!traits_type::eq(_M_data()[__size], __c)) 883 return __size; 884 } 885 while (__size--); 886 } 887 return npos; 888 } 889 890 template<typename _CharT, typename _Traits, typename _Alloc> 891 int 892 basic_string<_CharT, _Traits, _Alloc>:: 893 compare(size_type __pos, size_type __n, const basic_string& __str) const 894 { 895 _M_check(__pos, "basic_string::compare"); 896 __n = _M_limit(__pos, __n); 897 const size_type __osize = __str.size(); 898 const size_type __len = std::min(__n, __osize); 899 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 900 if (!__r) 901 __r = __n - __osize; 902 return __r; 903 } 904 905 template<typename _CharT, typename _Traits, typename _Alloc> 906 int 907 basic_string<_CharT, _Traits, _Alloc>:: 908 compare(size_type __pos1, size_type __n1, const basic_string& __str, 909 size_type __pos2, size_type __n2) const 910 { 911 _M_check(__pos1, "basic_string::compare"); 912 __str._M_check(__pos2, "basic_string::compare"); 913 __n1 = _M_limit(__pos1, __n1); 914 __n2 = __str._M_limit(__pos2, __n2); 915 const size_type __len = std::min(__n1, __n2); 916 int __r = traits_type::compare(_M_data() + __pos1, 917 __str.data() + __pos2, __len); 918 if (!__r) 919 __r = __n1 - __n2; 920 return __r; 921 } 922 923 template<typename _CharT, typename _Traits, typename _Alloc> 924 int 925 basic_string<_CharT, _Traits, _Alloc>:: 926 compare(const _CharT* __s) const 927 { 928 __glibcxx_requires_string(__s); 929 const size_type __size = this->size(); 930 const size_type __osize = traits_type::length(__s); 931 const size_type __len = std::min(__size, __osize); 932 int __r = traits_type::compare(_M_data(), __s, __len); 933 if (!__r) 934 __r = __size - __osize; 935 return __r; 936 } 937 938 template<typename _CharT, typename _Traits, typename _Alloc> 939 int 940 basic_string <_CharT, _Traits, _Alloc>:: 941 compare(size_type __pos, size_type __n1, const _CharT* __s) const 942 { 943 __glibcxx_requires_string(__s); 944 _M_check(__pos, "basic_string::compare"); 945 __n1 = _M_limit(__pos, __n1); 946 const size_type __osize = traits_type::length(__s); 947 const size_type __len = std::min(__n1, __osize); 948 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 949 if (!__r) 950 __r = __n1 - __osize; 951 return __r; 952 } 953 954 template<typename _CharT, typename _Traits, typename _Alloc> 955 int 956 basic_string <_CharT, _Traits, _Alloc>:: 957 compare(size_type __pos, size_type __n1, const _CharT* __s, 958 size_type __n2) const 959 { 960 __glibcxx_requires_string_len(__s, __n2); 961 _M_check(__pos, "basic_string::compare"); 962 __n1 = _M_limit(__pos, __n1); 963 const size_type __len = std::min(__n1, __n2); 964 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 965 if (!__r) 966 __r = __n1 - __n2; 967 return __r; 968 } 969 970 // Inhibit implicit instantiations for required instantiations, 971 // which are defined via explicit instantiations elsewhere. 972 // NB: This syntax is a GNU extension. 973#if _GLIBCXX_EXTERN_TEMPLATE 974 extern template class basic_string<char>; 975 extern template 976 basic_istream<char>& 977 operator>>(basic_istream<char>&, string&); 978 extern template 979 basic_ostream<char>& 980 operator<<(basic_ostream<char>&, const string&); 981 extern template 982 basic_istream<char>& 983 getline(basic_istream<char>&, string&, char); 984 extern template 985 basic_istream<char>& 986 getline(basic_istream<char>&, string&); 987 988#ifdef _GLIBCXX_USE_WCHAR_T 989 extern template class basic_string<wchar_t>; 990 extern template 991 basic_istream<wchar_t>& 992 operator>>(basic_istream<wchar_t>&, wstring&); 993 extern template 994 basic_ostream<wchar_t>& 995 operator<<(basic_ostream<wchar_t>&, const wstring&); 996 extern template 997 basic_istream<wchar_t>& 998 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 999 extern template 1000 basic_istream<wchar_t>& 1001 getline(basic_istream<wchar_t>&, wstring&); 1002#endif 1003#endif 1004} // namespace std 1005 1006#endif 1007