ropeimpl.h

00001 /*
00002  * Copyright (c) 1997
00003  * Silicon Graphics Computer Systems, Inc.
00004  *
00005  * Permission to use, copy, modify, distribute and sell this software
00006  * and its documentation for any purpose is hereby granted without fee,
00007  * provided that the above copyright notice appear in all copies and
00008  * that both that copyright notice and this permission notice appear
00009  * in supporting documentation.  Silicon Graphics makes no
00010  * representations about the suitability of this software for any
00011  * purpose.  It is provided "as is" without express or implied warranty.
00012  */
00013 
00014 /* NOTE: This is an internal header file, included by other STL headers.
00015  *   You should not attempt to use it directly.
00016  */
00017 
00018 #ifndef UNDER_CE
00019 # include <stdio.h>     
00020 #ifdef __STL_USE_NEW_IOSTREAMS 
00021 # include <iostream>
00022 #else /* __STL_USE_NEW_IOSTREAMS */
00023 # include <iostream.h>
00024 #endif /* __STL_USE_NEW_IOSTREAMS */
00025 #else
00026 #include <wce_defs.h>
00027 #endif /* UNDER_CE */
00028 
00029 #ifdef __STL_USE_EXCEPTIONS
00030 # include <stdexcept>
00031 #endif
00032 
00033 __STL_BEGIN_NAMESPACE
00034 
00035 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
00036 #pragma set woff 1174
00037 #endif
00038 
00039 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
00040 // if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
00041 // Results in a valid buf_ptr if the iterator can be legitimately
00042 // dereferenced.
00043 template <class _CharT, class _Alloc>
00044 void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( 
00045   _Rope_iterator_base<_CharT,_Alloc>& __x)
00046 {
00047     const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
00048     size_t __leaf_pos = __x._M_leaf_pos;
00049     size_t __pos = __x._M_current_pos;
00050 
00051     switch(__leaf->_M_tag) {
00052         case _RopeRep::_S_leaf:
00053             __x._M_buf_start = 
00054               ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
00055             __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
00056             __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
00057             break;
00058         case _RopeRep::_S_function:
00059         case _RopeRep::_S_substringfn:
00060             {
00061                 size_t __len = _S_iterator_buf_len;
00062                 size_t __buf_start_pos = __leaf_pos;
00063                 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
00064                 char_producer<_CharT>* __fn =
00065                         ((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;
00066 
00067                 if (__buf_start_pos + __len <= __pos) {
00068                     __buf_start_pos = __pos - __len/4;
00069                     if (__buf_start_pos + __len > __leaf_end) {
00070                         __buf_start_pos = __leaf_end - __len;
00071                     }
00072                 }
00073                 if (__buf_start_pos + __len > __leaf_end) {
00074                     __len = __leaf_end - __buf_start_pos;
00075                 }
00076                 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
00077                 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
00078                 __x._M_buf_start = __x._M_tmp_buf;
00079                 __x._M_buf_end = __x._M_tmp_buf + __len;
00080             }
00081             break;
00082         default:
00083             __stl_assert(0);
00084     }
00085 }
00086 
00087 // Set path and buffer inside a rope iterator.  We assume that 
00088 // pos and root are already set.
00089 template <class _CharT, class _Alloc>
00090 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
00091 (_Rope_iterator_base<_CharT,_Alloc>& __x)
00092 {
00093     const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
00094     const _RopeRep* __curr_rope;
00095     int __curr_depth = -1;  /* index into path    */
00096     size_t __curr_start_pos = 0;
00097     size_t __pos = __x._M_current_pos;
00098     unsigned char __dirns = 0; // Bit vector marking right turns in the path
00099 
00100     __stl_assert(__pos <= __x._M_root->_M_size);
00101     if (__pos >= __x._M_root->_M_size) {
00102         __x._M_buf_ptr = 0;
00103         return;
00104     }
00105     __curr_rope = __x._M_root;
00106     if (0 != __curr_rope->_M_c_string) {
00107         /* Treat the root as a leaf. */
00108         __x._M_buf_start = __curr_rope->_M_c_string;
00109         __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
00110         __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
00111         __x._M_path_end[0] = __curr_rope;
00112         __x._M_leaf_index = 0;
00113         __x._M_leaf_pos = 0;
00114         return;
00115     }
00116     for(;;) {
00117         ++__curr_depth;
00118         __stl_assert(__curr_depth <= _RopeRep::_S_max_rope_depth);
00119         __path[__curr_depth] = __curr_rope;
00120         switch(__curr_rope->_M_tag) {
00121           case _RopeRep::_S_leaf:
00122           case _RopeRep::_S_function:
00123           case _RopeRep::_S_substringfn:
00124             __x._M_leaf_pos = __curr_start_pos;
00125             goto done;
00126           case _RopeRep::_S_concat:
00127             {
00128                 _Rope_RopeConcatenation<_CharT,_Alloc>* __c =
00129                         (_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
00130                 _RopeRep* __left = __c->_M_left;
00131                 size_t __left_len = __left->_M_size;
00132                 
00133                 __dirns <<= 1;
00134                 if (__pos >= __curr_start_pos + __left_len) {
00135                     __dirns |= 1;
00136                     __curr_rope = __c->_M_right;
00137                     __curr_start_pos += __left_len;
00138                 } else {
00139                     __curr_rope = __left;
00140                 }
00141             }
00142             break;
00143         }
00144     }
00145   done:
00146     // Copy last section of path into _M_path_end.
00147       {
00148         int __i = -1;
00149         int __j = __curr_depth + 1 - _S_path_cache_len;
00150 
00151         if (__j < 0) __j = 0;
00152         while (__j <= __curr_depth) {
00153             __x._M_path_end[++__i] = __path[__j++];
00154         }
00155         __x._M_leaf_index = __i;
00156       }
00157       __x._M_path_directions = __dirns;
00158       _S_setbuf(__x);
00159 }
00160 
00161 // Specialized version of the above.  Assumes that
00162 // the path cache is valid for the previous position.
00163 template <class _CharT, class _Alloc>
00164 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
00165 (_Rope_iterator_base<_CharT,_Alloc>& __x)
00166 {
00167     int __current_index = __x._M_leaf_index;
00168     const _RopeRep* __current_node = __x._M_path_end[__current_index];
00169     size_t __len = __current_node->_M_size;
00170     size_t __node_start_pos = __x._M_leaf_pos;
00171     unsigned char __dirns = __x._M_path_directions;
00172     _Rope_RopeConcatenation<_CharT,_Alloc>* __c;
00173 
00174     __stl_assert(__x._M_current_pos <= __x._M_root->_M_size);
00175     if (__x._M_current_pos - __node_start_pos < __len) {
00176         /* More stuff in this leaf, we just didn't cache it. */
00177         _S_setbuf(__x);
00178         return;
00179     }
00180     __stl_assert(__node_start_pos + __len == __x._M_current_pos);
00181     //  node_start_pos is starting position of last_node.
00182     while (--__current_index >= 0) {
00183         if (!(__dirns & 1) /* Path turned left */) 
00184           break;
00185         __current_node = __x._M_path_end[__current_index];
00186         __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
00187         // Otherwise we were in the right child.  Thus we should pop
00188         // the concatenation node.
00189         __node_start_pos -= __c->_M_left->_M_size;
00190         __dirns >>= 1;
00191     }
00192     if (__current_index < 0) {
00193         // We underflowed the cache. Punt.
00194         _S_setcache(__x);
00195         return;
00196     }
00197     __current_node = __x._M_path_end[__current_index];
00198     __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
00199     // current_node is a concatenation node.  We are positioned on the first
00200     // character in its right child.
00201     // node_start_pos is starting position of current_node.
00202     __node_start_pos += __c->_M_left->_M_size;
00203     __current_node = __c->_M_right;
00204     __x._M_path_end[++__current_index] = __current_node;
00205     __dirns |= 1;
00206     while (_RopeRep::_S_concat == __current_node->_M_tag) {
00207         ++__current_index;
00208         if (_S_path_cache_len == __current_index) {
00209             int __i;
00210             for (__i = 0; __i < _S_path_cache_len-1; __i++) {
00211                 __x._M_path_end[__i] = __x._M_path_end[__i+1];
00212             }
00213             --__current_index;
00214         }
00215         __current_node =
00216             ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
00217         __x._M_path_end[__current_index] = __current_node;
00218         __dirns <<= 1;
00219         // node_start_pos is unchanged.
00220     }
00221     __x._M_leaf_index = __current_index;
00222     __x._M_leaf_pos = __node_start_pos;
00223     __x._M_path_directions = __dirns;
00224     _S_setbuf(__x);
00225 }
00226 
00227 template <class _CharT, class _Alloc>
00228 void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
00229     _M_current_pos += __n;
00230     if (0 != _M_buf_ptr) {
00231         size_t __chars_left = _M_buf_end - _M_buf_ptr;
00232         if (__chars_left > __n) {
00233             _M_buf_ptr += __n;
00234         } else if (__chars_left == __n) {
00235             _M_buf_ptr += __n;
00236             _S_setcache_for_incr(*this);
00237         } else {
00238             _M_buf_ptr = 0;
00239         }
00240     }
00241 }
00242 
00243 template <class _CharT, class _Alloc>
00244 void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
00245     if (0 != _M_buf_ptr) {
00246         size_t __chars_left = _M_buf_ptr - _M_buf_start;
00247         if (__chars_left >= __n) {
00248             _M_buf_ptr -= __n;
00249         } else {
00250             _M_buf_ptr = 0;
00251         }
00252     }
00253     _M_current_pos -= __n;
00254 }
00255 
00256 template <class _CharT, class _Alloc>
00257 void _Rope_iterator<_CharT,_Alloc>::_M_check() {
00258     if (_M_root_rope->_M_tree_ptr != _M_root) {
00259         // _Rope was modified.  Get things fixed up.
00260         _RopeRep::_S_unref(_M_root);
00261         _M_root = _M_root_rope->_M_tree_ptr;
00262         _RopeRep::_S_ref(_M_root);
00263         _M_buf_ptr = 0;
00264     }
00265 }
00266 
00267 template <class _CharT, class _Alloc>
00268 inline 
00269 _Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator(
00270   const _Rope_iterator<_CharT,_Alloc>& __x)
00271 : _Rope_iterator_base<_CharT,_Alloc>(__x) 
00272 { }
00273 
00274 template <class _CharT, class _Alloc>
00275 inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator(
00276   rope<_CharT,_Alloc>& __r, size_t __pos)
00277 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 
00278   _M_root_rope(&__r)
00279 {
00280     _RopeRep::_S_ref(_M_root);
00281 }
00282 
00283 template <class _CharT, class _Alloc>
00284 inline size_t 
00285 rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s)
00286 {
00287     const _CharT* __p = __s;
00288 
00289     while (!_S_is0(*__p)) { ++__p; }
00290     return (__p - __s);
00291 }
00292 
00293 
00294 #ifndef __GC
00295 
00296 template <class _CharT, class _Alloc>
00297 inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string()
00298 {
00299     _CharT* __cstr = _M_c_string;
00300     if (0 != __cstr) {
00301         size_t __size = _M_size + 1;
00302         destroy(__cstr, __cstr + __size);
00303         _Data_deallocate(__cstr, __size);
00304     }
00305 }
00306 
00307 
00308 template <class _CharT, class _Alloc>
00309 #ifdef __STL_USE_STD_ALLOCATORS
00310   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
00311                                                            size_t __n,
00312                                                            allocator_type __a)
00313 #else
00314   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
00315                                                            size_t __n)
00316 #endif
00317 {
00318     if (!_S_is_basic_char_type((_CharT*)0)) {
00319         destroy(__s, __s + __n);
00320     }
00321 //  This has to be a static member, so this gets a bit messy
00322 #   ifdef __STL_USE_STD_ALLOCATORS
00323         __a.deallocate(
00324             __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
00325 #   else
00326         _Data_deallocate(
00327             __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
00328 #   endif
00329 }
00330 
00331 
00332 //  There are several reasons for not doing this with virtual destructors
00333 //  and a class specific delete operator:
00334 //  - A class specific delete operator can't easily get access to
00335 //    allocator instances if we need them.
00336 //  - Any virtual function would need a 4 or byte vtable pointer;
00337 //    this only requires a one byte tag per object.
00338 template <class _CharT, class _Alloc>
00339 void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
00340 {
00341     switch(_M_tag) {
00342         case _S_leaf:
00343             {
00344                 _Rope_RopeLeaf<_CharT,_Alloc>* __l
00345                         = (_Rope_RopeLeaf<_CharT,_Alloc>*)this;
00346                 __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
00347                 _L_deallocate(__l, 1);
00348                 break;
00349             }
00350         case _S_concat:
00351             {
00352                 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
00353                     = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;
00354                 __c->_Rope_RopeConcatenation<_CharT,_Alloc>::
                       ~_Rope_RopeConcatenation();
00355                 _C_deallocate(__c, 1);
00356                 break;
00357             }
00358         case _S_function:
00359             {
00360                 _Rope_RopeFunction<_CharT,_Alloc>* __f
00361                     = (_Rope_RopeFunction<_CharT,_Alloc>*)this;
00362                 __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();
00363                 _F_deallocate(__f, 1);
00364                 break;
00365             }
00366         case _S_substringfn:
00367             {
00368                 _Rope_RopeSubstring<_CharT,_Alloc>* __ss =
00369                         (_Rope_RopeSubstring<_CharT,_Alloc>*)this;
00370                 __ss->_Rope_RopeSubstring<_CharT,_Alloc>::
                        ~_Rope_RopeSubstring();
00371                 _S_deallocate(__ss, 1);
00372                 break;
00373             }
00374     }
00375 }
00376 #else
00377 
00378 template <class _CharT, class _Alloc>
00379 #ifdef __STL_USE_STD_ALLOCATORS
00380   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
00381                 (const _CharT*, size_t, allocator_type)
00382 #else
00383   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
00384                 (const _CharT*, size_t)
00385 #endif
00386 {}
00387 
00388 #endif
00389 
00390 
00391 // Concatenate a C string onto a leaf rope by copying the rope data.
00392 // Used for short ropes.
00393 template <class _CharT, class _Alloc>
00394 rope<_CharT,_Alloc>::_RopeLeaf*
00395 rope<_CharT,_Alloc>::_S_leaf_concat_char_iter
00396                 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
00397 {
00398     size_t __old_len = __r->_M_size;
00399     _CharT* __new_data = (_CharT*)
00400         _Data_allocate(_S_rounded_up_size(__old_len + __len));
00401     _RopeLeaf* __result;
00402     
00403     uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
00404     uninitialized_copy_n(__iter, __len, __new_data + __old_len);
00405     _S_cond_store_eos(__new_data[__old_len + __len]);
00406     __STL_TRY {
00407         __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
00408                                    __r->get_allocator());
00409     }
00410     __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
00411                                              __r->get_allocator()));
00412     return __result;
00413 }
00414 
00415 #ifndef __GC
00416 // As above, but it's OK to clobber original if refcount is 1
00417 template <class _CharT, class _Alloc>
00418 rope<_CharT,_Alloc>::_RopeLeaf*
00419 rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter
00420                 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
00421 {
00422     __stl_assert(__r->_M_ref_count >= 1);
00423     if (__r->_M_ref_count > 1)
00424       return _S_leaf_concat_char_iter(__r, __iter, __len);
00425     size_t __old_len = __r->_M_size;
00426     if (_S_allocated_capacity(__old_len) >= __old_len + __len) {
00427         // The space has been partially initialized for the standard
00428         // character types.  But that doesn't matter for those types.
00429         uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
00430         if (_S_is_basic_char_type((_CharT*)0)) {
00431             _S_cond_store_eos(__r->_M_data[__old_len + __len]);
00432             __stl_assert(__r->_M_c_string == __r->_M_data);
00433         } else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
00434             __r->_M_free_c_string();
00435             __r->_M_c_string = 0;
00436         }
00437         __r->_M_size = __old_len + __len;
00438         __stl_assert(__r->_M_ref_count == 1);
00439         __r->_M_ref_count = 2;
00440         return __r;
00441     } else {
00442         _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
00443         __stl_assert(__result->_M_ref_count == 1);
00444         return __result;
00445     }
00446 }
00447 #endif
00448 
00449 // Assumes left and right are not 0.
00450 // Does not increment (nor decrement on exception) child reference counts.
00451 // Result has ref count 1.
00452 template <class _CharT, class _Alloc>
00453 rope<_CharT,_Alloc>::_RopeRep*
00454 rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)
00455 {
00456     _RopeConcatenation* __result =
00457       _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
00458     size_t __depth = __result->_M_depth;
00459     
00460 #   ifdef __STL_USE_STD_ALLOCATORS
00461       __stl_assert(__left->get_allocator() == __right->get_allocator());
00462 #   endif
00463     if (__depth > 20 && (__result->_M_size < 1000 ||
00464                          __depth > _RopeRep::_S_max_rope_depth)) {
00465         _RopeRep* __balanced;
00466       
00467         __STL_TRY {
00468            __balanced = _S_balance(__result);
00469 #          ifndef __GC
00470              if (__result != __balanced) {
00471                 __stl_assert(1 == __result->_M_ref_count
00472                              && 1 == __balanced->_M_ref_count);
00473              }
00474 #          endif
00475            __result->_M_unref_nonnil();
00476         }
00477         __STL_UNWIND((_C_deallocate(__result,1)));
00478                 // In case of exception, we need to deallocate
00479                 // otherwise dangling result node.  But caller
00480                 // still owns its children.  Thus unref is
00481                 // inappropriate.
00482         return __balanced;
00483     } else {
00484         return __result;
00485     }
00486 }
00487 
00488 template <class _CharT, class _Alloc>
00489 rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter
00490                 (_RopeRep* __r, const _CharT*__s, size_t __slen)
00491 {
00492     _RopeRep* __result;
00493     if (0 == __slen) {
00494         _S_ref(__r);
00495         return __r;
00496     }
00497     if (0 == __r)
00498       return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00499                                               __r->get_allocator());
00500     if (_RopeRep::_S_leaf == __r->_M_tag && 
00501           __r->_M_size + __slen <= _S_copy_max) {
00502         __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
00503 #       ifndef __GC
00504           __stl_assert(1 == __result->_M_ref_count);
00505 #       endif
00506         return __result;
00507     }
00508     if (_RopeRep::_S_concat == __r->_M_tag
00509         && _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
00510         _RopeLeaf* __right = 
00511           (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
00512         if (__right->_M_size + __slen <= _S_copy_max) {
00513           _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
00514           _RopeRep* __nright = 
00515             _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
00516           __left->_M_ref_nonnil();
00517           __STL_TRY {
00518             __result = _S_tree_concat(__left, __nright);
00519           }
00520           __STL_UNWIND(_S_unref(__left); _S_unref(__nright));
00521 #         ifndef __GC
00522             __stl_assert(1 == __result->_M_ref_count);
00523 #         endif
00524           return __result;
00525         }
00526     }
00527     _RopeRep* __nright =
00528       __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00529     __STL_TRY {
00530       __r->_M_ref_nonnil();
00531       __result = _S_tree_concat(__r, __nright);
00532     }
00533     __STL_UNWIND(_S_unref(__r); _S_unref(__nright));
00534 #   ifndef __GC
00535       __stl_assert(1 == __result->_M_ref_count);
00536 #   endif
00537     return __result;
00538 }
00539 
00540 #ifndef __GC
00541 template <class _CharT, class _Alloc>
00542 rope<_CharT,_Alloc>::_RopeRep* 
00543 rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
00544   _RopeRep* __r, const _CharT* __s, size_t __slen)
00545 {
00546     _RopeRep* __result;
00547     if (0 == __r)
00548       return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
00549                                               __r->get_allocator());
00550     size_t __count = __r->_M_ref_count;
00551     size_t __orig_size = __r->_M_size;
00552     __stl_assert(__count >= 1);
00553     if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);
00554     if (0 == __slen) {
00555         __r->_M_ref_count = 2;      // One more than before
00556         return __r;
00557     }
00558     if (__orig_size + __slen <= _S_copy_max && 
00559           _RopeRep::_S_leaf == __r->_M_tag) {
00560         __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
00561         return __result;
00562     }
00563     if (_RopeRep::_S_concat == __r->_M_tag) {
00564         _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
00565         if (_RopeRep::_S_leaf == __right->_M_tag
00566             && __right->_M_size + __slen <= _S_copy_max) {
00567           _RopeRep* __new_right = 
00568             _S_destr_leaf_concat_char_iter(__right, __s, __slen);
00569           if (__right == __new_right) {
00570               __stl_assert(__new_right->_M_ref_count == 2);
00571               __new_right->_M_ref_count = 1;
00572           } else {
00573               __stl_assert(__new_right->_M_ref_count >= 1);
00574               __right->_M_unref_nonnil();
00575           }
00576           __stl_assert(__r->_M_ref_count == 1);
00577           __r->_M_ref_count = 2;    // One more than before.
00578           ((_RopeConcatenation*)__r)->_M_right = __new_right;
00579           __r->_M_size = __orig_size + __slen;
00580           if (0 != __r->_M_c_string) {
00581               __r->_M_free_c_string();
00582               __r->_M_c_string = 0;
00583           }
00584           return __r;
00585         }
00586     }
00587     _RopeRep* __right =
00588       __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
00589     __r->_M_ref_nonnil();
00590     __STL_TRY {
00591       __result = _S_tree_concat(__r, __right);
00592     }
00593     __STL_UNWIND(_S_unref(__r); _S_unref(__right))
00594     __stl_assert(1 == __result->_M_ref_count);
00595     return __result;
00596 }
00597 #endif /* !__GC */
00598 
00599 template <class _CharT, class _Alloc>
00600 rope<_CharT,_Alloc>::_RopeRep*
00601 rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right)
00602 {
00603     if (0 == __left) {
00604         _S_ref(__right);
00605         return __right;
00606     }
00607     if (0 == __right) {
00608         __left->_M_ref_nonnil();
00609         return __left;
00610     }
00611     if (_RopeRep::_S_leaf == __right->_M_tag) {
00612         if (_RopeRep::_S_leaf == __left->_M_tag) {
00613           if (__right->_M_size + __left->_M_size <= _S_copy_max) {
00614             return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
00615                                          ((_RopeLeaf*)__right)->_M_data,
00616                                          __right->_M_size);
00617           }
00618         } else if (_RopeRep::_S_concat == __left->_M_tag
00619                    && _RopeRep::_S_leaf ==
00620                       ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
00621           _RopeLeaf* __leftright =
00622                     (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 
00623           if (__leftright->_M_size + __right->_M_size <= _S_copy_max) {
00624             _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
00625             _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
00626                                            ((_RopeLeaf*)__right)->_M_data,
00627                                            __right->_M_size);
00628             __leftleft->_M_ref_nonnil();
00629             __STL_TRY {
00630               return(_S_tree_concat(__leftleft, __rest));
00631             }
00632             __STL_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
00633           }
00634         }
00635     }
00636     __left->_M_ref_nonnil();
00637     __right->_M_ref_nonnil();
00638     __STL_TRY {
00639       return(_S_tree_concat(__left, __right));
00640     }
00641     __STL_UNWIND(_S_unref(__left); _S_unref(__right));
00642 }
00643 
00644 template <class _CharT, class _Alloc>
00645 rope<_CharT,_Alloc>::_RopeRep*
00646 rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, 
00647                                size_t __start, size_t __endp1)
00648 {
00649     if (0 == __base) return 0;
00650     size_t __len = __base->_M_size;
00651     size_t __adj_endp1;
00652     const size_t __lazy_threshold = 128;
00653     
00654     if (__endp1 >= __len) {
00655         if (0 == __start) {
00656             __base->_M_ref_nonnil();
00657             return __base;
00658         } else {
00659             __adj_endp1 = __len;
00660         }
00661     } else {
00662         __adj_endp1 = __endp1;
00663     }
00664     switch(__base->_M_tag) {
00665         case _RopeRep::_S_concat:
00666             {
00667                 _RopeConcatenation* __c = (_RopeConcatenation*)__base;
00668                 _RopeRep* __left = __c->_M_left;
00669                 _RopeRep* __right = __c->_M_right;
00670                 size_t __left_len = __left->_M_size;
00671                 _RopeRep* __result;
00672 
00673                 if (__adj_endp1 <= __left_len) {
00674                     return _S_substring(__left, __start, __endp1);
00675                 } else if (__start >= __left_len) {
00676                     return _S_substring(__right, __start - __left_len,
00677                                   __adj_endp1 - __left_len);
00678                 }
00679                 _Self_destruct_ptr __left_result(
00680                   _S_substring(__left, __start, __left_len));
00681                 _Self_destruct_ptr __right_result(
00682                   _S_substring(__right, 0, __endp1 - __left_len));
00683                 __result = _S_concat(__left_result, __right_result);
00684 #               ifndef __GC
00685                   __stl_assert(1 == __result->_M_ref_count);
00686 #               endif
00687                 return __result;
00688             }
00689         case _RopeRep::_S_leaf:
00690             {
00691                 _RopeLeaf* __l = (_RopeLeaf*)__base;
00692                 _RopeLeaf* __result;
00693                 size_t __result_len;
00694                 if (__start >= __adj_endp1) return 0;
00695                 __result_len = __adj_endp1 - __start;
00696                 if (__result_len > __lazy_threshold) goto lazy;
00697 #               ifdef __GC
00698                     const _CharT* __section = __l->_M_data + __start;
00699                     __result = _S_new_RopeLeaf(__section, __result_len,
00700                                           __base->get_allocator());
00701                     __result->_M_c_string = 0;  // Not eos terminated.
00702 #               else
00703                     // We should sometimes create substring node instead.
00704                     __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
00705                                         __l->_M_data + __start, __result_len,
00706                                         __base->get_allocator());
00707 #               endif
00708                 return __result;
00709             }
00710         case _RopeRep::_S_substringfn:
00711             // Avoid introducing multiple layers of substring nodes.
00712             {
00713                 _RopeSubstring* __old = (_RopeSubstring*)__base;
00714                 size_t __result_len;
00715                 if (__start >= __adj_endp1) return 0;
00716                 __result_len = __adj_endp1 - __start;
00717                 if (__result_len > __lazy_threshold) {
00718                     _RopeSubstring* __result =
00719                         _S_new_RopeSubstring(__old->_M_base,
00720                                           __start + __old->_M_start,
00721                                           __adj_endp1 - __start,
00722                                           __base->get_allocator());
00723                     return __result;
00724 
00725                 } // *** else fall through: ***
00726             }
00727         case _RopeRep::_S_function:
00728             {
00729                 _RopeFunction* __f = (_RopeFunction*)__base;
00730                 _CharT* __section;
00731                 size_t __result_len;
00732                 if (__start >= __adj_endp1) return 0;
00733                 __result_len = __adj_endp1 - __start;
00734 
00735                 if (__result_len > __lazy_threshold) goto lazy;
00736                 __section = (_CharT*)
00737                         _Data_allocate(_S_rounded_up_size(__result_len));
00738                 __STL_TRY {
00739                   (*(__f->_M_fn))(__start, __result_len, __section);
00740                 }
00741                 __STL_UNWIND(_RopeRep::__STL_FREE_STRING(
00742                        __section, __result_len, __base->get_allocator()));
00743                 _S_cond_store_eos(__section[__result_len]);
00744                 return _S_new_RopeLeaf(__section, __result_len,
00745                                        __base->get_allocator());
00746             }
00747     }
00748     /*NOTREACHED*/
00749     __stl_assert(false);
00750   lazy:
00751     {
00752         // Create substring node.
00753         return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
00754                                __base->get_allocator());
00755     }
00756 }
00757 
00758 template<class _CharT>
00759 class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
00760     private:
00761         _CharT* _M_buf_ptr;
00762     public:
00763 
00764         _Rope_flatten_char_consumer(_CharT* __buffer) {
00765             _M_buf_ptr = __buffer;
00766         };
00767         ~_Rope_flatten_char_consumer() {}
00768         bool operator() (const _CharT* __leaf, size_t __n) {
00769             uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
00770             _M_buf_ptr += __n;
00771             return true;
00772         }
00773 };
00774             
00775 template<class _CharT>
00776 class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
00777     private:
00778         _CharT _M_pattern;
00779     public:
00780         size_t _M_count;  // Number of nonmatching characters
00781         _Rope_find_char_char_consumer(_CharT __p) 
00782           : _M_pattern(__p), _M_count(0) {}
00783         ~_Rope_find_char_char_consumer() {}
00784         bool operator() (const _CharT* __leaf, size_t __n) {
00785             size_t __i;
00786             for (__i = 0; __i < __n; __i++) {
00787                 if (__leaf[__i] == _M_pattern) {
00788                     _M_count += __i; return false;
00789                 }
00790             }
00791             _M_count += __n; return true;
00792         }
00793 };
00794 
00795 #ifndef UNDER_CE            
00796 #ifdef __STL_USE_NEW_IOSTREAMS
00797   template<class _CharT, class _Traits>
00798   // Here _CharT is both the stream and rope character type.
00799 #else
00800   template<class _CharT>
00801   // Here _CharT is the rope character type.  Unlike in the
00802   // above case, we somewhat handle the case in which it doesn't
00803   // match the stream character type, i.e. char.
00804 #endif
00805 class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
00806     private:
00807 #       ifdef __STL_USE_NEW_IOSTREAMS
00808           typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
00809 #       else
00810           typedef ostream _Insert_ostream;
00811 #       endif
00812         _Insert_ostream& _M_o;
00813     public:
00814         _Rope_insert_char_consumer(_Insert_ostream& __writer) 
00815           : _M_o(__writer) {};
00816         ~_Rope_insert_char_consumer() { };
00817                 // Caller is presumed to own the ostream
00818         bool operator() (const _CharT* __leaf, size_t __n);
00819                 // Returns true to continue traversal.
00820 };
00821             
00822 #ifdef __STL_USE_NEW_IOSTREAMS
00823   template<class _CharT, class _Traits>
00824   bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
00825                                         (const _CharT* __leaf, size_t __n)
00826   {
00827     size_t __i;
00828     //  We assume that formatting is set up correctly for each element.
00829     for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
00830     return true;
00831   }
00832 
00833 #else
00834   template<class _CharT>
00835   bool _Rope_insert_char_consumer<_CharT>::operator()
00836                                         (const _CharT* __leaf, size_t __n)
00837   {
00838     size_t __i;
00839     //  We assume that formatting is set up correctly for each element.
00840     for (__i = 0; __i < __n; __i++) _M_o << __leaf[__i];
00841     return true;
00842   }
00843 
00844 
00845   __STL_TEMPLATE_NULL
00846   inline bool _Rope_insert_char_consumer<char>::operator()
00847                                         (const char* __leaf, size_t __n)
00848   {
00849     size_t __i;
00850     for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
00851     return true;
00852   }
00853 #endif
00854 
00855 #endif //UNDER_CE
00856 
00857 template <class _CharT, class _Alloc>
00858 bool rope<_CharT, _Alloc>::_S_apply_to_pieces(
00859                                 _Rope_char_consumer<_CharT>& __c,
00860                                 const _RopeRep* __r,
00861                                 size_t __begin, size_t __end)
00862 {
00863     if (0 == __r) return true;
00864     switch(__r->_M_tag) {
00865         case _RopeRep::_S_concat:
00866             {
00867                 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
00868                 _RopeRep* __left =  __conc->_M_left;
00869                 size_t __left_len = __left->_M_size;
00870                 if (__begin < __left_len) {
00871                     size_t __left_end = min(__left_len, __end);
00872                     if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
00873                         return false;
00874                 }
00875                 if (__end > __left_len) {
00876                     _RopeRep* __right =  __conc->_M_right;
00877                     size_t __right_start = max(__left_len, __begin);
00878                     if (!_S_apply_to_pieces(__c, __right,
00879                                          __right_start - __left_len,
00880                                          __end - __left_len)) {
00881                         return false;
00882                     }
00883                 }
00884             }
00885             return true;
00886         case _RopeRep::_S_leaf:
00887             {
00888                 _RopeLeaf* __l = (_RopeLeaf*)__r;
00889                 return __c(__l->_M_data + __begin, __end - __begin);
00890             }
00891         case _RopeRep::_S_function:
00892         case _RopeRep::_S_substringfn:
00893             {
00894                 _RopeFunction* __f = (_RopeFunction*)__r;
00895                 size_t __len = __end - __begin;
00896                 bool __result;
00897                 _CharT* __buffer =
00898                   (_CharT*)alloc::allocate(__len * sizeof(_CharT));
00899                 __STL_TRY {
00900                   (*(__f->_M_fn))(__begin, __len, __buffer);
00901                   __result = __c(__buffer, __len);
00902                   alloc::deallocate(__buffer, __len * sizeof(_CharT));
00903                 }
00904                 __STL_UNWIND((alloc::deallocate(__buffer,
00905                                                 __len * sizeof(_CharT))))
00906                 return __result;
00907             }
00908         default:
00909             __stl_assert(false);
00910             /*NOTREACHED*/
00911             return false;
00912     }
00913 }
00914 
00915 #ifndef UNDER_CE
00916 
00917 #ifdef __STL_USE_NEW_IOSTREAMS
00918   template<class _CharT, class _Traits>
00919   inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
00920 #else
00921   inline void _Rope_fill(ostream& __o, size_t __n)
00922 #endif
00923 {
00924     char __f = __o.fill();
00925     size_t __i;
00926 
00927     for (__i = 0; __i < __n; __i++) __o.put(__f);
00928 }
00929 #endif //UNDER_CE    
00930 
00931 template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; }
00932 inline bool _Rope_is_simple(char*) { return true; }
00933 inline bool _Rope_is_simple(wchar_t*) { return true; }
00934 
00935 #ifndef UNDER_CE
00936 
00937 #ifdef __STL_USE_NEW_IOSTREAMS
00938   template<class _CharT, class _Traits, class _Alloc>
00939   basic_ostream<_CharT, _Traits>& operator<<
00940                                         (basic_ostream<_CharT, _Traits>& __o,
00941                                          const rope<_CharT, _Alloc>& __r)
00942 #else
00943   template<class _CharT, class _Alloc>
00944   ostream& operator<< (ostream& __o, const rope<_CharT, _Alloc>& __r)
00945 #endif
00946 {
00947     size_t __w = __o.width();
00948     bool __left = bool(__o.flags() & ios::left);
00949     size_t __pad_len;
00950     size_t __rope_len = __r.size();
00951 #   ifdef __STL_USE_NEW_IOSTREAMS
00952       _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
00953 #   else
00954       _Rope_insert_char_consumer<_CharT> __c(__o);
00955 #   endif
00956     bool __is_simple = _Rope_is_simple((_CharT*)0);
00957     
00958     if (__rope_len < __w) {
00959         __pad_len = __w - __rope_len;
00960     } else {
00961         __pad_len = 0;
00962     }
00963     if (!__is_simple) __o.width(__w/__rope_len);
00964     __STL_TRY {
00965       if (__is_simple && !__left && __pad_len > 0) {
00966         _Rope_fill(__o, __pad_len);
00967       }
00968       __r.apply_to_pieces(0, __r.size(), __c);
00969       if (__is_simple && __left && __pad_len > 0) {
00970         _Rope_fill(__o, __pad_len);
00971       }
00972       if (!__is_simple)
00973         __o.width(__w);
00974     }
00975     __STL_UNWIND(if (!__is_simple) __o.width(__w))
00976     return __o;
00977 }
00978 
00979 #endif //UNDER_CE
00980 
00981 template <class _CharT, class _Alloc>
00982 _CharT*
00983 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
00984                                  size_t __start, size_t __len,
00985                                  _CharT* __buffer)
00986 {
00987     _Rope_flatten_char_consumer<_CharT> __c(__buffer);
00988     _S_apply_to_pieces(__c, __r, __start, __start + __len);
00989     return(__buffer + __len);
00990 }
00991 
00992 template <class _CharT, class _Alloc>
00993 size_t
00994 rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const
00995 {
00996     _Rope_find_char_char_consumer<_CharT> __c(__pattern);
00997     _S_apply_to_pieces(__c, _M_tree_ptr, __start, size());
00998     size_type __result_pos = __start + __c._M_count;
00999 #   ifndef __STL_OLD_ROPE_SEMANTICS
01000         if (__result_pos == size()) __result_pos = npos;
01001 #   endif
01002     return __result_pos;
01003 }
01004 
01005 template <class _CharT, class _Alloc>
01006 _CharT*
01007 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer)
01008 {
01009     if (0 == __r) return __buffer;
01010     switch(__r->_M_tag) {
01011         case _RopeRep::_S_concat:
01012             {
01013                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01014                 _RopeRep* __left = __c->_M_left;
01015                 _RopeRep* __right = __c->_M_right;
01016                 _CharT* __rest = _S_flatten(__left, __buffer);
01017                 return _S_flatten(__right, __rest);
01018             }
01019         case _RopeRep::_S_leaf:
01020             {
01021                 _RopeLeaf* __l = (_RopeLeaf*)__r;
01022                 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
01023             }
01024         case _RopeRep::_S_function:
01025         case _RopeRep::_S_substringfn:
01026             // We dont yet do anything with substring nodes.
01027             // This needs to be fixed before ropefiles will work well.
01028             {
01029                 _RopeFunction* __f = (_RopeFunction*)__r;
01030                 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
01031                 return __buffer + __f->_M_size;
01032             }
01033         default:
01034             __stl_assert(false);
01035             /*NOTREACHED*/
01036             return 0;
01037     }
01038 }
01039 
01040 
01041 #ifndef UNDER_CE
01042 
01043 // This needs work for _CharT != char
01044 template <class _CharT, class _Alloc>
01045 void
01046 rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent)
01047 {
01048     for (int __i = 0; __i < __indent; __i++) putchar(' ');
01049     if (0 == __r) {
01050         printf("NULL\n"); return;
01051     }
01052     if (_RopeRep::_S_concat == __r->_M_tag) {
01053         _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01054         _RopeRep* __left = __c->_M_left;
01055         _RopeRep* __right = __c->_M_right;
01056 
01057 #       ifdef __GC
01058           printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
01059             __r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not");
01060 #       else
01061           printf("Concatenation %p (rc = %ld, depth = %d, "
01062                    "len = %ld, %s balanced)\n",
01063                  __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
01064                  __r->_M_is_balanced? "" : "not");
01065 #       endif
01066         _S_dump(__left, __indent + 2);
01067         _S_dump(__right, __indent + 2);
01068         return;
01069     } else {
01070         char* __kind;
01071 
01072         switch (__r->_M_tag) {
01073             case _RopeRep::_S_leaf:
01074                 __kind = "Leaf";
01075                 break;
01076             case _RopeRep::_S_function:
01077                 __kind = "Function";
01078                 break;
01079             case _RopeRep::_S_substringfn:
01080                 __kind = "Function representing substring";
01081                 break;
01082             default:
01083                 __kind = "(corrupted kind field!)";
01084         }
01085 #       ifdef __GC
01086           printf("%s %p (depth = %d, len = %ld) ",
01087                  __kind, __r, __r->_M_depth, __r->_M_size);
01088 #       else
01089           printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
01090                  __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
01091 #       endif
01092         if (_S_is_one_byte_char_type((_CharT*)0)) {
01093             const int __max_len = 40;
01094             _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
01095             _CharT __buffer[__max_len + 1];
01096             bool __too_big = __r->_M_size > __prefix->_M_size;
01097 
01098             _S_flatten(__prefix, __buffer);
01099             __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 
01100             printf("%s%s\n", 
01101                    (char*)__buffer, __too_big? "...\n" : "\n");
01102         } else {
01103             printf("\n");
01104         }
01105     }
01106 }
01107 
01108 #endif //UNDER_CE
01109 
01110 template <class _CharT, class _Alloc>
01111 const unsigned long
01112 rope<_CharT,_Alloc>::_S_min_len[
01113   _Rope_RopeRep<_CharT,_Alloc>::_S_max_rope_depth + 1] = {
01114 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
01115 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
01116 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
01117 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
01118 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
01119 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
01120 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
01121 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
01122 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
01123 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
01124 /* 45 */2971215073u };
01125 // These are Fibonacci numbers < 2**32.
01126 
01127 template <class _CharT, class _Alloc>
01128 rope<_CharT,_Alloc>::_RopeRep*
01129 rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r)
01130 {
01131     _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1];
01132     _RopeRep* __result = 0;
01133     int __i;
01134     // Invariant:
01135     // The concatenation of forest in descending order is equal to __r.
01136     // __forest[__i]._M_size >= _S_min_len[__i]
01137     // __forest[__i]._M_depth = __i
01138     // References from forest are included in refcount.
01139 
01140     for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 
01141       __forest[__i] = 0;
01142     __STL_TRY {
01143       _S_add_to_forest(__r, __forest);
01144       for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 
01145         if (0 != __forest[__i]) {
01146 #       ifndef __GC
01147           _Self_destruct_ptr __old(__result);
01148 #       endif
01149           __result = _S_concat(__forest[__i], __result);
01150         __forest[__i]->_M_unref_nonnil();
01151 #       if !defined(__GC) && defined(__STL_USE_EXCEPTIONS)
01152           __forest[__i] = 0;
01153 #       endif
01154       }
01155     }
01156     __STL_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++)
01157                  _S_unref(__forest[__i]))
01158     if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
01159 #     ifdef __STL_USE_EXCEPTIONS
01160         __STL_THROW(length_error("rope too long"));
01161 #     else
01162         abort();
01163 #     endif
01164     }
01165     return(__result);
01166 }
01167 
01168 
01169 template <class _CharT, class _Alloc>
01170 void
01171 rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
01172 {
01173     if (__r->_M_is_balanced) {
01174         _S_add_leaf_to_forest(__r, __forest);
01175         return;
01176     }
01177     __stl_assert(__r->_M_tag == _RopeRep::_S_concat);
01178     {
01179         _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01180 
01181         _S_add_to_forest(__c->_M_left, __forest);
01182         _S_add_to_forest(__c->_M_right, __forest);
01183     }
01184 }
01185 
01186 
01187 template <class _CharT, class _Alloc>
01188 void
01189 rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
01190 {
01191     _RopeRep* __insertee;               // included in refcount
01192     _RopeRep* __too_tiny = 0;           // included in refcount
01193     int __i;                            // forest[0..__i-1] is empty
01194     size_t __s = __r->_M_size;
01195 
01196     for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
01197         if (0 != __forest[__i]) {
01198 #           ifndef __GC
01199               _Self_destruct_ptr __old(__too_tiny);
01200 #           endif
01201             __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
01202             __forest[__i]->_M_unref_nonnil();
01203             __forest[__i] = 0;
01204         }
01205     }
01206     {
01207 #       ifndef __GC
01208           _Self_destruct_ptr __old(__too_tiny);
01209 #       endif
01210         __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
01211     }
01212     // Too_tiny dead, and no longer included in refcount.
01213     // Insertee is live and included.
01214     __stl_assert(_S_is_almost_balanced(__insertee));
01215     __stl_assert(__insertee->_M_depth <= __r->_M_depth + 1);
01216     for (;; ++__i) {
01217         if (0 != __forest[__i]) {
01218 #           ifndef __GC
01219               _Self_destruct_ptr __old(__insertee);
01220 #           endif
01221             __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
01222             __forest[__i]->_M_unref_nonnil();
01223             __forest[__i] = 0;
01224             __stl_assert(_S_is_almost_balanced(__insertee));
01225         }
01226         __stl_assert(_S_min_len[__i] <= __insertee->_M_size);
01227         __stl_assert(__forest[__i] == 0);
01228         if (__i == _RopeRep::_S_max_rope_depth || 
01229               __insertee->_M_size < _S_min_len[__i+1]) {
01230             __forest[__i] = __insertee;
01231             // refcount is OK since __insertee is now dead.
01232             return;
01233         }
01234     }
01235 }
01236 
01237 template <class _CharT, class _Alloc>
01238 _CharT
01239 rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
01240 {
01241     __GC_CONST _CharT* __cstr = __r->_M_c_string;
01242 
01243     __stl_assert(__i < __r->_M_size);
01244     if (0 != __cstr) return __cstr[__i]; 
01245     for(;;) {
01246       switch(__r->_M_tag) {
01247         case _RopeRep::_S_concat:
01248             {
01249                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01250                 _RopeRep* __left = __c->_M_left;
01251                 size_t __left_len = __left->_M_size;
01252 
01253                 if (__i >= __left_len) {
01254                     __i -= __left_len;
01255                     __r = __c->_M_right;
01256                 } else {
01257                     __r = __left;
01258                 }
01259             }
01260             break;
01261         case _RopeRep::_S_leaf:
01262             {
01263                 _RopeLeaf* __l = (_RopeLeaf*)__r;
01264                 return __l->_M_data[__i];
01265             }
01266         case _RopeRep::_S_function:
01267         case _RopeRep::_S_substringfn:
01268             {
01269                 _RopeFunction* __f = (_RopeFunction*)__r;
01270                 _CharT __result;
01271 
01272                 (*(__f->_M_fn))(__i, 1, &__result);
01273                 return __result;
01274             }
01275       }
01276     }
01277 }
01278 
01279 # ifndef __GC
01280 // Return a uniquely referenced character slot for the given
01281 // position, or 0 if that's not possible.
01282 template <class _CharT, class _Alloc>
01283 _CharT*
01284 rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
01285 {
01286     _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
01287     size_t __csptr = 0;
01288 
01289     for(;;) {
01290       if (__r->_M_ref_count > 1) return 0;
01291       switch(__r->_M_tag) {
01292         case _RopeRep::_S_concat:
01293             {
01294                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
01295                 _RopeRep* __left = __c->_M_left;
01296                 size_t __left_len = __left->_M_size;
01297 
01298                 if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
01299                 if (__i >= __left_len) {
01300                     __i -= __left_len;
01301                     __r = __c->_M_right;
01302                 } else {
01303                     __r = __left;
01304                 }
01305             }
01306             break;
01307         case _RopeRep::_S_leaf:
01308             {
01309                 _RopeLeaf* __l = (_RopeLeaf*)__r;
01310                 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
01311                     __clrstack[__csptr++] = __l;
01312                 while (__csptr > 0) {
01313                     -- __csptr;
01314                     _RopeRep* __d = __clrstack[__csptr];
01315                     __d->_M_free_c_string();
01316                     __d->_M_c_string = 0;
01317                 }
01318                 return __l->_M_data + __i;
01319             }
01320         case _RopeRep::_S_function:
01321         case _RopeRep::_S_substringfn:
01322             return 0;
01323       }
01324     }
01325 }
01326 # endif /* __GC */
01327 
01328 // The following could be implemented trivially using
01329 // lexicographical_compare_3way.
01330 // We do a little more work to avoid dealing with rope iterators for
01331 // flat strings.
01332 template <class _CharT, class _Alloc>
01333 int
01334 rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, 
01335                                  const _RopeRep* __right)
01336 {
01337     size_t __left_len;
01338     size_t __right_len;
01339 
01340     if (0 == __right) return 0 != __left;
01341     if (0 == __left) return -1;
01342     __left_len = __left->_M_size;
01343     __right_len = __right->_M_size;
01344     if (_RopeRep::_S_leaf == __left->_M_tag) {
01345         _RopeLeaf* __l = (_RopeLeaf*) __left;
01346         if (_RopeRep::_S_leaf == __right->_M_tag) {
01347             _RopeLeaf* __r = (_RopeLeaf*) __right;
01348             return lexicographical_compare_3way(
01349                         __l->_M_data, __l->_M_data + __left_len,
01350                         __r->_M_data, __r->_M_data + __right_len);
01351         } else {
01352             const_iterator __rstart(__right, 0);
01353             const_iterator __rend(__right, __right_len);
01354             return lexicographical_compare_3way(
01355                         __l->_M_data, __l->_M_data + __left_len,
01356                         __rstart, __rend);
01357         }
01358     } else {
01359         const_iterator __lstart(__left, 0);
01360         const_iterator __lend(__left, __left_len);
01361         if (_RopeRep::_S_leaf == __right->_M_tag) {
01362             _RopeLeaf* __r = (_RopeLeaf*) __right;
01363             return lexicographical_compare_3way(
01364                                    __lstart, __lend,
01365                                    __r->_M_data, __r->_M_data + __right_len);
01366         } else {
01367             const_iterator __rstart(__right, 0);
01368             const_iterator __rend(__right, __right_len);
01369             return lexicographical_compare_3way(
01370                                    __lstart, __lend,
01371                                    __rstart, __rend);
01372         }
01373     }
01374 }
01375 
01376 // Assignment to reference proxies.
01377 template <class _CharT, class _Alloc>
01378 _Rope_char_ref_proxy<_CharT, _Alloc>&
01379 _Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
01380     _RopeRep* __old = _M_root->_M_tree_ptr;
01381 #   ifndef __GC
01382         // First check for the case in which everything is uniquely
01383         // referenced.  In that case we can do this destructively.
01384         _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
01385         if (0 != __ptr) {
01386             *__ptr = __c;
01387             return *this;
01388         }
01389 #   endif
01390     _Self_destruct_ptr __left(
01391       _My_rope::_S_substring(__old, 0, _M_pos));
01392     _Self_destruct_ptr __right(
01393       _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size));
01394     _Self_destruct_ptr __result_left(
01395       _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
01396 
01397 #   ifndef __GC
01398       __stl_assert(__left == __result_left || 1 == __result_left->_M_ref_count);
01399 #   endif
01400     _RopeRep* __result =
01401                 _My_rope::_S_concat(__result_left, __right);
01402 #   ifndef __GC
01403       __stl_assert(1 <= __result->_M_ref_count);
01404       _RopeRep::_S_unref(__old);
01405 #   endif
01406     _M_root->_M_tree_ptr = __result;
01407     return *this;
01408 }
01409 
01410 template <class _CharT, class _Alloc>
01411 inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const
01412 {
01413     if (_M_current_valid) {
01414         return _M_current;
01415     } else {
01416         return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
01417     }
01418 }
01419 template <class _CharT, class _Alloc>
01420 _Rope_char_ptr_proxy<_CharT, _Alloc>
01421 _Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
01422     return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
01423 }
01424 
01425 template <class _CharT, class _Alloc>
01426 rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c,
01427                            const allocator_type& __a)
01428 : _Base(__a)
01429 {
01430     rope<_CharT,_Alloc> __result;
01431     const size_t __exponentiate_threshold = 32;
01432     size_t __exponent;
01433     size_t __rest;
01434     _CharT* __rest_buffer;
01435     _RopeRep* __remainder;
01436     rope<_CharT,_Alloc> __remainder_rope;
01437 
01438     if (0 == __n)
01439       return;
01440     
01441     __exponent = __n / __exponentiate_threshold;
01442     __rest = __n % __exponentiate_threshold;
01443     if (0 == __rest) {
01444         __remainder = 0;
01445     } else {
01446         __rest_buffer = _Data_allocate(_S_rounded_up_size(__rest));
01447         uninitialized_fill_n(__rest_buffer, __rest, __c);
01448         _S_cond_store_eos(__rest_buffer[__rest]);
01449         __STL_TRY {
01450             __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
01451         }
01452         __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a))
01453     }
01454     __remainder_rope._M_tree_ptr = __remainder;
01455     if (__exponent != 0) {
01456         _CharT* __base_buffer =
01457           _Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
01458         _RopeLeaf* __base_leaf;
01459         rope __base_rope;
01460         uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
01461         _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
01462         __STL_TRY {
01463           __base_leaf = _S_new_RopeLeaf(__base_buffer,
01464                                         __exponentiate_threshold, __a);
01465         }
01466         __STL_UNWIND(_RopeRep::__STL_FREE_STRING(__base_buffer, 
01467                                                  __exponentiate_threshold, __a))
01468         __base_rope._M_tree_ptr = __base_leaf;
01469         if (1 == __exponent) {
01470           __result = __base_rope;
01471 #         ifndef __GC
01472             __stl_assert(2 == __result._M_tree_ptr->_M_ref_count);
01473                 // One each for base_rope and __result
01474 #         endif
01475         } else {
01476           __result = power(__base_rope, __exponent,
01477                            _Rope_Concat_fn<_CharT,_Alloc>());
01478         }
01479         if (0 != __remainder) {
01480           __result += __remainder_rope;
01481         }
01482     } else {
01483         __result = __remainder_rope;
01484     }
01485     _M_tree_ptr = __result._M_tree_ptr;
01486     _M_tree_ptr->_M_ref_nonnil();
01487 }
01488 
01489 template<class _CharT, class _Alloc>
01490   _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1];
01491 
01492 template<class _CharT, class _Alloc>
01493 const _CharT* rope<_CharT,_Alloc>::c_str() const {
01494     if (0 == _M_tree_ptr) {
01495         _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
01496                                              // but probably fast.
01497         return _S_empty_c_str;
01498     }
01499     __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
01500     if (0 != __old_c_string) return(__old_c_string);
01501     size_t __s = size();
01502     _CharT* __result = _Data_allocate(__s + 1);
01503     _S_flatten(_M_tree_ptr, __result);
01504     __result[__s] = _S_eos((_CharT*)0);
01505 #   ifdef __GC
01506         _M_tree_ptr->_M_c_string = __result;
01507 #   else
01508       if ((__old_c_string = (__GC_CONST _CharT*)
01509              _Atomic_swap((unsigned long *)(&(_M_tree_ptr->_M_c_string)),
01510                           (unsigned long)__result)) != 0) {
01511         // It must have been added in the interim.  Hence it had to have been
01512         // separately allocated.  Deallocate the old copy, since we just
01513         // replaced it.
01514         destroy(__old_c_string, __old_c_string + __s + 1);
01515         _Data_deallocate(__old_c_string, __s + 1);
01516       }
01517 #   endif
01518     return(__result);
01519 }
01520 
01521 template<class _CharT, class _Alloc>
01522 const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
01523     if (0 == _M_tree_ptr) {
01524         _S_empty_c_str[0] = _S_eos((_CharT*)0);
01525         return _S_empty_c_str;
01526     }
01527     __GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string;
01528     if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 0 != __old_c_string) {
01529         return(__old_c_string);
01530     }
01531     size_t __s = size();
01532     _CharT* __result = _Data_allocate(_S_rounded_up_size(__s));
01533     _S_flatten(_M_tree_ptr, __result);
01534     __result[__s] = _S_eos((_CharT*)0);
01535     _M_tree_ptr->_M_unref_nonnil();
01536     _M_tree_ptr = _S_new_RopeLeaf(__result, __s, get_allocator());
01537     return(__result);
01538 }
01539 
01540 // Algorithm specializations.  More should be added.
01541 
01542 template<class _Rope_iterator>  // was templated on CharT and Alloc
01543 void                            // VC++ workaround
01544 _Rope_rotate(_Rope_iterator __first,
01545              _Rope_iterator __middle,
01546              _Rope_iterator __last)
01547 {
01548   typedef typename _Rope_iterator::value_type _CharT;
01549   typedef typename _Rope_iterator::_allocator_type _Alloc;
01550   
01551   __stl_assert(__first.container() == __middle.container()
01552                            && __middle.container() == __last.container());
01553   rope<_CharT,_Alloc>& __r(__first.container());
01554   rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
01555   rope<_CharT,_Alloc> __suffix = 
01556     __r.substr(__last.index(), __r.size() - __last.index());
01557   rope<_CharT,_Alloc> __part1 = 
01558     __r.substr(__middle.index(), __last.index() - __middle.index());
01559   rope<_CharT,_Alloc> __part2 = 
01560     __r.substr(__first.index(), __middle.index() - __first.index());
01561   __r = __prefix;
01562   __r += __part1;
01563   __r += __part2;
01564   __r += __suffix;
01565 }
01566 
01567 #if !defined(__GNUC__) && !defined (UNDER_CE)
01568 // Appears to confuse g++
01569 inline void rotate(_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __first,
01570                    _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __middle,
01571                    _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __last) {
01572     _Rope_rotate(__first, __middle, __last);
01573 }
01574 #endif
01575 
01576 # if 0
01577 // Probably not useful for several reasons:
01578 // - for SGIs 7.1 compiler and probably some others,
01579 //   this forces lots of rope<wchar_t, ...> instantiations, creating a
01580 //   code bloat and compile time problem.  (Fixed in 7.2.)
01581 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
01582 //   for unicode strings.  Unsigned short may be a better character
01583 //   type.
01584 inline void rotate(
01585                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first,
01586                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle,
01587                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last) {
01588     _Rope_rotate(__first, __middle, __last);
01589 }
01590 # endif
01591 
01592 
01593 #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
01594 #pragma reset woff 1174
01595 #endif
01596 
01597 __STL_END_NAMESPACE
01598 
01599 // Local Variables:
01600 // mode:C++
01601 // End:
01602 

---