ropeimpl.h

STL完整源码,实现STL文件的读写和三维体的重建及其分析

    }
}

template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase * rope<charT,Alloc>::concat_char_iter
		(RopeBase * r, const charT *s, size_t slen)
{
    RopeBase *result;
    if (0 == slen) {
	ref(r);
	return r;
    }
    if (0 == r) return RopeLeaf_from_unowned_char_ptr(s, slen);
    if (RopeBase::leaf == r -> tag && r -> size + slen <= copy_max) {
	result = leaf_concat_char_iter((RopeLeaf *)r, s, slen);
#       ifndef __GC
	  __stl_assert(1 == result -> refcount);
#       endif
	return result;
    }
    if (RopeBase::concat == r -> tag
	&& RopeBase::leaf == ((RopeConcatenation *)r) -> right -> tag) {
	RopeLeaf *right = (RopeLeaf *)(((RopeConcatenation *)r) -> right);
	if (right -> size + slen <= copy_max) {
	  RopeBase * left = ((RopeConcatenation *)r) -> left;
	  RopeBase * nright = leaf_concat_char_iter((RopeLeaf *)right, s, slen);
	  left -> ref_nonnil();
	  __STL_TRY {
	    result = tree_concat(left, nright);
          }
	  __STL_UNWIND(unref(left); unref(nright));
#         ifndef __GC
	    __stl_assert(1 == result -> refcount);
#         endif
	  return result;
	}
    }
    RopeBase * nright = RopeLeaf_from_unowned_char_ptr(s, slen);
    __STL_TRY {
      r -> ref_nonnil();
      result = tree_concat(r, nright);
    }
    __STL_UNWIND(unref(r); unref(nright));
#   ifndef __GC
      __stl_assert(1 == result -> refcount);
#   endif
    return result;
}

#ifndef __GC
template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase * rope<charT,Alloc>
::destr_concat_char_iter
		(RopeBase * r, const charT *s, size_t slen)
{
    RopeBase *result;
    if (0 == r) return RopeLeaf_from_unowned_char_ptr(s, slen);
    size_t count = r -> refcount;
    size_t orig_size = r -> size;
    __stl_assert(count >= 1);
    if (count > 1) return concat_char_iter(r, s, slen);
    if (0 == slen) {
	r -> refcount = 2;      // One more than before
	return r;
    }
    if (orig_size + slen <= copy_max && RopeBase::leaf == r -> tag) {
	result = destr_leaf_concat_char_iter((RopeLeaf *)r, s, slen);
	return result;
    }
    if (RopeBase::concat == r -> tag) {
	RopeLeaf *right = (RopeLeaf *)(((RopeConcatenation *)r) -> right);
	if (RopeBase::leaf == right -> tag
	    && right -> size + slen <= copy_max) {
	  RopeBase * new_right = destr_leaf_concat_char_iter(right, s, slen);
	  if (right == new_right) {
	      __stl_assert(new_right -> refcount == 2);
	      new_right -> refcount = 1;
	  } else {
	      __stl_assert(new_right -> refcount >= 1);
	      right -> unref_nonnil();
	  }
	  __stl_assert(r -> refcount == 1);
	  r -> refcount = 2;    // One more than before.
	  ((RopeConcatenation *)r) -> right = new_right;
	  r -> size = orig_size + slen;
	  if (0 != r -> c_string) {
	      r -> free_c_string();
	      r -> c_string = 0;
	  }
	  return r;
	}
    }
    RopeBase *right = RopeLeaf_from_unowned_char_ptr(s, slen);
    r -> ref_nonnil();
    __STL_TRY {
      result = tree_concat(r, right);
    }
    __STL_UNWIND(unref(r); unref(right))
    __stl_assert(1 == result -> refcount);
    return result;
}
#endif /* !__GC */

template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase *
rope<charT,Alloc>::concat(RopeBase * left, RopeBase * right)
{
    if (0 == left) {
	ref(right);
	return right;
    }
    if (0 == right) {
	left -> ref_nonnil();
	return left;
    }
    if (RopeBase::leaf == right -> tag) {
	if (RopeBase::leaf == left -> tag) {
	  if (right -> size + left -> size <= copy_max) {
	    return leaf_concat_char_iter((RopeLeaf *)left,
					 ((RopeLeaf *)right) -> data,
					 right -> size);
	  }
	} else if (RopeBase::concat == left -> tag
		   && RopeBase::leaf ==
		      ((RopeConcatenation *)left) -> right -> tag) {
	  RopeLeaf * leftright =
		    (RopeLeaf *)(((RopeConcatenation *)left) -> right); 
	  if (leftright -> size + right -> size <= copy_max) {
	    RopeBase * leftleft = ((RopeConcatenation *)left) -> left;
	    RopeBase * rest = leaf_concat_char_iter(leftright,
					   ((RopeLeaf *)right) -> data,
					   right -> size);
	    leftleft -> ref_nonnil();
	    __STL_TRY {
	      return(tree_concat(leftleft, rest));
            }
	    __STL_UNWIND(unref(leftleft); unref(rest))
	  }
	}
    }
    left -> ref_nonnil();
    right -> ref_nonnil();
    __STL_TRY {
      return(tree_concat(left, right));
    }
    __STL_UNWIND(unref(left); unref(right));
}

template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase *
rope<charT,Alloc>::substring(RopeBase * base, size_t start, size_t endp1)
{
    if (0 == base) return 0;
    size_t len = base -> size;
    size_t adj_endp1;
    const size_t lazy_threshold = 128;
    
    if (endp1 >= len) {
	if (0 == start) {
	    base -> ref_nonnil();
	    return base;
	} else {
	    adj_endp1 = len;
	}
    } else {
	adj_endp1 = endp1;
    }
    switch(base -> tag) {
	case RopeBase::concat:
	    {
		RopeConcatenation *c = (RopeConcatenation *)base;
		RopeBase *left = c -> left;
		RopeBase *right = c -> right;
		size_t left_len = left -> size;
		RopeBase * result;

		if (adj_endp1 <= left_len) {
		    return substring(left, start, endp1);
		} else if (start >= left_len) {
		    return substring(right, start - left_len,
				  adj_endp1 - left_len);
		}
		self_destruct_ptr left_result(substring(left, start,
							left_len));
		self_destruct_ptr right_result(
				substring(right, 0, endp1 - left_len));
		result = concat(left_result, right_result);
#               ifndef __GC
		  __stl_assert(1 == result -> refcount);
#               endif
		return result;
	    }
	case RopeBase::leaf:
	    {
		RopeLeaf * l = (RopeLeaf *)base;
		RopeLeaf * result;
		size_t result_len;
		if (start >= adj_endp1) return 0;
		result_len = adj_endp1 - start;
		if (result_len > lazy_threshold) goto lazy;
#               ifdef __GC
		    const charT *section = l -> data + start;
		    result = RopeLeaf_from_char_ptr(section, result_len);
		    result -> c_string = 0;  // Not eos terminated.
#               else
		    // We should sometimes create substring node instead.
		    result = RopeLeaf_from_unowned_char_ptr(
					l -> data + start, result_len);
#               endif
		return result;
	    }
	case RopeBase::substringfn:
	    // Avoid introducing mutiple layers of substring nodes.
	    {
		RopeSubstring *old = (RopeSubstring *)base;
		size_t result_len;
		if (start >= adj_endp1) return 0;
		result_len = adj_endp1 - start;
		if (result_len > lazy_threshold) {
		    RopeSubstring * space = SAlloc::allocate();
		    RopeSubstring * result =
			new(space) RopeSubstring(old -> base,
						 start + old -> start,
						 adj_endp1 - start);
		    return result;
		} // else fall through:
	    }
	case RopeBase::function:
	    {
		RopeFunction * f = (RopeFunction *)base;
		charT *section;
		size_t result_len;
		if (start >= adj_endp1) return 0;
		result_len = adj_endp1 - start;

		if (result_len > lazy_threshold) goto lazy;
		section = (charT *)
			DataAlloc::allocate(rounded_up_size(result_len));
		__STL_TRY {
		  (*(f -> fn))(start, result_len, section);
                }
		__STL_UNWIND(RopeBase::free_string(section, result_len));
		__cond_store_eos(section[result_len]);
		return RopeLeaf_from_char_ptr(section, result_len);
	    }
    }
    /*NOTREACHED*/
    __stl_assert(false);
  lazy:
    {
	// Create substring node.
	RopeSubstring * space = SAlloc::allocate();
	RopeSubstring * result = new(space) RopeSubstring(base, start,
							  adj_endp1 - start);
	return result;
    }
}

template<class charT>
class __rope_flatten_char_consumer : public __rope_char_consumer<charT> {
    private:
	charT * buf_ptr;
    public:
	charT * buffer;
	__rope_flatten_char_consumer(charT * buffer) {
	    buf_ptr = buffer;
	};
	~__rope_flatten_char_consumer() {}
	bool operator() (const charT* leaf, size_t n) {
	    uninitialized_copy_n(leaf, n, buf_ptr);
	    buf_ptr += n;
	    return true;
	}
};
	    
template<class charT>
class __rope_find_char_char_consumer : public __rope_char_consumer<charT> {
    private:
	charT pattern;
    public:
	size_t count;  // Number of nonmatching characters
	__rope_find_char_char_consumer(charT p) : pattern(p), count(0) {}
	~__rope_find_char_char_consumer() {}
	bool operator() (const charT* leaf, size_t n) {
	    size_t i;
	    for (i = 0; i < n; i++) {
		if (leaf[i] == pattern) {
		    count += i; return false;
		}
	    }
	    count += n; return true;
	}
};
	    
template<class charT>
class __rope_insert_char_consumer : public __rope_char_consumer<charT> {
    private:
	typedef ostream insert_ostream;
	insert_ostream & o;
    public:
	charT * buffer;
	__rope_insert_char_consumer(insert_ostream & writer) : o(writer) {};
	~__rope_insert_char_consumer() { };
		// Caller is presumed to own the ostream
	bool operator() (const charT* leaf, size_t n);
		// Returns true to continue traversal.
};
	    
template<class charT>
bool __rope_insert_char_consumer<charT>::operator()
					(const charT * leaf, size_t n)
{
    size_t i;
    //  We assume that formatting is set up correctly for each element.
    for (i = 0; i < n; i++) o << leaf[i];
    return true;
}

inline bool __rope_insert_char_consumer<char>::operator()
					(const char * leaf, size_t n)
{
    size_t i;
    for (i = 0; i < n; i++) o.put(leaf[i]);
    return true;
}

#if !defined(_MSC_VER) && !defined(__BORLANDC__)
// I couldn't get this to work with the VC++ version of basic_ostream.
inline bool __rope_insert_char_consumer<wchar_t>::operator()
					(const wchar_t * leaf, size_t n)
{
    size_t i;
    for (i = 0; i < n; i++) o.put(leaf[i]);
    return true;
}
#endif /* !_MSC_VER  && !BORLAND */

template <class charT, class Alloc>
bool rope<charT, Alloc>::apply_to_pieces(
				__rope_char_consumer<charT>& c,
				const RopeBase * r,
				size_t begin, size_t end)
{
    if (0 == r) return true;
    switch(r -> tag) {
	case RopeBase::concat:
	    {
		RopeConcatenation *conc = (RopeConcatenation *)r;
		RopeBase *left = conc -> left;
		size_t left_len = left -> size;
		if (begin < left_len) {
		    size_t left_end = min(left_len, end);
		    if (!apply_to_pieces(c, left, begin, left_end)) {
			return false;
		    }
		}
		if (end > left_len) {
		    RopeBase *right = conc -> right;
		    size_t right_start = max(left_len, begin);
		    if (!apply_to_pieces(c, right,
					 right_start - left_len,
					 end - left_len)) {
			return false;
		    }
		}
	    }
	    return true;
	case RopeBase::leaf:
	    {
		RopeLeaf * l = (RopeLeaf *)r;
		return c(l -> data + begin, end - begin);
	    }
	case RopeBase::function:
	case RopeBase::substringfn:
	    {
		RopeFunction * f = (RopeFunction *)r;
		size_t len = end - begin;
		bool result;
		charT * buffer = DataAlloc::allocate(len);
		__STL_TRY {
		  (*(f -> fn))(begin, end, buffer);
		  result = c(buffer, len);
                  DataAlloc::deallocate(buffer, len);
                }
		__STL_UNWIND(DataAlloc::deallocate(buffer, len))
		return result;
	    }
	default:
	    __stl_assert(false);
	    /*NOTREACHED*/
	    return false;
    }
}

inline void __rope_fill(ostream& o, size_t n)
{
    char f = o.fill();
    size_t i;

    for (i = 0; i < n; i++) o.put(f);
}
    

template <class charT> inline bool __rope_is_simple(charT *) { return false; }
inline bool __rope_is_simple(char *) { return true; }
inline bool __rope_is_simple(wchar_t *) { return true; }


template<class charT, class Alloc>
ostream& operator<< (ostream& o, const rope<charT, Alloc>& r)
{
    size_t w = o.width();
    bool left = bool(o.flags() & ios::left);
    size_t pad_len;
    size_t rope_len = r.size();
    __rope_insert_char_consumer<charT> c(o);
    bool is_simple = __rope_is_simple((charT *)0);
    
    if (rope_len < w) {
	pad_len = w - rope_len;
    } else {
	pad_len = 0;
    }
    if (!is_simple) o.width(w/rope_len);
    __STL_TRY {
      if (is_simple && !left && pad_len > 0) {
	__rope_fill(o, pad_len);
      }
      r.apply_to_pieces(0, r.size(), c);
      if (is_simple && left && pad_len > 0) {
	__rope_fill(o, pad_len);
      }
      if (!is_simple)
        o.width(w);
    }
    __STL_UNWIND(if (!is_simple) o.width(w))
    return o;
}

template <class charT, class Alloc>
charT *
rope<charT,Alloc>::flatten(RopeBase * r,
				 size_t start, size_t len,
				 charT * buffer)
{
    __rope_flatten_char_consumer<charT> c(buffer);
    apply_to_pieces(c, r, start, start + len);
    return(buffer + len);
}

template <class charT, class Alloc>
size_t
rope<charT,Alloc>::find(charT pattern, size_t start) const
{
    __rope_find_char_char_consumer<charT> c(pattern);
    apply_to_pieces(c, tree_ptr, start, size());
    return start + c.count;
}

template <class charT, class Alloc>
charT *
rope<charT,Alloc>::flatten(RopeBase * r, charT * buffer)
{
    if (0 == r) return buffer;
    switch(r -> tag) {
	case RopeBase::concat:
	    {
		RopeConcatenation *c = (RopeConcatenation *)r;
		RopeBase *left = c -> left;
		RopeBase *right = c -> right;
		charT * rest = flatten(left, buffer);
		return flatten(right, rest);
	    }
	case RopeBase::leaf:
	    {
		RopeLeaf * l = (RopeLeaf *)r;
		return copy_n(l -> data, l -> size, buffer).second;
	    }
	case RopeBase::function:
	case RopeBase::substringfn:
	    // We dont yet do anything with substring nodes.
	    // This needs to be fixed before ropefiles will work well.
	    {
		RopeFunction * f = (RopeFunction *)r;
		(*(f -> fn))(0, f -> size, buffer);
		return buffer + f -> size;
	    }
	default:
	    __stl_assert(false);
	    /*NOTREACHED*/
	    return 0;
    }
}


// This needs work for charT != char
template <class charT, class Alloc>
void
rope<charT,Alloc>::dump(RopeBase * r, int indent)
{
    for (int i = 0; i < indent; i++) putchar(' ');
    if (0 == r) {
	printf("NULL\n"); return;
    }
    if (RopeBase::concat == r -> tag) {
	RopeConcatenation *c = (RopeConcatenation *)r;
	RopeBase *left = c -> left;
	RopeBase *right = c -> right;

#       ifdef __GC
	  printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
		 r, r -> depth, r -> size, r -> is_balanced? "" : "not");
#       else