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