home *** CD-ROM | disk | FTP | other *** search
/ PC World 2000 January / PCWorld_2000-01_cd.bin / Software / Servis / Devc / _SETUP.4 / Group3 / ropeimpl.h < prev    next >
C/C++ Source or Header  |  1998-03-08  |  43KB  |  1,538 lines
  1. /*
  2.  * Copyright (c) 1997
  3.  * Silicon Graphics Computer Systems, Inc.
  4.  *
  5.  * Permission to use, copy, modify, distribute and sell this software
  6.  * and its documentation for any purpose is hereby granted without fee,
  7.  * provided that the above copyright notice appear in all copies and
  8.  * that both that copyright notice and this permission notice appear
  9.  * in supporting documentation.  Silicon Graphics makes no
  10.  * representations about the suitability of this software for any
  11.  * purpose.  It is provided "as is" without express or implied warranty.
  12.  */
  13.  
  14. /* NOTE: This is an internal header file, included by other STL headers.
  15.  *   You should not attempt to use it directly.
  16.  */
  17.  
  18. # include <stdio.h>
  19. # include <iostream.h>
  20.  
  21. __STL_BEGIN_NAMESPACE
  22.  
  23. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  24. #pragma set woff 1174
  25. #endif
  26.  
  27. // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
  28. // if necessary.  Assumes path_end[leaf_index] and leaf_pos are correct.
  29. // Results in a valid buf_ptr if the iterator can be legitimately
  30. // dereferenced.
  31. template <class charT, class Alloc>
  32. void __rope_iterator_base<charT,Alloc>::setbuf
  33. (__rope_iterator_base<charT,Alloc> &x)
  34. {
  35.     const RopeBase * leaf = x.path_end[x.leaf_index];
  36.     size_t leaf_pos = x.leaf_pos;
  37.     size_t pos = x.current_pos;
  38.  
  39.     switch(leaf -> tag) {
  40.     case RopeBase::leaf:
  41.         x.buf_start = ((__rope_RopeLeaf<charT,Alloc> *)leaf) -> data;
  42.         x.buf_ptr = x.buf_start + (pos - leaf_pos);
  43.         x.buf_end = x.buf_start + leaf -> size;
  44.         break;
  45.     case RopeBase::function:
  46.     case RopeBase::substringfn:
  47.         {
  48.         size_t len = iterator_buf_len;
  49.         size_t buf_start_pos = leaf_pos;
  50.         size_t leaf_end = leaf_pos + leaf -> size;
  51.         char_producer<charT> *fn =
  52.             ((__rope_RopeFunction<charT,Alloc> *)leaf) -> fn;
  53.  
  54.         if (buf_start_pos + len <= pos) {
  55.             buf_start_pos = pos - len/4;
  56.             if (buf_start_pos + len > leaf_end) {
  57.             buf_start_pos = leaf_end - len;
  58.             }
  59.         }
  60.         if (buf_start_pos + len > leaf_end) {
  61.             len = leaf_end - buf_start_pos;
  62.         }
  63.         (*fn)(buf_start_pos - leaf_pos, len, x.tmp_buf);
  64.         x.buf_ptr = x.tmp_buf + (pos - buf_start_pos);
  65.         x.buf_start = x.tmp_buf;
  66.         x.buf_end = x.tmp_buf + len;
  67.         }
  68.         break;
  69.     default:
  70.         __stl_assert(0);
  71.     }
  72. }
  73.  
  74. // Set path and buffer inside a rope iterator.  We assume that 
  75. // pos and root are already set.
  76. template <class charT, class Alloc>
  77. void __rope_iterator_base<charT,Alloc>::setcache
  78. (__rope_iterator_base<charT,Alloc> &x)
  79. {
  80.     const RopeBase * path[RopeBase::max_rope_depth+1];
  81.     const RopeBase * curr_rope;
  82.     int curr_depth = -1;  /* index into path    */
  83.     size_t curr_start_pos = 0;
  84.     size_t pos = x.current_pos;
  85.     unsigned char dirns = 0;    // Bit vector indicating right turns in the path
  86.  
  87.     __stl_assert(pos <= x.root -> size);
  88.     if (pos >= x.root -> size) {
  89.     x.buf_ptr = 0;
  90.     return;
  91.     }
  92.     curr_rope = x.root;
  93.     if (0 != curr_rope -> c_string) {
  94.     /* Treat the root as a leaf. */
  95.     x.buf_start = curr_rope -> c_string;
  96.     x.buf_end = curr_rope -> c_string + curr_rope -> size;
  97.     x.buf_ptr = curr_rope -> c_string + pos;
  98.     x.path_end[0] = curr_rope;
  99.     x.leaf_index = 0;
  100.     x.leaf_pos = 0;
  101.     return;
  102.     }
  103.     for(;;) {
  104.     ++curr_depth;
  105.     __stl_assert(curr_depth <= RopeBase::max_rope_depth);
  106.     path[curr_depth] = curr_rope;
  107.     switch(curr_rope -> tag) {
  108.       case RopeBase::leaf:
  109.       case RopeBase::function:
  110.       case RopeBase::substringfn:
  111.         x.leaf_pos = curr_start_pos;
  112.         goto done;
  113.       case RopeBase::concat:
  114.         {
  115.         __rope_RopeConcatenation<charT,Alloc> *c =
  116.             (__rope_RopeConcatenation<charT,Alloc> *)curr_rope;
  117.         RopeBase * left = c -> left;
  118.         size_t left_len = left -> size;
  119.         
  120.         dirns <<= 1;
  121.         if (pos >= curr_start_pos + left_len) {
  122.             dirns |= 1;
  123.             curr_rope = c -> right;
  124.             curr_start_pos += left_len;
  125.         } else {
  126.             curr_rope = left;
  127.         }
  128.         }
  129.         break;
  130.     }
  131.     }
  132.   done:
  133.     // Copy last section of path into path_end.
  134.       {
  135.     int i = -1;
  136.     int j = curr_depth  + 1 - path_cache_len;
  137.  
  138.     if (j < 0) j = 0;
  139.     while (j <= curr_depth) {
  140.         x.path_end[++i] = path[j++];
  141.     }
  142.     x.leaf_index = i;
  143.       }
  144.       x.path_directions = dirns;
  145.     setbuf(x);
  146. }
  147.  
  148. // Specialized version of the above.  Assumes that
  149. // the path cache is valid for the previous position.
  150. template <class charT, class Alloc>
  151. void __rope_iterator_base<charT,Alloc>::setcache_for_incr
  152. (__rope_iterator_base<charT,Alloc> &x)
  153. {
  154.     int current_index = x.leaf_index;
  155.     const RopeBase * current_node = x.path_end[current_index];
  156.     size_t len = current_node -> size;
  157.     size_t node_start_pos = x.leaf_pos;
  158.     unsigned char dirns = x.path_directions;
  159.     __rope_RopeConcatenation<charT,Alloc> * c;
  160.  
  161.     __stl_assert(x.current_pos <= x.root -> size);
  162.     if (x.current_pos - node_start_pos < len) {
  163.     /* More stuff in this leaf, we just didn't cache it. */
  164.     setbuf(x);
  165.     return;
  166.     }
  167.     __stl_assert(node_start_pos + len == x.current_pos);
  168.     //  node_start_pos is starting position of last_node.
  169.     while (--current_index >= 0) {
  170.     if (!(dirns & 1) /* Path turned left */) break;
  171.     current_node = x.path_end[current_index];
  172.     c = (__rope_RopeConcatenation<charT,Alloc> *)current_node;
  173.     // Otherwise we were in the right child.  Thus we should pop
  174.     // the concatenation node.
  175.     node_start_pos -= c -> left -> size;
  176.     dirns >>= 1;
  177.     }
  178.     if (current_index < 0) {
  179.     // We underflowed the cache. Punt.
  180.     setcache(x);
  181.     return;
  182.     }
  183.     current_node = x.path_end[current_index];
  184.     c = (__rope_RopeConcatenation<charT,Alloc> *)current_node;
  185.     // current_node is a concatenation node.  We are positioned on the first
  186.     // character in its right child.
  187.     // node_start_pos is starting position of current_node.
  188.     node_start_pos += c -> left -> size;
  189.     current_node = c -> right;
  190.     x.path_end[++current_index] = current_node;
  191.     dirns |= 1;
  192.     while (RopeBase::concat == current_node -> tag) {
  193.     ++current_index;
  194.     if (path_cache_len == current_index) {
  195.         int i;
  196.         for (i = 0; i < path_cache_len-1; i++) {
  197.         x.path_end[i] = x.path_end[i+1];
  198.         }
  199.         --current_index;
  200.     }
  201.     current_node =
  202.         ((__rope_RopeConcatenation<charT,Alloc> *)current_node) -> left;
  203.     x.path_end[current_index] = current_node;
  204.     dirns <<= 1;
  205.     // node_start_pos is unchanged.
  206.     }
  207.     x.leaf_index = current_index;
  208.     x.leaf_pos = node_start_pos;
  209.     x.path_directions = dirns;
  210.     setbuf(x);
  211. }
  212.  
  213. template <class charT, class Alloc>
  214. void __rope_iterator_base<charT,Alloc>::incr(size_t n) {
  215.     current_pos += n;
  216.     if (0 != buf_ptr) {
  217.         size_t chars_left = buf_end - buf_ptr;
  218.         if (chars_left > n) {
  219.             buf_ptr += n;
  220.         } else if (chars_left == n) {
  221.             buf_ptr += n;
  222.             setcache_for_incr(*this);
  223.         } else {
  224.             buf_ptr = 0;
  225.         }
  226.     }
  227. }
  228.  
  229. template <class charT, class Alloc>
  230. void __rope_iterator_base<charT,Alloc>::decr(size_t n) {
  231.     if (0 != buf_ptr) {
  232.         size_t chars_left = buf_ptr - buf_start;
  233.         if (chars_left >= n) {
  234.             buf_ptr -= n;
  235.         } else {
  236.             buf_ptr = 0;
  237.         }
  238.     }
  239.     current_pos -= n;
  240. }
  241.  
  242. template <class charT, class Alloc>
  243. void __rope_iterator<charT,Alloc>::check() {
  244.     if (root_rope -> tree_ptr != root) {
  245.         // Rope was modified.  Get things fixed up.
  246.         RopeBase::unref(root);
  247.         root = root_rope -> tree_ptr;
  248.         RopeBase::ref(root);
  249.         buf_ptr = 0;
  250.     }
  251. }
  252.  
  253. template <class charT, class Alloc>
  254. inline __rope_const_iterator<charT, Alloc>::__rope_const_iterator
  255. (const __rope_iterator<charT,Alloc> & x)
  256. : __rope_iterator_base<charT,Alloc>(x) { }
  257.  
  258. template <class charT, class Alloc>
  259. inline __rope_iterator<charT,Alloc>::__rope_iterator
  260. (rope<charT,Alloc>& r, size_t pos)
  261.         : __rope_iterator_base<charT,Alloc>(r.tree_ptr, pos), root_rope(&r) {
  262.     RopeBase::ref(root);
  263. }
  264.  
  265. template <class charT, class Alloc>
  266. inline size_t rope<charT,Alloc>::char_ptr_len(const charT *s)
  267. {
  268.     const charT *p = s;
  269.  
  270.     while (!is0(*p)) { ++p; }
  271.     return(p - s);
  272. }
  273.  
  274. template <class charT, class Alloc>
  275. rope<charT,Alloc>::RopeLeaf *
  276. rope<charT,Alloc>::RopeLeaf_from_char_ptr(__GC_CONST charT *s, size_t size)
  277. {
  278.     RopeLeaf *t = LAlloc::allocate();
  279.  
  280.     t -> tag = RopeBase::leaf;
  281.     if (__is_basic_char_type((charT *)0)) {
  282.     // already eos terminated.
  283.     t -> c_string = s;
  284.     } else {
  285.     t -> c_string = 0;
  286.     }
  287.     t -> is_balanced = true;
  288.     t -> depth = 0;
  289.     t -> size = size;
  290.     t -> data = s;
  291. #   ifndef __GC
  292.     t -> refcount = 1;
  293.     t -> init_refcount_lock();
  294. #   endif
  295.     return (t);
  296. }
  297.  
  298. # ifdef __GC
  299. template <class charT, class Alloc>
  300. void __rope_RopeBase<charT,Alloc>::fn_finalization_proc(void * tree, void *)
  301. {
  302.     delete ((__rope_RopeFunction<charT,Alloc> *)tree) -> fn;
  303. }
  304. # endif
  305.  
  306. template <class charT, class Alloc>
  307. rope<charT,Alloc>::RopeFunction *
  308. rope<charT,Alloc>::RopeFunction_from_fn
  309. (char_producer<charT> *fn, size_t size, bool delete_fn)
  310. {
  311.     if (0 == size) return 0;
  312.     RopeFunction *t = FAlloc::allocate();
  313.     t -> tag = RopeBase::function;
  314.     t -> c_string = 0;
  315.     t -> is_balanced = true;
  316.     t -> depth = 0;
  317.     t -> size = size;
  318.     t -> fn = fn;
  319. #   ifdef __GC
  320.     if (delete_fn) {
  321.         GC_REGISTER_FINALIZER(t, RopeBase::fn_finalization_proc, 0, 0, 0);
  322.     }
  323. #   else
  324.     t -> delete_when_done = delete_fn;
  325.     t -> refcount = 1;
  326.     t -> init_refcount_lock();
  327. #   endif
  328.     return (t);
  329. }
  330.  
  331. #ifndef __GC
  332.  
  333. template <class charT, class Alloc>
  334. inline void __rope_RopeBase<charT,Alloc>::free_c_string()
  335. {
  336.     charT * cstr = c_string;
  337.     if (0 != cstr) {
  338.     size_t sz = size + 1;
  339.     destroy(cstr, cstr + sz);
  340.     DataAlloc::deallocate(cstr, sz);
  341.     }
  342. }
  343.  
  344. template <class charT, class Alloc>
  345. inline void __rope_RopeBase<charT,Alloc>::free_string(charT* s, size_t n)
  346. {
  347.     if (!__is_basic_char_type((charT *)0)) {
  348.     destroy(s, s + n);
  349.     }
  350.     DataAlloc::deallocate(s, rounded_up_size(n));
  351. }
  352.  
  353. template <class charT, class Alloc>
  354. void __rope_RopeBase<charT,Alloc>::free_tree()
  355. {
  356.     switch(tag) {
  357.     case leaf:
  358.         {
  359.             __rope_RopeLeaf<charT,Alloc> * l =
  360.             (__rope_RopeLeaf<charT,Alloc> *)this;
  361.         charT * d = l -> data;
  362.         
  363.         if (d != c_string) {
  364.             free_c_string();
  365.         }
  366.         free_string(d, size);
  367.         LAlloc::deallocate(l);
  368.         }
  369.         break;
  370.     case concat:
  371.         {
  372.         __rope_RopeConcatenation<charT,Alloc> * c =
  373.             (__rope_RopeConcatenation<charT,Alloc> *)this;
  374.         __rope_RopeBase * left = c -> left;
  375.         __rope_RopeBase * right = c -> right;
  376.         free_c_string();
  377.         left -> unref_nonnil();
  378.         right -> unref_nonnil();
  379.         CAlloc::deallocate(c);
  380.         }
  381.         break;
  382.     case function:
  383.         {
  384.         __rope_RopeFunction<charT,Alloc> * fn =
  385.               (__rope_RopeFunction<charT,Alloc> *)this;
  386.             free_c_string();
  387.             if ( fn -> delete_when_done) {
  388.             delete fn -> fn;
  389.             }
  390.             FAlloc::deallocate(fn);
  391.             break;
  392.         }
  393.     case substringfn:
  394.         {
  395.             __rope_RopeSubstring<charT,Alloc> * ss =
  396.             (__rope_RopeSubstring<charT,Alloc> *)this;
  397.         __rope_RopeBase *base = ss -> base;
  398.         free_c_string();
  399.         base -> unref_nonnil();
  400.         SAlloc::deallocate(ss);
  401.         break;
  402.         }
  403.     }
  404. }
  405. #else
  406.  
  407. template <class charT, class Alloc>
  408. inline void __rope_RopeBase<charT,Alloc>::free_string(charT* s, size_t n)
  409. {}
  410.  
  411. #endif
  412.  
  413.  
  414. // Concatenate a C string onto a leaf rope by copying the rope data.
  415. // Used for short ropes.
  416. template <class charT, class Alloc>
  417. rope<charT,Alloc>::RopeLeaf *
  418. rope<charT,Alloc>::leaf_concat_char_iter
  419.         (RopeLeaf * r, const charT * iter, size_t len)
  420. {
  421.     size_t old_len = r -> size;
  422.     charT * new_data = (charT *)
  423.     DataAlloc::allocate(rounded_up_size(old_len + len));
  424.     RopeLeaf * result;
  425.     
  426.     uninitialized_copy_n(r -> data, old_len, new_data);
  427.     uninitialized_copy_n(iter, len, new_data + old_len);
  428.     __cond_store_eos(new_data[old_len + len]);
  429.     __STL_TRY {
  430.     result = RopeLeaf_from_char_ptr(new_data, old_len + len);
  431.     }
  432.     __STL_UNWIND(RopeBase::free_string(new_data, old_len + len));
  433.     return result;
  434. }
  435.  
  436. #ifndef __GC
  437. // As above, but it's OK to clobber original if refcount is 1
  438. template <class charT, class Alloc>
  439. rope<charT,Alloc>::RopeLeaf *
  440. rope<charT,Alloc>::destr_leaf_concat_char_iter
  441.         (RopeLeaf * r, const charT * iter, size_t len)
  442. {
  443.     __stl_assert(r -> refcount >= 1);
  444.     if (r -> refcount > 1) return leaf_concat_char_iter(r, iter, len);
  445.     size_t old_len = r -> size;
  446.     if (allocated_capacity(old_len) >= old_len + len) {
  447.     // The space has been partially initialized for the standard
  448.     // character types.  But that doesn't matter for those types.
  449.     uninitialized_copy_n(iter, len, r -> data + old_len);
  450.     if (__is_basic_char_type((charT *)0)) {
  451.         __cond_store_eos(r -> data[old_len + len]);
  452.         __stl_assert(r -> c_string == r -> data);
  453.     } else if (r -> c_string != r -> data && 0 != r -> c_string) {
  454.         r -> free_c_string();
  455.         r -> c_string = 0;
  456.     }
  457.     r -> size = old_len + len;
  458.     __stl_assert(r -> refcount == 1);
  459.     r -> refcount = 2;
  460.     return r;
  461.     } else {
  462.     RopeLeaf * result = leaf_concat_char_iter(r, iter, len);
  463.     __stl_assert(result -> refcount == 1);
  464.     return result;
  465.     }
  466. }
  467. #endif
  468.  
  469. // Assumes left and right are not 0.
  470. // Does not increment (nor decrement on exception) child reference counts.
  471. // Result has ref count 1.
  472. template <class charT, class Alloc>
  473. rope<charT,Alloc>::RopeBase *
  474. rope<charT,Alloc>::tree_concat (RopeBase * left, RopeBase * right)
  475. {
  476.     RopeConcatenation * result = CAlloc::allocate();
  477.     unsigned char child_depth = left -> depth;
  478.     size_t rsize;
  479.  
  480.     result -> tag = RopeBase::concat;
  481.     result -> c_string = 0;
  482.     result -> is_balanced = false;
  483.     result -> size = rsize = left -> size + right -> size;
  484.     if (right -> depth > child_depth) child_depth = right -> depth;
  485.     unsigned char depth = (unsigned char)(child_depth + 1);
  486.     result -> depth = depth;
  487.     result -> left = left;
  488.     result -> right = right;
  489. #   ifndef __GC
  490.     result -> refcount = 1;
  491.     result -> init_refcount_lock();
  492. #   endif
  493.     if (depth > 20 && (rsize < 1000 || depth > RopeBase::max_rope_depth)) {
  494.     RopeBase * balanced;
  495.  
  496.     __STL_TRY {
  497.        balanced = balance(result);
  498. #          ifndef __GC
  499.          if (result != balanced) {
  500.         __stl_assert(1 == result -> refcount
  501.                  && 1 == balanced -> refcount);
  502.          }
  503. #          endif
  504.        result -> unref_nonnil();
  505.         }
  506.     __STL_UNWIND(CAlloc::deallocate(result));
  507.         // In case of exception, we need to deallocate
  508.         // otherwise dangling result node.  But caller
  509.         // still owns its children.  Thus unref is
  510.         // inappropriate.
  511.     return balanced;
  512.     } else {
  513.     return result;
  514.     }
  515. }
  516.  
  517. template <class charT, class Alloc>
  518. rope<charT,Alloc>::RopeBase * rope<charT,Alloc>::concat_char_iter
  519.         (RopeBase * r, const charT *s, size_t slen)
  520. {
  521.     RopeBase *result;
  522.     if (0 == slen) {
  523.     ref(r);
  524.     return r;
  525.     }
  526.     if (0 == r) return RopeLeaf_from_unowned_char_ptr(s, slen);
  527.     if (RopeBase::leaf == r -> tag && r -> size + slen <= copy_max) {
  528.     result = leaf_concat_char_iter((RopeLeaf *)r, s, slen);
  529. #       ifndef __GC
  530.       __stl_assert(1 == result -> refcount);
  531. #       endif
  532.     return result;
  533.     }
  534.     if (RopeBase::concat == r -> tag
  535.     && RopeBase::leaf == ((RopeConcatenation *)r) -> right -> tag) {
  536.     RopeLeaf *right = (RopeLeaf *)(((RopeConcatenation *)r) -> right);
  537.     if (right -> size + slen <= copy_max) {
  538.       RopeBase * left = ((RopeConcatenation *)r) -> left;
  539.       RopeBase * nright = leaf_concat_char_iter((RopeLeaf *)right, s, slen);
  540.       left -> ref_nonnil();
  541.       __STL_TRY {
  542.         result = tree_concat(left, nright);
  543.           }
  544.       __STL_UNWIND(unref(left); unref(nright));
  545. #         ifndef __GC
  546.         __stl_assert(1 == result -> refcount);
  547. #         endif
  548.       return result;
  549.     }
  550.     }
  551.     RopeBase * nright = RopeLeaf_from_unowned_char_ptr(s, slen);
  552.     __STL_TRY {
  553.       r -> ref_nonnil();
  554.       result = tree_concat(r, nright);
  555.     }
  556.     __STL_UNWIND(unref(r); unref(nright));
  557. #   ifndef __GC
  558.       __stl_assert(1 == result -> refcount);
  559. #   endif
  560.     return result;
  561. }
  562.  
  563. #ifndef __GC
  564. template <class charT, class Alloc>
  565. rope<charT,Alloc>::RopeBase * rope<charT,Alloc>
  566. ::destr_concat_char_iter
  567.         (RopeBase * r, const charT *s, size_t slen)
  568. {
  569.     RopeBase *result;
  570.     if (0 == r) return RopeLeaf_from_unowned_char_ptr(s, slen);
  571.     size_t count = r -> refcount;
  572.     size_t orig_size = r -> size;
  573.     __stl_assert(count >= 1);
  574.     if (count > 1) return concat_char_iter(r, s, slen);
  575.     if (0 == slen) {
  576.     r -> refcount = 2;      // One more than before
  577.     return r;
  578.     }
  579.     if (orig_size + slen <= copy_max && RopeBase::leaf == r -> tag) {
  580.     result = destr_leaf_concat_char_iter((RopeLeaf *)r, s, slen);
  581.     return result;
  582.     }
  583.     if (RopeBase::concat == r -> tag) {
  584.     RopeLeaf *right = (RopeLeaf *)(((RopeConcatenation *)r) -> right);
  585.     if (RopeBase::leaf == right -> tag
  586.         && right -> size + slen <= copy_max) {
  587.       RopeBase * new_right = destr_leaf_concat_char_iter(right, s, slen);
  588.       if (right == new_right) {
  589.           __stl_assert(new_right -> refcount == 2);
  590.           new_right -> refcount = 1;
  591.       } else {
  592.           __stl_assert(new_right -> refcount >= 1);
  593.           right -> unref_nonnil();
  594.       }
  595.       __stl_assert(r -> refcount == 1);
  596.       r -> refcount = 2;    // One more than before.
  597.       ((RopeConcatenation *)r) -> right = new_right;
  598.       r -> size = orig_size + slen;
  599.       if (0 != r -> c_string) {
  600.           r -> free_c_string();
  601.           r -> c_string = 0;
  602.       }
  603.       return r;
  604.     }
  605.     }
  606.     RopeBase *right = RopeLeaf_from_unowned_char_ptr(s, slen);
  607.     r -> ref_nonnil();
  608.     __STL_TRY {
  609.       result = tree_concat(r, right);
  610.     }
  611.     __STL_UNWIND(unref(r); unref(right))
  612.     __stl_assert(1 == result -> refcount);
  613.     return result;
  614. }
  615. #endif /* !__GC */
  616.  
  617. template <class charT, class Alloc>
  618. rope<charT,Alloc>::RopeBase *
  619. rope<charT,Alloc>::concat(RopeBase * left, RopeBase * right)
  620. {
  621.     if (0 == left) {
  622.     ref(right);
  623.     return right;
  624.     }
  625.     if (0 == right) {
  626.     left -> ref_nonnil();
  627.     return left;
  628.     }
  629.     if (RopeBase::leaf == right -> tag) {
  630.     if (RopeBase::leaf == left -> tag) {
  631.       if (right -> size + left -> size <= copy_max) {
  632.         return leaf_concat_char_iter((RopeLeaf *)left,
  633.                      ((RopeLeaf *)right) -> data,
  634.                      right -> size);
  635.       }
  636.     } else if (RopeBase::concat == left -> tag
  637.            && RopeBase::leaf ==
  638.               ((RopeConcatenation *)left) -> right -> tag) {
  639.       RopeLeaf * leftright =
  640.             (RopeLeaf *)(((RopeConcatenation *)left) -> right); 
  641.       if (leftright -> size + right -> size <= copy_max) {
  642.         RopeBase * leftleft = ((RopeConcatenation *)left) -> left;
  643.         RopeBase * rest = leaf_concat_char_iter(leftright,
  644.                        ((RopeLeaf *)right) -> data,
  645.                        right -> size);
  646.         leftleft -> ref_nonnil();
  647.         __STL_TRY {
  648.           return(tree_concat(leftleft, rest));
  649.             }
  650.         __STL_UNWIND(unref(leftleft); unref(rest))
  651.       }
  652.     }
  653.     }
  654.     left -> ref_nonnil();
  655.     right -> ref_nonnil();
  656.     __STL_TRY {
  657.       return(tree_concat(left, right));
  658.     }
  659.     __STL_UNWIND(unref(left); unref(right));
  660. }
  661.  
  662. template <class charT, class Alloc>
  663. rope<charT,Alloc>::RopeBase *
  664. rope<charT,Alloc>::substring(RopeBase * base, size_t start, size_t endp1)
  665. {
  666.     if (0 == base) return 0;
  667.     size_t len = base -> size;
  668.     size_t adj_endp1;
  669.     const size_t lazy_threshold = 128;
  670.     
  671.     if (endp1 >= len) {
  672.     if (0 == start) {
  673.         base -> ref_nonnil();
  674.         return base;
  675.     } else {
  676.         adj_endp1 = len;
  677.     }
  678.     } else {
  679.     adj_endp1 = endp1;
  680.     }
  681.     switch(base -> tag) {
  682.     case RopeBase::concat:
  683.         {
  684.         RopeConcatenation *c = (RopeConcatenation *)base;
  685.         RopeBase *left = c -> left;
  686.         RopeBase *right = c -> right;
  687.         size_t left_len = left -> size;
  688.         RopeBase * result;
  689.  
  690.         if (adj_endp1 <= left_len) {
  691.             return substring(left, start, endp1);
  692.         } else if (start >= left_len) {
  693.             return substring(right, start - left_len,
  694.                   adj_endp1 - left_len);
  695.         }
  696.         self_destruct_ptr left_result(substring(left, start,
  697.                             left_len));
  698.         self_destruct_ptr right_result(
  699.                 substring(right, 0, endp1 - left_len));
  700.         result = concat(left_result, right_result);
  701. #               ifndef __GC
  702.           __stl_assert(1 == result -> refcount);
  703. #               endif
  704.         return result;
  705.         }
  706.     case RopeBase::leaf:
  707.         {
  708.         RopeLeaf * l = (RopeLeaf *)base;
  709.         RopeLeaf * result;
  710.         size_t result_len;
  711.         if (start >= adj_endp1) return 0;
  712.         result_len = adj_endp1 - start;
  713.         if (result_len > lazy_threshold) goto lazy;
  714. #               ifdef __GC
  715.             const charT *section = l -> data + start;
  716.             result = RopeLeaf_from_char_ptr(section, result_len);
  717.             result -> c_string = 0;  // Not eos terminated.
  718. #               else
  719.             // We should sometimes create substring node instead.
  720.             result = RopeLeaf_from_unowned_char_ptr(
  721.                     l -> data + start, result_len);
  722. #               endif
  723.         return result;
  724.         }
  725.     case RopeBase::substringfn:
  726.         // Avoid introducing mutiple layers of substring nodes.
  727.         {
  728.         RopeSubstring *old = (RopeSubstring *)base;
  729.         size_t result_len;
  730.         if (start >= adj_endp1) return 0;
  731.         result_len = adj_endp1 - start;
  732.         if (result_len > lazy_threshold) {
  733.             RopeSubstring * space = SAlloc::allocate();
  734.             RopeSubstring * result =
  735.             new(space) RopeSubstring(old -> base,
  736.                          start + old -> start,
  737.                          adj_endp1 - start);
  738.             return result;
  739.         } // else fall through:
  740.         }
  741.     case RopeBase::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.             DataAlloc::allocate(rounded_up_size(result_len));
  752.         __STL_TRY {
  753.           (*(f -> fn))(start, result_len, section);
  754.                 }
  755.         __STL_UNWIND(RopeBase::free_string(section, result_len));
  756.         __cond_store_eos(section[result_len]);
  757.         return RopeLeaf_from_char_ptr(section, result_len);
  758.         }
  759.     }
  760.     /*NOTREACHED*/
  761.     __stl_assert(false);
  762.   lazy:
  763.     {
  764.     // Create substring node.
  765.     RopeSubstring * space = SAlloc::allocate();
  766.     RopeSubstring * result = new(space) RopeSubstring(base, start,
  767.                               adj_endp1 - start);
  768.     return result;
  769.     }
  770. }
  771.  
  772. template<class charT>
  773. class __rope_flatten_char_consumer : public __rope_char_consumer<charT> {
  774.     private:
  775.     charT * buf_ptr;
  776.     public:
  777.     charT * buffer;
  778.     __rope_flatten_char_consumer(charT * buffer) {
  779.         buf_ptr = buffer;
  780.     };
  781.     ~__rope_flatten_char_consumer() {}
  782.     bool operator() (const charT* leaf, size_t n) {
  783.         uninitialized_copy_n(leaf, n, buf_ptr);
  784.         buf_ptr += n;
  785.         return true;
  786.     }
  787. };
  788.         
  789. template<class charT>
  790. class __rope_find_char_char_consumer : public __rope_char_consumer<charT> {
  791.     private:
  792.     charT pattern;
  793.     public:
  794.     size_t count;  // Number of nonmatching characters
  795.     __rope_find_char_char_consumer(charT p) : pattern(p), count(0) {}
  796.     ~__rope_find_char_char_consumer() {}
  797.     bool operator() (const charT* leaf, size_t n) {
  798.         size_t i;
  799.         for (i = 0; i < n; i++) {
  800.         if (leaf[i] == pattern) {
  801.             count += i; return false;
  802.         }
  803.         }
  804.         count += n; return true;
  805.     }
  806. };
  807.         
  808. template<class charT>
  809. class __rope_insert_char_consumer : public __rope_char_consumer<charT> {
  810.     private:
  811.     typedef ostream insert_ostream;
  812.     insert_ostream & o;
  813.     public:
  814.     charT * buffer;
  815.     __rope_insert_char_consumer(insert_ostream & writer) : o(writer) {};
  816.     ~__rope_insert_char_consumer() { };
  817.         // Caller is presumed to own the ostream
  818.     bool operator() (const charT* leaf, size_t n);
  819.         // Returns true to continue traversal.
  820. };
  821.         
  822. template<class charT>
  823. bool __rope_insert_char_consumer<charT>::operator()
  824.                     (const charT * leaf, size_t n)
  825. {
  826.     size_t i;
  827.     //  We assume that formatting is set up correctly for each element.
  828.     for (i = 0; i < n; i++) o << leaf[i];
  829.     return true;
  830. }
  831.  
  832. inline bool __rope_insert_char_consumer<char>::operator()
  833.                     (const char * leaf, size_t n)
  834. {
  835.     size_t i;
  836.     for (i = 0; i < n; i++) o.put(leaf[i]);
  837.     return true;
  838. }
  839.  
  840. #if !defined(_MSC_VER) && !defined(__BORLANDC__)
  841. // I couldn't get this to work work with the VC++ version of basic_ostream.
  842. inline bool __rope_insert_char_consumer<wchar_t>::operator()
  843.                     (const wchar_t * leaf, size_t n)
  844. {
  845.     size_t i;
  846.     for (i = 0; i < n; i++) o.put(leaf[i]);
  847.     return true;
  848. }
  849. #endif /* !_MSC_VER  && !BORLAND */
  850.  
  851. template <class charT, class Alloc>
  852. bool rope<charT, Alloc>::apply_to_pieces(
  853.                 __rope_char_consumer<charT>& c,
  854.                 const RopeBase * r,
  855.                 size_t begin, size_t end)
  856. {
  857.     if (0 == r) return true;
  858.     switch(r -> tag) {
  859.     case RopeBase::concat:
  860.         {
  861.         RopeConcatenation *conc = (RopeConcatenation *)r;
  862.         RopeBase *left = conc -> left;
  863.         size_t left_len = left -> size;
  864.         if (begin < left_len) {
  865.             size_t left_end = min(left_len, end);
  866.             if (!apply_to_pieces(c, left, begin, left_end)) {
  867.             return false;
  868.             }
  869.         }
  870.         if (end > left_len) {
  871.             RopeBase *right = conc -> right;
  872.             size_t right_start = max(left_len, begin);
  873.             if (!apply_to_pieces(c, right,
  874.                      right_start - left_len,
  875.                      end - left_len)) {
  876.             return false;
  877.             }
  878.         }
  879.         }
  880.         return true;
  881.     case RopeBase::leaf:
  882.         {
  883.         RopeLeaf * l = (RopeLeaf *)r;
  884.         return c(l -> data + begin, end - begin);
  885.         }
  886.     case RopeBase::function:
  887.     case RopeBase::substringfn:
  888.         {
  889.         RopeFunction * f = (RopeFunction *)r;
  890.         size_t len = end - begin;
  891.         bool result;
  892.         charT * buffer = DataAlloc::allocate(len);
  893.         __STL_TRY {
  894.           (*(f -> fn))(begin, end, buffer);
  895.           result = c(buffer, len);
  896.                   DataAlloc::deallocate(buffer, len);
  897.                 }
  898.         __STL_UNWIND(DataAlloc::deallocate(buffer, len))
  899.         return result;
  900.         }
  901.     default:
  902.         __stl_assert(false);
  903.         /*NOTREACHED*/
  904.         return false;
  905.     }
  906. }
  907.  
  908. inline void __rope_fill(ostream& o, size_t n)
  909. {
  910.     char f = o.fill();
  911.     size_t i;
  912.  
  913.     for (i = 0; i < n; i++) o.put(f);
  914. }
  915.     
  916.  
  917. template <class charT> inline bool __rope_is_simple(charT *) { return false; }
  918. inline bool __rope_is_simple(char *) { return true; }
  919. inline bool __rope_is_simple(wchar_t *) { return true; }
  920.  
  921.  
  922. template<class charT, class Alloc>
  923. ostream& operator<< (ostream& o, const rope<charT, Alloc>& r)
  924. {
  925.     size_t w = o.width();
  926.     bool left = bool(o.flags() & ios::left);
  927.     size_t pad_len;
  928.     size_t rope_len = r.size();
  929.     __rope_insert_char_consumer<charT> c(o);
  930.     bool is_simple = __rope_is_simple((charT *)0);
  931.     
  932.     if (rope_len < w) {
  933.     pad_len = w - rope_len;
  934.     } else {
  935.     pad_len = 0;
  936.     }
  937.     if (!is_simple) o.width(w/rope_len);
  938.     __STL_TRY {
  939.       if (is_simple && !left && pad_len > 0) {
  940.     __rope_fill(o, pad_len);
  941.       }
  942.       r.apply_to_pieces(0, r.size(), c);
  943.       if (is_simple && left && pad_len > 0) {
  944.     __rope_fill(o, pad_len);
  945.       }
  946.       if (!is_simple)
  947.         o.width(w);
  948.     }
  949.     __STL_UNWIND(if (!is_simple) o.width(w))
  950.     return o;
  951. }
  952.  
  953. template <class charT, class Alloc>
  954. charT *
  955. rope<charT,Alloc>::flatten(RopeBase * r,
  956.                  size_t start, size_t len,
  957.                  charT * buffer)
  958. {
  959.     __rope_flatten_char_consumer<charT> c(buffer);
  960.     apply_to_pieces(c, r, start, start + len);
  961.     return(buffer + len);
  962. }
  963.  
  964. template <class charT, class Alloc>
  965. size_t
  966. rope<charT,Alloc>::find(charT pattern, size_t start) const
  967. {
  968.     __rope_find_char_char_consumer<charT> c(pattern);
  969.     apply_to_pieces(c, tree_ptr, start, size());
  970.     return start + c.count;
  971. }
  972.  
  973. template <class charT, class Alloc>
  974. charT *
  975. rope<charT,Alloc>::flatten(RopeBase * r, charT * buffer)
  976. {
  977.     if (0 == r) return buffer;
  978.     switch(r -> tag) {
  979.     case RopeBase::concat:
  980.         {
  981.         RopeConcatenation *c = (RopeConcatenation *)r;
  982.         RopeBase *left = c -> left;
  983.         RopeBase *right = c -> right;
  984.         charT * rest = flatten(left, buffer);
  985.         return flatten(right, rest);
  986.         }
  987.     case RopeBase::leaf:
  988.         {
  989.         RopeLeaf * l = (RopeLeaf *)r;
  990.         return copy_n(l -> data, l -> size, buffer).second;
  991.         }
  992.     case RopeBase::function:
  993.     case RopeBase::substringfn:
  994.         // We dont yet do anything with substring nodes.
  995.         // This needs to be fixed before ropefiles will work well.
  996.         {
  997.         RopeFunction * f = (RopeFunction *)r;
  998.         (*(f -> fn))(0, f -> size, buffer);
  999.         return buffer + f -> size;
  1000.         }
  1001.     default:
  1002.         __stl_assert(false);
  1003.         /*NOTREACHED*/
  1004.         return 0;
  1005.     }
  1006. }
  1007.  
  1008.  
  1009. // This needs work for charT != char
  1010. template <class charT, class Alloc>
  1011. void
  1012. rope<charT,Alloc>::dump(RopeBase * r, int indent)
  1013. {
  1014.     for (int i = 0; i < indent; i++) putchar(' ');
  1015.     if (0 == r) {
  1016.     printf("NULL\n"); return;
  1017.     }
  1018.     if (RopeBase::concat == r -> tag) {
  1019.     RopeConcatenation *c = (RopeConcatenation *)r;
  1020.     RopeBase *left = c -> left;
  1021.     RopeBase *right = c -> right;
  1022.  
  1023. #       ifdef __GC
  1024.       printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
  1025.          r, r -> depth, r -> size, r -> is_balanced? "" : "not");
  1026. #       else
  1027.       printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
  1028.          r, r -> refcount, r -> depth, r -> size,
  1029.          r -> is_balanced? "" : "not");
  1030. #       endif
  1031.     dump(left, indent + 2);
  1032.     dump(right, indent + 2);
  1033.     return;
  1034.     } else {
  1035.     char * kind;
  1036.  
  1037.     switch (r -> tag) {
  1038.         case RopeBase::leaf:
  1039.         kind = "Leaf";
  1040.         break;
  1041.         case RopeBase::function:
  1042.         kind = "Function";
  1043.         break;
  1044.         case RopeBase::substringfn:
  1045.         kind = "Function representing substring";
  1046.         break;
  1047.         default:
  1048.         kind = "(corrupted kind field!)";
  1049.     }
  1050. #       ifdef __GC
  1051.       printf("%s %p (depth = %d, len = %ld) ",
  1052.          kind, r, r -> depth, r -> size);
  1053. #       else
  1054.       printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
  1055.          kind, r, r -> refcount, r -> depth, r -> size);
  1056. #       endif
  1057.     if (__is_one_byte_char_type((charT *)0)) {
  1058.         const int max_len = 40;
  1059.         self_destruct_ptr prefix(substring(r, 0, max_len));
  1060.         charT buffer[max_len + 1];
  1061.         bool too_big = r -> size > prefix-> size;
  1062.  
  1063.         flatten(prefix, buffer);
  1064.         buffer[prefix -> size] = __eos((charT *)0); 
  1065.         printf("%s%s\n", (char *)buffer, too_big? "...\n" : "\n");
  1066.     } else {
  1067.         printf("\n");
  1068.     }
  1069.     }
  1070. }
  1071.  
  1072. template <class charT, class Alloc>
  1073. const unsigned long
  1074. rope<charT,Alloc>::min_len[__rope_RopeBase<charT,Alloc>::max_rope_depth + 1] = {
  1075. /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
  1076. /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
  1077. /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
  1078. /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
  1079. /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
  1080. /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
  1081. /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
  1082. /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
  1083. /* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
  1084. /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
  1085. /* 45 */2971215073 };
  1086. // These are Fibonacci numbers < 2**32.
  1087.  
  1088. template <class charT, class Alloc>
  1089. rope<charT,Alloc>::RopeBase *
  1090. rope<charT,Alloc>::balance(RopeBase *r)
  1091. {
  1092.     RopeBase * forest[RopeBase::max_rope_depth + 1];
  1093.     RopeBase * result = 0;
  1094.     int i;
  1095.     // Inariant:
  1096.     // The concatenation of forest in descending order is equal to r.
  1097.     // forest[i].size >= min_len[i]
  1098.     // forest[i].depth = i
  1099.     // References from forest are included in refcount.
  1100.  
  1101.     for (i = 0; i <= RopeBase::max_rope_depth; ++i) forest[i] = 0;
  1102.     __STL_TRY {
  1103.       add_to_forest(r, forest);
  1104.       for (i = 0; i <= RopeBase::max_rope_depth; ++i) if (0 != forest[i]) {
  1105. #    ifndef __GC
  1106.       self_destruct_ptr old(result);
  1107. #    endif
  1108.     result = concat(forest[i], result);
  1109.     forest[i] -> unref_nonnil();
  1110. #    if !defined(__GC) && defined(__STL_USE_EXCEPTIONS)
  1111.       forest[i] = 0;
  1112. #    endif
  1113.       }
  1114.     }
  1115.     __STL_UNWIND(for(i = 0; i <= RopeBase::max_rope_depth; i++)
  1116.          unref(forest[i]))
  1117.     if (result -> depth > RopeBase::max_rope_depth) abort();
  1118.     return(result);
  1119. }
  1120.  
  1121.  
  1122. template <class charT, class Alloc>
  1123. void
  1124. rope<charT,Alloc>::add_to_forest(RopeBase *r, RopeBase **forest)
  1125. {
  1126.     if (r -> is_balanced) {
  1127.     add_leaf_to_forest(r, forest);
  1128.     return;
  1129.     }
  1130.     __stl_assert(r -> tag == RopeBase::concat);
  1131.     {
  1132.     RopeConcatenation *c = (RopeConcatenation *)r;
  1133.  
  1134.     add_to_forest(c -> left, forest);
  1135.     add_to_forest(c -> right, forest);
  1136.     }
  1137. }
  1138.  
  1139.  
  1140. template <class charT, class Alloc>
  1141. void
  1142. rope<charT,Alloc>::add_leaf_to_forest(RopeBase *r, RopeBase **forest)
  1143. {
  1144.     RopeBase * insertee;           // included in refcount
  1145.     RopeBase * too_tiny = 0;        // included in refcount
  1146.     int i;                  // forest[0..i-1] is empty
  1147.     size_t s = r -> size;
  1148.  
  1149.     for (i = 0; s >= min_len[i+1]/* not this bucket */; ++i) {
  1150.     if (0 != forest[i]) {
  1151. #        ifndef __GC
  1152.           self_destruct_ptr old(too_tiny);
  1153. #        endif
  1154.         too_tiny = concat_and_set_balanced(forest[i], too_tiny);
  1155.         forest[i] -> unref_nonnil();
  1156.         forest[i] = 0;
  1157.     }
  1158.     }
  1159.     {
  1160. #    ifndef __GC
  1161.       self_destruct_ptr old(too_tiny);
  1162. #    endif
  1163.     insertee = concat_and_set_balanced(too_tiny, r);
  1164.     }
  1165.     // Too_tiny dead, and no longer included in refcount.
  1166.     // Insertee is live and included.
  1167.     __stl_assert(is_almost_balanced(insertee));
  1168.     __stl_assert(insertee -> depth <= r -> depth + 1);
  1169.     for (;; ++i) {
  1170.     if (0 != forest[i]) {
  1171. #        ifndef __GC
  1172.           self_destruct_ptr old(insertee);
  1173. #        endif
  1174.         insertee = concat_and_set_balanced(forest[i], insertee);
  1175.         forest[i] -> unref_nonnil();
  1176.         forest[i] = 0;
  1177.         __stl_assert(is_almost_balanced(insertee));
  1178.     }
  1179.     __stl_assert(min_len[i] <= insertee -> size);
  1180.     __stl_assert(forest[i] == 0);
  1181.     if (i == RopeBase::max_rope_depth
  1182.         || insertee -> size < 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>::fetch(RopeBase *r, size_type i)
  1193. {
  1194.     __GC_CONST charT * cstr = r -> c_string;
  1195.  
  1196.     __stl_assert(i < r -> size);
  1197.     if (0 != cstr) return cstr[i]; 
  1198.     for(;;) {
  1199.       switch(r -> tag) {
  1200.     case RopeBase::concat:
  1201.         {
  1202.         RopeConcatenation *c = (RopeConcatenation *)r;
  1203.         RopeBase *left = c -> left;
  1204.         size_t left_len = left -> size;
  1205.  
  1206.         if (i >= left_len) {
  1207.             i -= left_len;
  1208.             r = c -> right;
  1209.         } else {
  1210.             r = left;
  1211.         }
  1212.         }
  1213.         break;
  1214.     case RopeBase::leaf:
  1215.         {
  1216.         RopeLeaf * l = (RopeLeaf *)r;
  1217.         return l -> data[i];
  1218.         }
  1219.     case RopeBase::function:
  1220.     case RopeBase::substringfn:
  1221.         {
  1222.         RopeFunction * f = (RopeFunction *)r;
  1223.         charT result;
  1224.  
  1225.         (*(f -> fn))(i, 1, &result);
  1226.         return result;
  1227.         }
  1228.       }
  1229.     }
  1230. }
  1231.  
  1232. # ifndef __GC
  1233. // Return a uniquely referenced character slot for the given
  1234. // position, or 0 if that's not possible.
  1235. template <class charT, class Alloc>
  1236. charT*
  1237. rope<charT,Alloc>::fetch_ptr(RopeBase *r, size_type i)
  1238. {
  1239.     RopeBase * clrstack[RopeBase::max_rope_depth];
  1240.     size_t csptr = 0;
  1241.  
  1242.     for(;;) {
  1243.       if (r -> refcount > 1) return 0;
  1244.       switch(r -> tag) {
  1245.     case RopeBase::concat:
  1246.         {
  1247.         RopeConcatenation *c = (RopeConcatenation *)r;
  1248.         RopeBase *left = c -> left;
  1249.         size_t left_len = left -> size;
  1250.  
  1251.         if (c -> c_string != 0) clrstack[csptr++] = c;
  1252.         if (i >= left_len) {
  1253.             i -= left_len;
  1254.             r = c -> right;
  1255.         } else {
  1256.             r = left;
  1257.         }
  1258.         }
  1259.         break;
  1260.     case RopeBase::leaf:
  1261.         {
  1262.         RopeLeaf * l = (RopeLeaf *)r;
  1263.         if (l -> c_string != l -> data && l -> c_string != 0)
  1264.             clrstack[csptr++] = l;
  1265.         while (csptr > 0) {
  1266.             -- csptr;
  1267.             RopeBase * d = clrstack[csptr];
  1268.             d -> free_c_string();
  1269.             d -> c_string = 0;
  1270.         }
  1271.         return l -> data + i;
  1272.         }
  1273.     case RopeBase::function:
  1274.     case RopeBase::substringfn:
  1275.         return 0;
  1276.       }
  1277.     }
  1278. }
  1279. # endif /* __GC */
  1280.  
  1281. // The following could be implemented trivially using
  1282. // lexicographical_compare_3way.
  1283. // We do a little more work to avoid dealing with rope iterators for
  1284. // flat strings.
  1285. template <class charT, class Alloc>
  1286. int
  1287. rope<charT,Alloc>::compare (const RopeBase *left, const RopeBase *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 -> size;
  1295.     right_len = right -> size;
  1296.     if (RopeBase::leaf == left -> tag) {
  1297.     RopeLeaf *l = (RopeLeaf *) left;
  1298.     if (RopeBase::leaf == right -> tag) {
  1299.         RopeLeaf *r = (RopeLeaf *) right;
  1300.         return lexicographical_compare_3way(
  1301.             l -> data, l -> data + left_len,
  1302.             r -> data, r -> 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 -> data, l -> data + left_len,
  1308.             rstart, rend);
  1309.     }
  1310.     } else {
  1311.     const_iterator lstart(left, 0);
  1312.     const_iterator lend(left, left_len);
  1313.     if (RopeBase::leaf == right -> tag) {
  1314.         RopeLeaf *r = (RopeLeaf *) right;
  1315.         return lexicographical_compare_3way(
  1316.                    lstart, lend,
  1317.                    r -> data, r -> 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_charT_ref_proxy<charT, Alloc>&
  1331. __rope_charT_ref_proxy<charT, Alloc>::operator= (charT c) {
  1332.     RopeBase * old = root -> 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 * charT_ptr = my_rope::fetch_ptr(old, pos);
  1337.     if (0 != charT_ptr) {
  1338.         *charT_ptr = c;
  1339.         return *this;
  1340.     }
  1341. #   endif
  1342.     self_destruct_ptr left(my_rope::substring(old, 0, pos));
  1343.     self_destruct_ptr right(my_rope::substring(old, pos+1, old -> size));
  1344.     self_destruct_ptr result_left(my_rope::destr_concat_char_iter(left, &c, 1));
  1345. #   ifndef __GC
  1346.       __stl_assert(left == result_left || 1 == result_left -> refcount);
  1347. #   endif
  1348.     RopeBase * result =
  1349.         my_rope::concat(result_left, right);
  1350. #   ifndef __GC
  1351.       __stl_assert(1 <= result -> refcount);
  1352.       RopeBase::unref(old);
  1353. #   endif
  1354.     root -> tree_ptr = result;
  1355.     return *this;
  1356. }
  1357.  
  1358. template <class charT, class Alloc>
  1359. inline __rope_charT_ref_proxy<charT, Alloc>::operator charT () const
  1360. {
  1361.     if (current_valid) {
  1362.     return current;
  1363.     } else {
  1364.         return my_rope::fetch(root->tree_ptr, pos);
  1365.     }
  1366. }
  1367. template <class charT, class Alloc>
  1368. __rope_charT_ptr_proxy<charT, Alloc>
  1369. __rope_charT_ref_proxy<charT, Alloc>::operator& () const {
  1370.     return __rope_charT_ptr_proxy<charT, Alloc>(*this);
  1371. }
  1372.  
  1373. template <class charT, class Alloc>
  1374. rope<charT, Alloc>::rope(size_t n, charT c)
  1375. {
  1376.     rope result;
  1377.     const size_t exponentiate_threshold = 32;
  1378.     size_t exponent;
  1379.     size_t rest;
  1380.     charT *rest_buffer;
  1381.     RopeBase * remainder;
  1382.     rope remainder_rope;
  1383.  
  1384.     if (0 == n) { tree_ptr = 0; return; }
  1385.     exponent = n / exponentiate_threshold;
  1386.     rest = n % exponentiate_threshold;
  1387.     if (0 == rest) {
  1388.     remainder = 0;
  1389.     } else {
  1390.     rest_buffer = DataAlloc::allocate(rounded_up_size(rest));
  1391.     uninitialized_fill_n(rest_buffer, rest, c);
  1392.     __cond_store_eos(rest_buffer[rest]);
  1393.     __STL_TRY {
  1394.         remainder = RopeLeaf_from_char_ptr(rest_buffer, rest);
  1395.         }
  1396.     __STL_UNWIND(RopeBase::free_string(rest_buffer, rest))
  1397.     }
  1398.     remainder_rope.tree_ptr = remainder;
  1399.     if (exponent != 0) {
  1400.     charT * base_buffer =
  1401.         DataAlloc::allocate(rounded_up_size(exponentiate_threshold));
  1402.     RopeLeaf * base_leaf;
  1403.     rope base_rope;
  1404.     uninitialized_fill_n(base_buffer, exponentiate_threshold, c);
  1405.     __cond_store_eos(base_buffer[exponentiate_threshold]);
  1406.     __STL_TRY {
  1407.           base_leaf = RopeLeaf_from_char_ptr(base_buffer,
  1408.                                              exponentiate_threshold);
  1409.         }
  1410.     __STL_UNWIND(RopeBase::free_string(base_buffer, exponentiate_threshold))
  1411.     base_rope.tree_ptr = base_leaf;
  1412.      if (1 == exponent) {
  1413.       result = base_rope;
  1414. #         ifndef __GC
  1415.         __stl_assert(1 == result -> tree_ptr -> refcount);
  1416. #         endif
  1417.     } else {
  1418.       result = power(base_rope, exponent, concat_fn());
  1419.     }
  1420.     if (0 != remainder) {
  1421.       result += remainder_rope;
  1422.     }
  1423.     } else {
  1424.     result = remainder_rope;
  1425.     }
  1426.     tree_ptr = result.tree_ptr;
  1427.     tree_ptr -> ref_nonnil();
  1428. }
  1429.  
  1430. template<class charT, class Alloc> charT rope<charT,Alloc>::empty_c_str[1];
  1431.  
  1432. # ifdef __STL_PTHREADS
  1433.     template<class charT, class Alloc>
  1434.     pthread_mutex_t rope<charT,Alloc>::swap_lock = PTHREAD_MUTEX_INITIALIZER;
  1435. # endif
  1436.  
  1437. template<class charT, class Alloc>
  1438. const charT * rope<charT,Alloc>::c_str() const {
  1439.     if (0 == tree_ptr) {
  1440.         empty_c_str[0] = __eos((charT *)0);  // Possibly redundant,
  1441.                          // but probably fast.
  1442.         return empty_c_str;
  1443.     }
  1444.     __GC_CONST charT * old_c_string = tree_ptr -> c_string;
  1445.     if (0 != old_c_string) return(old_c_string);
  1446.     size_t s = size();
  1447.     charT * result = DataAlloc::allocate(s + 1);
  1448.     flatten(tree_ptr, result);
  1449.     result[s] = __eos((charT *)0);
  1450. #   ifdef __GC
  1451.     tree_ptr -> c_string = result;
  1452. #   else
  1453.       if ((old_c_string = atomic_swap(&(tree_ptr -> c_string), result)) != 0) {
  1454.     // It must have been added in the interim.  Hence it had to have been
  1455.     // separately allocated.  Deallocate the old copy, since we just
  1456.     // replaced it.
  1457.     destroy(old_c_string, old_c_string + s + 1);
  1458.     DataAlloc::deallocate(old_c_string, s + 1);
  1459.       }
  1460. #   endif
  1461.     return(result);
  1462. }
  1463.  
  1464. template<class charT, class Alloc>
  1465. const charT * rope<charT,Alloc>::replace_with_c_str() {
  1466.     if (0 == tree_ptr) {
  1467.         empty_c_str[0] = __eos((charT *)0);
  1468.         return empty_c_str;
  1469.     }
  1470.     __GC_CONST charT * old_c_string = tree_ptr -> c_string;
  1471.     if (RopeBase::leaf == tree_ptr -> tag && 0 != old_c_string) {
  1472.     return(old_c_string);
  1473.     }
  1474.     size_t s = size();
  1475.     charT * result = DataAlloc::allocate(rounded_up_size(s));
  1476.     flatten(tree_ptr, result);
  1477.     result[s] = __eos((charT *)0);
  1478.     tree_ptr -> unref_nonnil();
  1479.     tree_ptr = RopeLeaf_from_char_ptr(result, s);
  1480.     return(result);
  1481. }
  1482.  
  1483. // Algorithm specializations.  More should be added.
  1484.  
  1485. #ifndef _MSC_VER
  1486. // I couldn't get this to work with VC++
  1487. template<class charT,class Alloc>
  1488. void
  1489. __rope_rotate(__rope_iterator<charT,Alloc> first,
  1490.               __rope_iterator<charT,Alloc> middle,
  1491.               __rope_iterator<charT,Alloc> last) {
  1492.     __stl_assert(first.container() == middle.container()
  1493.                  && middle.container() == last.container());
  1494.     rope<charT,Alloc>& r(first.container());
  1495.     rope<charT,Alloc> prefix = r.substr(0, first.index());
  1496.     rope<charT,Alloc> suffix = r.substr(last.index(), r.size() - last.index());
  1497.     rope<charT,Alloc> part1 = r.substr(middle.index(),
  1498.                                        last.index() - middle.index());
  1499.     rope<charT,Alloc> part2 = r.substr(first.index(),
  1500.                                        middle.index() - first.index());
  1501.     r = prefix;
  1502.     r += part1;
  1503.     r += part2;
  1504.     r += suffix;
  1505. }
  1506.  
  1507. inline void rotate(__rope_iterator<char,__ALLOC> first,
  1508.                    __rope_iterator<char,__ALLOC> middle,
  1509.                    __rope_iterator<char,__ALLOC> last) {
  1510.     __rope_rotate(first, middle, last);
  1511. }
  1512.  
  1513. # if 0
  1514. // Probably not useful for several reasons:
  1515. // - for SGIs 7.1 compiler and probably some others,
  1516. //   this forces lots of rope<wchar_t, ...> instantiations, creating a
  1517. //   code bloat and compile time problem.  (Fixed in 7.2.)
  1518. // - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
  1519. //   for unicode strings.  Unsigned short may be a better character
  1520. //   type.
  1521. inline void rotate(__rope_iterator<wchar_t,__ALLOC> first,
  1522.                    __rope_iterator<wchar_t,__ALLOC> middle,
  1523.                    __rope_iterator<wchar_t,__ALLOC> last) {
  1524.     __rope_rotate(first, middle, last);
  1525. }
  1526. # endif
  1527. #endif /* _MSC_VER */
  1528.  
  1529. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1530. #pragma reset woff 1174
  1531. #endif
  1532.  
  1533. __STL_END_NAMESPACE
  1534.  
  1535. // Local Variables:
  1536. // mode:C++
  1537. // End:
  1538.