contrib/gcc-4.1/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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  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[int(_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 - int(_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 (int(_S_path_cache_len) == __current_index)
 240             {
 241               int __i;
 242               for (__i = 0; __i < int(_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, get_allocator());
 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, __a);
 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
 504           && (__result->_M_size < 1000
 505               || __depth > size_t(_Rope_constants::_S_max_rope_depth)))
 506         {
 507           _RopeRep* __balanced;
 508
 509           try
 510             {
 511               __balanced = _S_balance(__result);
 512               __result->_M_unref_nonnil();
 513             }
 514           catch(...)
 515             {
 516               _C_deallocate(__result,1);
 517               __throw_exception_again;
 518             }
 519           // In case of exception, we need to deallocate
 520           // otherwise dangling result node.  But caller
 521           // still owns its children.  Thus unref is
 522           // inappropriate.
 523           return __balanced;
 524         }
 525       else
 526         return __result;
 527     }
 528
 529   template <class _CharT, class _Alloc>
 530     typename rope<_CharT, _Alloc>::_RopeRep*
 531     rope<_CharT, _Alloc>::
 532     _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen)
 533     {
 534       _RopeRep* __result;
 535       if (0 == __slen)
 536         {
 537           _S_ref(__r);
 538           return __r;
 539         }
 540       if (0 == __r)
 541         return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
 542                                                 __r->get_allocator());
 543       if (_Rope_constants::_S_leaf == __r->_M_tag
 544           && __r->_M_size + __slen <= size_t(_S_copy_max))
 545         {
 546           __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
 547           return __result;
 548         }
 549       if (_Rope_constants::_S_concat == __r->_M_tag
 550           && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
 551                                           __r)->_M_right->_M_tag)
 552         {
 553           _RopeLeaf* __right =
 554             (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
 555           if (__right->_M_size + __slen <= size_t(_S_copy_max))
 556             {
 557               _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
 558               _RopeRep* __nright =
 559                 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
 560               __left->_M_ref_nonnil();
 561               try
 562                 { __result = _S_tree_concat(__left, __nright); }
 563               catch(...)
 564                 {
 565                   _S_unref(__left);
 566                   _S_unref(__nright);
 567                   __throw_exception_again;
 568                 }
 569               return __result;
 570             }
 571         }
 572       _RopeRep* __nright =
 573         __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
 574       try
 575         {
 576           __r->_M_ref_nonnil();
 577           __result = _S_tree_concat(__r, __nright);
 578         }
 579       catch(...)
 580         {
 581           _S_unref(__r);
 582           _S_unref(__nright);
 583           __throw_exception_again;
 584         }
 585       return __result;
 586     }
 587
 588 #ifndef __GC
 589   template <class _CharT, class _Alloc>
 590     typename rope<_CharT,_Alloc>::_RopeRep*
 591     rope<_CharT,_Alloc>::
 592     _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen)
 593     {
 594       _RopeRep* __result;
 595       if (0 == __r)
 596         return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
 597                                                 __r->get_allocator());
 598       size_t __count = __r->_M_ref_count;
 599       size_t __orig_size = __r->_M_size;
 600       if (__count > 1)
 601         return _S_concat_char_iter(__r, __s, __slen);
 602       if (0 == __slen)
 603         {
 604           __r->_M_ref_count = 2;      // One more than before
 605           return __r;
 606         }
 607       if (__orig_size + __slen <= size_t(_S_copy_max)
 608           && _Rope_constants::_S_leaf == __r->_M_tag)
 609         {
 610           __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s,
 611                                                     __slen);
 612           return __result;
 613         }
 614       if (_Rope_constants::_S_concat == __r->_M_tag)
 615         {
 616           _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
 617                                              __r)->_M_right);
 618           if (_Rope_constants::_S_leaf == __right->_M_tag
 619               && __right->_M_size + __slen <= size_t(_S_copy_max))
 620             {
 621               _RopeRep* __new_right =
 622                 _S_destr_leaf_concat_char_iter(__right, __s, __slen);
 623               if (__right == __new_right)
 624                 __new_right->_M_ref_count = 1;
 625               else
 626                 __right->_M_unref_nonnil();
 627               __r->_M_ref_count = 2;    // One more than before.
 628               ((_RopeConcatenation*)__r)->_M_right = __new_right;
 629               __r->_M_size = __orig_size + __slen;
 630               if (0 != __r->_M_c_string)
 631                 {
 632                   __r->_M_free_c_string();
 633                   __r->_M_c_string = 0;
 634                 }
 635               return __r;
 636             }
 637         }
 638       _RopeRep* __right =
 639         __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
 640       __r->_M_ref_nonnil();
 641       try
 642         { __result = _S_tree_concat(__r, __right); }
 643       catch(...)
 644         {
 645           _S_unref(__r);
 646           _S_unref(__right);
 647           __throw_exception_again;
 648         }
 649       return __result;
 650     }
 651 #endif /* !__GC */
 652
 653   template <class _CharT, class _Alloc>
 654     typename rope<_CharT, _Alloc>::_RopeRep*
 655     rope<_CharT, _Alloc>::
 656     _S_concat(_RopeRep* __left, _RopeRep* __right)
 657     {
 658       if (0 == __left)
 659         {
 660           _S_ref(__right);
 661           return __right;
 662         }
 663       if (0 == __right)
 664         {
 665           __left->_M_ref_nonnil();
 666           return __left;
 667         }
 668       if (_Rope_constants::_S_leaf == __right->_M_tag)
 669         {
 670           if (_Rope_constants::_S_leaf == __left->_M_tag)
 671             {
 672               if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max))
 673                 return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
 674                                                 ((_RopeLeaf*)__right)->_M_data,
 675                                                 __right->_M_size);
 676             }
 677           else if (_Rope_constants::_S_concat == __left->_M_tag
 678                    && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
 679                                                    __left)->_M_right->_M_tag)
 680             {
 681               _RopeLeaf* __leftright =
 682                 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
 683               if (__leftright->_M_size
 684                   + __right->_M_size <= size_t(_S_copy_max))
 685                 {
 686                   _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
 687                   _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
 688                                                               ((_RopeLeaf*)
 689                                                                __right)->
 690                                                               _M_data,
 691                                                               __right->_M_size);
 692                   __leftleft->_M_ref_nonnil();
 693                   try
 694                     { return(_S_tree_concat(__leftleft, __rest)); }
 695                   catch(...)
 696                     {
 697                       _S_unref(__leftleft);
 698                       _S_unref(__rest);
 699                       __throw_exception_again;
 700                     }
 701                 }
 702             }
 703         }
 704       __left->_M_ref_nonnil();
 705       __right->_M_ref_nonnil();
 706       try
 707         { return(_S_tree_concat(__left, __right)); }
 708       catch(...)
 709         {
 710           _S_unref(__left);
 711           _S_unref(__right);
 712           __throw_exception_again;
 713         }
 714     }
 715
 716   template <class _CharT, class _Alloc>
 717     typename rope<_CharT, _Alloc>::_RopeRep*
 718     rope<_CharT, _Alloc>::
 719     _S_substring(_RopeRep* __base, size_t __start, size_t __endp1)
 720     {
 721       if (0 == __base)
 722         return 0;
 723       size_t __len = __base->_M_size;
 724       size_t __adj_endp1;
 725       const size_t __lazy_threshold = 128;
 726
 727       if (__endp1 >= __len)
 728         {
 729           if (0 == __start)
 730             {
 731               __base->_M_ref_nonnil();
 732               return __base;
 733             }
 734           else
 735             __adj_endp1 = __len;
 736
 737         }
 738       else
 739         __adj_endp1 = __endp1;
 740
 741       switch(__base->_M_tag)
 742         {
 743         case _Rope_constants::_S_concat:
 744             {
 745               _RopeConcatenation* __c = (_RopeConcatenation*)__base;
 746               _RopeRep* __left = __c->_M_left;
 747               _RopeRep* __right = __c->_M_right;
 748               size_t __left_len = __left->_M_size;
 749               _RopeRep* __result;
 750
 751               if (__adj_endp1 <= __left_len)
 752                 return _S_substring(__left, __start, __endp1);
 753               else if (__start >= __left_len)
 754                 return _S_substring(__right, __start - __left_len,
 755                                     __adj_endp1 - __left_len);
 756               _Self_destruct_ptr __left_result(_S_substring(__left,
 757                                                             __start,
 758                                                             __left_len));
 759               _Self_destruct_ptr __right_result(_S_substring(__right, 0,
 760                                                              __endp1
 761                                                              - __left_len));
 762               __result = _S_concat(__left_result, __right_result);
 763               return __result;
 764             }
 765         case _Rope_constants::_S_leaf:
 766           {
 767             _RopeLeaf* __l = (_RopeLeaf*)__base;
 768             _RopeLeaf* __result;
 769             size_t __result_len;
 770             if (__start >= __adj_endp1)
 771               return 0;
 772             __result_len = __adj_endp1 - __start;
 773             if (__result_len > __lazy_threshold)
 774               goto lazy;
 775 #ifdef __GC
 776             const _CharT* __section = __l->_M_data + __start;
 777             __result = _S_new_RopeLeaf(__section, __result_len,
 778                                        __base->get_allocator());
 779             __result->_M_c_string = 0;  // Not eos terminated.
 780 #else
 781             // We should sometimes create substring node instead.
 782             __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
 783                                                         __result_len,
 784                                                         __base->
 785                                                         get_allocator());
 786 #endif
 787             return __result;
 788           }
 789         case _Rope_constants::_S_substringfn:
 790           // Avoid introducing multiple layers of substring nodes.
 791           {
 792             _RopeSubstring* __old = (_RopeSubstring*)__base;
 793             size_t __result_len;
 794             if (__start >= __adj_endp1)
 795               return 0;
 796             __result_len = __adj_endp1 - __start;
 797             if (__result_len > __lazy_threshold)
 798               {
 799                 _RopeSubstring* __result =
 800                   _S_new_RopeSubstring(__old->_M_base,
 801                                        __start + __old->_M_start,
 802                                        __adj_endp1 - __start,
 803                                        __base->get_allocator());
 804                 return __result;
 805
 806               } // *** else fall through: ***
 807           }
 808         case _Rope_constants::_S_function:
 809           {
 810             _RopeFunction* __f = (_RopeFunction*)__base;
 811             _CharT* __section;
 812             size_t __result_len;
 813             if (__start >= __adj_endp1)
 814               return 0;
 815             __result_len = __adj_endp1 - __start;
 816
 817             if (__result_len > __lazy_threshold)
 818               goto lazy;
 819             __section = (_CharT*)
 820               _Data_allocate(_S_rounded_up_size(__result_len));
 821             try
 822               { (*(__f->_M_fn))(__start, __result_len, __section); }
 823             catch(...)
 824               {
 825                 _RopeRep::__STL_FREE_STRING(__section, __result_len,
 826                                             __base->get_allocator());
 827                 __throw_exception_again;
 828               }
 829             _S_cond_store_eos(__section[__result_len]);
 830             return _S_new_RopeLeaf(__section, __result_len,
 831                                    __base->get_allocator());
 832           }
 833         }
 834     lazy:
 835       {
 836         // Create substring node.
 837         return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
 838                                     __base->get_allocator());
 839       }
 840     }
 841
 842   template<class _CharT>
 843     class _Rope_flatten_char_consumer
 844     : public _Rope_char_consumer<_CharT>
 845     {
 846     private:
 847       _CharT* _M_buf_ptr;
 848     public:
 849
 850       _Rope_flatten_char_consumer(_CharT* __buffer)
 851       { _M_buf_ptr = __buffer; };
 852
 853       ~_Rope_flatten_char_consumer() {}
 854
 855       bool
 856       operator()(const _CharT* __leaf, size_t __n)
 857       {
 858         uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
 859         _M_buf_ptr += __n;
 860         return true;
 861       }
 862     };
 863
 864   template<class _CharT>
 865     class _Rope_find_char_char_consumer
 866     : public _Rope_char_consumer<_CharT>
 867     {
 868     private:
 869       _CharT _M_pattern;
 870     public:
 871       size_t _M_count;  // Number of nonmatching characters
 872
 873       _Rope_find_char_char_consumer(_CharT __p)
 874       : _M_pattern(__p), _M_count(0) {}
 875
 876       ~_Rope_find_char_char_consumer() {}
 877
 878       bool
 879       operator()(const _CharT* __leaf, size_t __n)
 880       {
 881         size_t __i;
 882         for (__i = 0; __i < __n; __i++)
 883           {
 884             if (__leaf[__i] == _M_pattern)
 885               {
 886                 _M_count += __i;
 887                 return false;
 888               }
 889           }
 890         _M_count += __n; return true;
 891       }
 892     };
 893
 894   template<class _CharT, class _Traits>
 895   // Here _CharT is both the stream and rope character type.
 896     class _Rope_insert_char_consumer
 897     : public _Rope_char_consumer<_CharT>
 898     {
 899     private:
 900       typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
 901       _Insert_ostream& _M_o;
 902     public:
 903       _Rope_insert_char_consumer(_Insert_ostream& __writer)
 904         : _M_o(__writer) {};
 905       ~_Rope_insert_char_consumer() { };
 906       // Caller is presumed to own the ostream
 907       bool operator() (const _CharT* __leaf, size_t __n);
 908       // Returns true to continue traversal.
 909     };
 910
 911   template<class _CharT, class _Traits>
 912     bool
 913     _Rope_insert_char_consumer<_CharT, _Traits>::
 914     operator()(const _CharT* __leaf, size_t __n)
 915     {
 916       size_t __i;
 917       //  We assume that formatting is set up correctly for each element.
 918       for (__i = 0; __i < __n; __i++)
 919         _M_o.put(__leaf[__i]);
 920       return true;
 921     }
 922
 923   template <class _CharT, class _Alloc>
 924     bool
 925     rope<_CharT, _Alloc>::
 926     _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
 927                        const _RopeRep* __r, size_t __begin, size_t __end)
 928     {
 929       if (0 == __r)
 930         return true;
 931       switch(__r->_M_tag)
 932         {
 933         case _Rope_constants::_S_concat:
 934           {
 935             _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
 936             _RopeRep* __left =  __conc->_M_left;
 937             size_t __left_len = __left->_M_size;
 938             if (__begin < __left_len)
 939               {
 940                 size_t __left_end = std::min(__left_len, __end);
 941                 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
 942                   return false;
 943               }
 944             if (__end > __left_len)
 945               {
 946                 _RopeRep* __right =  __conc->_M_right;
 947                 size_t __right_start = std::max(__left_len, __begin);
 948                 if (!_S_apply_to_pieces(__c, __right,
 949                                         __right_start - __left_len,
 950                                         __end - __left_len))
 951                   return false;
 952               }
 953           }
 954           return true;
 955         case _Rope_constants::_S_leaf:
 956           {
 957             _RopeLeaf* __l = (_RopeLeaf*)__r;
 958             return __c(__l->_M_data + __begin, __end - __begin);
 959           }
 960         case _Rope_constants::_S_function:
 961         case _Rope_constants::_S_substringfn:
 962             {
 963               _RopeFunction* __f = (_RopeFunction*)__r;
 964               size_t __len = __end - __begin;
 965               bool __result;
 966               _CharT* __buffer =
 967                 (_CharT*)_Alloc().allocate(__len * sizeof(_CharT));
 968               try
 969                 {
 970                   (*(__f->_M_fn))(__begin, __len, __buffer);
 971                   __result = __c(__buffer, __len);
 972                   _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
 973                 }
 974               catch(...)
 975                 {
 976                   _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
 977                   __throw_exception_again;
 978                 }
 979               return __result;
 980             }
 981         default:
 982           return false;
 983         }
 984     }
 985
 986   template<class _CharT, class _Traits>
 987     inline void
 988     _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n)
 989     {
 990       char __f = __o.fill();
 991       size_t __i;
 992
 993       for (__i = 0; __i < __n; __i++)
 994         __o.put(__f);
 995     }
 996
 997
 998   template <class _CharT>
 999     inline bool
1000     _Rope_is_simple(_CharT*)
1001     { return false; }
1002
1003   inline bool
1004   _Rope_is_simple(char*)
1005   { return true; }
1006
1007   inline bool
1008   _Rope_is_simple(wchar_t*)
1009   { return true; }
1010
1011   template<class _CharT, class _Traits, class _Alloc>
1012     basic_ostream<_CharT, _Traits>&
1013     operator<<(basic_ostream<_CharT, _Traits>& __o,
1014                const rope<_CharT, _Alloc>& __r)
1015     {
1016       size_t __w = __o.width();
1017       bool __left = bool(__o.flags() & std::ios::left);
1018       size_t __pad_len;
1019       size_t __rope_len = __r.size();
1020       _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);
1021       bool __is_simple = _Rope_is_simple((_CharT*)0);
1022
1023       if (__rope_len < __w)
1024         __pad_len = __w - __rope_len;
1025       else
1026         __pad_len = 0;
1027
1028       if (!__is_simple)
1029         __o.width(__w / __rope_len);
1030       try
1031         {
1032           if (__is_simple && !__left && __pad_len > 0)
1033             _Rope_fill(__o, __pad_len);
1034           __r.apply_to_pieces(0, __r.size(), __c);
1035           if (__is_simple && __left && __pad_len > 0)
1036             _Rope_fill(__o, __pad_len);
1037           if (!__is_simple)
1038             __o.width(__w);
1039         }
1040       catch(...)
1041         {
1042           if (!__is_simple)
1043             __o.width(__w);
1044           __throw_exception_again;
1045         }
1046       return __o;
1047     }
1048
1049   template <class _CharT, class _Alloc>
1050     _CharT*
1051     rope<_CharT, _Alloc>::
1052     _S_flatten(_RopeRep* __r, size_t __start, size_t __len,
1053                _CharT* __buffer)
1054     {
1055       _Rope_flatten_char_consumer<_CharT> __c(__buffer);
1056       _S_apply_to_pieces(__c, __r, __start, __start + __len);
1057       return(__buffer + __len);
1058     }
1059
1060   template <class _CharT, class _Alloc>
1061     size_t
1062     rope<_CharT, _Alloc>::
1063     find(_CharT __pattern, size_t __start) const
1064     {
1065       _Rope_find_char_char_consumer<_CharT> __c(__pattern);
1066       _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
1067       size_type __result_pos = __start + __c._M_count;
1068 #ifndef __STL_OLD_ROPE_SEMANTICS
1069       if (__result_pos == size())
1070         __result_pos = npos;
1071 #endif
1072       return __result_pos;
1073     }
1074
1075   template <class _CharT, class _Alloc>
1076     _CharT*
1077     rope<_CharT, _Alloc>::
1078     _S_flatten(_RopeRep* __r, _CharT* __buffer)
1079     {
1080       if (0 == __r)
1081         return __buffer;
1082       switch(__r->_M_tag)
1083         {
1084         case _Rope_constants::_S_concat:
1085           {
1086             _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1087             _RopeRep* __left = __c->_M_left;
1088             _RopeRep* __right = __c->_M_right;
1089             _CharT* __rest = _S_flatten(__left, __buffer);
1090             return _S_flatten(__right, __rest);
1091           }
1092         case _Rope_constants::_S_leaf:
1093           {
1094             _RopeLeaf* __l = (_RopeLeaf*)__r;
1095             return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
1096           }
1097         case _Rope_constants::_S_function:
1098         case _Rope_constants::_S_substringfn:
1099           // We don't yet do anything with substring nodes.
1100           // This needs to be fixed before ropefiles will work well.
1101           {
1102             _RopeFunction* __f = (_RopeFunction*)__r;
1103             (*(__f->_M_fn))(0, __f->_M_size, __buffer);
1104             return __buffer + __f->_M_size;
1105           }
1106         default:
1107           return 0;
1108         }
1109     }
1110
1111   // This needs work for _CharT != char
1112   template <class _CharT, class _Alloc>
1113     void
1114     rope<_CharT, _Alloc>::
1115     _S_dump(_RopeRep* __r, int __indent)
1116     {
1117       for (int __i = 0; __i < __indent; __i++)
1118         putchar(' ');
1119       if (0 == __r)
1120         {
1121           printf("NULL\n");
1122           return;
1123         }
1124       if (_Rope_constants::_S_concat == __r->_M_tag)
1125         {
1126           _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1127           _RopeRep* __left = __c->_M_left;
1128           _RopeRep* __right = __c->_M_right;
1129
1130 #ifdef __GC
1131           printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
1132                  __r, __r->_M_depth, __r->_M_size,
1133                  __r->_M_is_balanced? "" : "not");
1134 #else
1135           printf("Concatenation %p (rc = %ld, depth = %d, "
1136                  "len = %ld, %s balanced)\n",
1137                  __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
1138                  __r->_M_is_balanced? "" : "not");
1139 #endif
1140           _S_dump(__left, __indent + 2);
1141           _S_dump(__right, __indent + 2);
1142           return;
1143         }
1144       else
1145         {
1146           char* __kind;
1147
1148           switch (__r->_M_tag)
1149             {
1150             case _Rope_constants::_S_leaf:
1151               __kind = "Leaf";
1152               break;
1153             case _Rope_constants::_S_function:
1154               __kind = "Function";
1155               break;
1156             case _Rope_constants::_S_substringfn:
1157               __kind = "Function representing substring";
1158               break;
1159             default:
1160               __kind = "(corrupted kind field!)";
1161             }
1162 #ifdef __GC
1163           printf("%s %p (depth = %d, len = %ld) ",
1164                  __kind, __r, __r->_M_depth, __r->_M_size);
1165 #else
1166           printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
1167                  __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
1168 #endif
1169           if (_S_is_one_byte_char_type((_CharT*)0))
1170             {
1171               const int __max_len = 40;
1172               _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
1173               _CharT __buffer[__max_len + 1];
1174               bool __too_big = __r->_M_size > __prefix->_M_size;
1175
1176               _S_flatten(__prefix, __buffer);
1177               __buffer[__prefix->_M_size] = _S_eos((_CharT*)0);
1178               printf("%s%s\n", (char*)__buffer,
1179                      __too_big? "...\n" : "\n");
1180             }
1181           else
1182             printf("\n");
1183         }
1184     }
1185
1186   template <class _CharT, class _Alloc>
1187     const unsigned long
1188     rope<_CharT, _Alloc>::
1189     _S_min_len[int(_Rope_constants::_S_max_rope_depth) + 1] = {
1190       /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
1191       /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
1192       /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
1193       /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
1194       /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
1195       /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
1196       /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
1197       /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
1198       /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
1199       /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
1200       /* 45 */2971215073u };
1201   // These are Fibonacci numbers < 2**32.
1202
1203   template <class _CharT, class _Alloc>
1204     typename rope<_CharT, _Alloc>::_RopeRep*
1205     rope<_CharT, _Alloc>::
1206     _S_balance(_RopeRep* __r)
1207     {
1208       _RopeRep* __forest[int(_Rope_constants::_S_max_rope_depth) + 1];
1209       _RopeRep* __result = 0;
1210       int __i;
1211       // Invariant:
1212       // The concatenation of forest in descending order is equal to __r.
1213       // __forest[__i]._M_size >= _S_min_len[__i]
1214       // __forest[__i]._M_depth = __i
1215       // References from forest are included in refcount.
1216
1217       for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i)
1218         __forest[__i] = 0;
1219       try
1220         {
1221           _S_add_to_forest(__r, __forest);
1222           for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i)
1223             if (0 != __forest[__i])
1224               {
1225 #ifndef __GC
1226                 _Self_destruct_ptr __old(__result);
1227 #endif
1228                 __result = _S_concat(__forest[__i], __result);
1229                 __forest[__i]->_M_unref_nonnil();
1230 #if !defined(__GC) && defined(__EXCEPTIONS)
1231                 __forest[__i] = 0;
1232 #endif
1233               }
1234         }
1235       catch(...)
1236         {
1237           for(__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); __i++)
1238             _S_unref(__forest[__i]);
1239           __throw_exception_again;
1240         }
1241
1242       if (__result->_M_depth > int(_Rope_constants::_S_max_rope_depth))
1243         __throw_length_error(__N("rope::_S_balance"));
1244       return(__result);
1245     }
1246
1247   template <class _CharT, class _Alloc>
1248     void
1249     rope<_CharT, _Alloc>::
1250     _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
1251     {
1252       if (__r->_M_is_balanced)
1253         {
1254           _S_add_leaf_to_forest(__r, __forest);
1255           return;
1256         }
1257
1258       {
1259         _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1260
1261         _S_add_to_forest(__c->_M_left, __forest);
1262         _S_add_to_forest(__c->_M_right, __forest);
1263       }
1264     }
1265
1266
1267   template <class _CharT, class _Alloc>
1268     void
1269     rope<_CharT, _Alloc>::
1270     _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
1271     {
1272       _RopeRep* __insertee;             // included in refcount
1273       _RopeRep* __too_tiny = 0;         // included in refcount
1274       int __i;                          // forest[0..__i-1] is empty
1275       size_t __s = __r->_M_size;
1276
1277       for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i)
1278         {
1279           if (0 != __forest[__i])
1280             {
1281 #ifndef __GC
1282               _Self_destruct_ptr __old(__too_tiny);
1283 #endif
1284               __too_tiny = _S_concat_and_set_balanced(__forest[__i],
1285                                                       __too_tiny);
1286               __forest[__i]->_M_unref_nonnil();
1287               __forest[__i] = 0;
1288             }
1289         }
1290       {
1291 #ifndef __GC
1292         _Self_destruct_ptr __old(__too_tiny);
1293 #endif
1294         __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
1295       }
1296       // Too_tiny dead, and no longer included in refcount.
1297       // Insertee is live and included.
1298       for (;; ++__i)
1299         {
1300           if (0 != __forest[__i])
1301             {
1302 #ifndef __GC
1303               _Self_destruct_ptr __old(__insertee);
1304 #endif
1305               __insertee = _S_concat_and_set_balanced(__forest[__i],
1306                                                       __insertee);
1307               __forest[__i]->_M_unref_nonnil();
1308               __forest[__i] = 0;
1309             }
1310           if (__i == int(_Rope_constants::_S_max_rope_depth)
1311               || __insertee->_M_size < _S_min_len[__i+1])
1312             {
1313               __forest[__i] = __insertee;
1314               // refcount is OK since __insertee is now dead.
1315               return;
1316             }
1317         }
1318     }
1319
1320   template <class _CharT, class _Alloc>
1321     _CharT
1322     rope<_CharT, _Alloc>::
1323     _S_fetch(_RopeRep* __r, size_type __i)
1324     {
1325       __GC_CONST _CharT* __cstr = __r->_M_c_string;
1326
1327       if (0 != __cstr)
1328         return __cstr[__i];
1329       for(;;)
1330         {
1331           switch(__r->_M_tag)
1332             {
1333             case _Rope_constants::_S_concat:
1334               {
1335                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1336                 _RopeRep* __left = __c->_M_left;
1337                 size_t __left_len = __left->_M_size;
1338
1339                 if (__i >= __left_len)
1340                   {
1341                     __i -= __left_len;
1342                     __r = __c->_M_right;
1343                   }
1344                 else
1345                   __r = __left;
1346               }
1347               break;
1348             case _Rope_constants::_S_leaf:
1349               {
1350                 _RopeLeaf* __l = (_RopeLeaf*)__r;
1351                 return __l->_M_data[__i];
1352               }
1353             case _Rope_constants::_S_function:
1354             case _Rope_constants::_S_substringfn:
1355               {
1356                 _RopeFunction* __f = (_RopeFunction*)__r;
1357                 _CharT __result;
1358
1359                 (*(__f->_M_fn))(__i, 1, &__result);
1360                 return __result;
1361               }
1362             }
1363         }
1364     }
1365
1366 #ifndef __GC
1367   // Return a uniquely referenced character slot for the given
1368   // position, or 0 if that's not possible.
1369   template <class _CharT, class _Alloc>
1370     _CharT*
1371     rope<_CharT, _Alloc>::
1372     _S_fetch_ptr(_RopeRep* __r, size_type __i)
1373     {
1374       _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth];
1375       size_t __csptr = 0;
1376
1377       for(;;)
1378         {
1379           if (__r->_M_ref_count > 1)
1380             return 0;
1381           switch(__r->_M_tag)
1382             {
1383             case _Rope_constants::_S_concat:
1384               {
1385                 _RopeConcatenation* __c = (_RopeConcatenation*)__r;
1386                 _RopeRep* __left = __c->_M_left;
1387                 size_t __left_len = __left->_M_size;
1388
1389                 if (__c->_M_c_string != 0)
1390                   __clrstack[__csptr++] = __c;
1391                 if (__i >= __left_len)
1392                   {
1393                     __i -= __left_len;
1394                     __r = __c->_M_right;
1395                   }
1396                 else
1397                   __r = __left;
1398               }
1399               break;
1400             case _Rope_constants::_S_leaf:
1401               {
1402                 _RopeLeaf* __l = (_RopeLeaf*)__r;
1403                 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
1404                   __clrstack[__csptr++] = __l;
1405                 while (__csptr > 0)
1406                   {
1407                     -- __csptr;
1408                     _RopeRep* __d = __clrstack[__csptr];
1409                     __d->_M_free_c_string();
1410                     __d->_M_c_string = 0;
1411                   }
1412                 return __l->_M_data + __i;
1413               }
1414             case _Rope_constants::_S_function:
1415             case _Rope_constants::_S_substringfn:
1416               return 0;
1417             }
1418         }
1419     }
1420 #endif /* __GC */
1421
1422   // The following could be implemented trivially using
1423   // lexicographical_compare_3way.
1424   // We do a little more work to avoid dealing with rope iterators for
1425   // flat strings.
1426   template <class _CharT, class _Alloc>
1427     int
1428     rope<_CharT, _Alloc>::
1429     _S_compare (const _RopeRep* __left, const _RopeRep* __right)
1430     {
1431       size_t __left_len;
1432       size_t __right_len;
1433
1434       if (0 == __right)
1435         return 0 != __left;
1436       if (0 == __left)
1437         return -1;
1438       __left_len = __left->_M_size;
1439       __right_len = __right->_M_size;
1440       if (_Rope_constants::_S_leaf == __left->_M_tag)
1441         {
1442           _RopeLeaf* __l = (_RopeLeaf*) __left;
1443           if (_Rope_constants::_S_leaf == __right->_M_tag)
1444             {
1445               _RopeLeaf* __r = (_RopeLeaf*) __right;
1446               return lexicographical_compare_3way(__l->_M_data,
1447                                                   __l->_M_data + __left_len,
1448                                                   __r->_M_data, __r->_M_data
1449                                                   + __right_len);
1450             }
1451           else
1452             {
1453               const_iterator __rstart(__right, 0);
1454               const_iterator __rend(__right, __right_len);
1455               return lexicographical_compare_3way(__l->_M_data, __l->_M_data
1456                                                   + __left_len,
1457                                                   __rstart, __rend);
1458             }
1459         }
1460       else
1461         {
1462           const_iterator __lstart(__left, 0);
1463           const_iterator __lend(__left, __left_len);
1464           if (_Rope_constants::_S_leaf == __right->_M_tag)
1465             {
1466               _RopeLeaf* __r = (_RopeLeaf*) __right;
1467               return lexicographical_compare_3way(__lstart, __lend,
1468                                                   __r->_M_data, __r->_M_data
1469                                                   + __right_len);
1470             }
1471           else
1472             {
1473               const_iterator __rstart(__right, 0);
1474               const_iterator __rend(__right, __right_len);
1475               return lexicographical_compare_3way(__lstart, __lend,
1476                                                   __rstart, __rend);
1477             }
1478         }
1479     }
1480
1481   // Assignment to reference proxies.
1482   template <class _CharT, class _Alloc>
1483     _Rope_char_ref_proxy<_CharT, _Alloc>&
1484     _Rope_char_ref_proxy<_CharT, _Alloc>::
1485     operator=(_CharT __c)
1486     {
1487       _RopeRep* __old = _M_root->_M_tree_ptr;
1488 #ifndef __GC
1489       // First check for the case in which everything is uniquely
1490       // referenced.  In that case we can do this destructively.
1491       _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
1492       if (0 != __ptr)
1493         {
1494           *__ptr = __c;
1495           return *this;
1496         }
1497 #endif
1498       _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
1499       _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
1500                                                         __old->_M_size));
1501       _Self_destruct_ptr __result_left(_My_rope::
1502                                        _S_destr_concat_char_iter(__left,
1503                                                                  &__c, 1));
1504
1505       _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
1506 #ifndef __GC
1507       _RopeRep::_S_unref(__old);
1508 #endif
1509       _M_root->_M_tree_ptr = __result;
1510       return *this;
1511     }
1512
1513   template <class _CharT, class _Alloc>
1514     inline _Rope_char_ref_proxy<_CharT, _Alloc>::
1515     operator _CharT() const
1516     {
1517       if (_M_current_valid)
1518         return _M_current;
1519       else
1520         return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
1521     }
1522
1523   template <class _CharT, class _Alloc>
1524     _Rope_char_ptr_proxy<_CharT, _Alloc>
1525     _Rope_char_ref_proxy<_CharT, _Alloc>::
1526     operator&() const
1527     { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }
1528
1529   template <class _CharT, class _Alloc>
1530     rope<_CharT, _Alloc>::
1531     rope(size_t __n, _CharT __c, const allocator_type& __a)
1532     : _Base(__a)
1533     {
1534       rope<_CharT,_Alloc> __result;
1535       const size_t __exponentiate_threshold = 32;
1536       size_t __exponent;
1537       size_t __rest;
1538       _CharT* __rest_buffer;
1539       _RopeRep* __remainder;
1540       rope<_CharT, _Alloc> __remainder_rope;
1541
1542       if (0 == __n)
1543         return;
1544
1545       __exponent = __n / __exponentiate_threshold;
1546       __rest = __n % __exponentiate_threshold;
1547       if (0 == __rest)
1548         __remainder = 0;
1549       else
1550         {
1551           __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
1552           __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
1553                                    get_allocator());
1554           _S_cond_store_eos(__rest_buffer[__rest]);
1555           try
1556             { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); }
1557           catch(...)
1558             {
1559               _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a);
1560               __throw_exception_again;
1561             }
1562         }
1563       __remainder_rope._M_tree_ptr = __remainder;
1564       if (__exponent != 0)
1565         {
1566           _CharT* __base_buffer =
1567             this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
1568           _RopeLeaf* __base_leaf;
1569           rope __base_rope;
1570           __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
1571                                    get_allocator());
1572           _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
1573           try
1574             {
1575               __base_leaf = _S_new_RopeLeaf(__base_buffer,
1576                                             __exponentiate_threshold, __a);
1577             }
1578           catch(...)
1579             {
1580               _RopeRep::__STL_FREE_STRING(__base_buffer,
1581                                           __exponentiate_threshold, __a);
1582               __throw_exception_again;
1583             }
1584           __base_rope._M_tree_ptr = __base_leaf;
1585           if (1 == __exponent)
1586             __result = __base_rope;
1587           else
1588             __result = power(__base_rope, __exponent,
1589                              _Rope_Concat_fn<_CharT, _Alloc>());
1590
1591           if (0 != __remainder)
1592             __result += __remainder_rope;
1593         }
1594       else
1595         __result = __remainder_rope;
1596
1597       this->_M_tree_ptr = __result._M_tree_ptr;
1598       this->_M_tree_ptr->_M_ref_nonnil();
1599     }
1600
1601   template<class _CharT, class _Alloc>
1602     _CharT
1603     rope<_CharT, _Alloc>::_S_empty_c_str[1];
1604
1605   template<class _CharT, class _Alloc>
1606     const _CharT*
1607     rope<_CharT, _Alloc>::
1608     c_str() const
1609     {
1610       if (0 == this->_M_tree_ptr)
1611         {
1612           _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
1613                                                    // but probably fast.
1614           return _S_empty_c_str;
1615         }
1616       __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
1617       __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
1618       if (0 == __result)
1619         {
1620           size_t __s = size();
1621           __result = this->_Data_allocate(__s + 1);
1622           _S_flatten(this->_M_tree_ptr, __result);
1623           __result[__s] = _S_eos((_CharT*)0);
1624           this->_M_tree_ptr->_M_c_string = __result;
1625         }
1626       __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
1627       return(__result);
1628     }
1629
1630   template<class _CharT, class _Alloc>
1631     const _CharT* rope<_CharT, _Alloc>::
1632     replace_with_c_str()
1633     {
1634       if (0 == this->_M_tree_ptr)
1635         {
1636           _S_empty_c_str[0] = _S_eos((_CharT*)0);
1637           return _S_empty_c_str;
1638         }
1639       __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
1640       if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag
1641           && 0 != __old_c_string)
1642         return(__old_c_string);
1643       size_t __s = size();
1644       _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
1645       _S_flatten(this->_M_tree_ptr, __result);
1646       __result[__s] = _S_eos((_CharT*)0);
1647       this->_M_tree_ptr->_M_unref_nonnil();
1648       this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
1649                                           this->get_allocator());
1650       return(__result);
1651     }
1652
1653   // Algorithm specializations.  More should be added.
1654
1655   template<class _Rope_iterator>  // was templated on CharT and Alloc
1656     void                          // VC++ workaround
1657     _Rope_rotate(_Rope_iterator __first,
1658                  _Rope_iterator __middle,
1659                  _Rope_iterator __last)
1660     {
1661       typedef typename _Rope_iterator::value_type _CharT;
1662       typedef typename _Rope_iterator::_allocator_type _Alloc;
1663
1664       rope<_CharT, _Alloc>& __r(__first.container());
1665       rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
1666       rope<_CharT, _Alloc> __suffix =
1667         __r.substr(__last.index(), __r.size() - __last.index());
1668       rope<_CharT, _Alloc> __part1 =
1669         __r.substr(__middle.index(), __last.index() - __middle.index());
1670       rope<_CharT, _Alloc> __part2 =
1671         __r.substr(__first.index(), __middle.index() - __first.index());
1672       __r = __prefix;
1673       __r += __part1;
1674       __r += __part2;
1675       __r += __suffix;
1676     }
1677
1678 #if !defined(__GNUC__)
1679   // Appears to confuse g++
1680   inline void
1681   rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first,
1682          _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle,
1683          _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last)
1684   { _Rope_rotate(__first, __middle, __last); }
1685 #endif
1686
1687 # if 0
1688   // Probably not useful for several reasons:
1689   // - for SGIs 7.1 compiler and probably some others,
1690   //   this forces lots of rope<wchar_t, ...> instantiations, creating a
1691   //   code bloat and compile time problem.  (Fixed in 7.2.)
1692   // - wchar_t is 4 bytes wide on most UNIX platforms, making it
1693   //   unattractive for unicode strings.  Unsigned short may be a better
1694   //   character type.
1695   inline void
1696   rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first,
1697          _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle,
1698          _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last)
1699   { _Rope_rotate(__first, __middle, __last); }
1700 # endif
1701
1702 } // namespace __gnu_cxx
1703
1704 // Local Variables:
1705 // mode:C++
1706 // End: