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

Generated on Thu Jul 23 21:16:15 2009 for libstdc++ by  doxygen 1.5.8