contrib/libstdc++3/include/ext/ropeimpl.h

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