Changeset 49fbfb5 in mainline

Timestamp:

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

Author:

Dzejrou <dzejrou@…>

Branches:

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

Children:

f8bbaa0

Parents:

be9eb15

git-author:

Dzejrou <dzejrou@…> (2018-04-29 19:22:10)

git-committer:

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

Message:

cpp: added some more functionality to rbtree_node

File:

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

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

@@ -30 +30 @@
 #define LIBCPP_INTERNAL_RBTREE_NODE
 
+#include <utility>
+
 namespace std::aux
 {
@@ -95 +97 @@
         }
 
+        bool is_right_child() const
+        {
+            if (parent)
+                return parent->right == this;
+            else
+                return false;
+        }
+
         void rotate_left()
         {
@@ -123 +133 @@
         }
 
+        rbtree_node* successor()
+        {
+            if (right)
+                return right->find_smallest();
+            else
+            {
+                auto current = this;
+                while (!current->is_left_child())
+                    current = current->parent;
+
+                return current->parent;
+            }
+        }
+
         void add_left_child(rbtree_node* node)
         {
@@ -141 +165 @@
         }
 
+        void swap(rbtree_node* other)
+        {
+            /**
+             * Parent can be null so we check both ways.
+             */
+            if (is_left_child())
+                parent->left = other;
+            else if (is_right_child())
+                parent->right = other;
+
+            if (other->is_left_child())
+                other->parent->left = this;
+            else if (other->is_right_child())
+                other->parent->right = this;
+
+            if (left)
+                left->parent = other;
+            if (right)
+                right->parent = other;
+            if (other->left)
+                other->left->parent = this;
+            if (other->right)
+                other->right->parent = this;
+
+            std::swap(parent, other->parent);
+            std::swap(left, other->left);
+            std::swap(right, other->right);
+        }
+
+        void unlink()
+        {
+            if (is_left_child())
+                parent->left = nullptr;
+            else if (is_right_child())
+                parent->right = nullptr;
+        }
+
         ~rbtree_node()
         {