Lines Matching defs:__x
63 _Rb_tree_increment(_Rb_tree_node_base* __x)
65 if (__x->_M_right != 0)
67 __x = __x->_M_right;
68 while (__x->_M_left != 0)
69 __x = __x->_M_left;
73 _Rb_tree_node_base* __y = __x->_M_parent;
74 while (__x == __y->_M_right)
76 __x = __y;
79 if (__x->_M_right != __y)
80 __x = __y;
82 return __x;
86 _Rb_tree_increment(const _Rb_tree_node_base* __x)
88 return _Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x));
92 _Rb_tree_decrement(_Rb_tree_node_base* __x)
94 if (__x->_M_color == _S_red
95 && __x->_M_parent->_M_parent == __x)
96 __x = __x->_M_right;
97 else if (__x->_M_left != 0)
99 _Rb_tree_node_base* __y = __x->_M_left;
102 __x = __y;
106 _Rb_tree_node_base* __y = __x->_M_parent;
107 while (__x == __y->_M_left)
109 __x = __y;
112 __x = __y;
114 return __x;
118 _Rb_tree_decrement(const _Rb_tree_node_base* __x)
120 return _Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x));
124 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x,
127 _Rb_tree_node_base* const __y = __x->_M_right;
129 __x->_M_right = __y->_M_left;
131 __y->_M_left->_M_parent = __x;
132 __y->_M_parent = __x->_M_parent;
134 if (__x == __root)
136 else if (__x == __x->_M_parent->_M_left)
137 __x->_M_parent->_M_left = __y;
139 __x->_M_parent->_M_right = __y;
140 __y->_M_left = __x;
141 __x->_M_parent = __y;
145 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x,
148 _Rb_tree_node_base* const __y = __x->_M_left;
150 __x->_M_left = __y->_M_right;
152 __y->_M_right->_M_parent = __x;
153 __y->_M_parent = __x->_M_parent;
155 if (__x == __root)
157 else if (__x == __x->_M_parent->_M_right)
158 __x->_M_parent->_M_right = __y;
160 __x->_M_parent->_M_left = __y;
161 __y->_M_right = __x;
162 __x->_M_parent = __y;
167 _Rb_tree_node_base* __x,
174 __x->_M_parent = __p;
175 __x->_M_left = 0;
176 __x->_M_right = 0;
177 __x->_M_color = _S_red;
185 __p->_M_left = __x; // also makes leftmost = __x when __p == &__header
189 __header._M_parent = __x;
190 __header._M_right = __x;
193 __header._M_left = __x; // maintain leftmost pointing to min node
197 __p->_M_right = __x;
200 __header._M_right = __x; // maintain rightmost pointing to max node
203 while (__x != __root
204 && __x->_M_parent->_M_color == _S_red)
206 _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent;
208 if (__x->_M_parent == __xpp->_M_left)
213 __x->_M_parent->_M_color = _S_black;
216 __x = __xpp;
220 if (__x == __x->_M_parent->_M_right)
222 __x = __x->_M_parent;
223 _Rb_tree_rotate_left(__x, __root);
225 __x->_M_parent->_M_color = _S_black;
235 __x->_M_parent->_M_color = _S_black;
238 __x = __xpp;
242 if (__x == __x->_M_parent->_M_left)
244 __x = __x->_M_parent;
245 _Rb_tree_rotate_right(__x, __root);
247 __x->_M_parent->_M_color = _S_black;
264 _Rb_tree_node_base* __x = 0;
268 __x = __y->_M_right; // __x might be null.
271 __x = __y->_M_left; // __x is not null.
275 __y = __y->_M_right; // __z's successor. __x might be null.
278 __x = __y->_M_right;
288 if (__x) __x->_M_parent = __y->_M_parent;
289 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left
309 if (__x)
310 __x->_M_parent = __y->_M_parent;
312 __root = __x;
315 __z->_M_parent->_M_left = __x;
317 __z->_M_parent->_M_right = __x;
323 __leftmost = _Rb_tree_node_base::_S_minimum(__x);
328 else // __x == __z->_M_left
329 __rightmost = _Rb_tree_node_base::_S_maximum(__x);
333 while (__x != __root && (__x == 0 || __x->_M_color == _S_black))
334 if (__x == __x_parent->_M_left)
350 __x = __x_parent;
388 __x = __x_parent;
408 if (__x) __x->_M_color = _S_black;