Changeset 21d97e8 in mainline for uspace/lib/cpp/include/internal/rbtree_node.hpp

Timestamp:

2018-07-05T21:41:23Z (7 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

lfn, master, serial, ticket/834-toolchain-update, topic/msim-upgrade, topic/simplify-dev-export

Children:

0fe0f32

Parents:

5608106c

git-author:

Dzejrou <dzejrou@…> (2018-05-14 17:03:57)

git-committer:

Dzejrou <dzejrou@…> (2018-07-05 21:41:23)

Message:

cpp: fixed bugs found by the map tests

File:

• uspace/lib/cpp/include/internal/rbtree_node.hpp (modified) (5 diffs)

uspace/lib/cpp/include/internal/rbtree_node.hpp

@@ -46 +46 @@
         {
             if (node && node->parent())
-                return node->parent->parent();
+                return node->parent()->parent();
             else
                 return nullptr;
@@ -55 +55 @@
             if (node && node->parent())
             {
-                if (node == node->parent->left())
-                    return node->parent->right();
-                else
-                    return node->parent->left();
+                if (node == node->parent()->left())
+                    return node->parent()->right();
+                else
+                    return node->parent()->left();
             }
             else
@@ -573 +573 @@
             const rbtree_multi_node* predecessor() const
             {
-                return utils::predecessor(this);
+                if (this != first_)
+                {
+                    auto tmp = first_;
+                    while (tmp->next_ != this)
+                        tmp = tmp->next_;
+
+                    return tmp;
+                }
+                else
+                {
+                    auto tmp = utils::predecessor(this);
+
+                    /**
+                     * If tmp was duplicate, we got a pointer
+                     * to the first node in the list. So we need
+                     * to move to the end.
+                     */
+                    while (tmp->next_ != nullptr)
+                        tmp = tmp->next_;
+
+                    return tmp;
+                }
             }
 
@@ -591 +612 @@
             }
 
-            rbtree_multi_node<T>* get_node_for_deletion()
-            {
+            rbtree_multi_node* get_node_for_deletion()
+            {
+                /**
+                 * To make sure we delete nodes in
+                 * the order of their insertion
+                 * (not required, but sensical), we
+                 * update then list and return this
+                 * for deletion.
+                 */
                 if (next_)
                 {
-                    auto tmp = next_;
-                    while (tmp && tmp->next_ != this)
+                    // Make next the new this.
+                    next_->first_ = next_;
+                    if (is_left_child())
+                        parent_->left_ = next_;
+                    else if (is_right_child())
+                        parent_->right_ = next_;
+
+                    if (left_)
+                        left_->parent_ = next_;
+                    if (right_)
+                        right_->parent_ = next_;
+
+                    /**
+                     * Update the first_ pointer
+                     * of the rest of the list.
+                     */
+                    auto tmp = next_->next_;
+                    while (tmp)
+                    {
+                        tmp->first_ = next_;
                         tmp = tmp->next_;
-
-                    return tmp; // This will get deleted.
+                    }
+
+                    /**
+                     * Otherwise destructor could
+                     * destroy them.
+                     */
+                    parent_ = nullptr;
+                    left_ = nullptr;
+                    right_ = nullptr;
+                    next_ = nullptr;
+                    first_ = nullptr;
+
+                    return this; // This will get deleted.
                 }
                 else
@@ -608 +665 @@
             {
                 if (is_left_child())
-                    parent->left_ = nullptr;
+                    parent_->left_ = nullptr;
                 else if (is_right_child())
-                    parent->right_ = nullptr;
+                    parent_->right_ = nullptr;
             }