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