ropeimpl.h Source File

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