stl_rope.h

著名的SGI的STL lib源码.(C++范型类编成,没有合适的分类,但是放到数据结构类别中也绝对适合)

/*
 * 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;