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

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:

647b756

Parents:

af0fbaac

git-author:

Dzejrou <dzejrou@…> (2018-04-30 19:48:15)

git-committer:

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

Message:

cpp: added more node operations, changed swap to value swap instead of link swap which was buggy and probably slower when move semantics are in the play

File:

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

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

@@ -124 +124 @@
         }
 
+        const rbtree_node* find_smallest() const
+        {
+            auto res = this;
+            while (res->left)
+                res = res->left;
+
+            return res;
+        }
+
         rbtree_node* find_largest()
         {
@@ -133 +142 @@
         }
 
-        rbtree_node* successor()
+        const rbtree_node* find_largest() const
+        {
+            auto res = this;
+            while (res->right)
+                res = res->right;
+
+            return res;
+        }
+
+        rbtree_node* successor() const
         {
             if (right)
@@ -167 +185 @@
         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);
+            std::swap(value, other->value);
         }