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