l4/pkg/libstdc++-v3/contrib/libstdc++-v3-4.9/include/ext/ropeimpl.h

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