_rope.c

来自「stl的源码」· C语言 代码 · 共 1,408 行 · 第 1/4 页

/*
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1999
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

// 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.
#ifndef _STLP_ROPEIMPL_H
#define _STLP_ROPEIMPL_H

#ifndef _STLP_INTERNAL_ROPE_H
#  include <stl/_rope.h>
#endif

#ifndef _STLP_INTERNAL_CSTDIO
#  include <stl/_cstdio.h>
#endif

#if !defined (_STLP_USE_NO_IOSTREAMS)
#  ifndef _STLP_INTERNAL_OSTREAM_H
#    include <stl/_ostream.h>
#  endif

#  ifndef _STLP_INTERNAL_ISTREAM
#    include <stl/_istream.h>
#  endif
#endif

#include <stl/_range_errors.h>

_STLP_BEGIN_NAMESPACE

#if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
#  define __allocator__ _Alloc
#else
#  define __allocator__ allocator_type
#endif

template<class _CharT, class _Alloc>
_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos)
  : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos),
  _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); }

template<class _CharT, class _Alloc>
_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos):
  _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos),
  _M_root_rope(&__r) {
#if !defined (__DMC__)
  _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this);
#else
  _Rope_iterator_base<_CharT, _Alloc>* __x = this;
  _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*__x);
#endif
}

template<class _CharT, class _Alloc>
void _Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string() {
  _CharT* __cstr = _M_c_string;
  if (0 != __cstr) {
    size_t _p_size = _M_size._M_data + 1;
    _STLP_STD::_Destroy_Range(__cstr, __cstr + _p_size);
    _M_size.deallocate(__cstr, _p_size);
  }
}

// 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._M_data[__x._M_leaf_index];
  size_t __leaf_pos = __x._M_leaf_pos;
  size_t __pos = __x._M_current_pos;

  switch(__leaf->_M_tag) {
  case _RopeRep::_S_leaf:
    typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
    __x._M_buf_start = __STATIC_CAST(const _RopeLeaf*, __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._M_data;
    break;
  case _RopeRep::_S_function:
  case _RopeRep::_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._M_data;
      typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
      char_producer<_CharT>* __fn = __STATIC_CAST(const _RopeFunction*, __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._M_data);
      __x._M_buf_ptr = __x._M_tmp_buf._M_data + (__pos - __buf_start_pos);
      __x._M_buf_start = __x._M_tmp_buf._M_data;
      __x._M_buf_end = __x._M_tmp_buf._M_data + __len;
    }
    break;
  default:
      _STLP_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>::_S_setcache(
  _Rope_iterator_base<_CharT,_Alloc>& __x) {
  const _RopeRep* __path[_RopeRep::_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

  _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data)
  if (__pos >= __x._M_root->_M_size._M_data) {
    __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._M_data;
    __x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
    __x._M_path_end._M_data[0] = __curr_rope;
    __x._M_leaf_index = 0;
    __x._M_leaf_pos = 0;
    return;
  }
  for(;;) {
    ++__curr_depth;
    _STLP_ASSERT(__curr_depth <= _RopeRep::_S_max_rope_depth)
    __path[__curr_depth] = __curr_rope;
    switch(__curr_rope->_M_tag) {
    case _RopeRep::_S_leaf:
    case _RopeRep::_S_function:
    case _RopeRep::_S_substringfn:
      __x._M_leaf_pos = __curr_start_pos;
      goto done;
    case _RopeRep::_S_concat:
      {
        const _RopeConcat* __c = __STATIC_CAST(const _RopeConcat*, __curr_rope);
        _RopeRep* __left = __c->_M_left;
        size_t __left_len = __left->_M_size._M_data;

        __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 - _S_path_cache_len;

    if (__j < 0) __j = 0;
    while (__j <= __curr_depth) {
      __x._M_path_end._M_data[++__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._M_data[__current_index];
  size_t __len = __current_node->_M_size._M_data;
  size_t __node_start_pos = __x._M_leaf_pos;
  unsigned char __dirns = __x._M_path_directions;
  const _RopeConcat* __c;

  _STLP_ASSERT(__x._M_current_pos <= __x._M_root->_M_size._M_data)
  if (__x._M_current_pos - __node_start_pos < __len) {
    /* More stuff in this leaf, we just didn't cache it. */
    _S_setbuf(__x);
    return;
  }
  _STLP_ASSERT(__node_start_pos + __len == __x._M_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._M_path_end._M_data[__current_index];
    __c = __STATIC_CAST(const _RopeConcat*, __current_node);
    // Otherwise we were in the right child.  Thus we should pop
    // the concatenation node.
    __node_start_pos -= __c->_M_left->_M_size._M_data;
    __dirns >>= 1;
  }
  if (__current_index < 0) {
    // We underflowed the cache. Punt.
    _S_setcache(__x);
    return;
  }
  __current_node = __x._M_path_end._M_data[__current_index];
  __c = __STATIC_CAST(const _RopeConcat*, __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._M_data;
  __current_node = __c->_M_right;
  __x._M_path_end._M_data[++__current_index] = __current_node;
  __dirns |= 1;
  while (_RopeRep::_S_concat == __current_node->_M_tag) {
    ++__current_index;
    if (_S_path_cache_len == __current_index) {
      int __i;
      for (__i = 0; __i < _S_path_cache_len-1; ++__i) {
        __x._M_path_end._M_data[__i] = __x._M_path_end._M_data[__i+1];
      }
      --__current_index;
    }
    __current_node = __STATIC_CAST(const _RopeConcat*, __current_node)->_M_left;
    __x._M_path_end._M_data[__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._M_data != 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._M_data;
    _RopeRep::_S_ref(this->_M_root);
    this->_M_buf_ptr = 0;
  }
}

//  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 _S_leaf:
    {
      typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
      _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, this);
      _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
      _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
                             _RopeLeaf).deallocate(__l, 1);
      break;
    }
  case _S_concat:
    {
      typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
      _RopeConcatenation* __c  = __STATIC_CAST(_RopeConcatenation*, this);
      _STLP_STD::_Destroy(__c);
      _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size,
                             _RopeConcatenation).deallocate(__c, 1);
      break;
    }
  case _S_function:
    {
      typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
      _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, this);
      _STLP_STD::_Destroy(__f);
      _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size,
                             _RopeFunction).deallocate(__f, 1);
      break;
    }
  case _S_substringfn:
    {
      typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
      _RopeSubstring* __rss = __STATIC_CAST(_RopeSubstring*, this);
      _STLP_STD::_Destroy(__rss);
      _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size,
                             _RopeSubstring).deallocate(__rss, 1);
      break;