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