Author: olehougaard
Date: Fri Sep 26 02:15:02 2008
New Revision: 382
Modified:
branches/bleeding_edge/src/array.js
branches/bleeding_edge/test/mozilla/mozilla.status
Log:
Fix for issue 95.
Fixed QuickSort so it doesn't overflow the stack with non-reflexsive
comparison functions.
Review URL: http://codereview.chromium.org/4297
Modified: branches/bleeding_edge/src/array.js
==============================================================================
--- branches/bleeding_edge/src/array.js (original)
+++ branches/bleeding_edge/src/array.js Fri Sep 26 02:15:02 2008
@@ -672,8 +672,10 @@
if (from >= to - 1) return;
var pivot_index = $floor($random() * (to - from)) + from;
var pivot = a[pivot_index];
+ a[pivot_index] = a[to - 1];
+ a[to - 1] = pivot;
var low_end = from; // Upper bound of the elements lower than pivot.
- var high_start = to; // Lower bound of the elements greater than pivot.
+ var high_start = to - 1; // Lower bound of the elements greater than
pivot.
for (var i = from; i < high_start; ) {
var element = a[i];
var order = Compare(element, pivot);
@@ -690,6 +692,9 @@
i++;
}
}
+ a[to - 1] = a[high_start];
+ a[high_start] = pivot;
+ high_start++;
QuickSort(a, from, low_end);
QuickSort(a, high_start, to);
}
Modified: branches/bleeding_edge/test/mozilla/mozilla.status
==============================================================================
--- branches/bleeding_edge/test/mozilla/mozilla.status (original)
+++ branches/bleeding_edge/test/mozilla/mozilla.status Fri Sep 26 02:15:02
2008
@@ -45,8 +45,6 @@
prefix mozilla
def FAIL_OK = FAIL, OKAY
-js1_5/Array/regress-360681-01: FAIL
-
##################### SKIPPED TESTS #####################
# This test checks that we behave properly in an out-of-memory
--~--~---------~--~----~------------~-------~--~----~
v8-dev mailing list
[email protected]
http://groups.google.com/group/v8-dev
-~----------~----~----~----~------~----~------~--~---
