_rope.h

来自「stl的源码」· C头文件 代码 · 共 1,929 行 · 第 1/5 页

  // _Result is counted in refcount.
  static _RopeRep* _S_substring(_RopeRep* __base,
                                size_t __start, size_t __endp1);

  static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
                                       const _CharT* __iter, size_t __slen);
  // Concatenate rope and char ptr, copying __s.
  // Should really take an arbitrary iterator.
  // Result is counted in refcount.
  static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
                                             const _CharT* __iter, size_t __slen);
    // As above, but one reference to __r is about to be
    // destroyed.  Thus the pieces may be recycled if all
    // relevent reference counts are 1.

  // General concatenation on _RopeRep.  _Result
  // has refcount of 1.  Adjusts argument refcounts.
  static _RopeRep* _S_concat_rep(_RopeRep* __left, _RopeRep* __right);

public:
#if defined (_STLP_MEMBER_TEMPLATES)
  template <class _CharConsumer>
#else
  typedef _Rope_char_consumer<_CharT> _CharConsumer;
#endif
  void apply_to_pieces(size_t __begin, size_t __end,
                       _CharConsumer& __c) const
  { _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __begin, __end); }

protected:

  static size_t _S_rounded_up_size(size_t __n)
  { return _RopeRep::_S_rounded_up_size(__n); }

  // Allocate and construct a RopeLeaf using the supplied allocator
  // Takes ownership of s instead of copying.
  static _RopeLeaf* _S_new_RopeLeaf(_CharT *__s,
                                    size_t _p_size, allocator_type __a) {
    _RopeLeaf* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
                                                _RopeLeaf).allocate(1);
    _STLP_TRY {
      new(__space) _RopeLeaf(__s, _p_size, __a);
    }
   _STLP_UNWIND(_STLP_CREATE_ALLOCATOR(allocator_type,__a,
                                       _RopeLeaf).deallocate(__space, 1))
    return __space;
  }

  static _RopeConcatenation* _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
                                                      allocator_type __a) {
   _RopeConcatenation* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
                                                        _RopeConcatenation).allocate(1);
    return new(__space) _RopeConcatenation(__left, __right, __a);
  }

  static _RopeFunction* _S_new_RopeFunction(char_producer<_CharT>* __f,
                                            size_t _p_size, bool __d, allocator_type __a) {
   _RopeFunction* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
                                                   _RopeFunction).allocate(1);
    return new(__space) _RopeFunction(__f, _p_size, __d, __a);
  }

  static _RopeSubstring* _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
                                              size_t __l, allocator_type __a) {
   _RopeSubstring* __space = _STLP_CREATE_ALLOCATOR(allocator_type, __a,
                                                    _RopeSubstring).allocate(1);
    return new(__space) _RopeSubstring(__b, __s, __l, __a);
  }

  static
  _RopeLeaf* _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
                                               size_t _p_size, allocator_type __a) {
    if (0 == _p_size) return 0;

   _CharT* __buf = _STLP_CREATE_ALLOCATOR(allocator_type,__a, _CharT).allocate(_S_rounded_up_size(_p_size));

    _STLP_PRIV __ucopy_n(__s, _p_size, __buf);
    _S_construct_null(__buf + _p_size);

    _STLP_TRY {
      return _S_new_RopeLeaf(__buf, _p_size, __a);
    }
    _STLP_UNWIND(_RopeRep::_S_free_string(__buf, _p_size, __a))
    _STLP_RET_AFTER_THROW(0)
  }


  // Concatenation of nonempty strings.
  // Always builds a concatenation node.
  // Rebalances if the result is too deep.
  // Result has refcount 1.
  // Does not increment left and right ref counts even though
  // they are referenced.
  static _RopeRep*
  _S_tree_concat(_RopeRep* __left, _RopeRep* __right);

  // Concatenation helper functions
  static _RopeLeaf*
  _S_leaf_concat_char_iter(_RopeLeaf* __r,
                           const _CharT* __iter, size_t __slen);
  // Concatenate by copying leaf.
  // should take an arbitrary iterator
  // result has refcount 1.
  static _RopeLeaf* _S_destr_leaf_concat_char_iter
  (_RopeLeaf* __r, const _CharT* __iter, size_t __slen);
  // A version that potentially clobbers __r if __r->_M_ref_count == 1.


  // A helper function for exponentiating strings.
  // This uses a nonstandard refcount convention.
  // The result has refcount 0.
  typedef _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc> _Concat_fn;
#if !defined (__GNUC__) || (__GNUC__ < 3)
  friend _Concat_fn;
#else
  friend struct _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc>;
#endif

public:
  static size_t _S_char_ptr_len(const _CharT* __s) {
    return char_traits<_CharT>::length(__s);
  }

public: /* for operators */
  rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, __t) { }
private:
  // Copy __r to the _CharT buffer.
  // Returns __buffer + __r->_M_size._M_data.
  // Assumes that buffer is uninitialized.
  static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);

  // Again, with explicit starting position and length.
  // Assumes that buffer is uninitialized.
  static _CharT* _S_flatten(_RopeRep* __r,
                            size_t __start, size_t __len,
                            _CharT* __buffer);

  // fbp : HP aCC prohibits access to protected min_len from within static methods ( ?? )
public:
  static const unsigned long _S_min_len[__ROPE_DEPTH_SIZE];
protected:
  static bool _S_is_balanced(_RopeRep* __r)
  { return (__r->_M_size._M_data >= _S_min_len[__r->_M_depth]); }

  static bool _S_is_almost_balanced(_RopeRep* __r) {
    return (__r->_M_depth == 0 ||
            __r->_M_size._M_data >= _S_min_len[__r->_M_depth - 1]);
  }

  static bool _S_is_roughly_balanced(_RopeRep* __r) {
    return (__r->_M_depth <= 1 ||
            __r->_M_size._M_data >= _S_min_len[__r->_M_depth - 2]);
  }

  // Assumes the result is not empty.
  static _RopeRep* _S_concat_and_set_balanced(_RopeRep* __left,
                                              _RopeRep* __right) {
    _RopeRep* __result = _S_concat_rep(__left, __right);
    if (_S_is_balanced(__result)) __result->_M_is_balanced = true;
    return __result;
  }

  // The basic rebalancing operation.  Logically copies the
  // rope.  The result has refcount of 1.  The client will
  // usually decrement the reference count of __r.
  // The result is within height 2 of balanced by the above
  // definition.
  static _RopeRep* _S_balance(_RopeRep* __r);

  // Add all unbalanced subtrees to the forest of balanceed trees.
  // Used only by balance.
  static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);

  // Add __r to forest, assuming __r is already balanced.
  static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);

#ifdef _STLP_DEBUG
  // Print to stdout, exposing structure
  static void _S_dump(_RopeRep* __r, int __indent = 0);
#endif

  // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
  static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);

  void _STLP_FUNCTION_THROWS _M_throw_out_of_range() const;

  void _M_reset(_RopeRep* __r) {
    //if (__r != _M_tree_ptr._M_data) {
      _S_unref(_M_tree_ptr._M_data);
      _M_tree_ptr._M_data = __r;
    //}
  }

public:
  bool empty() const { return 0 == _M_tree_ptr._M_data; }

  // Comparison member function.  This is public only for those
  // clients that need a ternary comparison.  Others
  // should use the comparison operators below.
  int compare(const _Self& __y) const {
    return _S_compare(_M_tree_ptr._M_data, __y._M_tree_ptr._M_data);
  }

  rope(const _CharT* __s, const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, _S_RopeLeaf_from_unowned_char_ptr(__s, _S_char_ptr_len(__s),__a))
  {}

  rope(const _CharT* __s, size_t __len,
       const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, (_S_RopeLeaf_from_unowned_char_ptr(__s, __len, __a)))
  {}

  // Should perhaps be templatized with respect to the iterator type
  // and use Sequence_buffer.  (It should perhaps use sequence_buffer
  // even now.)
  rope(const _CharT *__s, const _CharT *__e,
       const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, _S_RopeLeaf_from_unowned_char_ptr(__s, __e - __s, __a))
  {}

  rope(const const_iterator& __s, const const_iterator& __e,
       const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, _S_substring(__s._M_root, __s._M_current_pos,
                                    __e._M_current_pos))
  {}

  rope(const iterator& __s, const iterator& __e,
       const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, _S_substring(__s._M_root, __s._M_current_pos,
                                    __e._M_current_pos))
  {}

  rope(_CharT __c, const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, (_RopeRep*)0) {
    _CharT* __buf = _M_tree_ptr.allocate(_S_rounded_up_size(1));

    _Copy_Construct(__buf, __c);
    _S_construct_null(__buf + 1);

    _STLP_TRY {
      _M_tree_ptr._M_data = _S_new_RopeLeaf(__buf, 1, __a);
    }
    _STLP_UNWIND(_RopeRep::_S_free_string(__buf, 1, __a))
  }

  rope(size_t __n, _CharT __c,
       const allocator_type& __a = allocator_type()):
    _M_tree_ptr(__a, (_RopeRep*)0) {
    if (0 == __n)
      return;

    rope<_CharT,_Alloc> __result;
# define  __exponentiate_threshold size_t(32)
    _RopeRep* __remainder;
    rope<_CharT,_Alloc> __remainder_rope;

    // gcc-2.7.2 bugs
    typedef _STLP_PRIV _Rope_Concat_fn<_CharT,_Alloc> _Concat_fn;

    size_t __exponent = __n / __exponentiate_threshold;
    size_t __rest = __n % __exponentiate_threshold;
    if (0 == __rest) {
      __remainder = 0;
    } else {
      _CharT* __rest_buffer = _M_tree_ptr.allocate(_S_rounded_up_size(__rest));
      uninitialized_fill_n(__rest_buffer, __rest, __c);
      _S_construct_null(__rest_buffer + __rest);
      _STLP_TRY {
        __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a);
      }
      _STLP_UNWIND(_RopeRep::_S_free_string(__rest_buffer, __rest, __a))
    }
    __remainder_rope._M_tree_ptr._M_data = __remainder;
    if (__exponent != 0) {
      _CharT* __base_buffer = _M_tree_ptr.allocate(_S_rounded_up_size(__exponentiate_threshold));
      _RopeLeaf* __base_leaf;
      rope<_CharT,_Alloc> __base_rope;
      uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c);
      _S_construct_null(__base_buffer + __exponentiate_threshold);
      _STLP_TRY {
        __base_leaf = _S_new_RopeLeaf(__base_buffer,
                                      __exponentiate_threshold, __a);
      }
      _STLP_UNWIND(_RopeRep::_S_free_string(__base_buffer,
                                            __exponentiate_threshold, __a))
      __base_rope._M_tree_ptr._M_data = __base_leaf;
      if (1 == __exponent) {
        __result = __base_rope;
        // One each for base_rope and __result
        //_STLP_ASSERT(2 == __result._M_tree_ptr._M_data->_M_ref_count)
      } else {
        __result = _STLP_PRIV __power(__base_rope, __exponent, _Concat_fn());
      }
      if (0 != __remainder) {
        __result += __remainder_rope;
      }
    } else {
      __result = __remainder_rope;
    }
    _M_tree_ptr._M_data = __result._M_tree_ptr._M_data;
    _M_tree_ptr._M_data->_M_ref_nonnil();
# undef __exponentiate_threshold
  }

  rope(const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, (_RopeRep*)0) {}

  // Construct a rope from a function that can compute its members
  rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
       const allocator_type& __a = allocator_type())
    : _M_tree_ptr(__a, (_RopeRep*)0) {
    _M_tree_ptr._M_data = (0 == __len) ?
      0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
  }

  rope(const _Self& __x)
    : _M_tree_ptr(__x._M_tree_ptr, __x._M_tree_ptr._M_data) {
    _S_ref(_M_tree_ptr._M_data);
  }

#if !defined (_STLP_NO_MOVE_SEMANTIC)
  rope(__move_source<_Self> __src)
    : _M_tree_ptr(__src.get()._M_tree_ptr, __src.get()._M_tree_ptr._M_data) {
    __src.get()._M_tree_ptr._M_data = 0;
  }
#endif

  ~rope() {
    _S_unref(_M_tree_ptr._M_data);
  }

  _Self& operator=(const _Self& __x) {
    _STLP_ASSERT(get_allocator() == __x.get_allocator())
    _S_ref(__x._M_tree_ptr._M_data);
    _M_reset(__x._M_tree_ptr._M_data);
    return *this;
  }

  void clear() {
    _S_unref(_M_tree_ptr._M_data);
    _M_tree_ptr._M_data = 0;
  }
  void push_back(_CharT __x) {
    _M_reset(_S_destr_concat_char_iter(_M_tree_ptr._M_data, &__x, 1));
  }

  void pop_back() {
    _RopeRep* __old = _M_tree_ptr._M_data;
    _M_tree_ptr._M_data =
      _S_substring(_M_tree_ptr._M_data, 0, _M_tree_ptr._M_data->_M_size._M_data - 1);
    _S_unref(__old);
  }

  _CharT back() const {
    return _S_fetch(_M_tree_ptr._M_data, _M_tree_ptr._M_data->_M_size._M_data - 1);
  }

  void push_front(_CharT __x) {
    _RopeRep* __old = _M_tree_ptr._M_data;
    _RopeRep* __left =
      _S_RopeLeaf_from_unowned_char_ptr(&__x, 1, _M_tree_ptr);
    _STLP_TRY {
      _M_tree_ptr._M_data = _S_concat_rep(__left, _M_tree_ptr._M_data);
      _S_unref(__old);
      _S_unref(__left);
    }
    _STLP_UNWIND(_S_unref(__left))
  }

  void pop_front() {
    _RopeRep* __old = _M_tree_ptr._M_data;
    _M_tree_ptr._M_data = _S_substring(_M_tree_ptr._M_data, 1, _M_tree_ptr._M_data->_M_size._M_data);
    _S_unref(__old);
  }

  _CharT front() const {
    return _S_fetch(_M_tree_ptr._M_data, 0);
  }

  void balance() {
    _RopeRep* __old = _M_tree_ptr._M_data;
    _M_tree_ptr._M_data = _S_balance(_M_tree_ptr._M_data);
    _S_unref(__old);
  }