/* * Copyright (c) 1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. *//* NOTE: This is an internal header file, included by other STL headers. *   You should not attempt to use it directly. */#ifndef __SGI_STL_INTERNAL_ROPE_H# define __SGI_STL_INTERNAL_ROPE_H# ifdef __GC#   define __GC_CONST const# else#   define __GC_CONST   // constant except for deallocation# endif# ifdef __STL_SGI_THREADS#    include <mutex.h># endif__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)#pragma set woff 1174#endif// The end-of-C-string character.// This is what the draft standard says it should be.template <class charT>inline charT __eos(charT*) { return charT(); }// Test for basic character types.// For basic character types leaves having a trailing eos.template <class charT>inline bool __is_basic_char_type(charT *) { return false; }template <class charT>inline bool __is_one_byte_char_type(charT *) { return false; }inline bool __is_basic_char_type(char *) { return true; }inline bool __is_one_byte_char_type(char *) { return true; }inline bool __is_basic_char_type(wchar_t *) { return true; }// Store an eos iff charT is a basic character type.// Do not reference __eos if it isn't.template <class charT>inline void __cond_store_eos(charT&) {}inline void __cond_store_eos(char& c) { c = 0; }inline void __cond_store_eos(wchar_t& c) { c = 0; }	// rope<charT,Alloc> is a sequence of charT.// Ropes appear to be mutable, but update operations// really copy enough of the data structure to leave the original// valid.  Thus ropes can be logically copied by just copying// a pointer value.// The __eos function is used for those functions that// convert to/from C-like strings to detect the end of the string.// __compare is used as the character comparison function.template <class charT>class char_producer {    public:	virtual ~char_producer() {};	virtual void operator()(size_t start_pos, size_t len, charT* buffer)		= 0;	// Buffer should really be an arbitrary output iterator.	// That way we could flatten directly into an ostream, etc.	// This is thoroughly impossible, since iterator types don't	// have runtime descriptions.};// Sequence buffers://// Sequence must provide an append operation that appends an// array to the sequence.  Sequence buffers are useful only if// appending an entire array is cheaper than appending element by element.// This is true for many string representations.// This should  perhaps inherit from ostream<sequence::value_type>// and be implemented correspondingly, so that they can be used// for formatted.  For the sake of portability, we don't do this yet.//// For now, sequence buffers behave as output iterators.  But they also// behave a little like basic_ostringstream<sequence::value_type> and a// little like containers.template<class sequence, size_t buf_sz = 100#   if defined(__sgi) && !defined(__GNUC__)#	 define __TYPEDEF_WORKAROUND         ,class v = typename sequence::value_type#   endif        >// The 3rd parameter works around a common compiler bug.class sequence_buffer : public output_iterator {    public:#       ifndef __TYPEDEF_WORKAROUND	    typedef typename sequence::value_type value_type;#	else	    typedef v value_type;#	endif    protected:	sequence *prefix;	value_type buffer[buf_sz];	size_t buf_count;    public:	void flush() {	    prefix->append(buffer, buffer + buf_count);	    buf_count = 0;	}	~sequence_buffer() { flush(); }	sequence_buffer() : prefix(0), buf_count(0) {}	sequence_buffer(const sequence_buffer & x) {	    prefix = x.prefix;            buf_count = x.buf_count;            copy(x.buffer, x.buffer + x.buf_count, buffer);	}	sequence_buffer(sequence_buffer & x) {	    x.flush();	    prefix = x.prefix;	    buf_count = 0;	}	sequence_buffer(sequence& s) : prefix(&s), buf_count(0) {}	sequence_buffer& operator= (sequence_buffer& x) {	    x.flush();	    prefix = x.prefix;	    buf_count = 0;	    return *this;	}	sequence_buffer& operator= (const sequence_buffer& x) {	    prefix = x.prefix;	    buf_count = x.buf_count;	    copy(x.buffer, x.buffer + x.buf_count, buffer);	    return *this;	}	void push_back(value_type x)	{	    if (buf_count < buf_sz) {		buffer[buf_count] = x;		++buf_count;	    } else {		flush();		buffer[0] = x;		buf_count = 1;	    }	}	void append(value_type *s, size_t len)	{	    if (len + buf_count <= buf_sz) {		size_t i, j;		for (i = buf_count, j = 0; j < len; i++, j++) {		    buffer[i] = s[j];		}		buf_count += len;	    } else if (0 == buf_count) {		prefix->append(s, s + len);	    } else {		flush();		append(s, len);	    }	}	sequence_buffer& write(value_type *s, size_t len)	{	    append(s, len);	    return *this;	}	sequence_buffer& put(value_type x)	{	    push_back(x);	    return *this;	}	sequence_buffer& operator=(const value_type& rhs)	{	    push_back(rhs);	    return *this;	}	sequence_buffer& operator*() { return *this; }	sequence_buffer& operator++() { return *this; }	sequence_buffer& operator++(int) { return *this; }};// The following should be treated as private, at least for now.template<class charT>class __rope_char_consumer {    public:	// If we had member templates, these should not be virtual.	// For now we need to use run-time parametrization where	// compile-time would do.  Hence this should all be private	// for now.	// The symmetry with char_producer is accidental and temporary.	virtual ~__rope_char_consumer() {};	virtual bool operator()(const charT* buffer, size_t len) = 0;};//// What follows should really be local to rope.  Unfortunately,// that doesn't work, since it makes it impossible to define generic// equality on rope iterators.  According to the draft standard, the// template parameters for such an equality operator cannot be inferred// from the occurence of a member class as a parameter.// (SGI compilers in fact allow this, but the result wouldn't be// portable.)// Similarly, some of the static member functions are member functions// only to avoid polluting the global namespace, and to circumvent// restrictions on type inference for template functions.//template<class CharT, class Alloc=__ALLOC> class rope;template<class CharT, class Alloc> struct __rope_RopeConcatenation;template<class CharT, class Alloc> struct __rope_RopeLeaf;template<class CharT, class Alloc> struct __rope_RopeFunction;template<class CharT, class Alloc> struct __rope_RopeSubstring;template<class CharT, class Alloc> class __rope_iterator;template<class CharT, class Alloc> class __rope_const_iterator;template<class CharT, class Alloc> class __rope_charT_ref_proxy;template<class CharT, class Alloc> class __rope_charT_ptr_proxy;//// The internal data structure for representing a rope.  This is// private to the implementation.  A rope is really just a pointer// to one of these.//// A few basic functions for manipulating this data structure// are members of RopeBase.  Most of the more complex algorithms// are implemented as rope members.//// Some of the static member functions of RopeBase have identically// named functions in rope that simply invoke the RopeBase versions.//template<class charT, class Alloc>struct __rope_RopeBase {    typedef rope<charT,Alloc> my_rope;    typedef simple_alloc<charT, Alloc> DataAlloc;    typedef simple_alloc<__rope_RopeConcatenation<charT,Alloc>, Alloc> CAlloc;    typedef simple_alloc<__rope_RopeLeaf<charT,Alloc>, Alloc> LAlloc;    typedef simple_alloc<__rope_RopeFunction<charT,Alloc>, Alloc> FAlloc;    typedef simple_alloc<__rope_RopeSubstring<charT,Alloc>, Alloc> SAlloc;    public:    enum { max_rope_depth = 45 };    enum {leaf, concat, substringfn, function} tag:8;    bool is_balanced:8;    unsigned char depth;    size_t size;    __GC_CONST charT * c_string;			/* Flattened version of string, if needed.  */			/* typically 0.                             */			/* If it's not 0, then the memory is owned  */			/* by this node.                            */			/* In the case of a leaf, this may point to */			/* the same memory as the data field.	    */#   ifndef __GC#       if defined(__STL_WIN32THREADS)	    long refcount;  	// InterlockedIncrement wants a long *#	else	    size_t refcount;#	endif	// We count references from rope instances	// and references from other rope nodes.  We	// do not count const_iterator references.	// Iterator references are counted so that rope modifications	// can be detected after the fact.	// Generally function results are counted, i.e.	// a pointer returned by a function is included at the	// point at which the pointer is returned.	// The recipient should decrement the count if the	// result is not needed.	// Generally function arguments are not reflected	// in the reference count.  The callee should increment	// the count before saving the argument someplace that	// will outlive the call.#   endif#   ifndef __GC#       ifdef __STL_SGI_THREADS	    // Reference counting with multiple threads and no	    // hardware or thread package support is pretty awful.	    // Mutexes are normally too expensive.	    // We'll assume a COMPARE_AND_SWAP(destp, old, new)	    // operation, which might be cheaper.#           if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))#               define __add_and_fetch(l,v) add_then_test((unsigned long *)l,v)#           endif	    void init_refcount_lock() {}	    void incr_refcount ()	    {		__add_and_fetch(&refcount, 1);	    }	    size_t decr_refcount ()	    {		return __add_and_fetch(&refcount, (size_t)(-1));	    }#       elif defined(__STL_WIN32THREADS)	    void init_refcount_lock() {}            void incr_refcount ()            {                InterlockedIncrement(&refcount);            }            size_t decr_refcount ()            {                return InterlockedDecrement(&refcount);            }#	elif defined(__STL_PTHREADS)	    // This should be portable, but performance is expected	    // to be quite awful.  This really needs platform specific	    // code.	    pthread_mutex_t refcount_lock;	    void init_refcount_lock() {		pthread_mutex_init(&refcount_lock, 0);	    }	    void incr_refcount ()            {   		pthread_mutex_lock(&refcount_lock);                ++refcount;		pthread_mutex_unlock(&refcount_lock);            }            size_t decr_refcount ()            {   		size_t result;		pthread_mutex_lock(&refcount_lock);                result = --refcount;		pthread_mutex_unlock(&refcount_lock);                return result;            }#	else	    void init_refcount_lock() {}	    void incr_refcount ()	    {		++refcount;	    }	    size_t decr_refcount ()	    {		--refcount;		return refcount;	    }#       endif#   else	void incr_refcount () {}#   endif	static void free_string(charT *, size_t len);			// Deallocate data section of a leaf.			// This shouldn't be a member function.			// But its hard to do anything else at the			// moment, because it's templatized w.r.t.			// an allocator.			// Does nothing if __GC is defined.#   ifndef __GC	  void free_c_string();	  void free_tree();			// Deallocate t. Assumes t is not 0.	  void unref_nonnil()	  {	      if (0 == decr_refcount()) free_tree();	  }	  void ref_nonnil()	  {	      incr_refcount();	  }	  static void unref(__rope_RopeBase* t)	  {	      if (0 != t) {		  t -> unref_nonnil();	      }	  }	  static void ref(__rope_RopeBase* t)	  {	      if (0 != t) t -> incr_refcount();	  }	  static void free_if_unref(__rope_RopeBase* t) 	  {	      if (0 != t && 0 == t -> refcount) t -> free_tree();	  }#   else /* __GC */	  void unref_nonnil() {}	  void ref_nonnil() {}	  static void unref(__rope_RopeBase* t) {}	  static void ref(__rope_RopeBase* t) {}	  static void fn_finalization_proc(void * tree, void *);	  static void free_if_unref(__rope_RopeBase* t) {}#   endif    // The data fields of leaves are allocated with some    // extra space, to accomodate future growth and for basic    // character types, to hold a trailing eos character.    enum { alloc_granularity = 8 };    static size_t rounded_up_size(size_t n) {        size_t size_with_eos;	             if (__is_basic_char_type((charT *)0)) {    	    size_with_eos = n + 1;    	} else {  	    size_with_eos = n;	}#       ifdef __GC   	   return size_with_eos;#	else	   // Allow slop for in-place expansion.	   return (size_with_eos + alloc_granularity-1)			&~ (alloc_granularity-1);#	endif    }};template<class charT, class Alloc>struct __rope_RopeLeaf : public __rope_RopeBase<charT,Alloc> {  public:  // Apparently needed by VC++    __GC_CONST charT* data;     /* Not necessarily 0 terminated. */				/* The allocated size is	 */				/* rounded_up_size(size), except */				/* in the GC case, in which it	 */				/* doesn't matter.		 */};template<class charT, class Alloc>struct __rope_RopeConcatenation : public __rope_RopeBase<charT,Alloc> {  public:    __rope_RopeBase<charT,Alloc>* left;