ropeimpl.h

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

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

# include <stdio.h>
# include <iostream.h>

__STL_BEGIN_NAMESPACE

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

// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
// if necessary.  Assumes path_end[leaf_index] and leaf_pos are correct.
// Results in a valid buf_ptr if the iterator can be legitimately
// dereferenced.
template <class charT, class Alloc>
void __rope_iterator_base<charT,Alloc>::setbuf
(__rope_iterator_base<charT,Alloc> &x)
{
    const RopeBase * leaf = x.path_end[x.leaf_index];
    size_t leaf_pos = x.leaf_pos;
    size_t pos = x.current_pos;

    switch(leaf -> tag) {
	case RopeBase::leaf:
	    x.buf_start = ((__rope_RopeLeaf<charT,Alloc> *)leaf) -> data;
	    x.buf_ptr = x.buf_start + (pos - leaf_pos);
	    x.buf_end = x.buf_start + leaf -> size;
	    break;
	case RopeBase::function:
	case RopeBase::substringfn:
	    {
		size_t len = iterator_buf_len;
		size_t buf_start_pos = leaf_pos;
		size_t leaf_end = leaf_pos + leaf -> size;
		char_producer<charT> *fn =
			((__rope_RopeFunction<charT,Alloc> *)leaf) -> fn;

		if (buf_start_pos + len <= pos) {
		    buf_start_pos = pos - len/4;
		    if (buf_start_pos + len > leaf_end) {
			buf_start_pos = leaf_end - len;
		    }
		}
		if (buf_start_pos + len > leaf_end) {
		    len = leaf_end - buf_start_pos;
		}
		(*fn)(buf_start_pos - leaf_pos, len, x.tmp_buf);
		x.buf_ptr = x.tmp_buf + (pos - buf_start_pos);
		x.buf_start = x.tmp_buf;
		x.buf_end = x.tmp_buf + len;
	    }
	    break;
	default:
	    __stl_assert(0);
    }
}

// Set path and buffer inside a rope iterator.  We assume that 
// pos and root are already set.
template <class charT, class Alloc>
void __rope_iterator_base<charT,Alloc>::setcache
(__rope_iterator_base<charT,Alloc> &x)
{
    const RopeBase * path[RopeBase::max_rope_depth+1];
    const RopeBase * curr_rope;
    int curr_depth = -1;  /* index into path    */
    size_t curr_start_pos = 0;
    size_t pos = x.current_pos;
    unsigned char dirns = 0;	// Bit vector indicating right turns in the path

    __stl_assert(pos <= x.root -> size);
    if (pos >= x.root -> size) {
	x.buf_ptr = 0;
	return;
    }
    curr_rope = x.root;
    if (0 != curr_rope -> c_string) {
	/* Treat the root as a leaf. */
	x.buf_start = curr_rope -> c_string;
	x.buf_end = curr_rope -> c_string + curr_rope -> size;
	x.buf_ptr = curr_rope -> c_string + pos;
	x.path_end[0] = curr_rope;
	x.leaf_index = 0;
	x.leaf_pos = 0;
	return;
    }
    for(;;) {
	++curr_depth;
	__stl_assert(curr_depth <= RopeBase::max_rope_depth);
	path[curr_depth] = curr_rope;
	switch(curr_rope -> tag) {
	  case RopeBase::leaf:
	  case RopeBase::function:
	  case RopeBase::substringfn:
	    x.leaf_pos = curr_start_pos;
	    goto done;
	  case RopeBase::concat:
	    {
		__rope_RopeConcatenation<charT,Alloc> *c =
			(__rope_RopeConcatenation<charT,Alloc> *)curr_rope;
		RopeBase * left = c -> left;
		size_t left_len = left -> size;
		
		dirns <<= 1;
		if (pos >= curr_start_pos + left_len) {
		    dirns |= 1;
		    curr_rope = c -> right;
		    curr_start_pos += left_len;
		} else {
		    curr_rope = left;
		}
	    }
	    break;
	}
    }
  done:
    // Copy last section of path into path_end.
      {
	int i = -1;
	int j = curr_depth  + 1 - path_cache_len;

	if (j < 0) j = 0;
	while (j <= curr_depth) {
	    x.path_end[++i] = path[j++];
	}
	x.leaf_index = i;
      }
      x.path_directions = dirns;
    setbuf(x);
}

// Specialized version of the above.  Assumes that
// the path cache is valid for the previous position.
template <class charT, class Alloc>
void __rope_iterator_base<charT,Alloc>::setcache_for_incr
(__rope_iterator_base<charT,Alloc> &x)
{
    int current_index = x.leaf_index;
    const RopeBase * current_node = x.path_end[current_index];
    size_t len = current_node -> size;
    size_t node_start_pos = x.leaf_pos;
    unsigned char dirns = x.path_directions;
    __rope_RopeConcatenation<charT,Alloc> * c;

    __stl_assert(x.current_pos <= x.root -> size);
    if (x.current_pos - node_start_pos < len) {
	/* More stuff in this leaf, we just didn't cache it. */
	setbuf(x);
	return;
    }
    __stl_assert(node_start_pos + len == x.current_pos);
    //  node_start_pos is starting position of last_node.
    while (--current_index >= 0) {
	if (!(dirns & 1) /* Path turned left */) break;
	current_node = x.path_end[current_index];
	c = (__rope_RopeConcatenation<charT,Alloc> *)current_node;
	// Otherwise we were in the right child.  Thus we should pop
	// the concatenation node.
	node_start_pos -= c -> left -> size;
	dirns >>= 1;
    }
    if (current_index < 0) {
	// We underflowed the cache. Punt.
	setcache(x);
	return;
    }
    current_node = x.path_end[current_index];
    c = (__rope_RopeConcatenation<charT,Alloc> *)current_node;
    // current_node is a concatenation node.  We are positioned on the first
    // character in its right child.
    // node_start_pos is starting position of current_node.
    node_start_pos += c -> left -> size;
    current_node = c -> right;
    x.path_end[++current_index] = current_node;
    dirns |= 1;
    while (RopeBase::concat == current_node -> tag) {
	++current_index;
	if (path_cache_len == current_index) {
	    int i;
	    for (i = 0; i < path_cache_len-1; i++) {
		x.path_end[i] = x.path_end[i+1];
	    }
	    --current_index;
	}
	current_node =
	    ((__rope_RopeConcatenation<charT,Alloc> *)current_node) -> left;
	x.path_end[current_index] = current_node;
	dirns <<= 1;
	// node_start_pos is unchanged.
    }
    x.leaf_index = current_index;
    x.leaf_pos = node_start_pos;
    x.path_directions = dirns;
    setbuf(x);
}

template <class charT, class Alloc>
void __rope_iterator_base<charT,Alloc>::incr(size_t n) {
    current_pos += n;
    if (0 != buf_ptr) {
        size_t chars_left = buf_end - buf_ptr;
        if (chars_left > n) {
            buf_ptr += n;
        } else if (chars_left == n) {
            buf_ptr += n;
            setcache_for_incr(*this);
        } else {
            buf_ptr = 0;
        }
    }
}

template <class charT, class Alloc>
void __rope_iterator_base<charT,Alloc>::decr(size_t n) {
    if (0 != buf_ptr) {
        size_t chars_left = buf_ptr - buf_start;
        if (chars_left >= n) {
            buf_ptr -= n;
        } else {
            buf_ptr = 0;
        }
    }
    current_pos -= n;
}

template <class charT, class Alloc>
void __rope_iterator<charT,Alloc>::check() {
    if (root_rope -> tree_ptr != root) {
        // Rope was modified.  Get things fixed up.
        RopeBase::unref(root);
        root = root_rope -> tree_ptr;
        RopeBase::ref(root);
        buf_ptr = 0;
    }
}

template <class charT, class Alloc>
inline __rope_const_iterator<charT, Alloc>::__rope_const_iterator
(const __rope_iterator<charT,Alloc> & x)
: __rope_iterator_base<charT,Alloc>(x) { }

template <class charT, class Alloc>
inline __rope_iterator<charT,Alloc>::__rope_iterator
(rope<charT,Alloc>& r, size_t pos)
        : __rope_iterator_base<charT,Alloc>(r.tree_ptr, pos), root_rope(&r) {
    RopeBase::ref(root);
}

template <class charT, class Alloc>
inline size_t rope<charT,Alloc>::char_ptr_len(const charT *s)
{
    const charT *p = s;

    while (!is0(*p)) { ++p; }
    return(p - s);
}

template <class charT, class Alloc>
rope<charT,Alloc>::RopeLeaf *
rope<charT,Alloc>::RopeLeaf_from_char_ptr(__GC_CONST charT *s, size_t size)
{
    RopeLeaf *t = LAlloc::allocate();

    t -> tag = RopeBase::leaf;
    if (__is_basic_char_type((charT *)0)) {
	// already eos terminated.
	t -> c_string = s;
    } else {
	t -> c_string = 0;
    }
    t -> is_balanced = true;
    t -> depth = 0;
    t -> size = size;
    t -> data = s;
#   ifndef __GC
	t -> refcount = 1;
	t -> init_refcount_lock();
#   endif
    return (t);
}

# ifdef __GC
template <class charT, class Alloc>
void __rope_RopeBase<charT,Alloc>::fn_finalization_proc(void * tree, void *)
{
    delete ((__rope_RopeFunction<charT,Alloc> *)tree) -> fn;
}
# endif

template <class charT, class Alloc>
rope<charT,Alloc>::RopeFunction *
rope<charT,Alloc>::RopeFunction_from_fn
(char_producer<charT> *fn, size_t size, bool delete_fn)
{
    if (0 == size) return 0;
    RopeFunction *t = FAlloc::allocate();
    t -> tag = RopeBase::function;
    t -> c_string = 0;
    t -> is_balanced = true;
    t -> depth = 0;
    t -> size = size;
    t -> fn = fn;
#   ifdef __GC
	if (delete_fn) {
	    GC_REGISTER_FINALIZER(t, RopeBase::fn_finalization_proc, 0, 0, 0);
	}
#   else
	t -> delete_when_done = delete_fn;
	t -> refcount = 1;
	t -> init_refcount_lock();
#   endif
    return (t);
}

#ifndef __GC

template <class charT, class Alloc>
inline void __rope_RopeBase<charT,Alloc>::free_c_string()
{
    charT * cstr = c_string;
    if (0 != cstr) {
	size_t sz = size + 1;
	destroy(cstr, cstr + sz);
	DataAlloc::deallocate(cstr, sz);
    }
}

template <class charT, class Alloc>
inline void __rope_RopeBase<charT,Alloc>::free_string(charT* s, size_t n)
{
    if (!__is_basic_char_type((charT *)0)) {
	destroy(s, s + n);
    }
    DataAlloc::deallocate(s, rounded_up_size(n));
}

template <class charT, class Alloc>
void __rope_RopeBase<charT,Alloc>::free_tree()
{
    switch(tag) {
	case leaf:
	    {
	        __rope_RopeLeaf<charT,Alloc> * l =
			(__rope_RopeLeaf<charT,Alloc> *)this;
		charT * d = l -> data;
		
		if (d != c_string) {
		    free_c_string();
		}
		free_string(d, size);
		LAlloc::deallocate(l);
	    }
	    break;
	case concat:
	    {
		__rope_RopeConcatenation<charT,Alloc> * c =
			(__rope_RopeConcatenation<charT,Alloc> *)this;
		__rope_RopeBase * left = c -> left;
		__rope_RopeBase * right = c -> right;
		free_c_string();
		left -> unref_nonnil();
		right -> unref_nonnil();
		CAlloc::deallocate(c);
	    }
	    break;
	case function:
	    {
		__rope_RopeFunction<charT,Alloc> * fn =
		  	(__rope_RopeFunction<charT,Alloc> *)this;
	        free_c_string();
	        if ( fn -> delete_when_done) {
		    delete fn -> fn;
	        }
	        FAlloc::deallocate(fn);
	        break;
	    }
	case substringfn:
	    {
	        __rope_RopeSubstring<charT,Alloc> * ss =
			(__rope_RopeSubstring<charT,Alloc> *)this;
		__rope_RopeBase *base = ss -> base;
		free_c_string();
		base -> unref_nonnil();
		SAlloc::deallocate(ss);
		break;
	    }
    }
}
#else

template <class charT, class Alloc>
inline void __rope_RopeBase<charT,Alloc>::free_string(charT* s, size_t n)
{}

#endif


// Concatenate a C string onto a leaf rope by copying the rope data.
// Used for short ropes.
template <class charT, class Alloc>
rope<charT,Alloc>::RopeLeaf *
rope<charT,Alloc>::leaf_concat_char_iter
		(RopeLeaf * r, const charT * iter, size_t len)
{
    size_t old_len = r -> size;
    charT * new_data = (charT *)
	DataAlloc::allocate(rounded_up_size(old_len + len));
    RopeLeaf * result;
    
    uninitialized_copy_n(r -> data, old_len, new_data);
    uninitialized_copy_n(iter, len, new_data + old_len);
    __cond_store_eos(new_data[old_len + len]);
    __STL_TRY {
	result = RopeLeaf_from_char_ptr(new_data, old_len + len);
    }
    __STL_UNWIND(RopeBase::free_string(new_data, old_len + len));
    return result;
}

#ifndef __GC
// As above, but it's OK to clobber original if refcount is 1
template <class charT, class Alloc>
rope<charT,Alloc>::RopeLeaf *
rope<charT,Alloc>::destr_leaf_concat_char_iter
		(RopeLeaf * r, const charT * iter, size_t len)
{
    __stl_assert(r -> refcount >= 1);
    if (r -> refcount > 1) return leaf_concat_char_iter(r, iter, len);
    size_t old_len = r -> size;
    if (allocated_capacity(old_len) >= old_len + len) {
	// The space has been partially initialized for the standard
	// character types.  But that doesn't matter for those types.
	uninitialized_copy_n(iter, len, r -> data + old_len);
	if (__is_basic_char_type((charT *)0)) {
	    __cond_store_eos(r -> data[old_len + len]);
	    __stl_assert(r -> c_string == r -> data);
	} else if (r -> c_string != r -> data && 0 != r -> c_string) {
	    r -> free_c_string();
	    r -> c_string = 0;
	}
	r -> size = old_len + len;
	__stl_assert(r -> refcount == 1);
	r -> refcount = 2;
	return r;
    } else {
	RopeLeaf * result = leaf_concat_char_iter(r, iter, len);
	__stl_assert(result -> refcount == 1);
	return result;
    }
}
#endif

// Assumes left and right are not 0.
// Does not increment (nor decrement on exception) child reference counts.
// Result has ref count 1.
template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase *
rope<charT,Alloc>::tree_concat (RopeBase * left, RopeBase * right)
{
    RopeConcatenation * result = CAlloc::allocate();
    unsigned char child_depth = left -> depth;
    size_t rsize;

    result -> tag = RopeBase::concat;
    result -> c_string = 0;
    result -> is_balanced = false;
    result -> size = rsize = left -> size + right -> size;
    if (right -> depth > child_depth) child_depth = right -> depth;
    unsigned char depth = (unsigned char)(child_depth + 1);
    result -> depth = depth;
    result -> left = left;
    result -> right = right;
#   ifndef __GC
	result -> refcount = 1;
	result -> init_refcount_lock();
#   endif
    if (depth > 20 && (rsize < 1000 || depth > RopeBase::max_rope_depth)) {
	RopeBase * balanced;

	__STL_TRY {
	   balanced = balance(result);
#          ifndef __GC
	     if (result != balanced) {
		__stl_assert(1 == result -> refcount
			     && 1 == balanced -> refcount);
	     }
#          endif
	   result -> unref_nonnil();
        }
	__STL_UNWIND(CAlloc::deallocate(result));
		// In case of exception, we need to deallocate
		// otherwise dangling result node.  But caller
		// still owns its children.  Thus unref is
		// inappropriate.
	return balanced;
    } else {
	return result;