1 // Short-string-optimized versatile string base -*- C++ -*- 2 3 // Copyright (C) 2005-2014 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 ext/sso_string_base.h 26 * This is an internal header file, included by other library headers. 27 * Do not attempt to use it directly. @headername{ext/vstring.h} 28 */ 29 30 #ifndef _SSO_STRING_BASE_H 31 #define _SSO_STRING_BASE_H 1 32 33 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 34 { 35 _GLIBCXX_BEGIN_NAMESPACE_VERSION 36 37 template<typename _CharT, typename _Traits, typename _Alloc> 38 class __sso_string_base 39 : protected __vstring_utility<_CharT, _Traits, _Alloc> 40 { 41 public: 42 typedef _Traits traits_type; 43 typedef typename _Traits::char_type value_type; 44 45 typedef __vstring_utility<_CharT, _Traits, _Alloc> _Util_Base; 46 typedef typename _Util_Base::_CharT_alloc_type _CharT_alloc_type; 47 typedef typename _CharT_alloc_type::size_type size_type; 48 49 private: 50 // Data Members: 51 typename _Util_Base::template _Alloc_hider<_CharT_alloc_type> 52 _M_dataplus; 53 size_type _M_string_length; 54 55 enum { _S_local_capacity = 15 }; 56 57 union 58 { 59 _CharT _M_local_data[_S_local_capacity + 1]; 60 size_type _M_allocated_capacity; 61 }; 62 63 void 64 _M_data(_CharT* __p) 65 { _M_dataplus._M_p = __p; } 66 67 void 68 _M_length(size_type __length) 69 { _M_string_length = __length; } 70 71 void 72 _M_capacity(size_type __capacity) 73 { _M_allocated_capacity = __capacity; } 74 75 bool 76 _M_is_local() const 77 { return _M_data() == _M_local_data; } 78 79 // Create & Destroy 80 _CharT* 81 _M_create(size_type&, size_type); 82 83 void 84 _M_dispose() 85 { 86 if (!_M_is_local()) 87 _M_destroy(_M_allocated_capacity); 88 #if __google_stl_debug_dangling_string 89 else { 90 // Wipe local storage for destructed string with 0xCD. 91 // This mimics what DebugAllocation does to free()d memory. 92 __builtin_memset(_M_local_data, 0xcd, sizeof(_M_local_data)); 93 } 94 #endif 95 } 96 97 void 98 _M_destroy(size_type __size) throw() 99 { _M_get_allocator().deallocate(_M_data(), __size + 1); } 100 101 // _M_construct_aux is used to implement the 21.3.1 para 15 which 102 // requires special behaviour if _InIterator is an integral type 103 template<typename _InIterator> 104 void 105 _M_construct_aux(_InIterator __beg, _InIterator __end, 106 std::__false_type) 107 { 108 typedef typename iterator_traits<_InIterator>::iterator_category _Tag; 109 _M_construct(__beg, __end, _Tag()); 110 } 111 112 // _GLIBCXX_RESOLVE_LIB_DEFECTS 113 // 438. Ambiguity in the "do the right thing" clause 114 template<typename _Integer> 115 void 116 _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type) 117 { _M_construct_aux_2(static_cast<size_type>(__beg), __end); } 118 119 void 120 _M_construct_aux_2(size_type __req, _CharT __c) 121 { _M_construct(__req, __c); } 122 123 template<typename _InIterator> 124 void 125 _M_construct(_InIterator __beg, _InIterator __end) 126 { 127 typedef typename std::__is_integer<_InIterator>::__type _Integral; 128 _M_construct_aux(__beg, __end, _Integral()); 129 } 130 131 // For Input Iterators, used in istreambuf_iterators, etc. 132 template<typename _InIterator> 133 void 134 _M_construct(_InIterator __beg, _InIterator __end, 135 std::input_iterator_tag); 136 137 // For forward_iterators up to random_access_iterators, used for 138 // string::iterator, _CharT*, etc. 139 template<typename _FwdIterator> 140 void 141 _M_construct(_FwdIterator __beg, _FwdIterator __end, 142 std::forward_iterator_tag); 143 144 void 145 _M_construct(size_type __req, _CharT __c); 146 147 public: 148 size_type 149 _M_max_size() const 150 { return (_M_get_allocator().max_size() - 1) / 2; } 151 152 _CharT* 153 _M_data() const 154 { return _M_dataplus._M_p; } 155 156 size_type 157 _M_length() const 158 { return _M_string_length; } 159 160 size_type 161 _M_capacity() const 162 { 163 return _M_is_local() ? size_type(_S_local_capacity) 164 : _M_allocated_capacity; 165 } 166 167 bool 168 _M_is_shared() const 169 { return false; } 170 171 void 172 _M_set_leaked() { } 173 174 void 175 _M_leak() { } 176 177 void 178 _M_set_length_no_wipe(size_type __n) 179 { 180 _M_length(__n); 181 traits_type::assign(_M_data()[__n], _CharT()); 182 } 183 184 void 185 _M_set_length(size_type __n) 186 { 187 #if __google_stl_debug_dangling_string 188 if (__n + 1 < _M_length()) 189 { 190 // Wipe the storage with 0xCD. 191 // Also wipes the old NUL terminator. 192 __builtin_memset(_M_data() + __n + 1, 0xcd, _M_length() - __n); 193 } 194 #endif 195 _M_set_length_no_wipe(__n); 196 } 197 198 __sso_string_base() 199 : _M_dataplus(_M_local_data) 200 { _M_set_length_no_wipe(0); } 201 202 __sso_string_base(const _Alloc& __a); 203 204 __sso_string_base(const __sso_string_base& __rcs); 205 206 #if __cplusplus >= 201103L 207 __sso_string_base(__sso_string_base&& __rcs); 208 #endif 209 210 __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a); 211 212 template<typename _InputIterator> 213 __sso_string_base(_InputIterator __beg, _InputIterator __end, 214 const _Alloc& __a); 215 216 ~__sso_string_base() 217 { 218 _M_dispose(); 219 #ifdef __google_stl_debug_dangling_string 220 __builtin_memset(this, 0xcd, sizeof(*this)); 221 #endif 222 } 223 224 _CharT_alloc_type& 225 _M_get_allocator() 226 { return _M_dataplus; } 227 228 const _CharT_alloc_type& 229 _M_get_allocator() const 230 { return _M_dataplus; } 231 232 void 233 _M_swap(__sso_string_base& __rcs); 234 235 void 236 _M_assign(const __sso_string_base& __rcs); 237 238 void 239 _M_reserve(size_type __res); 240 241 void 242 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 243 size_type __len2); 244 245 void 246 _M_erase(size_type __pos, size_type __n); 247 248 void 249 _M_clear() 250 { _M_set_length(0); } 251 252 bool 253 _M_compare(const __sso_string_base&) const 254 { return false; } 255 }; 256 257 template<typename _CharT, typename _Traits, typename _Alloc> 258 void 259 __sso_string_base<_CharT, _Traits, _Alloc>:: 260 _M_swap(__sso_string_base& __rcs) 261 { 262 if (this == &__rcs) 263 return; 264 265 // _GLIBCXX_RESOLVE_LIB_DEFECTS 266 // 431. Swapping containers with unequal allocators. 267 std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(), 268 __rcs._M_get_allocator()); 269 270 if (_M_is_local()) 271 if (__rcs._M_is_local()) 272 { 273 if (_M_length() && __rcs._M_length()) 274 { 275 _CharT __tmp_data[_S_local_capacity + 1]; 276 traits_type::copy(__tmp_data, __rcs._M_local_data, 277 _S_local_capacity + 1); 278 traits_type::copy(__rcs._M_local_data, _M_local_data, 279 _S_local_capacity + 1); 280 traits_type::copy(_M_local_data, __tmp_data, 281 _S_local_capacity + 1); 282 } 283 else if (__rcs._M_length()) 284 { 285 traits_type::copy(_M_local_data, __rcs._M_local_data, 286 _S_local_capacity + 1); 287 _M_length(__rcs._M_length()); 288 __rcs._M_set_length(0); 289 return; 290 } 291 else if (_M_length()) 292 { 293 traits_type::copy(__rcs._M_local_data, _M_local_data, 294 _S_local_capacity + 1); 295 __rcs._M_length(_M_length()); 296 _M_set_length(0); 297 return; 298 } 299 } 300 else 301 { 302 const size_type __tmp_capacity = __rcs._M_allocated_capacity; 303 traits_type::copy(__rcs._M_local_data, _M_local_data, 304 _S_local_capacity + 1); 305 _M_data(__rcs._M_data()); 306 __rcs._M_data(__rcs._M_local_data); 307 _M_capacity(__tmp_capacity); 308 } 309 else 310 { 311 const size_type __tmp_capacity = _M_allocated_capacity; 312 if (__rcs._M_is_local()) 313 { 314 traits_type::copy(_M_local_data, __rcs._M_local_data, 315 _S_local_capacity + 1); 316 __rcs._M_data(_M_data()); 317 _M_data(_M_local_data); 318 } 319 else 320 { 321 _CharT* __tmp_ptr = _M_data(); 322 _M_data(__rcs._M_data()); 323 __rcs._M_data(__tmp_ptr); 324 _M_capacity(__rcs._M_allocated_capacity); 325 } 326 __rcs._M_capacity(__tmp_capacity); 327 } 328 329 const size_type __tmp_length = _M_length(); 330 _M_length(__rcs._M_length()); 331 __rcs._M_length(__tmp_length); 332 } 333 334 template<typename _CharT, typename _Traits, typename _Alloc> 335 _CharT* 336 __sso_string_base<_CharT, _Traits, _Alloc>:: 337 _M_create(size_type& __capacity, size_type __old_capacity) 338 { 339 // _GLIBCXX_RESOLVE_LIB_DEFECTS 340 // 83. String::npos vs. string::max_size() 341 if (__capacity > _M_max_size()) 342 std::__throw_length_error(__N("__sso_string_base::_M_create")); 343 344 // The below implements an exponential growth policy, necessary to 345 // meet amortized linear time requirements of the library: see 346 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 347 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 348 { 349 __capacity = 2 * __old_capacity; 350 // Never allocate a string bigger than max_size. 351 if (__capacity > _M_max_size()) 352 __capacity = _M_max_size(); 353 } 354 355 // NB: Need an array of char_type[__capacity], plus a terminating 356 // null char_type() element. 357 return _M_get_allocator().allocate(__capacity + 1); 358 } 359 360 template<typename _CharT, typename _Traits, typename _Alloc> 361 __sso_string_base<_CharT, _Traits, _Alloc>:: 362 __sso_string_base(const _Alloc& __a) 363 : _M_dataplus(__a, _M_local_data) 364 { _M_set_length_no_wipe(0); } 365 366 template<typename _CharT, typename _Traits, typename _Alloc> 367 __sso_string_base<_CharT, _Traits, _Alloc>:: 368 __sso_string_base(const __sso_string_base& __rcs) 369 : _M_dataplus(__rcs._M_get_allocator(), _M_local_data) 370 { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); } 371 372 #if __cplusplus >= 201103L 373 template<typename _CharT, typename _Traits, typename _Alloc> 374 __sso_string_base<_CharT, _Traits, _Alloc>:: 375 __sso_string_base(__sso_string_base&& __rcs) 376 : _M_dataplus(__rcs._M_get_allocator(), _M_local_data) 377 { 378 if (__rcs._M_is_local()) 379 { 380 if (__rcs._M_length()) 381 traits_type::copy(_M_local_data, __rcs._M_local_data, 382 _S_local_capacity + 1); 383 } 384 else 385 { 386 _M_data(__rcs._M_data()); 387 _M_capacity(__rcs._M_allocated_capacity); 388 } 389 390 _M_set_length_no_wipe(__rcs._M_length()); 391 __rcs._M_data(__rcs._M_local_data); 392 __rcs._M_set_length_no_wipe(0); 393 } 394 #endif 395 396 template<typename _CharT, typename _Traits, typename _Alloc> 397 __sso_string_base<_CharT, _Traits, _Alloc>:: 398 __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a) 399 : _M_dataplus(__a, _M_local_data) 400 { _M_construct(__n, __c); } 401 402 template<typename _CharT, typename _Traits, typename _Alloc> 403 template<typename _InputIterator> 404 __sso_string_base<_CharT, _Traits, _Alloc>:: 405 __sso_string_base(_InputIterator __beg, _InputIterator __end, 406 const _Alloc& __a) 407 : _M_dataplus(__a, _M_local_data) 408 { _M_construct(__beg, __end); } 409 410 // NB: This is the special case for Input Iterators, used in 411 // istreambuf_iterators, etc. 412 // Input Iterators have a cost structure very different from 413 // pointers, calling for a different coding style. 414 template<typename _CharT, typename _Traits, typename _Alloc> 415 template<typename _InIterator> 416 void 417 __sso_string_base<_CharT, _Traits, _Alloc>:: 418 _M_construct(_InIterator __beg, _InIterator __end, 419 std::input_iterator_tag) 420 { 421 size_type __len = 0; 422 size_type __capacity = size_type(_S_local_capacity); 423 424 while (__beg != __end && __len < __capacity) 425 { 426 _M_data()[__len++] = *__beg; 427 ++__beg; 428 } 429 430 __try 431 { 432 while (__beg != __end) 433 { 434 if (__len == __capacity) 435 { 436 // Allocate more space. 437 __capacity = __len + 1; 438 _CharT* __another = _M_create(__capacity, __len); 439 this->_S_copy(__another, _M_data(), __len); 440 _M_dispose(); 441 _M_data(__another); 442 _M_capacity(__capacity); 443 } 444 _M_data()[__len++] = *__beg; 445 ++__beg; 446 } 447 } 448 __catch(...) 449 { 450 _M_dispose(); 451 __throw_exception_again; 452 } 453 454 _M_set_length_no_wipe(__len); 455 } 456 457 template<typename _CharT, typename _Traits, typename _Alloc> 458 template<typename _InIterator> 459 void 460 __sso_string_base<_CharT, _Traits, _Alloc>:: 461 _M_construct(_InIterator __beg, _InIterator __end, 462 std::forward_iterator_tag) 463 { 464 // NB: Not required, but considered best practice. 465 if (__is_null_pointer(__beg) && __beg != __end) 466 std::__throw_logic_error(__N("__sso_string_base::" 467 "_M_construct null not valid")); 468 469 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 470 471 if (__dnew > size_type(_S_local_capacity)) 472 { 473 _M_data(_M_create(__dnew, size_type(0))); 474 _M_capacity(__dnew); 475 } 476 477 // Check for out_of_range and length_error exceptions. 478 __try 479 { this->_S_copy_chars(_M_data(), __beg, __end); } 480 __catch(...) 481 { 482 _M_dispose(); 483 __throw_exception_again; 484 } 485 486 _M_set_length_no_wipe(__dnew); 487 } 488 489 template<typename _CharT, typename _Traits, typename _Alloc> 490 void 491 __sso_string_base<_CharT, _Traits, _Alloc>:: 492 _M_construct(size_type __n, _CharT __c) 493 { 494 if (__n > size_type(_S_local_capacity)) 495 { 496 _M_data(_M_create(__n, size_type(0))); 497 _M_capacity(__n); 498 } 499 500 if (__n) 501 this->_S_assign(_M_data(), __n, __c); 502 503 _M_set_length_no_wipe(__n); 504 } 505 506 template<typename _CharT, typename _Traits, typename _Alloc> 507 void 508 __sso_string_base<_CharT, _Traits, _Alloc>:: 509 _M_assign(const __sso_string_base& __rcs) 510 { 511 if (this != &__rcs) 512 { 513 const size_type __rsize = __rcs._M_length(); 514 const size_type __capacity = _M_capacity(); 515 516 if (__rsize > __capacity) 517 { 518 size_type __new_capacity = __rsize; 519 _CharT* __tmp = _M_create(__new_capacity, __capacity); 520 _M_dispose(); 521 _M_data(__tmp); 522 _M_capacity(__new_capacity); 523 } 524 525 if (__rsize) 526 this->_S_copy(_M_data(), __rcs._M_data(), __rsize); 527 528 _M_set_length(__rsize); 529 } 530 } 531 532 template<typename _CharT, typename _Traits, typename _Alloc> 533 void 534 __sso_string_base<_CharT, _Traits, _Alloc>:: 535 _M_reserve(size_type __res) 536 { 537 // Make sure we don't shrink below the current size. 538 if (__res < _M_length()) 539 __res = _M_length(); 540 541 const size_type __capacity = _M_capacity(); 542 if (__res != __capacity) 543 { 544 if (__res > __capacity 545 || __res > size_type(_S_local_capacity)) 546 { 547 _CharT* __tmp = _M_create(__res, __capacity); 548 this->_S_copy(__tmp, _M_data(), _M_length() + 1); 549 _M_dispose(); 550 _M_data(__tmp); 551 _M_capacity(__res); 552 } 553 else if (!_M_is_local()) 554 { 555 this->_S_copy(_M_local_data, _M_data(), _M_length() + 1); 556 _M_destroy(__capacity); 557 _M_data(_M_local_data); 558 } 559 } 560 } 561 562 template<typename _CharT, typename _Traits, typename _Alloc> 563 void 564 __sso_string_base<_CharT, _Traits, _Alloc>:: 565 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 566 size_type __len2) 567 { 568 const size_type __how_much = _M_length() - __pos - __len1; 569 570 size_type __new_capacity = _M_length() + __len2 - __len1; 571 _CharT* __r = _M_create(__new_capacity, _M_capacity()); 572 573 if (__pos) 574 this->_S_copy(__r, _M_data(), __pos); 575 if (__s && __len2) 576 this->_S_copy(__r + __pos, __s, __len2); 577 if (__how_much) 578 this->_S_copy(__r + __pos + __len2, 579 _M_data() + __pos + __len1, __how_much); 580 581 _M_dispose(); 582 _M_data(__r); 583 _M_capacity(__new_capacity); 584 } 585 586 template<typename _CharT, typename _Traits, typename _Alloc> 587 void 588 __sso_string_base<_CharT, _Traits, _Alloc>:: 589 _M_erase(size_type __pos, size_type __n) 590 { 591 const size_type __how_much = _M_length() - __pos - __n; 592 593 if (__how_much && __n) 594 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 595 596 _M_set_length(_M_length() - __n); 597 } 598 599 _GLIBCXX_END_NAMESPACE_VERSION 600 } // namespace 601 602 #endif /* _SSO_STRING_BASE_H */ 603
