_rope.c

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

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;
    }
    _STLP_ASSERT(__r->_M_tag == _RopeRep::_S_concat)
    {
      _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._M_data;

    for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
  if (0 != __forest[__i]) {
        _Self_destruct_ptr __old(__too_tiny);
      __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny);
      __forest[__i]->_M_unref_nonnil();
      __forest[__i] = 0;
  }
    }
    {
    _Self_destruct_ptr __old(__too_tiny);
  __insertee = _S_concat_and_set_balanced(__too_tiny, __r);
    }
    // Too_tiny dead, and no longer included in refcount.
    // Insertee is live and included.
    _STLP_ASSERT(_S_is_almost_balanced(__insertee))
    _STLP_ASSERT(__insertee->_M_depth <= __r->_M_depth + 1)
    for (;; ++__i) {
      if (0 != __forest[__i]) {
        _Self_destruct_ptr __old(__insertee);
      __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee);
      __forest[__i]->_M_unref_nonnil();
      __forest[__i] = 0;
      _STLP_ASSERT(_S_is_almost_balanced(__insertee))
  }
  _STLP_ASSERT(_S_min_len[__i] <= __insertee->_M_size._M_data)
  _STLP_ASSERT(__forest[__i] == 0)
  if (__i == _RopeRep::_S_max_rope_depth ||
        __insertee->_M_size._M_data < _S_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>::_S_fetch(_RopeRep* __r, size_type __i)
{
    _CharT* __cstr = __r->_M_c_string;

    _STLP_ASSERT(__i < __r->_M_size._M_data)
    if (0 != __cstr) return __cstr[__i];
    for(;;) {
      switch(__r->_M_tag) {
  case _RopeRep::_S_concat:
      {
    _RopeConcatenation* __c = (_RopeConcatenation*)__r;
    _RopeRep* __left = __c->_M_left;
    size_t __left_len = __left->_M_size._M_data;

    if (__i >= __left_len) {
        __i -= __left_len;
        __r = __c->_M_right;
    } else {
        __r = __left;
    }
      }
      break;
  case _RopeRep::_S_leaf:
      {
    _RopeLeaf* __l = (_RopeLeaf*)__r;
    return __l->_M_data[__i];
      }
  case _RopeRep::_S_function:
  case _RopeRep::_S_substringfn:
      {
    _RopeFunction* __f = (_RopeFunction*)__r;
    _CharT __result;

    (*(__f->_M_fn))(__i, 1, &__result);
    return __result;
      }
      }
    }
#if defined(_STLP_NEED_UNREACHABLE_RETURN)
    return 0;
#endif
}

// 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>::_S_fetch_ptr(_RopeRep* __r, size_type __i)
{
    _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth];
    size_t __csptr = 0;

    for(;;) {
      // if (__r->_M_ref_count > 1) return 0;
      if ( __r->_M_incr() > 2 ) {
        __r->_M_decr();
        return 0;
      }
      switch(__r->_M_tag) {
  case _RopeRep::_S_concat:
      {
    _RopeConcatenation* __c = (_RopeConcatenation*)__r;
    _RopeRep* __left = __c->_M_left;
    size_t __left_len = __left->_M_size._M_data;

    if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c;
    if (__i >= __left_len) {
        __i -= __left_len;
        __r = __c->_M_right;
    } else {
        __r = __left;
    }
      }
      break;
  case _RopeRep::_S_leaf:
      {
    _RopeLeaf* __l = (_RopeLeaf*)__r;
    if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
        __clrstack[__csptr++] = __l;
    while (__csptr > 0) {
        -- __csptr;
        _RopeRep* __d = __clrstack[__csptr];
        __d->_M_free_c_string();
        __d->_M_c_string = 0;
    }
    return __l->_M_data + __i;
      }
  case _RopeRep::_S_function:
  case _RopeRep::_S_substringfn:
      return 0;
      }
    }
#if defined(_STLP_NEED_UNREACHABLE_RETURN)
    return 0;
#endif

}

// 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>::_S_compare (const _RopeRep* __left,
                                 const _RopeRep* __right) {
  size_t __left_len;
  size_t __right_len;

  if (0 == __right) return 0 != __left;
  if (0 == __left) return -1;
  __left_len = __left->_M_size._M_data;
  __right_len = __right->_M_size._M_data;
  if (_RopeRep::_S_leaf == __left->_M_tag) {
    const _RopeLeaf* __l = __STATIC_CAST(const _RopeLeaf*, __left);
    if (_RopeRep::_S_leaf == __right->_M_tag) {
      const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
      return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
                                                       __r->_M_data, __r->_M_data + __right_len);
    }
    else {
      const_iterator __rstart(__right, 0);
      const_iterator __rend(__right, __right_len);
      return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len,
                                                       __rstart, __rend);
    }
  }
  else {
    const_iterator __lstart(__left, 0);
    const_iterator __lend(__left, __left_len);
    if (_RopeRep::_S_leaf == __right->_M_tag) {
      const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right);
      return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend,
                                                       __r->_M_data, __r->_M_data + __right_len);
    }
    else {
      const_iterator __rstart(__right, 0);
      const_iterator __rend(__right, __right_len);
      return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend, __rstart, __rend);
    }
  }
}

// Assignment to reference proxies.
template <class _CharT, class _Alloc>
_Rope_char_ref_proxy<_CharT, _Alloc>&
_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) {
    _RopeRep* __old = _M_root->_M_tree_ptr._M_data;
  // First check for the case in which everything is uniquely
  // referenced.  In that case we can do this destructively.
  _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
  if (0 != __ptr) {
      *__ptr = __c;
      return *this;
  }
    _Self_destruct_ptr __left(
      _My_rope::_S_substring(__old, 0, _M_pos));
    _Self_destruct_ptr __right(
      _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size._M_data));
    _Self_destruct_ptr __result_left(
      _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));

    // _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count)
    _RopeRep* __result =
      _My_rope::_S_concat_rep(__result_left, __right);
    // _STLP_ASSERT(1 <= __result->_M_ref_count)
    _RopeRep::_S_unref(__old);
    _M_root->_M_tree_ptr._M_data = __result;
    return *this;
}

template <class _CharT, class _Alloc>
_Rope_char_ptr_proxy<_CharT, _Alloc>
_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const {
    return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this);
}

template<class _CharT, class _Alloc>
_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() };
// # endif

#if !defined (_STLP_STATIC_CONST_INIT_BUG) && !defined (_STLP_NO_STATIC_CONST_DEFINITION)
template <class _CharT, class _Alloc>
const size_t rope<_CharT, _Alloc>::npos;
#endif

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::c_str() const {
  if (0 == _M_tree_ptr._M_data) {
    // Possibly redundant, but probably fast.
    _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
    return _S_empty_c_str;
  }
  _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
  if (0 != __old_c_string) return __old_c_string;
  size_t __s = size();
  _CharT* __result = _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).allocate(__s + 1);
  _S_flatten(_M_tree_ptr._M_data, __result);
  _S_construct_null(__result + __s);
  __old_c_string = __STATIC_CAST(_CharT*, _Atomic_swap_ptr(__REINTERPRET_CAST(void* _STLP_VOLATILE*, &(_M_tree_ptr._M_data->_M_c_string)),
                                                           __result));
  if (0 != __old_c_string) {
    // 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.
    _STLP_STD::_Destroy_Range(__old_c_string, __old_c_string + __s + 1);
    _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).deallocate(__old_c_string, __s + 1);
  }
  return __result;
}

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
  if (0 == _M_tree_ptr._M_data) {
    _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
    return _S_empty_c_str;
  }
  _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
  if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) {
    return __old_c_string;
  }
  size_t __s = size();
  _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s));
  _S_flatten(_M_tree_ptr._M_data, __result);
  _S_construct_null(__result + __s);
  _M_tree_ptr._M_data->_M_unref_nonnil();
  _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, _M_tree_ptr);
  return __result;
}

// Algorithm specializations.  More should be added.

#if (!defined (_STLP_MSVC) || (_STLP_MSVC >= 1310)) && !defined (__DMC__)
// 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) {
  _STLP_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;
}


# 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, allocator<char> > __first,
                _Rope_iterator<wchar_t, allocator<char> > __middle,
                _Rope_iterator<wchar_t, allocator<char> > __last) {
    _Rope_rotate(__first, __middle, __last);
}
# endif
#endif /* _STLP_MSVC */

#   undef __RopeLeaf__
#   undef __RopeRep__
#   undef __RopeLeaf
#   undef __RopeRep
#   undef size_type

_STLP_END_NAMESPACE

# endif /* ROPEIMPL_H */

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