contrib/gcc-3.4/libstdc++-v3/include/ext/ropeimpl.h

   1 // SGI's rope class implementation -*- C++ -*-
   2
   3 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 /*
  31  * Copyright (c) 1997
  32  * Silicon Graphics Computer Systems, Inc.
  33  *
  34  * Permission to use, copy, modify, distribute and sell this software
  35  * and its documentation for any purpose is hereby granted without fee,
  36  * provided that the above copyright notice appear in all copies and
  37  * that both that copyright notice and this permission notice appear
  38  * in supporting documentation.  Silicon Graphics makes no
  39  * representations about the suitability of this software for any
  40  * purpose.  It is provided "as is" without express or implied warranty.
  41  */
  42
  43 /** @file ropeimpl.h
  44  *  This is an internal header file, included by other library headers.
  45  *  You should not attempt to use it directly.
  46  */
  47
  48 #include <cstdio>
  49 #include <ostream>
  50 #include <bits/functexcept.h>
  51
  52 #include <ext/algorithm> // For copy_n and lexicographical_compare_3way
  53 #include <ext/memory> // For uninitialized_copy_n
  54 #include <ext/numeric> // For power
  55
  56 namespace __gnu_cxx
  57 {
  58   using std::size_t;
  59   using std::printf;
  60   using std::basic_ostream;
  61   using std::__throw_length_error;
  62   using std::_Destroy;
  63   using std::uninitialized_fill_n;
  64
  65 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
  66 // if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
  67 // Results in a valid buf_ptr if the iterator can be legitimately
  68 // dereferenced.
  69 template <class _CharT, class _Alloc>
  70 void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf(
  71   _Rope_iterator_base<_CharT,_Alloc>& __x)
  72 {
  73     const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
  74     size_t __leaf_pos = __x._M_leaf_pos;
  75     size_t __pos = __x._M_current_pos;
  76
  77     switch(__leaf->_M_tag) {
  78         case _Rope_constants::_S_leaf:
  79             __x._M_buf_start =
  80               ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
  81             __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
  82             __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
  83             break;
  84         case _Rope_constants::_S_function:
  85         case _Rope_constants::_S_substringfn:
  86             {
  87                 size_t __len = _S_iterator_buf_len;
  88                 size_t __buf_start_pos = __leaf_pos;
  89                 size_t __leaf_end = __leaf_pos + __leaf->_M_size;
  90                 char_producer<_CharT>* __fn =
  91                         ((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;
  92
  93                 if (__buf_start_pos + __len <= __pos) {
  94                     __buf_start_pos = __pos - __len/4;
  95                     if (__buf_start_pos + __len > __leaf_end) {
  96                         __buf_start_pos = __leaf_end - __len;
  97                     }
  98                 }
  99                 if (__buf_start_pos + __len > __leaf_end) {
 100                     __len = __leaf_end - __buf_start_pos;
 101                 }
 102                 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
 103                 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
 104                 __x._M_buf_start = __x._M_tmp_buf;
 105                 __x._M_buf_end = __x._M_tmp_buf + __len;
 106             }
 107             break;
 108         default:
 109           break;
 110     }
 111 }
 112
 113 // Set path and buffer inside a rope iterator.  We assume that
 114 // pos and root are already set.
 115 template <class _CharT, class _Alloc>
 116 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
 117 (_Rope_iterator_base<_CharT,_Alloc>& __x)
 118 {
 119     const _RopeRep* __path[_Rope_constants::_S_max_rope_depth + 1];
 120     const _RopeRep* __curr_rope;
 121     int __curr_depth = -1;  /* index into path    */
 122     size_t __curr_start_pos = 0;
 123     size_t __pos = __x._M_current_pos;
 124     unsigned char __dirns = 0; // Bit vector marking right turns in the path
 125
 126     if (__pos >= __x._M_root->_M_size) {
 127         __x._M_buf_ptr = 0;
 128         return;
 129     }
 130     __curr_rope = __x._M_root;
 131     if (0 != __curr_rope->_M_c_string) {
 132         /* Treat the root as a leaf. */
 133         __x._M_buf_start = __curr_rope->_M_c_string;
 134         __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
 135         __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
 136         __x._M_path_end[0] = __curr_rope;
 137         __x._M_leaf_index = 0;
 138         __x._M_leaf_pos = 0;
 139         return;
 140     }
 141     for(;;) {
 142         ++__curr_depth;
 143         __path[__curr_depth] = __curr_rope;
 144         switch(__curr_rope->_M_tag) {
 145           case _Rope_constants::_S_leaf:
 146           case _Rope_constants::_S_function:
 147           case _Rope_constants::_S_substringfn:
 148             __x._M_leaf_pos = __curr_start_pos;
 149             goto done;
 150           case _Rope_constants::_S_concat:
 151             {
 152                 _Rope_RopeConcatenation<_CharT,_Alloc>* __c =
 153                         (_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
 154                 _RopeRep* __left = __c->_M_left;
 155                 size_t __left_len = __left->_M_size;
 156
 157                 __dirns <<= 1;
 158                 if (__pos >= __curr_start_pos + __left_len) {
 159                     __dirns |= 1;
 160                     __curr_rope = __c->_M_right;
 161                     __curr_start_pos += __left_len;
 162                 } else {
 163                     __curr_rope = __left;
 164                 }
 165             }
 166             break;
 167         }
 168     }
 169   done:
 170     // Copy last section of path into _M_path_end.
 171       {
 172         int __i = -1;
 173         int __j = __curr_depth + 1 - _S_path_cache_len;
 174
 175         if (__j < 0) __j = 0;
 176         while (__j <= __curr_depth) {
 177             __x._M_path_end[++__i] = __path[__j++];
 178         }
 179         __x._M_leaf_index = __i;
 180       }
 181       __x._M_path_directions = __dirns;
 182       _S_setbuf(__x);
 183 }
 184
 185 // Specialized version of the above.  Assumes that
 186 // the path cache is valid for the previous position.
 187 template <class _CharT, class _Alloc>
 188 void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
 189 (_Rope_iterator_base<_CharT,_Alloc>& __x)
 190 {
 191     int __current_index = __x._M_leaf_index;
 192     const _RopeRep* __current_node = __x._M_path_end[__current_index];
 193     size_t __len = __current_node->_M_size;
 194     size_t __node_start_pos = __x._M_leaf_pos;
 195     unsigned char __dirns = __x._M_path_directions;
 196     _Rope_RopeConcatenation<_CharT,_Alloc>* __c;
 197
 198     if (__x._M_current_pos - __node_start_pos < __len) {
 199         /* More stuff in this leaf, we just didn't cache it. */
 200         _S_setbuf(__x);
 201         return;
 202     }
 203     //  node_start_pos is starting position of last_node.
 204     while (--__current_index >= 0) {
 205         if (!(__dirns & 1) /* Path turned left */)
 206           break;
 207         __current_node = __x._M_path_end[__current_index];
 208         __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
 209         // Otherwise we were in the right child.  Thus we should pop
 210         // the concatenation node.
 211         __node_start_pos -= __c->_M_left->_M_size;
 212         __dirns >>= 1;
 213     }
 214     if (__current_index < 0) {
 215         // We underflowed the cache. Punt.
 216         _S_setcache(__x);
 217         return;
 218     }
 219     __current_node = __x._M_path_end[__current_index];
 220     __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
 221     // current_node is a concatenation node.  We are positioned on the first
 222     // character in its right child.
 223     // node_start_pos is starting position of current_node.
 224     __node_start_pos += __c->_M_left->_M_size;
 225     __current_node = __c->_M_right;
 226     __x._M_path_end[++__current_index] = __current_node;
 227     __dirns |= 1;
 228     while (_Rope_constants::_S_concat == __current_node->_M_tag) {
 229         ++__current_index;
 230         if (_S_path_cache_len == __current_index) {
 231             int __i;
 232             for (__i = 0; __i < _S_path_cache_len-1; __i++) {
 233                 __x._M_path_end[__i] = __x._M_path_end[__i+1];
 234             }
 235             --__current_index;
 236         }
 237         __current_node =
 238             ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
 239         __x._M_path_end[__current_index] = __current_node;
 240         __dirns <<= 1;
 241         // node_start_pos is unchanged.
 242     }
 243     __x._M_leaf_index = __current_index;
 244     __x._M_leaf_pos = __node_start_pos;
 245     __x._M_path_directions = __dirns;
 246     _S_setbuf(__x);
 247 }
 248
 249 template <class _CharT, class _Alloc>
 250 void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
 251     _M_current_pos += __n;
 252     if (0 != _M_buf_ptr) {
 253         size_t __chars_left = _M_buf_end - _M_buf_ptr;
 254         if (__chars_left > __n) {
 255             _M_buf_ptr += __n;
 256         } else if (__chars_left == __n) {
 257             _M_buf_ptr += __n;
 258             _S_setcache_for_incr(*this);
 259         } else {
 260             _M_buf_ptr = 0;
 261         }
 262     }
 263 }
 264
 265 template <class _CharT, class _Alloc>
 266 void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
 267     if (0 != _M_buf_ptr) {
 268         size_t __chars_left = _M_buf_ptr - _M_buf_start;
 269         if (__chars_left >= __n) {
 270             _M_buf_ptr -= __n;
 271         } else {
 272             _M_buf_ptr = 0;
 273         }
 274     }
 275     _M_current_pos -= __n;
 276 }
 277
 278 template <class _CharT, class _Alloc>
 279 void _Rope_iterator<_CharT,_Alloc>::_M_check() {
 280     if (_M_root_rope->_M_tree_ptr != this->_M_root) {
 281         // _Rope was modified.  Get things fixed up.
 282         _RopeRep::_S_unref(this->_M_root);
 283         this->_M_root = _M_root_rope->_M_tree_ptr;
 284         _RopeRep::_S_ref(this->_M_root);
 285         this->_M_buf_ptr = 0;
 286     }
 287 }
 288
 289 template <class _CharT, class _Alloc>
 290 inline
 291 _Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator(
 292   const _Rope_iterator<_CharT,_Alloc>& __x)
 293 : _Rope_iterator_base<_CharT,_Alloc>(__x)
 294 { }
 295
 296 template <class _CharT, class _Alloc>
 297 inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator(
 298   rope<_CharT,_Alloc>& __r, size_t __pos)
 299 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),
 300   _M_root_rope(&__r)
 301 {
 302     _RopeRep::_S_ref(this->_M_root);
 303 }
 304
 305 template <class _CharT, class _Alloc>
 306 inline size_t
 307 rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s)
 308 {
 309     const _CharT* __p = __s;
 310
 311     while (!_S_is0(*__p)) { ++__p; }
 312     return (__p - __s);
 313 }
 314
 315
 316 #ifndef __GC
 317
 318 template <class _CharT, class _Alloc>
 319 inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string()
 320 {
 321     _CharT* __cstr = _M_c_string;
 322     if (0 != __cstr) {
 323         size_t __size = this->_M_size + 1;
 324         _Destroy(__cstr, __cstr + __size);
 325         this->_Data_deallocate(__cstr, __size);
 326     }
 327 }
 328
 329
 330 template <class _CharT, class _Alloc>
 331   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,
 332                                                            size_t __n,
 333                                                            allocator_type __a)
 334 {
 335     if (!_S_is_basic_char_type((_CharT*)0)) {
 336         _Destroy(__s, __s + __n);
 337     }
 338 //  This has to be a static member, so this gets a bit messy
 339         __a.deallocate(
 340             __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));
 341 }
 342
 343
 344 //  There are several reasons for not doing this with virtual destructors
 345 //  and a class specific delete operator:
 346 //  - A class specific delete operator can't easily get access to
 347 //    allocator instances if we need them.
 348 //  - Any virtual function would need a 4 or byte vtable pointer;
 349 //    this only requires a one byte tag per object.
 350 template <class _CharT, class _Alloc>
 351 void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
 352 {
 353     switch(_M_tag) {
 354         case _Rope_constants::_S_leaf:
 355             {
 356                 _Rope_RopeLeaf<_CharT,_Alloc>* __l
 357                         = (_Rope_RopeLeaf<_CharT,_Alloc>*)this;
 358                 __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
 359                 _L_deallocate(__l, 1);
 360                 break;
 361             }
 362         case _Rope_constants::_S_concat:
 363             {
 364                 _Rope_RopeConcatenation<_CharT,_Alloc>* __c
 365                     = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;
 366                 __c->_Rope_RopeConcatenation<_CharT,_Alloc>::
 367                        ~_Rope_RopeConcatenation();
 368                 _C_deallocate(__c, 1);
 369                 break;
 370             }
 371         case _Rope_constants::_S_function:
 372             {
 373                 _Rope_RopeFunction<_CharT,_Alloc>* __f
 374                     = (_Rope_RopeFunction<_CharT,_Alloc>*)this;
 375                 __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();
 376                 _F_deallocate(__f, 1);
 377                 break;
 378             }
 379         case _Rope_constants::_S_substringfn:
 380             {
 381                 _Rope_RopeSubstring<_CharT,_Alloc>* __ss =
 382                         (_Rope_RopeSubstring<_CharT,_Alloc>*)this;
 383                 __ss->_Rope_RopeSubstring<_CharT,_Alloc>::
 384                         ~_Rope_RopeSubstring();
 385                 _S_deallocate(__ss, 1);
 386                 break;
 387             }
 388     }
 389 }
 390 #else
 391
 392 template <class _CharT, class _Alloc>
 393   inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
 394                 (const _CharT*, size_t, allocator_type)
 395 {}
 396
 397 #endif
 398
 399
 400 // Concatenate a C string onto a leaf rope by copying the rope data.
 401 // Used for short ropes.
 402 template <class _CharT, class _Alloc>
 403 typename rope<_CharT,_Alloc>::_RopeLeaf*
 404 rope<_CharT,_Alloc>::_S_leaf_concat_char_iter
 405                 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
 406 {
 407     size_t __old_len = __r->_M_size;
 408     _CharT* __new_data = (_CharT*)
 409       _Data_allocate(_S_rounded_up_size(__old_len + __len));
 410     _RopeLeaf* __result;
 411
 412     uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
 413     uninitialized_copy_n(__iter, __len, __new_data + __old_len);
 414     _S_cond_store_eos(__new_data[__old_len + __len]);
 415     try {
 416         __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
 417                                    __r->get_allocator());
 418     }
 419     catch(...)
 420       {
 421         _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
 422                                     __r->get_allocator());
 423         __throw_exception_again;
 424       }
 425     return __result;
 426 }
 427
 428 #ifndef __GC
 429 // As above, but it's OK to clobber original if refcount is 1
 430 template <class _CharT, class _Alloc>
 431 typename rope<_CharT,_Alloc>::_RopeLeaf*
 432 rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter
 433                 (_RopeLeaf* __r, const _CharT* __iter, size_t __len)
 434 {
 435     if (__r->_M_ref_count > 1)
 436       return _S_leaf_concat_char_iter(__r, __iter, __len);
 437     size_t __old_len = __r->_M_size;
 438     if (_S_allocated_capacity(__old_len) >= __old_len + __len) {
 439         // The space has been partially initialized for the standard
 440         // character types.  But that doesn't matter for those types.
 441         uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
 442         if (_S_is_basic_char_type((_CharT*)0)) {
 443             _S_cond_store_eos(__r->_M_data[__old_len + __len]);
 444         } else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
 445             __r->_M_free_c_string();
 446             __r->_M_c_string = 0;
 447         }
 448         __r->_M_size = __old_len + __len;
 449         __r->_M_ref_count = 2;
 450         return __r;
 451     } else {
 452         _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
 453         return __result;
 454     }
 455 }
 456 #endif
 457
 458 // Assumes left and right are not 0.
 459 // Does not increment (nor decrement on exception) child reference counts.
 460 // Result has ref count 1.
 461 template <class _CharT, class _Alloc>
 462 typename rope<_CharT,_Alloc>::_RopeRep*
 463 rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right)
 464 {
 465   _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
 466                                                       __left->get_allocator());
 467   size_t __depth = __result->_M_depth;
 468
 469   if (__depth > 20 && (__result->_M_size < 1000 ||
 470                        __depth > _Rope_constants::_S_max_rope_depth))
 471     {
 472       _RopeRep* __balanced;
 473
 474       try
 475         {
 476           __balanced = _S_balance(__result);
 477           __result->_M_unref_nonnil();
 478         }
 479       catch(...)
 480         {
 481           _C_deallocate(__result,1);
 482           __throw_exception_again;
 483         }
 484       // In case of exception, we need to deallocate
 485       // otherwise dangling result node.  But caller
 486       // still owns its children.  Thus unref is
 487       // inappropriate.
 488       return __balanced;
 489     }
 490   else
 491     return __result;
 492 }
 493
 494 template <class _CharT, class _Alloc>
 495 typename
 496 rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter
 497                 (_RopeRep* __r, const _CharT*__s, size_t __slen)
 498 {
 499     _RopeRep* __result;
 500     if (0 == __slen) {
 501         _S_ref(__r);
 502         return __r;
 503     }
 504     if (0 == __r)
 505       return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
 506                                               __r->get_allocator());
 507     if (_Rope_constants::_S_leaf == __r->_M_tag &&
 508           __r->_M_size + __slen <= _S_copy_max) {
 509         __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
 510         return __result;
 511     }
 512     if (_Rope_constants::_S_concat == __r->_M_tag
 513         && _Rope_constants::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
 514         _RopeLeaf* __right =
 515           (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
 516         if (__right->_M_size + __slen <= _S_copy_max) {
 517           _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
 518           _RopeRep* __nright =
 519             _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
 520           __left->_M_ref_nonnil();
 521           try {
 522             __result = _S_tree_concat(__left, __nright);
 523           }
 524           catch(...)
 525             {
 526               _S_unref(__left);
 527               _S_unref(__nright);
 528               __throw_exception_again;
 529             }
 530           return __result;
 531         }
 532     }
 533     _RopeRep* __nright =
 534       __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
 535     try {
 536       __r->_M_ref_nonnil();
 537       __result = _S_tree_concat(__r, __nright);
 538     }
 539     catch(...)
 540       {
 541         _S_unref(__r);
 542         _S_unref(__nright);
 543         __throw_exception_again;
 544       }
 545     return __result;
 546 }
 547
 548 #ifndef __GC
 549 template <class _CharT, class _Alloc>
 550 typename rope<_CharT,_Alloc>::_RopeRep*
 551 rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
 552   _RopeRep* __r, const _CharT* __s, size_t __slen)
 553 {
 554     _RopeRep* __result;
 555     if (0 == __r)
 556       return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
 557                                               __r->get_allocator());
 558     size_t __count = __r->_M_ref_count;
 559     size_t __orig_size = __r->_M_size;
 560     if (__count > 1) return _S_concat_char_iter(__r, __s, __slen);
 561     if (0 == __slen) {
 562         __r->_M_ref_count = 2;      // One more than before
 563         return __r;
 564     }
 565     if (__orig_size + __slen <= _S_copy_max &&
 566           _Rope_constants::_S_leaf == __r->_M_tag) {
 567         __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
 568         return __result;
 569     }
 570     if (_Rope_constants::_S_concat == __r->_M_tag) {
 571         _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
 572         if (_Rope_constants::_S_leaf == __right->_M_tag
 573             && __right->_M_size + __slen <= _S_copy_max) {
 574           _RopeRep* __new_right =
 575             _S_destr_leaf_concat_char_iter(__right, __s, __slen);
 576           if (__right == __new_right)
 577             __new_right->_M_ref_count = 1;
 578           else
 579             __right->_M_unref_nonnil();
 580           __r->_M_ref_count = 2;    // One more than before.
 581           ((_RopeConcatenation*)__r)->_M_right = __new_right;
 582           __r->_M_size = __orig_size + __slen;
 583           if (0 != __r->_M_c_string) {
 584               __r->_M_free_c_string();
 585               __r->_M_c_string = 0;
 586           }
 587           return __r;
 588         }
 589     }
 590     _RopeRep* __right =
 591       __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
 592     __r->_M_ref_nonnil();
 593     try {
 594       __result = _S_tree_concat(__r, __right);
 595     }
 596     catch(...)
 597       {
 598         _S_unref(__r);
 599         _S_unref(__right);
 600         __throw_exception_again;
 601       }
 602     return __result;
 603 }
 604 #endif /* !__GC */
 605
 606 template <class _CharT, class _Alloc>
 607 typename rope<_CharT,_Alloc>::_RopeRep*
 608 rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right)
 609 {
 610     if (0 == __left) {
 611         _S_ref(__right);
 612         return __right;
 613     }
 614     if (0 == __right) {
 615         __left->_M_ref_nonnil();
 616         return __left;
 617     }
 618     if (_Rope_constants::_S_leaf == __right->_M_tag) {
 619         if (_Rope_constants::_S_leaf == __left->_M_tag) {
 620           if (__right->_M_size + __left->_M_size <= _S_copy_max) {
 621             return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
 622                                          ((_RopeLeaf*)__right)->_M_data,
 623                                          __right->_M_size);
 624           }
 625         } else if (_Rope_constants::_S_concat == __left->_M_tag
 626                    && _Rope_constants::_S_leaf ==
 627                       ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
 628           _RopeLeaf* __leftright =
 629                     (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
 630           if (__leftright->_M_size + __right->_M_size <= _S_copy_max) {
 631             _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
 632             _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
 633                                            ((_RopeLeaf*)__right)->_M_data,
 634                                            __right->_M_size);
 635             __leftleft->_M_ref_nonnil();
 636             try {
 637               return(_S_tree_concat(__leftleft, __rest));
 638             }
 639             catch(...)
 640               {
 641                 _S_unref(__leftleft);
 642                 _S_unref(__rest);
 643                 __throw_exception_again;
 644               }
 645           }
 646         }
 647     }
 648     __left->_M_ref_nonnil();
 649     __right->_M_ref_nonnil();
 650     try {
 651       return(_S_tree_concat(__left, __right));
 652     }
 653     catch(...)
 654       {
 655         _S_unref(__left);
 656         _S_unref(__right);
 657         __throw_exception_again;
 658       }
 659 }
 660
 661 template <class _CharT, class _Alloc>
 662 typename rope<_CharT,_Alloc>::_RopeRep*
 663 rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base,
 664                                size_t __start, size_t __endp1)
 665 {
 666     if (0 == __base) return 0;
 667     size_t __len = __base->_M_size;
 668     size_t __adj_endp1;
 669     const size_t __lazy_threshold = 128;
 670
 671     if (__endp1 >= __len) {
 672         if (0 == __start) {
 673             __base->_M_ref_nonnil();
 674             return __base;
 675         } else {
 676             __adj_endp1 = __len;
 677         }
 678     } else {
 679         __adj_endp1 = __endp1;
 680     }
 681     switch(__base->_M_tag) {
 682         case _Rope_constants::_S_concat:
 683             {
 684                 _RopeConcatenation* __c = (_RopeConcatenation*)__base;
 685                 _RopeRep* __left = __c->_M_left;
 686                 _RopeRep* __right = __c->_M_right;
 687                 size_t __left_len = __left->_M_size;
 688                 _RopeRep* __result;
 689
 690                 if (__adj_endp1 <= __left_len) {
 691                     return _S_substring(__left, __start, __endp1);
 692                 } else if (__start >= __left_len) {
 693                     return _S_substring(__right, __start - __left_len,
 694                                   __adj_endp1 - __left_len);
 695                 }
 696                 _Self_destruct_ptr __left_result(
 697                   _S_substring(__left, __start, __left_len));
 698                 _Self_destruct_ptr __right_result(
 699                   _S_substring(__right, 0, __endp1 - __left_len));
 700                 __result = _S_concat(__left_result, __right_result);
 701                 return __result;
 702             }
 703         case _Rope_constants::_S_leaf:
 704             {
 705                 _RopeLeaf* __l = (_RopeLeaf*)__base;
 706                 _RopeLeaf* __result;
 707                 size_t __result_len;
 708                 if (__start >= __adj_endp1) return 0;
 709                 __result_len = __adj_endp1 - __start;
 710                 if (__result_len > __lazy_threshold) goto lazy;
 711 #               ifdef __GC
 712                     const _CharT* __section = __l->_M_data + __start;
 713                     __result = _S_new_RopeLeaf(__section, __result_len,
 714                                           __base->get_allocator());
 715                     __result->_M_c_string = 0;  // Not eos terminated.
 716 #               else
 717                     // We should sometimes create substring node instead.
 718                     __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(
 719                                         __l->_M_data + __start, __result_len,
 720                                         __base->get_allocator());
 721 #               endif
 722                 return __result;
 723             }
 724         case _Rope_constants::_S_substringfn:
 725             // Avoid introducing multiple layers of substring nodes.
 726             {
 727                 _RopeSubstring* __old = (_RopeSubstring*)__base;
 728                 size_t __result_len;
 729                 if (__start >= __adj_endp1) return 0;
 730                 __result_len = __adj_endp1 - __start;
 731                 if (__result_len > __lazy_threshold) {
 732                     _RopeSubstring* __result =
 733                         _S_new_RopeSubstring(__old->_M_base,
 734                                           __start + __old->_M_start,
 735                                           __adj_endp1 - __start,
 736                                           __base->get_allocator());
 737                     return __result;
 738
 739                 } // *** else fall through: ***
 740             }
 741         case _Rope_constants::_S_function:
 742             {
 743                 _RopeFunction* __f = (_RopeFunction*)__base;
 744                 _CharT* __section;
 745                 size_t __result_len;
 746                 if (__start >= __adj_endp1) return 0;
 747                 __result_len = __adj_endp1 - __start;
 748
 749                 if (__result_len > __lazy_threshold) goto lazy;
 750                 __section = (_CharT*)
 751                   _Data_allocate(_S_rounded_up_size(__result_len));
 752                 try {
 753                   (*(__f->_M_fn))(__start, __result_len, __section);
 754                 }
 755                 catch(...)
 756                   {
 757                     _RopeRep::__STL_FREE_STRING(
 758                        __section, __result_len, __base->get_allocator());
 759                     __throw_exception_again;
 760                   }
 761                 _S_cond_store_eos(__section[__result_len]);
 762                 return _S_new_RopeLeaf(__section, __result_len,
 763                                        __base->get_allocator());
 764             }
 765     }
 766   lazy:
 767     {
 768         // Create substring node.
 769         return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
 770                                __base->get_allocator());
 771     }
 772 }
 773
 774 template<class _CharT>
 775 class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
 776     private:
 777         _CharT* _M_buf_ptr;
 778     public:
 779
 780         _Rope_flatten_char_consumer(_CharT* __buffer) {
 781             _M_buf_ptr = __buffer;
 782         };
 783         ~_Rope_flatten_char_consumer() {}
 784         bool operator() (const _CharT* __leaf, size_t __n) {
 785             uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
 786             _M_buf_ptr += __n;
 787             return true;
 788         }
 789 };
 790
 791 template<class _CharT>
 792 class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> {
 793     private:
 794         _CharT _M_pattern;
 795     public:
 796         size_t _M_count;  // Number of nonmatching characters
 797         _Rope_find_char_char_consumer(_CharT __p)
 798           : _M_pattern(__p), _M_count(0) {}
 799         ~_Rope_find_char_char_consumer() {}
 800         bool operator() (const _CharT* __leaf, size_t __n) {
 801             size_t __i;
 802             for (__i = 0; __i < __n; __i++) {
 803                 if (__leaf[__i] == _M_pattern) {
 804                     _M_count += __i; return false;
 805                 }
 806             }
 807             _M_count += __n; return true;
 808         }
 809 };
 810
 811   template<class _CharT, class _Traits>
 812   // Here _CharT is both the stream and rope character type.
 813 class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> {
 814     private:
 815           typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
 816         _Insert_ostream& _M_o;
 817     public:
 818         _Rope_insert_char_consumer(_Insert_ostream& __writer)
 819           : _M_o(__writer) {};
 820         ~_Rope_insert_char_consumer() { };
 821                 // Caller is presumed to own the ostream
 822         bool operator() (const _CharT* __leaf, size_t __n);
 823                 // Returns true to continue traversal.
 824 };
 825
 826 template<class _CharT, class _Traits>
 827 bool _Rope_insert_char_consumer<_CharT, _Traits>::operator()
 828                                       (const _CharT* __leaf, size_t __n)
 829 {
 830   size_t __i;
 831   //  We assume that formatting is set up correctly for each element.
 832   for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]);
 833   return true;
 834 }
 835
 836 template <class _CharT, class _Alloc>
 837 bool rope<_CharT, _Alloc>::_S_apply_to_pieces(
 838                                 _Rope_char_consumer<_CharT>& __c,
 839                                 const _RopeRep* __r,
 840                                 size_t __begin, size_t __end)
 841 {
 842     if (0 == __r) return true;
 843     switch(__r->_M_tag) {
 844         case _Rope_constants::_S_concat:
 845             {
 846                 _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
 847                 _RopeRep* __left =  __conc->_M_left;
 848                 size_t __left_len = __left->_M_size;
 849                 if (__begin < __left_len) {
 850                     size_t __left_end = std::min(__left_len, __end);
 851                     if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
 852                         return false;
 853                 }
 854                 if (__end > __left_len) {
 855                     _RopeRep* __right =  __conc->_M_right;
 856                     size_t __right_start = std::max(__left_len, __begin);
 857                     if (!_S_apply_to_pieces(__c, __right,
 858                                          __right_start - __left_len,
 859                                          __end - __left_len)) {
 860                         return false;
 861                     }
 862                 }
 863             }
 864             return true;
 865         case _Rope_constants::_S_leaf:
 866             {
 867                 _RopeLeaf* __l = (_RopeLeaf*)__r;
 868                 return __c(__l->_M_data + __begin, __end - __begin);
 869             }
 870         case _Rope_constants::_S_function:
 871         case _Rope_constants::_S_substringfn:
 872             {
 873                 _RopeFunction* __f = (_RopeFunction*)__r;
 874                 size_t __len = __end - __begin;
 875                 bool __result;
 876                 _CharT* __buffer =
 877                   (_CharT*)_Alloc().allocate(__len * sizeof(_CharT));
 878                 try {
 879                   (*(__f->_M_fn))(__begin, __len, __buffer);
 880                   __result = __c(__buffer, __len);
 881                   _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
 882                 }
 883                 catch(...)
 884                   {
 885                     _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
 886                     __throw_exception_again;
 887                   }
 888                 return __result;
 889             }
 890         default:
 891           return false;
 892     }
 893 }
 894
 895   template<class _CharT, class _Traits>
 896   inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
 897 {
 898     char __f = __o.fill();
 899     size_t __i;
 900
 901     for (__i = 0; __i < __n; __i++) __o.put(__f);
 902 }
 903
 904
 905 template <class _CharT> inline bool _Rope_is_simple(_CharT*) { return false; }
 906 inline bool _Rope_is_simple(char*) { return true; }
 907 inline bool _Rope_is_simple(wchar_t*) { return true; }
 908
 909 template<class _CharT, class _Traits, class _Alloc>
 910 basic_ostream<_CharT, _Traits>& operator<< (basic_ostream<_CharT, _Traits>& __o,
 911                                             const rope<_CharT, _Alloc>& __r)
 912 {
 913     size_t __w = __o.width();
 914     bool __left = bool(__o.flags() & std::ios::left);
 915     size_t __pad_len;
 916     size_t __rope_len = __r.size();
 917       _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
 918     bool __is_simple = _Rope_is_simple((_CharT*)0);
 919
 920     if (__rope_len < __w) {
 921         __pad_len = __w - __rope_len;
 922     } else {
 923         __pad_len = 0;
 924     }
 925     if (!__is_simple) __o.width(__w/__rope_len);
 926     try {
 927       if (__is_simple && !__left && __pad_len > 0) {
 928         _Rope_fill(__o, __pad_len);
 929       }
 930       __r.apply_to_pieces(0, __r.size(), __c);
 931       if (__is_simple && __left && __pad_len > 0) {
 932         _Rope_fill(__o, __pad_len);
 933       }
 934       if (!__is_simple)
 935         __o.width(__w);
 936     }
 937     catch(...)
 938       {
 939         if (!__is_simple)
 940           __o.width(__w);
 941         __throw_exception_again;
 942       }
 943     return __o;
 944 }
 945
 946 template <class _CharT, class _Alloc>
 947 _CharT*
 948 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r,
 949                                  size_t __start, size_t __len,
 950                                  _CharT* __buffer)
 951 {
 952     _Rope_flatten_char_consumer<_CharT> __c(__buffer);
 953     _S_apply_to_pieces(__c, __r, __start, __start + __len);
 954     return(__buffer + __len);
 955 }
 956
 957 template <class _CharT, class _Alloc>
 958 size_t
 959 rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const
 960 {
 961     _Rope_find_char_char_consumer<_CharT> __c(__pattern);
 962     _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
 963     size_type __result_pos = __start + __c._M_count;
 964 #   ifndef __STL_OLD_ROPE_SEMANTICS
 965         if (__result_pos == size()) __result_pos = npos;
 966 #   endif
 967     return __result_pos;
 968 }
 969
 970 template <class _CharT, class _Alloc>
 971 _CharT*
 972 rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer)
 973 {
 974     if (0 == __r) return __buffer;
 975     switch(__r->_M_tag) {
 976         case _Rope_constants::_S_concat:
 977             {
 978                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
 979                 _RopeRep* __left = __c->_M_left;
 980                 _RopeRep* __right = __c->_M_right;
 981                 _CharT* __rest = _S_flatten(__left, __buffer);
 982                 return _S_flatten(__right, __rest);
 983             }
 984         case _Rope_constants::_S_leaf:
 985             {
 986                 _RopeLeaf* __l = (_RopeLeaf*)__r;
 987                 return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
 988             }
 989         case _Rope_constants::_S_function:
 990         case _Rope_constants::_S_substringfn:
 991             // We don't yet do anything with substring nodes.
 992             // This needs to be fixed before ropefiles will work well.
 993             {
 994                 _RopeFunction* __f = (_RopeFunction*)__r;
 995                 (*(__f->_M_fn))(0, __f->_M_size, __buffer);
 996                 return __buffer + __f->_M_size;
 997             }
 998         default:
 999             return 0;
1000     }
1001 }
1002
1003
1004 // This needs work for _CharT != char
1005 template <class _CharT, class _Alloc>
1006 void
1007 rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent)
1008 {
1009     for (int __i = 0; __i < __indent; __i++) putchar(' ');
1010     if (0 == __r) {
1011         printf("NULL\n"); return;
1012     }
1013     if (_Rope_constants::_S_concat == __r->_M_tag) {
1014         _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1015         _RopeRep* __left = __c->_M_left;
1016         _RopeRep* __right = __c->_M_right;
1017
1018 #       ifdef __GC
1019           printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1020             __r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not");
1021 #       else
1022           printf("Concatenation %p (rc = %ld, depth = %d, "
1023                    "len = %ld, %s balanced)\n",
1024                  __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1025                  __r->_M_is_balanced? "" : "not");
1026 #       endif
1027         _S_dump(__left, __indent + 2);
1028         _S_dump(__right, __indent + 2);
1029         return;
1030     } else {
1031         char* __kind;
1032
1033         switch (__r->_M_tag) {
1034             case _Rope_constants::_S_leaf:
1035                 __kind = "Leaf";
1036                 break;
1037             case _Rope_constants::_S_function:
1038                 __kind = "Function";
1039                 break;
1040             case _Rope_constants::_S_substringfn:
1041                 __kind = "Function representing substring";
1042                 break;
1043             default:
1044                 __kind = "(corrupted kind field!)";
1045         }
1046 #       ifdef __GC
1047           printf("%s %p (depth = %d, len = %ld) ",
1048                  __kind, __r, __r->_M_depth, __r->_M_size);
1049 #       else
1050           printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1051                  __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1052 #       endif
1053         if (_S_is_one_byte_char_type((_CharT*)0)) {
1054             const int __max_len = 40;
1055             _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1056             _CharT __buffer[__max_len + 1];
1057             bool __too_big = __r->_M_size > __prefix->_M_size;
1058
1059             _S_flatten(__prefix, __buffer);
1060             __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1061             printf("%s%s\n",
1062                    (char*)__buffer, __too_big? "...\n" : "\n");
1063         } else {
1064             printf("\n");
1065         }
1066     }
1067 }
1068
1069 template <class _CharT, class _Alloc>
1070 const unsigned long
1071 rope<_CharT,_Alloc>::_S_min_len[_Rope_constants::_S_max_rope_depth + 1] = {
1072 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1073 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1074 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1075 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1076 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1077 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1078 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1079 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1080 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1081 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1082 /* 45 */2971215073u };
1083 // These are Fibonacci numbers < 2**32.
1084
1085 template <class _CharT, class _Alloc>
1086 typename rope<_CharT,_Alloc>::_RopeRep*
1087 rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r)
1088 {
1089     _RopeRep* __forest[_Rope_constants::_S_max_rope_depth + 1];
1090     _RopeRep* __result = 0;
1091     int __i;
1092     // Invariant:
1093     // The concatenation of forest in descending order is equal to __r.
1094     // __forest[__i]._M_size >= _S_min_len[__i]
1095     // __forest[__i]._M_depth = __i
1096     // References from forest are included in refcount.
1097
1098     for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i)
1099       __forest[__i] = 0;
1100     try {
1101       _S_add_to_forest(__r, __forest);
1102       for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i)
1103         if (0 != __forest[__i]) {
1104 #       ifndef __GC
1105           _Self_destruct_ptr __old(__result);
1106 #       endif
1107           __result = _S_concat(__forest[__i], __result);
1108         __forest[__i]->_M_unref_nonnil();
1109 #       if !defined(__GC) && defined(__EXCEPTIONS)
1110           __forest[__i] = 0;
1111 #       endif
1112       }
1113     }
1114     catch(...)
1115       {
1116         for(__i = 0; __i <= _Rope_constants::_S_max_rope_depth; __i++)
1117           _S_unref(__forest[__i]);
1118         __throw_exception_again;
1119       }
1120
1121     if (__result->_M_depth > _Rope_constants::_S_max_rope_depth)
1122       __throw_length_error(__N("rope::_S_balance"));
1123     return(__result);
1124 }
1125
1126
1127 template <class _CharT, class _Alloc>
1128 void
1129 rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1130 {
1131     if (__r->_M_is_balanced) {
1132         _S_add_leaf_to_forest(__r, __forest);
1133         return;
1134     }
1135
1136     {
1137         _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1138
1139         _S_add_to_forest(__c->_M_left, __forest);
1140         _S_add_to_forest(__c->_M_right, __forest);
1141     }
1142 }
1143
1144
1145 template <class _CharT, class _Alloc>
1146 void
1147 rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1148 {
1149     _RopeRep* __insertee;               // included in refcount
1150     _RopeRep* __too_tiny = 0;           // included in refcount
1151     int __i;                            // forest[0..__i-1] is empty
1152     size_t __s = __r->_M_size;
1153
1154     for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
1155         if (0 != __forest[__i]) {
1156 #           ifndef __GC
1157               _Self_destruct_ptr __old(__too_tiny);
1158 #           endif
1159             __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
1160             __forest[__i]->_M_unref_nonnil();
1161             __forest[__i] = 0;
1162         }
1163     }
1164     {
1165 #       ifndef __GC
1166           _Self_destruct_ptr __old(__too_tiny);
1167 #       endif
1168         __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1169     }
1170     // Too_tiny dead, and no longer included in refcount.
1171     // Insertee is live and included.
1172     for (;; ++__i) {
1173         if (0 != __forest[__i]) {
1174 #           ifndef __GC
1175               _Self_destruct_ptr __old(__insertee);
1176 #           endif
1177             __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
1178             __forest[__i]->_M_unref_nonnil();
1179             __forest[__i] = 0;
1180         }
1181         if (__i == _Rope_constants::_S_max_rope_depth ||
1182               __insertee->_M_size < _S_min_len[__i+1]) {
1183             __forest[__i] = __insertee;
1184             // refcount is OK since __insertee is now dead.
1185             return;
1186         }
1187     }
1188 }
1189
1190 template <class _CharT, class _Alloc>
1191 _CharT
1192 rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i)
1193 {
1194     __GC_CONST _CharT* __cstr = __r->_M_c_string;
1195
1196     if (0 != __cstr) return __cstr[__i];
1197     for(;;) {
1198       switch(__r->_M_tag) {
1199         case _Rope_constants::_S_concat:
1200             {
1201                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1202                 _RopeRep* __left = __c->_M_left;
1203                 size_t __left_len = __left->_M_size;
1204
1205                 if (__i >= __left_len) {
1206                     __i -= __left_len;
1207                     __r = __c->_M_right;
1208                 } else {
1209                     __r = __left;
1210                 }
1211             }
1212             break;
1213         case _Rope_constants::_S_leaf:
1214             {
1215                 _RopeLeaf* __l = (_RopeLeaf*)__r;
1216                 return __l->_M_data[__i];
1217             }
1218         case _Rope_constants::_S_function:
1219         case _Rope_constants::_S_substringfn:
1220             {
1221                 _RopeFunction* __f = (_RopeFunction*)__r;
1222                 _CharT __result;
1223
1224                 (*(__f->_M_fn))(__i, 1, &__result);
1225                 return __result;
1226             }
1227       }
1228     }
1229 }
1230
1231 # ifndef __GC
1232 // Return a uniquely referenced character slot for the given
1233 // position, or 0 if that's not possible.
1234 template <class _CharT, class _Alloc>
1235 _CharT*
1236 rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
1237 {
1238     _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth];
1239     size_t __csptr = 0;
1240
1241     for(;;) {
1242       if (__r->_M_ref_count > 1) return 0;
1243       switch(__r->_M_tag) {
1244         case _Rope_constants::_S_concat:
1245             {
1246                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1247                 _RopeRep* __left = __c->_M_left;
1248                 size_t __left_len = __left->_M_size;
1249
1250                 if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
1251                 if (__i >= __left_len) {
1252                     __i -= __left_len;
1253                     __r = __c->_M_right;
1254                 } else {
1255                     __r = __left;
1256                 }
1257             }
1258             break;
1259         case _Rope_constants::_S_leaf:
1260             {
1261                 _RopeLeaf* __l = (_RopeLeaf*)__r;
1262                 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1263                     __clrstack[__csptr++] = __l;
1264                 while (__csptr > 0) {
1265                     -- __csptr;
1266                     _RopeRep* __d = __clrstack[__csptr];
1267                     __d->_M_free_c_string();
1268                     __d->_M_c_string = 0;
1269                 }
1270                 return __l->_M_data + __i;
1271             }
1272         case _Rope_constants::_S_function:
1273         case _Rope_constants::_S_substringfn:
1274             return 0;
1275       }
1276     }
1277 }
1278 # endif /* __GC */
1279
1280 // The following could be implemented trivially using
1281 // lexicographical_compare_3way.
1282 // We do a little more work to avoid dealing with rope iterators for
1283 // flat strings.
1284 template <class _CharT, class _Alloc>
1285 int
1286 rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left,
1287                                  const _RopeRep* __right)
1288 {
1289     size_t __left_len;
1290     size_t __right_len;
1291
1292     if (0 == __right) return 0 != __left;
1293     if (0 == __left) return -1;
1294     __left_len = __left->_M_size;
1295     __right_len = __right->_M_size;
1296     if (_Rope_constants::_S_leaf == __left->_M_tag) {
1297         _RopeLeaf* __l = (_RopeLeaf*) __left;
1298         if (_Rope_constants::_S_leaf == __right->_M_tag) {
1299             _RopeLeaf* __r = (_RopeLeaf*) __right;
1300             return lexicographical_compare_3way(
1301                         __l->_M_data, __l->_M_data + __left_len,
1302                         __r->_M_data, __r->_M_data + __right_len);
1303         } else {
1304             const_iterator __rstart(__right, 0);
1305             const_iterator __rend(__right, __right_len);
1306             return lexicographical_compare_3way(
1307                         __l->_M_data, __l->_M_data + __left_len,
1308                         __rstart, __rend);
1309         }
1310     } else {
1311         const_iterator __lstart(__left, 0);
1312         const_iterator __lend(__left, __left_len);
1313         if (_Rope_constants::_S_leaf == __right->_M_tag) {
1314             _RopeLeaf* __r = (_RopeLeaf*) __right;
1315             return lexicographical_compare_3way(
1316                                    __lstart, __lend,
1317                                    __r->_M_data, __r->_M_data + __right_len);
1318         } else {
1319             const_iterator __rstart(__right, 0);
1320             const_iterator __rend(__right, __right_len);
1321             return lexicographical_compare_3way(
1322                                    __lstart, __lend,
1323                                    __rstart, __rend);
1324         }
1325     }
1326 }
1327
1328 // Assignment to reference proxies.
1329 template <class _CharT, class _Alloc>
1330 _Rope_char_ref_proxy<_CharT, _Alloc>&
1331 _Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
1332     _RopeRep* __old = _M_root->_M_tree_ptr;
1333 #   ifndef __GC
1334         // First check for the case in which everything is uniquely
1335         // referenced.  In that case we can do this destructively.
1336         _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1337         if (0 != __ptr) {
1338             *__ptr = __c;
1339             return *this;
1340         }
1341 #   endif
1342     _Self_destruct_ptr __left(
1343       _My_rope::_S_substring(__old, 0, _M_pos));
1344     _Self_destruct_ptr __right(
1345       _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size));
1346     _Self_destruct_ptr __result_left(
1347       _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));
1348
1349     _RopeRep* __result =
1350                 _My_rope::_S_concat(__result_left, __right);
1351 #   ifndef __GC
1352       _RopeRep::_S_unref(__old);
1353 #   endif
1354     _M_root->_M_tree_ptr = __result;
1355     return *this;
1356 }
1357
1358 template <class _CharT, class _Alloc>
1359 inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const
1360 {
1361     if (_M_current_valid) {
1362         return _M_current;
1363     } else {
1364         return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1365     }
1366 }
1367 template <class _CharT, class _Alloc>
1368 _Rope_char_ptr_proxy<_CharT, _Alloc>
1369 _Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
1370     return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
1371 }
1372
1373 template <class _CharT, class _Alloc>
1374 rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c,
1375                            const allocator_type& __a)
1376 : _Base(__a)
1377 {
1378     rope<_CharT,_Alloc> __result;
1379     const size_t __exponentiate_threshold = 32;
1380     size_t __exponent;
1381     size_t __rest;
1382     _CharT* __rest_buffer;
1383     _RopeRep* __remainder;
1384     rope<_CharT,_Alloc> __remainder_rope;
1385
1386     if (0 == __n)
1387       return;
1388
1389     __exponent = __n / __exponentiate_threshold;
1390     __rest = __n % __exponentiate_threshold;
1391     if (0 == __rest) {
1392         __remainder = 0;
1393     } else {
1394         __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1395         uninitialized_fill_n(__rest_buffer, __rest, __c);
1396         _S_cond_store_eos(__rest_buffer[__rest]);
1397         try {
1398             __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
1399         }
1400         catch(...)
1401           {
1402             _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a);
1403             __throw_exception_again;
1404           }
1405     }
1406     __remainder_rope._M_tree_ptr = __remainder;
1407     if (__exponent != 0) {
1408         _CharT* __base_buffer =
1409           this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1410         _RopeLeaf* __base_leaf;
1411         rope __base_rope;
1412         uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
1413         _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1414         try {
1415           __base_leaf = _S_new_RopeLeaf(__base_buffer,
1416                                         __exponentiate_threshold, __a);
1417         }
1418         catch(...)
1419           {
1420             _RopeRep::__STL_FREE_STRING(__base_buffer,
1421                                         __exponentiate_threshold, __a);
1422             __throw_exception_again;
1423           }
1424         __base_rope._M_tree_ptr = __base_leaf;
1425         if (1 == __exponent) {
1426           __result = __base_rope;
1427         } else {
1428           __result = power(__base_rope, __exponent,
1429                            _Rope_Concat_fn<_CharT,_Alloc>());
1430         }
1431         if (0 != __remainder) {
1432           __result += __remainder_rope;
1433         }
1434     } else {
1435         __result = __remainder_rope;
1436     }
1437     this->_M_tree_ptr = __result._M_tree_ptr;
1438     this->_M_tree_ptr->_M_ref_nonnil();
1439 }
1440
1441 template<class _CharT, class _Alloc>
1442   _CharT rope<_CharT,_Alloc>::_S_empty_c_str[1];
1443
1444 template<class _CharT, class _Alloc>
1445 const _CharT* rope<_CharT,_Alloc>::c_str() const {
1446     if (0 == this->_M_tree_ptr) {
1447         _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
1448                                              // but probably fast.
1449         return _S_empty_c_str;
1450     }
1451     __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1452     __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1453     if (0 == __result)
1454       {
1455         size_t __s = size();
1456         __result = this->_Data_allocate(__s + 1);
1457         _S_flatten(this->_M_tree_ptr, __result);
1458         __result[__s] = _S_eos((_CharT*)0);
1459         this->_M_tree_ptr->_M_c_string = __result;
1460       }
1461     __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1462     return(__result);
1463 }
1464
1465 template<class _CharT, class _Alloc>
1466 const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
1467     if (0 == this->_M_tree_ptr) {
1468         _S_empty_c_str[0] = _S_eos((_CharT*)0);
1469         return _S_empty_c_str;
1470     }
1471     __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1472     if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag
1473         && 0 != __old_c_string) {
1474         return(__old_c_string);
1475     }
1476     size_t __s = size();
1477     _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1478     _S_flatten(this->_M_tree_ptr, __result);
1479     __result[__s] = _S_eos((_CharT*)0);
1480     this->_M_tree_ptr->_M_unref_nonnil();
1481     this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, this->get_allocator());
1482     return(__result);
1483 }
1484
1485 // Algorithm specializations.  More should be added.
1486
1487 template<class _Rope_iterator>  // was templated on CharT and Alloc
1488 void                            // VC++ workaround
1489 _Rope_rotate(_Rope_iterator __first,
1490              _Rope_iterator __middle,
1491              _Rope_iterator __last)
1492 {
1493   typedef typename _Rope_iterator::value_type _CharT;
1494   typedef typename _Rope_iterator::_allocator_type _Alloc;
1495
1496   rope<_CharT,_Alloc>& __r(__first.container());
1497   rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index());
1498   rope<_CharT,_Alloc> __suffix =
1499     __r.substr(__last.index(), __r.size() - __last.index());
1500   rope<_CharT,_Alloc> __part1 =
1501     __r.substr(__middle.index(), __last.index() - __middle.index());
1502   rope<_CharT,_Alloc> __part2 =
1503     __r.substr(__first.index(), __middle.index() - __first.index());
1504   __r = __prefix;
1505   __r += __part1;
1506   __r += __part2;
1507   __r += __suffix;
1508 }
1509
1510 #if !defined(__GNUC__)
1511 // Appears to confuse g++
1512 inline void rotate(_Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __first,
1513                    _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __middle,
1514                    _Rope_iterator<char,__STL_DEFAULT_ALLOCATOR(char)> __last) {
1515     _Rope_rotate(__first, __middle, __last);
1516 }
1517 #endif
1518
1519 # if 0
1520 // Probably not useful for several reasons:
1521 // - for SGIs 7.1 compiler and probably some others,
1522 //   this forces lots of rope<wchar_t, ...> instantiations, creating a
1523 //   code bloat and compile time problem.  (Fixed in 7.2.)
1524 // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
1525 //   for unicode strings.  Unsigned short may be a better character
1526 //   type.
1527 inline void rotate(
1528                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __first,
1529                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __middle,
1530                 _Rope_iterator<wchar_t,__STL_DEFAULT_ALLOCATOR(char)> __last) {
1531     _Rope_rotate(__first, __middle, __last);
1532 }
1533 # endif
1534
1535 } // namespace __gnu_cxx
1536
1537 // Local Variables:
1538 // mode:C++
1539 // End: