| OLD | NEW |
| 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
| 2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
| 3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
| 4 // met: | 4 // met: |
| 5 // | 5 // |
| 6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
| 7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
| 8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
| 9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
| 10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
| (...skipping 666 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 677 function QuickSort(a, from, to) { | 677 function QuickSort(a, from, to) { |
| 678 // Insertion sort is faster for short arrays. | 678 // Insertion sort is faster for short arrays. |
| 679 if (to - from <= 22) { | 679 if (to - from <= 22) { |
| 680 InsertionSort(a, from, to); | 680 InsertionSort(a, from, to); |
| 681 return; | 681 return; |
| 682 } | 682 } |
| 683 var pivot_index = $floor($random() * (to - from)) + from; | 683 var pivot_index = $floor($random() * (to - from)) + from; |
| 684 var pivot = a[pivot_index]; | 684 var pivot = a[pivot_index]; |
| 685 // Issue 95: Keep the pivot element out of the comparisons to avoid | 685 // Issue 95: Keep the pivot element out of the comparisons to avoid |
| 686 // infinite recursion if comparefn(pivot, pivot) != 0. | 686 // infinite recursion if comparefn(pivot, pivot) != 0. |
| 687 a[pivot_index] = a[from]; | 687 %_SwapElements(a, from, pivot_index); |
| 688 a[from] = pivot; | |
| 689 var low_end = from; // Upper bound of the elements lower than pivot. | 688 var low_end = from; // Upper bound of the elements lower than pivot. |
| 690 var high_start = to; // Lower bound of the elements greater than pivot. | 689 var high_start = to; // Lower bound of the elements greater than pivot. |
| 691 // From low_end to i are elements equal to pivot. | 690 // From low_end to i are elements equal to pivot. |
| 692 // From i to high_start are elements that haven't been compared yet. | 691 // From i to high_start are elements that haven't been compared yet. |
| 693 for (var i = from + 1; i < high_start; ) { | 692 for (var i = from + 1; i < high_start; ) { |
| 694 var element = a[i]; | 693 var element = a[i]; |
| 695 var order = %_CallFunction(global_receiver, element, pivot, comparefn); | 694 var order = %_CallFunction(global_receiver, element, pivot, comparefn); |
| 696 if (order < 0) { | 695 if (order < 0) { |
| 697 a[i] = a[low_end]; | 696 %_SwapElements(a, i, low_end); |
| 698 a[low_end] = element; | |
| 699 i++; | 697 i++; |
| 700 low_end++; | 698 low_end++; |
| 701 } else if (order > 0) { | 699 } else if (order > 0) { |
| 702 high_start--; | 700 high_start--; |
| 703 a[i] = a[high_start]; | 701 %_SwapElements(a, i, high_start); |
| 704 a[high_start] = element; | |
| 705 } else { // order == 0 | 702 } else { // order == 0 |
| 706 i++; | 703 i++; |
| 707 } | 704 } |
| 708 } | 705 } |
| 709 QuickSort(a, from, low_end); | 706 QuickSort(a, from, low_end); |
| 710 QuickSort(a, high_start, to); | 707 QuickSort(a, high_start, to); |
| 711 } | 708 } |
| 712 | 709 |
| 713 // Copies elements in the range 0..length from obj's prototype chain | 710 // Copies elements in the range 0..length from obj's prototype chain |
| 714 // to obj itself, if obj has holes. Returns one more than the maximal index | 711 // to obj itself, if obj has holes. Returns one more than the maximal index |
| (...skipping 406 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 1121 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), | 1118 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), |
| 1122 "reduce", getFunction("reduce", ArrayReduce, 1), | 1119 "reduce", getFunction("reduce", ArrayReduce, 1), |
| 1123 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) | 1120 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) |
| 1124 )); | 1121 )); |
| 1125 | 1122 |
| 1126 %FinishArrayPrototypeSetup($Array.prototype); | 1123 %FinishArrayPrototypeSetup($Array.prototype); |
| 1127 } | 1124 } |
| 1128 | 1125 |
| 1129 | 1126 |
| 1130 SetupArray(); | 1127 SetupArray(); |
| OLD | NEW |