Lines Matching defs:__x
60 _Rb_global<_Dummy>::_Rotate_left(_Rb_tree_node_base* __x,
62 _Rb_tree_node_base* __y = __x->_M_right;
63 __x->_M_right = __y->_M_left;
65 __y->_M_left->_M_parent = __x;
66 __y->_M_parent = __x->_M_parent;
68 if (__x == __root)
70 else if (__x == __x->_M_parent->_M_left)
71 __x->_M_parent->_M_left = __y;
73 __x->_M_parent->_M_right = __y;
74 __y->_M_left = __x;
75 __x->_M_parent = __y;
79 _Rb_global<_Dummy>::_Rotate_right(_Rb_tree_node_base* __x,
81 _Rb_tree_node_base* __y = __x->_M_left;
82 __x->_M_left = __y->_M_right;
84 __y->_M_right->_M_parent = __x;
85 __y->_M_parent = __x->_M_parent;
87 if (__x == __root)
89 else if (__x == __x->_M_parent->_M_right)
90 __x->_M_parent->_M_right = __y;
92 __x->_M_parent->_M_left = __y;
93 __y->_M_right = __x;
94 __x->_M_parent = __y;
98 _Rb_global<_Dummy>::_Rebalance(_Rb_tree_node_base* __x,
100 __x->_M_color = _S_rb_tree_red;
101 while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) {
102 if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) {
103 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right;
105 __x->_M_parent->_M_color = _S_rb_tree_black;
107 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
108 __x = __x->_M_parent->_M_parent;
111 if (__x == __x->_M_parent->_M_right) {
112 __x = __x->_M_parent;
113 _Rotate_left(__x, __root);
115 __x->_M_parent->_M_color = _S_rb_tree_black;
116 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
117 _Rotate_right(__x->_M_parent->_M_parent, __root);
121 _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left;
123 __x->_M_parent->_M_color = _S_rb_tree_black;
125 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
126 __x = __x->_M_parent->_M_parent;
129 if (__x == __x->_M_parent->_M_left) {
130 __x = __x->_M_parent;
131 _Rotate_right(__x, __root);
133 __x->_M_parent->_M_color = _S_rb_tree_black;
134 __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red;
135 _Rotate_left(__x->_M_parent->_M_parent, __root);
148 _Rb_tree_node_base* __x;
152 __x = __y->_M_right; // __x might be null.
155 __x = __y->_M_left; // __x is not null.
157 __y = _Rb_tree_node_base::_S_minimum(__y->_M_right); // __z's successor. __x might be null.
158 __x = __y->_M_right;
167 if (__x) __x->_M_parent = __y->_M_parent;
168 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
187 if (__x) __x->_M_parent = __y->_M_parent;
189 __root = __x;
192 __z->_M_parent->_M_left = __x;
194 __z->_M_parent->_M_right = __x;
202 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
208 else // __x == __z->_M_left
209 __rightmost = _Rb_tree_node_base::_S_maximum(__x);
214 while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
215 if (__x == __x_parent->_M_left) {
227 __x = __x_parent;
255 __x = __x_parent;
272 if (__x) __x->_M_color = _S_rb_tree_black;
322 const _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>& __x) {
323 if (this != &__x) {
327 _M_key_compare = __x._M_key_compare;
328 if (__x._M_root() == 0) {
334 _M_root() = _M_copy(__x._M_root(), &this->_M_header._M_data);
337 _M_node_count = __x._M_node_count;
389 _Base_ptr __x = _M_root();
390 while (__x != 0) {
391 __y = __x;
392 if (_M_key_compare(_KeyOfValue()(__val), _S_key(__x))) {
393 __x = _S_left(__x);
396 __x = _S_right(__x);
398 return _M_insert(__y, __val, __x);
407 _Base_ptr __x = _M_root();
409 while (__x != 0) {
410 __y = __x;
411 __comp = _M_key_compare(_KeyOfValue()(__val), _S_key(__x));
412 __x = __comp ? _S_left(__x) : _S_right(__x);
417 return pair<iterator,bool>(_M_insert(__y, __val, /* __x*/ __y), true);
422 return pair<iterator,bool>(_M_insert(__y, __val, __x), true);
624 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc> ::_M_copy(_Rb_tree_node_base* __x,
626 // structural copy. __x and __p must be non-null.
627 _Base_ptr __top = _M_clone_node(__x);
631 if (_S_right(__x))
632 _S_right(__top) = _M_copy(_S_right(__x), __top);
634 __x = _S_left(__x);
636 while (__x != 0) {
637 _Base_ptr __y = _M_clone_node(__x);
640 if (_S_right(__x))
641 _S_right(__y) = _M_copy(_S_right(__x), __y);
643 __x = _S_left(__x);
655 _Rb_tree<_Key,_Compare,_Value,_KeyOfValue,_Traits,_Alloc>::_M_erase(_Rb_tree_node_base *__x) {
657 while (__x != 0) {
658 _M_erase(_S_right(__x));
659 _Base_ptr __y = _S_left(__x);
660 _STLP_STD::_Destroy(&_S_value(__x));
661 this->_M_header.deallocate(__STATIC_CAST(_Link_type, __x),1);
662 __x = __y;
691 _Base_ptr __x = __it._M_node;
692 _Base_ptr __L = _S_left(__x);
693 _Base_ptr __R = _S_right(__x);
695 if (__x->_M_color == _S_rb_tree_red)
700 if (__L && _M_key_compare(_S_key(__x), _S_key(__L)))
702 if (__R && _M_key_compare(_S_key(__R), _S_key(__x)))
705 if (!__L && !__R && __black_count(__x, _M_root()) != __len)
