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