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

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