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