ropeimpl.h

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

	  printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
		 r, r -> refcount, r -> depth, r -> size,
		 r -> is_balanced? "" : "not");
#       endif
	dump(left, indent + 2);
	dump(right, indent + 2);
	return;
    } else {
	char * kind;

	switch (r -> tag) {
	    case RopeBase::leaf:
		kind = "Leaf";
		break;
	    case RopeBase::function:
		kind = "Function";
		break;
	    case RopeBase::substringfn:
		kind = "Function representing substring";
		break;
	    default:
		kind = "(corrupted kind field!)";
	}
#       ifdef __GC
	  printf("%s %p (depth = %d, len = %ld) ",
		 kind, r, r -> depth, r -> size);
#       else
	  printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
		 kind, r, r -> refcount, r -> depth, r -> size);
#       endif
	if (__is_one_byte_char_type((charT *)0)) {
	    const int max_len = 40;
	    self_destruct_ptr prefix(substring(r, 0, max_len));
	    charT buffer[max_len + 1];
	    bool too_big = r -> size > prefix-> size;

	    flatten(prefix, buffer);
	    buffer[prefix -> size] = __eos((charT *)0); 
	    printf("%s%s\n", (char *)buffer, too_big? "...\n" : "\n");
	} else {
	    printf("\n");
	}
    }
}

template <class charT, class Alloc>
const unsigned long
rope<charT,Alloc>::min_len[__rope_RopeBase<charT,Alloc>::max_rope_depth + 1] = {
/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21,
/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377,
/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181,
/* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368,
/* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811,
/* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309,
/* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352,
/* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155,
/* 39 */165580141, /* 40 */267914296, /* 41 */433494437,
/* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903,
/* 45 */2971215073 };
// These are Fibonacci numbers < 2**32.

template <class charT, class Alloc>
rope<charT,Alloc>::RopeBase *
rope<charT,Alloc>::balance(RopeBase *r)
{
    RopeBase * forest[RopeBase::max_rope_depth + 1];
    RopeBase * result = 0;
    int i;
    // Inariant:
    // The concatenation of forest in descending order is equal to r.
    // forest[i].size >= min_len[i]
    // forest[i].depth = i
    // References from forest are included in refcount.

    for (i = 0; i <= RopeBase::max_rope_depth; ++i) forest[i] = 0;
    __STL_TRY {
      add_to_forest(r, forest);
      for (i = 0; i <= RopeBase::max_rope_depth; ++i) if (0 != forest[i]) {
#	ifndef __GC
	  self_destruct_ptr old(result);
#	endif
	result = concat(forest[i], result);
	forest[i] -> unref_nonnil();
#	if !defined(__GC) && defined(__STL_USE_EXCEPTIONS)
	  forest[i] = 0;
#	endif
      }
    }
    __STL_UNWIND(for(i = 0; i <= RopeBase::max_rope_depth; i++)
		 unref(forest[i]))
    if (result -> depth > RopeBase::max_rope_depth) abort();
    return(result);
}


template <class charT, class Alloc>
void
rope<charT,Alloc>::add_to_forest(RopeBase *r, RopeBase **forest)
{
    if (r -> is_balanced) {
	add_leaf_to_forest(r, forest);
	return;
    }
    __stl_assert(r -> tag == RopeBase::concat);
    {
	RopeConcatenation *c = (RopeConcatenation *)r;

	add_to_forest(c -> left, forest);
	add_to_forest(c -> right, forest);
    }
}


template <class charT, class Alloc>
void
rope<charT,Alloc>::add_leaf_to_forest(RopeBase *r, RopeBase **forest)
{
    RopeBase * insertee;   		// included in refcount
    RopeBase * too_tiny = 0;    	// included in refcount
    int i;  				// forest[0..i-1] is empty
    size_t s = r -> size;

    for (i = 0; s >= min_len[i+1]/* not this bucket */; ++i) {
	if (0 != forest[i]) {
#	    ifndef __GC
	      self_destruct_ptr old(too_tiny);
#	    endif
	    too_tiny = concat_and_set_balanced(forest[i], too_tiny);
	    forest[i] -> unref_nonnil();
	    forest[i] = 0;
	}
    }
    {
#	ifndef __GC
	  self_destruct_ptr old(too_tiny);
#	endif
	insertee = concat_and_set_balanced(too_tiny, r);
    }
    // Too_tiny dead, and no longer included in refcount.
    // Insertee is live and included.
    __stl_assert(is_almost_balanced(insertee));
    __stl_assert(insertee -> depth <= r -> depth + 1);
    for (;; ++i) {
	if (0 != forest[i]) {
#	    ifndef __GC
	      self_destruct_ptr old(insertee);
#	    endif
	    insertee = concat_and_set_balanced(forest[i], insertee);
	    forest[i] -> unref_nonnil();
	    forest[i] = 0;
	    __stl_assert(is_almost_balanced(insertee));
	}
	__stl_assert(min_len[i] <= insertee -> size);
	__stl_assert(forest[i] == 0);
	if (i == RopeBase::max_rope_depth
	    || insertee -> size < min_len[i+1]) {
	    forest[i] = insertee;
	    // refcount is OK since insertee is now dead.
	    return;
	}
    }
}

template <class charT, class Alloc>
charT
rope<charT,Alloc>::fetch(RopeBase *r, size_type i)
{
    __GC_CONST charT * cstr = r -> c_string;

    __stl_assert(i < r -> size);
    if (0 != cstr) return cstr[i]; 
    for(;;) {
      switch(r -> tag) {
	case RopeBase::concat:
	    {
		RopeConcatenation *c = (RopeConcatenation *)r;
		RopeBase *left = c -> left;
		size_t left_len = left -> size;

		if (i >= left_len) {
		    i -= left_len;
		    r = c -> right;
		} else {
		    r = left;
		}
	    }
	    break;
	case RopeBase::leaf:
	    {
		RopeLeaf * l = (RopeLeaf *)r;
		return l -> data[i];
	    }
	case RopeBase::function:
	case RopeBase::substringfn:
	    {
		RopeFunction * f = (RopeFunction *)r;
		charT result;

		(*(f -> fn))(i, 1, &result);
		return result;
	    }
      }
    }
}

# ifndef __GC
// Return a uniquely referenced character slot for the given
// position, or 0 if that's not possible.
template <class charT, class Alloc>
charT*
rope<charT,Alloc>::fetch_ptr(RopeBase *r, size_type i)
{
    RopeBase * clrstack[RopeBase::max_rope_depth];
    size_t csptr = 0;

    for(;;) {
      if (r -> refcount > 1) return 0;
      switch(r -> tag) {
	case RopeBase::concat:
	    {
		RopeConcatenation *c = (RopeConcatenation *)r;
		RopeBase *left = c -> left;
		size_t left_len = left -> size;

		if (c -> c_string != 0) clrstack[csptr++] = c;
		if (i >= left_len) {
		    i -= left_len;
		    r = c -> right;
		} else {
		    r = left;
		}
	    }
	    break;
	case RopeBase::leaf:
	    {
		RopeLeaf * l = (RopeLeaf *)r;
		if (l -> c_string != l -> data && l -> c_string != 0)
		    clrstack[csptr++] = l;
		while (csptr > 0) {
		    -- csptr;
		    RopeBase * d = clrstack[csptr];
		    d -> free_c_string();
		    d -> c_string = 0;
		}
		return l -> data + i;
	    }
	case RopeBase::function:
	case RopeBase::substringfn:
	    return 0;
      }
    }
}
# endif /* __GC */

// The following could be implemented trivially using
// lexicographical_compare_3way.
// We do a little more work to avoid dealing with rope iterators for
// flat strings.
template <class charT, class Alloc>
int
rope<charT,Alloc>::compare (const RopeBase *left, const RopeBase *right)
{
    size_t left_len;
    size_t right_len;

    if (0 == right) return 0 != left;
    if (0 == left) return -1;
    left_len = left -> size;
    right_len = right -> size;
    if (RopeBase::leaf == left -> tag) {
	RopeLeaf *l = (RopeLeaf *) left;
	if (RopeBase::leaf == right -> tag) {
	    RopeLeaf *r = (RopeLeaf *) right;
	    return lexicographical_compare_3way(
			l -> data, l -> data + left_len,
			r -> data, r -> data + right_len);
	} else {
	    const_iterator rstart(right, 0);
	    const_iterator rend(right, right_len);
	    return lexicographical_compare_3way(
			l -> data, l -> data + left_len,
			rstart, rend);
	}
    } else {
	const_iterator lstart(left, 0);
	const_iterator lend(left, left_len);
	if (RopeBase::leaf == right -> tag) {
	    RopeLeaf *r = (RopeLeaf *) right;
	    return lexicographical_compare_3way(
				   lstart, lend,
				   r -> data, r -> data + right_len);
	} else {
	    const_iterator rstart(right, 0);
	    const_iterator rend(right, right_len);
	    return lexicographical_compare_3way(
				   lstart, lend,
				   rstart, rend);
	}
    }
}

// Assignment to reference proxies.
template <class charT, class Alloc>
__rope_charT_ref_proxy<charT, Alloc>&
__rope_charT_ref_proxy<charT, Alloc>::operator= (charT c) {
    RopeBase * old = root -> tree_ptr;
#   ifndef __GC
	// First check for the case in which everything is uniquely
	// referenced.  In that case we can do this destructively.
	charT * charT_ptr = my_rope::fetch_ptr(old, pos);
	if (0 != charT_ptr) {
	    *charT_ptr = c;
	    return *this;
	}
#   endif
    self_destruct_ptr left(my_rope::substring(old, 0, pos));
    self_destruct_ptr right(my_rope::substring(old, pos+1, old -> size));
    self_destruct_ptr result_left(my_rope::destr_concat_char_iter(left, &c, 1));
#   ifndef __GC
      __stl_assert(left == result_left || 1 == result_left -> refcount);
#   endif
    RopeBase * result =
		my_rope::concat(result_left, right);
#   ifndef __GC
      __stl_assert(1 <= result -> refcount);
      RopeBase::unref(old);
#   endif
    root -> tree_ptr = result;
    return *this;
}

template <class charT, class Alloc>
inline __rope_charT_ref_proxy<charT, Alloc>::operator charT () const
{
    if (current_valid) {
	return current;
    } else {
        return my_rope::fetch(root->tree_ptr, pos);
    }
}
template <class charT, class Alloc>
__rope_charT_ptr_proxy<charT, Alloc>
__rope_charT_ref_proxy<charT, Alloc>::operator& () const {
    return __rope_charT_ptr_proxy<charT, Alloc>(*this);
}

template <class charT, class Alloc>
rope<charT, Alloc>::rope(size_t n, charT c)
{
    rope result;
    const size_t exponentiate_threshold = 32;
    size_t exponent;
    size_t rest;
    charT *rest_buffer;
    RopeBase * remainder;
    rope remainder_rope;

    if (0 == n) { tree_ptr = 0; return; }
    exponent = n / exponentiate_threshold;
    rest = n % exponentiate_threshold;
    if (0 == rest) {
	remainder = 0;
    } else {
	rest_buffer = DataAlloc::allocate(rounded_up_size(rest));
	uninitialized_fill_n(rest_buffer, rest, c);
	__cond_store_eos(rest_buffer[rest]);
	__STL_TRY {
	    remainder = RopeLeaf_from_char_ptr(rest_buffer, rest);
        }
	__STL_UNWIND(RopeBase::free_string(rest_buffer, rest))
    }
    remainder_rope.tree_ptr = remainder;
    if (exponent != 0) {
	charT * base_buffer =
		DataAlloc::allocate(rounded_up_size(exponentiate_threshold));
	RopeLeaf * base_leaf;
	rope base_rope;
	uninitialized_fill_n(base_buffer, exponentiate_threshold, c);
	__cond_store_eos(base_buffer[exponentiate_threshold]);
	__STL_TRY {
          base_leaf = RopeLeaf_from_char_ptr(base_buffer,
                                             exponentiate_threshold);
        }
	__STL_UNWIND(RopeBase::free_string(base_buffer, exponentiate_threshold))
	base_rope.tree_ptr = base_leaf;
 	if (1 == exponent) {
	  result = base_rope;
#         ifndef __GC
	    __stl_assert(1 == result -> tree_ptr -> refcount);
#         endif
	} else {
	  result = power(base_rope, exponent, concat_fn());
	}
	if (0 != remainder) {
	  result += remainder_rope;
	}
    } else {
	result = remainder_rope;
    }
    tree_ptr = result.tree_ptr;
    tree_ptr -> ref_nonnil();
}

template<class charT, class Alloc> charT rope<charT,Alloc>::empty_c_str[1];

# ifdef __STL_PTHREADS
    template<class charT, class Alloc>
    pthread_mutex_t rope<charT,Alloc>::swap_lock = PTHREAD_MUTEX_INITIALIZER;
# endif

template<class charT, class Alloc>
const charT * rope<charT,Alloc>::c_str() const {
    if (0 == tree_ptr) {
        empty_c_str[0] = __eos((charT *)0);  // Possibly redundant,
					     // but probably fast.
        return empty_c_str;
    }
    __GC_CONST charT * old_c_string = tree_ptr -> c_string;
    if (0 != old_c_string) return(old_c_string);
    size_t s = size();
    charT * result = DataAlloc::allocate(s + 1);
    flatten(tree_ptr, result);
    result[s] = __eos((charT *)0);
#   ifdef __GC
	tree_ptr -> c_string = result;
#   else
      if ((old_c_string = atomic_swap(&(tree_ptr -> c_string), result)) != 0) {
	// It must have been added in the interim.  Hence it had to have been
	// separately allocated.  Deallocate the old copy, since we just
	// replaced it.
	destroy(old_c_string, old_c_string + s + 1);
	DataAlloc::deallocate(old_c_string, s + 1);
      }
#   endif
    return(result);
}

template<class charT, class Alloc>
const charT * rope<charT,Alloc>::replace_with_c_str() {
    if (0 == tree_ptr) {
        empty_c_str[0] = __eos((charT *)0);
        return empty_c_str;
    }
    __GC_CONST charT * old_c_string = tree_ptr -> c_string;
    if (RopeBase::leaf == tree_ptr -> tag && 0 != old_c_string) {
	return(old_c_string);
    }
    size_t s = size();
    charT * result = DataAlloc::allocate(rounded_up_size(s));
    flatten(tree_ptr, result);
    result[s] = __eos((charT *)0);
    tree_ptr -> unref_nonnil();
    tree_ptr = RopeLeaf_from_char_ptr(result, s);
    return(result);
}

// Algorithm specializations.  More should be added.

#ifndef _MSC_VER
// I couldn't get this to work with VC++
template<class charT,class Alloc>
void
__rope_rotate(__rope_iterator<charT,Alloc> first,
              __rope_iterator<charT,Alloc> middle,
              __rope_iterator<charT,Alloc> last) {
    __stl_assert(first.container() == middle.container()
                 && middle.container() == last.container());
    rope<charT,Alloc>& r(first.container());
    rope<charT,Alloc> prefix = r.substr(0, first.index());
    rope<charT,Alloc> suffix = r.substr(last.index(), r.size() - last.index());
    rope<charT,Alloc> part1 = r.substr(middle.index(),
                                       last.index() - middle.index());
    rope<charT,Alloc> part2 = r.substr(first.index(),
                                       middle.index() - first.index());
    r = prefix;
    r += part1;
    r += part2;
    r += suffix;
}

inline void rotate(__rope_iterator<char,__ALLOC> first,
                   __rope_iterator<char,__ALLOC> middle,
                   __rope_iterator<char,__ALLOC> last) {
    __rope_rotate(first, middle, last);
}

# if 0
// Probably not useful for several reasons:
// - for SGIs 7.1 compiler and probably some others,
//   this forces lots of rope<wchar_t, ...> instantiations, creating a
//   code bloat and compile time problem.  (Fixed in 7.2.)
// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive
//   for unicode strings.  Unsigned short may be a better character
//   type.
inline void rotate(__rope_iterator<wchar_t,__ALLOC> first,
                   __rope_iterator<wchar_t,__ALLOC> middle,
                   __rope_iterator<wchar_t,__ALLOC> last) {
    __rope_rotate(first, middle, last);
}
# endif
#endif /* _MSC_VER */

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

__STL_END_NAMESPACE

// Local Variables:
// mode:C++
// End: