Reviewers: Mads Ager, Description: Fix for issue 95.
Fixed QuickSort so it doesn't overflow the stack with non-reflexsive comparison functions. Please review this at http://codereview.chromium.org/4297 Affected files: M src/array.js M test/mozilla/mozilla.status Index: test/mozilla/mozilla.status =================================================================== --- test/mozilla/mozilla.status (revision 380) +++ test/mozilla/mozilla.status (working copy) @@ -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 Index: src/array.js =================================================================== --- src/array.js (revision 380) +++ src/array.js (working copy) @@ -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); } --~--~---------~--~----~------------~-------~--~----~ v8-dev mailing list [email protected] http://groups.google.com/group/v8-dev -~----------~----~----~----~------~----~------~--~---
