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
00037
00038
00039
00040
00041
00042
00043
00044
00045
00046
00047
00048
#include <cstdio>
00049
#include <ostream>
00050
#include <bits/functexcept.h>
00051
00052
#include <ext/algorithm>
00053
#include <ext/memory>
00054
#include <ext/numeric>
00055
00056
namespace __gnu_cxx
00057 {
00058
using std::size_t;
00059
using std::printf;
00060
using std::basic_ostream;
00061
using std::__throw_length_error;
00062
using std::_Destroy;
00063
using std::uninitialized_fill_n;
00064
00065
00066
00067
00068
00069
template <
class _CharT,
class _Alloc>
00070
void
00071 _Rope_iterator_base<_CharT, _Alloc>::
00072 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
00073 {
00074
const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
00075 size_t __leaf_pos = __x._M_leaf_pos;
00076 size_t __pos = __x._M_current_pos;
00077
00078
switch(__leaf->_M_tag)
00079 {
00080
case _Rope_constants::_S_leaf:
00081 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
00082 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
00083 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
00084
break;
00085
case _Rope_constants::_S_function:
00086
case _Rope_constants::_S_substringfn:
00087 {
00088 size_t __len = _S_iterator_buf_len;
00089 size_t __buf_start_pos = __leaf_pos;
00090 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
00091 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
00092 _Alloc>*)__leaf)->_M_fn;
00093
if (__buf_start_pos + __len <= __pos)
00094 {
00095 __buf_start_pos = __pos - __len / 4;
00096
if (__buf_start_pos + __len > __leaf_end)
00097 __buf_start_pos = __leaf_end - __len;
00098 }
00099
if (__buf_start_pos + __len > __leaf_end)
00100 __len = __leaf_end - __buf_start_pos;
00101 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
00102 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
00103 __x._M_buf_start = __x._M_tmp_buf;
00104 __x._M_buf_end = __x._M_tmp_buf + __len;
00105 }
00106
break;
00107
default:
00108
break;
00109 }
00110 }
00111
00112
00113
00114
template <
class _CharT,
class _Alloc>
00115
void
00116 _Rope_iterator_base<_CharT, _Alloc>::
00117 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
00118 {
00119
const _RopeRep* __path[_Rope_constants::_S_max_rope_depth + 1];
00120
const _RopeRep* __curr_rope;
00121
int __curr_depth = -1;
00122 size_t __curr_start_pos = 0;
00123 size_t __pos = __x._M_current_pos;
00124
unsigned char __dirns = 0;
00125
00126
if (__pos >= __x._M_root->_M_size)
00127 {
00128 __x._M_buf_ptr = 0;
00129
return;
00130 }
00131 __curr_rope = __x._M_root;
00132
if (0 != __curr_rope->_M_c_string)
00133 {
00134
00135 __x._M_buf_start = __curr_rope->_M_c_string;
00136 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
00137 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
00138 __x._M_path_end[0] = __curr_rope;
00139 __x._M_leaf_index = 0;
00140 __x._M_leaf_pos = 0;
00141
return;
00142 }
00143
for(;;)
00144 {
00145 ++__curr_depth;
00146 __path[__curr_depth] = __curr_rope;
00147
switch(__curr_rope->_M_tag)
00148 {
00149
case _Rope_constants::_S_leaf:
00150
case _Rope_constants::_S_function:
00151
case _Rope_constants::_S_substringfn:
00152 __x._M_leaf_pos = __curr_start_pos;
00153
goto done;
00154
case _Rope_constants::_S_concat:
00155 {
00156 _Rope_RopeConcatenation<_CharT, _Alloc>* __c =
00157 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
00158 _RopeRep* __left = __c->_M_left;
00159 size_t __left_len = __left->_M_size;
00160
00161 __dirns <<= 1;
00162
if (__pos >= __curr_start_pos + __left_len)
00163 {
00164 __dirns |= 1;
00165 __curr_rope = __c->_M_right;
00166 __curr_start_pos += __left_len;
00167 }
00168
else
00169 __curr_rope = __left;
00170 }
00171
break;
00172 }
00173 }
00174 done:
00175
00176 {
00177
int __i = -1;
00178
int __j = __curr_depth + 1 - _S_path_cache_len;
00179
00180
if (__j < 0) __j = 0;
00181
while (__j <= __curr_depth)
00182 __x._M_path_end[++__i] = __path[__j++];
00183 __x._M_leaf_index = __i;
00184 }
00185 __x._M_path_directions = __dirns;
00186 _S_setbuf(__x);
00187 }
00188
00189
00190
00191
template <
class _CharT,
class _Alloc>
00192
void
00193 _Rope_iterator_base<_CharT, _Alloc>::
00194 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
00195 {
00196
int __current_index = __x._M_leaf_index;
00197
const _RopeRep* __current_node = __x._M_path_end[__current_index];
00198 size_t __len = __current_node->_M_size;
00199 size_t __node_start_pos = __x._M_leaf_pos;
00200
unsigned char __dirns = __x._M_path_directions;
00201 _Rope_RopeConcatenation<_CharT, _Alloc>* __c;
00202
00203
if (__x._M_current_pos - __node_start_pos < __len)
00204 {
00205
00206 _S_setbuf(__x);
00207
return;
00208 }
00209
00210
while (--__current_index >= 0)
00211 {
00212
if (!(__dirns & 1) )
00213
break;
00214 __current_node = __x._M_path_end[__current_index];
00215 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
00216
00217
00218 __node_start_pos -= __c->_M_left->_M_size;
00219 __dirns >>= 1;
00220 }
00221
if (__current_index < 0)
00222 {
00223
00224 _S_setcache(__x);
00225
return;
00226 }
00227 __current_node = __x._M_path_end[__current_index];
00228 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node;
00229
00230
00231
00232 __node_start_pos += __c->_M_left->_M_size;
00233 __current_node = __c->_M_right;
00234 __x._M_path_end[++__current_index] = __current_node;
00235 __dirns |= 1;
00236
while (_Rope_constants::_S_concat == __current_node->_M_tag)
00237 {
00238 ++__current_index;
00239
if (_S_path_cache_len == __current_index)
00240 {
00241
int __i;
00242
for (__i = 0; __i < _S_path_cache_len-1; __i++)
00243 __x._M_path_end[__i] = __x._M_path_end[__i+1];
00244 --__current_index;
00245 }
00246 __current_node =
00247 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
00248 __x._M_path_end[__current_index] = __current_node;
00249 __dirns <<= 1;
00250
00251 }
00252 __x._M_leaf_index = __current_index;
00253 __x._M_leaf_pos = __node_start_pos;
00254 __x._M_path_directions = __dirns;
00255 _S_setbuf(__x);
00256 }
00257
00258
template <
class _CharT,
class _Alloc>
00259
void
00260 _Rope_iterator_base<_CharT, _Alloc>::
00261 _M_incr(size_t __n)
00262 {
00263 _M_current_pos += __n;
00264
if (0 != _M_buf_ptr)
00265 {
00266 size_t __chars_left = _M_buf_end - _M_buf_ptr;
00267
if (__chars_left > __n)
00268 _M_buf_ptr += __n;
00269
else if (__chars_left == __n)
00270 {
00271 _M_buf_ptr += __n;
00272 _S_setcache_for_incr(*
this);
00273 }
00274
else
00275 _M_buf_ptr = 0;
00276 }
00277 }
00278
00279
template <
class _CharT,
class _Alloc>
00280
void
00281 _Rope_iterator_base<_CharT, _Alloc>::
00282 _M_decr(size_t __n)
00283 {
00284
if (0 != _M_buf_ptr)
00285 {
00286 size_t __chars_left = _M_buf_ptr - _M_buf_start;
00287
if (__chars_left >= __n)
00288 _M_buf_ptr -= __n;
00289
else
00290 _M_buf_ptr = 0;
00291 }
00292 _M_current_pos -= __n;
00293 }
00294
00295
template <
class _CharT,
class _Alloc>
00296
void
00297 _Rope_iterator<_CharT, _Alloc>::
00298 _M_check()
00299 {
00300
if (_M_root_rope->_M_tree_ptr != this->_M_root)
00301 {
00302
00303 _RopeRep::_S_unref(this->_M_root);
00304 this->_M_root = _M_root_rope->_M_tree_ptr;
00305 _RopeRep::_S_ref(this->_M_root);
00306 this->_M_buf_ptr = 0;
00307 }
00308 }
00309
00310
template <
class _CharT,
class _Alloc>
00311
inline
00312 _Rope_const_iterator<_CharT, _Alloc>::
00313 _Rope_const_iterator(
const _Rope_iterator<_CharT, _Alloc>& __x)
00314 : _Rope_iterator_base<_CharT, _Alloc>(__x)
00315 { }
00316
00317
template <
class _CharT,
class _Alloc>
00318
inline
00319 _Rope_iterator<_CharT, _Alloc>::
00320 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos)
00321 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
00322 _M_root_rope(&__r)
00323 { _RopeRep::_S_ref(this->_M_root); }
00324
00325
template <
class _CharT,
class _Alloc>
00326
inline size_t
00327 rope<_CharT, _Alloc>::
00328 _S_char_ptr_len(
const _CharT* __s)
00329 {
00330
const _CharT* __p = __s;
00331
00332
while (!_S_is0(*__p))
00333 ++__p;
00334
return (__p - __s);
00335 }
00336
00337
00338
#ifndef __GC
00339
00340
template <
class _CharT,
class _Alloc>
00341
inline void
00342 _Rope_RopeRep<_CharT, _Alloc>::
00343 _M_free_c_string()
00344 {
00345 _CharT* __cstr = _M_c_string;
00346
if (0 != __cstr)
00347 {
00348 size_t __size = this->_M_size + 1;
00349 _Destroy(__cstr, __cstr + __size, get_allocator());
00350 this->_Data_deallocate(__cstr, __size);
00351 }
00352 }
00353
00354
template <
class _CharT,
class _Alloc>
00355
inline void
00356 _Rope_RopeRep<_CharT, _Alloc>::
00357 _S_free_string(_CharT* __s, size_t __n, allocator_type __a)
00358 {
00359
if (!_S_is_basic_char_type((_CharT*)0))
00360 _Destroy(__s, __s + __n, __a);
00361
00362
00363 __a.deallocate(__s,
00364 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
00365 }
00366
00367
00368
00369
00370
00371
00372
00373
template <
class _CharT,
class _Alloc>
00374
void
00375 _Rope_RopeRep<_CharT, _Alloc>::
00376 _M_free_tree()
00377 {
00378
switch(_M_tag)
00379 {
00380
case _Rope_constants::_S_leaf:
00381 {
00382 _Rope_RopeLeaf<_CharT, _Alloc>* __l
00383 = (_Rope_RopeLeaf<_CharT, _Alloc>*)
this;
00384 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
00385 _L_deallocate(__l, 1);
00386
break;
00387 }
00388
case _Rope_constants::_S_concat:
00389 {
00390 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
00391 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)
this;
00392 __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
~_Rope_RopeConcatenation();
00393 _C_deallocate(__c, 1);
00394
break;
00395 }
00396
case _Rope_constants::_S_function:
00397 {
00398 _Rope_RopeFunction<_CharT, _Alloc>* __f
00399 = (_Rope_RopeFunction<_CharT, _Alloc>*)
this;
00400 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
00401 _F_deallocate(__f, 1);
00402
break;
00403 }
00404
case _Rope_constants::_S_substringfn:
00405 {
00406 _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
00407 (_Rope_RopeSubstring<_CharT, _Alloc>*)
this;
00408 __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
~_Rope_RopeSubstring();
00409 _S_deallocate(__ss, 1);
00410
break;
00411 }
00412 }
00413 }
00414
#else
00415
00416
template <
class _CharT,
class _Alloc>
00417
inline void
00418 _Rope_RopeRep<_CharT, _Alloc>::
00419 _S_free_string(
const _CharT*, size_t, allocator_type)
00420 { }
00421
00422
#endif
00423
00424
00425
00426
template <
class _CharT,
class _Alloc>
00427
typename rope<_CharT, _Alloc>::_RopeLeaf*
00428 rope<_CharT, _Alloc>::
00429 _S_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter, size_t __len)
00430 {
00431 size_t __old_len = __r->_M_size;
00432 _CharT* __new_data = (_CharT*)
00433 _Data_allocate(_S_rounded_up_size(__old_len + __len));
00434 _RopeLeaf* __result;
00435
00436 uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
00437 uninitialized_copy_n(__iter, __len, __new_data + __old_len);
00438 _S_cond_store_eos(__new_data[__old_len + __len]);
00439
try
00440 {
00441 __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
00442 __r->get_allocator());
00443 }
00444
catch(...)
00445 {
00446 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
00447 __r->get_allocator());
00448 __throw_exception_again;
00449 }
00450
return __result;
00451 }
00452
00453
#ifndef __GC
00454
00455
template <
class _CharT,
class _Alloc>
00456
typename rope<_CharT,_Alloc>::_RopeLeaf*
00457 rope<_CharT, _Alloc>::
00458 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
const _CharT* __iter,
00459 size_t __len)
00460 {
00461
if (__r->_M_ref_count > 1)
00462
return _S_leaf_concat_char_iter(__r, __iter, __len);
00463 size_t __old_len = __r->_M_size;
00464
if (_S_allocated_capacity(__old_len) >= __old_len + __len)
00465 {
00466
00467
00468 uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
00469
if (_S_is_basic_char_type((_CharT*)0))
00470 _S_cond_store_eos(__r->_M_data[__old_len + __len]);
00471
else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
00472 {
00473 __r->_M_free_c_string();
00474 __r->_M_c_string = 0;
00475 }
00476 __r->_M_size = __old_len + __len;
00477 __r->_M_ref_count = 2;
00478
return __r;
00479 }
00480
else
00481 {
00482 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
00483
return __result;
00484 }
00485 }
00486
#endif
00487
00488
00489
00490
00491
template <
class _CharT,
class _Alloc>
00492
typename rope<_CharT, _Alloc>::_RopeRep*
00493 rope<_CharT, _Alloc>::
00494 _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
00495 {
00496 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
00497 __left->
00498 get_allocator());
00499 size_t __depth = __result->_M_depth;
00500
00501
if (__depth > 20 && (__result->_M_size < 1000
00502 || __depth > _Rope_constants::_S_max_rope_depth))
00503 {
00504 _RopeRep* __balanced;
00505
00506
try
00507 {
00508 __balanced = _S_balance(__result);
00509 __result->_M_unref_nonnil();
00510 }
00511
catch(...)
00512 {
00513 _C_deallocate(__result,1);
00514 __throw_exception_again;
00515 }
00516
00517
00518
00519
00520
return __balanced;
00521 }
00522
else
00523
return __result;
00524 }
00525
00526
template <
class _CharT,
class _Alloc>
00527
typename rope<_CharT, _Alloc>::_RopeRep*
00528 rope<_CharT, _Alloc>::
00529 _S_concat_char_iter(_RopeRep* __r,
const _CharT*__s, size_t __slen)
00530 {
00531 _RopeRep* __result;
00532
if (0 == __slen)
00533 {
00534 _S_ref(__r);
00535
return __r;
00536 }
00537
if (0 == __r)
00538
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00539 __r->get_allocator());
00540
if (_Rope_constants::_S_leaf == __r->_M_tag
00541 && __r->_M_size + __slen <= _S_copy_max)
00542 {
00543 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
00544
return __result;
00545 }
00546
if (_Rope_constants::_S_concat == __r->_M_tag
00547 && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
00548 __r)->_M_right->_M_tag)
00549 {
00550 _RopeLeaf* __right =
00551 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
00552
if (__right->_M_size + __slen <= _S_copy_max)
00553 {
00554 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
00555 _RopeRep* __nright =
00556 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
00557 __left->_M_ref_nonnil();
00558
try
00559 { __result = _S_tree_concat(__left, __nright); }
00560
catch(...)
00561 {
00562 _S_unref(__left);
00563 _S_unref(__nright);
00564 __throw_exception_again;
00565 }
00566
return __result;
00567 }
00568 }
00569 _RopeRep* __nright =
00570 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00571
try
00572 {
00573 __r->_M_ref_nonnil();
00574 __result = _S_tree_concat(__r, __nright);
00575 }
00576
catch(...)
00577 {
00578 _S_unref(__r);
00579 _S_unref(__nright);
00580 __throw_exception_again;
00581 }
00582
return __result;
00583 }
00584
00585
#ifndef __GC
00586
template <
class _CharT,
class _Alloc>
00587
typename rope<_CharT,_Alloc>::_RopeRep*
00588 rope<_CharT,_Alloc>::
00589 _S_destr_concat_char_iter(_RopeRep* __r,
const _CharT* __s, size_t __slen)
00590 {
00591 _RopeRep* __result;
00592
if (0 == __r)
00593
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00594 __r->get_allocator());
00595 size_t __count = __r->_M_ref_count;
00596 size_t __orig_size = __r->_M_size;
00597
if (__count > 1)
00598
return _S_concat_char_iter(__r, __s, __slen);
00599
if (0 == __slen)
00600 {
00601 __r->_M_ref_count = 2;
00602
return __r;
00603 }
00604
if (__orig_size + __slen <= _S_copy_max
00605 && _Rope_constants::_S_leaf == __r->_M_tag)
00606 {
00607 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
00608 __slen);
00609
return __result;
00610 }
00611
if (_Rope_constants::_S_concat == __r->_M_tag)
00612 {
00613 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
00614 __r)->_M_right);
00615
if (_Rope_constants::_S_leaf == __right->_M_tag
00616 && __right->_M_size + __slen <= _S_copy_max)
00617 {
00618 _RopeRep* __new_right =
00619 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
00620
if (__right == __new_right)
00621 __new_right->_M_ref_count = 1;
00622
else
00623 __right->_M_unref_nonnil();
00624 __r->_M_ref_count = 2;
00625 ((_RopeConcatenation*)__r)->_M_right = __new_right;
00626 __r->_M_size = __orig_size + __slen;
00627
if (0 != __r->_M_c_string)
00628 {
00629 __r->_M_free_c_string();
00630 __r->_M_c_string = 0;
00631 }
00632
return __r;
00633 }
00634 }
00635 _RopeRep* __right =
00636 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00637 __r->_M_ref_nonnil();
00638
try
00639 { __result = _S_tree_concat(__r, __right); }
00640
catch(...)
00641 {
00642 _S_unref(__r);
00643 _S_unref(__right);
00644 __throw_exception_again;
00645 }
00646
return __result;
00647 }
00648
#endif
00649
00650
template <
class _CharT,
class _Alloc>
00651
typename rope<_CharT, _Alloc>::_RopeRep*
00652 rope<_CharT, _Alloc>::
00653 _S_concat(_RopeRep* __left, _RopeRep* __right)
00654 {
00655
if (0 == __left)
00656 {
00657 _S_ref(__right);
00658
return __right;
00659 }
00660
if (0 == __right)
00661 {
00662 __left->_M_ref_nonnil();
00663
return __left;
00664 }
00665
if (_Rope_constants::_S_leaf == __right->_M_tag)
00666 {
00667
if (_Rope_constants::_S_leaf == __left->_M_tag)
00668 {
00669
if (__right->_M_size + __left->_M_size <= _S_copy_max)
00670
return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
00671 ((_RopeLeaf*)__right)->_M_data,
00672 __right->_M_size);
00673 }
00674
else if (_Rope_constants::_S_concat == __left->_M_tag
00675 && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
00676 __left)->_M_right->_M_tag)
00677 {
00678 _RopeLeaf* __leftright =
00679 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
00680
if (__leftright->_M_size + __right->_M_size <= _S_copy_max)
00681 {
00682 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
00683 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
00684 ((_RopeLeaf*)
00685 __right)->
00686 _M_data,
00687 __right->_M_size);
00688 __leftleft->_M_ref_nonnil();
00689
try
00690 {
return(_S_tree_concat(__leftleft, __rest)); }
00691
catch(...)
00692 {
00693 _S_unref(__leftleft);
00694 _S_unref(__rest);
00695 __throw_exception_again;
00696 }
00697 }
00698 }
00699 }
00700 __left->_M_ref_nonnil();
00701 __right->_M_ref_nonnil();
00702
try
00703 {
return(_S_tree_concat(__left, __right)); }
00704
catch(...)
00705 {
00706 _S_unref(__left);
00707 _S_unref(__right);
00708 __throw_exception_again;
00709 }
00710 }
00711
00712
template <
class _CharT,
class _Alloc>
00713
typename rope<_CharT, _Alloc>::_RopeRep*
00714 rope<_CharT, _Alloc>::
00715 _S_substring(_RopeRep* __base, size_t __start, size_t __endp1)
00716 {
00717
if (0 == __base)
00718
return 0;
00719 size_t __len = __base->_M_size;
00720 size_t __adj_endp1;
00721
const size_t __lazy_threshold = 128;
00722
00723
if (__endp1 >= __len)
00724 {
00725
if (0 == __start)
00726 {
00727 __base->_M_ref_nonnil();
00728
return __base;
00729 }
00730
else
00731 __adj_endp1 = __len;
00732
00733 }
00734
else
00735 __adj_endp1 = __endp1;
00736
00737
switch(__base->_M_tag)
00738 {
00739
case _Rope_constants::_S_concat:
00740 {
00741 _RopeConcatenation* __c = (_RopeConcatenation*)__base;
00742 _RopeRep* __left = __c->_M_left;
00743 _RopeRep* __right = __c->_M_right;
00744 size_t __left_len = __left->_M_size;
00745 _RopeRep* __result;
00746
00747
if (__adj_endp1 <= __left_len)
00748
return _S_substring(__left, __start, __endp1);
00749
else if (__start >= __left_len)
00750
return _S_substring(__right, __start - __left_len,
00751 __adj_endp1 - __left_len);
00752 _Self_destruct_ptr __left_result(_S_substring(__left,
00753 __start,
00754 __left_len));
00755 _Self_destruct_ptr __right_result(_S_substring(__right, 0,
00756 __endp1
00757 - __left_len));
00758 __result = _S_concat(__left_result, __right_result);
00759
return __result;
00760 }
00761
case _Rope_constants::_S_leaf:
00762 {
00763 _RopeLeaf* __l = (_RopeLeaf*)__base;
00764 _RopeLeaf* __result;
00765 size_t __result_len;
00766
if (__start >= __adj_endp1)
00767
return 0;
00768 __result_len = __adj_endp1 - __start;
00769
if (__result_len > __lazy_threshold)
00770
goto lazy;
00771
#ifdef __GC
00772
const _CharT* __section = __l->_M_data + __start;
00773 __result = _S_new_RopeLeaf(__section, __result_len,
00774 __base->get_allocator());
00775 __result->_M_c_string = 0;
00776
#else
00777
00778 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
00779 __result_len,
00780 __base->
00781 get_allocator());
00782
#endif
00783
return __result;
00784 }
00785
case _Rope_constants::_S_substringfn:
00786
00787 {
00788 _RopeSubstring* __old = (_RopeSubstring*)__base;
00789 size_t __result_len;
00790
if (__start >= __adj_endp1)
00791
return 0;
00792 __result_len = __adj_endp1 - __start;
00793
if (__result_len > __lazy_threshold)
00794 {
00795 _RopeSubstring* __result =
00796 _S_new_RopeSubstring(__old->_M_base,
00797 __start + __old->_M_start,
00798 __adj_endp1 - __start,
00799 __base->get_allocator());
00800
return __result;
00801
00802 }
00803 }
00804
case _Rope_constants::_S_function:
00805 {
00806 _RopeFunction* __f = (_RopeFunction*)__base;
00807 _CharT* __section;
00808 size_t __result_len;
00809
if (__start >= __adj_endp1)
00810
return 0;
00811 __result_len = __adj_endp1 - __start;
00812
00813
if (__result_len > __lazy_threshold)
00814
goto lazy;
00815 __section = (_CharT*)
00816 _Data_allocate(_S_rounded_up_size(__result_len));
00817
try
00818 { (*(__f->_M_fn))(__start, __result_len, __section); }
00819
catch(...)
00820 {
00821 _RopeRep::__STL_FREE_STRING(__section, __result_len,
00822 __base->get_allocator());
00823 __throw_exception_again;
00824 }
00825 _S_cond_store_eos(__section[__result_len]);
00826
return _S_new_RopeLeaf(__section, __result_len,
00827 __base->get_allocator());
00828 }
00829 }
00830 lazy:
00831 {
00832
00833
return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
00834 __base->get_allocator());
00835 }
00836 }
00837
00838
template<
class _CharT>
00839
class _Rope_flatten_char_consumer
00840 :
public _Rope_char_consumer<_CharT>
00841 {
00842
private:
00843 _CharT* _M_buf_ptr;
00844
public:
00845
00846 _Rope_flatten_char_consumer(_CharT* __buffer)
00847 { _M_buf_ptr = __buffer; };
00848
00849 ~_Rope_flatten_char_consumer() {}
00850
00851
bool
00852 operator()(
const _CharT* __leaf, size_t __n)
00853 {
00854 uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
00855 _M_buf_ptr += __n;
00856
return true;
00857 }
00858 };
00859
00860
template<
class _CharT>
00861
class _Rope_find_char_char_consumer
00862 :
public _Rope_char_consumer<_CharT>
00863 {
00864
private:
00865 _CharT _M_pattern;
00866
public:
00867 size_t _M_count;
00868
00869 _Rope_find_char_char_consumer(_CharT __p)
00870 : _M_pattern(__p), _M_count(0) {}
00871
00872 ~_Rope_find_char_char_consumer() {}
00873
00874
bool
00875 operator()(
const _CharT* __leaf, size_t __n)
00876 {
00877 size_t __i;
00878
for (__i = 0; __i < __n; __i++)
00879 {
00880
if (__leaf[__i] == _M_pattern)
00881 {
00882 _M_count += __i;
00883
return false;
00884 }
00885 }
00886 _M_count += __n;
return true;
00887 }
00888 };
00889
00890
template<
class _CharT,
class _Traits>
00891
00892
class _Rope_insert_char_consumer
00893 :
public _Rope_char_consumer<_CharT>
00894 {
00895
private:
00896
typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
00897 _Insert_ostream& _M_o;
00898
public:
00899 _Rope_insert_char_consumer(_Insert_ostream& __writer)
00900 : _M_o(__writer) {};
00901 ~_Rope_insert_char_consumer() { };
00902
00903
bool operator() (
const _CharT* __leaf, size_t __n);
00904
00905 };
00906
00907
template<
class _CharT,
class _Traits>
00908
bool
00909 _Rope_insert_char_consumer<_CharT, _Traits>::
00910 operator()(
const _CharT* __leaf, size_t __n)
00911 {
00912 size_t __i;
00913
00914
for (__i = 0; __i < __n; __i++)
00915 _M_o.put(__leaf[__i]);
00916
return true;
00917 }
00918
00919
template <
class _CharT,
class _Alloc>
00920
bool
00921 rope<_CharT, _Alloc>::
00922 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
00923
const _RopeRep* __r, size_t __begin, size_t __end)
00924 {
00925
if (0 == __r)
00926
return true;
00927
switch(__r->_M_tag)
00928 {
00929
case _Rope_constants::_S_concat:
00930 {
00931 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
00932 _RopeRep* __left = __conc->_M_left;
00933 size_t __left_len = __left->_M_size;
00934
if (__begin < __left_len)
00935 {
00936 size_t __left_end =
std::min(__left_len, __end);
00937
if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
00938
return false;
00939 }
00940
if (__end > __left_len)
00941 {
00942 _RopeRep* __right = __conc->_M_right;
00943 size_t __right_start =
std::max(__left_len, __begin);
00944
if (!_S_apply_to_pieces(__c, __right,
00945 __right_start - __left_len,
00946 __end - __left_len))
00947
return false;
00948 }
00949 }
00950
return true;
00951
case _Rope_constants::_S_leaf:
00952 {
00953 _RopeLeaf* __l = (_RopeLeaf*)__r;
00954
return __c(__l->_M_data + __begin, __end - __begin);
00955 }
00956
case _Rope_constants::_S_function:
00957
case _Rope_constants::_S_substringfn:
00958 {
00959 _RopeFunction* __f = (_RopeFunction*)__r;
00960 size_t __len = __end - __begin;
00961
bool __result;
00962 _CharT* __buffer =
00963 (_CharT*)_Alloc().allocate(__len *
sizeof(_CharT));
00964
try
00965 {
00966 (*(__f->_M_fn))(__begin, __len, __buffer);
00967 __result = __c(__buffer, __len);
00968 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
00969 }
00970
catch(...)
00971 {
00972 _Alloc().deallocate(__buffer, __len *
sizeof(_CharT));
00973 __throw_exception_again;
00974 }
00975
return __result;
00976 }
00977
default:
00978
return false;
00979 }
00980 }
00981
00982
template<
class _CharT,
class _Traits>
00983
inline void
00984 _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
00985 {
00986
char __f = __o.fill();
00987 size_t __i;
00988
00989
for (__i = 0; __i < __n; __i++)
00990 __o.put(__f);
00991 }
00992
00993
00994
template <
class _CharT>
00995
inline bool
00996 _Rope_is_simple(_CharT*)
00997 {
return false; }
00998
00999
inline bool
01000 _Rope_is_simple(
char*)
01001 {
return true; }
01002
01003
inline bool
01004 _Rope_is_simple(
wchar_t*)
01005 {
return true; }
01006
01007
template<
class _CharT,
class _Traits,
class _Alloc>
01008 basic_ostream<_CharT, _Traits>&
01009 operator<<(basic_ostream<_CharT, _Traits>& __o,
01010
const rope<_CharT, _Alloc>& __r)
01011 {
01012 size_t __w = __o.width();
01013
bool __left = bool(__o.flags() & std::ios::left);
01014 size_t __pad_len;
01015 size_t __rope_len = __r.size();
01016 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
01017
bool __is_simple = _Rope_is_simple((_CharT*)0);
01018
01019
if (__rope_len < __w)
01020 __pad_len = __w - __rope_len;
01021
else
01022 __pad_len = 0;
01023
01024
if (!__is_simple)
01025 __o.width(__w / __rope_len);
01026
try
01027 {
01028
if (__is_simple && !__left && __pad_len > 0)
01029 _Rope_fill(__o, __pad_len);
01030 __r.apply_to_pieces(0, __r.size(), __c);
01031
if (__is_simple && __left && __pad_len > 0)
01032 _Rope_fill(__o, __pad_len);
01033
if (!__is_simple)
01034 __o.width(__w);
01035 }
01036
catch(...)
01037 {
01038
if (!__is_simple)
01039 __o.width(__w);
01040 __throw_exception_again;
01041 }
01042
return __o;
01043 }
01044
01045
template <
class _CharT,
class _Alloc>
01046 _CharT*
01047 rope<_CharT, _Alloc>::
01048 _S_flatten(_RopeRep* __r, size_t __start, size_t __len,
01049 _CharT* __buffer)
01050 {
01051 _Rope_flatten_char_consumer<_CharT> __c(__buffer);
01052 _S_apply_to_pieces(__c, __r, __start, __start + __len);
01053
return(__buffer + __len);
01054 }
01055
01056
template <
class _CharT,
class _Alloc>
01057 size_t
01058
rope<_CharT, _Alloc>::
01059
find(_CharT __pattern, size_t __start)
const
01060
{
01061 _Rope_find_char_char_consumer<_CharT> __c(__pattern);
01062 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
01063 size_type __result_pos = __start + __c._M_count;
01064
#ifndef __STL_OLD_ROPE_SEMANTICS
01065
if (__result_pos == size())
01066 __result_pos = npos;
01067
#endif
01068
return __result_pos;
01069 }
01070
01071
template <
class _CharT,
class _Alloc>
01072 _CharT*
01073 rope<_CharT, _Alloc>::
01074 _S_flatten(_RopeRep* __r, _CharT* __buffer)
01075 {
01076
if (0 == __r)
01077
return __buffer;
01078
switch(__r->_M_tag)
01079 {
01080
case _Rope_constants::_S_concat:
01081 {
01082 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01083 _RopeRep* __left = __c->_M_left;
01084 _RopeRep* __right = __c->_M_right;
01085 _CharT* __rest = _S_flatten(__left, __buffer);
01086
return _S_flatten(__right, __rest);
01087 }
01088
case _Rope_constants::_S_leaf:
01089 {
01090 _RopeLeaf* __l = (_RopeLeaf*)__r;
01091
return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
01092 }
01093
case _Rope_constants::_S_function:
01094
case _Rope_constants::_S_substringfn:
01095
01096
01097 {
01098 _RopeFunction* __f = (_RopeFunction*)__r;
01099 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
01100
return __buffer + __f->_M_size;
01101 }
01102
default:
01103
return 0;
01104 }
01105 }
01106
01107
01108
template <
class _CharT,
class _Alloc>
01109
void
01110 rope<_CharT, _Alloc>::
01111 _S_dump(_RopeRep* __r,
int __indent)
01112 {
01113
for (
int __i = 0; __i < __indent; __i++)
01114 putchar(
' ');
01115
if (0 == __r)
01116 {
01117 printf(
"NULL\n");
01118
return;
01119 }
01120
if (_Rope_constants::_S_concat == __r->_M_tag)
01121 {
01122 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01123 _RopeRep* __left = __c->_M_left;
01124 _RopeRep* __right = __c->_M_right;
01125
01126
#ifdef __GC
01127
printf(
"Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
01128 __r, __r->_M_depth, __r->_M_size,
01129 __r->_M_is_balanced?
"" :
"not");
01130
#else
01131
printf(
"Concatenation %p (rc = %ld, depth = %d, "
01132
"len = %ld, %s balanced)\n",
01133 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
01134 __r->_M_is_balanced?
"" :
"not");
01135
#endif
01136
_S_dump(__left, __indent + 2);
01137 _S_dump(__right, __indent + 2);
01138
return;
01139 }
01140
else
01141 {
01142
char* __kind;
01143
01144
switch (__r->_M_tag)
01145 {
01146
case _Rope_constants::_S_leaf:
01147 __kind =
"Leaf";
01148
break;
01149
case _Rope_constants::_S_function:
01150 __kind =
"Function";
01151
break;
01152
case _Rope_constants::_S_substringfn:
01153 __kind =
"Function representing substring";
01154
break;
01155
default:
01156 __kind =
"(corrupted kind field!)";
01157 }
01158
#ifdef __GC
01159
printf(
"%s %p (depth = %d, len = %ld) ",
01160 __kind, __r, __r->_M_depth, __r->_M_size);
01161
#else
01162
printf(
"%s %p (rc = %ld, depth = %d, len = %ld) ",
01163 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
01164
#endif
01165
if (_S_is_one_byte_char_type((_CharT*)0))
01166 {
01167
const int __max_len = 40;
01168 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
01169 _CharT __buffer[__max_len + 1];
01170
bool __too_big = __r->_M_size > __prefix->_M_size;
01171
01172 _S_flatten(__prefix, __buffer);
01173 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
01174 printf(
"%s%s\n", (
char*)__buffer,
01175 __too_big?
"...\n" :
"\n");
01176 }
01177
else
01178 printf(
"\n");
01179 }
01180 }
01181
01182
template <
class _CharT,
class _Alloc>
01183
const unsigned long
01184 rope<_CharT, _Alloc>::
01185 _S_min_len[_Rope_constants::_S_max_rope_depth + 1] = {
01186 1, 2, 3, 5, 8, 13, 21,
01187 34, 55, 89, 144, 233, 377,
01188 610, 987, 1597, 2584, 4181,
01189 6765, 10946, 17711, 28657, 46368,
01190 75025, 121393, 196418, 317811,
01191 514229, 832040, 1346269, 2178309,
01192 3524578, 5702887, 9227465, 14930352,
01193 24157817, 39088169, 63245986, 102334155,
01194 165580141, 267914296, 433494437,
01195 701408733, 1134903170, 1836311903,
01196 2971215073u };
01197
01198
01199
template <
class _CharT,
class _Alloc>
01200
typename rope<_CharT, _Alloc>::_RopeRep*
01201 rope<_CharT, _Alloc>::
01202 _S_balance(_RopeRep* __r)
01203 {
01204 _RopeRep* __forest[_Rope_constants::_S_max_rope_depth + 1];
01205 _RopeRep* __result = 0;
01206
int __i;
01207
01208
01209
01210
01211
01212
01213
for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i)
01214 __forest[__i] = 0;
01215
try
01216 {
01217 _S_add_to_forest(__r, __forest);
01218
for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i)
01219
if (0 != __forest[__i])
01220 {
01221
#ifndef __GC
01222
_Self_destruct_ptr __old(__result);
01223
#endif
01224
__result = _S_concat(__forest[__i], __result);
01225 __forest[__i]->_M_unref_nonnil();
01226
#if !defined(__GC) && defined(__EXCEPTIONS)
01227
__forest[__i] = 0;
01228
#endif
01229
}
01230 }
01231
catch(...)
01232 {
01233
for(__i = 0; __i <= _Rope_constants::_S_max_rope_depth; __i++)
01234 _S_unref(__forest[__i]);
01235 __throw_exception_again;
01236 }
01237
01238
if (__result->_M_depth > _Rope_constants::_S_max_rope_depth)
01239 __throw_length_error(__N(
"rope::_S_balance"));
01240
return(__result);
01241 }
01242
01243
template <
class _CharT,
class _Alloc>
01244
void
01245 rope<_CharT, _Alloc>::
01246 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
01247 {
01248
if (__r->_M_is_balanced)
01249 {
01250 _S_add_leaf_to_forest(__r, __forest);
01251
return;
01252 }
01253
01254 {
01255 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01256
01257 _S_add_to_forest(__c->_M_left, __forest);
01258 _S_add_to_forest(__c->_M_right, __forest);
01259 }
01260 }
01261
01262
01263
template <
class _CharT,
class _Alloc>
01264
void
01265 rope<_CharT, _Alloc>::
01266 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
01267 {
01268 _RopeRep* __insertee;
01269 _RopeRep* __too_tiny = 0;
01270
int __i;
01271 size_t __s = __r->_M_size;
01272
01273
for (__i = 0; __s >= _S_min_len[__i+1]; ++__i)
01274 {
01275
if (0 != __forest[__i])
01276 {
01277
#ifndef __GC
01278
_Self_destruct_ptr __old(__too_tiny);
01279
#endif
01280
__too_tiny = _S_concat_and_set_balanced(__forest[__i],
01281 __too_tiny);
01282 __forest[__i]->_M_unref_nonnil();
01283 __forest[__i] = 0;
01284 }
01285 }
01286 {
01287
#ifndef __GC
01288
_Self_destruct_ptr __old(__too_tiny);
01289
#endif
01290
__insertee = _S_concat_and_set_balanced(__too_tiny, __r);
01291 }
01292
01293
01294
for (;; ++__i)
01295 {
01296
if (0 != __forest[__i])
01297 {
01298
#ifndef __GC
01299
_Self_destruct_ptr __old(__insertee);
01300
#endif
01301
__insertee = _S_concat_and_set_balanced(__forest[__i],
01302 __insertee);
01303 __forest[__i]->_M_unref_nonnil();
01304 __forest[__i] = 0;
01305 }
01306
if (__i == _Rope_constants::_S_max_rope_depth
01307 || __insertee->_M_size < _S_min_len[__i+1])
01308 {
01309 __forest[__i] = __insertee;
01310
01311
return;
01312 }
01313 }
01314 }
01315
01316
template <
class _CharT,
class _Alloc>
01317 _CharT
01318 rope<_CharT, _Alloc>::
01319 _S_fetch(_RopeRep* __r, size_type __i)
01320 {
01321 __GC_CONST _CharT* __cstr = __r->_M_c_string;
01322
01323
if (0 != __cstr)
01324
return __cstr[__i];
01325
for(;;)
01326 {
01327
switch(__r->_M_tag)
01328 {
01329
case _Rope_constants::_S_concat:
01330 {
01331 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01332 _RopeRep* __left = __c->_M_left;
01333 size_t __left_len = __left->_M_size;
01334
01335
if (__i >= __left_len)
01336 {
01337 __i -= __left_len;
01338 __r = __c->_M_right;
01339 }
01340
else
01341 __r = __left;
01342 }
01343
break;
01344
case _Rope_constants::_S_leaf:
01345 {
01346 _RopeLeaf* __l = (_RopeLeaf*)__r;
01347
return __l->_M_data[__i];
01348 }
01349
case _Rope_constants::_S_function:
01350
case _Rope_constants::_S_substringfn:
01351 {
01352 _RopeFunction* __f = (_RopeFunction*)__r;
01353 _CharT __result;
01354
01355 (*(__f->_M_fn))(__i, 1, &__result);
01356
return __result;
01357 }
01358 }
01359 }
01360 }
01361
01362
#ifndef __GC
01363
01364
01365
template <
class _CharT,
class _Alloc>
01366 _CharT*
01367 rope<_CharT, _Alloc>::
01368 _S_fetch_ptr(_RopeRep* __r, size_type __i)
01369 {
01370 _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth];
01371 size_t __csptr = 0;
01372
01373
for(;;)
01374 {
01375
if (__r->_M_ref_count > 1)
01376
return 0;
01377
switch(__r->_M_tag)
01378 {
01379
case _Rope_constants::_S_concat:
01380 {
01381 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01382 _RopeRep* __left = __c->_M_left;
01383 size_t __left_len = __left->_M_size;
01384
01385
if (__c->_M_c_string != 0)
01386 __clrstack[__csptr++] = __c;
01387
if (__i >= __left_len)
01388 {
01389 __i -= __left_len;
01390 __r = __c->_M_right;
01391 }
01392
else
01393 __r = __left;
01394 }
01395
break;
01396
case _Rope_constants::_S_leaf:
01397 {
01398 _RopeLeaf* __l = (_RopeLeaf*)__r;
01399
if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
01400 __clrstack[__csptr++] = __l;
01401
while (__csptr > 0)
01402 {
01403 -- __csptr;
01404 _RopeRep* __d = __clrstack[__csptr];
01405 __d->_M_free_c_string();
01406 __d->_M_c_string = 0;
01407 }
01408
return __l->_M_data + __i;
01409 }
01410
case _Rope_constants::_S_function:
01411
case _Rope_constants::_S_substringfn:
01412
return 0;
01413 }
01414 }
01415 }
01416
#endif
01417
01418
01419
01420
01421
01422
template <
class _CharT,
class _Alloc>
01423
int
01424 rope<_CharT, _Alloc>::
01425 _S_compare (
const _RopeRep* __left,
const _RopeRep* __right)
01426 {
01427 size_t __left_len;
01428 size_t __right_len;
01429
01430
if (0 == __right)
01431
return 0 != __left;
01432
if (0 == __left)
01433
return -1;
01434 __left_len = __left->_M_size;
01435 __right_len = __right->_M_size;
01436
if (_Rope_constants::_S_leaf == __left->_M_tag)
01437 {
01438 _RopeLeaf* __l = (_RopeLeaf*) __left;
01439
if (_Rope_constants::_S_leaf == __right->_M_tag)
01440 {
01441 _RopeLeaf* __r = (_RopeLeaf*) __right;
01442
return lexicographical_compare_3way(__l->_M_data,
01443 __l->_M_data + __left_len,
01444 __r->_M_data, __r->_M_data
01445 + __right_len);
01446 }
01447
else
01448 {
01449 const_iterator __rstart(__right, 0);
01450 const_iterator __rend(__right, __right_len);
01451
return lexicographical_compare_3way(__l->_M_data, __l->_M_data
01452 + __left_len,
01453 __rstart, __rend);
01454 }
01455 }
01456
else
01457 {
01458 const_iterator __lstart(__left, 0);
01459 const_iterator __lend(__left, __left_len);
01460
if (_Rope_constants::_S_leaf == __right->_M_tag)
01461 {
01462 _RopeLeaf* __r = (_RopeLeaf*) __right;
01463
return lexicographical_compare_3way(__lstart, __lend,
01464 __r->_M_data, __r->_M_data
01465 + __right_len);
01466 }
01467
else
01468 {
01469 const_iterator __rstart(__right, 0);
01470 const_iterator __rend(__right, __right_len);
01471
return lexicographical_compare_3way(__lstart, __lend,
01472 __rstart, __rend);
01473 }
01474 }
01475 }
01476
01477
01478
template <
class _CharT,
class _Alloc>
01479 _Rope_char_ref_proxy<_CharT, _Alloc>&
01480 _Rope_char_ref_proxy<_CharT, _Alloc>::
01481 operator=(_CharT __c)
01482 {
01483 _RopeRep* __old = _M_root->_M_tree_ptr;
01484
#ifndef __GC
01485
01486
01487 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
01488
if (0 != __ptr)
01489 {
01490 *__ptr = __c;
01491
return *
this;
01492 }
01493
#endif
01494
_Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
01495 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
01496 __old->_M_size));
01497 _Self_destruct_ptr __result_left(_My_rope::
01498 _S_destr_concat_char_iter(__left,
01499 &__c, 1));
01500
01501 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
01502
#ifndef __GC
01503
_RopeRep::_S_unref(__old);
01504
#endif
01505
_M_root->_M_tree_ptr = __result;
01506
return *
this;
01507 }
01508
01509
template <
class _CharT,
class _Alloc>
01510
inline _Rope_char_ref_proxy<_CharT, _Alloc>::
01511 operator _CharT()
const
01512
{
01513
if (_M_current_valid)
01514
return _M_current;
01515
else
01516
return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
01517 }
01518
01519
template <
class _CharT,
class _Alloc>
01520 _Rope_char_ptr_proxy<_CharT, _Alloc>
01521 _Rope_char_ref_proxy<_CharT, _Alloc>::
01522 operator&()
const
01523
{
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
01524
01525
template <
class _CharT,
class _Alloc>
01526 rope<_CharT, _Alloc>::
01527 rope(size_t __n, _CharT __c,
const allocator_type& __a)
01528 : _Base(__a)
01529 {
01530 rope<_CharT,_Alloc> __result;
01531
const size_t __exponentiate_threshold = 32;
01532 size_t __exponent;
01533 size_t __rest;
01534 _CharT* __rest_buffer;
01535 _RopeRep* __remainder;
01536 rope<_CharT, _Alloc> __remainder_rope;
01537
01538
if (0 == __n)
01539
return;
01540
01541 __exponent = __n / __exponentiate_threshold;
01542 __rest = __n % __exponentiate_threshold;
01543
if (0 == __rest)
01544 __remainder = 0;
01545
else
01546 {
01547 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
01548 __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
01549 get_allocator());
01550 _S_cond_store_eos(__rest_buffer[__rest]);
01551
try
01552 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); }
01553
catch(...)
01554 {
01555 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a);
01556 __throw_exception_again;
01557 }
01558 }
01559 __remainder_rope._M_tree_ptr = __remainder;
01560
if (__exponent != 0)
01561 {
01562 _CharT* __base_buffer =
01563 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
01564 _RopeLeaf* __base_leaf;
01565 rope __base_rope;
01566 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
01567 get_allocator());
01568 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
01569
try
01570 {
01571 __base_leaf = _S_new_RopeLeaf(__base_buffer,
01572 __exponentiate_threshold, __a);
01573 }
01574
catch(...)
01575 {
01576 _RopeRep::__STL_FREE_STRING(__base_buffer,
01577 __exponentiate_threshold, __a);
01578 __throw_exception_again;
01579 }
01580 __base_rope._M_tree_ptr = __base_leaf;
01581
if (1 == __exponent)
01582 __result = __base_rope;
01583
else
01584 __result = power(__base_rope, __exponent,
01585 _Rope_Concat_fn<_CharT, _Alloc>());
01586
01587
if (0 != __remainder)
01588 __result += __remainder_rope;
01589 }
01590
else
01591 __result = __remainder_rope;
01592
01593 this->_M_tree_ptr = __result._M_tree_ptr;
01594 this->_M_tree_ptr->_M_ref_nonnil();
01595 }
01596
01597
template<
class _CharT,
class _Alloc>
01598 _CharT
01599 rope<_CharT, _Alloc>::_S_empty_c_str[1];
01600
01601
template<
class _CharT,
class _Alloc>
01602
const _CharT*
01603 rope<_CharT, _Alloc>::
01604 c_str()
const
01605
{
01606
if (0 == this->_M_tree_ptr)
01607 {
01608 _S_empty_c_str[0] = _S_eos((_CharT*)0);
01609
01610
return _S_empty_c_str;
01611 }
01612 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
01613 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
01614
if (0 == __result)
01615 {
01616 size_t __s = size();
01617 __result = this->_Data_allocate(__s + 1);
01618 _S_flatten(this->_M_tree_ptr, __result);
01619 __result[__s] = _S_eos((_CharT*)0);
01620 this->_M_tree_ptr->_M_c_string = __result;
01621 }
01622 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
01623
return(__result);
01624 }
01625
01626
template<
class _CharT,
class _Alloc>
01627
const _CharT* rope<_CharT, _Alloc>::
01628 replace_with_c_str()
01629 {
01630
if (0 == this->_M_tree_ptr)
01631 {
01632 _S_empty_c_str[0] = _S_eos((_CharT*)0);
01633
return _S_empty_c_str;
01634 }
01635 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
01636
if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag
01637 && 0 != __old_c_string)
01638
return(__old_c_string);
01639 size_t __s = size();
01640 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
01641 _S_flatten(this->_M_tree_ptr, __result);
01642 __result[__s] = _S_eos((_CharT*)0);
01643 this->_M_tree_ptr->_M_unref_nonnil();
01644 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
01645 this->get_allocator());
01646
return(__result);
01647 }
01648
01649
01650
01651
template<
class _Rope_iterator>
01652
void
01653 _Rope_rotate(_Rope_iterator __first,
01654 _Rope_iterator __middle,
01655 _Rope_iterator __last)
01656 {
01657
typedef typename _Rope_iterator::value_type _CharT;
01658
typedef typename _Rope_iterator::_allocator_type _Alloc;
01659
01660 rope<_CharT, _Alloc>& __r(__first.container());
01661 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
01662 rope<_CharT, _Alloc> __suffix =
01663 __r.substr(__last.index(), __r.size() - __last.index());
01664 rope<_CharT, _Alloc> __part1 =
01665 __r.substr(__middle.index(), __last.index() - __middle.index());
01666 rope<_CharT, _Alloc> __part2 =
01667 __r.substr(__first.index(), __middle.index() - __first.index());
01668 __r = __prefix;
01669 __r += __part1;
01670 __r += __part2;
01671 __r += __suffix;
01672 }
01673
01674
#if !defined(__GNUC__)
01675
01676
inline void
01677
rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first,
01678 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle,
01679 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last)
01680 { _Rope_rotate(__first, __middle, __last); }
01681
#endif
01682
01683
# if 0
01684
01685
01686
01687
01688
01689
01690
01691
inline void
01692
rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first,
01693 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle,
01694 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last)
01695 { _Rope_rotate(__first, __middle, __last); }
01696
# endif
01697
01698 }
01699
01700
01701
01702
01703