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 659 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
670 } else { | 670 } else { |
671 break; | 671 break; |
672 } | 672 } |
673 } | 673 } |
674 a[j + 1] = element; | 674 a[j + 1] = element; |
675 } | 675 } |
676 } | 676 } |
677 | 677 |
678 function QuickSort(a, from, to) { | 678 function QuickSort(a, from, to) { |
679 // Insertion sort is faster for short arrays. | 679 // Insertion sort is faster for short arrays. |
680 if (to - from <= 22) { | 680 if (to - from <= 13) { |
681 InsertionSort(a, from, to); | 681 InsertionSort(a, from, to); |
682 return; | 682 return; |
683 } | 683 } |
684 var pivot_index = $floor($random() * (to - from)) + from; | 684 |
685 var pivot = a[pivot_index]; | 685 // Find a pivot as the median of first, last and middle element. |
686 // Issue 95: Keep the pivot element out of the comparisons to avoid | 686 var v0 = a[from]; |
687 // infinite recursion if comparefn(pivot, pivot) != 0. | 687 var v1 = a[to - 1]; |
688 %_SwapElements(a, from, pivot_index); | 688 var middle_index = from + ((to - from) >> 1); |
689 var low_end = from; // Upper bound of the elements lower than pivot. | 689 var v2 = a[middle_index]; |
690 var high_start = to; // Lower bound of the elements greater than pivot. | 690 var c01 = comparefn(v0, v1); |
| 691 if (c01 > 0) { |
| 692 // v1 < v0, so swap them. |
| 693 var tmp = v0; |
| 694 v0 = v1; |
| 695 v1 = tmp; |
| 696 } // v0 <= v1. |
| 697 var c02 = comparefn(v0, v2); |
| 698 if (c02 >= 0) { |
| 699 // v2 <= v0 <= v1. |
| 700 var tmp = v0; |
| 701 v0 = v2; |
| 702 v2 = v1; |
| 703 v1 = tmp; |
| 704 } else { |
| 705 // v0 <= v1 && v0 < v2 |
| 706 var c12 = comparefn(v1, v2); |
| 707 if (c12 > 0) { |
| 708 // v0 <= v2 < v1 |
| 709 var tmp = v1; |
| 710 v1 = v2; |
| 711 v2 = tmp; |
| 712 } |
| 713 } |
| 714 // v0 <= v1 <= v2 |
| 715 a[from] = v0; |
| 716 a[to - 1] = v2; |
| 717 var pivot = v1; |
| 718 var low_end = from + 1; // Upper bound of the elements lower than pivot. |
| 719 var high_start = to - 1; // Lower bound of the elements greater than pivot. |
| 720 a[middle_index] = a[low_end]; |
| 721 a[low_end] = pivot; |
| 722 |
691 // From low_end to i are elements equal to pivot. | 723 // From low_end to i are elements equal to pivot. |
692 // From i to high_start are elements that haven't been compared yet. | 724 // From i to high_start are elements that haven't been compared yet. |
693 for (var i = from + 1; i < high_start; ) { | 725 for (var i = low_end + 1; i < high_start; ) { |
694 var element = a[i]; | 726 var element = a[i]; |
695 var order = %_CallFunction(global_receiver, element, pivot, comparefn); | 727 var order = %_CallFunction(global_receiver, element, pivot, comparefn); |
696 if (order < 0) { | 728 if (order < 0) { |
697 %_SwapElements(a, i, low_end); | 729 %_SwapElements(a, i, low_end); |
698 i++; | 730 i++; |
699 low_end++; | 731 low_end++; |
700 } else if (order > 0) { | 732 } else if (order > 0) { |
701 high_start--; | 733 high_start--; |
702 %_SwapElements(a, i, high_start); | 734 %_SwapElements(a, i, high_start); |
703 } else { // order == 0 | 735 } else { // order == 0 |
704 i++; | 736 i++; |
705 } | 737 } |
706 } | 738 } |
707 QuickSort(a, from, low_end); | 739 QuickSort(a, from, low_end); |
708 QuickSort(a, high_start, to); | 740 QuickSort(a, high_start, to); |
709 } | 741 } |
710 | 742 |
711 // Copies elements in the range 0..length from obj's prototype chain | 743 // Copy elements in the range 0..length from obj's prototype chain |
712 // to obj itself, if obj has holes. Returns one more than the maximal index | 744 // to obj itself, if obj has holes. Return one more than the maximal index |
713 // of a prototype property. | 745 // of a prototype property. |
714 function CopyFromPrototype(obj, length) { | 746 function CopyFromPrototype(obj, length) { |
715 var max = 0; | 747 var max = 0; |
716 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { | 748 for (var proto = obj.__proto__; proto; proto = proto.__proto__) { |
717 var indices = %GetArrayKeys(proto, length); | 749 var indices = %GetArrayKeys(proto, length); |
718 if (indices.length > 0) { | 750 if (indices.length > 0) { |
719 if (indices[0] == -1) { | 751 if (indices[0] == -1) { |
720 // It's an interval. | 752 // It's an interval. |
721 var proto_length = indices[1]; | 753 var proto_length = indices[1]; |
722 for (var i = 0; i < proto_length; i++) { | 754 for (var i = 0; i < proto_length; i++) { |
(...skipping 449 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1172 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), | 1204 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), |
1173 "reduce", getFunction("reduce", ArrayReduce, 1), | 1205 "reduce", getFunction("reduce", ArrayReduce, 1), |
1174 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) | 1206 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) |
1175 )); | 1207 )); |
1176 | 1208 |
1177 %FinishArrayPrototypeSetup($Array.prototype); | 1209 %FinishArrayPrototypeSetup($Array.prototype); |
1178 } | 1210 } |
1179 | 1211 |
1180 | 1212 |
1181 SetupArray(); | 1213 SetupArray(); |
OLD | NEW |