libstdc++
|
00001 // Short-string-optimized versatile string base -*- C++ -*- 00002 00003 // Copyright (C) 2005-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /** @file ext/sso_string_base.h 00026 * This is an internal header file, included by other library headers. 00027 * Do not attempt to use it directly. @headername{ext/vstring.h} 00028 */ 00029 00030 #ifndef _SSO_STRING_BASE_H 00031 #define _SSO_STRING_BASE_H 1 00032 00033 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00034 { 00035 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00036 00037 template<typename _CharT, typename _Traits, typename _Alloc> 00038 class __sso_string_base 00039 : protected __vstring_utility<_CharT, _Traits, _Alloc> 00040 { 00041 public: 00042 typedef _Traits traits_type; 00043 typedef typename _Traits::char_type value_type; 00044 00045 typedef __vstring_utility<_CharT, _Traits, _Alloc> _Util_Base; 00046 typedef typename _Util_Base::_CharT_alloc_type _CharT_alloc_type; 00047 typedef typename _CharT_alloc_type::size_type size_type; 00048 00049 private: 00050 // Data Members: 00051 typename _Util_Base::template _Alloc_hider<_CharT_alloc_type> 00052 _M_dataplus; 00053 size_type _M_string_length; 00054 00055 enum { _S_local_capacity = 15 }; 00056 00057 union 00058 { 00059 _CharT _M_local_data[_S_local_capacity + 1]; 00060 size_type _M_allocated_capacity; 00061 }; 00062 00063 void 00064 _M_data(_CharT* __p) 00065 { _M_dataplus._M_p = __p; } 00066 00067 void 00068 _M_length(size_type __length) 00069 { _M_string_length = __length; } 00070 00071 void 00072 _M_capacity(size_type __capacity) 00073 { _M_allocated_capacity = __capacity; } 00074 00075 bool 00076 _M_is_local() const 00077 { return _M_data() == _M_local_data; } 00078 00079 // Create & Destroy 00080 _CharT* 00081 _M_create(size_type&, size_type); 00082 00083 void 00084 _M_dispose() 00085 { 00086 if (!_M_is_local()) 00087 _M_destroy(_M_allocated_capacity); 00088 } 00089 00090 void 00091 _M_destroy(size_type __size) throw() 00092 { _M_get_allocator().deallocate(_M_data(), __size + 1); } 00093 00094 // _M_construct_aux is used to implement the 21.3.1 para 15 which 00095 // requires special behaviour if _InIterator is an integral type 00096 template<typename _InIterator> 00097 void 00098 _M_construct_aux(_InIterator __beg, _InIterator __end, 00099 std::__false_type) 00100 { 00101 typedef typename iterator_traits<_InIterator>::iterator_category _Tag; 00102 _M_construct(__beg, __end, _Tag()); 00103 } 00104 00105 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00106 // 438. Ambiguity in the "do the right thing" clause 00107 template<typename _Integer> 00108 void 00109 _M_construct_aux(_Integer __beg, _Integer __end, std::__true_type) 00110 { _M_construct_aux_2(static_cast<size_type>(__beg), __end); } 00111 00112 void 00113 _M_construct_aux_2(size_type __req, _CharT __c) 00114 { _M_construct(__req, __c); } 00115 00116 template<typename _InIterator> 00117 void 00118 _M_construct(_InIterator __beg, _InIterator __end) 00119 { 00120 typedef typename std::__is_integer<_InIterator>::__type _Integral; 00121 _M_construct_aux(__beg, __end, _Integral()); 00122 } 00123 00124 // For Input Iterators, used in istreambuf_iterators, etc. 00125 template<typename _InIterator> 00126 void 00127 _M_construct(_InIterator __beg, _InIterator __end, 00128 std::input_iterator_tag); 00129 00130 // For forward_iterators up to random_access_iterators, used for 00131 // string::iterator, _CharT*, etc. 00132 template<typename _FwdIterator> 00133 void 00134 _M_construct(_FwdIterator __beg, _FwdIterator __end, 00135 std::forward_iterator_tag); 00136 00137 void 00138 _M_construct(size_type __req, _CharT __c); 00139 00140 public: 00141 size_type 00142 _M_max_size() const 00143 { return (_M_get_allocator().max_size() - 1) / 2; } 00144 00145 _CharT* 00146 _M_data() const 00147 { return _M_dataplus._M_p; } 00148 00149 size_type 00150 _M_length() const 00151 { return _M_string_length; } 00152 00153 size_type 00154 _M_capacity() const 00155 { 00156 return _M_is_local() ? size_type(_S_local_capacity) 00157 : _M_allocated_capacity; 00158 } 00159 00160 bool 00161 _M_is_shared() const 00162 { return false; } 00163 00164 void 00165 _M_set_leaked() { } 00166 00167 void 00168 _M_leak() { } 00169 00170 void 00171 _M_set_length(size_type __n) 00172 { 00173 _M_length(__n); 00174 traits_type::assign(_M_data()[__n], _CharT()); 00175 } 00176 00177 __sso_string_base() 00178 : _M_dataplus(_M_local_data) 00179 { _M_set_length(0); } 00180 00181 __sso_string_base(const _Alloc& __a); 00182 00183 __sso_string_base(const __sso_string_base& __rcs); 00184 00185 #if __cplusplus >= 201103L 00186 __sso_string_base(__sso_string_base&& __rcs); 00187 #endif 00188 00189 __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a); 00190 00191 template<typename _InputIterator> 00192 __sso_string_base(_InputIterator __beg, _InputIterator __end, 00193 const _Alloc& __a); 00194 00195 ~__sso_string_base() 00196 { _M_dispose(); } 00197 00198 _CharT_alloc_type& 00199 _M_get_allocator() 00200 { return _M_dataplus; } 00201 00202 const _CharT_alloc_type& 00203 _M_get_allocator() const 00204 { return _M_dataplus; } 00205 00206 void 00207 _M_swap(__sso_string_base& __rcs); 00208 00209 void 00210 _M_assign(const __sso_string_base& __rcs); 00211 00212 void 00213 _M_reserve(size_type __res); 00214 00215 void 00216 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 00217 size_type __len2); 00218 00219 void 00220 _M_erase(size_type __pos, size_type __n); 00221 00222 void 00223 _M_clear() 00224 { _M_set_length(0); } 00225 00226 bool 00227 _M_compare(const __sso_string_base&) const 00228 { return false; } 00229 }; 00230 00231 template<typename _CharT, typename _Traits, typename _Alloc> 00232 void 00233 __sso_string_base<_CharT, _Traits, _Alloc>:: 00234 _M_swap(__sso_string_base& __rcs) 00235 { 00236 if (this == &__rcs) 00237 return; 00238 00239 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00240 // 431. Swapping containers with unequal allocators. 00241 std::__alloc_swap<_CharT_alloc_type>::_S_do_it(_M_get_allocator(), 00242 __rcs._M_get_allocator()); 00243 00244 if (_M_is_local()) 00245 if (__rcs._M_is_local()) 00246 { 00247 if (_M_length() && __rcs._M_length()) 00248 { 00249 _CharT __tmp_data[_S_local_capacity + 1]; 00250 traits_type::copy(__tmp_data, __rcs._M_local_data, 00251 _S_local_capacity + 1); 00252 traits_type::copy(__rcs._M_local_data, _M_local_data, 00253 _S_local_capacity + 1); 00254 traits_type::copy(_M_local_data, __tmp_data, 00255 _S_local_capacity + 1); 00256 } 00257 else if (__rcs._M_length()) 00258 { 00259 traits_type::copy(_M_local_data, __rcs._M_local_data, 00260 _S_local_capacity + 1); 00261 _M_length(__rcs._M_length()); 00262 __rcs._M_set_length(0); 00263 return; 00264 } 00265 else if (_M_length()) 00266 { 00267 traits_type::copy(__rcs._M_local_data, _M_local_data, 00268 _S_local_capacity + 1); 00269 __rcs._M_length(_M_length()); 00270 _M_set_length(0); 00271 return; 00272 } 00273 } 00274 else 00275 { 00276 const size_type __tmp_capacity = __rcs._M_allocated_capacity; 00277 traits_type::copy(__rcs._M_local_data, _M_local_data, 00278 _S_local_capacity + 1); 00279 _M_data(__rcs._M_data()); 00280 __rcs._M_data(__rcs._M_local_data); 00281 _M_capacity(__tmp_capacity); 00282 } 00283 else 00284 { 00285 const size_type __tmp_capacity = _M_allocated_capacity; 00286 if (__rcs._M_is_local()) 00287 { 00288 traits_type::copy(_M_local_data, __rcs._M_local_data, 00289 _S_local_capacity + 1); 00290 __rcs._M_data(_M_data()); 00291 _M_data(_M_local_data); 00292 } 00293 else 00294 { 00295 _CharT* __tmp_ptr = _M_data(); 00296 _M_data(__rcs._M_data()); 00297 __rcs._M_data(__tmp_ptr); 00298 _M_capacity(__rcs._M_allocated_capacity); 00299 } 00300 __rcs._M_capacity(__tmp_capacity); 00301 } 00302 00303 const size_type __tmp_length = _M_length(); 00304 _M_length(__rcs._M_length()); 00305 __rcs._M_length(__tmp_length); 00306 } 00307 00308 template<typename _CharT, typename _Traits, typename _Alloc> 00309 _CharT* 00310 __sso_string_base<_CharT, _Traits, _Alloc>:: 00311 _M_create(size_type& __capacity, size_type __old_capacity) 00312 { 00313 // _GLIBCXX_RESOLVE_LIB_DEFECTS 00314 // 83. String::npos vs. string::max_size() 00315 if (__capacity > _M_max_size()) 00316 std::__throw_length_error(__N("__sso_string_base::_M_create")); 00317 00318 // The below implements an exponential growth policy, necessary to 00319 // meet amortized linear time requirements of the library: see 00320 // http://gcc.gnu.org/ml/libstdc++/2001-07/msg00085.html. 00321 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity) 00322 { 00323 __capacity = 2 * __old_capacity; 00324 // Never allocate a string bigger than max_size. 00325 if (__capacity > _M_max_size()) 00326 __capacity = _M_max_size(); 00327 } 00328 00329 // NB: Need an array of char_type[__capacity], plus a terminating 00330 // null char_type() element. 00331 return _M_get_allocator().allocate(__capacity + 1); 00332 } 00333 00334 template<typename _CharT, typename _Traits, typename _Alloc> 00335 __sso_string_base<_CharT, _Traits, _Alloc>:: 00336 __sso_string_base(const _Alloc& __a) 00337 : _M_dataplus(__a, _M_local_data) 00338 { _M_set_length(0); } 00339 00340 template<typename _CharT, typename _Traits, typename _Alloc> 00341 __sso_string_base<_CharT, _Traits, _Alloc>:: 00342 __sso_string_base(const __sso_string_base& __rcs) 00343 : _M_dataplus(__rcs._M_get_allocator(), _M_local_data) 00344 { _M_construct(__rcs._M_data(), __rcs._M_data() + __rcs._M_length()); } 00345 00346 #if __cplusplus >= 201103L 00347 template<typename _CharT, typename _Traits, typename _Alloc> 00348 __sso_string_base<_CharT, _Traits, _Alloc>:: 00349 __sso_string_base(__sso_string_base&& __rcs) 00350 : _M_dataplus(__rcs._M_get_allocator(), _M_local_data) 00351 { 00352 if (__rcs._M_is_local()) 00353 { 00354 if (__rcs._M_length()) 00355 traits_type::copy(_M_local_data, __rcs._M_local_data, 00356 _S_local_capacity + 1); 00357 } 00358 else 00359 { 00360 _M_data(__rcs._M_data()); 00361 _M_capacity(__rcs._M_allocated_capacity); 00362 } 00363 00364 _M_set_length(__rcs._M_length()); 00365 __rcs._M_data(__rcs._M_local_data); 00366 __rcs._M_set_length(0); 00367 } 00368 #endif 00369 00370 template<typename _CharT, typename _Traits, typename _Alloc> 00371 __sso_string_base<_CharT, _Traits, _Alloc>:: 00372 __sso_string_base(size_type __n, _CharT __c, const _Alloc& __a) 00373 : _M_dataplus(__a, _M_local_data) 00374 { _M_construct(__n, __c); } 00375 00376 template<typename _CharT, typename _Traits, typename _Alloc> 00377 template<typename _InputIterator> 00378 __sso_string_base<_CharT, _Traits, _Alloc>:: 00379 __sso_string_base(_InputIterator __beg, _InputIterator __end, 00380 const _Alloc& __a) 00381 : _M_dataplus(__a, _M_local_data) 00382 { _M_construct(__beg, __end); } 00383 00384 // NB: This is the special case for Input Iterators, used in 00385 // istreambuf_iterators, etc. 00386 // Input Iterators have a cost structure very different from 00387 // pointers, calling for a different coding style. 00388 template<typename _CharT, typename _Traits, typename _Alloc> 00389 template<typename _InIterator> 00390 void 00391 __sso_string_base<_CharT, _Traits, _Alloc>:: 00392 _M_construct(_InIterator __beg, _InIterator __end, 00393 std::input_iterator_tag) 00394 { 00395 size_type __len = 0; 00396 size_type __capacity = size_type(_S_local_capacity); 00397 00398 while (__beg != __end && __len < __capacity) 00399 { 00400 _M_data()[__len++] = *__beg; 00401 ++__beg; 00402 } 00403 00404 __try 00405 { 00406 while (__beg != __end) 00407 { 00408 if (__len == __capacity) 00409 { 00410 // Allocate more space. 00411 __capacity = __len + 1; 00412 _CharT* __another = _M_create(__capacity, __len); 00413 this->_S_copy(__another, _M_data(), __len); 00414 _M_dispose(); 00415 _M_data(__another); 00416 _M_capacity(__capacity); 00417 } 00418 _M_data()[__len++] = *__beg; 00419 ++__beg; 00420 } 00421 } 00422 __catch(...) 00423 { 00424 _M_dispose(); 00425 __throw_exception_again; 00426 } 00427 00428 _M_set_length(__len); 00429 } 00430 00431 template<typename _CharT, typename _Traits, typename _Alloc> 00432 template<typename _InIterator> 00433 void 00434 __sso_string_base<_CharT, _Traits, _Alloc>:: 00435 _M_construct(_InIterator __beg, _InIterator __end, 00436 std::forward_iterator_tag) 00437 { 00438 // NB: Not required, but considered best practice. 00439 if (__is_null_pointer(__beg) && __beg != __end) 00440 std::__throw_logic_error(__N("__sso_string_base::" 00441 "_M_construct null not valid")); 00442 00443 size_type __dnew = static_cast<size_type>(std::distance(__beg, __end)); 00444 00445 if (__dnew > size_type(_S_local_capacity)) 00446 { 00447 _M_data(_M_create(__dnew, size_type(0))); 00448 _M_capacity(__dnew); 00449 } 00450 00451 // Check for out_of_range and length_error exceptions. 00452 __try 00453 { this->_S_copy_chars(_M_data(), __beg, __end); } 00454 __catch(...) 00455 { 00456 _M_dispose(); 00457 __throw_exception_again; 00458 } 00459 00460 _M_set_length(__dnew); 00461 } 00462 00463 template<typename _CharT, typename _Traits, typename _Alloc> 00464 void 00465 __sso_string_base<_CharT, _Traits, _Alloc>:: 00466 _M_construct(size_type __n, _CharT __c) 00467 { 00468 if (__n > size_type(_S_local_capacity)) 00469 { 00470 _M_data(_M_create(__n, size_type(0))); 00471 _M_capacity(__n); 00472 } 00473 00474 if (__n) 00475 this->_S_assign(_M_data(), __n, __c); 00476 00477 _M_set_length(__n); 00478 } 00479 00480 template<typename _CharT, typename _Traits, typename _Alloc> 00481 void 00482 __sso_string_base<_CharT, _Traits, _Alloc>:: 00483 _M_assign(const __sso_string_base& __rcs) 00484 { 00485 if (this != &__rcs) 00486 { 00487 const size_type __rsize = __rcs._M_length(); 00488 const size_type __capacity = _M_capacity(); 00489 00490 if (__rsize > __capacity) 00491 { 00492 size_type __new_capacity = __rsize; 00493 _CharT* __tmp = _M_create(__new_capacity, __capacity); 00494 _M_dispose(); 00495 _M_data(__tmp); 00496 _M_capacity(__new_capacity); 00497 } 00498 00499 if (__rsize) 00500 this->_S_copy(_M_data(), __rcs._M_data(), __rsize); 00501 00502 _M_set_length(__rsize); 00503 } 00504 } 00505 00506 template<typename _CharT, typename _Traits, typename _Alloc> 00507 void 00508 __sso_string_base<_CharT, _Traits, _Alloc>:: 00509 _M_reserve(size_type __res) 00510 { 00511 // Make sure we don't shrink below the current size. 00512 if (__res < _M_length()) 00513 __res = _M_length(); 00514 00515 const size_type __capacity = _M_capacity(); 00516 if (__res != __capacity) 00517 { 00518 if (__res > __capacity 00519 || __res > size_type(_S_local_capacity)) 00520 { 00521 _CharT* __tmp = _M_create(__res, __capacity); 00522 this->_S_copy(__tmp, _M_data(), _M_length() + 1); 00523 _M_dispose(); 00524 _M_data(__tmp); 00525 _M_capacity(__res); 00526 } 00527 else if (!_M_is_local()) 00528 { 00529 this->_S_copy(_M_local_data, _M_data(), _M_length() + 1); 00530 _M_destroy(__capacity); 00531 _M_data(_M_local_data); 00532 } 00533 } 00534 } 00535 00536 template<typename _CharT, typename _Traits, typename _Alloc> 00537 void 00538 __sso_string_base<_CharT, _Traits, _Alloc>:: 00539 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s, 00540 size_type __len2) 00541 { 00542 const size_type __how_much = _M_length() - __pos - __len1; 00543 00544 size_type __new_capacity = _M_length() + __len2 - __len1; 00545 _CharT* __r = _M_create(__new_capacity, _M_capacity()); 00546 00547 if (__pos) 00548 this->_S_copy(__r, _M_data(), __pos); 00549 if (__s && __len2) 00550 this->_S_copy(__r + __pos, __s, __len2); 00551 if (__how_much) 00552 this->_S_copy(__r + __pos + __len2, 00553 _M_data() + __pos + __len1, __how_much); 00554 00555 _M_dispose(); 00556 _M_data(__r); 00557 _M_capacity(__new_capacity); 00558 } 00559 00560 template<typename _CharT, typename _Traits, typename _Alloc> 00561 void 00562 __sso_string_base<_CharT, _Traits, _Alloc>:: 00563 _M_erase(size_type __pos, size_type __n) 00564 { 00565 const size_type __how_much = _M_length() - __pos - __n; 00566 00567 if (__how_much && __n) 00568 this->_S_move(_M_data() + __pos, _M_data() + __pos + __n, __how_much); 00569 00570 _M_set_length(_M_length() - __n); 00571 } 00572 00573 _GLIBCXX_END_NAMESPACE_VERSION 00574 } // namespace 00575 00576 #endif /* _SSO_STRING_BASE_H */