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