1169691Skan// Short-string-optimized versatile string base -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the 7169691Skan// terms of the GNU General Public License as published by the 8169691Skan// Free Software Foundation; either version 2, or (at your option) 9169691Skan// any later version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, 12169691Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14169691Skan// GNU General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License along 17169691Skan// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 19169691Skan// USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free software 22169691Skan// library without restriction. Specifically, if other files instantiate 23169691Skan// templates or use macros or inline functions from this file, or you compile 24169691Skan// this file and link it with other files to produce an executable, this 25169691Skan// file does not by itself cause the resulting executable to be covered by 26169691Skan// the GNU General Public License. This exception does not however 27169691Skan// invalidate any other reasons why the executable file might be covered by 28169691Skan// the GNU General Public License. 29169691Skan 30169691Skan/** @file ext/sso_string_base.h 31169691Skan * This file is a GNU extension to the Standard C++ Library. 32169691Skan * This is an internal header file, included by other library headers. 33169691Skan * You should not attempt to use it directly. 34169691Skan */ 35169691Skan 36169691Skan#ifndef _SSO_STRING_BASE_H 37169691Skan#define _SSO_STRING_BASE_H 1 38169691Skan 39169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 40169691Skan 41169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 42169691Skan class __sso_string_base 43169691Skan : protected __vstring_utility<_CharT, _Traits, _Alloc> 44169691Skan { 45169691Skan public: 46169691Skan typedef _Traits traits_type; 47169691Skan typedef typename _Traits::char_type value_type; 48169691Skan 49169691Skan typedef __vstring_utility<_CharT, _Traits, _Alloc> _Util_Base; 50169691Skan typedef typename _Util_Base::_CharT_alloc_type _CharT_alloc_type; 51169691Skan typedef typename _CharT_alloc_type::size_type size_type; 52169691Skan 53169691Skan private: 54169691Skan // Data Members: 55169691Skan typename _Util_Base::template _Alloc_hider<_CharT_alloc_type> 56169691Skan _M_dataplus; 57169691Skan size_type _M_string_length; 58169691Skan 59169691Skan enum { _S_local_capacity = 15 }; 60169691Skan 61169691Skan union 62169691Skan { 63169691Skan _CharT _M_local_data[_S_local_capacity + 1]; 64169691Skan size_type _M_allocated_capacity; 65169691Skan }; 66169691Skan 67169691Skan void 68169691Skan _M_data(_CharT* __p) 69169691Skan { _M_dataplus._M_p = __p; } 70169691Skan 71169691Skan void 72169691Skan _M_length(size_type __length) 73169691Skan { _M_string_length = __length; } 74169691Skan 75169691Skan void 76169691Skan _M_capacity(size_type __capacity) 77169691Skan { _M_allocated_capacity = __capacity; } 78169691Skan 79169691Skan bool 80169691Skan _M_is_local() const 81169691Skan { return _M_data() == _M_local_data; } 82169691Skan 83169691Skan // Create & Destroy 84169691Skan _CharT* 85169691Skan _M_create(size_type&, size_type); 86169691Skan 87169691Skan void 88169691Skan _M_dispose() 89169691Skan { 90169691Skan if (!_M_is_local()) 91169691Skan _M_destroy(_M_allocated_capacity); 92169691Skan } 93169691Skan 94169691Skan void 95169691Skan _M_destroy(size_type __size) throw() 96169691Skan { _M_get_allocator().deallocate(_M_data(), __size + 1); } 97169691Skan 98169691Skan // _M_construct_aux is used to implement the 21.3.1 para 15 which 99169691Skan // requires special behaviour if _InIterator is an integral type 100169691Skan template<typename _InIterator> 101169691Skan void 102169691Skan _M_construct_aux(_InIterator __beg, _InIterator __end, 103169691Skan std::__false_type) 104169691Skan { 105169691Skan typedef typename iterator_traits<_InIterator>::iterator_category _Tag; 106169691Skan _M_construct(__beg, __end, _Tag()); 107169691Skan } 108169691Skan 109169691Skan template<typename _InIterator> 110169691Skan void 111169691Skan _M_construct_aux(_InIterator __beg, _InIterator __end, 112169691Skan std::__true_type) 113169691Skan { _M_construct(static_cast<size_type>(__beg), 114169691Skan static_cast<value_type>(__end)); } 115169691Skan 116169691Skan template<typename _InIterator> 117169691Skan void 118169691Skan _M_construct(_InIterator __beg, _InIterator __end) 119169691Skan { 120169691Skan typedef typename std::__is_integer<_InIterator>::__type _Integral; 121169691Skan _M_construct_aux(__beg, __end, _Integral()); 122169691Skan } 123169691Skan 124169691Skan // For Input Iterators, used in istreambuf_iterators, etc. 125169691Skan template<typename _InIterator> 126169691Skan void 127169691Skan _M_construct(_InIterator __beg, _InIterator __end, 128169691Skan std::input_iterator_tag); 129169691Skan 130169691Skan // For forward_iterators up to random_access_iterators, used for 131169691Skan // string::iterator, _CharT*, etc. 132169691Skan template<typename _FwdIterator> 133169691Skan void 134169691Skan _M_construct(_FwdIterator __beg, _FwdIterator __end, 135169691Skan std::forward_iterator_tag); 136169691Skan 137169691Skan void 138169691Skan _M_construct(size_type __req, _CharT __c); 139169691Skan 140169691Skan public: 141169691Skan size_type 142169691Skan _M_max_size() const 143169691Skan { return (_M_get_allocator().max_size() - 1) / 2; } 144169691Skan 145169691Skan _CharT* 146169691Skan _M_data() const 147169691Skan { return _M_dataplus._M_p; } 148169691Skan 149169691Skan size_type 150169691Skan _M_length() const 151169691Skan { return _M_string_length; } 152169691Skan 153169691Skan size_type 154169691Skan _M_capacity() const 155169691Skan { 156169691Skan return _M_is_local() ? size_type(_S_local_capacity) 157169691Skan : _M_allocated_capacity; 158169691Skan } 159169691Skan 160169691Skan bool 161169691Skan _M_is_shared() const 162169691Skan { return false; } 163169691Skan 164169691Skan void 165169691Skan _M_set_leaked() { } 166169691Skan 167169691Skan void 168169691Skan _M_leak() { } 169169691Skan 170169691Skan void 171169691Skan _M_set_length(size_type __n) 172169691Skan { 173169691Skan _M_length(__n); 174169691Skan traits_type::assign(_M_data()[__n], _CharT()); 175169691Skan } 176169691Skan 177169691Skan __sso_string_base() 178169691Skan : _M_dataplus(_Alloc(), _M_local_data) 179169691Skan { _M_set_length(0); } 180169691Skan 181169691Skan __sso_string_base(const _Alloc& __a); 182169691Skan 183169691Skan __sso_string_base(const __sso_string_base& __rcs); 184169691Skan 185169691Skan __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a); 186169691Skan 187169691Skan template<typename _InputIterator> 188169691Skan __sso_string_base(_InputIterator __beg, _InputIterator __end, 189169691Skan const _Alloc& __a); 190169691Skan 191169691Skan ~__sso_string_base() 192169691Skan { _M_dispose(); } 193169691Skan 194169691Skan _CharT_alloc_type& 195169691Skan _M_get_allocator() 196169691Skan { return _M_dataplus; } 197169691Skan 198169691Skan const _CharT_alloc_type& 199169691Skan _M_get_allocator() const 200169691Skan { return _M_dataplus; } 201169691Skan 202169691Skan void 203169691Skan _M_swap(__sso_string_base& __rcs); 204169691Skan 205169691Skan void 206169691Skan _M_assign(const __sso_string_base& __rcs); 207169691Skan 208169691Skan void 209169691Skan _M_reserve(size_type __res); 210169691Skan 211169691Skan void 212169691Skan _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 213169691Skan size_type __len2); 214169691Skan 215169691Skan void 216169691Skan _M_erase(size_type __pos, size_type __n); 217169691Skan 218169691Skan void 219169691Skan _M_clear() 220169691Skan { _M_set_length(0); } 221169691Skan 222169691Skan bool 223169691Skan _M_compare(const __sso_string_base&) const 224169691Skan { return false; } 225169691Skan }; 226169691Skan 227169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 228169691Skan void 229169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 230169691Skan _M_swap(__sso_string_base& __rcs) 231169691Skan { 232169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 233169691Skan // 431. Swapping containers with unequal allocators. 234169691Skan std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(), 235169691Skan __rcs._M_get_allocator()); 236169691Skan 237169691Skan if (_M_is_local()) 238169691Skan if (__rcs._M_is_local()) 239169691Skan { 240169691Skan if (_M_length() && __rcs._M_length()) 241169691Skan { 242169691Skan _CharT __tmp_data[_S_local_capacity + 1]; 243169691Skan traits_type::copy(__tmp_data, __rcs._M_local_data, 244169691Skan _S_local_capacity + 1); 245169691Skan traits_type::copy(__rcs._M_local_data, _M_local_data, 246169691Skan _S_local_capacity + 1); 247169691Skan traits_type::copy(_M_local_data, __tmp_data, 248169691Skan _S_local_capacity + 1); 249169691Skan } 250169691Skan else if (__rcs._M_length()) 251169691Skan { 252169691Skan traits_type::copy(_M_local_data, __rcs._M_local_data, 253169691Skan _S_local_capacity + 1); 254169691Skan _M_length(__rcs._M_length()); 255169691Skan __rcs._M_set_length(0); 256169691Skan return; 257169691Skan } 258169691Skan else if (_M_length()) 259169691Skan { 260169691Skan traits_type::copy(__rcs._M_local_data, _M_local_data, 261169691Skan _S_local_capacity + 1); 262169691Skan __rcs._M_length(_M_length()); 263169691Skan _M_set_length(0); 264169691Skan return; 265169691Skan } 266169691Skan } 267169691Skan else 268169691Skan { 269169691Skan const size_type __tmp_capacity = __rcs._M_allocated_capacity; 270169691Skan traits_type::copy(__rcs._M_local_data, _M_local_data, 271169691Skan _S_local_capacity + 1); 272169691Skan _M_data(__rcs._M_data()); 273169691Skan __rcs._M_data(__rcs._M_local_data); 274169691Skan _M_capacity(__tmp_capacity); 275169691Skan } 276169691Skan else 277169691Skan { 278169691Skan const size_type __tmp_capacity = _M_allocated_capacity; 279169691Skan if (__rcs._M_is_local()) 280169691Skan { 281169691Skan traits_type::copy(_M_local_data, __rcs._M_local_data, 282169691Skan _S_local_capacity + 1); 283169691Skan __rcs._M_data(_M_data()); 284169691Skan _M_data(_M_local_data); 285169691Skan } 286169691Skan else 287169691Skan { 288169691Skan _CharT* __tmp_ptr = _M_data(); 289169691Skan _M_data(__rcs._M_data()); 290169691Skan __rcs._M_data(__tmp_ptr); 291169691Skan _M_capacity(__rcs._M_allocated_capacity); 292169691Skan } 293169691Skan __rcs._M_capacity(__tmp_capacity); 294169691Skan } 295169691Skan 296169691Skan const size_type __tmp_length = _M_length(); 297169691Skan _M_length(__rcs._M_length()); 298169691Skan __rcs._M_length(__tmp_length); 299169691Skan } 300169691Skan 301169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 302169691Skan _CharT* 303169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 304169691Skan _M_create(size_type& __capacity, size_type __old_capacity) 305169691Skan { 306169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 307169691Skan // 83. String::npos vs. string::max_size() 308169691Skan if (__capacity > _M_max_size()) 309169691Skan std::__throw_length_error(__N("__sso_string_base::_M_create")); 310169691Skan 311169691Skan // The below implements an exponential growth policy, necessary to 312169691Skan // meet amortized linear time requirements of the library: see 313169691Skan // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 314169691Skan if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 315169691Skan { 316169691Skan __capacity = 2 * __old_capacity; 317169691Skan // Never allocate a string bigger than max_size. 318169691Skan if (__capacity > _M_max_size()) 319169691Skan __capacity = _M_max_size(); 320169691Skan } 321169691Skan 322169691Skan // NB: Need an array of char_type[__capacity], plus a terminating 323169691Skan // null char_type() element. 324169691Skan return _M_get_allocator().allocate(__capacity + 1); 325169691Skan } 326169691Skan 327169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 328169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 329169691Skan __sso_string_base(const _Alloc& __a) 330169691Skan : _M_dataplus(__a, _M_local_data) 331169691Skan { _M_set_length(0); } 332169691Skan 333169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 334169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 335169691Skan __sso_string_base(const __sso_string_base& __rcs) 336169691Skan : _M_dataplus(__rcs._M_get_allocator(), _M_local_data) 337169691Skan { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); } 338169691Skan 339169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 340169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 341169691Skan __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a) 342169691Skan : _M_dataplus(__a, _M_local_data) 343169691Skan { _M_construct(__n, __c); } 344169691Skan 345169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 346169691Skan template<typename _InputIterator> 347169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 348169691Skan __sso_string_base(_InputIterator __beg, _InputIterator __end, 349169691Skan const _Alloc& __a) 350169691Skan : _M_dataplus(__a, _M_local_data) 351169691Skan { _M_construct(__beg, __end); } 352169691Skan 353169691Skan // NB: This is the special case for Input Iterators, used in 354169691Skan // istreambuf_iterators, etc. 355169691Skan // Input Iterators have a cost structure very different from 356169691Skan // pointers, calling for a different coding style. 357169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 358169691Skan template<typename _InIterator> 359169691Skan void 360169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 361169691Skan _M_construct(_InIterator __beg, _InIterator __end, 362169691Skan std::input_iterator_tag) 363169691Skan { 364169691Skan size_type __len = 0; 365169691Skan size_type __capacity = size_type(_S_local_capacity); 366169691Skan 367169691Skan while (__beg != __end && __len < __capacity) 368169691Skan { 369169691Skan _M_data()[__len++] = *__beg; 370169691Skan ++__beg; 371169691Skan } 372169691Skan 373169691Skan try 374169691Skan { 375169691Skan while (__beg != __end) 376169691Skan { 377169691Skan if (__len == __capacity) 378169691Skan { 379169691Skan // Allocate more space. 380169691Skan __capacity = __len + 1; 381169691Skan _CharT* __another = _M_create(__capacity, __len); 382169691Skan _S_copy(__another, _M_data(), __len); 383169691Skan _M_dispose(); 384169691Skan _M_data(__another); 385169691Skan _M_capacity(__capacity); 386169691Skan } 387169691Skan _M_data()[__len++] = *__beg; 388169691Skan ++__beg; 389169691Skan } 390169691Skan } 391169691Skan catch(...) 392169691Skan { 393169691Skan _M_dispose(); 394169691Skan __throw_exception_again; 395169691Skan } 396169691Skan 397169691Skan _M_set_length(__len); 398169691Skan } 399169691Skan 400169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 401169691Skan template<typename _InIterator> 402169691Skan void 403169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 404169691Skan _M_construct(_InIterator __beg, _InIterator __end, 405169691Skan std::forward_iterator_tag) 406169691Skan { 407169691Skan // NB: Not required, but considered best practice. 408169691Skan if (__builtin_expect(_S_is_null_pointer(__beg) && __beg != __end, 0)) 409169691Skan std::__throw_logic_error(__N("__sso_string_base::" 410169691Skan "_M_construct NULL not valid")); 411169691Skan 412169691Skan size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 413169691Skan 414169691Skan if (__dnew > size_type(_S_local_capacity)) 415169691Skan { 416169691Skan _M_data(_M_create(__dnew, size_type(0))); 417169691Skan _M_capacity(__dnew); 418169691Skan } 419169691Skan 420169691Skan // Check for out_of_range and length_error exceptions. 421169691Skan try 422169691Skan { _S_copy_chars(_M_data(), __beg, __end); } 423169691Skan catch(...) 424169691Skan { 425169691Skan _M_dispose(); 426169691Skan __throw_exception_again; 427169691Skan } 428169691Skan 429169691Skan _M_set_length(__dnew); 430169691Skan } 431169691Skan 432169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 433169691Skan void 434169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 435169691Skan _M_construct(size_type __n, _CharT __c) 436169691Skan { 437169691Skan if (__n > size_type(_S_local_capacity)) 438169691Skan { 439169691Skan _M_data(_M_create(__n, size_type(0))); 440169691Skan _M_capacity(__n); 441169691Skan } 442169691Skan 443169691Skan if (__n) 444169691Skan _S_assign(_M_data(), __n, __c); 445169691Skan 446169691Skan _M_set_length(__n); 447169691Skan } 448169691Skan 449169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 450169691Skan void 451169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 452169691Skan _M_assign(const __sso_string_base& __rcs) 453169691Skan { 454169691Skan if (this != &__rcs) 455169691Skan { 456169691Skan const size_type __rsize = __rcs._M_length(); 457169691Skan const size_type __capacity = _M_capacity(); 458169691Skan 459169691Skan if (__rsize > __capacity) 460169691Skan { 461169691Skan size_type __new_capacity = __rsize; 462169691Skan _CharT* __tmp = _M_create(__new_capacity, __capacity); 463169691Skan _M_dispose(); 464169691Skan _M_data(__tmp); 465169691Skan _M_capacity(__new_capacity); 466169691Skan } 467169691Skan 468169691Skan if (__rsize) 469169691Skan _S_copy(_M_data(), __rcs._M_data(), __rsize); 470169691Skan 471169691Skan _M_set_length(__rsize); 472169691Skan } 473169691Skan } 474169691Skan 475169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 476169691Skan void 477169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 478169691Skan _M_reserve(size_type __res) 479169691Skan { 480169691Skan // Make sure we don't shrink below the current size. 481169691Skan if (__res < _M_length()) 482169691Skan __res = _M_length(); 483169691Skan 484169691Skan const size_type __capacity = _M_capacity(); 485169691Skan if (__res != __capacity) 486169691Skan { 487169691Skan if (__res > __capacity 488169691Skan || __res > size_type(_S_local_capacity)) 489169691Skan { 490169691Skan _CharT* __tmp = _M_create(__res, __capacity); 491169691Skan _S_copy(__tmp, _M_data(), _M_length() + 1); 492169691Skan _M_dispose(); 493169691Skan _M_data(__tmp); 494169691Skan _M_capacity(__res); 495169691Skan } 496169691Skan else if (!_M_is_local()) 497169691Skan { 498169691Skan _S_copy(_M_local_data, _M_data(), _M_length() + 1); 499169691Skan _M_destroy(__capacity); 500169691Skan _M_data(_M_local_data); 501169691Skan } 502169691Skan } 503169691Skan } 504169691Skan 505169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 506169691Skan void 507169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 508169691Skan _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 509169691Skan const size_type __len2) 510169691Skan { 511169691Skan const size_type __how_much = _M_length() - __pos - __len1; 512169691Skan 513169691Skan size_type __new_capacity = _M_length() + __len2 - __len1; 514169691Skan _CharT* __r = _M_create(__new_capacity, _M_capacity()); 515169691Skan 516169691Skan if (__pos) 517169691Skan _S_copy(__r, _M_data(), __pos); 518169691Skan if (__s && __len2) 519169691Skan _S_copy(__r + __pos, __s, __len2); 520169691Skan if (__how_much) 521169691Skan _S_copy(__r + __pos + __len2, 522169691Skan _M_data() + __pos + __len1, __how_much); 523169691Skan 524169691Skan _M_dispose(); 525169691Skan _M_data(__r); 526169691Skan _M_capacity(__new_capacity); 527169691Skan } 528169691Skan 529169691Skan template<typename _CharT, typename _Traits, typename _Alloc> 530169691Skan void 531169691Skan __sso_string_base<_CharT, _Traits, _Alloc>:: 532169691Skan _M_erase(size_type __pos, size_type __n) 533169691Skan { 534169691Skan const size_type __how_much = _M_length() - __pos - __n; 535169691Skan 536169691Skan if (__how_much && __n) 537169691Skan _S_move(_M_data() + __pos, _M_data() + __pos + __n, 538169691Skan __how_much); 539169691Skan 540169691Skan _M_set_length(_M_length() - __n); 541169691Skan } 542169691Skan 543169691Skan template<> 544169691Skan inline bool 545169691Skan __sso_string_base<char, std::char_traits<char>, 546169691Skan std::allocator<char> >:: 547169691Skan _M_compare(const __sso_string_base& __rcs) const 548169691Skan { 549169691Skan if (this == &__rcs) 550169691Skan return true; 551169691Skan return false; 552169691Skan } 553169691Skan 554169691Skan#ifdef _GLIBCXX_USE_WCHAR_T 555169691Skan template<> 556169691Skan inline bool 557169691Skan __sso_string_base<wchar_t, std::char_traits<wchar_t>, 558169691Skan std::allocator<wchar_t> >:: 559169691Skan _M_compare(const __sso_string_base& __rcs) const 560169691Skan { 561169691Skan if (this == &__rcs) 562169691Skan return true; 563169691Skan return false; 564169691Skan } 565169691Skan#endif 566169691Skan 567169691Skan_GLIBCXX_END_NAMESPACE 568169691Skan 569169691Skan#endif /* _SSO_STRING_BASE_H */ 570