_rope.c

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

    }
  }
}

# if defined ( _STLP_NESTED_TYPE_PARAM_BUG )
#   define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
#   define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
#   define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc>
#   define _RopeRep _Rope_RopeRep<_CharT,_Alloc>
#   define size_type size_t
# else
#   define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
#   define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
# endif

template <class _CharT, class _Alloc>
void rope<_CharT, _Alloc>::_M_throw_out_of_range() const {
  __stl_throw_out_of_range("rope");
}

// Concatenate a C string onto a leaf rope by copying the rope data.
// Used for short ropes.
template <class _CharT, class _Alloc>
__RopeLeaf__*
rope<_CharT,_Alloc>::_S_leaf_concat_char_iter (
  _RopeLeaf* __r, const _CharT* __iter, size_t __len) {
  size_t __old_len = __r->_M_size._M_data;
  _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len));
  _RopeLeaf* __result;

  _STLP_PRIV __ucopy_n(__r->_M_data, __old_len, __new_data);
  _STLP_PRIV __ucopy_n(__iter, __len, __new_data + __old_len);
  _S_construct_null(__new_data + __old_len + __len);
  _STLP_TRY {
    __result = _S_new_RopeLeaf(__new_data, __old_len + __len, __r->get_allocator());
  }
  _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len,
                                        __r->get_allocator()))
  return __result;
}

template <class _CharT, class _Alloc>
void _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r,
                         size_t __size, const __true_type& /*basic char type*/) {
  _S_construct_null(__r->_M_data + __size);
  _STLP_ASSERT(__r->_M_c_string == __r->_M_data)
}

template <class _CharT, class _Alloc>
void _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r,
                         size_t, const __false_type& /*basic char type*/) {
  if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) {
    __r->_M_free_c_string();
    __r->_M_c_string = 0;
  }
}

// As above, but it's OK to clobber original if refcount is 1
template <class _CharT, class _Alloc>
__RopeLeaf__*
rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter (_RopeLeaf* __r, const _CharT* __iter, size_t __len) {
  //_STLP_ASSERT(__r->_M_ref_count >= 1)
  if ( /* __r->_M_ref_count > 1 */  __r->_M_incr() > 2 ) { // - ptr
    __r->_M_decr(); // - ptr
    return _S_leaf_concat_char_iter(__r, __iter, __len);
  }
  __r->_M_decr(); // - ptr, __r->_M_ref_count == 1 or 0
  size_t __old_len = __r->_M_size._M_data;
  if (_S_rounded_up_size(__old_len) == _S_rounded_up_size(__old_len + __len)) {
    // The space has been partially initialized for the standard
    // character types.  But that doesn't matter for those types.
    _STLP_PRIV __ucopy_n(__iter, __len, __r->_M_data + __old_len);
    _Terminate_RopeLeaf(__r, __old_len + __len, _IsBasicCharType());
    __r->_M_size._M_data = __old_len + __len;
    // _STLP_ASSERT(__r->_M_ref_count == 1)
    // __r->_M_ref_count = 2;
    __r->_M_incr(); // i.e.  __r->_M_ref_count = 2
    return __r;
  } else {
    _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
    //_STLP_ASSERT(__result->_M_ref_count == 1)
    return __result;
  }
}

// Assumes left and right are not 0.
// Does not increment (nor decrement on exception) child reference counts.
// Result has ref count 1.
template <class _CharT, class _Alloc>
__RopeRep__*
rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) {
  _RopeConcatenation* __result =
    _S_new_RopeConcatenation(__left, __right, __left->get_allocator());
  size_t __depth = __result->_M_depth;

  _STLP_ASSERT(__left->get_allocator() == __right->get_allocator())
  if (__depth > 20 && (__result->_M_size._M_data < 1000 ||
      __depth > _RopeRep::_S_max_rope_depth)) {
    _RopeRep* __balanced;

    _STLP_TRY {
      __balanced = _S_balance(__result);
     // _STLP_ASSERT(__result == __balanced ||
     //              1 == __result->_M_ref_count &&
     //              1 == __balanced->_M_ref_count)
      __result->_M_unref_nonnil();
    }
    _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type,(allocator_type&)__left->_M_size,
                                         _RopeConcatenation).deallocate(__result,1)))
    // In case of exception, we need to deallocate
    // otherwise dangling result node.  But caller
    // still owns its children.  Thus unref is
    // inappropriate.
    return __balanced;
  } else {
    return __result;
  }
}

template <class _CharT, class _Alloc>
__RopeRep__*
rope<_CharT,_Alloc>::_S_concat_char_iter (_RopeRep* __r,
                                          const _CharT*__s, size_t __slen) {
  _RopeRep* __result;
  if (0 == __slen) {
    _S_ref(__r);
    return __r;
  }
  if (0 == __r)
    return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
  if (_RopeRep::_S_leaf == __r->_M_tag &&
      __r->_M_size._M_data + __slen <= _S_copy_max) {
    __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
    // _STLP_ASSERT(1 == __result->_M_ref_count)
    return __result;
  }
  if (_RopeRep::_S_concat == __r->_M_tag &&
      _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
    _RopeLeaf* __right = (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
    if (__right->_M_size._M_data + __slen <= _S_copy_max) {
      _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
      _RopeRep* __nright = _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
      __left->_M_ref_nonnil();
      _STLP_TRY {
        __result = _S_tree_concat(__left, __nright);
      }
      _STLP_UNWIND(_S_unref(__left); _S_unref(__nright))
      // _STLP_ASSERT(1 == __result->_M_ref_count)
      return __result;
    }
  }
  _RopeRep* __nright =
    _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
  _STLP_TRY {
    __r->_M_ref_nonnil();
    __result = _S_tree_concat(__r, __nright);
  }
  _STLP_UNWIND(_S_unref(__r); _S_unref(__nright))
  // _STLP_ASSERT(1 == __result->_M_ref_count)
  return __result;
}

template <class _CharT, class _Alloc>
__RopeRep__*
rope<_CharT,_Alloc>::_S_destr_concat_char_iter(
  _RopeRep* __r, const _CharT* __s, size_t __slen) {
  _RopeRep* __result;
  if (0 == __r)
    return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen,
                                             __r->get_allocator());
  // size_t __count = __r->_M_ref_count;
  size_t __orig_size = __r->_M_size._M_data;
  // _STLP_ASSERT(__count >= 1)
  if ( /* __count > 1 */ __r->_M_incr() > 2 ) {
    __r->_M_decr();
    return _S_concat_char_iter(__r, __s, __slen);
  }
  if (0 == __slen) {
    return __r;
  }
  __r->_M_decr();
  if (__orig_size + __slen <= _S_copy_max && _RopeRep::_S_leaf == __r->_M_tag) {
    return _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
  }
  if (_RopeRep::_S_concat == __r->_M_tag) {
    _RopeLeaf* __right = __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __r)->_M_right);
    if (_RopeRep::_S_leaf == __right->_M_tag &&
        __right->_M_size._M_data + __slen <= _S_copy_max) {
      _RopeRep* __new_right = _S_destr_leaf_concat_char_iter(__right, __s, __slen);
      if (__right == __new_right) {
        // _STLP_ASSERT(__new_right->_M_ref_count == 2)
        // __new_right->_M_ref_count = 1;
        __new_right->_M_decr();
      } else {
        // _STLP_ASSERT(__new_right->_M_ref_count >= 1)
        __right->_M_unref_nonnil();
      }
      // _STLP_ASSERT(__r->_M_ref_count == 1)
      // __r->_M_ref_count = 2;    // One more than before.
      __r->_M_incr();
      __STATIC_CAST(_RopeConcatenation*, __r)->_M_right = __new_right;
      // E.Musser : moved below
      //    __r->_M_size._M_data = __orig_size + __slen;
      if (0 != __r->_M_c_string) {
        __r->_M_free_c_string();
        __r->_M_c_string = 0;
      }
      __r->_M_size._M_data = __orig_size + __slen;
      return __r;
    }
  }
  _RopeRep* __right =
    _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator());
  __r->_M_ref_nonnil();
  _STLP_TRY {
    __result = _S_tree_concat(__r, __right);
  }
  _STLP_UNWIND(_S_unref(__r); _S_unref(__right))
    // _STLP_ASSERT(1 == __result->_M_ref_count)
  return __result;
}

template <class _CharT, class _Alloc>
__RopeRep__*
rope<_CharT,_Alloc>::_S_concat_rep(_RopeRep* __left, _RopeRep* __right) {
  if (0 == __left) {
    _S_ref(__right);
    return __right;
  }
  if (0 == __right) {
    __left->_M_ref_nonnil();
    return __left;
  }
  if (_RopeRep::_S_leaf == __right->_M_tag) {
    if (_RopeRep::_S_leaf == __left->_M_tag) {
      if (__right->_M_size._M_data + __left->_M_size._M_data <= _S_copy_max) {
        return _S_leaf_concat_char_iter(__STATIC_CAST(_RopeLeaf*, __left),
                                        __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
                                        __right->_M_size._M_data);
      }
    } else if (_RopeRep::_S_concat == __left->_M_tag &&
               _RopeRep::_S_leaf == __STATIC_CAST(_RopeConcatenation*, __left)->_M_right->_M_tag) {
      _RopeLeaf* __leftright =
        __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __left)->_M_right);
      if (__leftright->_M_size._M_data + __right->_M_size._M_data <= _S_copy_max) {
        _RopeRep* __leftleft = __STATIC_CAST(_RopeConcatenation*, __left)->_M_left;
        _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
                                                    __STATIC_CAST(_RopeLeaf*, __right)->_M_data,
                                                    __right->_M_size._M_data);
        __leftleft->_M_ref_nonnil();
        _STLP_TRY {
          return _S_tree_concat(__leftleft, __rest);
        }
        _STLP_UNWIND(_S_unref(__leftleft); _S_unref(__rest))
      }
    }
  }
  __left->_M_ref_nonnil();
  __right->_M_ref_nonnil();
  _STLP_TRY {
    return _S_tree_concat(__left, __right);
  }
  _STLP_UNWIND(_S_unref(__left); _S_unref(__right))
  _STLP_RET_AFTER_THROW(0)
}

template <class _CharT, class _Alloc>
__RopeRep__*
rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base,
                                  size_t __start, size_t __endp1) {
  if (0 == __base) return 0;
  size_t __len = __base->_M_size._M_data;
  size_t __adj_endp1;
  const size_t __lazy_threshold = 128;

  if (__endp1 >= __len) {
    if (0 == __start) {
      __base->_M_ref_nonnil();
      return __base;
    } else {
      __adj_endp1 = __len;
    }
  } else {
    __adj_endp1 = __endp1;
  }
  switch(__base->_M_tag) {
  case _RopeRep::_S_concat:
  {
    _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __base);
    _RopeRep* __left = __c->_M_left;
    _RopeRep* __right = __c->_M_right;
    size_t __left_len = __left->_M_size._M_data;
    _RopeRep* __result;

    if (__adj_endp1 <= __left_len) {
      return _S_substring(__left, __start, __endp1);
    } else if (__start >= __left_len) {
      return _S_substring(__right, __start - __left_len,
                          __adj_endp1 - __left_len);
    }
    _Self_destruct_ptr __left_result(_S_substring(__left, __start, __left_len));
    _Self_destruct_ptr __right_result(_S_substring(__right, 0, __endp1 - __left_len));
    _STLP_MPWFIX_TRY    //*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block
    __result = _S_concat_rep(__left_result, __right_result);
    // _STLP_ASSERT(1 == __result->_M_ref_count)
    return __result;
    _STLP_MPWFIX_CATCH    //*TY 06/01/2000 -
  }
  case _RopeRep::_S_leaf:
  {
    _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __base);
    _RopeLeaf* __result;
    size_t __result_len;
    if (__start >= __adj_endp1) return 0;
    __result_len = __adj_endp1 - __start;
    if (__result_len > __lazy_threshold) goto lazy;
    const _CharT* __section = __l->_M_data + __start;
    // We should sometimes create substring node instead.
    __result = _S_RopeLeaf_from_unowned_char_ptr(__section, __result_len,
                                                 __base->get_allocator());
    return __result;
  }
  case _RopeRep::_S_substringfn:
  // Avoid introducing multiple layers of substring nodes.
  {
    _RopeSubstring* __old = __STATIC_CAST(_RopeSubstring*, __base);
    size_t __result_len;
    if (__start >= __adj_endp1) return 0;
    __result_len = __adj_endp1 - __start;
    if (__result_len > __lazy_threshold) {
      _RopeSubstring* __result = _S_new_RopeSubstring(__old->_M_base,
                                                      __start + __old->_M_start,
                                                      __adj_endp1 - __start,
                                                      __base->get_allocator());
      return __result;
    } // *** else fall through: ***
  }
  case _RopeRep::_S_function:
  {
    _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __base);
    if (__start >= __adj_endp1) return 0;
    size_t __result_len = __adj_endp1 - __start;

    if (__result_len > __lazy_threshold) goto lazy;
    _CharT* __section = __base->_M_size.allocate(_S_rounded_up_size(__result_len));
    _STLP_TRY {
      (*(__f->_M_fn))(__start, __result_len, __section);
    }
    _STLP_UNWIND(_RopeRep::_S_free_string(__section,
                                          __result_len, __base->get_allocator()))
    _S_construct_null(__section + __result_len);
    return _S_new_RopeLeaf(__section, __result_len,