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 |