ropeimpl.h

linux下编程用 编译软件

      bool
      operator()(const _CharT* __leaf, size_t __n)
      {
	uninitialized_copy_n(__leaf, __n, _M_buf_ptr);
	_M_buf_ptr += __n;
	return true;
      }
    };

  template<class _CharT>
    class _Rope_find_char_char_consumer
    : public _Rope_char_consumer<_CharT>
    {
    private:
      _CharT _M_pattern;
    public:
      size_t _M_count;  // Number of nonmatching characters
      
      _Rope_find_char_char_consumer(_CharT __p)
      : _M_pattern(__p), _M_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] == _M_pattern)
	      {
		_M_count += __i;
		return false;
	      }
	  }
	_M_count += __n; return true;
      }
    };

  template<class _CharT, class _Traits>
  // Here _CharT is both the stream and rope character type.
    class _Rope_insert_char_consumer
    : public _Rope_char_consumer<_CharT>
    {
    private:
      typedef basic_ostream<_CharT,_Traits> _Insert_ostream;
      _Insert_ostream& _M_o;
    public:
      _Rope_insert_char_consumer(_Insert_ostream& __writer)
	: _M_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, class _Traits>
    bool
    _Rope_insert_char_consumer<_CharT, _Traits>::
    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++)
	_M_o.put(__leaf[__i]);
      return true;
    }

  template <class _CharT, class _Alloc>
    bool
    rope<_CharT, _Alloc>::
    _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c,
		       const _RopeRep* __r, size_t __begin, size_t __end)
    {
      if (0 == __r)
	return true;
      switch(__r->_M_tag)
	{
	case _Rope_constants::_S_concat:
	  {
	    _RopeConcatenation* __conc = (_RopeConcatenation*)__r;
	    _RopeRep* __left =  __conc->_M_left;
	    size_t __left_len = __left->_M_size;
	    if (__begin < __left_len)
	      {
		size_t __left_end = std::min(__left_len, __end);
		if (!_S_apply_to_pieces(__c, __left, __begin, __left_end))
		  return false;
	      }
	    if (__end > __left_len)
	      {
		_RopeRep* __right =  __conc->_M_right;
		size_t __right_start = std::max(__left_len, __begin);
		if (!_S_apply_to_pieces(__c, __right,
					__right_start - __left_len,
					__end - __left_len))
		  return false;
	      }
	  }
	  return true;
	case _Rope_constants::_S_leaf:
	  {
	    _RopeLeaf* __l = (_RopeLeaf*)__r;
	    return __c(__l->_M_data + __begin, __end - __begin);
	  }
	case _Rope_constants::_S_function:
	case _Rope_constants::_S_substringfn:
	    {
	      _RopeFunction* __f = (_RopeFunction*)__r;
	      size_t __len = __end - __begin;
	      bool __result;
	      _CharT* __buffer =
		(_CharT*)_Alloc().allocate(__len * sizeof(_CharT));
	      try
		{
		  (*(__f->_M_fn))(__begin, __len, __buffer);
		  __result = __c(__buffer, __len);
                  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
                }
	      catch(...)
		{
		  _Alloc().deallocate(__buffer, __len * sizeof(_CharT));
		  __throw_exception_again;
		}
	      return __result;
	    }
	default:
	  return false;
	}
    }

  template<class _CharT, class _Traits>
    inline void
    _Rope_fill(basic_ostream<_CharT, _Traits>& __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 _Traits, class _Alloc>
    basic_ostream<_CharT, _Traits>&
    operator<<(basic_ostream<_CharT, _Traits>& __o,
	       const rope<_CharT, _Alloc>& __r)
    {
      size_t __w = __o.width();
      bool __left = bool(__o.flags() & std::ios::left);
      size_t __pad_len;
      size_t __rope_len = __r.size();
      _Rope_insert_char_consumer<_CharT, _Traits> __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);
      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);
	}
      catch(...)
	{
	  if (!__is_simple)
	    __o.width(__w);
	  __throw_exception_again;
	}
      return __o;
    }

  template <class _CharT, class _Alloc>
    _CharT*
    rope<_CharT, _Alloc>::
    _S_flatten(_RopeRep* __r, size_t __start, size_t __len,
	       _CharT* __buffer)
    {
      _Rope_flatten_char_consumer<_CharT> __c(__buffer);
      _S_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);
      _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size());
      size_type __result_pos = __start + __c._M_count;
#ifndef __STL_OLD_ROPE_SEMANTICS
      if (__result_pos == size())
	__result_pos = npos;
#endif
      return __result_pos;
    }

  template <class _CharT, class _Alloc>
    _CharT*
    rope<_CharT, _Alloc>::
    _S_flatten(_RopeRep* __r, _CharT* __buffer)
    {
      if (0 == __r)
	return __buffer;
      switch(__r->_M_tag)
	{
	case _Rope_constants::_S_concat:
	  {
	    _RopeConcatenation* __c = (_RopeConcatenation*)__r;
	    _RopeRep* __left = __c->_M_left;
	    _RopeRep* __right = __c->_M_right;
	    _CharT* __rest = _S_flatten(__left, __buffer);
	    return _S_flatten(__right, __rest);
	  }
	case _Rope_constants::_S_leaf:
	  {
	    _RopeLeaf* __l = (_RopeLeaf*)__r;
	    return copy_n(__l->_M_data, __l->_M_size, __buffer).second;
	  }
	case _Rope_constants::_S_function:
	case _Rope_constants::_S_substringfn:
	  // We don't yet do anything with substring nodes.
	  // This needs to be fixed before ropefiles will work well.
	  {
	    _RopeFunction* __f = (_RopeFunction*)__r;
	    (*(__f->_M_fn))(0, __f->_M_size, __buffer);
	    return __buffer + __f->_M_size;
	  }
	default:
	  return 0;
	}
    }

  // This needs work for _CharT != char
  template <class _CharT, class _Alloc>
    void
    rope<_CharT, _Alloc>::
    _S_dump(_RopeRep* __r, int __indent)
    {
      for (int __i = 0; __i < __indent; __i++)
	putchar(' ');
      if (0 == __r)
	{
	  printf("NULL\n");
	  return;
	}
      if (_Rope_constants::_S_concat == __r->_M_tag)
	{
	  _RopeConcatenation* __c = (_RopeConcatenation*)__r;
	  _RopeRep* __left = __c->_M_left;
	  _RopeRep* __right = __c->_M_right;
	  
#ifdef __GC
	  printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n",
		 __r, __r->_M_depth, __r->_M_size,
		 __r->_M_is_balanced? "" : "not");
#else
	  printf("Concatenation %p (rc = %ld, depth = %d, "
		 "len = %ld, %s balanced)\n",
		 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size,
		 __r->_M_is_balanced? "" : "not");
#endif
	  _S_dump(__left, __indent + 2);
	  _S_dump(__right, __indent + 2);
	  return;
	}
      else
	{
	  char* __kind;
	  
	  switch (__r->_M_tag)
	    {
	    case _Rope_constants::_S_leaf:
	      __kind = "Leaf";
	      break;
	    case _Rope_constants::_S_function:
	      __kind = "Function";
	      break;
	    case _Rope_constants::_S_substringfn:
	      __kind = "Function representing substring";
	      break;
	    default:
	      __kind = "(corrupted kind field!)";
	    }
#ifdef __GC
	  printf("%s %p (depth = %d, len = %ld) ",
		 __kind, __r, __r->_M_depth, __r->_M_size);
#else
	  printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
		 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size);
#endif
	  if (_S_is_one_byte_char_type((_CharT*)0))
	    {
	      const int __max_len = 40;
	      _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len));
	      _CharT __buffer[__max_len + 1];
	      bool __too_big = __r->_M_size > __prefix->_M_size;
	      
	      _S_flatten(__prefix, __buffer);
	      __buffer[__prefix->_M_size] = _S_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>::
    _S_min_len[int(_Rope_constants::_S_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 */2971215073u };
  // These are Fibonacci numbers < 2**32.

  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeRep*
    rope<_CharT, _Alloc>::
    _S_balance(_RopeRep* __r)
    {
      _RopeRep* __forest[int(_Rope_constants::_S_max_rope_depth) + 1];
      _RopeRep* __result = 0;
      int __i;
      // Invariant:
      // The concatenation of forest in descending order is equal to __r.
      // __forest[__i]._M_size >= _S_min_len[__i]
      // __forest[__i]._M_depth = __i
      // References from forest are included in refcount.
      
      for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i)
	__forest[__i] = 0;
      try
	{
	  _S_add_to_forest(__r, __forest);
	  for (__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); ++__i)
	    if (0 != __forest[__i])
	      {
#ifndef __GC
		_Self_destruct_ptr __old(__result);
#endif
		__result = _S_concat(__forest[__i], __result);
		__forest[__i]->_M_unref_nonnil();
#if !defined(__GC) && defined(__EXCEPTIONS)
		__forest[__i] = 0;
#endif
	      }
	}
      catch(...)
	{
	  for(__i = 0; __i <= int(_Rope_constants::_S_max_rope_depth); __i++)
	    _S_unref(__forest[__i]);
	  __throw_exception_again;
	}
      
      if (__result->_M_depth > int(_Rope_constants::_S_max_rope_depth))
	__throw_length_error(__N("rope::_S_balance"));
      return(__result);
    }

  template <class _CharT, class _Alloc>
    void
    rope<_CharT, _Alloc>::
    _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest)
    {
      if (__r->_M_is_balanced)
	{
	  _S_add_leaf_to_forest(__r, __forest);
	  return;
	}

      {
	_RopeConcatenation* __c = (_RopeConcatenation*)__r;
	
	_S_add_to_forest(__c->_M_left, __forest);
	_S_add_to_forest(__c->_M_right, __forest);
      }
    }


  template <class _CharT, class _Alloc>
    void
    rope<_CharT, _Alloc>::
    _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest)
    {
      _RopeRep* __insertee;		// included in refcount
      _RopeRep* __too_tiny = 0;		// included in refcount
      int __i;				// forest[0..__i-1] is empty
      size_t __s = __r->_M_size;
      
      for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i)
	{
	  if (0 != __forest[__i])
	    {
#ifndef __GC