p9rs7xtfl
/
p3elvfktj
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
Branches Tags
${ item.name }
Create tag ${ searchTerm }
Create branch ${ searchTerm }
from 'master'
${ noResults }
p3elvfktj/AES/include/rw/_tree.cc

547 lines
19 KiB
Raw Permalink Blame History

/***************************************************************************
*
* _tree.cc - Non-inline tree definitions for the Standard Library
*
* $Id: _tree.cc 172106 2011-11-02 17:04:12Z statham $
*
***************************************************************************
*
* Copyright (c) 1994
* Hewlett-Packard Company
*
* Permission to use, copy, modify, distribute and sell this software
* and its documentation for any purpose is hereby granted without fee,
* provided that the above copyright notice appear in all copies and
* that both that copyright notice and this permission notice appear
* in supporting documentation. Hewlett-Packard Company makes no
* representations about the suitability of this software for any
* purpose. It is provided "as is" without express or implied warranty.
*
***************************************************************************
*
* Copyright (c) 1994-2001 Rogue Wave Software, Inc. All Rights Reserved.
*
* This computer software is owned by Rogue Wave Software, Inc. and is
* protected by U.S. copyright laws and other laws and by international
* treaties. This computer software is furnished by Rogue Wave Software,
* Inc. pursuant to a written license agreement and may be used, copied,
* transmitted, and stored only in accordance with the terms of such
* license and with the inclusion of the above copyright notice. This
* computer software or any other copies thereof may not be provided or
* otherwise made available to any other person.
*
* U.S. Government Restricted Rights. This computer software is provided
* with Restricted Rights. Use, duplication, or disclosure by the
* Government is subject to restrictions as set forth in subparagraph (c)
* (1) (ii) of The Rights in Technical Data and Computer Software clause
* at DFARS 252.227-7013 or subparagraphs (c) (1) and (2) of the
* Commercial Computer Software--Restricted Rights at 48 CFR 52.227-19,
* as applicable. Manufacturer is Rogue Wave Software, Inc., 5500
* Flatiron Parkway, Boulder, Colorado 80301 USA.
*
**************************************************************************/
// for convenience
#define _ITER_NODE(it) (_ITER_BASE (it)._C_node)
_RWSTD_NAMESPACE_BEGIN (__rw)
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_deallocate_buffers ()
{
while ((void*)_C_buf_list) {
_C_buf_ptr_t __tmp = _C_buf_list;
_C_buf_list = (_C_buf_ptr_t)(_C_buf_list->_C_next_buffer);
_C_node_alloc_t(*this).deallocate(__tmp->_C_buffer,__tmp->size);
_C_buf_alloc_t(*this).deallocate(__tmp,1);
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>&
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
operator= (const __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>& __x)
{
if (!(this == &__x)) {
erase(begin(), end());
_C_root() = _C_copy(__x._C_root(), _C_header);
if (!(void*)_C_root()) {
_C_leftmost() = _C_header; _C_rightmost() = _C_header;
}
else {
_C_leftmost() = _C_node_t::_C_minimum(_C_root());
_C_rightmost() = _C_node_t::_C_maximum(_C_root());
}
_C_node_count = __x._C_node_count;
}
return *this;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_insert (_C_link_t __x, _C_link_t __y, const _Val& __v)
{
_C_link_t __z = _C_get_node(__v);
++_C_node_count;
if ( __y == _C_header || (void*)__x
|| _C_key_comp(_KeyOf()(__v), __y->_C_key ())) {
// Also makes _C_leftmost() = `z' when `y' == _C_header.
__y->_C_left() = __z;
if (__y == _C_header) {
_C_root() = __z; _C_rightmost() = __z;
}
else if (__y == _C_leftmost())
_C_leftmost() = __z; // Maintain _C_leftmost() pointing to minimum node.
}
else {
__y->_C_right() = __z;
if (__y == _C_rightmost())
_C_rightmost() = __z; // Maintain _C_rightmost() pointing to maximum node.
}
__z->_C_parent() = __y;
__x = __z; // Recolor and rebalance the tree.
while (__x != _C_root() && __x->_C_parent()->_C_color() == _C_node_t::_C_red) {
if (__x->_C_parent() == __x->_C_parent()->_C_parent()->_C_left()) {
__y = __x->_C_parent()->_C_parent()->_C_right();
if ((void*)__y && __y->_C_color() == _C_node_t::_C_red) {
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
__y->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent()->_C_parent();
}
else {
if (__x == __x->_C_parent()->_C_right()) {
__x = __x->_C_parent();
__rotate_left(__x);
}
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
__rotate_right(__x->_C_parent()->_C_parent());
}
}
else {
__y = __x->_C_parent()->_C_parent()->_C_left();
if ((void*)__y && __y->_C_color() == _C_node_t::_C_red) {
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
__y->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent()->_C_parent();
}
else {
if (__x == __x->_C_parent()->_C_left()) {
__x = __x->_C_parent();
__rotate_right(__x);
}
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_parent()->_C_color() = _C_node_t::_C_red;
__rotate_left(__x->_C_parent()->_C_parent());
}
}
}
_C_root()->_C_color() = _C_node_t::_C_black;
return _C_make_iter (__z);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_STD::pair<_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator,
bool>
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (const _Val& __v)
{
_C_link_t __y = _C_header;
_C_link_t __x = _C_root();
bool _RWSTD_COMP = true;
while ((void*)__x) {
__y = __x;
_RWSTD_COMP = _C_key_comp(_KeyOf()(__v), __x->_C_key());
__x = _RWSTD_COMP ? __x->_C_left() : __x->_C_right();
}
if (_C_insert_always) {
return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
}
iterator __j = _C_make_iter(__y);
if (_RWSTD_COMP) {
if (__j == begin()) {
return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
}
else
--__j;
}
if (_C_key_comp (_ITER_NODE (__j)->_C_key (), _KeyOf ()(__v))) {
return _STD::pair<iterator, bool>(_C_insert(__x, __y, __v), true);
}
return _STD::pair<iterator, bool>(__j, false);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::insert (iterator __it,
const _Val& __v)
{
_RWSTD_ASSERT_RANGE (begin (), __it);
if (__it == begin ()) {
if ( size() > 0
&& _C_key_comp (_KeyOf()(__v), _ITER_NODE (__it)->_C_key ()))
return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
return insert(__v).first;
}
else if (__it == end()) {
if (_C_key_comp(_C_rightmost()->_C_key(), _KeyOf()(__v)))
return _C_insert(0, _C_rightmost(), __v);
else
return insert(__v).first;
}
else {
iterator __prev = --__it;
if ( _C_key_comp (_ITER_NODE (__prev)->_C_key (), _KeyOf ()(__v))
&& _C_key_comp (_KeyOf()(__v), _ITER_NODE (__it)->_C_key ())) {
if (!(void*)_ITER_NODE (__prev)->_C_right ())
return _C_insert(0, _ITER_NODE (__prev), __v);
return _C_insert (_ITER_NODE (__it), _ITER_NODE (__it), __v);
}
return insert (__v).first;
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator __it)
{
_RWSTD_ASSERT_RANGE (begin (), __it);
iterator __tmp = __it;
if (__tmp == end())
// Attempting to erase an empty container.
return end ();
else
// Retain 'next' __it for return.
++__tmp;
_C_link_t __z (_ITER_NODE (__it));
_C_link_t __y = __z;
_C_link_t __x;
bool __deleted = false;
if (!(void*)__y->_C_left()) {
if (!(void*)__y->_C_right()) {
__x = __y->_C_parent();
_C_erase_leaf(__y);
__deleted = true;
}
else
__x = __y->_C_right();
}
else {
if (!(void*)__y->_C_right())
__x = __y->_C_left();
else {
__y = __y->_C_right();
while ((void*)__y->_C_left())
__y = __y->_C_left();
__x = __y->_C_right();
}
}
if (!__deleted && __y != __z) {
//
// Relink __y in place of __z.
//
__z->_C_left()->_C_parent() = __y;
__y->_C_left() = __z->_C_left();
if (__y != __z->_C_right()) {
if ((void*)__x)
__x->_C_parent() = __y->_C_parent();
__y->_C_parent()->_C_left() = __x; // __y must be a left child.
__y->_C_right() = __z->_C_right();
__z->_C_right()->_C_parent() = __y;
}
else if ((void*)__x)
__x->_C_parent() = __y;
if (_C_root() == __z)
_C_root() = __y;
else if (__z->_C_parent()->_C_left() == __z)
__z->_C_parent()->_C_left() = __y;
else
__z->_C_parent()->_C_right() = __y;
__y->_C_parent() = __z->_C_parent();
if (!(void*)__x)
__x = __y; // Don't want to start balancing with nil
_STD::swap(__y->_C_color(), __z->_C_color());
__y = __z; // __y points to node to be actually deleted.
}
else if (!__deleted) {
//
// __y == __z
//
__x->_C_parent() = __y->_C_parent();
if (_C_root() == __z)
_C_root() = __x;
else {
if (__z->_C_parent()->_C_left() == __z)
__z->_C_parent()->_C_left() = __x;
else
__z->_C_parent()->_C_right() = __x;
}
if (_C_leftmost() == __z) {
if (!(void*)__z->_C_right()) // __z->_C_left() must be NIL also.
_C_leftmost() = __z->_C_parent();
else
_C_leftmost() = _C_node_t::_C_minimum(__x);
}
if (_C_rightmost() == __z) {
if (!(void*)__z->_C_left()) // __z->_C_right() must be NIL also.
_C_rightmost() = __z->_C_parent();
else
_C_rightmost() = _C_node_t::_C_maximum(__x);
}
}
if (__x != _C_header && __y->_C_color() != _C_node_t::_C_red) {
while (__x != _C_root() && __x->_C_color() == _C_node_t::_C_black) {
if (__x == __x->_C_parent()->_C_left()) {
_C_link_t __w = __x->_C_parent()->_C_right();
if (!(void*)__w) {
__x->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent();
}
else {
if (__w->_C_color() == _C_node_t::_C_red) {
__w->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_color() = _C_node_t::_C_red;
__rotate_left(__x->_C_parent());
__w = __x->_C_parent()->_C_right();
}
if (!(void*)__w) {
__x->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent();
}
else if (( !(void*)__w->_C_left()
|| __w->_C_left()->_C_color() == _C_node_t::_C_black) &&
( !(void*)__w->_C_right()
|| __w->_C_right()->_C_color() == _C_node_t::_C_black)) {
__w->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent();
}
else {
if ( !(void*)__w->_C_right()
|| __w->_C_right()->_C_color() == _C_node_t::_C_black) {
if ((void*)__w->_C_left())
__w->_C_left()->_C_color() = _C_node_t::_C_black;
__w->_C_color() = _C_node_t::_C_red;
__rotate_right(__w);
__w = __x->_C_parent()->_C_right();
}
if ((void*)__w) {
__w->_C_color() = __x->_C_parent()->_C_color();
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
if ((void*)__w->_C_right())
__w->_C_right()->_C_color() = _C_node_t::_C_black;
__rotate_left(__x->_C_parent());
}
break;
}
}
}
else {
//
// Same as then clause with "right" and "left" exchanged.
//
_C_link_t __w = __x->_C_parent()->_C_left();
if (!(void*)__w) {
__x->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent();
}
else {
if (__w->_C_color() == _C_node_t::_C_red) {
__w->_C_color() = _C_node_t::_C_black;
__x->_C_parent()->_C_color() = _C_node_t::_C_red;
__rotate_right(__x->_C_parent());
__w = __x->_C_parent()->_C_left();
}
if (!(void*)__w) {
__x->_C_color() = _C_node_t::_C_red;
__x = __x->_C_parent();
}
else if ( ( !(void*)__w->_C_right()
|| __w->_C_right()->_C_color() == _C_node_t::_C_black)
&& ( !(void*)__w->_C_left()
|| __w->_C_left()->_C_color() == _C_node_t::_C_black)) {
__w->_C_color() = _C_node_t::_C_red; __x = __x->_C_parent();
}
else {
if ( !(void*)__w->_C_left()
|| __w->_C_left()->_C_color() == _C_node_t::_C_black) {
if ((void*)__w->_C_right())
__w->_C_right()->_C_color() = _C_node_t::_C_black;
__w->_C_color() = _C_node_t::_C_red;
__rotate_left(__w);
__w = __x->_C_parent()->_C_left();
}
if ((void*)__w) {
__w->_C_color() = __x->_C_parent()->_C_color();
__x->_C_parent()->_C_color() = _C_node_t::_C_black;
if ((void*)__w->_C_left())
__w->_C_left()->_C_color() = _C_node_t::_C_black;
__rotate_right(__x->_C_parent());
}
break;
}
}
}
}
__x->_C_color() = _C_node_t::_C_black;
}
_C_put_node(__y);
--_C_node_count;
return __tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::size_type
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (const _Key& __x)
{
_STD::pair<iterator, iterator> __p = equal_range(__x);
size_type __n = _DISTANCE(__p.first, __p.second, size_type);
erase(__p.first, __p.second);
return __n;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_link_t
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::
_C_copy (_C_link_t __x, _C_link_t __p)
{
// Structural copy.
_C_link_t __res = __x;
while ((void*)__x) {
_C_link_t __y = _C_get_node(__x->_C_value());
if (__res == __x)
__res = __y; // Save for return value.
__p->_C_left() = __y;
__y->_C_parent() = __p;
__y->_C_color() = __x->_C_color();
__y->_C_right() = _C_copy(__x->_C_right(), __y);
__p = __y;
__x = __x->_C_left();
}
__p->_C_left() = 0;
return __res;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
void __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::_C_erase (_C_link_t __x)
{
//
// Erase without rebalancing.
//
while ((void*)__x) {
_C_erase(__x->_C_right());
_C_link_t __y = __x->_C_left();
_C_put_node(__x);
__x = __y;
}
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::erase (iterator __first,
iterator __last)
{
_RWSTD_ASSERT_RANGE (begin (), __first);
_RWSTD_ASSERT_RANGE (__first, __last);
iterator __tmp = end();
if (__first == begin() && __last == end() && _C_node_count != 0) {
_C_erase(_C_root());
_C_leftmost() = _C_header;
_C_root() = 0;
_C_rightmost() = _C_header;
_C_node_count = 0;
__tmp = end();
} else {
while (__first != __last)
__tmp = erase(__first++);
}
return __tmp;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::find (const _Key& __k)
{
_C_link_t __y = _C_header; // __last node that is not less than __k.
_C_link_t __x = _C_root(); // Current node.
while ((void*)__x) {
if (!_C_key_comp(__x->_C_key(), __k))
__y = __x, __x = __x->_C_left();
else
__x = __x->_C_right();
}
iterator __j = _C_make_iter (__y);
return ( __j == end()
|| _C_key_comp (__k, _ITER_NODE (__j)->_C_key ())) ? end () : __j;
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::lower_bound (const _Key& __k)
{
_C_link_t __y = _C_header; // __last node that is not less than __k.
_C_link_t __x = _C_root(); // Current node.
while ((void*)__x) {
if (!_C_key_comp(__x->_C_key(), __k))
__y = __x, __x = __x->_C_left();
else
__x = __x->_C_right();
}
return _C_make_iter (__y);
}
template <class _Key, class _Val, class _KeyOf, class _Comp, class _Alloc>
_TYPENAME __rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::iterator
__rb_tree<_Key, _Val, _KeyOf, _Comp, _Alloc>::upper_bound (const _Key& __k)
{
_C_link_t __y = _C_header; // __last node that is greater than __k.
_C_link_t __x = _C_root(); // Current node.
while ((void*)__x) {
if (_C_key_comp(__k,__x->_C_key()))
__y = __x, __x = __x->_C_left();
else
__x = __x->_C_right();
}
return _C_make_iter (__y);
}
_RWSTD_NAMESPACE_END // __rw
#undef _ITER_NODE
Reference in new issue View Git Blame Copy Permalink