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