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 <bits/atomicity.h>
00040
00041 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(&_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(&_M_rep()->_M_info._M_refcount, -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, __false_type)
00228 {
00229 typedef typename iterator_traits<_InIterator>::iterator_category _Tag;
00230 return _S_construct(__beg, __end, __a, _Tag());
00231 }
00232
00233 template<typename _InIterator>
00234 static _CharT*
00235 _S_construct_aux(_InIterator __beg, _InIterator __end,
00236 const _Alloc& __a, __true_type)
00237 { return _S_construct(static_cast<size_type>(__beg),
00238 static_cast<value_type>(__end), __a); }
00239
00240 template<typename _InIterator>
00241 static _CharT*
00242 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a)
00243 {
00244 typedef typename std::__is_integer<_InIterator>::__type _Integral;
00245 return _S_construct_aux(__beg, __end, __a, _Integral());
00246 }
00247
00248
00249 template<typename _InIterator>
00250 static _CharT*
00251 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00252 std::input_iterator_tag);
00253
00254
00255
00256 template<typename _FwdIterator>
00257 static _CharT*
00258 _S_construct(_FwdIterator __beg, _FwdIterator __end, const _Alloc& __a,
00259 std::forward_iterator_tag);
00260
00261 static _CharT*
00262 _S_construct(size_type __req, _CharT __c, const _Alloc& __a);
00263
00264 public:
00265 size_type
00266 _M_max_size() const
00267 { return size_type(_S_max_size); }
00268
00269 _CharT*
00270 _M_data() const
00271 { return _M_dataplus._M_p; }
00272
00273 size_type
00274 _M_length() const
00275 { return _M_rep()->_M_info._M_length; }
00276
00277 size_type
00278 _M_capacity() const
00279 { return _M_rep()->_M_info._M_capacity; }
00280
00281 bool
00282 _M_is_shared() const
00283 { return _M_rep()->_M_info._M_refcount > 0; }
00284
00285 void
00286 _M_set_leaked()
00287 { _M_rep()->_M_info._M_refcount = -1; }
00288
00289 void
00290 _M_leak()
00291 {
00292 if (!_M_is_leaked())
00293 _M_leak_hard();
00294 }
00295
00296 void
00297 _M_set_length(size_type __n)
00298 { _M_rep()->_M_set_length(__n); }
00299
00300 __rc_string_base()
00301 : _M_dataplus(_Alloc(), _S_empty_rep._M_refcopy()) { }
00302
00303 __rc_string_base(const _Alloc& __a);
00304
00305 __rc_string_base(const __rc_string_base& __rcs);
00306
00307 __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a);
00308
00309 template<typename _InputIterator>
00310 __rc_string_base(_InputIterator __beg, _InputIterator __end,
00311 const _Alloc& __a);
00312
00313 ~__rc_string_base()
00314 { _M_dispose(); }
00315
00316 allocator_type&
00317 _M_get_allocator()
00318 { return _M_dataplus; }
00319
00320 const allocator_type&
00321 _M_get_allocator() const
00322 { return _M_dataplus; }
00323
00324 void
00325 _M_swap(__rc_string_base& __rcs);
00326
00327 void
00328 _M_assign(const __rc_string_base& __rcs);
00329
00330 void
00331 _M_reserve(size_type __res);
00332
00333 void
00334 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00335 size_type __len2);
00336
00337 void
00338 _M_erase(size_type __pos, size_type __n);
00339
00340 void
00341 _M_clear()
00342 { _M_erase(size_type(0), _M_length()); }
00343
00344 bool
00345 _M_compare(const __rc_string_base&) const
00346 { return false; }
00347 };
00348
00349 template<typename _CharT, typename _Traits, typename _Alloc>
00350 typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep_empty
00351 __rc_string_base<_CharT, _Traits, _Alloc>::_S_empty_rep;
00352
00353 template<typename _CharT, typename _Traits, typename _Alloc>
00354 typename __rc_string_base<_CharT, _Traits, _Alloc>::_Rep*
00355 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00356 _S_create(size_type __capacity, size_type __old_capacity,
00357 const _Alloc& __alloc)
00358 {
00359
00360
00361 if (__capacity > size_type(_S_max_size))
00362 std::__throw_length_error(__N("__rc_string_base::_Rep::_S_create"));
00363
00364
00365
00366
00367
00368
00369
00370
00371
00372
00373
00374
00375
00376
00377
00378
00379
00380
00381
00382
00383
00384
00385
00386
00387 const size_type __pagesize = 4096;
00388 const size_type __malloc_header_size = 4 * sizeof(void*);
00389
00390
00391
00392
00393 if (__capacity > __old_capacity && __capacity < 2 * __old_capacity)
00394 {
00395 __capacity = 2 * __old_capacity;
00396
00397 if (__capacity > size_type(_S_max_size))
00398 __capacity = size_type(_S_max_size);
00399 }
00400
00401
00402
00403
00404
00405
00406 size_type __size = ((__capacity + 1) * sizeof(_CharT)
00407 + 2 * sizeof(_Rep) - 1);
00408
00409 const size_type __adj_size = __size + __malloc_header_size;
00410 if (__adj_size > __pagesize && __capacity > __old_capacity)
00411 {
00412 const size_type __extra = __pagesize - __adj_size % __pagesize;
00413 __capacity += __extra / sizeof(_CharT);
00414 if (__capacity > size_type(_S_max_size))
00415 __capacity = size_type(_S_max_size);
00416 __size = (__capacity + 1) * sizeof(_CharT) + 2 * sizeof(_Rep) - 1;
00417 }
00418
00419
00420
00421 _Rep* __place = _Rep_alloc_type(__alloc).allocate(__size / sizeof(_Rep));
00422 _Rep* __p = new (__place) _Rep;
00423 __p->_M_info._M_capacity = __capacity;
00424 return __p;
00425 }
00426
00427 template<typename _CharT, typename _Traits, typename _Alloc>
00428 void
00429 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00430 _M_destroy(const _Alloc& __a) throw ()
00431 {
00432 const size_type __size = ((_M_info._M_capacity + 1) * sizeof(_CharT)
00433 + 2 * sizeof(_Rep) - 1);
00434 _Rep_alloc_type(__a).deallocate(this, __size / sizeof(_Rep));
00435 }
00436
00437 template<typename _CharT, typename _Traits, typename _Alloc>
00438 _CharT*
00439 __rc_string_base<_CharT, _Traits, _Alloc>::_Rep::
00440 _M_clone(const _Alloc& __alloc, size_type __res)
00441 {
00442
00443 const size_type __requested_cap = _M_info._M_length + __res;
00444 _Rep* __r = _Rep::_S_create(__requested_cap, _M_info._M_capacity,
00445 __alloc);
00446
00447 if (_M_info._M_length)
00448 _S_copy(__r->_M_refdata(), _M_refdata(), _M_info._M_length);
00449
00450 __r->_M_set_length(_M_info._M_length);
00451 return __r->_M_refdata();
00452 }
00453
00454 template<typename _CharT, typename _Traits, typename _Alloc>
00455 __rc_string_base<_CharT, _Traits, _Alloc>::
00456 __rc_string_base(const _Alloc& __a)
00457 : _M_dataplus(__a, _S_construct(size_type(), _CharT(), __a)) { }
00458
00459 template<typename _CharT, typename _Traits, typename _Alloc>
00460 __rc_string_base<_CharT, _Traits, _Alloc>::
00461 __rc_string_base(const __rc_string_base& __rcs)
00462 : _M_dataplus(__rcs._M_get_allocator(),
00463 __rcs._M_grab(__rcs._M_get_allocator())) { }
00464
00465 template<typename _CharT, typename _Traits, typename _Alloc>
00466 __rc_string_base<_CharT, _Traits, _Alloc>::
00467 __rc_string_base(size_type __n, _CharT __c, const _Alloc& __a)
00468 : _M_dataplus(__a, _S_construct(__n, __c, __a)) { }
00469
00470 template<typename _CharT, typename _Traits, typename _Alloc>
00471 template<typename _InputIterator>
00472 __rc_string_base<_CharT, _Traits, _Alloc>::
00473 __rc_string_base(_InputIterator __beg, _InputIterator __end,
00474 const _Alloc& __a)
00475 : _M_dataplus(__a, _S_construct(__beg, __end, __a)) { }
00476
00477 template<typename _CharT, typename _Traits, typename _Alloc>
00478 void
00479 __rc_string_base<_CharT, _Traits, _Alloc>::
00480 _M_leak_hard()
00481 {
00482 if (_M_is_shared())
00483 _M_erase(0, 0);
00484 _M_set_leaked();
00485 }
00486
00487
00488
00489
00490
00491 template<typename _CharT, typename _Traits, typename _Alloc>
00492 template<typename _InIterator>
00493 _CharT*
00494 __rc_string_base<_CharT, _Traits, _Alloc>::
00495 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00496 std::input_iterator_tag)
00497 {
00498 if (__beg == __end && __a == _Alloc())
00499 return _S_empty_rep._M_refcopy();
00500
00501
00502 _CharT __buf[128];
00503 size_type __len = 0;
00504 while (__beg != __end && __len < sizeof(__buf) / sizeof(_CharT))
00505 {
00506 __buf[__len++] = *__beg;
00507 ++__beg;
00508 }
00509 _Rep* __r = _Rep::_S_create(__len, size_type(0), __a);
00510 _S_copy(__r->_M_refdata(), __buf, __len);
00511 try
00512 {
00513 while (__beg != __end)
00514 {
00515 if (__len == __r->_M_info._M_capacity)
00516 {
00517
00518 _Rep* __another = _Rep::_S_create(__len + 1, __len, __a);
00519 _S_copy(__another->_M_refdata(), __r->_M_refdata(), __len);
00520 __r->_M_destroy(__a);
00521 __r = __another;
00522 }
00523 __r->_M_refdata()[__len++] = *__beg;
00524 ++__beg;
00525 }
00526 }
00527 catch(...)
00528 {
00529 __r->_M_destroy(__a);
00530 __throw_exception_again;
00531 }
00532 __r->_M_set_length(__len);
00533 return __r->_M_refdata();
00534 }
00535
00536 template<typename _CharT, typename _Traits, typename _Alloc>
00537 template<typename _InIterator>
00538 _CharT*
00539 __rc_string_base<_CharT, _Traits, _Alloc>::
00540 _S_construct(_InIterator __beg, _InIterator __end, const _Alloc& __a,
00541 std::forward_iterator_tag)
00542 {
00543 if (__beg == __end && __a == _Alloc())
00544 return _S_empty_rep._M_refcopy();
00545
00546
00547 if (__builtin_expect(_S_is_null_pointer(__beg) && __beg != __end, 0))
00548 std::__throw_logic_error(__N("__rc_string_base::"
00549 "_S_construct NULL not valid"));
00550
00551 const size_type __dnew = static_cast<size_type>(std::distance(__beg,
00552 __end));
00553
00554 _Rep* __r = _Rep::_S_create(__dnew, size_type(0), __a);
00555 try
00556 { _S_copy_chars(__r->_M_refdata(), __beg, __end); }
00557 catch(...)
00558 {
00559 __r->_M_destroy(__a);
00560 __throw_exception_again;
00561 }
00562 __r->_M_set_length(__dnew);
00563 return __r->_M_refdata();
00564 }
00565
00566 template<typename _CharT, typename _Traits, typename _Alloc>
00567 _CharT*
00568 __rc_string_base<_CharT, _Traits, _Alloc>::
00569 _S_construct(size_type __n, _CharT __c, const _Alloc& __a)
00570 {
00571 if (__n == 0 && __a == _Alloc())
00572 return _S_empty_rep._M_refcopy();
00573
00574
00575 _Rep* __r = _Rep::_S_create(__n, size_type(0), __a);
00576 if (__n)
00577 _S_assign(__r->_M_refdata(), __n, __c);
00578
00579 __r->_M_set_length(__n);
00580 return __r->_M_refdata();
00581 }
00582
00583 template<typename _CharT, typename _Traits, typename _Alloc>
00584 void
00585 __rc_string_base<_CharT, _Traits, _Alloc>::
00586 _M_swap(__rc_string_base& __rcs)
00587 {
00588 if (_M_is_leaked())
00589 _M_set_sharable();
00590 if (__rcs._M_is_leaked())
00591 __rcs._M_set_sharable();
00592
00593 _CharT* __tmp = _M_data();
00594 _M_data(__rcs._M_data());
00595 __rcs._M_data(__tmp);
00596
00597
00598 std::__alloc_swap<allocator_type>::_S_do_it(_M_get_allocator(),
00599 __rcs._M_get_allocator());
00600 }
00601
00602 template<typename _CharT, typename _Traits, typename _Alloc>
00603 void
00604 __rc_string_base<_CharT, _Traits, _Alloc>::
00605 _M_assign(const __rc_string_base& __rcs)
00606 {
00607 if (_M_rep() != __rcs._M_rep())
00608 {
00609 _CharT* __tmp = __rcs._M_grab(_M_get_allocator());
00610 _M_dispose();
00611 _M_data(__tmp);
00612 }
00613 }
00614
00615 template<typename _CharT, typename _Traits, typename _Alloc>
00616 void
00617 __rc_string_base<_CharT, _Traits, _Alloc>::
00618 _M_reserve(size_type __res)
00619 {
00620
00621 if (__res < _M_length())
00622 __res = _M_length();
00623
00624 if (__res != _M_capacity() || _M_is_shared())
00625 {
00626 _CharT* __tmp = _M_rep()->_M_clone(_M_get_allocator(),
00627 __res - _M_length());
00628 _M_dispose();
00629 _M_data(__tmp);
00630 }
00631 }
00632
00633 template<typename _CharT, typename _Traits, typename _Alloc>
00634 void
00635 __rc_string_base<_CharT, _Traits, _Alloc>::
00636 _M_mutate(size_type __pos, size_type __len1, const _CharT* __s,
00637 size_type __len2)
00638 {
00639 const size_type __how_much = _M_length() - __pos - __len1;
00640
00641 _Rep* __r = _Rep::_S_create(_M_length() + __len2 - __len1,
00642 _M_capacity(), _M_get_allocator());
00643
00644 if (__pos)
00645 _S_copy(__r->_M_refdata(), _M_data(), __pos);
00646 if (__s && __len2)
00647 _S_copy(__r->_M_refdata() + __pos, __s, __len2);
00648 if (__how_much)
00649 _S_copy(__r->_M_refdata() + __pos + __len2,
00650 _M_data() + __pos + __len1, __how_much);
00651
00652 _M_dispose();
00653 _M_data(__r->_M_refdata());
00654 }
00655
00656 template<typename _CharT, typename _Traits, typename _Alloc>
00657 void
00658 __rc_string_base<_CharT, _Traits, _Alloc>::
00659 _M_erase(size_type __pos, size_type __n)
00660 {
00661 const size_type __new_size = _M_length() - __n;
00662 const size_type __how_much = _M_length() - __pos - __n;
00663
00664 if (_M_is_shared())
00665 {
00666
00667 _Rep* __r = _Rep::_S_create(__new_size, _M_capacity(),
00668 _M_get_allocator());
00669
00670 if (__pos)
00671 _S_copy(__r->_M_refdata(), _M_data(), __pos);
00672 if (__how_much)
00673 _S_copy(__r->_M_refdata() + __pos,
00674 _M_data() + __pos + __n, __how_much);
00675
00676 _M_dispose();
00677 _M_data(__r->_M_refdata());
00678 }
00679 else if (__how_much && __n)
00680 {
00681
00682 _S_move(_M_data() + __pos,
00683 _M_data() + __pos + __n, __how_much);
00684 }
00685
00686 _M_rep()->_M_set_length(__new_size);
00687 }
00688
00689 template<>
00690 inline bool
00691 __rc_string_base<char, std::char_traits<char>,
00692 std::allocator<char> >::
00693 _M_compare(const __rc_string_base& __rcs) const
00694 {
00695 if (_M_rep() == __rcs._M_rep())
00696 return true;
00697 return false;
00698 }
00699
00700 template<>
00701 inline bool
00702 __rc_string_base<wchar_t, std::char_traits<wchar_t>,
00703 std::allocator<wchar_t> >::
00704 _M_compare(const __rc_string_base& __rcs) const
00705 {
00706 if (_M_rep() == __rcs._M_rep())
00707 return true;
00708 return false;
00709 }
00710 }
00711
00712 #endif