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