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