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

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

Location:

uspace/lib/cpp/include/internal

Files:

• rbtree.hpp (modified) (3 diffs)
• rbtree_iterators.hpp (modified) (6 diffs)
• rbtree_node.hpp (modified) (5 diffs)
• rbtree_policies.hpp (modified) (3 diffs)

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

@@ -353 +353 @@
                 if (!node)
                     return nullptr;
+
+                --size_;
+
+                auto succ = node->successor();
                 if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
                 {
@@ -359 +363 @@
                      * we popped one node from a list of nodes
                      * with equivalent keys and we can delete it
-                     * and return the original as it is still
-                     * in place.
+                     * and return the successor which was the next
+                     * in the list.
                      */
                     delete tmp;
 
-                    return node;
-                }
-
-                --size_;
-
-                if (node == root_)
-                {
+                    update_root_(succ); // Incase the first in list was root.
+                    return succ;
+                }
+                else if (node == root_)
+                { // Only executed if root_ is unique.
+                    root_ = nullptr;
                     delete node;
-                    root_ = nullptr;
 
                     return nullptr;
                 }
 
-                auto succ = node->successor();
                 if (node->left() && node->right())
                 {
@@ -407 +408 @@
                     else if (node->is_right_child())
                         child->parent()->right(child);
+                    node->parent(nullptr);
+                    node->left(nullptr);
+                    node->right(nullptr);
 
                     // Repair if needed.

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

@@ -78 +78 @@
             rbtree_iterator& operator++()
             {
+                if (end_)
+                    return *this;
+
                 if (current_)
                 {
@@ -102 +105 @@
                 if (end_)
                 {
-                    try_undo_end_();
+                    end_ = false;
 
                     return *this;
@@ -145 +148 @@
             node_type* current_;
             bool end_;
-
-            void try_undo_end_()
-            {
-                if (!current_)
-                    return;
-
-                /**
-                 * We can do this if we are past end().
-                 * This means we are the largest.
-                 */
-                if (current_->find_largest() == current_)
-                    end_ = false;
-            }
     };
 
@@ -224 +214 @@
             rbtree_const_iterator& operator++()
             {
+                if (end_)
+                    return *this;
+
                 if (current_)
                 {
@@ -248 +241 @@
                 if (end_)
                 {
-                    try_undo_end_();
+                    end_ = false;
 
                     return *this;
@@ -286 +279 @@
             const node_type* current_;
             bool end_;
-
-            void try_undo_end_()
-            {
-                if (!current_)
-                    return;
-
-                /**
-                 * We can do this if we are past end().
-                 * This means we are the largest.
-                 */
-                if (current_->find_largest() == current_)
-                    end_ = false;
-            }
     };
 

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;
             }
 

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

@@ -277 +277 @@
 
             size_type res{};
-            while (tree.keys_equal(tree.get_key(*it), key))
+            while (it != tree.end() && tree.keys_equal(tree.get_key(*it), key))
             {
                 ++res;
@@ -291 +291 @@
             auto it = lower_bound_const(tree, key);
 
-            return typename Tree::iterator{it.node(), it.end()};
+            return typename Tree::iterator{
+                const_cast<typename Tree::node_type*>(it.node()), it.end()
+            };
         }
 
@@ -328 +330 @@
             auto it = upper_bound_const(tree, key);
 
-            return typename Tree::iterator{it.node(), it.end()};
+            return typename Tree::iterator{
+                const_cast<typename Tree::node_type*>(it.node()), it.end()
+            };
         }