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