_rope.c

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

                           __base->get_allocator());
  }
  }
  /*NOTREACHED*/
  _STLP_ASSERT(false)
  lazy:
  {
    // Create substring node.
    return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
                                __base->get_allocator());
  }
}

template<class _CharT>
class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> {
private:
  _CharT* _M_buf_ptr;
public:
  _Rope_flatten_char_consumer(_CharT* __buffer) {
    _M_buf_ptr = __buffer;
  }
  ~_Rope_flatten_char_consumer() {}
  bool operator() (const _CharT* __leaf, size_t __n) {
    _STLP_PRIV __ucopy_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;
  }
};

#if !defined (_STLP_USE_NO_IOSTREAMS)
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;
  typedef _Rope_insert_char_consumer<_CharT,_Traits> _Self;
  _Insert_ostream& _M_o;

  //explicitely defined as private to avoid warnings:
  _Self& operator = (_Self const&);
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;
}
#endif /* !_STLP_USE_NO_IOSTREAMS */

template <class _CharT, class _Alloc, class _CharConsumer>
bool _S_apply_to_pieces(_CharConsumer& __c,
                        _Rope_RopeRep<_CharT, _Alloc> * __r,
                        size_t __begin, size_t __end) {
  typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
  typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation;
  typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf;
  typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction;

  if (0 == __r) return true;
  switch(__r->_M_tag) {
  case _RopeRep::_S_concat:
  {
    _RopeConcatenation* __conc = __STATIC_CAST(_RopeConcatenation*, __r);
    _RopeRep* __left =  __conc->_M_left;
    size_t __left_len = __left->_M_size._M_data;
    if (__begin < __left_len) {
      size_t __left_end = (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 = (max)(__left_len, __begin);
      if (!_S_apply_to_pieces(__c, __right,
                              __right_start - __left_len,
                              __end - __left_len)) {
        return false;
      }
    }
  }
  return true;
  case _RopeRep::_S_leaf:
  {
    _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
    return __c(__l->_M_data + __begin, __end - __begin);
  }
  case _RopeRep::_S_function:
  case _RopeRep::_S_substringfn:
  {
    _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
    size_t __len = __end - __begin;
    bool __result;
    _CharT* __buffer = __r->get_allocator().allocate(__len);
    _STLP_TRY {
      (*(__f->_M_fn))(__begin, __len, __buffer);
      __result = __c(__buffer, __len);
      __r->get_allocator().deallocate(__buffer, __len);
    }
    _STLP_UNWIND((__r->get_allocator().deallocate(__buffer, __len)))
    return __result;
  }
  default:
    _STLP_ASSERT(false)
    /*NOTREACHED*/
    return false;
  }
}

#if !defined (_STLP_USE_NO_IOSTREAMS)
template<class _CharT, class _Traits>
inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, streamsize __n) {
  char __f = __o.fill();
  for (streamsize __i = 0; __i < __n; ++__i) __o.put(__f);
}

template<class _CharT, class _Traits, class _Alloc>
basic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o,
                                          const rope<_CharT, _Alloc>& __r, const __true_type& /*_IsBasicCharType*/) {
  streamsize __w = __o.width();
  const bool __left = (__o.flags() & ios::left) != 0;
  size_t __rope_len = __r.size();
  _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);

  const bool __need_pad = (((sizeof(streamsize) > sizeof(size_t)) && (__STATIC_CAST(streamsize, __rope_len) < __w)) ||
                           ((sizeof(streamsize) <= sizeof(size_t)) && (__rope_len < __STATIC_CAST(size_t, __w))));
  streamsize __pad_len = __need_pad ? __w - __rope_len : 0;

  if (!__left && __pad_len > 0) {
    _Rope_fill(__o, __pad_len);
  }
  __r.apply_to_pieces(0, __rope_len, __c);
  if (__left && __pad_len > 0) {
    _Rope_fill(__o, __pad_len);
  }
  return __o;
}

template<class _CharT, class _Traits, class _Alloc>
basic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o,
                                         const rope<_CharT, _Alloc>& __r, const __false_type& /*_IsBasicCharType*/) {
  streamsize __w = __o.width();
  size_t __rope_len = __r.size();
  _Rope_insert_char_consumer<_CharT, _Traits> __c(__o);

  __o.width(__w /__rope_len);
  _STLP_TRY {
    __r.apply_to_pieces(0, __rope_len, __c);
    __o.width(__w);
  }
  _STLP_UNWIND(__o.width(__w))
  return __o;
}

template<class _CharT, class _Traits, class _Alloc>
basic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __o,
                                           const rope<_CharT, _Alloc>& __r) {
  typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral;
  return _S_io_get(__o, __r, _Char_Is_Integral());
}
#endif /* NO_IOSTREAMS */

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, _M_tree_ptr._M_data, __start, size());
  size_type __result_pos = __start + __c._M_count;
#ifndef _STLP_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(_Rope_RopeRep<_CharT, _Alloc>* __r, _CharT* __buffer) {
  if (0 == __r) return __buffer;
  switch(__r->_M_tag) {
  case _RopeRep::_S_concat:
  {
    _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r);
    _RopeRep* __left = __c->_M_left;
    _RopeRep* __right = __c->_M_right;
    _CharT* __rest = _S_flatten(__left, __buffer);
    return _S_flatten(__right, __rest);
  }
  case _RopeRep::_S_leaf:
  {
    _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r);
    return _STLP_PRIV __ucopy_n(__l->_M_data, __l->_M_size._M_data, __buffer).second;
  }
  case _RopeRep::_S_function:
  case _RopeRep::_S_substringfn:
  // We dont yet do anything with substring nodes.
  // This needs to be fixed before ropefiles will work well.
  {
    _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r);
    (*(__f->_M_fn))(0, __f->_M_size._M_data, __buffer);
    return __buffer + __f->_M_size._M_data;
  }
  default:
    _STLP_ASSERT(false)
    /*NOTREACHED*/
    return 0;
  }
}

#ifdef _STLP_DEBUG
// 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 (_RopeRep::_S_concat == __r->_M_tag) {
    _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r);
    _RopeRep* __left = __c->_M_left;
    _RopeRep* __right = __c->_M_right;
    printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n",
      __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data,
      __r->_M_is_balanced? "" : "not");
    _S_dump(__left, __indent + 2);
    _S_dump(__right, __indent + 2);
    return;
  }
  else {
    const char* __kind;

    switch (__r->_M_tag) {
      case _RopeRep::_S_leaf:
        __kind = "Leaf";
        break;
      case _RopeRep::_S_function:
        __kind = "Function";
        break;
      case _RopeRep::_S_substringfn:
        __kind = "Function representing substring";
        break;
      default:
        __kind = "(corrupted kind field!)";
    }
    printf("%s %p (rc = %ld, depth = %d, len = %ld) ",
     __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data);
    if (sizeof(_CharT) == 1) {
      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._M_data > __prefix->_M_size._M_data;

      _S_flatten(__prefix, __buffer);
      __buffer[__prefix->_M_size._M_data] = _STLP_DEFAULT_CONSTRUCTED(_CharT);
      printf("%s%s\n", (char*)__buffer, __too_big? "...\n" : "\n");
    } else {
      printf("\n");
    }
  }
}
#endif /* _STLP_DEBUG */

# define __ROPE_TABLE_BODY  = { \
/* 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 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul,   \
/* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul,                \
/* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul,             \
/* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul,          \
/* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul,      \
/* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul,                        \
/* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul,                      \
/* 45 */2971215073ul }

template <class _CharT, class _Alloc>
const unsigned long
rope<_CharT,_Alloc>::_S_min_len[__ROPE_DEPTH_SIZE] __ROPE_TABLE_BODY;
# undef __ROPE_DEPTH_SIZE
# undef __ROPE_MAX_DEPTH
# undef __ROPE_TABLE_BODY

// These are Fibonacci numbers < 2**32.

template <class _CharT, class _Alloc>
__RopeRep__* rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) {
  _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                                                         0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
                                                         0,0,0,0,0,0};
  _RopeRep* __result = 0;
  int __i;
  // Invariant:
  // The concatenation of forest in descending order is equal to __r.
  // __forest[__i]._M_size._M_data >= _S_min_len[__i]
  // __forest[__i]._M_depth = __i
  // References from forest are included in refcount.

  _STLP_TRY {
    _S_add_to_forest(__r, __forest);
    for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
      if (0 != __forest[__i]) {
        _Self_destruct_ptr __old(__result);
        __result = _S_concat_rep(__forest[__i], __result);
        __forest[__i]->_M_unref_nonnil();
# ifdef _STLP_USE_EXCEPTIONS
        __forest[__i] = 0;
# endif
      }
    }
    _STLP_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i)
    _S_unref(__forest[__i]))
    if (__result->_M_depth > _RopeRep::_S_max_rope_depth) {
      __stl_throw_range_error("rope too long");
    }
    return(__result);
}