diff options
author | mikari <mikari@yandex-team.ru> | 2022-02-10 16:48:47 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:48:47 +0300 |
commit | f821ddfc9200113ec259d8d35b7cf3833372abc9 (patch) | |
tree | 5d5cb817648f650d76cf1076100726fd9b8448e8 /library/cpp/containers/intrusive_rb_tree/rb_tree.h | |
parent | 2e0ed5ad2d70bf924ccd3cbbfab508784ab36325 (diff) | |
download | ydb-f821ddfc9200113ec259d8d35b7cf3833372abc9.tar.gz |
Restoring authorship annotation for <mikari@yandex-team.ru>. Commit 2 of 2.
Diffstat (limited to 'library/cpp/containers/intrusive_rb_tree/rb_tree.h')
-rw-r--r-- | library/cpp/containers/intrusive_rb_tree/rb_tree.h | 50 |
1 files changed, 25 insertions, 25 deletions
diff --git a/library/cpp/containers/intrusive_rb_tree/rb_tree.h b/library/cpp/containers/intrusive_rb_tree/rb_tree.h index 4118d01a25..0259452a14 100644 --- a/library/cpp/containers/intrusive_rb_tree/rb_tree.h +++ b/library/cpp/containers/intrusive_rb_tree/rb_tree.h @@ -67,8 +67,8 @@ public: static void Rebalance(TBasePtr x, TBasePtr& root); static TBasePtr RebalanceForErase(TBasePtr z, TBasePtr& root, TBasePtr& leftmost, TBasePtr& rightmost); - static void DecrementChildrenUntilRoot(TBasePtr x, TBasePtr root); - static void RecalcChildren(TBasePtr x); + static void DecrementChildrenUntilRoot(TBasePtr x, TBasePtr root); + static void RecalcChildren(TBasePtr x); static TBasePtr IncrementNode(TBasePtr); static TBasePtr DecrementNode(TBasePtr); @@ -610,21 +610,21 @@ void TRbGlobal<TDummy>::Rebalance(TRbTreeNodeBase* x, TRbTreeNodeBase*& root) { } template <class TDummy> -void TRbGlobal<TDummy>::RecalcChildren(TRbTreeNodeBase* x) { - x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1; -} - -template <class TDummy> -void TRbGlobal<TDummy>::DecrementChildrenUntilRoot(TRbTreeNodeBase* x, TRbTreeNodeBase* root) { - auto* ptr = x; - --ptr->Children_; - while (ptr != root) { - ptr = ptr->Parent_; - --ptr->Children_; - } -} - -template <class TDummy> +void TRbGlobal<TDummy>::RecalcChildren(TRbTreeNodeBase* x) { + x->Children_ = ((x->Left_) ? x->Left_->Children_ : 0) + ((x->Right_) ? x->Right_->Children_ : 0) + 1; +} + +template <class TDummy> +void TRbGlobal<TDummy>::DecrementChildrenUntilRoot(TRbTreeNodeBase* x, TRbTreeNodeBase* root) { + auto* ptr = x; + --ptr->Children_; + while (ptr != root) { + ptr = ptr->Parent_; + --ptr->Children_; + } +} + +template <class TDummy> TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, TRbTreeNodeBase*& root, TRbTreeNodeBase*& leftmost, @@ -665,14 +665,14 @@ TRbTreeNodeBase* TRbGlobal<TDummy>::RebalanceForErase(TRbTreeNodeBase* z, z->Parent_->Right_ = y; y->Parent_ = z->Parent_; DoSwap(y->Color_, z->Color_); - - RecalcChildren(y); - if (x_parent != y) { - --x_parent->Children_; - } - if (x_parent != root) { - DecrementChildrenUntilRoot(x_parent->Parent_, root); - } + + RecalcChildren(y); + if (x_parent != y) { + --x_parent->Children_; + } + if (x_parent != root) { + DecrementChildrenUntilRoot(x_parent->Parent_, root); + } y = z; // y now points to node to be actually deleted } else { |