Changeset 73e3791 in mainline for uspace/lib/cpp/include/internal/rbtree.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:

27f1bc0

Parents:

6175b78

git-author:

Dzejrou <dzejrou@…> (2018-05-13 22:57:14)

git-committer:

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

Message:

cpp: revamped rbtree so that it now stores equivalent keys in a list

File:

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

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

@@ -41 +41 @@
         class KeyComp, class Alloc, class Size,
         class Iterator, class ConstIterator,
-        class Policy
+        class Policy, class Node
     >
     class rbtree
@@ -53 +53 @@
             using key_extract    = KeyExtractor;
 
-            using iterator             = Iterator;
-            using const_iterator       = ConstIterator;
+            using iterator       = Iterator;
+            using const_iterator = ConstIterator;
 
             using reverse_iterator       = std::reverse_iterator<iterator>;
             using const_reverse_iterator = std::reverse_iterator<const_iterator>;
 
-            using node_type = rbtree_node<value_type>;
+            using node_type = Node;
 
             rbtree(const key_compare& kcmp = key_compare{})
@@ -100 +100 @@
             bool empty() const noexcept
             {
-                return size_;
+                return size_ == 0U;
             }
 
@@ -202 +202 @@
 
                 node = delete_node(node);
-                return iterator{const_cast<node_type*>(node), node == nullptr};
+                if (!node)
+                    return iterator{find_largest_(), true};
+                else
+                    return iterator{const_cast<node_type*>(node), false};
             }
 
@@ -322 +325 @@
                     parent = current;
                     if (key_compare_(key, key_extractor_(current->value)))
-                        current = current->left;
+                        current = current->left();
                     else if (key_compare_(key_extractor_(current->value), key))
-                        current = current->right;
+                        current = current->right();
                     else
                         return current;
@@ -337 +340 @@
                 if (!node)
                     return nullptr;
+                if (auto tmp = node->get_node_for_deletion(); tmp != nullptr)
+                {
+                    /**
+                     * This will kick in multi containers,
+                     * 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.
+                     */
+                    delete tmp;
+
+                    return node;
+                }
 
                 --size_;
 
+                if (node == root_)
+                {
+                    delete node;
+                    root_ = nullptr;
+
+                    return nullptr;
+                }
+
                 auto succ = node->successor();
-                if (node->left && node->right)
+                if (node->left() && node->right())
                 {
                     node->swap(succ);
-
-                    // Succ has at most one child.
-                    delete_node(succ);
-
-                    return node;
-                }
-
-                auto child = node->right ? node->right : node->left;
+                    if (succ && !succ->parent())
+                        root_ = succ;
+
+                    // Node now has at most one child.
+                    // Also: If succ was nullptr, the swap
+                    //       didn't do anything and we can
+                    //       safely delete node.
+                    return delete_node(node);
+                }
+
+                auto child = node->right() ? node->right() : node->left();
                 if (!child)
                 {
@@ -362 +389 @@
                 {
                     // Replace with the child.
-                    child->parent = node->parent;
+                    child->parent(node->parent());
                     if (node->is_left_child())
-                        child->parent->left = child;
+                        child->parent()->left(child);
                     else if (node->is_right_child())
-                        child->parent->right = child;
+                        child->parent()->right(child);
 
                     // Repair if needed.
@@ -380 +407 @@
             void insert_node(node_type* node, node_type* parent)
             {
-                if (!node)
-                    return;
-
-                ++size_;
-                if (!parent)
-                {
-                    node->color = rbcolor::black;
-                    root_ = node;
-                }
-                else
-                {
-                    if (keys_comp(get_key(node->value), parent->value))
-                        parent->add_left_child(node);
-                    else
-                        parent->add_right_child(node);
-
-                    repair_after_insert_(node);
-                    update_root_(node);
-                }
+                Policy::insert(*this, node, parent);
             }
 
@@ -413 +422 @@
                 {
                     if (key_compare_(key, key_extractor_(current->value)))
-                        current = current->left;
+                        current = current->left();
                     else if (key_compare_(key_extractor_(current->value), key))
-                        current = current->right;
+                        current = current->right();
                     else
                         return current;
@@ -445 +454 @@
 
                 root_ = const_cast<node_type*>(node);
-                while (root_->parent)
-                    root_ = root_->parent;
+                while (root_->parent())
+                    root_ = root_->parent();
             }