ropeimpl.h
上传用户:sichengcw
上传日期:2009-02-17
资源大小:202k
文件大小:42k
源码类别:

STL

开发平台:

Visual C++

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