Lines Matching refs:__x
68 // Returns: true if __x is a left child of its parent, else false
69 // Precondition: __x != nullptr.
73 __tree_is_left_child(_NodePtr __x) _NOEXCEPT
75 return __x == __x->__parent_->__left_;
78 // Determines if the subtree rooted at __x is a proper red black subtree. If
79 // __x is a proper subtree, returns the black height (null counts as 1). If
80 // __x is an improper subtree, returns 0.
83 __tree_sub_invariant(_NodePtr __x)
85 if (__x == nullptr)
88 // check __x->__left_ consistency
89 if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
91 // check __x->__right_ consistency
92 if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
94 // check __x->__left_ != __x->__right_ unless both are nullptr
95 if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
98 if (!__x->__is_black_)
100 if (__x->__left_ && !__x->__left_->__is_black_)
102 if (__x->__right_ && !__x->__right_->__is_black_)
105 unsigned __h = __tree_sub_invariant(__x->__left_);
108 if (__h != __tree_sub_invariant(__x->__right_))
110 return __h + __x->__is_black_; // return black height of this node
122 // check __x->__parent_ consistency
134 // Returns: pointer to the left-most node under __x.
135 // Precondition: __x != nullptr.
139 __tree_min(_NodePtr __x) _NOEXCEPT
141 while (__x->__left_ != nullptr)
142 __x = __x->__left_;
143 return __x;
146 // Returns: pointer to the right-most node under __x.
147 // Precondition: __x != nullptr.
151 __tree_max(_NodePtr __x) _NOEXCEPT
153 while (__x->__right_ != nullptr)
154 __x = __x->__right_;
155 return __x;
158 // Returns: pointer to the next in-order node after __x.
159 // Precondition: __x != nullptr.
162 __tree_next(_NodePtr __x) _NOEXCEPT
164 if (__x->__right_ != nullptr)
165 return __tree_min(__x->__right_);
166 while (!__tree_is_left_child(__x))
167 __x = __x->__parent_unsafe();
168 return __x->__parent_unsafe();
174 __tree_next_iter(_NodePtr __x) _NOEXCEPT
176 if (__x->__right_ != nullptr)
177 return static_cast<_EndNodePtr>(__tree_min(__x->__right_));
178 while (!__tree_is_left_child(__x))
179 __x = __x->__parent_unsafe();
180 return static_cast<_EndNodePtr>(__x->__parent_);
183 // Returns: pointer to the previous in-order node before __x.
184 // Precondition: __x != nullptr.
185 // Note: __x may be the end node.
189 __tree_prev_iter(_EndNodePtr __x) _NOEXCEPT
191 if (__x->__left_ != nullptr)
192 return __tree_max(__x->__left_);
193 _NodePtr __xx = static_cast<_NodePtr>(__x);
200 // Precondition: __x != nullptr.
203 __tree_leaf(_NodePtr __x) _NOEXCEPT
207 if (__x->__left_ != nullptr)
209 __x = __x->__left_;
212 if (__x->__right_ != nullptr)
214 __x = __x->__right_;
219 return __x;
222 // Effects: Makes __x->__right_ the subtree root with __x as its left child
224 // Precondition: __x->__right_ != nullptr
227 __tree_left_rotate(_NodePtr __x) _NOEXCEPT
229 _NodePtr __y = __x->__right_;
230 __x->__right_ = __y->__left_;
231 if (__x->__right_ != nullptr)
232 __x->__right_->__set_parent(__x);
233 __y->__parent_ = __x->__parent_;
234 if (__tree_is_left_child(__x))
235 __x->__parent_->__left_ = __y;
237 __x->__parent_unsafe()->__right_ = __y;
238 __y->__left_ = __x;
239 __x->__set_parent(__y);
242 // Effects: Makes __x->__left_ the subtree root with __x as its right child
244 // Precondition: __x->__left_ != nullptr
247 __tree_right_rotate(_NodePtr __x) _NOEXCEPT
249 _NodePtr __y = __x->__left_;
250 __x->__left_ = __y->__right_;
251 if (__x->__left_ != nullptr)
252 __x->__left_->__set_parent(__x);
253 __y->__parent_ = __x->__parent_;
254 if (__tree_is_left_child(__x))
255 __x->__parent_->__left_ = __y;
257 __x->__parent_unsafe()->__right_ = __y;
258 __y->__right_ = __x;
259 __x->__set_parent(__y);
262 // Effects: Rebalances __root after attaching __x to a leaf.
263 // Precondition: __root != nulptr && __x != nullptr.
264 // __x has no children.
265 // __x == __root or == a direct or indirect child of __root.
266 // If __x were to be unlinked from __root (setting __root to
267 // nullptr if __root == __x), __tree_invariant(__root) == true.
272 __tree_balance_after_insert(_NodePtr __root, _NodePtr __x) _NOEXCEPT
274 __x->__is_black_ = __x == __root;
275 while (__x != __root && !__x->__parent_unsafe()->__is_black_)
277 // __x->__parent_ != __root because __x->__parent_->__is_black == false
278 if (__tree_is_left_child(__x->__parent_unsafe()))
280 _NodePtr __y = __x->__parent_unsafe()->__parent_unsafe()->__right_;
283 __x = __x->__parent_unsafe();
284 __x->__is_black_ = true;
285 __x = __x->__parent_unsafe();
286 __x->__is_black_ = __x == __root;
291 if (!__tree_is_left_child(__x))
293 __x = __x->__parent_unsafe();
294 __tree_left_rotate(__x);
296 __x = __x->__parent_unsafe();
297 __x->__is_black_ = true;
298 __x = __x->__parent_unsafe();
299 __x->__is_black_ = false;
300 __tree_right_rotate(__x);
306 _NodePtr __y = __x->__parent_unsafe()->__parent_->__left_;
309 __x = __x->__parent_unsafe();
310 __x->__is_black_ = true;
311 __x = __x->__parent_unsafe();
312 __x->__is_black_ = __x == __root;
317 if (__tree_is_left_child(__x))
319 __x = __x->__parent_unsafe();
320 __tree_right_rotate(__x);
322 __x = __x->__parent_unsafe();
323 __x->__is_black_ = true;
324 __x = __x->__parent_unsafe();
325 __x->__is_black_ = false;
326 __tree_left_rotate(__x);
350 // __x is __y's possibly null single child
351 _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_;
352 // __w is __x's possibly null uncle (will become __x's sibling)
354 // link __x to __y's parent, and find __w
355 if (__x != nullptr)
356 __x->__parent_ = __y->__parent_;
359 __y->__parent_->__left_ = __x;
363 __root = __x; // __w == nullptr
367 __y->__parent_unsafe()->__right_ = __x;
373 // but copy __z's color. This does not impact __x or __w.
376 // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr
396 // __x has an implicit black color (transferred from the removed __y)
398 // If __x is __root (in which case it can't be null), it is supposed
401 // If __x is red (in which case it can't be null), then it can absorb
403 // Since __y was black and only had one child (which __x points to), __x
406 // if (__x == __root || __x != nullptr && !__x->__is_black_)
407 if (__x != nullptr)
408 __x->__is_black_ = true;
411 // Else __x isn't root, and is "doubly black", even though it may
413 // see a black height >= 2 on the __x side and a black height
425 // __x is still valid
437 __x = __w->__parent_unsafe();
438 // __x can no longer be null
439 if (__x == __root || !__x->__is_black_)
441 __x->__is_black_ = true;
445 __w = __tree_is_left_child(__x) ?
446 __x->__parent_unsafe()->__right_ :
447 __x->__parent_->__left_;
477 // __x is still valid
489 __x = __w->__parent_unsafe();
490 // __x can no longer be null
491 if (!__x->__is_black_ || __x == __root)
493 __x->__is_black_ = true;
497 __w = __tree_is_left_child(__x) ?
498 __x->__parent_unsafe()->__right_ :
499 __x->__parent_->__left_;
857 bool operator==(const __tree_iterator& __x, const __tree_iterator& __y)
858 {return __x.__ptr_ == __y.__ptr_;}
860 bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y)
861 {return !(__x == __y);}
940 bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
941 {return __x.__ptr_ == __y.__ptr_;}
943 bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y)
944 {return !(__x == __y);}
1162 pair<iterator, bool> __emplace_unique(_Pp&& __x) {
1163 return __emplace_unique_extract_key(_VSTD::forward<_Pp>(__x),
1186 __emplace_unique_extract_key(_Pp&& __x, __extract_key_fail_tag) {
1187 return __emplace_unique_impl(_VSTD::forward<_Pp>(__x));
1193 __emplace_unique_extract_key(_Pp&& __x, __extract_key_self_tag) {
1194 return __emplace_unique_key_args(__x, _VSTD::forward<_Pp>(__x));
1200 __emplace_unique_extract_key(_Pp&& __x, __extract_key_first_tag) {
1201 return __emplace_unique_key_args(__x.first, _VSTD::forward<_Pp>(__x));
1206 iterator __emplace_hint_unique(const_iterator __p, _Pp&& __x) {
1207 return __emplace_hint_unique_extract_key(__p, _VSTD::forward<_Pp>(__x),
1231 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_fail_tag) {
1232 return __emplace_hint_unique_impl(__p, _VSTD::forward<_Pp>(__x));
1238 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_self_tag) {
1239 return __emplace_hint_unique_key_args(__p, __x, _VSTD::forward<_Pp>(__x));
1245 __emplace_hint_unique_extract_key(const_iterator __p, _Pp&& __x, __extract_key_first_tag) {
1246 return __emplace_hint_unique_key_args(__p, __x.first, _VSTD::forward<_Pp>(__x));
2868 swap(__tree<_Tp, _Compare, _Allocator>& __x,
2870 _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y)))
2872 __x.swap(__y);