Lines Matching refs:__x
74 // Returns: true if __x is a left child of its parent, else false
75 // Precondition: __x != nullptr.
79 __tree_is_left_child(_NodePtr __x) _NOEXCEPT
81 return __x == __x->__parent_->__left_;
84 // Determines if the subtree rooted at __x is a proper red black subtree. If
85 // __x is a proper subtree, returns the black height (null counts as 1). If
86 // __x is an improper subtree, returns 0.
89 __tree_sub_invariant(_NodePtr __x)
91 if (__x == nullptr)
94 // check __x->__left_ consistency
95 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
97 // check __x->__right_ consistency
98 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
100 // check __x->__left_ != __x->__right_ unless both are nullptr
101 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
104 if (!__x->__is_black_)
106 if (__x->__left_ && !__x->__left_->__is_black_)
108 if (__x->__right_ && !__x->__right_->__is_black_)
111 unsigned __h = __tree_sub_invariant(__x->__left_);
114 if (__h != __tree_sub_invariant(__x->__right_))
116 return __h + __x->__is_black_; // return black height of this node
128 // check __x->__parent_ consistency
140 // Returns: pointer to the left-most node under __x.
141 // Precondition: __x != nullptr.
145 __tree_min(_NodePtr __x) _NOEXCEPT
147 while (__x->__left_ != nullptr)
148 __x = __x->__left_;
149 return __x;
152 // Returns: pointer to the right-most node under __x.
153 // Precondition: __x != nullptr.
157 __tree_max(_NodePtr __x) _NOEXCEPT
159 while (__x->__right_ != nullptr)
160 __x = __x->__right_;
161 return __x;
164 // Returns: pointer to the next in-order node after __x.
165 // Precondition: __x != nullptr.
168 __tree_next(_NodePtr __x) _NOEXCEPT
170 if (__x->__right_ != nullptr)
171 return __tree_min(__x->__right_);
172 while (!__tree_is_left_child(__x))
173 __x = __x->__parent_unsafe();
174 return __x->__parent_unsafe();
180 __tree_next_iter(_NodePtr __x) _NOEXCEPT
182 if (__x->__right_ != nullptr)
183 return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
184 while (!__tree_is_left_child(__x))
185 __x = __x->__parent_unsafe();
186 return static_cast<_EndNodePtr>(__x->__parent_);
189 // Returns: pointer to the previous in-order node before __x.
190 // Precondition: __x != nullptr.
191 // Note: __x may be the end node.
195 __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT
197 if (__x->__left_ != nullptr)
198 return __tree_max(__x->__left_);
199 _NodePtr __xx = static_cast<_NodePtr>(__x);
206 // Precondition: __x != nullptr.
209 __tree_leaf(_NodePtr __x) _NOEXCEPT
213 if (__x->__left_ != nullptr)
215 __x = __x->__left_;
218 if (__x->__right_ != nullptr)
220 __x = __x->__right_;
225 return __x;
228 // Effects: Makes __x->__right_ the subtree root with __x as its left child
230 // Precondition: __x->__right_ != nullptr
233 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
235 _NodePtr __y = __x->__right_;
236 __x->__right_ = __y->__left_;
237 if (__x->__right_ != nullptr)
238 __x->__right_->__set_parent(__x);
239 __y->__parent_ = __x->__parent_;
240 if (__tree_is_left_child(__x))
241 __x->__parent_->__left_ = __y;
243 __x->__parent_unsafe()->__right_ = __y;
244 __y->__left_ = __x;
245 __x->__set_parent(__y);
248 // Effects: Makes __x->__left_ the subtree root with __x as its right child
250 // Precondition: __x->__left_ != nullptr
253 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
255 _NodePtr __y = __x->__left_;
256 __x->__left_ = __y->__right_;
257 if (__x->__left_ != nullptr)
258 __x->__left_->__set_parent(__x);
259 __y->__parent_ = __x->__parent_;
260 if (__tree_is_left_child(__x))
261 __x->__parent_->__left_ = __y;
263 __x->__parent_unsafe()->__right_ = __y;
264 __y->__right_ = __x;
265 __x->__set_parent(__y);
268 // Effects: Rebalances __root after attaching __x to a leaf.
269 // Precondition: __root != nulptr && __x != nullptr.
270 // __x has no children.
271 // __x == __root or == a direct or indirect child of __root.
272 // If __x were to be unlinked from __root (setting __root to
273 // nullptr if __root == __x), __tree_invariant(__root) == true.
278 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
280 __x->__is_black_ = __x == __root;
281 while (__x != __root && !__x->__parent_unsafe()->__is_black_)
283 // __x->__parent_ != __root because __x->__parent_->__is_black == false
284 if (__tree_is_left_child(__x->__parent_unsafe()))
286 _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
289 __x = __x->__parent_unsafe();
290 __x->__is_black_ = true;
291 __x = __x->__parent_unsafe();
292 __x->__is_black_ = __x == __root;
297 if (!__tree_is_left_child(__x))
299 __x = __x->__parent_unsafe();
300 __tree_left_rotate(__x);
302 __x = __x->__parent_unsafe();
303 __x->__is_black_ = true;
304 __x = __x->__parent_unsafe();
305 __x->__is_black_ = false;
306 __tree_right_rotate(__x);
312 _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
315 __x = __x->__parent_unsafe();
316 __x->__is_black_ = true;
317 __x = __x->__parent_unsafe();
318 __x->__is_black_ = __x == __root;
323 if (__tree_is_left_child(__x))
325 __x = __x->__parent_unsafe();
326 __tree_right_rotate(__x);
328 __x = __x->__parent_unsafe();
329 __x->__is_black_ = true;
330 __x = __x->__parent_unsafe();
331 __x->__is_black_ = false;
332 __tree_left_rotate(__x);
356 // __x is __y's possibly null single child
357 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
358 // __w is __x's possibly null uncle (will become __x's sibling)
360 // link __x to __y's parent, and find __w
361 if (__x != nullptr)
362 __x->__parent_ = __y->__parent_;
365 __y->__parent_->__left_ = __x;
369 __root = __x; // __w == nullptr
373 __y->__parent_unsafe()->__right_ = __x;
379 // but copy __z's color. This does not impact __x or __w.
382 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
402 // __x has an implicit black color (transferred from the removed __y)
404 // If __x is __root (in which case it can't be null), it is supposed
407 // If __x is red (in which case it can't be null), then it can absorb
409 // Since __y was black and only had one child (which __x points to), __x
412 // if (__x == __root || __x != nullptr && !__x->__is_black_)
413 if (__x != nullptr)
414 __x->__is_black_ = true;
417 // Else __x isn't root, and is "doubly black", even though it may
419 // see a black height >= 2 on the __x side and a black height
431 // __x is still valid
443 __x = __w->__parent_unsafe();
444 // __x can no longer be null
445 if (__x == __root || !__x->__is_black_)
447 __x->__is_black_ = true;
451 __w = __tree_is_left_child(__x) ?
452 __x->__parent_unsafe()->__right_ :
453 __x->__parent_->__left_;
483 // __x is still valid
495 __x = __w->__parent_unsafe();
496 // __x can no longer be null
497 if (!__x->__is_black_ || __x == __root)
499 __x->__is_black_ = true;
503 __w = __tree_is_left_child(__x) ?
504 __x->__parent_unsafe()->__right_ :
505 __x->__parent_->__left_;
860 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
861 {return __x.__ptr_ == __y.__ptr_;}
863 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
864 {return !(__x == __y);}
943 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
944 {return __x.__ptr_ == __y.__ptr_;}
946 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
947 {return !(__x == __y);}
1161 pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1162 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1185 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1186 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1192 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1193 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1199 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1200 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1205 iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1206 return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1230 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1231 return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1237 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1238 return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x)).first;
1244 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1245 return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x)).first;
2735 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2737 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2739 __x.swap(__y);