Lines Matching refs:__x
60 local_Rb_tree_increment(_Rb_tree_node_base* __x) throw () in local_Rb_tree_increment() argument
62 if (__x->_M_right != 0) in local_Rb_tree_increment()
64 __x = __x->_M_right; in local_Rb_tree_increment()
65 while (__x->_M_left != 0) in local_Rb_tree_increment()
66 __x = __x->_M_left; in local_Rb_tree_increment()
70 _Rb_tree_node_base* __y = __x->_M_parent; in local_Rb_tree_increment()
71 while (__x == __y->_M_right) in local_Rb_tree_increment()
73 __x = __y; in local_Rb_tree_increment()
76 if (__x->_M_right != __y) in local_Rb_tree_increment()
77 __x = __y; in local_Rb_tree_increment()
79 return __x; in local_Rb_tree_increment()
83 _Rb_tree_increment(_Rb_tree_node_base* __x) throw () in _Rb_tree_increment() argument
85 return local_Rb_tree_increment(__x); in _Rb_tree_increment()
89 _Rb_tree_increment(const _Rb_tree_node_base* __x) throw () in _Rb_tree_increment() argument
91 return local_Rb_tree_increment(const_cast<_Rb_tree_node_base*>(__x)); in _Rb_tree_increment()
95 local_Rb_tree_decrement(_Rb_tree_node_base* __x) throw () in local_Rb_tree_decrement() argument
97 if (__x->_M_color == _S_red in local_Rb_tree_decrement()
98 && __x->_M_parent->_M_parent == __x) in local_Rb_tree_decrement()
99 __x = __x->_M_right; in local_Rb_tree_decrement()
100 else if (__x->_M_left != 0) in local_Rb_tree_decrement()
102 _Rb_tree_node_base* __y = __x->_M_left; in local_Rb_tree_decrement()
105 __x = __y; in local_Rb_tree_decrement()
109 _Rb_tree_node_base* __y = __x->_M_parent; in local_Rb_tree_decrement()
110 while (__x == __y->_M_left) in local_Rb_tree_decrement()
112 __x = __y; in local_Rb_tree_decrement()
115 __x = __y; in local_Rb_tree_decrement()
117 return __x; in local_Rb_tree_decrement()
121 _Rb_tree_decrement(_Rb_tree_node_base* __x) throw () in _Rb_tree_decrement() argument
123 return local_Rb_tree_decrement(__x); in _Rb_tree_decrement()
127 _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw () in _Rb_tree_decrement() argument
129 return local_Rb_tree_decrement(const_cast<_Rb_tree_node_base*>(__x)); in _Rb_tree_decrement()
133 local_Rb_tree_rotate_left(_Rb_tree_node_base* const __x, in local_Rb_tree_rotate_left() argument
136 _Rb_tree_node_base* const __y = __x->_M_right; in local_Rb_tree_rotate_left()
138 __x->_M_right = __y->_M_left; in local_Rb_tree_rotate_left()
140 __y->_M_left->_M_parent = __x; in local_Rb_tree_rotate_left()
141 __y->_M_parent = __x->_M_parent; in local_Rb_tree_rotate_left()
143 if (__x == __root) in local_Rb_tree_rotate_left()
145 else if (__x == __x->_M_parent->_M_left) in local_Rb_tree_rotate_left()
146 __x->_M_parent->_M_left = __y; in local_Rb_tree_rotate_left()
148 __x->_M_parent->_M_right = __y; in local_Rb_tree_rotate_left()
149 __y->_M_left = __x; in local_Rb_tree_rotate_left()
150 __x->_M_parent = __y; in local_Rb_tree_rotate_left()
158 _Rb_tree_rotate_left(_Rb_tree_node_base* const __x, in _Rb_tree_rotate_left() argument
160 { local_Rb_tree_rotate_left (__x, __root); } in _Rb_tree_rotate_left()
164 local_Rb_tree_rotate_right(_Rb_tree_node_base* const __x, in local_Rb_tree_rotate_right() argument
167 _Rb_tree_node_base* const __y = __x->_M_left; in local_Rb_tree_rotate_right()
169 __x->_M_left = __y->_M_right; in local_Rb_tree_rotate_right()
171 __y->_M_right->_M_parent = __x; in local_Rb_tree_rotate_right()
172 __y->_M_parent = __x->_M_parent; in local_Rb_tree_rotate_right()
174 if (__x == __root) in local_Rb_tree_rotate_right()
176 else if (__x == __x->_M_parent->_M_right) in local_Rb_tree_rotate_right()
177 __x->_M_parent->_M_right = __y; in local_Rb_tree_rotate_right()
179 __x->_M_parent->_M_left = __y; in local_Rb_tree_rotate_right()
180 __y->_M_right = __x; in local_Rb_tree_rotate_right()
181 __x->_M_parent = __y; in local_Rb_tree_rotate_right()
189 _Rb_tree_rotate_right(_Rb_tree_node_base* const __x, in _Rb_tree_rotate_right() argument
191 { local_Rb_tree_rotate_right (__x, __root); } in _Rb_tree_rotate_right()
196 _Rb_tree_node_base* __x, in _Rb_tree_insert_and_rebalance() argument
203 __x->_M_parent = __p; in _Rb_tree_insert_and_rebalance()
204 __x->_M_left = 0; in _Rb_tree_insert_and_rebalance()
205 __x->_M_right = 0; in _Rb_tree_insert_and_rebalance()
206 __x->_M_color = _S_red; in _Rb_tree_insert_and_rebalance()
214 __p->_M_left = __x; // also makes leftmost = __x when __p == &__header in _Rb_tree_insert_and_rebalance()
218 __header._M_parent = __x; in _Rb_tree_insert_and_rebalance()
219 __header._M_right = __x; in _Rb_tree_insert_and_rebalance()
222 __header._M_left = __x; // maintain leftmost pointing to min node in _Rb_tree_insert_and_rebalance()
226 __p->_M_right = __x; in _Rb_tree_insert_and_rebalance()
229 __header._M_right = __x; // maintain rightmost pointing to max node in _Rb_tree_insert_and_rebalance()
232 while (__x != __root in _Rb_tree_insert_and_rebalance()
233 && __x->_M_parent->_M_color == _S_red) in _Rb_tree_insert_and_rebalance()
235 _Rb_tree_node_base* const __xpp = __x->_M_parent->_M_parent; in _Rb_tree_insert_and_rebalance()
237 if (__x->_M_parent == __xpp->_M_left) in _Rb_tree_insert_and_rebalance()
242 __x->_M_parent->_M_color = _S_black; in _Rb_tree_insert_and_rebalance()
245 __x = __xpp; in _Rb_tree_insert_and_rebalance()
249 if (__x == __x->_M_parent->_M_right) in _Rb_tree_insert_and_rebalance()
251 __x = __x->_M_parent; in _Rb_tree_insert_and_rebalance()
252 local_Rb_tree_rotate_left(__x, __root); in _Rb_tree_insert_and_rebalance()
254 __x->_M_parent->_M_color = _S_black; in _Rb_tree_insert_and_rebalance()
264 __x->_M_parent->_M_color = _S_black; in _Rb_tree_insert_and_rebalance()
267 __x = __xpp; in _Rb_tree_insert_and_rebalance()
271 if (__x == __x->_M_parent->_M_left) in _Rb_tree_insert_and_rebalance()
273 __x = __x->_M_parent; in _Rb_tree_insert_and_rebalance()
274 local_Rb_tree_rotate_right(__x, __root); in _Rb_tree_insert_and_rebalance()
276 __x->_M_parent->_M_color = _S_black; in _Rb_tree_insert_and_rebalance()
293 _Rb_tree_node_base* __x = 0; in _Rb_tree_rebalance_for_erase() local
297 __x = __y->_M_right; // __x might be null. in _Rb_tree_rebalance_for_erase()
300 __x = __y->_M_left; // __x is not null. in _Rb_tree_rebalance_for_erase()
307 __x = __y->_M_right; in _Rb_tree_rebalance_for_erase()
317 if (__x) __x->_M_parent = __y->_M_parent; in _Rb_tree_rebalance_for_erase()
318 __y->_M_parent->_M_left = __x; // __y must be a child of _M_left in _Rb_tree_rebalance_for_erase()
338 if (__x) in _Rb_tree_rebalance_for_erase()
339 __x->_M_parent = __y->_M_parent; in _Rb_tree_rebalance_for_erase()
341 __root = __x; in _Rb_tree_rebalance_for_erase()
344 __z->_M_parent->_M_left = __x; in _Rb_tree_rebalance_for_erase()
346 __z->_M_parent->_M_right = __x; in _Rb_tree_rebalance_for_erase()
353 __leftmost = _Rb_tree_node_base::_S_minimum(__x); in _Rb_tree_rebalance_for_erase()
361 __rightmost = _Rb_tree_node_base::_S_maximum(__x); in _Rb_tree_rebalance_for_erase()
366 while (__x != __root && (__x == 0 || __x->_M_color == _S_black)) in _Rb_tree_rebalance_for_erase()
367 if (__x == __x_parent->_M_left) in _Rb_tree_rebalance_for_erase()
383 __x = __x_parent; in _Rb_tree_rebalance_for_erase()
421 __x = __x_parent; in _Rb_tree_rebalance_for_erase()
441 if (__x) __x->_M_color = _S_black; in _Rb_tree_rebalance_for_erase()