1 // Components for manipulating sequences of characters -*- C++ -*- 2 3 // Copyright (C) 1997-2020 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /** @file bits/basic_string.tcc 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{string} 28 */ 29 30 // 31 // ISO C++ 14882: 21 Strings library 32 // 33 34 // Written by Jason Merrill based upon the specification by Takanori Adachi 35 // in ANSI X3J16/94-0013R2. Rewritten by Nathan Myers to ISO-14882. 36 // Non-reference-counted implementation written by Paolo Carlini and 37 // updated by Jonathan Wakely for ISO-14882-2011. 38 39 #ifndef _BASIC_STRING_TCC 40 #define _BASIC_STRING_TCC 1 41 42 #pragma GCC system_header 43 44 #include <bits/cxxabi_forced.h> 45 46 namespace std _GLIBCXX_VISIBILITY(default) 47 { 48 _GLIBCXX_BEGIN_NAMESPACE_VERSION 49 50 #if _GLIBCXX_USE_CXX11_ABI 51 52 template<typename _CharT, typename _Traits, typename _Alloc> 53 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 54 basic_string<_CharT, _Traits, _Alloc>::npos; 55 56 template<typename _CharT, typename _Traits, typename _Alloc> 57 void 58 basic_string<_CharT, _Traits, _Alloc>:: swap(basic_string & __s)59 swap(basic_string& __s) _GLIBCXX_NOEXCEPT 60 { 61 if (this == &__s) 62 return; 63 64 _Alloc_traits::_S_on_swap(_M_get_allocator(), __s._M_get_allocator()); 65 66 if (_M_is_local()) 67 if (__s._M_is_local()) 68 { 69 if (length() && __s.length()) 70 { 71 _CharT __tmp_data[_S_local_capacity + 1]; 72 traits_type::copy(__tmp_data, __s._M_local_buf, 73 _S_local_capacity + 1); 74 traits_type::copy(__s._M_local_buf, _M_local_buf, 75 _S_local_capacity + 1); 76 traits_type::copy(_M_local_buf, __tmp_data, 77 _S_local_capacity + 1); 78 } 79 else if (__s.length()) 80 { 81 traits_type::copy(_M_local_buf, __s._M_local_buf, 82 _S_local_capacity + 1); 83 _M_length(__s.length()); 84 __s._M_set_length(0); 85 return; 86 } 87 else if (length()) 88 { 89 traits_type::copy(__s._M_local_buf, _M_local_buf, 90 _S_local_capacity + 1); 91 __s._M_length(length()); 92 _M_set_length(0); 93 return; 94 } 95 } 96 else 97 { 98 const size_type __tmp_capacity = __s._M_allocated_capacity; 99 traits_type::copy(__s._M_local_buf, _M_local_buf, 100 _S_local_capacity + 1); 101 _M_data(__s._M_data()); 102 __s._M_data(__s._M_local_buf); 103 _M_capacity(__tmp_capacity); 104 } 105 else 106 { 107 const size_type __tmp_capacity = _M_allocated_capacity; 108 if (__s._M_is_local()) 109 { 110 traits_type::copy(_M_local_buf, __s._M_local_buf, 111 _S_local_capacity + 1); 112 __s._M_data(_M_data()); 113 _M_data(_M_local_buf); 114 } 115 else 116 { 117 pointer __tmp_ptr = _M_data(); 118 _M_data(__s._M_data()); 119 __s._M_data(__tmp_ptr); 120 _M_capacity(__s._M_allocated_capacity); 121 } 122 __s._M_capacity(__tmp_capacity); 123 } 124 125 const size_type __tmp_length = length(); 126 _M_length(__s.length()); 127 __s._M_length(__tmp_length); 128 } 129 130 template<typename _CharT, typename _Traits, typename _Alloc> 131 typename basic_string<_CharT, _Traits, _Alloc>::pointer 132 basic_string<_CharT, _Traits, _Alloc>:: _M_create(size_type & __capacity,size_type __old_capacity)133 _M_create(size_type& __capacity, size_type __old_capacity) 134 { 135 // _GLIBCXX_RESOLVE_LIB_DEFECTS 136 // 83. String::npos vs. string::max_size() 137 if (__capacity > max_size()) 138 std::__throw_length_error(__N("basic_string::_M_create")); 139 140 // The below implements an exponential growth policy, necessary to 141 // meet amortized linear time requirements of the library: see 142 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 143 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 144 { 145 __capacity = 2 * __old_capacity; 146 // Never allocate a string bigger than max_size. 147 if (__capacity > max_size()) 148 __capacity = max_size(); 149 } 150 151 // NB: Need an array of char_type[__capacity], plus a terminating 152 // null char_type() element. 153 return _Alloc_traits::allocate(_M_get_allocator(), __capacity + 1); 154 } 155 156 // NB: This is the special case for Input Iterators, used in 157 // istreambuf_iterators, etc. 158 // Input Iterators have a cost structure very different from 159 // pointers, calling for a different coding style. 160 template<typename _CharT, typename _Traits, typename _Alloc> 161 template<typename _InIterator> 162 void 163 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(_InIterator __beg,_InIterator __end,std::input_iterator_tag)164 _M_construct(_InIterator __beg, _InIterator __end, 165 std::input_iterator_tag) 166 { 167 size_type __len = 0; 168 size_type __capacity = size_type(_S_local_capacity); 169 170 while (__beg != __end && __len < __capacity) 171 { 172 _M_data()[__len++] = *__beg; 173 ++__beg; 174 } 175 176 __try 177 { 178 while (__beg != __end) 179 { 180 if (__len == __capacity) 181 { 182 // Allocate more space. 183 __capacity = __len + 1; 184 pointer __another = _M_create(__capacity, __len); 185 this->_S_copy(__another, _M_data(), __len); 186 _M_dispose(); 187 _M_data(__another); 188 _M_capacity(__capacity); 189 } 190 _M_data()[__len++] = *__beg; 191 ++__beg; 192 } 193 } 194 __catch(...) 195 { 196 _M_dispose(); 197 __throw_exception_again; 198 } 199 200 _M_set_length(__len); 201 } 202 203 template<typename _CharT, typename _Traits, typename _Alloc> 204 template<typename _InIterator> 205 void 206 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(_InIterator __beg,_InIterator __end,std::forward_iterator_tag)207 _M_construct(_InIterator __beg, _InIterator __end, 208 std::forward_iterator_tag) 209 { 210 // NB: Not required, but considered best practice. 211 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 212 std::__throw_logic_error(__N("basic_string::" 213 "_M_construct null not valid")); 214 215 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 216 217 if (__dnew > size_type(_S_local_capacity)) 218 { 219 _M_data(_M_create(__dnew, size_type(0))); 220 _M_capacity(__dnew); 221 } 222 223 // Check for out_of_range and length_error exceptions. 224 __try 225 { this->_S_copy_chars(_M_data(), __beg, __end); } 226 __catch(...) 227 { 228 _M_dispose(); 229 __throw_exception_again; 230 } 231 232 _M_set_length(__dnew); 233 } 234 235 template<typename _CharT, typename _Traits, typename _Alloc> 236 void 237 basic_string<_CharT, _Traits, _Alloc>:: _M_construct(size_type __n,_CharT __c)238 _M_construct(size_type __n, _CharT __c) 239 { 240 if (__n > size_type(_S_local_capacity)) 241 { 242 _M_data(_M_create(__n, size_type(0))); 243 _M_capacity(__n); 244 } 245 246 if (__n) 247 this->_S_assign(_M_data(), __n, __c); 248 249 _M_set_length(__n); 250 } 251 252 template<typename _CharT, typename _Traits, typename _Alloc> 253 void 254 basic_string<_CharT, _Traits, _Alloc>:: _M_assign(const basic_string & __str)255 _M_assign(const basic_string& __str) 256 { 257 if (this != &__str) 258 { 259 const size_type __rsize = __str.length(); 260 const size_type __capacity = capacity(); 261 262 if (__rsize > __capacity) 263 { 264 size_type __new_capacity = __rsize; 265 pointer __tmp = _M_create(__new_capacity, __capacity); 266 _M_dispose(); 267 _M_data(__tmp); 268 _M_capacity(__new_capacity); 269 } 270 271 if (__rsize) 272 this->_S_copy(_M_data(), __str._M_data(), __rsize); 273 274 _M_set_length(__rsize); 275 } 276 } 277 278 template<typename _CharT, typename _Traits, typename _Alloc> 279 void 280 basic_string<_CharT, _Traits, _Alloc>:: reserve(size_type __res)281 reserve(size_type __res) 282 { 283 // Make sure we don't shrink below the current size. 284 if (__res < length()) 285 __res = length(); 286 287 const size_type __capacity = capacity(); 288 if (__res != __capacity) 289 { 290 if (__res > __capacity 291 || __res > size_type(_S_local_capacity)) 292 { 293 pointer __tmp = _M_create(__res, __capacity); 294 this->_S_copy(__tmp, _M_data(), length() + 1); 295 _M_dispose(); 296 _M_data(__tmp); 297 _M_capacity(__res); 298 } 299 else if (!_M_is_local()) 300 { 301 this->_S_copy(_M_local_data(), _M_data(), length() + 1); 302 _M_destroy(__capacity); 303 _M_data(_M_local_data()); 304 } 305 } 306 } 307 308 template<typename _CharT, typename _Traits, typename _Alloc> 309 void 310 basic_string<_CharT, _Traits, _Alloc>:: _M_mutate(size_type __pos,size_type __len1,const _CharT * __s,size_type __len2)311 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 312 size_type __len2) 313 { 314 const size_type __how_much = length() - __pos - __len1; 315 316 size_type __new_capacity = length() + __len2 - __len1; 317 pointer __r = _M_create(__new_capacity, capacity()); 318 319 if (__pos) 320 this->_S_copy(__r, _M_data(), __pos); 321 if (__s && __len2) 322 this->_S_copy(__r + __pos, __s, __len2); 323 if (__how_much) 324 this->_S_copy(__r + __pos + __len2, 325 _M_data() + __pos + __len1, __how_much); 326 327 _M_dispose(); 328 _M_data(__r); 329 _M_capacity(__new_capacity); 330 } 331 332 template<typename _CharT, typename _Traits, typename _Alloc> 333 void 334 basic_string<_CharT, _Traits, _Alloc>:: _M_erase(size_type __pos,size_type __n)335 _M_erase(size_type __pos, size_type __n) 336 { 337 const size_type __how_much = length() - __pos - __n; 338 339 if (__how_much && __n) 340 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 341 342 _M_set_length(length() - __n); 343 } 344 345 template<typename _CharT, typename _Traits, typename _Alloc> 346 void 347 basic_string<_CharT, _Traits, _Alloc>:: resize(size_type __n,_CharT __c)348 resize(size_type __n, _CharT __c) 349 { 350 const size_type __size = this->size(); 351 if (__size < __n) 352 this->append(__n - __size, __c); 353 else if (__n < __size) 354 this->_M_set_length(__n); 355 } 356 357 template<typename _CharT, typename _Traits, typename _Alloc> 358 basic_string<_CharT, _Traits, _Alloc>& 359 basic_string<_CharT, _Traits, _Alloc>:: _M_append(const _CharT * __s,size_type __n)360 _M_append(const _CharT* __s, size_type __n) 361 { 362 const size_type __len = __n + this->size(); 363 364 if (__len <= this->capacity()) 365 { 366 if (__n) 367 this->_S_copy(this->_M_data() + this->size(), __s, __n); 368 } 369 else 370 this->_M_mutate(this->size(), size_type(0), __s, __n); 371 372 this->_M_set_length(__len); 373 return *this; 374 } 375 376 template<typename _CharT, typename _Traits, typename _Alloc> 377 template<typename _InputIterator> 378 basic_string<_CharT, _Traits, _Alloc>& 379 basic_string<_CharT, _Traits, _Alloc>:: _M_replace_dispatch(const_iterator __i1,const_iterator __i2,_InputIterator __k1,_InputIterator __k2,std::__false_type)380 _M_replace_dispatch(const_iterator __i1, const_iterator __i2, 381 _InputIterator __k1, _InputIterator __k2, 382 std::__false_type) 383 { 384 // _GLIBCXX_RESOLVE_LIB_DEFECTS 385 // 2788. unintentionally require a default constructible allocator 386 const basic_string __s(__k1, __k2, this->get_allocator()); 387 const size_type __n1 = __i2 - __i1; 388 return _M_replace(__i1 - begin(), __n1, __s._M_data(), 389 __s.size()); 390 } 391 392 template<typename _CharT, typename _Traits, typename _Alloc> 393 basic_string<_CharT, _Traits, _Alloc>& 394 basic_string<_CharT, _Traits, _Alloc>:: _M_replace_aux(size_type __pos1,size_type __n1,size_type __n2,_CharT __c)395 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 396 _CharT __c) 397 { 398 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 399 400 const size_type __old_size = this->size(); 401 const size_type __new_size = __old_size + __n2 - __n1; 402 403 if (__new_size <= this->capacity()) 404 { 405 pointer __p = this->_M_data() + __pos1; 406 407 const size_type __how_much = __old_size - __pos1 - __n1; 408 if (__how_much && __n1 != __n2) 409 this->_S_move(__p + __n2, __p + __n1, __how_much); 410 } 411 else 412 this->_M_mutate(__pos1, __n1, 0, __n2); 413 414 if (__n2) 415 this->_S_assign(this->_M_data() + __pos1, __n2, __c); 416 417 this->_M_set_length(__new_size); 418 return *this; 419 } 420 421 template<typename _CharT, typename _Traits, typename _Alloc> 422 basic_string<_CharT, _Traits, _Alloc>& 423 basic_string<_CharT, _Traits, _Alloc>:: _M_replace(size_type __pos,size_type __len1,const _CharT * __s,const size_type __len2)424 _M_replace(size_type __pos, size_type __len1, const _CharT* __s, 425 const size_type __len2) 426 { 427 _M_check_length(__len1, __len2, "basic_string::_M_replace"); 428 429 const size_type __old_size = this->size(); 430 const size_type __new_size = __old_size + __len2 - __len1; 431 432 if (__new_size <= this->capacity()) 433 { 434 pointer __p = this->_M_data() + __pos; 435 436 const size_type __how_much = __old_size - __pos - __len1; 437 if (_M_disjunct(__s)) 438 { 439 if (__how_much && __len1 != __len2) 440 this->_S_move(__p + __len2, __p + __len1, __how_much); 441 if (__len2) 442 this->_S_copy(__p, __s, __len2); 443 } 444 else 445 { 446 // Work in-place. 447 if (__len2 && __len2 <= __len1) 448 this->_S_move(__p, __s, __len2); 449 if (__how_much && __len1 != __len2) 450 this->_S_move(__p + __len2, __p + __len1, __how_much); 451 if (__len2 > __len1) 452 { 453 if (__s + __len2 <= __p + __len1) 454 this->_S_move(__p, __s, __len2); 455 else if (__s >= __p + __len1) 456 this->_S_copy(__p, __s + __len2 - __len1, __len2); 457 else 458 { 459 const size_type __nleft = (__p + __len1) - __s; 460 this->_S_move(__p, __s, __nleft); 461 this->_S_copy(__p + __nleft, __p + __len2, 462 __len2 - __nleft); 463 } 464 } 465 } 466 } 467 else 468 this->_M_mutate(__pos, __len1, __s, __len2); 469 470 this->_M_set_length(__new_size); 471 return *this; 472 } 473 474 template<typename _CharT, typename _Traits, typename _Alloc> 475 typename basic_string<_CharT, _Traits, _Alloc>::size_type 476 basic_string<_CharT, _Traits, _Alloc>:: copy(_CharT * __s,size_type __n,size_type __pos) const477 copy(_CharT* __s, size_type __n, size_type __pos) const 478 { 479 _M_check(__pos, "basic_string::copy"); 480 __n = _M_limit(__pos, __n); 481 __glibcxx_requires_string_len(__s, __n); 482 if (__n) 483 _S_copy(__s, _M_data() + __pos, __n); 484 // 21.3.5.7 par 3: do not append null. (good.) 485 return __n; 486 } 487 488 #else // !_GLIBCXX_USE_CXX11_ABI 489 490 template<typename _CharT, typename _Traits, typename _Alloc> 491 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 492 basic_string<_CharT, _Traits, _Alloc>:: 493 _Rep::_S_max_size = (((npos - sizeof(_Rep_base))/sizeof(_CharT)) - 1) / 4; 494 495 template<typename _CharT, typename _Traits, typename _Alloc> 496 const _CharT 497 basic_string<_CharT, _Traits, _Alloc>:: 498 _Rep::_S_terminal = _CharT(); 499 500 template<typename _CharT, typename _Traits, typename _Alloc> 501 const typename basic_string<_CharT, _Traits, _Alloc>::size_type 502 basic_string<_CharT, _Traits, _Alloc>::npos; 503 504 // Linker sets _S_empty_rep_storage to all 0s (one reference, empty string) 505 // at static init time (before static ctors are run). 506 template<typename _CharT, typename _Traits, typename _Alloc> 507 typename basic_string<_CharT, _Traits, _Alloc>::size_type 508 basic_string<_CharT, _Traits, _Alloc>::_Rep::_S_empty_rep_storage[ 509 (sizeof(_Rep_base) + sizeof(_CharT) + sizeof(size_type) - 1) / 510 sizeof(size_type)]; 511 512 // NB: This is the special case for Input Iterators, used in 513 // istreambuf_iterators, etc. 514 // Input Iterators have a cost structure very different from 515 // pointers, calling for a different coding style. 516 template<typename _CharT, typename _Traits, typename _Alloc> 517 template<typename _InIterator> 518 _CharT* 519 basic_string<_CharT, _Traits, _Alloc>:: 520 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 521 input_iterator_tag) 522 { 523 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 524 if (__beg == __end && __a == _Alloc()) 525 return _S_empty_rep()._M_refdata(); 526 #endif 527 // Avoid reallocation for common case. 528 _CharT __buf[128]; 529 size_type __len = 0; 530 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT)) 531 { 532 __buf[__len++] = *__beg; 533 ++__beg; 534 } 535 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a); 536 _M_copy(__r->_M_refdata(), __buf, __len); 537 __try 538 { 539 while (__beg != __end) 540 { 541 if (__len == __r->_M_capacity) 542 { 543 // Allocate more space. 544 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a); 545 _M_copy(__another->_M_refdata(), __r->_M_refdata(), __len); 546 __r->_M_destroy(__a); 547 __r = __another; 548 } 549 __r->_M_refdata()[__len++] = *__beg; 550 ++__beg; 551 } 552 } 553 __catch(...) 554 { 555 __r->_M_destroy(__a); 556 __throw_exception_again; 557 } 558 __r->_M_set_length_and_sharable(__len); 559 return __r->_M_refdata(); 560 } 561 562 template<typename _CharT, typename _Traits, typename _Alloc> 563 template <typename _InIterator> 564 _CharT* 565 basic_string<_CharT, _Traits, _Alloc>:: 566 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a, 567 forward_iterator_tag) 568 { 569 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 570 if (__beg == __end && __a == _Alloc()) 571 return _S_empty_rep()._M_refdata(); 572 #endif 573 // NB: Not required, but considered best practice. 574 if (__gnu_cxx::__is_null_pointer(__beg) && __beg != __end) 575 __throw_logic_error(__N("basic_string::_S_construct null not valid")); 576 577 const size_type __dnew = static_cast<size_type>(std::distance(__beg, 578 __end)); 579 // Check for out_of_range and length_error exceptions. 580 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a); 581 __try 582 { _S_copy_chars(__r->_M_refdata(), __beg, __end); } 583 __catch(...) 584 { 585 __r->_M_destroy(__a); 586 __throw_exception_again; 587 } 588 __r->_M_set_length_and_sharable(__dnew); 589 return __r->_M_refdata(); 590 } 591 592 template<typename _CharT, typename _Traits, typename _Alloc> 593 _CharT* 594 basic_string<_CharT, _Traits, _Alloc>:: 595 _S_construct(size_type __n, _CharT __c, const _Alloc& __a) 596 { 597 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 598 if (__n == 0 && __a == _Alloc()) 599 return _S_empty_rep()._M_refdata(); 600 #endif 601 // Check for out_of_range and length_error exceptions. 602 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a); 603 if (__n) 604 _M_assign(__r->_M_refdata(), __n, __c); 605 606 __r->_M_set_length_and_sharable(__n); 607 return __r->_M_refdata(); 608 } 609 610 template<typename _CharT, typename _Traits, typename _Alloc> 611 basic_string<_CharT, _Traits, _Alloc>:: 612 basic_string(const basic_string& __str) 613 : _M_dataplus(__str._M_rep()->_M_grab(_Alloc(__str.get_allocator()), 614 __str.get_allocator()), 615 __str.get_allocator()) 616 { } 617 618 template<typename _CharT, typename _Traits, typename _Alloc> 619 basic_string<_CharT, _Traits, _Alloc>:: 620 basic_string(const _Alloc& __a) 621 : _M_dataplus(_S_construct(size_type(), _CharT(), __a), __a) 622 { } 623 624 template<typename _CharT, typename _Traits, typename _Alloc> 625 basic_string<_CharT, _Traits, _Alloc>:: 626 basic_string(const basic_string& __str, size_type __pos, const _Alloc& __a) 627 : _M_dataplus(_S_construct(__str._M_data() 628 + __str._M_check(__pos, 629 "basic_string::basic_string"), 630 __str._M_data() + __str._M_limit(__pos, npos) 631 + __pos, __a), __a) 632 { } 633 634 template<typename _CharT, typename _Traits, typename _Alloc> 635 basic_string<_CharT, _Traits, _Alloc>:: 636 basic_string(const basic_string& __str, size_type __pos, size_type __n) 637 : _M_dataplus(_S_construct(__str._M_data() 638 + __str._M_check(__pos, 639 "basic_string::basic_string"), 640 __str._M_data() + __str._M_limit(__pos, __n) 641 + __pos, _Alloc()), _Alloc()) 642 { } 643 644 template<typename _CharT, typename _Traits, typename _Alloc> 645 basic_string<_CharT, _Traits, _Alloc>:: 646 basic_string(const basic_string& __str, size_type __pos, 647 size_type __n, const _Alloc& __a) 648 : _M_dataplus(_S_construct(__str._M_data() 649 + __str._M_check(__pos, 650 "basic_string::basic_string"), 651 __str._M_data() + __str._M_limit(__pos, __n) 652 + __pos, __a), __a) 653 { } 654 655 // TBD: DPG annotate 656 template<typename _CharT, typename _Traits, typename _Alloc> 657 basic_string<_CharT, _Traits, _Alloc>:: 658 basic_string(const _CharT* __s, size_type __n, const _Alloc& __a) 659 : _M_dataplus(_S_construct(__s, __s + __n, __a), __a) 660 { } 661 662 template<typename _CharT, typename _Traits, typename _Alloc> 663 basic_string<_CharT, _Traits, _Alloc>:: 664 basic_string(size_type __n, _CharT __c, const _Alloc& __a) 665 : _M_dataplus(_S_construct(__n, __c, __a), __a) 666 { } 667 668 // TBD: DPG annotate 669 template<typename _CharT, typename _Traits, typename _Alloc> 670 template<typename _InputIterator> 671 basic_string<_CharT, _Traits, _Alloc>:: 672 basic_string(_InputIterator __beg, _InputIterator __end, const _Alloc& __a) 673 : _M_dataplus(_S_construct(__beg, __end, __a), __a) 674 { } 675 676 #if __cplusplus >= 201103L 677 template<typename _CharT, typename _Traits, typename _Alloc> 678 basic_string<_CharT, _Traits, _Alloc>:: 679 basic_string(initializer_list<_CharT> __l, const _Alloc& __a) 680 : _M_dataplus(_S_construct(__l.begin(), __l.end(), __a), __a) 681 { } 682 #endif 683 684 template<typename _CharT, typename _Traits, typename _Alloc> 685 basic_string<_CharT, _Traits, _Alloc>& 686 basic_string<_CharT, _Traits, _Alloc>:: 687 assign(const basic_string& __str) 688 { 689 if (_M_rep() != __str._M_rep()) 690 { 691 // XXX MT 692 const allocator_type __a = this->get_allocator(); 693 _CharT* __tmp = __str._M_rep()->_M_grab(__a, __str.get_allocator()); 694 _M_rep()->_M_dispose(__a); 695 _M_data(__tmp); 696 } 697 return *this; 698 } 699 700 template<typename _CharT, typename _Traits, typename _Alloc> 701 basic_string<_CharT, _Traits, _Alloc>& 702 basic_string<_CharT, _Traits, _Alloc>:: 703 assign(const _CharT* __s, size_type __n) 704 { 705 __glibcxx_requires_string_len(__s, __n); 706 _M_check_length(this->size(), __n, "basic_string::assign"); 707 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 708 return _M_replace_safe(size_type(0), this->size(), __s, __n); 709 else 710 { 711 // Work in-place. 712 const size_type __pos = __s - _M_data(); 713 if (__pos >= __n) 714 _M_copy(_M_data(), __s, __n); 715 else if (__pos) 716 _M_move(_M_data(), __s, __n); 717 _M_rep()->_M_set_length_and_sharable(__n); 718 return *this; 719 } 720 } 721 722 template<typename _CharT, typename _Traits, typename _Alloc> 723 basic_string<_CharT, _Traits, _Alloc>& 724 basic_string<_CharT, _Traits, _Alloc>:: 725 append(size_type __n, _CharT __c) 726 { 727 if (__n) 728 { 729 _M_check_length(size_type(0), __n, "basic_string::append"); 730 const size_type __len = __n + this->size(); 731 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 732 this->reserve(__len); 733 _M_assign(_M_data() + this->size(), __n, __c); 734 _M_rep()->_M_set_length_and_sharable(__len); 735 } 736 return *this; 737 } 738 739 template<typename _CharT, typename _Traits, typename _Alloc> 740 basic_string<_CharT, _Traits, _Alloc>& 741 basic_string<_CharT, _Traits, _Alloc>:: 742 append(const _CharT* __s, size_type __n) 743 { 744 __glibcxx_requires_string_len(__s, __n); 745 if (__n) 746 { 747 _M_check_length(size_type(0), __n, "basic_string::append"); 748 const size_type __len = __n + this->size(); 749 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 750 { 751 if (_M_disjunct(__s)) 752 this->reserve(__len); 753 else 754 { 755 const size_type __off = __s - _M_data(); 756 this->reserve(__len); 757 __s = _M_data() + __off; 758 } 759 } 760 _M_copy(_M_data() + this->size(), __s, __n); 761 _M_rep()->_M_set_length_and_sharable(__len); 762 } 763 return *this; 764 } 765 766 template<typename _CharT, typename _Traits, typename _Alloc> 767 basic_string<_CharT, _Traits, _Alloc>& 768 basic_string<_CharT, _Traits, _Alloc>:: 769 append(const basic_string& __str) 770 { 771 const size_type __size = __str.size(); 772 if (__size) 773 { 774 const size_type __len = __size + this->size(); 775 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 776 this->reserve(__len); 777 _M_copy(_M_data() + this->size(), __str._M_data(), __size); 778 _M_rep()->_M_set_length_and_sharable(__len); 779 } 780 return *this; 781 } 782 783 template<typename _CharT, typename _Traits, typename _Alloc> 784 basic_string<_CharT, _Traits, _Alloc>& 785 basic_string<_CharT, _Traits, _Alloc>:: 786 append(const basic_string& __str, size_type __pos, size_type __n) 787 { 788 __str._M_check(__pos, "basic_string::append"); 789 __n = __str._M_limit(__pos, __n); 790 if (__n) 791 { 792 const size_type __len = __n + this->size(); 793 if (__len > this->capacity() || _M_rep()->_M_is_shared()) 794 this->reserve(__len); 795 _M_copy(_M_data() + this->size(), __str._M_data() + __pos, __n); 796 _M_rep()->_M_set_length_and_sharable(__len); 797 } 798 return *this; 799 } 800 801 template<typename _CharT, typename _Traits, typename _Alloc> 802 basic_string<_CharT, _Traits, _Alloc>& 803 basic_string<_CharT, _Traits, _Alloc>:: 804 insert(size_type __pos, const _CharT* __s, size_type __n) 805 { 806 __glibcxx_requires_string_len(__s, __n); 807 _M_check(__pos, "basic_string::insert"); 808 _M_check_length(size_type(0), __n, "basic_string::insert"); 809 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 810 return _M_replace_safe(__pos, size_type(0), __s, __n); 811 else 812 { 813 // Work in-place. 814 const size_type __off = __s - _M_data(); 815 _M_mutate(__pos, 0, __n); 816 __s = _M_data() + __off; 817 _CharT* __p = _M_data() + __pos; 818 if (__s + __n <= __p) 819 _M_copy(__p, __s, __n); 820 else if (__s >= __p) 821 _M_copy(__p, __s + __n, __n); 822 else 823 { 824 const size_type __nleft = __p - __s; 825 _M_copy(__p, __s, __nleft); 826 _M_copy(__p + __nleft, __p + __n, __n - __nleft); 827 } 828 return *this; 829 } 830 } 831 832 template<typename _CharT, typename _Traits, typename _Alloc> 833 typename basic_string<_CharT, _Traits, _Alloc>::iterator 834 basic_string<_CharT, _Traits, _Alloc>:: 835 erase(iterator __first, iterator __last) 836 { 837 _GLIBCXX_DEBUG_PEDASSERT(__first >= _M_ibegin() && __first <= __last 838 && __last <= _M_iend()); 839 840 // NB: This isn't just an optimization (bail out early when 841 // there is nothing to do, really), it's also a correctness 842 // issue vs MT, see libstdc++/40518. 843 const size_type __size = __last - __first; 844 if (__size) 845 { 846 const size_type __pos = __first - _M_ibegin(); 847 _M_mutate(__pos, __size, size_type(0)); 848 _M_rep()->_M_set_leaked(); 849 return iterator(_M_data() + __pos); 850 } 851 else 852 return __first; 853 } 854 855 template<typename _CharT, typename _Traits, typename _Alloc> 856 basic_string<_CharT, _Traits, _Alloc>& 857 basic_string<_CharT, _Traits, _Alloc>:: 858 replace(size_type __pos, size_type __n1, const _CharT* __s, 859 size_type __n2) 860 { 861 __glibcxx_requires_string_len(__s, __n2); 862 _M_check(__pos, "basic_string::replace"); 863 __n1 = _M_limit(__pos, __n1); 864 _M_check_length(__n1, __n2, "basic_string::replace"); 865 bool __left; 866 if (_M_disjunct(__s) || _M_rep()->_M_is_shared()) 867 return _M_replace_safe(__pos, __n1, __s, __n2); 868 else if ((__left = __s + __n2 <= _M_data() + __pos) 869 || _M_data() + __pos + __n1 <= __s) 870 { 871 // Work in-place: non-overlapping case. 872 size_type __off = __s - _M_data(); 873 __left ? __off : (__off += __n2 - __n1); 874 _M_mutate(__pos, __n1, __n2); 875 _M_copy(_M_data() + __pos, _M_data() + __off, __n2); 876 return *this; 877 } 878 else 879 { 880 // Todo: overlapping case. 881 const basic_string __tmp(__s, __n2); 882 return _M_replace_safe(__pos, __n1, __tmp._M_data(), __n2); 883 } 884 } 885 886 template<typename _CharT, typename _Traits, typename _Alloc> 887 void 888 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 889 _M_destroy(const _Alloc& __a) throw () 890 { 891 const size_type __size = sizeof(_Rep_base) + 892 (this->_M_capacity + 1) * sizeof(_CharT); 893 _Raw_bytes_alloc(__a).deallocate(reinterpret_cast<char*>(this), __size); 894 } 895 896 template<typename _CharT, typename _Traits, typename _Alloc> 897 void 898 basic_string<_CharT, _Traits, _Alloc>:: 899 _M_leak_hard() 900 { 901 #if _GLIBCXX_FULLY_DYNAMIC_STRING == 0 902 if (_M_rep() == &_S_empty_rep()) 903 return; 904 #endif 905 if (_M_rep()->_M_is_shared()) 906 _M_mutate(0, 0, 0); 907 _M_rep()->_M_set_leaked(); 908 } 909 910 template<typename _CharT, typename _Traits, typename _Alloc> 911 void 912 basic_string<_CharT, _Traits, _Alloc>:: 913 _M_mutate(size_type __pos, size_type __len1, size_type __len2) 914 { 915 const size_type __old_size = this->size(); 916 const size_type __new_size = __old_size + __len2 - __len1; 917 const size_type __how_much = __old_size - __pos - __len1; 918 919 if (__new_size > this->capacity() || _M_rep()->_M_is_shared()) 920 { 921 // Must reallocate. 922 const allocator_type __a = get_allocator(); 923 _Rep* __r = _Rep::_S_create(__new_size, this->capacity(), __a); 924 925 if (__pos) 926 _M_copy(__r->_M_refdata(), _M_data(), __pos); 927 if (__how_much) 928 _M_copy(__r->_M_refdata() + __pos + __len2, 929 _M_data() + __pos + __len1, __how_much); 930 931 _M_rep()->_M_dispose(__a); 932 _M_data(__r->_M_refdata()); 933 } 934 else if (__how_much && __len1 != __len2) 935 { 936 // Work in-place. 937 _M_move(_M_data() + __pos + __len2, 938 _M_data() + __pos + __len1, __how_much); 939 } 940 _M_rep()->_M_set_length_and_sharable(__new_size); 941 } 942 943 template<typename _CharT, typename _Traits, typename _Alloc> 944 void 945 basic_string<_CharT, _Traits, _Alloc>:: 946 reserve(size_type __res) 947 { 948 if (__res != this->capacity() || _M_rep()->_M_is_shared()) 949 { 950 // Make sure we don't shrink below the current size 951 if (__res < this->size()) 952 __res = this->size(); 953 const allocator_type __a = get_allocator(); 954 _CharT* __tmp = _M_rep()->_M_clone(__a, __res - this->size()); 955 _M_rep()->_M_dispose(__a); 956 _M_data(__tmp); 957 } 958 } 959 960 template<typename _CharT, typename _Traits, typename _Alloc> 961 void 962 basic_string<_CharT, _Traits, _Alloc>:: 963 swap(basic_string& __s) 964 _GLIBCXX_NOEXCEPT_IF(allocator_traits<_Alloc>::is_always_equal::value) 965 { 966 if (_M_rep()->_M_is_leaked()) 967 _M_rep()->_M_set_sharable(); 968 if (__s._M_rep()->_M_is_leaked()) 969 __s._M_rep()->_M_set_sharable(); 970 if (this->get_allocator() == __s.get_allocator()) 971 { 972 _CharT* __tmp = _M_data(); 973 _M_data(__s._M_data()); 974 __s._M_data(__tmp); 975 } 976 // The code below can usually be optimized away. 977 else 978 { 979 const basic_string __tmp1(_M_ibegin(), _M_iend(), 980 __s.get_allocator()); 981 const basic_string __tmp2(__s._M_ibegin(), __s._M_iend(), 982 this->get_allocator()); 983 *this = __tmp2; 984 __s = __tmp1; 985 } 986 } 987 988 template<typename _CharT, typename _Traits, typename _Alloc> 989 typename basic_string<_CharT, _Traits, _Alloc>::_Rep* 990 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 991 _S_create(size_type __capacity, size_type __old_capacity, 992 const _Alloc& __alloc) 993 { 994 // _GLIBCXX_RESOLVE_LIB_DEFECTS 995 // 83. String::npos vs. string::max_size() 996 if (__capacity > _S_max_size) 997 __throw_length_error(__N("basic_string::_S_create")); 998 999 // The standard places no restriction on allocating more memory 1000 // than is strictly needed within this layer at the moment or as 1001 // requested by an explicit application call to reserve(). 1002 1003 // Many malloc implementations perform quite poorly when an 1004 // application attempts to allocate memory in a stepwise fashion 1005 // growing each allocation size by only 1 char. Additionally, 1006 // it makes little sense to allocate less linear memory than the 1007 // natural blocking size of the malloc implementation. 1008 // Unfortunately, we would need a somewhat low-level calculation 1009 // with tuned parameters to get this perfect for any particular 1010 // malloc implementation. Fortunately, generalizations about 1011 // common features seen among implementations seems to suffice. 1012 1013 // __pagesize need not match the actual VM page size for good 1014 // results in practice, thus we pick a common value on the low 1015 // side. __malloc_header_size is an estimate of the amount of 1016 // overhead per memory allocation (in practice seen N * sizeof 1017 // (void*) where N is 0, 2 or 4). According to folklore, 1018 // picking this value on the high side is better than 1019 // low-balling it (especially when this algorithm is used with 1020 // malloc implementations that allocate memory blocks rounded up 1021 // to a size which is a power of 2). 1022 const size_type __pagesize = 4096; 1023 const size_type __malloc_header_size = 4 * sizeof(void*); 1024 1025 // The below implements an exponential growth policy, necessary to 1026 // meet amortized linear time requirements of the library: see 1027 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 1028 // It's active for allocations requiring an amount of memory above 1029 // system pagesize. This is consistent with the requirements of the 1030 // standard: http://gcc.gnu.org/ml/libstdc++/2001-07/msg00130.html 1031 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 1032 __capacity = 2 * __old_capacity; 1033 1034 // NB: Need an array of char_type[__capacity], plus a terminating 1035 // null char_type() element, plus enough for the _Rep data structure. 1036 // Whew. Seemingly so needy, yet so elemental. 1037 size_type __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 1038 1039 const size_type __adj_size = __size + __malloc_header_size; 1040 if (__adj_size > __pagesize && __capacity > __old_capacity) 1041 { 1042 const size_type __extra = __pagesize - __adj_size % __pagesize; 1043 __capacity += __extra / sizeof(_CharT); 1044 // Never allocate a string bigger than _S_max_size. 1045 if (__capacity > _S_max_size) 1046 __capacity = _S_max_size; 1047 __size = (__capacity + 1) * sizeof(_CharT) + sizeof(_Rep); 1048 } 1049 1050 // NB: Might throw, but no worries about a leak, mate: _Rep() 1051 // does not throw. 1052 void* __place = _Raw_bytes_alloc(__alloc).allocate(__size); 1053 _Rep *__p = new (__place) _Rep; 1054 __p->_M_capacity = __capacity; 1055 // ABI compatibility - 3.4.x set in _S_create both 1056 // _M_refcount and _M_length. All callers of _S_create 1057 // in basic_string.tcc then set just _M_length. 1058 // In 4.0.x and later both _M_refcount and _M_length 1059 // are initialized in the callers, unfortunately we can 1060 // have 3.4.x compiled code with _S_create callers inlined 1061 // calling 4.0.x+ _S_create. 1062 __p->_M_set_sharable(); 1063 return __p; 1064 } 1065 1066 template<typename _CharT, typename _Traits, typename _Alloc> 1067 _CharT* 1068 basic_string<_CharT, _Traits, _Alloc>::_Rep:: 1069 _M_clone(const _Alloc& __alloc, size_type __res) 1070 { 1071 // Requested capacity of the clone. 1072 const size_type __requested_cap = this->_M_length + __res; 1073 _Rep* __r = _Rep::_S_create(__requested_cap, this->_M_capacity, 1074 __alloc); 1075 if (this->_M_length) 1076 _M_copy(__r->_M_refdata(), _M_refdata(), this->_M_length); 1077 1078 __r->_M_set_length_and_sharable(this->_M_length); 1079 return __r->_M_refdata(); 1080 } 1081 1082 template<typename _CharT, typename _Traits, typename _Alloc> 1083 void 1084 basic_string<_CharT, _Traits, _Alloc>:: 1085 resize(size_type __n, _CharT __c) 1086 { 1087 const size_type __size = this->size(); 1088 _M_check_length(__size, __n, "basic_string::resize"); 1089 if (__size < __n) 1090 this->append(__n - __size, __c); 1091 else if (__n < __size) 1092 this->erase(__n); 1093 // else nothing (in particular, avoid calling _M_mutate() unnecessarily.) 1094 } 1095 1096 template<typename _CharT, typename _Traits, typename _Alloc> 1097 template<typename _InputIterator> 1098 basic_string<_CharT, _Traits, _Alloc>& 1099 basic_string<_CharT, _Traits, _Alloc>:: 1100 _M_replace_dispatch(iterator __i1, iterator __i2, _InputIterator __k1, 1101 _InputIterator __k2, __false_type) 1102 { 1103 const basic_string __s(__k1, __k2); 1104 const size_type __n1 = __i2 - __i1; 1105 _M_check_length(__n1, __s.size(), "basic_string::_M_replace_dispatch"); 1106 return _M_replace_safe(__i1 - _M_ibegin(), __n1, __s._M_data(), 1107 __s.size()); 1108 } 1109 1110 template<typename _CharT, typename _Traits, typename _Alloc> 1111 basic_string<_CharT, _Traits, _Alloc>& 1112 basic_string<_CharT, _Traits, _Alloc>:: 1113 _M_replace_aux(size_type __pos1, size_type __n1, size_type __n2, 1114 _CharT __c) 1115 { 1116 _M_check_length(__n1, __n2, "basic_string::_M_replace_aux"); 1117 _M_mutate(__pos1, __n1, __n2); 1118 if (__n2) 1119 _M_assign(_M_data() + __pos1, __n2, __c); 1120 return *this; 1121 } 1122 1123 template<typename _CharT, typename _Traits, typename _Alloc> 1124 basic_string<_CharT, _Traits, _Alloc>& 1125 basic_string<_CharT, _Traits, _Alloc>:: 1126 _M_replace_safe(size_type __pos1, size_type __n1, const _CharT* __s, 1127 size_type __n2) 1128 { 1129 _M_mutate(__pos1, __n1, __n2); 1130 if (__n2) 1131 _M_copy(_M_data() + __pos1, __s, __n2); 1132 return *this; 1133 } 1134 1135 template<typename _CharT, typename _Traits, typename _Alloc> 1136 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1137 basic_string<_CharT, _Traits, _Alloc>:: 1138 copy(_CharT* __s, size_type __n, size_type __pos) const 1139 { 1140 _M_check(__pos, "basic_string::copy"); 1141 __n = _M_limit(__pos, __n); 1142 __glibcxx_requires_string_len(__s, __n); 1143 if (__n) 1144 _M_copy(__s, _M_data() + __pos, __n); 1145 // 21.3.5.7 par 3: do not append null. (good.) 1146 return __n; 1147 } 1148 #endif // !_GLIBCXX_USE_CXX11_ABI 1149 1150 template<typename _CharT, typename _Traits, typename _Alloc> 1151 basic_string<_CharT, _Traits, _Alloc> operator +(const _CharT * __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)1152 operator+(const _CharT* __lhs, 1153 const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1154 { 1155 __glibcxx_requires_string(__lhs); 1156 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1157 typedef typename __string_type::size_type __size_type; 1158 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1159 rebind<_CharT>::other _Char_alloc_type; 1160 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits; 1161 const __size_type __len = _Traits::length(__lhs); 1162 __string_type __str(_Alloc_traits::_S_select_on_copy( 1163 __rhs.get_allocator())); 1164 __str.reserve(__len + __rhs.size()); 1165 __str.append(__lhs, __len); 1166 __str.append(__rhs); 1167 return __str; 1168 } 1169 1170 template<typename _CharT, typename _Traits, typename _Alloc> 1171 basic_string<_CharT, _Traits, _Alloc> operator +(_CharT __lhs,const basic_string<_CharT,_Traits,_Alloc> & __rhs)1172 operator+(_CharT __lhs, const basic_string<_CharT, _Traits, _Alloc>& __rhs) 1173 { 1174 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1175 typedef typename __string_type::size_type __size_type; 1176 typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template 1177 rebind<_CharT>::other _Char_alloc_type; 1178 typedef __gnu_cxx::__alloc_traits<_Char_alloc_type> _Alloc_traits; 1179 __string_type __str(_Alloc_traits::_S_select_on_copy( 1180 __rhs.get_allocator())); 1181 const __size_type __len = __rhs.size(); 1182 __str.reserve(__len + 1); 1183 __str.append(__size_type(1), __lhs); 1184 __str.append(__rhs); 1185 return __str; 1186 } 1187 1188 template<typename _CharT, typename _Traits, typename _Alloc> 1189 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1190 basic_string<_CharT, _Traits, _Alloc>:: find(const _CharT * __s,size_type __pos,size_type __n) const1191 find(const _CharT* __s, size_type __pos, size_type __n) const 1192 _GLIBCXX_NOEXCEPT 1193 { 1194 __glibcxx_requires_string_len(__s, __n); 1195 const size_type __size = this->size(); 1196 1197 if (__n == 0) 1198 return __pos <= __size ? __pos : npos; 1199 if (__pos >= __size) 1200 return npos; 1201 1202 const _CharT __elem0 = __s[0]; 1203 const _CharT* const __data = data(); 1204 const _CharT* __first = __data + __pos; 1205 const _CharT* const __last = __data + __size; 1206 size_type __len = __size - __pos; 1207 1208 while (__len >= __n) 1209 { 1210 // Find the first occurrence of __elem0: 1211 __first = traits_type::find(__first, __len - __n + 1, __elem0); 1212 if (!__first) 1213 return npos; 1214 // Compare the full strings from the first occurrence of __elem0. 1215 // We already know that __first[0] == __s[0] but compare them again 1216 // anyway because __s is probably aligned, which helps memcmp. 1217 if (traits_type::compare(__first, __s, __n) == 0) 1218 return __first - __data; 1219 __len = __last - ++__first; 1220 } 1221 return npos; 1222 } 1223 1224 template<typename _CharT, typename _Traits, typename _Alloc> 1225 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1226 basic_string<_CharT, _Traits, _Alloc>:: find(_CharT __c,size_type __pos) const1227 find(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1228 { 1229 size_type __ret = npos; 1230 const size_type __size = this->size(); 1231 if (__pos < __size) 1232 { 1233 const _CharT* __data = _M_data(); 1234 const size_type __n = __size - __pos; 1235 const _CharT* __p = traits_type::find(__data + __pos, __n, __c); 1236 if (__p) 1237 __ret = __p - __data; 1238 } 1239 return __ret; 1240 } 1241 1242 template<typename _CharT, typename _Traits, typename _Alloc> 1243 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1244 basic_string<_CharT, _Traits, _Alloc>:: rfind(const _CharT * __s,size_type __pos,size_type __n) const1245 rfind(const _CharT* __s, size_type __pos, size_type __n) const 1246 _GLIBCXX_NOEXCEPT 1247 { 1248 __glibcxx_requires_string_len(__s, __n); 1249 const size_type __size = this->size(); 1250 if (__n <= __size) 1251 { 1252 __pos = std::min(size_type(__size - __n), __pos); 1253 const _CharT* __data = _M_data(); 1254 do 1255 { 1256 if (traits_type::compare(__data + __pos, __s, __n) == 0) 1257 return __pos; 1258 } 1259 while (__pos-- > 0); 1260 } 1261 return npos; 1262 } 1263 1264 template<typename _CharT, typename _Traits, typename _Alloc> 1265 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1266 basic_string<_CharT, _Traits, _Alloc>:: rfind(_CharT __c,size_type __pos) const1267 rfind(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1268 { 1269 size_type __size = this->size(); 1270 if (__size) 1271 { 1272 if (--__size > __pos) 1273 __size = __pos; 1274 for (++__size; __size-- > 0; ) 1275 if (traits_type::eq(_M_data()[__size], __c)) 1276 return __size; 1277 } 1278 return npos; 1279 } 1280 1281 template<typename _CharT, typename _Traits, typename _Alloc> 1282 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1283 basic_string<_CharT, _Traits, _Alloc>:: find_first_of(const _CharT * __s,size_type __pos,size_type __n) const1284 find_first_of(const _CharT* __s, size_type __pos, size_type __n) const 1285 _GLIBCXX_NOEXCEPT 1286 { 1287 __glibcxx_requires_string_len(__s, __n); 1288 for (; __n && __pos < this->size(); ++__pos) 1289 { 1290 const _CharT* __p = traits_type::find(__s, __n, _M_data()[__pos]); 1291 if (__p) 1292 return __pos; 1293 } 1294 return npos; 1295 } 1296 1297 template<typename _CharT, typename _Traits, typename _Alloc> 1298 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1299 basic_string<_CharT, _Traits, _Alloc>:: find_last_of(const _CharT * __s,size_type __pos,size_type __n) const1300 find_last_of(const _CharT* __s, size_type __pos, size_type __n) const 1301 _GLIBCXX_NOEXCEPT 1302 { 1303 __glibcxx_requires_string_len(__s, __n); 1304 size_type __size = this->size(); 1305 if (__size && __n) 1306 { 1307 if (--__size > __pos) 1308 __size = __pos; 1309 do 1310 { 1311 if (traits_type::find(__s, __n, _M_data()[__size])) 1312 return __size; 1313 } 1314 while (__size-- != 0); 1315 } 1316 return npos; 1317 } 1318 1319 template<typename _CharT, typename _Traits, typename _Alloc> 1320 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1321 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(const _CharT * __s,size_type __pos,size_type __n) const1322 find_first_not_of(const _CharT* __s, size_type __pos, size_type __n) const 1323 _GLIBCXX_NOEXCEPT 1324 { 1325 __glibcxx_requires_string_len(__s, __n); 1326 for (; __pos < this->size(); ++__pos) 1327 if (!traits_type::find(__s, __n, _M_data()[__pos])) 1328 return __pos; 1329 return npos; 1330 } 1331 1332 template<typename _CharT, typename _Traits, typename _Alloc> 1333 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1334 basic_string<_CharT, _Traits, _Alloc>:: find_first_not_of(_CharT __c,size_type __pos) const1335 find_first_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1336 { 1337 for (; __pos < this->size(); ++__pos) 1338 if (!traits_type::eq(_M_data()[__pos], __c)) 1339 return __pos; 1340 return npos; 1341 } 1342 1343 template<typename _CharT, typename _Traits, typename _Alloc> 1344 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1345 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(const _CharT * __s,size_type __pos,size_type __n) const1346 find_last_not_of(const _CharT* __s, size_type __pos, size_type __n) const 1347 _GLIBCXX_NOEXCEPT 1348 { 1349 __glibcxx_requires_string_len(__s, __n); 1350 size_type __size = this->size(); 1351 if (__size) 1352 { 1353 if (--__size > __pos) 1354 __size = __pos; 1355 do 1356 { 1357 if (!traits_type::find(__s, __n, _M_data()[__size])) 1358 return __size; 1359 } 1360 while (__size--); 1361 } 1362 return npos; 1363 } 1364 1365 template<typename _CharT, typename _Traits, typename _Alloc> 1366 typename basic_string<_CharT, _Traits, _Alloc>::size_type 1367 basic_string<_CharT, _Traits, _Alloc>:: find_last_not_of(_CharT __c,size_type __pos) const1368 find_last_not_of(_CharT __c, size_type __pos) const _GLIBCXX_NOEXCEPT 1369 { 1370 size_type __size = this->size(); 1371 if (__size) 1372 { 1373 if (--__size > __pos) 1374 __size = __pos; 1375 do 1376 { 1377 if (!traits_type::eq(_M_data()[__size], __c)) 1378 return __size; 1379 } 1380 while (__size--); 1381 } 1382 return npos; 1383 } 1384 1385 template<typename _CharT, typename _Traits, typename _Alloc> 1386 int 1387 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n,const basic_string & __str) const1388 compare(size_type __pos, size_type __n, const basic_string& __str) const 1389 { 1390 _M_check(__pos, "basic_string::compare"); 1391 __n = _M_limit(__pos, __n); 1392 const size_type __osize = __str.size(); 1393 const size_type __len = std::min(__n, __osize); 1394 int __r = traits_type::compare(_M_data() + __pos, __str.data(), __len); 1395 if (!__r) 1396 __r = _S_compare(__n, __osize); 1397 return __r; 1398 } 1399 1400 template<typename _CharT, typename _Traits, typename _Alloc> 1401 int 1402 basic_string<_CharT, _Traits, _Alloc>:: compare(size_type __pos1,size_type __n1,const basic_string & __str,size_type __pos2,size_type __n2) const1403 compare(size_type __pos1, size_type __n1, const basic_string& __str, 1404 size_type __pos2, size_type __n2) const 1405 { 1406 _M_check(__pos1, "basic_string::compare"); 1407 __str._M_check(__pos2, "basic_string::compare"); 1408 __n1 = _M_limit(__pos1, __n1); 1409 __n2 = __str._M_limit(__pos2, __n2); 1410 const size_type __len = std::min(__n1, __n2); 1411 int __r = traits_type::compare(_M_data() + __pos1, 1412 __str.data() + __pos2, __len); 1413 if (!__r) 1414 __r = _S_compare(__n1, __n2); 1415 return __r; 1416 } 1417 1418 template<typename _CharT, typename _Traits, typename _Alloc> 1419 int 1420 basic_string<_CharT, _Traits, _Alloc>:: compare(const _CharT * __s) const1421 compare(const _CharT* __s) const _GLIBCXX_NOEXCEPT 1422 { 1423 __glibcxx_requires_string(__s); 1424 const size_type __size = this->size(); 1425 const size_type __osize = traits_type::length(__s); 1426 const size_type __len = std::min(__size, __osize); 1427 int __r = traits_type::compare(_M_data(), __s, __len); 1428 if (!__r) 1429 __r = _S_compare(__size, __osize); 1430 return __r; 1431 } 1432 1433 template<typename _CharT, typename _Traits, typename _Alloc> 1434 int 1435 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s) const1436 compare(size_type __pos, size_type __n1, const _CharT* __s) const 1437 { 1438 __glibcxx_requires_string(__s); 1439 _M_check(__pos, "basic_string::compare"); 1440 __n1 = _M_limit(__pos, __n1); 1441 const size_type __osize = traits_type::length(__s); 1442 const size_type __len = std::min(__n1, __osize); 1443 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1444 if (!__r) 1445 __r = _S_compare(__n1, __osize); 1446 return __r; 1447 } 1448 1449 template<typename _CharT, typename _Traits, typename _Alloc> 1450 int 1451 basic_string <_CharT, _Traits, _Alloc>:: compare(size_type __pos,size_type __n1,const _CharT * __s,size_type __n2) const1452 compare(size_type __pos, size_type __n1, const _CharT* __s, 1453 size_type __n2) const 1454 { 1455 __glibcxx_requires_string_len(__s, __n2); 1456 _M_check(__pos, "basic_string::compare"); 1457 __n1 = _M_limit(__pos, __n1); 1458 const size_type __len = std::min(__n1, __n2); 1459 int __r = traits_type::compare(_M_data() + __pos, __s, __len); 1460 if (!__r) 1461 __r = _S_compare(__n1, __n2); 1462 return __r; 1463 } 1464 1465 // 21.3.7.9 basic_string::getline and operators 1466 template<typename _CharT, typename _Traits, typename _Alloc> 1467 basic_istream<_CharT, _Traits>& operator >>(basic_istream<_CharT,_Traits> & __in,basic_string<_CharT,_Traits,_Alloc> & __str)1468 operator>>(basic_istream<_CharT, _Traits>& __in, 1469 basic_string<_CharT, _Traits, _Alloc>& __str) 1470 { 1471 typedef basic_istream<_CharT, _Traits> __istream_type; 1472 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1473 typedef typename __istream_type::ios_base __ios_base; 1474 typedef typename __istream_type::int_type __int_type; 1475 typedef typename __string_type::size_type __size_type; 1476 typedef ctype<_CharT> __ctype_type; 1477 typedef typename __ctype_type::ctype_base __ctype_base; 1478 1479 __size_type __extracted = 0; 1480 typename __ios_base::iostate __err = __ios_base::goodbit; 1481 typename __istream_type::sentry __cerb(__in, false); 1482 if (__cerb) 1483 { 1484 __try 1485 { 1486 // Avoid reallocation for common case. 1487 __str.erase(); 1488 _CharT __buf[128]; 1489 __size_type __len = 0; 1490 const streamsize __w = __in.width(); 1491 const __size_type __n = __w > 0 ? static_cast<__size_type>(__w) 1492 : __str.max_size(); 1493 const __ctype_type& __ct = use_facet<__ctype_type>(__in.getloc()); 1494 const __int_type __eof = _Traits::eof(); 1495 __int_type __c = __in.rdbuf()->sgetc(); 1496 1497 while (__extracted < __n 1498 && !_Traits::eq_int_type(__c, __eof) 1499 && !__ct.is(__ctype_base::space, 1500 _Traits::to_char_type(__c))) 1501 { 1502 if (__len == sizeof(__buf) / sizeof(_CharT)) 1503 { 1504 __str.append(__buf, sizeof(__buf) / sizeof(_CharT)); 1505 __len = 0; 1506 } 1507 __buf[__len++] = _Traits::to_char_type(__c); 1508 ++__extracted; 1509 __c = __in.rdbuf()->snextc(); 1510 } 1511 __str.append(__buf, __len); 1512 1513 if (_Traits::eq_int_type(__c, __eof)) 1514 __err |= __ios_base::eofbit; 1515 __in.width(0); 1516 } 1517 __catch(__cxxabiv1::__forced_unwind&) 1518 { 1519 __in._M_setstate(__ios_base::badbit); 1520 __throw_exception_again; 1521 } 1522 __catch(...) 1523 { 1524 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1525 // 91. Description of operator>> and getline() for string<> 1526 // might cause endless loop 1527 __in._M_setstate(__ios_base::badbit); 1528 } 1529 } 1530 // 211. operator>>(istream&, string&) doesn't set failbit 1531 if (!__extracted) 1532 __err |= __ios_base::failbit; 1533 if (__err) 1534 __in.setstate(__err); 1535 return __in; 1536 } 1537 1538 template<typename _CharT, typename _Traits, typename _Alloc> 1539 basic_istream<_CharT, _Traits>& getline(basic_istream<_CharT,_Traits> & __in,basic_string<_CharT,_Traits,_Alloc> & __str,_CharT __delim)1540 getline(basic_istream<_CharT, _Traits>& __in, 1541 basic_string<_CharT, _Traits, _Alloc>& __str, _CharT __delim) 1542 { 1543 typedef basic_istream<_CharT, _Traits> __istream_type; 1544 typedef basic_string<_CharT, _Traits, _Alloc> __string_type; 1545 typedef typename __istream_type::ios_base __ios_base; 1546 typedef typename __istream_type::int_type __int_type; 1547 typedef typename __string_type::size_type __size_type; 1548 1549 __size_type __extracted = 0; 1550 const __size_type __n = __str.max_size(); 1551 typename __ios_base::iostate __err = __ios_base::goodbit; 1552 typename __istream_type::sentry __cerb(__in, true); 1553 if (__cerb) 1554 { 1555 __try 1556 { 1557 __str.erase(); 1558 const __int_type __idelim = _Traits::to_int_type(__delim); 1559 const __int_type __eof = _Traits::eof(); 1560 __int_type __c = __in.rdbuf()->sgetc(); 1561 1562 while (__extracted < __n 1563 && !_Traits::eq_int_type(__c, __eof) 1564 && !_Traits::eq_int_type(__c, __idelim)) 1565 { 1566 __str += _Traits::to_char_type(__c); 1567 ++__extracted; 1568 __c = __in.rdbuf()->snextc(); 1569 } 1570 1571 if (_Traits::eq_int_type(__c, __eof)) 1572 __err |= __ios_base::eofbit; 1573 else if (_Traits::eq_int_type(__c, __idelim)) 1574 { 1575 ++__extracted; 1576 __in.rdbuf()->sbumpc(); 1577 } 1578 else 1579 __err |= __ios_base::failbit; 1580 } 1581 __catch(__cxxabiv1::__forced_unwind&) 1582 { 1583 __in._M_setstate(__ios_base::badbit); 1584 __throw_exception_again; 1585 } 1586 __catch(...) 1587 { 1588 // _GLIBCXX_RESOLVE_LIB_DEFECTS 1589 // 91. Description of operator>> and getline() for string<> 1590 // might cause endless loop 1591 __in._M_setstate(__ios_base::badbit); 1592 } 1593 } 1594 if (!__extracted) 1595 __err |= __ios_base::failbit; 1596 if (__err) 1597 __in.setstate(__err); 1598 return __in; 1599 } 1600 1601 // Inhibit implicit instantiations for required instantiations, 1602 // which are defined via explicit instantiations elsewhere. 1603 #if _GLIBCXX_EXTERN_TEMPLATE 1604 // The explicit instantiation definitions in src/c++11/string-inst.cc and 1605 // src/c++17/string-inst.cc only instantiate the members required for C++17 1606 // and earlier standards (so not C++20's starts_with and ends_with). 1607 // Suppress the explicit instantiation declarations for C++20, so C++20 1608 // code will implicitly instantiate std::string and std::wstring as needed. 1609 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 1610 extern template class basic_string<char>; 1611 # elif ! _GLIBCXX_USE_CXX11_ABI 1612 // Still need to prevent implicit instantiation of the COW empty rep, 1613 // to ensure the definition in libstdc++.so is unique (PR 86138). 1614 extern template basic_string<char>::size_type 1615 basic_string<char>::_Rep::_S_empty_rep_storage[]; 1616 # endif 1617 1618 extern template 1619 basic_istream<char>& 1620 operator>>(basic_istream<char>&, string&); 1621 extern template 1622 basic_ostream<char>& 1623 operator<<(basic_ostream<char>&, const string&); 1624 extern template 1625 basic_istream<char>& 1626 getline(basic_istream<char>&, string&, char); 1627 extern template 1628 basic_istream<char>& 1629 getline(basic_istream<char>&, string&); 1630 1631 #ifdef _GLIBCXX_USE_WCHAR_T 1632 # if __cplusplus <= 201703L && _GLIBCXX_EXTERN_TEMPLATE > 0 1633 extern template class basic_string<wchar_t>; 1634 # elif ! _GLIBCXX_USE_CXX11_ABI 1635 extern template basic_string<wchar_t>::size_type 1636 basic_string<wchar_t>::_Rep::_S_empty_rep_storage[]; 1637 # endif 1638 1639 extern template 1640 basic_istream<wchar_t>& 1641 operator>>(basic_istream<wchar_t>&, wstring&); 1642 extern template 1643 basic_ostream<wchar_t>& 1644 operator<<(basic_ostream<wchar_t>&, const wstring&); 1645 extern template 1646 basic_istream<wchar_t>& 1647 getline(basic_istream<wchar_t>&, wstring&, wchar_t); 1648 extern template 1649 basic_istream<wchar_t>& 1650 getline(basic_istream<wchar_t>&, wstring&); 1651 #endif // _GLIBCXX_USE_WCHAR_T 1652 #endif // _GLIBCXX_EXTERN_TEMPLATE 1653 1654 _GLIBCXX_END_NAMESPACE_VERSION 1655 } // namespace std 1656 1657 #endif 1658