stl_rope.h

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

    __rope_iterator& operator+=(difference_type n) {
	if (n >= 0) {
	    incr(n);
	} else {
	    decr(-n);
	}
	return *this;
    }
    __rope_iterator& operator--() {
	decr(1);
	return *this;
    }
    __rope_iterator& operator-=(difference_type n) {
	if (n >= 0) {
	    decr(n);
	} else {
	    incr(-n);
	}
	return *this;
    }
    __rope_iterator operator++(int) {
	size_t old_pos = current_pos;
	incr(1);
	return __rope_iterator<charT,Alloc>(root_rope, old_pos);
    }
    __rope_iterator operator--(int) {
	size_t old_pos = current_pos;
	decr(1);
	return __rope_iterator<charT,Alloc>(root_rope, old_pos);
    }
    reference operator[](ptrdiff_t n) {
	return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos + n);
    }
    friend bool operator== __STL_NULL_TMPL_ARGS
	(const __rope_iterator<charT,Alloc> & x,
	 const __rope_iterator<charT,Alloc> & y);
    friend bool operator< __STL_NULL_TMPL_ARGS
	(const __rope_iterator<charT,Alloc> & x,
	 const __rope_iterator<charT,Alloc> & y);
    friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
	(const __rope_iterator<charT,Alloc> & x,
	 const __rope_iterator<charT,Alloc> & y);
    friend __rope_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
	(const __rope_iterator<charT,Alloc> & x,
	 ptrdiff_t n);
    friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
	(const __rope_iterator<charT,Alloc> & x,
	 ptrdiff_t n);
    friend __rope_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
	(ptrdiff_t n,
	 const __rope_iterator<charT,Alloc> & x);

};

#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1375
#endif

template <class charT, class Alloc>
class rope {
    public:
	typedef charT value_type;
	typedef ptrdiff_t difference_type;
	typedef size_t size_type;
	typedef charT const_reference;
	typedef const charT* const_pointer;
	typedef __rope_iterator<charT,Alloc> iterator;
	typedef __rope_const_iterator<charT,Alloc> const_iterator;
	typedef __rope_charT_ref_proxy<charT,Alloc> reference;
	typedef __rope_charT_ptr_proxy<charT,Alloc> pointer;

	friend class __rope_iterator<charT,Alloc>;
	friend class __rope_const_iterator<charT,Alloc>;
	friend struct __rope_RopeBase<charT,Alloc>;
	friend class __rope_iterator_base<charT,Alloc>;
	friend class __rope_charT_ptr_proxy<charT,Alloc>;
	friend class __rope_charT_ref_proxy<charT,Alloc>;
	friend struct __rope_RopeSubstring<charT,Alloc>;

    protected:
	typedef __GC_CONST charT * cstrptr;
#       ifdef __STL_SGI_THREADS
	    static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
#               if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
                    return (cstrptr) test_and_set((unsigned long *)p,
			   		          (unsigned long)q);
#		else
                    return (cstrptr) __test_and_set((unsigned long *)p,
			   		            (unsigned long)q);
#		endif
            }
#       elif defined(__STL_WIN32THREADS)
	    static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
		return (cstrptr) InterlockedExchange((LPLONG)p, (LONG)q);
	    }
#	elif defined(__STL_PTHREADS)
	    // This should be portable, but performance is expected
	    // to be quite awful.  This really needs platform specific
	    // code.
	    static pthread_mutex_t swap_lock;
	    static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
		pthread_mutex_lock(&swap_lock);
		cstrptr result = *p;
		*p = q;
		pthread_mutex_unlock(&swap_lock);
		return result;
            }
#	else
	    static cstrptr atomic_swap(cstrptr *p, cstrptr q) {
                cstrptr result = *p;
                *p = q;
		return result;
	    }
#       endif

	static charT empty_c_str[1];

    	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;
	static bool is0(charT c) { return c == __eos((charT *)0); }
	enum { copy_max = 23 };
		// For strings shorter than copy_max, we copy to
		// concatenate.

	typedef __rope_RopeBase<charT,Alloc> RopeBase;
	typedef __rope_RopeConcatenation<charT,Alloc> RopeConcatenation;
	typedef __rope_RopeLeaf<charT,Alloc> RopeLeaf;
	typedef __rope_RopeFunction<charT,Alloc> RopeFunction;
	typedef __rope_RopeSubstring<charT,Alloc> RopeSubstring;

	// The only data member of a rope:
	RopeBase *tree_ptr;

	// Retrieve a character at the indicated position.
	static charT fetch(RopeBase * r, size_type pos);

#	ifndef __GC
	    // Obtain a pointer to the character at the indicated position.
	    // The pointer can be used to change the character.
	    // If such a pointer cannot be produced, as is frequently the
	    // case, 0 is returned instead.
	    // (Returns nonzero only if all nodes in the path have a refcount
	    // of 1.)
	    static charT * fetch_ptr(RopeBase * r, size_type pos);
#	endif

	static bool apply_to_pieces(
				// should be template parameter
				__rope_char_consumer<charT>& c,
				const RopeBase * r,
				size_t begin, size_t end);
				// begin and end are assumed to be in range.

#	ifndef __GC
	  static void unref(RopeBase* t)
	  {
	      RopeBase::unref(t);
	  }
	  static void ref(RopeBase* t)
	  {
	      RopeBase::ref(t);
	  }
#       else /* __GC */
	  static void unref(RopeBase* t) {}
	  static void ref(RopeBase* t) {}
#       endif


#       ifdef __GC
	    typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
#   	else
	    typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
#	endif

	// Result is counted in refcount.
	static RopeBase * substring(RopeBase * base,
				    size_t start, size_t endp1);

	static RopeBase * concat_char_iter(RopeBase * r,
					  const charT *iter, size_t slen);
		// Concatenate rope and char ptr, copying s.
		// Should really take an arbitrary iterator.
		// Result is counted in refcount.
	static RopeBase * destr_concat_char_iter(RopeBase * r,
						 const charT *iter, size_t slen)
		// As above, but one reference to r is about to be
		// destroyed.  Thus the pieces may be recycled if all
		// relevent reference counts are 1.
#	    ifdef __GC
		// We can't really do anything since refcounts are unavailable.
		{ return concat_char_iter(r, iter, slen); }
#	    else
		;
#	    endif

	static RopeBase * concat(RopeBase *left, RopeBase *right);
		// General concatenation on RopeBase.  Result
		// has refcount of 1.  Adjusts argument refcounts.

   public:
	void apply_to_pieces( size_t begin, size_t end,
			      __rope_char_consumer<charT>& c) const {
	    apply_to_pieces(c, tree_ptr, begin, end);
	}


   protected:

	static size_t rounded_up_size(size_t n) {
	    return RopeBase::rounded_up_size(n);
	}

	static size_t allocated_capacity(size_t n) {
	    if (__is_basic_char_type((charT *)0)) {
		return rounded_up_size(n) - 1;
	    } else {
		return rounded_up_size(n);
	    }
	}
		
	// s should really be an arbitrary input iterator.
	// Adds a trailing NULL for basic char types.
	static charT * alloc_copy(const charT *s, size_t size)
	{
	    charT * result = DataAlloc::allocate(rounded_up_size(size));

	    uninitialized_copy_n(s, size, result);
	    __cond_store_eos(result[size]);
	    return(result);
	}

	// Basic constructors for rope tree nodes.
	// These return tree nodes with a 0 reference count.
	static RopeLeaf * RopeLeaf_from_char_ptr(__GC_CONST charT *s,
						 size_t size);
		// Takes ownership of its argument.
		// Result has refcount 1.
		// In the nonGC, basic_char_type  case it assumes that s
		// is eos-terminated.
		// In the nonGC case, it was allocated from Alloc with
		// rounded_up_size(size).

	static RopeLeaf * RopeLeaf_from_unowned_char_ptr(const charT *s,
						         size_t size) {
	    charT * buf = alloc_copy(s, size);
            __STL_TRY {
              return RopeLeaf_from_char_ptr(buf, size);
            }
            __STL_UNWIND(RopeBase::free_string(buf, size))
	}
	    

	// Concatenation of nonempty strings.
	// Always builds a concatenation node.
	// Rebalances if the result is too deep.
	// Result has refcount 1.
	// Does not increment left and right ref counts even though
	// they are referenced.
	static RopeBase * tree_concat(RopeBase * left, RopeBase * right);

	// Result has refcount 1.
	// If delete_fn is true, then fn is deleted when the rope
	// becomes inaccessible.
	static RopeFunction * RopeFunction_from_fn
			(char_producer<charT> *fn, size_t size,
			 bool delete_fn);

	// Concatenation helper functions
	static RopeLeaf * leaf_concat_char_iter
			(RopeLeaf * r, const charT * iter, size_t slen);
		// Concatenate by copying leaf.
		// should take an arbitrary iterator
		// result has refcount 1.
#	ifndef __GC
	  static RopeLeaf * destr_leaf_concat_char_iter
			(RopeLeaf * r, const charT * iter, size_t slen);
	  // A version that potentially clobbers r if r -> refcount == 1.
#       endif

	// A helper function for exponentiating strings.
	// This uses a nonstandard refcount convention.
	// The result has refcount 0.
	struct concat_fn;
	friend struct rope<charT,Alloc>::concat_fn;

	struct concat_fn
		: public binary_function<rope<charT,Alloc>, rope<charT,Alloc>,
				         rope<charT,Alloc> > {
		rope operator() (const rope& x, const rope& y) {
		    return x + y;
		}
	};

        friend rope identity_element(concat_fn) { return rope<charT,Alloc>(); }

	static size_t char_ptr_len(const charT * s);
			// slightly generalized strlen

	rope(RopeBase *t) : tree_ptr(t) { }


	// Copy r to the CharT buffer.
	// Returns buffer + r -> size.
	// Assumes that buffer is uninitialized.
	static charT * flatten(RopeBase * r, charT * buffer);

	// Again, with explicit starting position and length.
	// Assumes that buffer is uninitialized.
	static charT * flatten(RopeBase * r,
			       size_t start, size_t len,
			       charT * buffer);

	static const unsigned long min_len[RopeBase::max_rope_depth + 1];

	static bool is_balanced(RopeBase *r)
		{ return (r -> size >= min_len[r -> depth]); }

	static bool is_almost_balanced(RopeBase *r)
		{ return (r -> depth == 0 ||
			  r -> size >= min_len[r -> depth - 1]); }

	static bool is_roughly_balanced(RopeBase *r)
		{ return (r -> depth <= 1 ||
			  r -> size >= min_len[r -> depth - 2]); }

	// Assumes the result is not empty.
	static RopeBase * concat_and_set_balanced(RopeBase *left,
						  RopeBase *right)
	{
	    RopeBase * result = concat(left, right);
	    if (is_balanced(result)) result -> is_balanced = true;
	    return result;
	}

	// The basic rebalancing operation.  Logically copies the
	// rope.  The result has refcount of 1.  The client will
	// usually decrement the reference count of r.
	// The result isd within height 2 of balanced by the above
	// definition.
	static RopeBase * balance(RopeBase * r);

	// Add all unbalanced subtrees to the forest of balanceed trees.
	// Used only by balance.
	static void add_to_forest(RopeBase *r, RopeBase **forest);
	
	// Add r to forest, assuming r is already balanced.
	static void add_leaf_to_forest(RopeBase *r, RopeBase **forest);

	// Print to stdout, exposing structure
	static void dump(RopeBase * r, int indent = 0);

	// Return -1, 0, or 1 if x < y, x == y, or x > y resp.
	static int compare(const RopeBase *x, const RopeBase *y);

   public:
	bool empty() const { return 0 == tree_ptr; }

	// Comparison member function.  This is public only for those
	// clients that need a ternary comparison.  Others
	// should use the comparison operators below.
	int compare(const rope &y) const {
	    return compare(tree_ptr, y.tree_ptr);
	}

	rope(const charT *s)
	{
	    size_t len = char_ptr_len(s);

	    if (0 == len) {
		tree_ptr = 0;
	    } else {
		tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
#		ifndef __GC
		  __stl_assert(1 == tree_ptr -> refcount);
#		endif
	    }
	}

	rope(const charT *s, size_t len)
	{
	    if (0 == len) {
		tree_ptr = 0;
	    } else {
		tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
	    }
	}

	rope(const charT *s, charT *e)
	{
	    size_t len = e - s;

	    if (0 == len) {
		tree_ptr = 0;
	    } else {
		tree_ptr = RopeLeaf_from_unowned_char_ptr(s, len);
	    }
	}

	rope(const const_iterator& s, const const_iterator& e)
	{
	    tree_ptr = substring(s.root, s.current_pos, e.current_pos);
	}

	rope(const iterator& s, const iterator& e)
	{
	    tree_ptr = substring(s.root, s.current_pos, e.current_pos);
	}

	rope(charT c)
	{
	    charT * buf = DataAlloc::allocate(rounded_up_size(1));

	    construct(buf, c);
	    __STL_TRY {
	        tree_ptr = RopeLeaf_from_char_ptr(buf, 1);
            }
            __STL_UNWIND(RopeBase::free_string(buf, 1))
	}

	rope(size_t n, charT c);