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