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