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

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. #ifndef __SGI_STL_INTERNAL_ROPE_H
  17. # define __SGI_STL_INTERNAL_ROPE_H
  18. # ifdef __GC
  19. #   define __GC_CONST const
  20. # else
  21. #   define __GC_CONST   // constant except for deallocation
  22. # endif
  23. # ifdef __STL_SGI_THREADS
  24. #    include <mutex.h>
  25. # endif
  26. __STL_BEGIN_NAMESPACE
  27. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  28. #pragma set woff 1174
  29. #endif
  30. // The end-of-C-string character.
  31. // This is what the draft standard says it should be.
  32. template <class charT>
  33. inline charT __eos(charT*) { return charT(); }
  34. // Test for basic character types.
  35. // For basic character types leaves having a trailing eos.
  36. template <class charT>
  37. inline bool __is_basic_char_type(charT *) { return false; }
  38. template <class charT>
  39. inline bool __is_one_byte_char_type(charT *) { return false; }
  40. inline bool __is_basic_char_type(char *) { return true; }
  41. inline bool __is_one_byte_char_type(char *) { return true; }
  42. inline bool __is_basic_char_type(wchar_t *) { return true; }
  43. // Store an eos iff charT is a basic character type.
  44. // Do not reference __eos if it isn't.
  45. template <class charT>
  46. inline void __cond_store_eos(charT&) {}
  47. inline void __cond_store_eos(char& c) { c = 0; }
  48. inline void __cond_store_eos(wchar_t& c) { c = 0; }
  49. // rope<charT,Alloc> is a sequence of charT.
  50. // Ropes appear to be mutable, but update operations
  51. // really copy enough of the data structure to leave the original
  52. // valid.  Thus ropes can be logically copied by just copying
  53. // a pointer value.
  54. // The __eos function is used for those functions that
  55. // convert to/from C-like strings to detect the end of the string.
  56. // __compare is used as the character comparison function.
  57. template <class charT>
  58. class char_producer {
  59.     public:
  60. virtual ~char_producer() {};
  61. virtual void operator()(size_t start_pos, size_t len, charT* buffer)
  62. = 0;
  63. // Buffer should really be an arbitrary output iterator.
  64. // That way we could flatten directly into an ostream, etc.
  65. // This is thoroughly impossible, since iterator types don't
  66. // have runtime descriptions.
  67. };
  68. // Sequence buffers:
  69. //
  70. // Sequence must provide an append operation that appends an
  71. // array to the sequence.  Sequence buffers are useful only if
  72. // appending an entire array is cheaper than appending element by element.
  73. // This is true for many string representations.
  74. // This should  perhaps inherit from ostream<sequence::value_type>
  75. // and be implemented correspondingly, so that they can be used
  76. // for formatted.  For the sake of portability, we don't do this yet.
  77. //
  78. // For now, sequence buffers behave as output iterators.  But they also
  79. // behave a little like basic_ostringstream<sequence::value_type> and a
  80. // little like containers.
  81. template<class sequence, size_t buf_sz = 100
  82. #   if defined(__sgi) && !defined(__GNUC__)
  83. #  define __TYPEDEF_WORKAROUND
  84.          ,class v = typename sequence::value_type
  85. #   endif
  86.         >
  87. // The 3rd parameter works around a common compiler bug.
  88. class sequence_buffer : public output_iterator {
  89.     public:
  90. #       ifndef __TYPEDEF_WORKAROUND
  91.     typedef typename sequence::value_type value_type;
  92. # else
  93.     typedef v value_type;
  94. # endif
  95.     protected:
  96. sequence *prefix;
  97. value_type buffer[buf_sz];
  98. size_t buf_count;
  99.     public:
  100. void flush() {
  101.     prefix->append(buffer, buffer + buf_count);
  102.     buf_count = 0;
  103. }
  104. ~sequence_buffer() { flush(); }
  105. sequence_buffer() : prefix(0), buf_count(0) {}
  106. sequence_buffer(const sequence_buffer & x) {
  107.     prefix = x.prefix;
  108.             buf_count = x.buf_count;
  109.             copy(x.buffer, x.buffer + x.buf_count, buffer);
  110. }
  111. sequence_buffer(sequence_buffer & x) {
  112.     x.flush();
  113.     prefix = x.prefix;
  114.     buf_count = 0;
  115. }
  116. sequence_buffer(sequence& s) : prefix(&s), buf_count(0) {}
  117. sequence_buffer& operator= (sequence_buffer& x) {
  118.     x.flush();
  119.     prefix = x.prefix;
  120.     buf_count = 0;
  121.     return *this;
  122. }
  123. sequence_buffer& operator= (const sequence_buffer& x) {
  124.     prefix = x.prefix;
  125.     buf_count = x.buf_count;
  126.     copy(x.buffer, x.buffer + x.buf_count, buffer);
  127.     return *this;
  128. }
  129. void push_back(value_type x)
  130. {
  131.     if (buf_count < buf_sz) {
  132. buffer[buf_count] = x;
  133. ++buf_count;
  134.     } else {
  135. flush();
  136. buffer[0] = x;
  137. buf_count = 1;
  138.     }
  139. }
  140. void append(value_type *s, size_t len)
  141. {
  142.     if (len + buf_count <= buf_sz) {
  143. size_t i, j;
  144. for (i = buf_count, j = 0; j < len; i++, j++) {
  145.     buffer[i] = s[j];
  146. }
  147. buf_count += len;
  148.     } else if (0 == buf_count) {
  149. prefix->append(s, s + len);
  150.     } else {
  151. flush();
  152. append(s, len);
  153.     }
  154. }
  155. sequence_buffer& write(value_type *s, size_t len)
  156. {
  157.     append(s, len);
  158.     return *this;
  159. }
  160. sequence_buffer& put(value_type x)
  161. {
  162.     push_back(x);
  163.     return *this;
  164. }
  165. sequence_buffer& operator=(const value_type& rhs)
  166. {
  167.     push_back(rhs);
  168.     return *this;
  169. }
  170. sequence_buffer& operator*() { return *this; }
  171. sequence_buffer& operator++() { return *this; }
  172. sequence_buffer& operator++(int) { return *this; }
  173. };
  174. // The following should be treated as private, at least for now.
  175. template<class charT>
  176. class __rope_char_consumer {
  177.     public:
  178. // If we had member templates, these should not be virtual.
  179. // For now we need to use run-time parametrization where
  180. // compile-time would do.  Hence this should all be private
  181. // for now.
  182. // The symmetry with char_producer is accidental and temporary.
  183. virtual ~__rope_char_consumer() {};
  184. virtual bool operator()(const charT* buffer, size_t len) = 0;
  185. };
  186. //
  187. // What follows should really be local to rope.  Unfortunately,
  188. // that doesn't work, since it makes it impossible to define generic
  189. // equality on rope iterators.  According to the draft standard, the
  190. // template parameters for such an equality operator cannot be inferred
  191. // from the occurence of a member class as a parameter.
  192. // (SGI compilers in fact allow this, but the result wouldn't be
  193. // portable.)
  194. // Similarly, some of the static member functions are member functions
  195. // only to avoid polluting the global namespace, and to circumvent
  196. // restrictions on type inference for template functions.
  197. //
  198. template<class CharT, class Alloc=__ALLOC> class rope;
  199. template<class CharT, class Alloc> struct __rope_RopeConcatenation;
  200. template<class CharT, class Alloc> struct __rope_RopeLeaf;
  201. template<class CharT, class Alloc> struct __rope_RopeFunction;
  202. template<class CharT, class Alloc> struct __rope_RopeSubstring;
  203. template<class CharT, class Alloc> class __rope_iterator;
  204. template<class CharT, class Alloc> class __rope_const_iterator;
  205. template<class CharT, class Alloc> class __rope_charT_ref_proxy;
  206. template<class CharT, class Alloc> class __rope_charT_ptr_proxy;
  207. //
  208. // The internal data structure for representing a rope.  This is
  209. // private to the implementation.  A rope is really just a pointer
  210. // to one of these.
  211. //
  212. // A few basic functions for manipulating this data structure
  213. // are members of RopeBase.  Most of the more complex algorithms
  214. // are implemented as rope members.
  215. //
  216. // Some of the static member functions of RopeBase have identically
  217. // named functions in rope that simply invoke the RopeBase versions.
  218. //
  219. template<class charT, class Alloc>
  220. struct __rope_RopeBase {
  221.     typedef rope<charT,Alloc> my_rope;
  222.     typedef simple_alloc<charT, Alloc> DataAlloc;
  223.     typedef simple_alloc<__rope_RopeConcatenation<charT,Alloc>, Alloc> CAlloc;
  224.     typedef simple_alloc<__rope_RopeLeaf<charT,Alloc>, Alloc> LAlloc;
  225.     typedef simple_alloc<__rope_RopeFunction<charT,Alloc>, Alloc> FAlloc;
  226.     typedef simple_alloc<__rope_RopeSubstring<charT,Alloc>, Alloc> SAlloc;
  227.     public:
  228.     enum { max_rope_depth = 45 };
  229.     enum {leaf, concat, substringfn, function} tag:8;
  230.     bool is_balanced:8;
  231.     unsigned char depth;
  232.     size_t size;
  233.     __GC_CONST charT * c_string;
  234. /* Flattened version of string, if needed.  */
  235. /* typically 0.                             */
  236. /* If it's not 0, then the memory is owned  */
  237. /* by this node.                            */
  238. /* In the case of a leaf, this may point to */
  239. /* the same memory as the data field.     */
  240. #   ifndef __GC
  241. #       if defined(__STL_WIN32THREADS)
  242.     long refcount;   // InterlockedIncrement wants a long *
  243. # else
  244.     size_t refcount;
  245. # endif
  246. // We count references from rope instances
  247. // and references from other rope nodes.  We
  248. // do not count const_iterator references.
  249. // Iterator references are counted so that rope modifications
  250. // can be detected after the fact.
  251. // Generally function results are counted, i.e.
  252. // a pointer returned by a function is included at the
  253. // point at which the pointer is returned.
  254. // The recipient should decrement the count if the
  255. // result is not needed.
  256. // Generally function arguments are not reflected
  257. // in the reference count.  The callee should increment
  258. // the count before saving the argument someplace that
  259. // will outlive the call.
  260. #   endif
  261. #   ifndef __GC
  262. #       ifdef __STL_SGI_THREADS
  263.     // Reference counting with multiple threads and no
  264.     // hardware or thread package support is pretty awful.
  265.     // Mutexes are normally too expensive.
  266.     // We'll assume a COMPARE_AND_SWAP(destp, old, new)
  267.     // operation, which might be cheaper.
  268. #           if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
  269. #               define __add_and_fetch(l,v) add_then_test((unsigned long *)l,v)
  270. #           endif
  271.     void init_refcount_lock() {}
  272.     void incr_refcount ()
  273.     {
  274. __add_and_fetch(&refcount, 1);
  275.     }
  276.     size_t decr_refcount ()
  277.     {
  278. return __add_and_fetch(&refcount, (size_t)(-1));
  279.     }
  280. #       elif defined(__STL_WIN32THREADS)
  281.     void init_refcount_lock() {}
  282.             void incr_refcount ()
  283.             {
  284.                 InterlockedIncrement(&refcount);
  285.             }
  286.             size_t decr_refcount ()
  287.             {
  288.                 return InterlockedDecrement(&refcount);
  289.             }
  290. # elif defined(__STL_PTHREADS)
  291.     // This should be portable, but performance is expected
  292.     // to be quite awful.  This really needs platform specific
  293.     // code.
  294.     pthread_mutex_t refcount_lock;
  295.     void init_refcount_lock() {
  296. pthread_mutex_init(&refcount_lock, 0);
  297.     }
  298.     void incr_refcount ()
  299.             {   
  300. pthread_mutex_lock(&refcount_lock);
  301.                 ++refcount;
  302. pthread_mutex_unlock(&refcount_lock);
  303.             }
  304.             size_t decr_refcount ()
  305.             {   
  306. size_t result;
  307. pthread_mutex_lock(&refcount_lock);
  308.                 result = --refcount;
  309. pthread_mutex_unlock(&refcount_lock);
  310.                 return result;
  311.             }
  312. # else
  313.     void init_refcount_lock() {}
  314.     void incr_refcount ()
  315.     {
  316. ++refcount;
  317.     }
  318.     size_t decr_refcount ()
  319.     {
  320. --refcount;
  321. return refcount;
  322.     }
  323. #       endif
  324. #   else
  325. void incr_refcount () {}
  326. #   endif
  327. static void free_string(charT *, size_t len);
  328. // Deallocate data section of a leaf.
  329. // This shouldn't be a member function.
  330. // But its hard to do anything else at the
  331. // moment, because it's templatized w.r.t.
  332. // an allocator.
  333. // Does nothing if __GC is defined.
  334. #   ifndef __GC
  335.   void free_c_string();
  336.   void free_tree();
  337. // Deallocate t. Assumes t is not 0.
  338.   void unref_nonnil()
  339.   {
  340.       if (0 == decr_refcount()) free_tree();
  341.   }
  342.   void ref_nonnil()
  343.   {
  344.       incr_refcount();
  345.   }
  346.   static void unref(__rope_RopeBase* t)
  347.   {
  348.       if (0 != t) {
  349.   t -> unref_nonnil();
  350.       }
  351.   }
  352.   static void ref(__rope_RopeBase* t)
  353.   {
  354.       if (0 != t) t -> incr_refcount();
  355.   }
  356.   static void free_if_unref(__rope_RopeBase* t)
  357.     {
  358.       if (0 != t && 0 == t -> refcount) t -> free_tree();
  359.   }
  360. #   else /* __GC */
  361.   void unref_nonnil() {}
  362.   void ref_nonnil() {}
  363.   static void unref(__rope_RopeBase* t) {}
  364.   static void ref(__rope_RopeBase* t) {}
  365.   static void fn_finalization_proc(void * tree, void *);
  366.   static void free_if_unref(__rope_RopeBase* t) {}
  367. #   endif
  368.     // The data fields of leaves are allocated with some
  369.     // extra space, to accomodate future growth and for basic
  370.     // character types, to hold a trailing eos character.
  371.     enum { alloc_granularity = 8 };
  372.     static size_t rounded_up_size(size_t n) {
  373.         size_t size_with_eos;
  374.      
  375.         if (__is_basic_char_type((charT *)0)) {
  376.          size_with_eos = n + 1;
  377.      } else {
  378.        size_with_eos = n;
  379. }
  380. #       ifdef __GC
  381.        return size_with_eos;
  382. # else
  383.    // Allow slop for in-place expansion.
  384.    return (size_with_eos + alloc_granularity-1)
  385. &~ (alloc_granularity-1);
  386. # endif
  387.     }
  388. };
  389. template<class charT, class Alloc>
  390. struct __rope_RopeLeaf : public __rope_RopeBase<charT,Alloc> {
  391.   public:  // Apparently needed by VC++
  392.     __GC_CONST charT* data;     /* Not necessarily 0 terminated. */
  393. /* The allocated size is  */
  394. /* rounded_up_size(size), except */
  395. /* in the GC case, in which it  */
  396. /* doesn't matter.  */
  397. };
  398. template<class charT, class Alloc>
  399. struct __rope_RopeConcatenation : public __rope_RopeBase<charT,Alloc> {
  400.   public:
  401.     __rope_RopeBase<charT,Alloc>* left;
  402.     __rope_RopeBase<charT,Alloc>* right;
  403. };
  404. template<class charT, class Alloc>
  405. struct __rope_RopeFunction : public __rope_RopeBase<charT,Alloc> {
  406.   public:
  407.     char_producer<charT>* fn;
  408. #   ifndef __GC
  409.       bool delete_when_done; // Char_producer is owned by the
  410. // rope and should be explicitly
  411. // deleted when the rope becomes
  412. // inaccessible.
  413. #   else
  414.       // In the GC case, we either register the rope for
  415.       // finalization, or not.  Thus the field is unnecessary;
  416.       // the information is stored in the collector data structures.
  417. #   endif
  418. };
  419. // Substring results are usually represented using just
  420. // concatenation nodes.  But in the case of very long flat ropes
  421. // or ropes with a functional representation that isn't practical.
  422. // In that case, we represent the result as a special case of
  423. // RopeFunction, whose char_producer points back to the rope itself.
  424. // In all cases except repeated substring operations and
  425. // deallocation, we treat the result as a RopeFunction.
  426. template<class charT, class Alloc>
  427. struct __rope_RopeSubstring: public __rope_RopeFunction<charT,Alloc>,
  428.      public char_producer<charT> {
  429.   public:
  430.     __rope_RopeBase<charT,Alloc> * base; // not 0
  431.     size_t start;
  432.     virtual ~__rope_RopeSubstring() {}
  433.     virtual void operator()(size_t start_pos, size_t req_len,
  434.     charT *buffer) {
  435. switch(base -> tag) {
  436.     case function:
  437.     case substringfn:
  438.       {
  439. char_producer<charT> *fn =
  440. ((__rope_RopeFunction<charT,Alloc> *)base) -> fn;
  441. __stl_assert(start_pos + req_len <= size);
  442. __stl_assert(start + size <= base -> size);
  443. (*fn)(start_pos + start, req_len, buffer);
  444.       }
  445.       break;
  446.     case leaf:
  447.       {
  448. __GC_CONST charT * s =
  449. ((__rope_RopeLeaf<charT,Alloc> *)base) -> data;
  450. uninitialized_copy_n(s + start_pos + start, req_len,
  451.      buffer);
  452.       }
  453.       break;
  454.     default:
  455.       __stl_assert(false);
  456. }
  457.     }
  458.     __rope_RopeSubstring(__rope_RopeBase<charT,Alloc> * b, size_t s, size_t l) :
  459. base(b), start(s) {
  460. #       ifndef __GC
  461.     refcount = 1;
  462.     init_refcount_lock();
  463.     base -> ref_nonnil();
  464. #       endif
  465. size = l;
  466. tag = substringfn;
  467. depth = 0;
  468. c_string = 0;
  469. fn = this;
  470.     }
  471. };
  472. // Self-destructing pointers to RopeBase.
  473. // These are not conventional smart pointers.  Their
  474. // only purpose in life is to ensure that unref is called
  475. // on the pointer either at normal exit or if an exception
  476. // is raised.  It is the caller's responsibility to
  477. // adjust reference counts when these pointers are initialized
  478. // or assigned to.  (This convention significantly reduces
  479. // the number of potentially expensive reference count
  480. // updates.)
  481. #ifndef __GC
  482.   template<class charT, class Alloc>
  483.   struct __rope_self_destruct_ptr {
  484.     __rope_RopeBase<charT,Alloc> * ptr;
  485.     ~__rope_self_destruct_ptr() { __rope_RopeBase<charT,Alloc>::unref(ptr); }
  486. #   ifdef __STL_USE_EXCEPTIONS
  487. __rope_self_destruct_ptr() : ptr(0) {};
  488. #   else
  489. __rope_self_destruct_ptr() {};
  490. #   endif
  491.     __rope_self_destruct_ptr(__rope_RopeBase<charT,Alloc> * p) : ptr(p) {}
  492.     __rope_RopeBase<charT,Alloc> & operator*() { return *ptr; }
  493.     __rope_RopeBase<charT,Alloc> * operator->() { return ptr; }
  494.     operator __rope_RopeBase<charT,Alloc> *() { return ptr; }
  495.     __rope_self_destruct_ptr & operator= (__rope_RopeBase<charT,Alloc> * x)
  496. { ptr = x; return *this; }
  497.   };
  498. #endif
  499. // Dereferencing a nonconst iterator has to return something
  500. // that behaves almost like a reference.  It's not possible to
  501. // return an actual reference since assignment requires extra
  502. // work.  And we would get into the same problems as with the
  503. // CD2 version of basic_string.
  504. template<class charT, class Alloc>
  505. class __rope_charT_ref_proxy {
  506.     friend class rope<charT,Alloc>;
  507.     friend class __rope_iterator<charT,Alloc>;
  508.     friend class __rope_charT_ptr_proxy<charT,Alloc>;
  509. #   ifdef __GC
  510. typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
  511. #   else
  512.      typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
  513. #   endif
  514.     typedef __rope_RopeBase<charT,Alloc> RopeBase;
  515.     typedef rope<charT,Alloc> my_rope;
  516.     size_t pos;
  517.     charT current;
  518.     bool current_valid;
  519.     my_rope * root;     // The whole rope.
  520.   public:
  521.     __rope_charT_ref_proxy(my_rope * r, size_t p) :
  522. pos(p), root(r), current_valid(false) {}
  523.     __rope_charT_ref_proxy(my_rope * r, size_t p,
  524.     charT c) :
  525. pos(p), root(r), current(c), current_valid(true) {}
  526.     operator charT () const;
  527.     __rope_charT_ref_proxy& operator= (charT c);
  528.     __rope_charT_ptr_proxy<charT,Alloc> operator& () const;
  529.     __rope_charT_ref_proxy& operator= (const __rope_charT_ref_proxy& c) {
  530. return operator=((charT)c); 
  531.     }
  532. };
  533. template<class charT, class Alloc>
  534. class __rope_charT_ptr_proxy {
  535.     friend class __rope_charT_ref_proxy<charT,Alloc>;
  536.     size_t pos;
  537.     charT current;
  538.     bool current_valid;
  539.     rope<charT,Alloc> * root;     // The whole rope.
  540.   public:
  541.     __rope_charT_ptr_proxy(const __rope_charT_ref_proxy<charT,Alloc> & x) :
  542. pos(x.pos), root(x.root), current_valid(x.current_valid),
  543. current(x.current) {}
  544.     __rope_charT_ptr_proxy(const __rope_charT_ptr_proxy & x) :
  545. pos(x.pos), root(x.root), current_valid(x.current_valid),
  546. current(x.current) {}
  547.     __rope_charT_ptr_proxy() {}
  548.     __rope_charT_ptr_proxy(charT * x) : root(0), pos(0) {
  549. __stl_assert(0 == x);
  550.     }
  551.     __rope_charT_ptr_proxy& operator= (const __rope_charT_ptr_proxy& x) {
  552. pos = x.pos;
  553. current = x.current;
  554. current_valid = x.current_valid;
  555. root = x.root;
  556. return *this;
  557.     }
  558.     friend bool operator== __STL_NULL_TMPL_ARGS
  559.                 (const __rope_charT_ptr_proxy<charT,Alloc> & x,
  560.                  const __rope_charT_ptr_proxy<charT,Alloc> & y);
  561.     __rope_charT_ref_proxy<charT,Alloc> operator *() const {
  562. if (current_valid) {
  563.     return __rope_charT_ref_proxy<charT,Alloc>(root, pos, current);
  564. } else {
  565.     return __rope_charT_ref_proxy<charT,Alloc>(root, pos);
  566. }
  567.     }
  568. };
  569. // Rope iterators:
  570. // Unlike in the C version, we cache only part of the stack
  571. // for rope iterators, since they must be efficiently copyable.
  572. // When we run out of cache, we have to reconstruct the iterator
  573. // value.
  574. // Pointers from iterators are not included in reference counts.
  575. // Iterators are assumed to be thread private.  Ropes can
  576. // be shared.
  577. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  578. #pragma set woff 1375
  579. #endif
  580. template<class charT, class Alloc>
  581. class __rope_iterator_base:
  582.   public random_access_iterator<charT, ptrdiff_t> {
  583.   friend class rope<charT, Alloc>;
  584.   public:
  585.     typedef __rope_RopeBase<charT,Alloc> RopeBase;
  586. // Borland doesnt want this to be protected.
  587.   protected:
  588.     enum { path_cache_len = 4 }; // Must be <= 9.
  589.     enum { iterator_buf_len = 15 };
  590.     size_t current_pos;
  591.     RopeBase * root;     // The whole rope.
  592.     size_t leaf_pos;    // Starting position for current leaf
  593.     __GC_CONST charT * buf_start;
  594. // Buffer possibly
  595. // containing current char.
  596.     __GC_CONST charT * buf_ptr;
  597. // Pointer to current char in buffer.
  598. // != 0 ==> buffer valid.
  599.     __GC_CONST charT * buf_end;
  600. // One past last valid char in buffer.
  601.     // What follows is the path cache.  We go out of our
  602.     // way to make this compact.
  603.     // Path_end contains the bottom section of the path from
  604.     // the root to the current leaf.
  605.     const RopeBase * path_end[path_cache_len];
  606.     int leaf_index;     // Last valid pos in path_end;
  607.      // path_end[0] ... path_end[leaf_index-1]
  608. // point to concatenation nodes.
  609.     unsigned char path_directions;
  610.   // (path_directions >> i) & 1 is 1
  611.   // iff we got from path_end[leaf_index - i - 1]
  612.   // to path_end[leaf_index - i] by going to the
  613.   // right. Assumes path_cache_len <= 9.
  614.     charT tmp_buf[iterator_buf_len];
  615. // Short buffer for surrounding chars.
  616. // This is useful primarily for 
  617. // RopeFunctions.  We put the buffer
  618. // here to avoid locking in the
  619. // multithreaded case.
  620.     // The cached path is generally assumed to be valid
  621.     // only if the buffer is valid.
  622.     static void setbuf(__rope_iterator_base &x);
  623. // Set buffer contents given
  624. // path cache.
  625.     static void setcache(__rope_iterator_base &x);
  626. // Set buffer contents and
  627. // path cache.
  628.     static void setcache_for_incr(__rope_iterator_base &x);
  629. // As above, but assumes path
  630. // cache is valid for previous posn.
  631.     __rope_iterator_base() {}
  632.     __rope_iterator_base(RopeBase * root, size_t pos):
  633.    root(root), current_pos(pos), buf_ptr(0) {}
  634.     __rope_iterator_base(const __rope_iterator_base& x) {
  635. if (0 != x.buf_ptr) {
  636.     *this = x;
  637. } else {
  638.     current_pos = x.current_pos;
  639.     root = x.root;
  640.     buf_ptr = 0;
  641. }
  642.     }
  643.     void incr(size_t n);
  644.     void decr(size_t n);
  645.   public:
  646.     size_t index() const { return current_pos; }
  647. };
  648. template<class charT, class Alloc> class __rope_iterator;
  649. template<class charT, class Alloc>
  650. class __rope_const_iterator : public __rope_iterator_base<charT,Alloc> {
  651.     friend class rope<charT,Alloc>;
  652.   protected:
  653.     __rope_const_iterator(const RopeBase * root, size_t pos):
  654.    __rope_iterator_base<charT,Alloc>(
  655.      const_cast<RopeBase *>(root), pos)
  656.    // Only nonconst iterators modify root ref count
  657.     {}
  658.   public:
  659.     typedef charT reference;    // Really a value.  Returning a reference
  660. // Would be a mess, since it would have
  661. // to be included in refcount.
  662.     typedef const charT* pointer;
  663.   public:
  664.     __rope_const_iterator() {};
  665.     __rope_const_iterator(const __rope_const_iterator & x) :
  666. __rope_iterator_base<charT,Alloc>(x) { }
  667.     __rope_const_iterator(const __rope_iterator<charT,Alloc> & x);
  668.     __rope_const_iterator(const rope<charT,Alloc> &r, size_t pos) :
  669. __rope_iterator_base<charT,Alloc>(r.tree_ptr, pos) {}
  670.     __rope_const_iterator& operator= (const __rope_const_iterator & x) {
  671. if (0 != x.buf_ptr) {
  672.     *this = x;
  673. } else {
  674.     current_pos = x.current_pos;
  675.     root = x.root;
  676.     buf_ptr = 0;
  677. }
  678. return(*this);
  679.     }
  680.     reference operator*() {
  681. if (0 == buf_ptr) setcache(*this);
  682. return *buf_ptr;
  683.     }
  684.     __rope_const_iterator& operator++() {
  685. __GC_CONST charT * next;
  686. if (0 != buf_ptr && (next = buf_ptr + 1) < buf_end) {
  687.     buf_ptr = next;
  688.     ++current_pos;
  689. } else {
  690.     incr(1);
  691. }
  692. return *this;
  693.     }
  694.     __rope_const_iterator& operator+=(ptrdiff_t n) {
  695. if (n >= 0) {
  696.     incr(n);
  697. } else {
  698.     decr(-n);
  699. }
  700. return *this;
  701.     }
  702.     __rope_const_iterator& operator--() {
  703. decr(1);
  704. return *this;
  705.     }
  706.     __rope_const_iterator& operator-=(ptrdiff_t n) {
  707. if (n >= 0) {
  708.     decr(n);
  709. } else {
  710.     incr(-n);
  711. }
  712. return *this;
  713.     }
  714.     __rope_const_iterator operator++(int) {
  715. size_t old_pos = current_pos;
  716. incr(1);
  717. return __rope_const_iterator<charT,Alloc>(root, old_pos);
  718. // This makes a subsequent dereference expensive.
  719. // Perhaps we should instead copy the iterator
  720. // if it has a valid cache?
  721.     }
  722.     __rope_const_iterator operator--(int) {
  723. size_t old_pos = current_pos;
  724. decr(1);
  725. return __rope_const_iterator<charT,Alloc>(root, old_pos);
  726.     }
  727.     friend __rope_const_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
  728. (const __rope_const_iterator<charT,Alloc> & x,
  729.  ptrdiff_t n);
  730.     friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  731. (const __rope_const_iterator<charT,Alloc> & x,
  732.  ptrdiff_t n);
  733.     friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  734. (ptrdiff_t n,
  735.  const __rope_const_iterator<charT,Alloc> & x);
  736.     reference operator[](size_t n) {
  737. return rope<charT,Alloc>::fetch(root, current_pos + n);
  738.     }
  739.     friend bool operator== __STL_NULL_TMPL_ARGS
  740. (const __rope_const_iterator<charT,Alloc> & x,
  741.  const __rope_const_iterator<charT,Alloc> & y);
  742.     friend bool operator< __STL_NULL_TMPL_ARGS
  743. (const __rope_const_iterator<charT,Alloc> & x,
  744.  const __rope_const_iterator<charT,Alloc> & y);
  745.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  746. (const __rope_const_iterator<charT,Alloc> & x,
  747.  const __rope_const_iterator<charT,Alloc> & y);
  748. };
  749. template<class charT, class Alloc>
  750. class __rope_iterator : public __rope_iterator_base<charT,Alloc> {
  751.     friend class rope<charT,Alloc>;
  752.   protected:
  753.     rope<charT,Alloc> * root_rope;
  754. // root is treated as a cached version of this,
  755. // and is used to detect changes to the underlying
  756. // rope.
  757. // Root is included in the reference count.
  758. // This is necessary so that we can detect changes reliably.
  759. // Unfortunately, it requires careful bookkeeping for the
  760. // nonGC case.
  761.     __rope_iterator(rope<charT,Alloc> * r, size_t pos):
  762.      __rope_iterator_base<charT,Alloc>(r -> tree_ptr, pos),
  763.      root_rope(r) {
  764. RopeBase::ref(root);
  765.      }
  766.     void check();
  767.   public:
  768.     typedef __rope_charT_ref_proxy<charT,Alloc>  reference;
  769.     typedef __rope_charT_ref_proxy<charT,Alloc>* pointer;
  770.   public:
  771.     rope<charT,Alloc>& container() { return *root_rope; }
  772.     __rope_iterator() {
  773. root = 0;  // Needed for reference counting.
  774.     };
  775.     __rope_iterator(const __rope_iterator & x) :
  776. __rope_iterator_base<charT,Alloc>(x) {
  777. root_rope = x.root_rope;
  778. RopeBase::ref(root);
  779.     }
  780.     __rope_iterator(rope<charT,Alloc>& r, size_t pos);
  781.     ~__rope_iterator() {
  782. RopeBase::unref(root);
  783.     }
  784.     __rope_iterator& operator= (const __rope_iterator & x) {
  785. RopeBase *old = root;
  786. RopeBase::ref(x.root);
  787. if (0 != x.buf_ptr) {
  788.     *this = x;
  789. } else {
  790.     current_pos = x.current_pos;
  791.     root = x.root;
  792.     root_rope = x.root_rope;
  793.     buf_ptr = 0;
  794. }
  795. RopeBase::unref(old);
  796. return(*this);
  797.     }
  798.     reference operator*() {
  799. check();
  800. if (0 == buf_ptr) {
  801.     return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos);
  802. } else {
  803.     return __rope_charT_ref_proxy<charT,Alloc>(root_rope,
  804.        current_pos, *buf_ptr);
  805. }
  806.     }
  807.     __rope_iterator& operator++() {
  808. incr(1);
  809. return *this;
  810.     }
  811.     __rope_iterator& operator+=(difference_type n) {
  812. if (n >= 0) {
  813.     incr(n);
  814. } else {
  815.     decr(-n);
  816. }
  817. return *this;
  818.     }
  819.     __rope_iterator& operator--() {
  820. decr(1);
  821. return *this;
  822.     }
  823.     __rope_iterator& operator-=(difference_type n) {
  824. if (n >= 0) {
  825.     decr(n);
  826. } else {
  827.     incr(-n);
  828. }
  829. return *this;
  830.     }
  831.     __rope_iterator operator++(int) {
  832. size_t old_pos = current_pos;
  833. incr(1);
  834. return __rope_iterator<charT,Alloc>(root_rope, old_pos);
  835.     }
  836.     __rope_iterator operator--(int) {
  837. size_t old_pos = current_pos;
  838. decr(1);
  839. return __rope_iterator<charT,Alloc>(root_rope, old_pos);
  840.     }
  841.     reference operator[](ptrdiff_t n) {
  842. return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos + n);
  843.     }
  844.     friend bool operator== __STL_NULL_TMPL_ARGS
  845. (const __rope_iterator<charT,Alloc> & x,
  846.  const __rope_iterator<charT,Alloc> & y);
  847.     friend bool operator< __STL_NULL_TMPL_ARGS
  848. (const __rope_iterator<charT,Alloc> & x,
  849.  const __rope_iterator<charT,Alloc> & y);
  850.     friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
  851. (const __rope_iterator<charT,Alloc> & x,
  852.  const __rope_iterator<charT,Alloc> & y);
  853.     friend __rope_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
  854. (const __rope_iterator<charT,Alloc> & x,
  855.  ptrdiff_t n);
  856.     friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  857. (const __rope_iterator<charT,Alloc> & x,
  858.  ptrdiff_t n);
  859.     friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
  860. (ptrdiff_t n,
  861.  const __rope_iterator<charT,Alloc> & x);
  862. };
  863. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  864. #pragma reset woff 1375
  865. #endif
  866. template <class charT, class Alloc>
  867. class rope {
  868.     public:
  869. typedef charT value_type;
  870. typedef ptrdiff_t difference_type;
  871. typedef size_t size_type;
  872. typedef charT const_reference;
  873. typedef const charT* const_pointer;
  874. typedef __rope_iterator<charT,Alloc> iterator;
  875. typedef __rope_const_iterator<charT,Alloc> const_iterator;
  876. typedef __rope_charT_ref_proxy<charT,Alloc> reference;
  877. typedef __rope_charT_ptr_proxy<charT,Alloc> pointer;
  878. friend class __rope_iterator<charT,Alloc>;
  879. friend class __rope_const_iterator<charT,Alloc>;
  880. friend struct __rope_RopeBase<charT,Alloc>;
  881. friend class __rope_iterator_base<charT,Alloc>;
  882. friend class __rope_charT_ptr_proxy<charT,Alloc>;
  883. friend class __rope_charT_ref_proxy<charT,Alloc>;
  884. friend struct __rope_RopeSubstring<charT,Alloc>;
  885.     protected:
  886. typedef __GC_CONST charT * cstrptr;
  887. #       ifdef __STL_SGI_THREADS
  888.     static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  889. #               if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
  890.                     return (cstrptr) test_and_set((unsigned long *)p,
  891.               (unsigned long)q);
  892. # else
  893.                     return (cstrptr) __test_and_set((unsigned long *)p,
  894.                 (unsigned long)q);
  895. # endif
  896.             }
  897. #       elif defined(__STL_WIN32THREADS)
  898.     static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  899. return (cstrptr) InterlockedExchange((LPLONG)p, (LONG)q);
  900.     }
  901. # elif defined(__STL_PTHREADS)
  902.     // This should be portable, but performance is expected
  903.     // to be quite awful.  This really needs platform specific
  904.     // code.
  905.     static pthread_mutex_t swap_lock;
  906.     static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  907. pthread_mutex_lock(&swap_lock);
  908. cstrptr result = *p;
  909. *p = q;
  910. pthread_mutex_unlock(&swap_lock);
  911. return result;
  912.             }
  913. # else
  914.     static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
  915.                 cstrptr result = *p;
  916.                 *p = q;
  917. return result;
  918.     }
  919. #       endif
  920. static charT empty_c_str[1];
  921.      typedef simple_alloc<charT, Alloc> DataAlloc;
  922.      typedef simple_alloc<__rope_RopeConcatenation<charT,Alloc>, Alloc> CAlloc;
  923.      typedef simple_alloc<__rope_RopeLeaf<charT,Alloc>, Alloc> LAlloc;
  924.      typedef simple_alloc<__rope_RopeFunction<charT,Alloc>, Alloc> FAlloc;
  925.      typedef simple_alloc<__rope_RopeSubstring<charT,Alloc>, Alloc> SAlloc;
  926. static bool is0(charT c) { return c == __eos((charT *)0); }
  927. enum { copy_max = 23 };
  928. // For strings shorter than copy_max, we copy to
  929. // concatenate.
  930. typedef __rope_RopeBase<charT,Alloc> RopeBase;
  931. typedef __rope_RopeConcatenation<charT,Alloc> RopeConcatenation;
  932. typedef __rope_RopeLeaf<charT,Alloc> RopeLeaf;
  933. typedef __rope_RopeFunction<charT,Alloc> RopeFunction;
  934. typedef __rope_RopeSubstring<charT,Alloc> RopeSubstring;
  935. // The only data member of a rope:
  936. RopeBase *tree_ptr;
  937. // Retrieve a character at the indicated position.
  938. static charT fetch(RopeBase * r, size_type pos);
  939. # ifndef __GC
  940.     // Obtain a pointer to the character at the indicated position.
  941.     // The pointer can be used to change the character.
  942.     // If such a pointer cannot be produced, as is frequently the
  943.     // case, 0 is returned instead.
  944.     // (Returns nonzero only if all nodes in the path have a refcount
  945.     // of 1.)
  946.     static charT * fetch_ptr(RopeBase * r, size_type pos);
  947. # endif
  948. static bool apply_to_pieces(
  949. // should be template parameter
  950. __rope_char_consumer<charT>& c,
  951. const RopeBase * r,
  952. size_t begin, size_t end);
  953. // begin and end are assumed to be in range.
  954. # ifndef __GC
  955.   static void unref(RopeBase* t)
  956.   {
  957.       RopeBase::unref(t);
  958.   }
  959.   static void ref(RopeBase* t)
  960.   {
  961.       RopeBase::ref(t);
  962.   }
  963. #       else /* __GC */
  964.   static void unref(RopeBase* t) {}
  965.   static void ref(RopeBase* t) {}
  966. #       endif
  967. #       ifdef __GC
  968.     typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
  969. #    else
  970.     typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
  971. # endif
  972. // Result is counted in refcount.
  973. static RopeBase * substring(RopeBase * base,
  974.     size_t start, size_t endp1);
  975. static RopeBase * concat_char_iter(RopeBase * r,
  976.   const charT *iter, size_t slen);
  977. // Concatenate rope and char ptr, copying s.
  978. // Should really take an arbitrary iterator.
  979. // Result is counted in refcount.
  980. static RopeBase * destr_concat_char_iter(RopeBase * r,
  981.  const charT *iter, size_t slen)
  982. // As above, but one reference to r is about to be
  983. // destroyed.  Thus the pieces may be recycled if all
  984. // relevent reference counts are 1.
  985. #     ifdef __GC
  986. // We can't really do anything since refcounts are unavailable.
  987. { return concat_char_iter(r, iter, slen); }
  988. #     else
  989. ;
  990. #     endif
  991. static RopeBase * concat(RopeBase *left, RopeBase *right);
  992. // General concatenation on RopeBase.  Result
  993. // has refcount of 1.  Adjusts argument refcounts.
  994.    public:
  995. void apply_to_pieces( size_t begin, size_t end,
  996.       __rope_char_consumer<charT>& c) const {
  997.     apply_to_pieces(c, tree_ptr, begin, end);
  998. }
  999.    protected:
  1000. static size_t rounded_up_size(size_t n) {
  1001.     return RopeBase::rounded_up_size(n);
  1002. }
  1003. static size_t allocated_capacity(size_t n) {
  1004.     if (__is_basic_char_type((charT *)0)) {
  1005. return rounded_up_size(n) - 1;
  1006.     } else {
  1007. return rounded_up_size(n);
  1008.     }
  1009. }
  1010. // s should really be an arbitrary input iterator.
  1011. // Adds a trailing NULL for basic char types.
  1012. static charT * alloc_copy(const charT *s, size_t size)
  1013. {
  1014.     charT * result = DataAlloc::allocate(rounded_up_size(size));
  1015.     uninitialized_copy_n(s, size, result);
  1016.     __cond_store_eos(result[size]);
  1017.     return(result);
  1018. }
  1019. // Basic constructors for rope tree nodes.
  1020. // These return tree nodes with a 0 reference count.
  1021. static RopeLeaf * RopeLeaf_from_char_ptr(__GC_CONST charT *s,
  1022.  size_t size);
  1023. // Takes ownership of its argument.
  1024. // Result has refcount 1.
  1025. // In the nonGC, basic_char_type  case it assumes that s
  1026. // is eos-terminated.
  1027. // In the nonGC case, it was allocated from Alloc with
  1028. // rounded_up_size(size).
  1029. static RopeLeaf * RopeLeaf_from_unowned_char_ptr(const charT *s,
  1030.          size_t size) {
  1031.     charT * buf = alloc_copy(s, size);
  1032.             __STL_TRY {
  1033.               return RopeLeaf_from_char_ptr(buf, size);
  1034.             }
  1035.             __STL_UNWIND(RopeBase::free_string(buf, size))
  1036. }
  1037.     
  1038. // Concatenation of nonempty strings.
  1039. // Always builds a concatenation node.
  1040. // Rebalances if the result is too deep.
  1041. // Result has refcount 1.
  1042. // Does not increment left and right ref counts even though
  1043. // they are referenced.
  1044. static RopeBase * tree_concat(RopeBase * left, RopeBase * right);
  1045. // Result has refcount 1.
  1046. // If delete_fn is true, then fn is deleted when the rope
  1047. // becomes inaccessible.
  1048. static RopeFunction * RopeFunction_from_fn
  1049. (char_producer<charT> *fn, size_t size,
  1050.  bool delete_fn);
  1051. // Concatenation helper functions
  1052. static RopeLeaf * leaf_concat_char_iter
  1053. (RopeLeaf * r, const charT * iter, size_t slen);
  1054. // Concatenate by copying leaf.
  1055. // should take an arbitrary iterator
  1056. // result has refcount 1.
  1057. # ifndef __GC
  1058.   static RopeLeaf * destr_leaf_concat_char_iter
  1059. (RopeLeaf * r, const charT * iter, size_t slen);
  1060.   // A version that potentially clobbers r if r -> refcount == 1.
  1061. #       endif
  1062. // A helper function for exponentiating strings.
  1063. // This uses a nonstandard refcount convention.
  1064. // The result has refcount 0.
  1065. struct concat_fn;
  1066. friend struct rope<charT,Alloc>::concat_fn;
  1067. struct concat_fn
  1068. : public binary_function<rope<charT,Alloc>, rope<charT,Alloc>,
  1069.          rope<charT,Alloc> > {
  1070. rope operator() (const rope& x, const rope& y) {
  1071.     return x + y;
  1072. }
  1073. };
  1074.         friend rope identity_element(concat_fn) { return rope<charT,Alloc>(); }
  1075. static size_t char_ptr_len(const charT * s);
  1076. // slightly generalized strlen
  1077. rope(RopeBase *t) : tree_ptr(t) { }
  1078. // Copy r to the CharT buffer.
  1079. // Returns buffer + r -> size.
  1080. // Assumes that buffer is uninitialized.
  1081. static charT * flatten(RopeBase * r, charT * buffer);
  1082. // Again, with explicit starting position and length.
  1083. // Assumes that buffer is uninitialized.
  1084. static charT * flatten(RopeBase * r,
  1085.        size_t start, size_t len,
  1086.        charT * buffer);
  1087. static const unsigned long min_len[RopeBase::max_rope_depth + 1];
  1088. static bool is_balanced(RopeBase *r)
  1089. { return (r -> size >= min_len[r -> depth]); }
  1090. static bool is_almost_balanced(RopeBase *r)
  1091. { return (r -> depth == 0 ||
  1092.   r -> size >= min_len[r -> depth - 1]); }
  1093. static bool is_roughly_balanced(RopeBase *r)
  1094. { return (r -> depth <= 1 ||
  1095.   r -> size >= min_len[r -> depth - 2]); }
  1096. // Assumes the result is not empty.
  1097. static RopeBase * concat_and_set_balanced(RopeBase *left,
  1098.   RopeBase *right)
  1099. {
  1100.     RopeBase * result = concat(left, right);
  1101.     if (is_balanced(result)) result -> is_balanced = true;
  1102.     return result;
  1103. }
  1104. // The basic rebalancing operation.  Logically copies the
  1105. // rope.  The result has refcount of 1.  The client will
  1106. // usually decrement the reference count of r.
  1107. // The result isd within height 2 of balanced by the above
  1108. // definition.
  1109. static RopeBase * balance(RopeBase * r);
  1110. // Add all unbalanced subtrees to the forest of balanceed trees.
  1111. // Used only by balance.
  1112. static void add_to_forest(RopeBase *r, RopeBase **forest);
  1113. // Add r to forest, assuming r is already balanced.
  1114. static void add_leaf_to_forest(RopeBase *r, RopeBase **forest);
  1115. // Print to stdout, exposing structure
  1116. static void dump(RopeBase * r, int indent = 0);
  1117. // Return -1, 0, or 1 if x < y, x == y, or x > y resp.
  1118. static int compare(const RopeBase *x, const RopeBase *y);
  1119.    public:
  1120. bool empty() const { return 0 == tree_ptr; }
  1121. // Comparison member function.  This is public only for those
  1122. // clients that need a ternary comparison.  Others
  1123. // should use the comparison operators below.
  1124. int compare(const rope &y) const {
  1125.     return compare(tree_ptr, y.tree_ptr);
  1126. }
  1127. rope(const charT *s)
  1128. {
  1129.     size_t len = char_ptr_len(s);
  1130.     if (0 == len) {
  1131. tree_ptr = 0;
  1132.     } else {
  1133. tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1134. # ifndef __GC
  1135.   __stl_assert(1 == tree_ptr -> refcount);
  1136. # endif
  1137.     }
  1138. }
  1139. rope(const charT *s, size_t len)
  1140. {
  1141.     if (0 == len) {
  1142. tree_ptr = 0;
  1143.     } else {
  1144. tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1145.     }
  1146. }
  1147. rope(const charT *s, charT *e)
  1148. {
  1149.     size_t len = e - s;
  1150.     if (0 == len) {
  1151. tree_ptr = 0;
  1152.     } else {
  1153. tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
  1154.     }
  1155. }
  1156. rope(const const_iterator& s, const const_iterator& e)
  1157. {
  1158.     tree_ptr = substring(s.root, s.current_pos, e.current_pos);
  1159. }
  1160. rope(const iterator& s, const iterator& e)
  1161. {
  1162.     tree_ptr = substring(s.root, s.current_pos, e.current_pos);
  1163. }
  1164. rope(charT c)
  1165. {
  1166.     charT * buf = DataAlloc::allocate(rounded_up_size(1));
  1167.     construct(buf, c);
  1168.     __STL_TRY {
  1169.         tree_ptr = RopeLeaf_from_char_ptr(buf, 1);
  1170.             }
  1171.             __STL_UNWIND(RopeBase::free_string(buf, 1))
  1172. }
  1173. rope(size_t n, charT c);
  1174. // Should really be templatized with respect to the iterator type
  1175. // and use sequence_buffer.  (It should perhaps use sequence_buffer
  1176. // even now.)
  1177. rope(const charT *i, const charT *j)
  1178. {
  1179.     if (i == j) {
  1180. tree_ptr = 0;
  1181.     } else {
  1182. size_t len = j - i;
  1183. tree_ptr = RopeLeaf_from_unowned_char_ptr(i, len);
  1184.     }
  1185. }
  1186. rope()
  1187. {
  1188.     tree_ptr = 0;
  1189. }
  1190. // Construct a rope from a function that can compute its members
  1191. rope(char_producer<charT> *fn, size_t len, bool delete_fn)
  1192. {
  1193.     tree_ptr = RopeFunction_from_fn(fn, len, delete_fn);
  1194. }
  1195. rope(const rope &x)
  1196. {
  1197.     tree_ptr = x.tree_ptr;
  1198.     ref(tree_ptr);
  1199. }
  1200. ~rope()
  1201. {
  1202.     unref(tree_ptr);
  1203. }
  1204. rope& operator=(const rope& x)
  1205. {
  1206.     RopeBase *old = tree_ptr;
  1207.     tree_ptr = x.tree_ptr;
  1208.     ref(tree_ptr);
  1209.     unref(old);
  1210.     return(*this);
  1211. }
  1212. void push_back(charT x)
  1213. {
  1214.     RopeBase *old = tree_ptr;
  1215.     tree_ptr = concat_char_iter(tree_ptr, &x, 1);
  1216.     unref(old);
  1217. }
  1218. void pop_back()
  1219. {
  1220.     RopeBase *old = tree_ptr;
  1221.     tree_ptr = substring(tree_ptr, 0, tree_ptr -> size - 1);
  1222.     unref(old);
  1223. }
  1224. charT back() const
  1225. {
  1226.     return fetch(tree_ptr, tree_ptr -> size - 1);
  1227. }
  1228. void push_front(charT x)
  1229. {
  1230.     RopeBase *old = tree_ptr;
  1231.     RopeBase *left;
  1232.     left = RopeLeaf_from_unowned_char_ptr(&x, 1);
  1233.     __STL_TRY {
  1234.       tree_ptr = concat(left, tree_ptr);
  1235.       unref(old);
  1236.               unref(left);
  1237.             }
  1238.     __STL_UNWIND(unref(left))
  1239. }
  1240. void pop_front()
  1241. {
  1242.     RopeBase *old = tree_ptr;
  1243.     tree_ptr = substring(tree_ptr, 1, tree_ptr -> size);
  1244.     unref(old);
  1245. }
  1246. charT front() const
  1247. {
  1248.     return fetch(tree_ptr, 0);
  1249. }
  1250. void balance()
  1251. {
  1252.     RopeBase *old = tree_ptr;
  1253.     tree_ptr = balance(tree_ptr);
  1254.     unref(old);
  1255. }
  1256. void copy(charT * buffer) const {
  1257.     destroy(buffer, buffer + size());
  1258.     flatten(tree_ptr, buffer);
  1259. }
  1260. // This is the copy function from the standard, but
  1261. // with the arguments reordered to make it consistent with the
  1262. // rest of the interface.
  1263. // Note that this guaranteed not to compile if the draft standard
  1264. // order is assumed.
  1265. size_type copy(size_type pos, size_type n, charT *buffer) const {
  1266.     size_t sz = size();
  1267.     size_t len = (pos + n > sz? sz - pos : n);
  1268.     destroy(buffer, buffer + len);
  1269.     flatten(tree_ptr, pos, len, buffer);
  1270.     return len;
  1271. }
  1272. // Print to stdout, exposing structure.  May be useful for
  1273. // performance debugging.
  1274. void dump() {
  1275.     dump(tree_ptr);
  1276. }
  1277. // Convert to 0 terminated string in new allocated memory.
  1278. // Embedded 0s in the input do not terminate the copy.
  1279. const charT * c_str() const;
  1280. // As above, but lso use the flattened representation as the
  1281. // the new rope representation.
  1282. const charT * replace_with_c_str();
  1283. // Reclaim memory for the c_str generated flattened string.
  1284. // Intentionally undocumented, since it's hard to say when this
  1285. // is safe for multiple threads.
  1286. void delete_c_str () {
  1287.     if (0 == tree_ptr) return;
  1288.     if (RopeBase::leaf == tree_ptr -> tag
  1289. && ((RopeLeaf *)tree_ptr) -> data == tree_ptr -> c_string) {
  1290. // Representation shared
  1291. return;
  1292.     }
  1293. #     ifndef __GC
  1294.       tree_ptr -> free_c_string();
  1295. #     endif
  1296.     tree_ptr -> c_string = 0;
  1297. }
  1298. charT operator[] (size_type pos) const {
  1299.     return fetch(tree_ptr, pos);
  1300. }
  1301. charT at(size_type pos) const {
  1302.    // if (pos >= size()) throw out_of_range;
  1303.    return (*this)[pos];
  1304. }
  1305. const_iterator begin() const {
  1306.     return(const_iterator(tree_ptr, 0));
  1307. }
  1308. // An easy way to get a const iterator from a non-const container.
  1309. const_iterator const_begin() const {
  1310.     return(const_iterator(tree_ptr, 0));
  1311. }
  1312. const_iterator end() const {
  1313.     return(const_iterator(tree_ptr, size()));
  1314. }
  1315. const_iterator const_end() const {
  1316.     return(const_iterator(tree_ptr, size()));
  1317. }
  1318. size_type size() const { 
  1319.     return(0 == tree_ptr? 0 : tree_ptr -> size);
  1320. }
  1321. size_type length() const {
  1322.     return size();
  1323. }
  1324. size_type max_size() const {
  1325.     return min_len[RopeBase::max_rope_depth-1] - 1;
  1326.     //  Guarantees that the result can be sufficirntly
  1327.     //  balanced.  Longer ropes will probably still work,
  1328.     //  but it's harder to make guarantees.
  1329. }
  1330. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1331.         typedef reverse_iterator<const_iterator> const_reverse_iterator;
  1332. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1333. typedef reverse_iterator<const_iterator, value_type, const_reference,
  1334.  difference_type>  const_reverse_iterator;
  1335. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  1336. const_reverse_iterator rbegin() const {
  1337.     return const_reverse_iterator(end());
  1338. }
  1339. const_reverse_iterator const_rbegin() const {
  1340.     return const_reverse_iterator(end());
  1341. }
  1342. const_reverse_iterator rend() const {
  1343.     return const_reverse_iterator(begin());
  1344. }
  1345. const_reverse_iterator const_rend() const {
  1346.     return const_reverse_iterator(begin());
  1347. }
  1348. friend rope<charT,Alloc>
  1349.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1350.                                         const rope<charT,Alloc> &right);
  1351. friend rope<charT,Alloc>
  1352.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1353.                                         const charT* right);
  1354. friend rope<charT,Alloc>
  1355.         operator+ __STL_NULL_TMPL_ARGS (const rope<charT,Alloc> &left,
  1356.                                         charT right);
  1357. // The symmetric cases are intentionally omitted, since they're presumed
  1358. // to be less common, and we don't handle them as well.
  1359. // The following should really be templatized.
  1360. // The first argument should be an input iterator or
  1361. // forward iterator with value_type charT.
  1362. rope& append(const charT* iter, size_t n) {
  1363.     RopeBase* result = destr_concat_char_iter(tree_ptr, iter, n);
  1364.     unref(tree_ptr);
  1365.     tree_ptr = result;
  1366.     return *this;
  1367. }
  1368. rope& append(const charT* c_string) {
  1369.     size_t len = char_ptr_len(c_string);
  1370.     append(c_string, len);
  1371.     return(*this);
  1372. }
  1373. rope& append(const charT* s, const charT* e) {
  1374.     RopeBase* result =
  1375. destr_concat_char_iter(tree_ptr, s, e - s);
  1376.     unref(tree_ptr);
  1377.     tree_ptr = result;
  1378.     return *this;
  1379. }
  1380. rope& append(const_iterator s, const_iterator e) {
  1381.     __stl_assert(s.root == e.root);
  1382.     self_destruct_ptr appendee(substring(s.root, s.current_pos,
  1383.  e.current_pos));
  1384.     RopeBase* result = concat(tree_ptr, (RopeBase *)appendee);
  1385.     unref(tree_ptr);
  1386.     tree_ptr = result;
  1387.     return *this;
  1388. }
  1389. rope& append(charT c) {
  1390.     RopeBase* result = destr_concat_char_iter(tree_ptr, &c, 1);
  1391.     unref(tree_ptr);
  1392.     tree_ptr = result;
  1393.     return *this;
  1394. }
  1395. rope& append() { return append(charT()); }
  1396. rope& append(const rope& y) {
  1397.     RopeBase* result = concat(tree_ptr, y.tree_ptr);
  1398.     unref(tree_ptr);
  1399.     tree_ptr = result;
  1400.     return *this;
  1401. }
  1402. rope& append(size_t n, charT c) {
  1403.     rope<charT,Alloc> last(n, c);
  1404.     return append(last);
  1405. }
  1406. void swap(rope& b) {
  1407.     RopeBase * tmp = tree_ptr;
  1408.     tree_ptr = b.tree_ptr;
  1409.     b.tree_ptr = tmp;
  1410. }
  1411.     protected:
  1412. // Result is included in refcount.
  1413. static RopeBase * replace(RopeBase *old, size_t pos1,
  1414.   size_t pos2, RopeBase *r) {
  1415.     if (0 == old) { ref(r); return r; }
  1416.     self_destruct_ptr left(substring(old, 0, pos1));
  1417.     self_destruct_ptr right(substring(old, pos2, old -> size));
  1418.     RopeBase * result;
  1419.     if (0 == r) {
  1420. result = concat(left, right);
  1421.     } else {
  1422. self_destruct_ptr left_result(concat(left, r));
  1423. result = concat(left_result, right);
  1424.     }
  1425.     return result;
  1426. }
  1427.     public:
  1428. void insert(size_t p, const rope& r) {
  1429.     RopeBase * result = replace(tree_ptr, p, p,
  1430.        r.tree_ptr);
  1431.     unref(tree_ptr);
  1432.     tree_ptr = result;
  1433. }
  1434. void insert(size_t p, size_t n, charT c) {
  1435.     rope<charT,Alloc> r(n,c);
  1436.     insert(p, r);
  1437. }
  1438. void insert(size_t p, const charT * i, size_t n) {
  1439.     self_destruct_ptr left(substring(tree_ptr, 0, p));
  1440.     self_destruct_ptr right(substring(tree_ptr, p, size()));
  1441.     self_destruct_ptr left_result(concat_char_iter(left, i, n));
  1442.     RopeBase * result =
  1443. concat(left_result, right);
  1444.     unref(tree_ptr);
  1445.     tree_ptr = result;
  1446. }
  1447. void insert(size_t p, const charT * c_string) {
  1448.     insert(p, c_string, char_ptr_len(c_string));
  1449. }
  1450. void insert(size_t p, charT c) {
  1451.     insert(p, &c, 1);
  1452. }
  1453. void insert(size_t p) {
  1454.     charT c = charT();
  1455.     insert(p, &c, 1);
  1456. }
  1457. void insert(size_t p, const charT *i, const charT *j) {
  1458.     rope r(i, j);
  1459.     insert(p, r);
  1460. }
  1461. void insert(size_t p, const const_iterator& i,
  1462.       const const_iterator& j) {
  1463.     rope r(i, j);
  1464.     insert(p, r);
  1465. }
  1466. void insert(size_t p, const iterator& i,
  1467.       const iterator& j) {
  1468.     rope r(i, j);
  1469.     insert(p, r);
  1470. }
  1471. // (position, length) versions of replace operations:
  1472. void replace(size_t p, size_t n, const rope& r) {
  1473.     RopeBase * result = replace(tree_ptr, p, p + n,
  1474.        r.tree_ptr);
  1475.     unref(tree_ptr);
  1476.     tree_ptr = result;
  1477. }
  1478. void replace(size_t p, size_t n, const charT *i, size_t i_len) {
  1479.     rope r(i, i_len);
  1480.     replace(p, n, r);
  1481. }
  1482. void replace(size_t p, size_t n, charT c) {
  1483.     rope r(c);
  1484.     replace(p, n, r);
  1485. }
  1486. void replace(size_t p, size_t n, const charT *c_string) {
  1487.     rope r(c_string);
  1488.     replace(p, n, r);
  1489. }
  1490. void replace(size_t p, size_t n, const charT *i, const charT *j) {
  1491.     rope r(i, j);
  1492.     replace(p, n, r);
  1493. }
  1494. void replace(size_t p, size_t n,
  1495.      const const_iterator& i, const const_iterator& j) {
  1496.     rope r(i, j);
  1497.     replace(p, n, r);
  1498. }
  1499. void replace(size_t p, size_t n,
  1500.      const iterator& i, const iterator& j) {
  1501.     rope r(i, j);
  1502.     replace(p, n, r);
  1503. }
  1504. // Single character variants:
  1505. void replace(size_t p, charT c) {
  1506.     iterator i(this, p);
  1507.     *i = c;
  1508. }
  1509. void replace(size_t p, const rope& r) {
  1510.     replace(p, 1, r);
  1511. }
  1512. void replace(size_t p, const charT *i, size_t i_len) {
  1513.     replace(p, 1, i, i_len);
  1514. }
  1515. void replace(size_t p, const charT *c_string) {
  1516.     replace(p, 1, c_string);
  1517. }
  1518. void replace(size_t p, const charT *i, const charT *j) {
  1519.     replace(p, 1, i, j);
  1520. }
  1521. void replace(size_t p, const const_iterator& i,
  1522.        const const_iterator& j) {
  1523.     replace(p, 1, i, j);
  1524. }
  1525. void replace(size_t p, const iterator& i,
  1526.        const iterator& j) {
  1527.     replace(p, 1, i, j);
  1528. }
  1529. // Erase, (position, size) variant.
  1530. void erase(size_t p, size_t n) {
  1531.     RopeBase * result = replace(tree_ptr, p, p + n, 0);
  1532.     unref(tree_ptr);
  1533.     tree_ptr = result;
  1534. }
  1535. // Erase, single character
  1536. void erase(size_t p) {
  1537.     erase(p, p + 1);
  1538. }
  1539. // Insert, iterator variants.  
  1540. iterator insert(const iterator& p, const rope& r)
  1541. { insert(p.index(), r); return p; }
  1542. iterator insert(const iterator& p, size_t n, charT c)
  1543. { insert(p.index(), n, c); return p; }
  1544. iterator insert(const iterator& p, charT c) 
  1545. { insert(p.index(), c); return p; }
  1546. iterator insert(const iterator& p ) 
  1547. { insert(p.index()); return p; }
  1548. iterator insert(const iterator& p, const charT *c_string) 
  1549. { insert(p.index(), c_string); return p; }
  1550. iterator insert(const iterator& p, const charT *i, size_t n)
  1551. { insert(p.index(), i, n); return p; }
  1552. iterator insert(const iterator& p, const charT *i, const charT *j)
  1553. { insert(p.index(), i, j);  return p; }
  1554. iterator insert(const iterator& p,
  1555. const const_iterator& i, const const_iterator& j)
  1556. { insert(p.index(), i, j); return p; }
  1557. iterator insert(const iterator& p,
  1558. const iterator& i, const iterator& j)
  1559. { insert(p.index(), i, j); return p; }
  1560. // Replace, range variants.
  1561. void replace(const iterator& p, const iterator& q,
  1562.      const rope& r)
  1563. { replace(p.index(), q.index() - p.index(), r); }
  1564. void replace(const iterator& p, const iterator& q, charT c)
  1565. { replace(p.index(), q.index() - p.index(), c); }
  1566. void replace(const iterator& p, const iterator& q,
  1567.      const charT * c_string)
  1568. { replace(p.index(), q.index() - p.index(), c_string); }
  1569. void replace(const iterator& p, const iterator& q,
  1570.      const charT *i, size_t n)
  1571. { replace(p.index(), q.index() - p.index(), i, n); }
  1572. void replace(const iterator& p, const iterator& q,
  1573.      const charT *i, const charT *j)
  1574. { replace(p.index(), q.index() - p.index(), i, j); }
  1575. void replace(const iterator& p, const iterator& q,
  1576.      const const_iterator& i, const const_iterator& j)
  1577. { replace(p.index(), q.index() - p.index(), i, j); }
  1578. void replace(const iterator& p, const iterator& q,
  1579.      const iterator& i, const iterator& j)
  1580. { replace(p.index(), q.index() - p.index(), i, j); }
  1581. // Replace, iterator variants.
  1582. void replace(const iterator& p, const rope& r)
  1583. { replace(p.index(), r); }
  1584. void replace(const iterator& p, charT c)
  1585. { replace(p.index(), c); }
  1586. void replace(const iterator& p, const charT * c_string)
  1587. { replace(p.index(), c_string); }
  1588. void replace(const iterator& p, const charT *i, size_t n)
  1589. { replace(p.index(), i, n); }
  1590. void replace(const iterator& p, const charT *i, const charT *j)
  1591. { replace(p.index(), i, j); }
  1592. void replace(const iterator& p, const_iterator i, const_iterator j)
  1593. { replace(p.index(), i, j); }
  1594. void replace(const iterator& p, iterator i, iterator j)
  1595. { replace(p.index(), i, j); }
  1596. // Iterator and range variants of erase
  1597. iterator erase(const iterator &p, const iterator &q) {
  1598.             size_t p_index = p.index();
  1599.             erase(p_index, q.index() - p_index);
  1600.             return iterator(this, p_index);
  1601.         }
  1602.         iterator erase(const iterator &p) {
  1603.             size_t p_index = p.index();
  1604.             erase(p_index, 1);
  1605.             return iterator(this, p_index);
  1606.         }
  1607. rope substr(size_t start, size_t len = 1) const {
  1608.     return rope<charT,Alloc>(
  1609. substring(tree_ptr, start, start + len));
  1610. }
  1611. rope substr(iterator start, iterator end) const {
  1612.     return rope<charT,Alloc>(
  1613. substring(tree_ptr, start.index(), end.index()));
  1614. }
  1615. rope substr(iterator start) const {
  1616.     size_t pos = start.index();
  1617.     return rope<charT,Alloc>(
  1618. substring(tree_ptr, pos, pos + 1));
  1619. }
  1620. rope substr(const_iterator start, const_iterator end) const {
  1621.     // This might eventually take advantage of the cache in the
  1622.     // iterator.
  1623.     return rope<charT,Alloc>
  1624. (substring(tree_ptr, start.index(), end.index()));
  1625. }
  1626. rope<charT,Alloc> substr(const_iterator start) {
  1627.     size_t pos = start.index();
  1628.     return rope<charT,Alloc>(substring(tree_ptr, pos, pos + 1));
  1629. }
  1630. size_type find(charT c, size_type pos = 0) const;
  1631. size_type find(charT *s, size_type pos = 0) const {
  1632.     const_iterator result = search(const_begin() + pos, const_end(),
  1633.    s, s + char_ptr_len(s));
  1634.     return result.index();
  1635. }
  1636. iterator mutable_begin() {
  1637.     return(iterator(this, 0));
  1638. }
  1639. iterator mutable_end() {
  1640.     return(iterator(this, size()));
  1641. }
  1642. #     ifdef __STL_CLASS_PARTIAL_SPECIALIZATION
  1643.         typedef reverse_iterator<iterator> reverse_iterator;
  1644. #     else /* __STL_CLASS_PARTIAL_SPECIALIZATION */
  1645. typedef reverse_iterator<iterator, value_type, reference,
  1646.  difference_type>  reverse_iterator;
  1647. #     endif /* __STL_CLASS_PARTIAL_SPECIALIZATION */ 
  1648. reverse_iterator mutable_rbegin() {
  1649.     return reverse_iterator(mutable_end());
  1650. }
  1651. reverse_iterator mutable_rend() {
  1652.     return reverse_iterator(mutable_begin());
  1653. }
  1654. reference mutable_reference_at(size_type pos) {
  1655.     return reference(this, pos);
  1656. }
  1657. # ifdef __STD_STUFF
  1658.     reference operator[] (size_type pos) {
  1659. return charT_ref_proxy(this, pos);
  1660.     }
  1661.     reference at(size_type pos) {
  1662. // if (pos >= size()) throw out_of_range;
  1663. return (*this)[pos];
  1664.     }
  1665.     void resize(size_type n, charT c) {}
  1666.     void resize(size_type n) {}
  1667.     void reserve(size_type res_arg = 0) {}
  1668.     size_type capacity() const {
  1669. return max_size();
  1670.     }
  1671.   // Stuff below this line is dangerous because it's error prone.
  1672.   // I would really like to get rid of it.
  1673.     // copy function with funny arg ordering.
  1674.       size_type copy(charT *buffer, size_type n, size_type pos = 0)
  1675. const {
  1676. return copy(pos, n, buffer);
  1677.       }
  1678.     iterator end() { return mutable_end(); }
  1679.     iterator begin() { return mutable_begin(); }
  1680.     reverse_iterator rend() { return mutable_rend(); }
  1681.     reverse_iterator rbegin() { return mutable_rbegin(); }
  1682. # else
  1683.     const_iterator end() { return const_end(); }
  1684.     const_iterator begin() { return const_begin(); }
  1685.     const_reverse_iterator rend() { return const_rend(); }
  1686.   
  1687.     const_reverse_iterator rbegin() { return const_rbegin(); }
  1688. # endif
  1689. };
  1690. template <class charT, class Alloc>
  1691. inline bool operator== (const __rope_const_iterator<charT,Alloc> & x,
  1692. const __rope_const_iterator<charT,Alloc> & y) {
  1693. return (x.current_pos == y.current_pos && x.root == y.root);
  1694. }
  1695. template <class charT, class Alloc>
  1696. inline bool operator< (const __rope_const_iterator<charT,Alloc> & x,
  1697.        const __rope_const_iterator<charT,Alloc> & y) {
  1698. return (x.current_pos < y.current_pos);
  1699. }
  1700. template <class charT, class Alloc>
  1701. inline ptrdiff_t operator-(const __rope_const_iterator<charT,Alloc> & x,
  1702.    const __rope_const_iterator<charT,Alloc> & y) {
  1703. return x.current_pos - y.current_pos;
  1704. }
  1705. template <class charT, class Alloc>
  1706. inline __rope_const_iterator<charT,Alloc>
  1707. operator-(const __rope_const_iterator<charT,Alloc> & x,
  1708.   ptrdiff_t n) {
  1709. return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos - n);
  1710. }
  1711. template <class charT, class Alloc>
  1712. inline __rope_const_iterator<charT,Alloc>
  1713. operator+(const __rope_const_iterator<charT,Alloc> & x,
  1714.   ptrdiff_t n) {
  1715. return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
  1716. }
  1717. template <class charT, class Alloc>
  1718. inline __rope_const_iterator<charT,Alloc>
  1719. operator+(ptrdiff_t n,
  1720.   const __rope_const_iterator<charT,Alloc> & x) {
  1721. return __rope_const_iterator<charT,Alloc>(x.root, x.current_pos + n);
  1722. }
  1723. template <class charT, class Alloc>
  1724. inline bool operator== (const __rope_iterator<charT,Alloc> & x,
  1725. const __rope_iterator<charT,Alloc> & y) {
  1726. return (x.current_pos == y.current_pos && x.root_rope == y.root_rope);
  1727. }
  1728. template <class charT, class Alloc>
  1729. inline bool operator< (const __rope_iterator<charT,Alloc> & x,
  1730. const __rope_iterator<charT,Alloc> & y) {
  1731. return (x.current_pos < y.current_pos);
  1732. }
  1733. template <class charT, class Alloc>
  1734. inline ptrdiff_t operator-(const __rope_iterator<charT,Alloc> & x,
  1735.    const __rope_iterator<charT,Alloc> & y) {
  1736. return x.current_pos - y.current_pos;
  1737. }
  1738. template <class charT, class Alloc>
  1739. inline __rope_iterator<charT,Alloc>
  1740. operator-(const __rope_iterator<charT,Alloc> & x,
  1741.   ptrdiff_t n) {
  1742. return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos - n);
  1743. }
  1744. template <class charT, class Alloc>
  1745. inline __rope_iterator<charT,Alloc>
  1746. operator+(const __rope_iterator<charT,Alloc> & x,
  1747.   ptrdiff_t n) {
  1748. return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
  1749. }
  1750. template <class charT, class Alloc>
  1751. inline __rope_iterator<charT,Alloc>
  1752. operator+(ptrdiff_t n,
  1753.   const __rope_iterator<charT,Alloc> & x) {
  1754. return __rope_iterator<charT,Alloc>(x.root_rope, x.current_pos + n);
  1755. }
  1756. template <class charT, class Alloc>
  1757. inline
  1758. rope<charT,Alloc>
  1759. operator+ (const rope<charT,Alloc> &left,
  1760.    const rope<charT,Alloc> &right)
  1761. {
  1762.     return rope<charT,Alloc>
  1763. (rope<charT,Alloc>::concat(left.tree_ptr, right.tree_ptr));
  1764.     // Inlining this should make it possible to keep left and
  1765.     // right in registers.
  1766. }
  1767. template <class charT, class Alloc>
  1768. inline
  1769. rope<charT,Alloc>&
  1770. operator+= (rope<charT,Alloc> &left,
  1771.     const rope<charT,Alloc> &right)
  1772. {
  1773.     left.append(right);
  1774.     return left;
  1775. }
  1776. template <class charT, class Alloc>
  1777. inline
  1778. rope<charT,Alloc>
  1779. operator+ (const rope<charT,Alloc> &left,
  1780.    const charT* right) {
  1781.     size_t rlen = rope<charT,Alloc>::char_ptr_len(right);
  1782.     return rope<charT,Alloc>
  1783.    (rope<charT,Alloc>::concat_char_iter(left.tree_ptr, right, rlen)); 
  1784. }
  1785. template <class charT, class Alloc>
  1786. inline
  1787. rope<charT,Alloc>&
  1788. operator+= (rope<charT,Alloc> &left,
  1789.     const charT* right) {
  1790.     left.append(right);
  1791.     return left;
  1792. }
  1793. template <class charT, class Alloc>
  1794. inline
  1795. rope<charT,Alloc>
  1796. operator+ (const rope<charT,Alloc> &left, charT right) {
  1797.     return rope<charT,Alloc>
  1798. (rope<charT,Alloc>::concat_char_iter(left.tree_ptr, &right, 1));
  1799. }
  1800. template <class charT, class Alloc>
  1801. inline
  1802. rope<charT,Alloc>&
  1803. operator+= (rope<charT,Alloc> &left, charT right) {
  1804.     left.append(right);
  1805.     return left;
  1806. }
  1807. template <class charT, class Alloc>
  1808. bool
  1809. operator< (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
  1810.     return left.compare(right) < 0;
  1811. }
  1812. template <class charT, class Alloc>
  1813. bool
  1814. operator== (const rope<charT,Alloc> &left, const rope<charT,Alloc> &right) {
  1815.     return left.compare(right) == 0;
  1816. }
  1817. template <class charT, class Alloc>
  1818. inline bool operator== (const __rope_charT_ptr_proxy<charT,Alloc> & x,
  1819. const __rope_charT_ptr_proxy<charT,Alloc> & y) {
  1820. return (x.pos == y.pos && x.root == y.root);
  1821. }
  1822. template<class charT, class Alloc>
  1823. ostream& operator<< (ostream& o, const rope<charT, Alloc>& r);        
  1824. typedef rope<char, __ALLOC> crope;
  1825. typedef rope<wchar_t, __ALLOC> wrope;
  1826. inline crope::reference __mutable_reference_at(crope& c, size_t i)
  1827. {
  1828.     return c.mutable_reference_at(i);
  1829. }
  1830. inline wrope::reference __mutable_reference_at(wrope& c, size_t i)
  1831. {
  1832.     return c.mutable_reference_at(i);
  1833. }
  1834. #ifdef __STL_FUNCTION_TMPL_PARTIAL_ORDER
  1835. template <class charT, class Alloc>
  1836. inline void swap(rope<charT, Alloc>& x, rope<charT, Alloc>& y) {
  1837.   x.swap(y);
  1838. }
  1839. #else
  1840. inline void swap(crope x, crope y) { x.swap(y); }
  1841. inline void swap(wrope x, wrope y) { x.swap(y); }
  1842. #endif /* __STL_FUNCTION_TMPL_PARTIAL_ORDER */
  1843. // Hash functions should probably be revisited later:
  1844. __STL_TEMPLATE_NULL struct hash<crope>
  1845. {
  1846.   size_t operator()(const crope& str) const
  1847.   {
  1848.     size_t sz = str.size();
  1849.     if (0 == sz) return 0;
  1850.     return 13*str[0] + 5*str[sz - 1] + sz;
  1851.   }
  1852. };
  1853. __STL_TEMPLATE_NULL struct hash<wrope>
  1854. {
  1855.   size_t operator()(const wrope& str) const
  1856.   {
  1857.     size_t sz = str.size();
  1858.     if (0 == sz) return 0;
  1859.     return 13*str[0] + 5*str[sz - 1] + sz;
  1860.   }
  1861. };
  1862. #if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
  1863. #pragma reset woff 1174
  1864. #endif
  1865. __STL_END_NAMESPACE
  1866. # include <ropeimpl.h>
  1867. # endif /* __SGI_STL_INTERNAL_ROPE_H */
  1868. // Local Variables:
  1869. // mode:C++
  1870. // End: