stl_rope.h

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

    __rope_RopeBase<charT,Alloc>* right;
};

template<class charT, class Alloc>
struct __rope_RopeFunction : public __rope_RopeBase<charT,Alloc> {
  public:
    char_producer<charT>* fn;
#   ifndef __GC
      bool delete_when_done;	// Char_producer is owned by the
				// rope and should be explicitly
				// deleted when the rope becomes
				// inaccessible.
#   else
      // In the GC case, we either register the rope for
      // finalization, or not.  Thus the field is unnecessary;
      // the information is stored in the collector data structures.
#   endif
};
// Substring results are usually represented using just
// concatenation nodes.  But in the case of very long flat ropes
// or ropes with a functional representation that isn't practical.
// In that case, we represent the result as a special case of
// RopeFunction, whose char_producer points back to the rope itself.
// In all cases except repeated substring operations and
// deallocation, we treat the result as a RopeFunction.
template<class charT, class Alloc>
struct __rope_RopeSubstring: public __rope_RopeFunction<charT,Alloc>,
			     public char_producer<charT> {
  public:
    __rope_RopeBase<charT,Alloc> * base;	// not 0
    size_t start;
    virtual ~__rope_RopeSubstring() {}
    virtual void operator()(size_t start_pos, size_t req_len,
			    charT *buffer) {
	switch(base -> tag) {
	    case function:
	    case substringfn:
	      {
		char_producer<charT> *fn =
			((__rope_RopeFunction<charT,Alloc> *)base) -> fn;
		__stl_assert(start_pos + req_len <= size);
		__stl_assert(start + size <= base -> size);
		(*fn)(start_pos + start, req_len, buffer);
	      }
	      break;
	    case leaf:
	      {
		__GC_CONST charT * s =
			((__rope_RopeLeaf<charT,Alloc> *)base) -> data;
		uninitialized_copy_n(s + start_pos + start, req_len,
				     buffer);
	      }
	      break;
	    default:
	      __stl_assert(false);
	}
    }
    __rope_RopeSubstring(__rope_RopeBase<charT,Alloc> * b, size_t s, size_t l) :
	base(b), start(s) {
#       ifndef __GC
	    refcount = 1;
	    init_refcount_lock();
	    base -> ref_nonnil();
#       endif
	size = l;
	tag = substringfn;
	depth = 0;
	c_string = 0;
	fn = this;
    }
};


// Self-destructing pointers to RopeBase.
// These are not conventional smart pointers.  Their
// only purpose in life is to ensure that unref is called
// on the pointer either at normal exit or if an exception
// is raised.  It is the caller's responsibility to
// adjust reference counts when these pointers are initialized
// or assigned to.  (This convention significantly reduces
// the number of potentially expensive reference count
// updates.)
#ifndef __GC
  template<class charT, class Alloc>
  struct __rope_self_destruct_ptr {
    __rope_RopeBase<charT,Alloc> * ptr;
    ~__rope_self_destruct_ptr() { __rope_RopeBase<charT,Alloc>::unref(ptr); }
#   ifdef __STL_USE_EXCEPTIONS
	__rope_self_destruct_ptr() : ptr(0) {};
#   else
	__rope_self_destruct_ptr() {};
#   endif
    __rope_self_destruct_ptr(__rope_RopeBase<charT,Alloc> * p) : ptr(p) {}
    __rope_RopeBase<charT,Alloc> & operator*() { return *ptr; }
    __rope_RopeBase<charT,Alloc> * operator->() { return ptr; }
    operator __rope_RopeBase<charT,Alloc> *() { return ptr; }
    __rope_self_destruct_ptr & operator= (__rope_RopeBase<charT,Alloc> * x)
	{ ptr = x; return *this; }
  };
#endif

// Dereferencing a nonconst iterator has to return something
// that behaves almost like a reference.  It's not possible to
// return an actual reference since assignment requires extra
// work.  And we would get into the same problems as with the
// CD2 version of basic_string.
template<class charT, class Alloc>
class __rope_charT_ref_proxy {
    friend class rope<charT,Alloc>;
    friend class __rope_iterator<charT,Alloc>;
    friend class __rope_charT_ptr_proxy<charT,Alloc>;
#   ifdef __GC
	typedef __rope_RopeBase<charT,Alloc> * self_destruct_ptr;
#   else
    	typedef __rope_self_destruct_ptr<charT,Alloc> self_destruct_ptr;
#   endif
    typedef __rope_RopeBase<charT,Alloc> RopeBase;
    typedef rope<charT,Alloc> my_rope;
    size_t pos;
    charT current;
    bool current_valid;
    my_rope * root;     // The whole rope.
  public:
    __rope_charT_ref_proxy(my_rope * r, size_t p) :
	pos(p), root(r), current_valid(false) {}
    __rope_charT_ref_proxy(my_rope * r, size_t p,
		    charT c) :
	pos(p), root(r), current(c), current_valid(true) {}
    operator charT () const;
    __rope_charT_ref_proxy& operator= (charT c);
    __rope_charT_ptr_proxy<charT,Alloc> operator& () const;
    __rope_charT_ref_proxy& operator= (const __rope_charT_ref_proxy& c) {
	return operator=((charT)c); 
    }
};

template<class charT, class Alloc>
class __rope_charT_ptr_proxy {
    friend class __rope_charT_ref_proxy<charT,Alloc>;
    size_t pos;
    charT current;
    bool current_valid;
    rope<charT,Alloc> * root;     // The whole rope.
  public:
    __rope_charT_ptr_proxy(const __rope_charT_ref_proxy<charT,Alloc> & x) :
	pos(x.pos), root(x.root), current_valid(x.current_valid),
	current(x.current) {}
    __rope_charT_ptr_proxy(const __rope_charT_ptr_proxy & x) :
	pos(x.pos), root(x.root), current_valid(x.current_valid),
	current(x.current) {}
    __rope_charT_ptr_proxy() {}
    __rope_charT_ptr_proxy(charT * x) : root(0), pos(0) {
	__stl_assert(0 == x);
    }
    __rope_charT_ptr_proxy& operator= (const __rope_charT_ptr_proxy& x) {
	pos = x.pos;
	current = x.current;
	current_valid = x.current_valid;
	root = x.root;
	return *this;
    }
    friend bool operator== __STL_NULL_TMPL_ARGS
                (const __rope_charT_ptr_proxy<charT,Alloc> & x,
                 const __rope_charT_ptr_proxy<charT,Alloc> & y);
    __rope_charT_ref_proxy<charT,Alloc> operator *() const {
	if (current_valid) {
	    return __rope_charT_ref_proxy<charT,Alloc>(root, pos, current);
	} else {
	    return __rope_charT_ref_proxy<charT,Alloc>(root, pos);
	}
    }
};

// Rope iterators:
// Unlike in the C version, we cache only part of the stack
// for rope iterators, since they must be efficiently copyable.
// When we run out of cache, we have to reconstruct the iterator
// value.
// Pointers from iterators are not included in reference counts.
// Iterators are assumed to be thread private.  Ropes can
// be shared.

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

template<class charT, class Alloc>
class __rope_iterator_base:
  public random_access_iterator<charT, ptrdiff_t> {
  friend class rope<charT, Alloc>;
  public:
    typedef __rope_RopeBase<charT,Alloc> RopeBase;
	// Borland doesnt want this to be protected.
  protected:
    enum { path_cache_len = 4 }; // Must be <= 9.
    enum { iterator_buf_len = 15 };
    size_t current_pos;
    RopeBase * root;     // The whole rope.
    size_t leaf_pos;    // Starting position for current leaf
    __GC_CONST charT * buf_start;
			// Buffer possibly
			// containing current char.
    __GC_CONST charT * buf_ptr;
			// Pointer to current char in buffer.
			// != 0 ==> buffer valid.
    __GC_CONST charT * buf_end;
			// One past last valid char in buffer.
    // What follows is the path cache.  We go out of our
    // way to make this compact.
    // Path_end contains the bottom section of the path from
    // the root to the current leaf.
    const RopeBase * path_end[path_cache_len];
    int leaf_index;     // Last valid pos in path_end;
    			// path_end[0] ... path_end[leaf_index-1]
			// point to concatenation nodes.
    unsigned char path_directions;
			  // (path_directions >> i) & 1 is 1
			  // iff we got from path_end[leaf_index - i - 1]
			  // to path_end[leaf_index - i] by going to the
			  // right. Assumes path_cache_len <= 9.
    charT tmp_buf[iterator_buf_len];
			// Short buffer for surrounding chars.
			// This is useful primarily for 
			// RopeFunctions.  We put the buffer
			// here to avoid locking in the
			// multithreaded case.
    // The cached path is generally assumed to be valid
    // only if the buffer is valid.
    static void setbuf(__rope_iterator_base &x);
					// Set buffer contents given
					// path cache.
    static void setcache(__rope_iterator_base &x);
					// Set buffer contents and
					// path cache.
    static void setcache_for_incr(__rope_iterator_base &x);
					// As above, but assumes path
					// cache is valid for previous posn.
    __rope_iterator_base() {}
    __rope_iterator_base(RopeBase * root, size_t pos):
		   root(root), current_pos(pos), buf_ptr(0) {}
    __rope_iterator_base(const __rope_iterator_base& x) {
	if (0 != x.buf_ptr) {
	    *this = x;
	} else {
	    current_pos = x.current_pos;
	    root = x.root;
	    buf_ptr = 0;
	}
    }
    void incr(size_t n);
    void decr(size_t n);
  public:
    size_t index() const { return current_pos; }
};

template<class charT, class Alloc> class __rope_iterator;

template<class charT, class Alloc>
class __rope_const_iterator : public __rope_iterator_base<charT,Alloc> {
    friend class rope<charT,Alloc>;
  protected:
    __rope_const_iterator(const RopeBase * root, size_t pos):
		   __rope_iterator_base<charT,Alloc>(
		     const_cast<RopeBase *>(root), pos)
		   // Only nonconst iterators modify root ref count
    {}
  public:
    typedef charT reference;    // Really a value.  Returning a reference
				// Would be a mess, since it would have
				// to be included in refcount.
    typedef const charT* pointer;

  public:
    __rope_const_iterator() {};
    __rope_const_iterator(const __rope_const_iterator & x) :
				__rope_iterator_base<charT,Alloc>(x) { }
    __rope_const_iterator(const __rope_iterator<charT,Alloc> & x);
    __rope_const_iterator(const rope<charT,Alloc> &r, size_t pos) :
	__rope_iterator_base<charT,Alloc>(r.tree_ptr, pos) {}
    __rope_const_iterator& operator= (const __rope_const_iterator & x) {
	if (0 != x.buf_ptr) {
	    *this = x;
	} else {
	    current_pos = x.current_pos;
	    root = x.root;
	    buf_ptr = 0;
	}
	return(*this);
    }
    reference operator*() {
	if (0 == buf_ptr) setcache(*this);
	return *buf_ptr;
    }
    __rope_const_iterator& operator++() {
	__GC_CONST charT * next;
	if (0 != buf_ptr && (next = buf_ptr + 1) < buf_end) {
	    buf_ptr = next;
	    ++current_pos;
	} else {
	    incr(1);
	}
	return *this;
    }
    __rope_const_iterator& operator+=(ptrdiff_t n) {
	if (n >= 0) {
	    incr(n);
	} else {
	    decr(-n);
	}
	return *this;
    }
    __rope_const_iterator& operator--() {
	decr(1);
	return *this;
    }
    __rope_const_iterator& operator-=(ptrdiff_t n) {
	if (n >= 0) {
	    decr(n);
	} else {
	    incr(-n);
	}
	return *this;
    }
    __rope_const_iterator operator++(int) {
	size_t old_pos = current_pos;
	incr(1);
	return __rope_const_iterator<charT,Alloc>(root, old_pos);
	// This makes a subsequent dereference expensive.
	// Perhaps we should instead copy the iterator
	// if it has a valid cache?
    }
    __rope_const_iterator operator--(int) {
	size_t old_pos = current_pos;
	decr(1);
	return __rope_const_iterator<charT,Alloc>(root, old_pos);
    }
    friend __rope_const_iterator<charT,Alloc> operator- __STL_NULL_TMPL_ARGS
	(const __rope_const_iterator<charT,Alloc> & x,
	 ptrdiff_t n);
    friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
	(const __rope_const_iterator<charT,Alloc> & x,
	 ptrdiff_t n);
    friend __rope_const_iterator<charT,Alloc> operator+ __STL_NULL_TMPL_ARGS
	(ptrdiff_t n,
	 const __rope_const_iterator<charT,Alloc> & x);
    reference operator[](size_t n) {
	return rope<charT,Alloc>::fetch(root, current_pos + n);
    }
    friend bool operator== __STL_NULL_TMPL_ARGS
	(const __rope_const_iterator<charT,Alloc> & x,
	 const __rope_const_iterator<charT,Alloc> & y);
    friend bool operator< __STL_NULL_TMPL_ARGS
	(const __rope_const_iterator<charT,Alloc> & x,
	 const __rope_const_iterator<charT,Alloc> & y);
    friend ptrdiff_t operator- __STL_NULL_TMPL_ARGS
	(const __rope_const_iterator<charT,Alloc> & x,
	 const __rope_const_iterator<charT,Alloc> & y);
};

template<class charT, class Alloc>
class __rope_iterator : public __rope_iterator_base<charT,Alloc> {
    friend class rope<charT,Alloc>;
  protected:
    rope<charT,Alloc> * root_rope;
	// root is treated as a cached version of this,
	// and is used to detect changes to the underlying
	// rope.
	// Root is included in the reference count.
	// This is necessary so that we can detect changes reliably.
	// Unfortunately, it requires careful bookkeeping for the
	// nonGC case.
    __rope_iterator(rope<charT,Alloc> * r, size_t pos):
	     __rope_iterator_base<charT,Alloc>(r -> tree_ptr, pos),
	     root_rope(r) {
		RopeBase::ref(root);
	     }
    void check();
  public:
    typedef __rope_charT_ref_proxy<charT,Alloc>  reference;
    typedef __rope_charT_ref_proxy<charT,Alloc>* pointer;

  public:
    rope<charT,Alloc>& container() { return *root_rope; }
    __rope_iterator() {
	root = 0;  // Needed for reference counting.
    };
    __rope_iterator(const __rope_iterator & x) :
	__rope_iterator_base<charT,Alloc>(x) {
	root_rope = x.root_rope;
	RopeBase::ref(root);
    }
    __rope_iterator(rope<charT,Alloc>& r, size_t pos);
    ~__rope_iterator() {
	RopeBase::unref(root);
    }
    __rope_iterator& operator= (const __rope_iterator & x) {
	RopeBase *old = root;

	RopeBase::ref(x.root);
	if (0 != x.buf_ptr) {
	    *this = x;
	} else {
	    current_pos = x.current_pos;
	    root = x.root;
	    root_rope = x.root_rope;
	    buf_ptr = 0;
	}
	RopeBase::unref(old);
	return(*this);
    }
    reference operator*() {
	check();
	if (0 == buf_ptr) {
	    return __rope_charT_ref_proxy<charT,Alloc>(root_rope, current_pos);
	} else {
	    return __rope_charT_ref_proxy<charT,Alloc>(root_rope,
						       current_pos, *buf_ptr);
	}
    }
    __rope_iterator& operator++() {
	incr(1);
	return *this;
    }