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