# ropeimpl.h

Go to the documentation of this 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 _RopeRep::_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 _RopeRep::_S_function:
    00085     case _RopeRep::_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 _RopeRep::_S_leaf:
    00146       case _RopeRep::_S_function:
    00147       case _RopeRep::_S_substringfn:
    00148         __x._M_leaf_pos = __curr_start_pos;
    00149         goto done;
    00150       case _RopeRep::_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 (_RopeRep::_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     _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     __r->get_allocator().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 _RopeRep::_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 _RopeRep::_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 _RopeRep::_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 _RopeRep::_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         __base->get_allocator().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 (_RopeRep::_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 _RopeRep::_S_leaf:
    01033         __kind = "Leaf";
    01034         break;
    01035         case _RopeRep::_S_function:
    01036         __kind = "Function";
    01037         break;
    01038         case _RopeRep::_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 _RopeRep::_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 _RopeRep::_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 _RopeRep::_S_function:
    01271     case _RopeRep::_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 (_RopeRep::_S_leaf == __left->_M_tag) {
    01295     _RopeLeaf* __l = (_RopeLeaf*) __left;
    01296     if (_RopeRep::_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 (_RopeRep::_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 = __a.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       __a.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->get_allocator().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 (_RopeRep::_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 = get_allocator().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