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>

1 files changed, 32 insertions, 32 deletions

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)) {