stl_tree.h

自己做的交叉编译工具！gcc-3.4.5,glibc-2.3.6在ubuntu8.04上做的面向kernel-2.6.28的交叉编译工具

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator,
    bool>
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    insert_unique(const _Val& __v)
    {
      _Link_type __x = _M_begin();
      _Link_type __y = _M_end();
      bool __comp = true;
      while (__x != 0)
	{
	  __y = __x;
	  __comp = _M_impl._M_key_compare(_KeyOfValue()(__v), _S_key(__x));
	  __x = __comp ? _S_left(__x) : _S_right(__x);
	}
      iterator __j = iterator(__y);
      if (__comp)
	if (__j == begin())
	  return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
	else
	  --__j;
      if (_M_impl._M_key_compare(_S_key(__j._M_node), _KeyOfValue()(__v)))
	return pair<iterator,bool>(_M_insert(__x, __y, __v), true);
      return pair<iterator,bool>(__j, false);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    insert_unique(iterator __position, const _Val& __v)
    {
      if (__position._M_node == _M_leftmost())
	{
	  // begin()
	  if (size() > 0
	      && _M_impl._M_key_compare(_KeyOfValue()(__v), 
					_S_key(__position._M_node)))
	    return _M_insert(__position._M_node, __position._M_node, __v);
	  // First argument just needs to be non-null.
	  else
	    return insert_unique(__v).first;
	}
      else if (__position._M_node == _M_end())
	{
	  // end()
	  if (_M_impl._M_key_compare(_S_key(_M_rightmost()), 
				     _KeyOfValue()(__v)))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_unique(__v).first;
	}
      else
	{
	  iterator __before = __position;
	  --__before;
	  if (_M_impl._M_key_compare(_S_key(__before._M_node), 
				     _KeyOfValue()(__v))
	      && _M_impl._M_key_compare(_KeyOfValue()(__v),
					_S_key(__position._M_node)))
	    {
	      if (_S_right(__before._M_node) == 0)
		return _M_insert(0, __before._M_node, __v);
	      else
		return _M_insert(__position._M_node, __position._M_node, __v);
	      // First argument just needs to be non-null.
	    }
	  else
	    return insert_unique(__v).first;
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    insert_equal(iterator __position, const _Val& __v)
    {
      if (__position._M_node == _M_leftmost())
	{
	  // begin()
	  if (size() > 0
	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
					 _KeyOfValue()(__v)))
	    return _M_insert(__position._M_node, __position._M_node, __v);
	  // first argument just needs to be non-null
	  else
	    return insert_equal(__v);
	}
      else if (__position._M_node == _M_end())
	{
	  // end()
	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
				      _S_key(_M_rightmost())))
	    return _M_insert(0, _M_rightmost(), __v);
	  else
	    return insert_equal(__v);
	}
      else
	{
	  iterator __before = __position;
	  --__before;
	  if (!_M_impl._M_key_compare(_KeyOfValue()(__v), 
				      _S_key(__before._M_node))
	      && !_M_impl._M_key_compare(_S_key(__position._M_node),
					 _KeyOfValue()(__v)))
	    {
	      if (_S_right(__before._M_node) == 0)
		return _M_insert(0, __before._M_node, __v);
	      else
		return _M_insert(__position._M_node, __position._M_node, __v);
	      // First argument just needs to be non-null.
	    }
	  else
	    return insert_equal(__v);
	}
    }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
      void
      _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
      insert_equal(_II __first, _II __last)
      {
	for ( ; __first != __last; ++__first)
	  insert_equal(*__first);
      }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Cmp, typename _Alloc>
    template<class _II>
    void
    _Rb_tree<_Key,_Val,_KoV,_Cmp,_Alloc>::
    insert_unique(_II __first, _II __last)
    {
      for ( ; __first != __last; ++__first)
	insert_unique(*__first);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline void
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(iterator __position)
    {
      _Link_type __y =
	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase(__position._M_node,
							     this->_M_impl._M_header));
      destroy_node(__y);
      --_M_impl._M_node_count;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::erase(const _Key& __x)
    {
      pair<iterator,iterator> __p = equal_range(__x);
      size_type __n = std::distance(__p.first, __p.second);
      erase(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    _Rb_tree<_Key,_Val,_KoV,_Compare,_Alloc>::
    _M_copy(_Const_Link_type __x, _Link_type __p)
    {
      // Structural copy.  __x and __p must be non-null.
      _Link_type __top = _M_clone_node(__x);
      __top->_M_parent = __p;

      try
	{
	  if (__x->_M_right)
	    __top->_M_right = _M_copy(_S_right(__x), __top);
	  __p = __top;
	  __x = _S_left(__x);

	  while (__x != 0)
	    {
	      _Link_type __y = _M_clone_node(__x);
	      __p->_M_left = __y;
	      __y->_M_parent = __p;
	      if (__x->_M_right)
		__y->_M_right = _M_copy(_S_right(__x), __y);
	      __p = __y;
	      __x = _S_left(__x);
	    }
	}
      catch(...)
	{
	  _M_erase(__top);
	  __throw_exception_again;
	}
      return __top;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::_M_erase(_Link_type __x)
    {
      // Erase without rebalancing.
      while (__x != 0)
	{
	  _M_erase(_S_right(__x));
	  _Link_type __y = _S_left(__x);
	  destroy_node(__x);
	  __x = __y;
	}
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    erase(iterator __first, iterator __last)
    {
      if (__first == begin() && __last == end())
	clear();
      else
	while (__first != __last) erase(__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    void
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    erase(const _Key* __first, const _Key* __last)
    {
      while (__first != __last)
	erase(*__first++);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::find(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	if (!_M_impl._M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      iterator __j = iterator(__y);
      return (__j == end() 
	  || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    find(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.

     while (__x != 0)
       {
	 if (!_M_impl._M_key_compare(_S_key(__x), __k))
	   __y = __x, __x = _S_left(__x);
	 else
	   __x = _S_right(__x);
       }
     const_iterator __j = const_iterator(__y);
     return (__j == end() 
	  || _M_impl._M_key_compare(__k, _S_key(__j._M_node))) ? end() : __j;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::size_type
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    count(const _Key& __k) const
    {
      pair<const_iterator, const_iterator> __p = equal_range(__k);
      const size_type __n = std::distance(__p.first, __p.second);
      return __n;
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    lower_bound(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	if (!_M_impl._M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    lower_bound(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is not less than __k.

      while (__x != 0)
	if (!_M_impl._M_key_compare(_S_key(__x), __k))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    upper_bound(const _Key& __k)
    {
      _Link_type __x = _M_begin(); // Current node.
      _Link_type __y = _M_end(); // Last node which is greater than __k.

      while (__x != 0)
	if (_M_impl._M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::const_iterator
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    upper_bound(const _Key& __k) const
    {
      _Const_Link_type __x = _M_begin(); // Current node.
      _Const_Link_type __y = _M_end(); // Last node which is greater than __k.

      while (__x != 0)
	if (_M_impl._M_key_compare(__k, _S_key(__x)))
	  __y = __x, __x = _S_left(__x);
	else
	  __x = _S_right(__x);

      return const_iterator(__y);
    }

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    inline
    pair<typename _Rb_tree<_Key,_Val,_KeyOfValue,
			   _Compare,_Alloc>::iterator,
	 typename _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::iterator>
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::
    equal_range(const _Key& __k)
    { return pair<iterator, iterator>(lower_bound(__k), upper_bound(__k)); }

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
    inline
    pair<typename _Rb_tree<_Key, _Val, _KoV,
			   _Compare, _Alloc>::const_iterator,
	 typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::const_iterator>
    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    equal_range(const _Key& __k) const
    { return pair<const_iterator, const_iterator>(lower_bound(__k),
						  upper_bound(__k)); }

  unsigned int
  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
                       const _Rb_tree_node_base* __root);

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    bool
    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
    {
      if (_M_impl._M_node_count == 0 || begin() == end())
	return _M_impl._M_node_count == 0 && begin() == end()
	       && this->_M_impl._M_header._M_left == _M_end()
	       && this->_M_impl._M_header._M_right == _M_end();

      unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
      for (const_iterator __it = begin(); __it != end(); ++__it)
	{
	  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
	  _Const_Link_type __L = _S_left(__x);
	  _Const_Link_type __R = _S_right(__x);

	  if (__x->_M_color == _S_red)
	    if ((__L && __L->_M_color == _S_red)
		|| (__R && __R->_M_color == _S_red))
	      return false;

	  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
	    return false;
	  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
	    return false;

	  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
	    return false;
	}

      if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
	return false;
      if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
	return false;
      return true;
    }
} // namespace std

#endif