From 2ba2d245c152cdbb26f918bc4481c77b8004f3cd Mon Sep 17 00:00:00 2001
From: Lars Knoll <lars.knoll@digia.com>
Date: Thu, 9 Jan 2014 16:48:56 +0100
Subject: Fixes to sparse array handling

deleting entries in sparse arrays could lead
to rather unexpected results where values got
moved to wrong indices, as we didn't correctly
update the size_left values in the red-black tree.

Change-Id: If71fcc04d39f257194394cb4f734d0db14b92b69
Reviewed-by: Simon Hausmann <simon.hausmann@digia.com>
---
 src/qml/jsruntime/qv4sparsearray.cpp | 64 ++++++++++++++++++------------------
 1 file changed, 32 insertions(+), 32 deletions(-)

(limited to 'src/qml/jsruntime/qv4sparsearray.cpp')

diff --git a/src/qml/jsruntime/qv4sparsearray.cpp b/src/qml/jsruntime/qv4sparsearray.cpp
index 3ee89d5b53..97dd695067 100644
--- a/src/qml/jsruntime/qv4sparsearray.cpp
+++ b/src/qml/jsruntime/qv4sparsearray.cpp
@@ -245,51 +245,51 @@ void SparseArray::deleteNode(SparseArrayNode *z)
             else
                 mostLeftNode = y->parent();
         }
-    } else {
-        if (y->right == 0) {
+    } else if (y->right == 0) {
             x = y->left;
-        } else {
-            y = y->right;
-            while (y->left != 0)
-                y = y->left;
-            x = y->right;
-        }
+    } else {
+        y = y->right;
+        while (y->left != 0)
+            y = y->left;
+        x = y->right;
     }
     if (y != z) {
-        z->left->setParent(y);
-        y->left = z->left;
+        // move y into the position of z
+        // adjust size_left so the keys are ok.
+        z->size_left += y->size_left;
+        SparseArrayNode *n = y->parent();
+        while (n != z) {
+            n->size_left -= y->size_left;
+            n = n->parent();
+        }
+        y->size_left = 0;
+        z->value = y->value;
+
         if (y != z->right) {
             x_parent = y->parent();
-            if (x)
-                x->setParent(y->parent());
             y->parent()->left = x;
-            y->right = z->right;
-            z->right->setParent(y);
         } else {
-            x_parent = y;
+            x_parent = z;
+            z->right = x;
         }
-        if (root == z)
-            root = y;
-        else if (z->parent()->left == z)
-            z->parent()->left = y;
-        else
-            z->parent()->right = y;
-        y->setParent(z->parent());
-        // Swap the colors
-        SparseArrayNode::Color c = y->color();
-        y->setColor(z->color());
-        z->setColor(c);
-        y = z;
+        if (x)
+            x->setParent(x_parent);
     } else {
         x_parent = y->parent();
         if (x)
             x->setParent(y->parent());
-        if (root == z)
+        if (root == y)
             root = x;
-        else if (z->parent()->left == z)
-            z->parent()->left = x;
-        else
-            z->parent()->right = x;
+        else if (y->parent()->left == y) {
+            y->parent()->left = x;
+            if (x)
+                x->size_left += y->size_left;
+        } else {
+            y->parent()->right = x;
+            if (x)
+                x->size_left += y->size_left;
+        }
+        y->size_left = 0;
     }
     if (y->color() != SparseArrayNode::Red) {
         while (x != root && (x == 0 || x->color() == SparseArrayNode::Black)) {
-- 
cgit v1.2.3