Changeset 369f5df in mainline

Timestamp:

2018-07-05T21:41:22Z (6 years ago)

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

7644d6e

Parents:

647b756

git-author:

Dzejrou <dzejrou@…> (2018-04-30 19:50:44)

git-committer:

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

Message:

cpp: moved insert logic to policies, fixed delete

File:

• uspace/lib/cpp/include/internal/rbtree.hpp (modified) (7 diffs)

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

@@ -178 +178 @@
 
             template<class... Args>
-            pair<iterator, bool> emplace(Args&&... args)
-            {
-                auto ret = Policy::emplace(*this, forward<Args>(args)...);
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
-            }
-
-            pair<iterator, bool> insert(const value_type& val)
-            {
-                auto ret = Policy::insert(*this, val);
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
-            }
-
-            pair<iterator, bool> insert(value_type&& val)
-            {
-                auto ret = Policy::insert(*this, forward<value_type>(val));
-                if (!ret.second)
-                    return ret;
-                ++size_;
-
-                repair_after_insert_(ret.first.node());
-                update_root_(ret.first.node());
-
-                return ret;
+            auto emplace(Args&&... args)
+            {
+                return Policy::emplace(*this, forward<Args>(args)...);
+            }
+
+            auto insert(const value_type& val)
+            {
+                return Policy::insert(*this, val);
+            }
+
+            auto insert(value_type&& val)
+            {
+                return Policy::insert(*this, forward<value_type>(val));
             }
 
@@ -228 +204 @@
 
                 auto node = const_cast<node_type*>(it.node());
-                ++it;
-
-                delete_node(node);
-                return iterator{const_cast<node_type*>(it.node()), it.end()};
+
+                node = delete_node(node);
+                return iterator{const_cast<node_type*>(node), node == nullptr};
             }
 
@@ -320 +295 @@
                 auto it2 = other.begin();
 
+                // TODO: this doesn't compare values :/
                 while (keys_equal(*it1++, *it2++))
                 { /* DUMMY BODY */ }
@@ -358 +334 @@
             }
 
-            void delete_node(node_type* node)
-            {
+            node_type* delete_node(const node_type* n)
+            {
+                auto node = const_cast<node_type*>(n);
                 if (!node)
-                    return;
+                    return nullptr;
 
                 --size_;
 
+                auto succ = node->successor();
                 if (node->left && node->right)
                 {
-                    node->swap(node->successor());
-
-                    // Node now has at most one child.
-                    delete_node(node);
-
-                    return;
+                    node->swap(succ);
+
+                    // Succ has at most one child.
+                    delete_node(succ);
+
+                    return node;
                 }
 
@@ -379 +357 @@
                 {
                     // Simply remove the node.
+                    // TODO: repair here too?
                     node->unlink();
-
                     delete node;
                 }
@@ -389 +367 @@
                     if (node->is_left_child())
                         child->parent->left = child;
-                    else if (node->is_left_child())
+                    else if (node->is_right_child())
                         child->parent->right = child;
 
@@ -395 +373 @@
                     repair_after_erase_(node, child);
                     update_root_(child);
-                }
+
+                    delete node;
+                }
+
+                return succ;
             }