ropeimpl.h

linux下编程用 编译软件

// SGI's rope class implementation -*- C++ -*-

// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

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

/** @file ropeimpl.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#include <cstdio>
#include <ostream>
#include <bits/functexcept.h>

#include <ext/algorithm> // For copy_n and lexicographical_compare_3way
#include <ext/memory> // For uninitialized_copy_n
#include <ext/numeric> // For power

namespace __gnu_cxx
{
  using std::size_t;
  using std::printf;
  using std::basic_ostream;
  using std::__throw_length_error;
  using std::_Destroy;
  using std::uninitialized_fill_n;

  // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
  // if necessary.  Assumes _M_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>::
    _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x)
    {
      const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
      size_t __leaf_pos = __x._M_leaf_pos;
      size_t __pos = __x._M_current_pos;

      switch(__leaf->_M_tag)
	{
	case _Rope_constants::_S_leaf:
	  __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data;
	  __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
	  __x._M_buf_end = __x._M_buf_start + __leaf->_M_size;
	  break;
	case _Rope_constants::_S_function:
	case _Rope_constants::_S_substringfn:
	  {
	    size_t __len = _S_iterator_buf_len;
	    size_t __buf_start_pos = __leaf_pos;
	    size_t __leaf_end = __leaf_pos + __leaf->_M_size;
	    char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT,
					    _Alloc>*)__leaf)->_M_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._M_tmp_buf);
	    __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
	    __x._M_buf_start = __x._M_tmp_buf;
	    __x._M_buf_end = __x._M_tmp_buf + __len;
	  }
	  break;
	default:
	  break;
	}
    }

  // 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>::
    _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x)
    {
      const _RopeRep* __path[int(_Rope_constants::_S_max_rope_depth) + 1];
      const _RopeRep* __curr_rope;
      int __curr_depth = -1;  /* index into path    */
      size_t __curr_start_pos = 0;
      size_t __pos = __x._M_current_pos;
      unsigned char __dirns = 0; // Bit vector marking right turns in the path

      if (__pos >= __x._M_root->_M_size)
	{
	  __x._M_buf_ptr = 0;
	  return;
	}
      __curr_rope = __x._M_root;
      if (0 != __curr_rope->_M_c_string)
	{
	  /* Treat the root as a leaf. */
	  __x._M_buf_start = __curr_rope->_M_c_string;
	  __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size;
	  __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
	  __x._M_path_end[0] = __curr_rope;
	  __x._M_leaf_index = 0;
	  __x._M_leaf_pos = 0;
	  return;
	}
      for(;;)
	{
	  ++__curr_depth;
	  __path[__curr_depth] = __curr_rope;
	  switch(__curr_rope->_M_tag)
	    {
	    case _Rope_constants::_S_leaf:
	    case _Rope_constants::_S_function:
	    case _Rope_constants::_S_substringfn:
	      __x._M_leaf_pos = __curr_start_pos;
	      goto done;
	    case _Rope_constants::_S_concat:
	      {
		_Rope_RopeConcatenation<_CharT, _Alloc>* __c =
		  (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;

		__dirns <<= 1;
		if (__pos >= __curr_start_pos + __left_len)
		  {
		    __dirns |= 1;
		    __curr_rope = __c->_M_right;
		    __curr_start_pos += __left_len;
		  }
		else
		  __curr_rope = __left;
	      }
	      break;
	    }
	}
    done:
      // Copy last section of path into _M_path_end.
      {
	int __i = -1;
	int __j = __curr_depth + 1 - int(_S_path_cache_len);

	if (__j < 0) __j = 0;
	while (__j <= __curr_depth)
	  __x._M_path_end[++__i] = __path[__j++];
	__x._M_leaf_index = __i;
      }
      __x._M_path_directions = __dirns;
      _S_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>::
    _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x)
    {
      int __current_index = __x._M_leaf_index;
      const _RopeRep* __current_node = __x._M_path_end[__current_index];
      size_t __len = __current_node->_M_size;
      size_t __node_start_pos = __x._M_leaf_pos;
      unsigned char __dirns = __x._M_path_directions;
      _Rope_RopeConcatenation<_CharT, _Alloc>* __c;

      if (__x._M_current_pos - __node_start_pos < __len)
	{
	  /* More stuff in this leaf, we just didn't cache it. */
	  _S_setbuf(__x);
	  return;
	}
      //  node_start_pos is starting position of last_node.
      while (--__current_index >= 0)
	{
	  if (!(__dirns & 1) /* Path turned left */)
	    break;
	  __current_node = __x._M_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->_M_left->_M_size;
	  __dirns >>= 1;
	}
      if (__current_index < 0)
	{
	  // We underflowed the cache. Punt.
	  _S_setcache(__x);
	  return;
	}
      __current_node = __x._M_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->_M_left->_M_size;
      __current_node = __c->_M_right;
      __x._M_path_end[++__current_index] = __current_node;
      __dirns |= 1;
      while (_Rope_constants::_S_concat == __current_node->_M_tag)
	{
	  ++__current_index;
	  if (int(_S_path_cache_len) == __current_index)
	    {
	      int __i;
	      for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++)
		__x._M_path_end[__i] = __x._M_path_end[__i+1];
	      --__current_index;
	    }
	  __current_node =
	    ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left;
	  __x._M_path_end[__current_index] = __current_node;
	  __dirns <<= 1;
	  // node_start_pos is unchanged.
	}
      __x._M_leaf_index = __current_index;
      __x._M_leaf_pos = __node_start_pos;
      __x._M_path_directions = __dirns;
      _S_setbuf(__x);
    }

  template <class _CharT, class _Alloc>
    void
    _Rope_iterator_base<_CharT, _Alloc>::
    _M_incr(size_t __n)
    {
      _M_current_pos += __n;
      if (0 != _M_buf_ptr)
	{
	  size_t __chars_left = _M_buf_end - _M_buf_ptr;
	  if (__chars_left > __n)
	    _M_buf_ptr += __n;
	  else if (__chars_left == __n)
	    {
	      _M_buf_ptr += __n;
	      _S_setcache_for_incr(*this);
	    }
	  else
	    _M_buf_ptr = 0;
	}
    }

  template <class _CharT, class _Alloc>
    void
    _Rope_iterator_base<_CharT, _Alloc>::
    _M_decr(size_t __n)
    {
      if (0 != _M_buf_ptr)
	{
	  size_t __chars_left = _M_buf_ptr - _M_buf_start;
	  if (__chars_left >= __n)
	    _M_buf_ptr -= __n;
	  else
	    _M_buf_ptr = 0;
	}
      _M_current_pos -= __n;
    }

  template <class _CharT, class _Alloc>
    void
    _Rope_iterator<_CharT, _Alloc>::
    _M_check()
    {
      if (_M_root_rope->_M_tree_ptr != this->_M_root)
	{
	  // _Rope was modified.  Get things fixed up.
	  _RopeRep::_S_unref(this->_M_root);
	  this->_M_root = _M_root_rope->_M_tree_ptr;
	  _RopeRep::_S_ref(this->_M_root);
	  this->_M_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._M_tree_ptr, __pos),
      _M_root_rope(&__r)
    { _RopeRep::_S_ref(this->_M_root); }

  template <class _CharT, class _Alloc>
    inline size_t
    rope<_CharT, _Alloc>::
    _S_char_ptr_len(const _CharT* __s)
    {
      const _CharT* __p = __s;
      
      while (!_S_is0(*__p))
	++__p;
      return (__p - __s);
    }


#ifndef __GC

  template <class _CharT, class _Alloc>
    inline void
    _Rope_RopeRep<_CharT, _Alloc>::
    _M_free_c_string()
    {
      _CharT* __cstr = _M_c_string;
      if (0 != __cstr)
	{
	  size_t __size = this->_M_size + 1;
	  _Destroy(__cstr, __cstr + __size, get_allocator());
	  this->_Data_deallocate(__cstr, __size);
	}
    }

  template <class _CharT, class _Alloc>
    inline void
    _Rope_RopeRep<_CharT, _Alloc>::
    _S_free_string(_CharT* __s, size_t __n, allocator_type __a)
    {
      if (!_S_is_basic_char_type((_CharT*)0))
	_Destroy(__s, __s + __n, __a);
      
      //  This has to be a static member, so this gets a bit messy
      __a.deallocate(__s,
		     _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n));
    }

  //  There are several reasons for not doing this with virtual destructors
  //  and a class specific delete operator:
  //  - A class specific delete operator can't easily get access to
  //    allocator instances if we need them.
  //  - Any virtual function would need a 4 or byte vtable pointer;
  //    this only requires a one byte tag per object.
  template <class _CharT, class _Alloc>
    void
    _Rope_RopeRep<_CharT, _Alloc>::
    _M_free_tree()
    {
      switch(_M_tag)
	{
	case _Rope_constants::_S_leaf:
	  {
	    _Rope_RopeLeaf<_CharT, _Alloc>* __l
	      = (_Rope_RopeLeaf<_CharT, _Alloc>*)this;
	    __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf();
	    _L_deallocate(__l, 1);
	    break;
	  }
	case _Rope_constants::_S_concat:
	  {
	    _Rope_RopeConcatenation<_CharT,_Alloc>* __c
	      = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this;
	    __c->_Rope_RopeConcatenation<_CharT, _Alloc>::
	      ~_Rope_RopeConcatenation();
	    _C_deallocate(__c, 1);
	    break;
	  }
	case _Rope_constants::_S_function:
	  {
	    _Rope_RopeFunction<_CharT, _Alloc>* __f
	      = (_Rope_RopeFunction<_CharT, _Alloc>*)this;
	    __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction();
	    _F_deallocate(__f, 1);
	    break;
	  }
	case _Rope_constants::_S_substringfn:
	  {
	    _Rope_RopeSubstring<_CharT, _Alloc>* __ss =
	      (_Rope_RopeSubstring<_CharT, _Alloc>*)this;
	    __ss->_Rope_RopeSubstring<_CharT, _Alloc>::
	      ~_Rope_RopeSubstring();
	    _S_deallocate(__ss, 1);
	    break;
	  }
	}
    }
#else

  template <class _CharT, class _Alloc>
    inline void
    _Rope_RopeRep<_CharT, _Alloc>::
    _S_free_string(const _CharT*, size_t, allocator_type)
    { }

#endif

  // Concatenate a C string onto a leaf rope by copying the rope data.
  // Used for short ropes.