ropeimpl.h

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

Generated on Thu Feb 10 23:22:56 2005 for libstdc++-v3 Source by  doxygen 1.4.0