libstdc++-v3/include/ext/ropeimpl.h

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