00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028
00029
00030
00031 #ifndef _RC_STRING_BASE_H
00032 #define _RC_STRING_BASE_H 1
00033
00034 #include <ext/atomicity.h>
00035 #include <bits/stl_iterator_base_funcs.h>
00036
00037 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
00038 {
00039 _GLIBCXX_BEGIN_NAMESPACE_VERSION
00040
00041
00042
00043
00044
00045
00046
00047
00048
00049
00050
00051
00052
00053
00054
00055
00056
00057
00058
00059
00060
00061
00062
00063
00064
00065
00066
00067
00068
00069
00070
00071
00072
00073
00074
00075
00076
00077
00078
00079
00080
00081
00082 template<typename _CharT, typename _Traits, typename _Alloc>
00083 class __rc_string_base
00084 : protected __vstring_utility<_CharT, _Traits, _Alloc>
00085 {
00086 public:
00087 typedef _Traits traits_type;
00088 typedef typename _Traits::char_type value_type;
00089 typedef _Alloc allocator_type;
00090
00091 typedef __vstring_utility<_CharT, _Traits, _Alloc> _Util_Base;
00092 typedef typename _Util_Base::_CharT_alloc_type _CharT_alloc_type;
00093 typedef typename _CharT_alloc_type::size_type size_type;
00094
00095 private:
00096
00097
00098
00099
00100
00101
00102
00103
00104
00105
00106
00107
00108
00109 struct _Rep
00110 {
00111 union
00112 {
00113 struct
00114 {
00115 size_type _M_length;
00116 size_type _M_capacity;
00117 _Atomic_word _M_refcount;
00118 } _M_info;
00119
00120
00121 _CharT _M_align;
00122 };
00123
00124 typedef typename _Alloc::template rebind<_Rep>::other _Rep_alloc_type;
00125
00126 _CharT*
00127 _M_refdata() throw()
00128 { return reinterpret_cast<_CharT*>(this + 1); }
00129
00130 _CharT*
00131 _M_refcopy() throw()
00132 {
00133 __atomic_add_dispatch(&_M_info._M_refcount, 1);
00134 return _M_refdata();
00135 }
00136
00137 void
00138 _M_set_length(size_type __n)
00139 {
00140 _M_info._M_refcount = 0;
00141 _M_info._M_length = __n;
00142
00143
00144 traits_type::assign(_M_refdata()[__n], _CharT());
00145 }
00146
00147
00148 static _Rep*
00149 _S_create(size_type, size_type, const _Alloc&);
00150
00151 void
00152 _M_destroy(const _Alloc&) throw();
00153
00154 _CharT*
00155 _M_clone(const _Alloc&, size_type __res = 0);
00156 };
00157
00158 struct _Rep_empty
00159 : public _Rep
00160 {
00161 _CharT _M_terminal;
00162 };
00163
00164 static _Rep_empty _S_empty_rep;
00165
00166
00167
00168
00169
00170
00171
00172
00173
00174
00175
00176
00177
00178
00179 enum { _S_max_size = (((static_cast<size_type>(-1) - 2 * sizeof(_Rep)
00180 + 1) / sizeof(_CharT)) - 1) / 2 };
00181
00182
00183 mutable typename _Util_Base::template _Alloc_hider<_Alloc> _M_dataplus;
00184
00185 void
00186 _M_data(_CharT* __p)
00187 { _M_dataplus._M_p = __p; }
00188
00189 _Rep*
00190 _M_rep() const
00191 { return &((reinterpret_cast<_Rep*>(_M_data()))[-1]); }
00192
00193 _CharT*
00194 _M_grab(const _Alloc& __alloc) const
00195 {
00196 return (!_M_is_leaked() && _M_get_allocator() == __alloc)
00197 ? _M_rep()->_M_refcopy() : _M_rep()->_M_clone(__alloc);
00198 }
00199
00200 void
00201 _M_dispose()
00202 {
00203
00204 _GLIBCXX_SYNCHRONIZATION_HAPPENS_BEFORE(&_M_rep()->_M_info.
00205 _M_refcount);
00206 if (__exchange_and_add_dispatch(&_M_rep()->_M_info._M_refcount,
00207 -1) <= 0)
00208 {
00209 _GLIBCXX_SYNCHRONIZATION_HAPPENS_AFTER(&_M_rep()->_M_info.
00210 _M_refcount);
00211 _M_rep()->_M_destroy(_M_get_allocator());
00212 }
00213 }
00214
00215 bool
00216 _M_is_leaked() const
00217 { return _M_rep()->_M_info._M_refcount < 0; }
00218
00219 void
00220 _M_set_sharable()
00221 { _M_rep()->_M_info._M_refcount = 0; }
00222
00223 void
00224 _M_leak_hard();
00225
00226
00227
00228 template<typename _InIterator>
00229 static _CharT*
00230 _S_construct_aux(_InIterator __beg, _InIterator __end,
00231 const _Alloc& __a, std::__false_type)
00232 {
00233 typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
00234 return _S_construct(__beg, __end, __a, _Tag());
00235 }
00236
00237
00238
00239 template<typename _Integer>
00240 static _CharT*
00241 _S_construct_aux(_Integer __beg, _Integer __end,
00242 const _Alloc& __a, std::__true_type)
00243 { return _S_construct_aux_2(static_cast<size_type>(__beg),
00244 __end, __a); }
00245
00246 static _CharT*
00247 _S_construct_aux_2(size_type __req, _CharT __c, const _Alloc& __a)
00248 { return _S_construct(__req, __c, __a); }
00249
00250 template<typename _InIterator>
00251 static _CharT*
00252 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
00253 {
00254 typedef typename std::__is_integer<_InIterator>::__type _Integral;
00255 return _S_construct_aux(__beg, __end, __a, _Integral());
00256 }
00257
00258
00259 template<typename _InIterator>
00260 static _CharT*
00261 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00262 std::input_iterator_tag);
00263
00264
00265
00266 template<typename _FwdIterator>
00267 static _CharT*
00268 _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
00269 std::forward_iterator_tag);
00270
00271 static _CharT*
00272 _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
00273
00274 public:
00275 size_type
00276 _M_max_size() const
00277 { return size_type(_S_max_size); }
00278
00279 _CharT*
00280 _M_data() const
00281 { return _M_dataplus._M_p; }
00282
00283 size_type
00284 _M_length() const
00285 { return _M_rep()->_M_info._M_length; }
00286
00287 size_type
00288 _M_capacity() const
00289 { return _M_rep()->_M_info._M_capacity; }
00290
00291 bool
00292 _M_is_shared() const
00293 { return _M_rep()->_M_info._M_refcount > 0; }
00294
00295 void
00296 _M_set_leaked()
00297 { _M_rep()->_M_info._M_refcount = -1; }
00298
00299 void
00300 _M_leak()
00301 {
00302 if (!_M_is_leaked())
00303 _M_leak_hard();
00304 }
00305
00306 void
00307 _M_set_length(size_type __n)
00308 { _M_rep()->_M_set_length(__n); }
00309
00310 __rc_string_base()
00311 : _M_dataplus(_S_empty_rep._M_refcopy()) { }
00312
00313 __rc_string_base(const _Alloc& __a);
00314
00315 __rc_string_base(const __rc_string_base& __rcs);
00316
00317 #ifdef __GXX_EXPERIMENTAL_CXX0X__
00318 __rc_string_base(__rc_string_base&& __rcs)
00319 : _M_dataplus(__rcs._M_dataplus)
00320 { __rcs._M_data(_S_empty_rep._M_refcopy()); }
00321 #endif
00322
00323 __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a);
00324
00325 template<typename _InputIterator>
00326 __rc_string_base(_InputIterator __beg, _InputIterator __end,
00327 const _Alloc& __a);
00328
00329 ~__rc_string_base()
00330 { _M_dispose(); }
00331
00332 allocator_type&
00333 _M_get_allocator()
00334 { return _M_dataplus; }
00335
00336 const allocator_type&
00337 _M_get_allocator() const
00338 { return _M_dataplus; }
00339
00340 void
00341 _M_swap(__rc_string_base& __rcs);
00342
00343 void
00344 _M_assign(const __rc_string_base& __rcs);
00345
00346 void
00347 _M_reserve(size_type __res);
00348
00349 void
00350 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00351 size_type __len2);
00352
00353 void
00354 _M_erase(size_type __pos, size_type __n);
00355
00356 void
00357 _M_clear()
00358 { _M_erase(size_type(0), _M_length()); }
00359
00360 bool
00361 _M_compare(const __rc_string_base&) const
00362 { return false; }
00363 };
00364
00365 template<typename _CharT, typename _Traits, typename _Alloc>
00366 typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep_empty
00367 __rc_string_base<_CharT, _Traits, _Alloc>::_S_empty_rep;
00368
00369 template<typename _CharT, typename _Traits, typename _Alloc>
00370 typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep*
00371 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00372 _S_create(size_type __capacity, size_type __old_capacity,
00373 const _Alloc& __alloc)
00374 {
00375
00376
00377 if (__capacity > size_type(_S_max_size))
00378 std::__throw_length_error(__N("__rc_string_base::_Rep::_S_create"));
00379
00380
00381
00382
00383
00384
00385
00386
00387
00388
00389
00390
00391
00392
00393
00394
00395
00396
00397
00398
00399
00400
00401
00402
00403 const size_type __pagesize = 4096;
00404 const size_type __malloc_header_size = 4 * sizeof(void*);
00405
00406
00407
00408
00409 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00410 {
00411 __capacity = 2 * __old_capacity;
00412
00413 if (__capacity > size_type(_S_max_size))
00414 __capacity = size_type(_S_max_size);
00415 }
00416
00417
00418
00419
00420
00421
00422 size_type __size = ((__capacity + 1) * sizeof(_CharT)
00423 + 2 * sizeof(_Rep) - 1);
00424
00425 const size_type __adj_size = __size + __malloc_header_size;
00426 if (__adj_size > __pagesize && __capacity > __old_capacity)
00427 {
00428 const size_type __extra = __pagesize - __adj_size % __pagesize;
00429 __capacity += __extra / sizeof(_CharT);
00430 if (__capacity > size_type(_S_max_size))
00431 __capacity = size_type(_S_max_size);
00432 __size = (__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1;
00433 }
00434
00435
00436
00437 _Rep* __place = _Rep_alloc_type(__alloc).allocate(__size / sizeof(_Rep));
00438 _Rep* __p = new (__place) _Rep;
00439 __p->_M_info._M_capacity = __capacity;
00440 return __p;
00441 }
00442
00443 template<typename _CharT, typename _Traits, typename _Alloc>
00444 void
00445 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00446 _M_destroy(const _Alloc& __a) throw ()
00447 {
00448 const size_type __size = ((_M_info._M_capacity + 1) * sizeof(_CharT)
00449 + 2 * sizeof(_Rep) - 1);
00450 _Rep_alloc_type(__a).deallocate(this, __size / sizeof(_Rep));
00451 }
00452
00453 template<typename _CharT, typename _Traits, typename _Alloc>
00454 _CharT*
00455 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00456 _M_clone(const _Alloc& __alloc, size_type __res)
00457 {
00458
00459 const size_type __requested_cap = _M_info._M_length + __res;
00460 _Rep* __r = _Rep::_S_create(__requested_cap, _M_info._M_capacity,
00461 __alloc);
00462
00463 if (_M_info._M_length)
00464 _S_copy(__r->_M_refdata(), _M_refdata(), _M_info._M_length);
00465
00466 __r->_M_set_length(_M_info._M_length);
00467 return __r->_M_refdata();
00468 }
00469
00470 template<typename _CharT, typename _Traits, typename _Alloc>
00471 __rc_string_base<_CharT, _Traits, _Alloc>::
00472 __rc_string_base(const _Alloc& __a)
00473 : _M_dataplus(__a, _S_construct(size_type(), _CharT(), __a)) { }
00474
00475 template<typename _CharT, typename _Traits, typename _Alloc>
00476 __rc_string_base<_CharT, _Traits, _Alloc>::
00477 __rc_string_base(const __rc_string_base& __rcs)
00478 : _M_dataplus(__rcs._M_get_allocator(),
00479 __rcs._M_grab(__rcs._M_get_allocator())) { }
00480
00481 template<typename _CharT, typename _Traits, typename _Alloc>
00482 __rc_string_base<_CharT, _Traits, _Alloc>::
00483 __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a)
00484 : _M_dataplus(__a, _S_construct(__n, __c, __a)) { }
00485
00486 template<typename _CharT, typename _Traits, typename _Alloc>
00487 template<typename _InputIterator>
00488 __rc_string_base<_CharT, _Traits, _Alloc>::
00489 __rc_string_base(_InputIterator __beg, _InputIterator __end,
00490 const _Alloc& __a)
00491 : _M_dataplus(__a, _S_construct(__beg, __end, __a)) { }
00492
00493 template<typename _CharT, typename _Traits, typename _Alloc>
00494 void
00495 __rc_string_base<_CharT, _Traits, _Alloc>::
00496 _M_leak_hard()
00497 {
00498 if (_M_is_shared())
00499 _M_erase(0, 0);
00500 _M_set_leaked();
00501 }
00502
00503
00504
00505
00506
00507 template<typename _CharT, typename _Traits, typename _Alloc>
00508 template<typename _InIterator>
00509 _CharT*
00510 __rc_string_base<_CharT, _Traits, _Alloc>::
00511 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00512 std::input_iterator_tag)
00513 {
00514 if (__beg == __end && __a == _Alloc())
00515 return _S_empty_rep._M_refcopy();
00516
00517
00518 _CharT __buf[128];
00519 size_type __len = 0;
00520 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
00521 {
00522 __buf[__len++] = *__beg;
00523 ++__beg;
00524 }
00525 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
00526 _S_copy(__r->_M_refdata(), __buf, __len);
00527 __try
00528 {
00529 while (__beg != __end)
00530 {
00531 if (__len == __r->_M_info._M_capacity)
00532 {
00533
00534 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
00535 _S_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
00536 __r->_M_destroy(__a);
00537 __r = __another;
00538 }
00539 __r->_M_refdata()[__len++] = *__beg;
00540 ++__beg;
00541 }
00542 }
00543 __catch(...)
00544 {
00545 __r->_M_destroy(__a);
00546 __throw_exception_again;
00547 }
00548 __r->_M_set_length(__len);
00549 return __r->_M_refdata();
00550 }
00551
00552 template<typename _CharT, typename _Traits, typename _Alloc>
00553 template<typename _InIterator>
00554 _CharT*
00555 __rc_string_base<_CharT, _Traits, _Alloc>::
00556 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00557 std::forward_iterator_tag)
00558 {
00559 if (__beg == __end && __a == _Alloc())
00560 return _S_empty_rep._M_refcopy();
00561
00562
00563 if (__is_null_pointer(__beg) && __beg != __end)
00564 std::__throw_logic_error(__N("__rc_string_base::"
00565 "_S_construct null not valid"));
00566
00567 const size_type __dnew = static_cast<size_type>(std::distance(__beg,
00568 __end));
00569
00570 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
00571 __try
00572 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
00573 __catch(...)
00574 {
00575 __r->_M_destroy(__a);
00576 __throw_exception_again;
00577 }
00578 __r->_M_set_length(__dnew);
00579 return __r->_M_refdata();
00580 }
00581
00582 template<typename _CharT, typename _Traits, typename _Alloc>
00583 _CharT*
00584 __rc_string_base<_CharT, _Traits, _Alloc>::
00585 _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
00586 {
00587 if (__n == 0 && __a == _Alloc())
00588 return _S_empty_rep._M_refcopy();
00589
00590
00591 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
00592 if (__n)
00593 _S_assign(__r->_M_refdata(), __n, __c);
00594
00595 __r->_M_set_length(__n);
00596 return __r->_M_refdata();
00597 }
00598
00599 template<typename _CharT, typename _Traits, typename _Alloc>
00600 void
00601 __rc_string_base<_CharT, _Traits, _Alloc>::
00602 _M_swap(__rc_string_base& __rcs)
00603 {
00604 if (_M_is_leaked())
00605 _M_set_sharable();
00606 if (__rcs._M_is_leaked())
00607 __rcs._M_set_sharable();
00608
00609 _CharT* __tmp = _M_data();
00610 _M_data(__rcs._M_data());
00611 __rcs._M_data(__tmp);
00612
00613
00614
00615 std::__alloc_swap<allocator_type>::_S_do_it(_M_get_allocator(),
00616 __rcs._M_get_allocator());
00617 }
00618
00619 template<typename _CharT, typename _Traits, typename _Alloc>
00620 void
00621 __rc_string_base<_CharT, _Traits, _Alloc>::
00622 _M_assign(const __rc_string_base& __rcs)
00623 {
00624 if (_M_rep() != __rcs._M_rep())
00625 {
00626 _CharT* __tmp = __rcs._M_grab(_M_get_allocator());
00627 _M_dispose();
00628 _M_data(__tmp);
00629 }
00630 }
00631
00632 template<typename _CharT, typename _Traits, typename _Alloc>
00633 void
00634 __rc_string_base<_CharT, _Traits, _Alloc>::
00635 _M_reserve(size_type __res)
00636 {
00637
00638 if (__res < _M_length())
00639 __res = _M_length();
00640
00641 if (__res != _M_capacity() || _M_is_shared())
00642 {
00643 _CharT* __tmp = _M_rep()->_M_clone(_M_get_allocator(),
00644 __res - _M_length());
00645 _M_dispose();
00646 _M_data(__tmp);
00647 }
00648 }
00649
00650 template<typename _CharT, typename _Traits, typename _Alloc>
00651 void
00652 __rc_string_base<_CharT, _Traits, _Alloc>::
00653 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00654 size_type __len2)
00655 {
00656 const size_type __how_much = _M_length() - __pos - __len1;
00657
00658 _Rep* __r = _Rep::_S_create(_M_length() + __len2 - __len1,
00659 _M_capacity(), _M_get_allocator());
00660
00661 if (__pos)
00662 _S_copy(__r->_M_refdata(), _M_data(), __pos);
00663 if (__s && __len2)
00664 _S_copy(__r->_M_refdata() + __pos, __s, __len2);
00665 if (__how_much)
00666 _S_copy(__r->_M_refdata() + __pos + __len2,
00667 _M_data() + __pos + __len1, __how_much);
00668
00669 _M_dispose();
00670 _M_data(__r->_M_refdata());
00671 }
00672
00673 template<typename _CharT, typename _Traits, typename _Alloc>
00674 void
00675 __rc_string_base<_CharT, _Traits, _Alloc>::
00676 _M_erase(size_type __pos, size_type __n)
00677 {
00678 const size_type __new_size = _M_length() - __n;
00679 const size_type __how_much = _M_length() - __pos - __n;
00680
00681 if (_M_is_shared())
00682 {
00683
00684 _Rep* __r = _Rep::_S_create(__new_size, _M_capacity(),
00685 _M_get_allocator());
00686
00687 if (__pos)
00688 _S_copy(__r->_M_refdata(), _M_data(), __pos);
00689 if (__how_much)
00690 _S_copy(__r->_M_refdata() + __pos,
00691 _M_data() + __pos + __n, __how_much);
00692
00693 _M_dispose();
00694 _M_data(__r->_M_refdata());
00695 }
00696 else if (__how_much && __n)
00697 {
00698
00699 _S_move(_M_data() + __pos,
00700 _M_data() + __pos + __n, __how_much);
00701 }
00702
00703 _M_rep()->_M_set_length(__new_size);
00704 }
00705
00706 template<>
00707 inline bool
00708 __rc_string_base<char, std::char_traits<char>,
00709 std::allocator<char> >::
00710 _M_compare(const __rc_string_base& __rcs) const
00711 {
00712 if (_M_rep() == __rcs._M_rep())
00713 return true;
00714 return false;
00715 }
00716
00717 #ifdef _GLIBCXX_USE_WCHAR_T
00718 template<>
00719 inline bool
00720 __rc_string_base<wchar_t, std::char_traits<wchar_t>,
00721 std::allocator<wchar_t> >::
00722 _M_compare(const __rc_string_base& __rcs) const
00723 {
00724 if (_M_rep() == __rcs._M_rep())
00725 return true;
00726 return false;
00727 }
00728 #endif
00729
00730 _GLIBCXX_END_NAMESPACE_VERSION
00731 }
00732
00733 #endif