libstdc++-v3 Source: ropeimpl.h Source File

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