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
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 {
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