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