OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 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 724 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
735 if (x === y) return 0; | 735 if (x === y) return 0; |
736 if (%_IsSmi(x) && %_IsSmi(y)) { | 736 if (%_IsSmi(x) && %_IsSmi(y)) { |
737 return %SmiLexicographicCompare(x, y); | 737 return %SmiLexicographicCompare(x, y); |
738 } | 738 } |
739 x = ToString(x); | 739 x = ToString(x); |
740 y = ToString(y); | 740 y = ToString(y); |
741 if (x == y) return 0; | 741 if (x == y) return 0; |
742 else return x < y ? -1 : 1; | 742 else return x < y ? -1 : 1; |
743 }; | 743 }; |
744 } | 744 } |
745 var global_receiver = %GetGlobalReceiver(); | 745 var receiver = |
| 746 %_IsNativeOrStrictMode(comparefn) ? void 0 : %GetGlobalReceiver(); |
746 | 747 |
747 function InsertionSort(a, from, to) { | 748 function InsertionSort(a, from, to) { |
748 for (var i = from + 1; i < to; i++) { | 749 for (var i = from + 1; i < to; i++) { |
749 var element = a[i]; | 750 var element = a[i]; |
750 for (var j = i - 1; j >= from; j--) { | 751 for (var j = i - 1; j >= from; j--) { |
751 var tmp = a[j]; | 752 var tmp = a[j]; |
752 var order = %_CallFunction(global_receiver, tmp, element, comparefn); | 753 var order = %_CallFunction(receiver, tmp, element, comparefn); |
753 if (order > 0) { | 754 if (order > 0) { |
754 a[j + 1] = tmp; | 755 a[j + 1] = tmp; |
755 } else { | 756 } else { |
756 break; | 757 break; |
757 } | 758 } |
758 } | 759 } |
759 a[j + 1] = element; | 760 a[j + 1] = element; |
760 } | 761 } |
761 } | 762 } |
762 | 763 |
763 function QuickSort(a, from, to) { | 764 function QuickSort(a, from, to) { |
764 // Insertion sort is faster for short arrays. | 765 // Insertion sort is faster for short arrays. |
765 if (to - from <= 10) { | 766 if (to - from <= 10) { |
766 InsertionSort(a, from, to); | 767 InsertionSort(a, from, to); |
767 return; | 768 return; |
768 } | 769 } |
769 // Find a pivot as the median of first, last and middle element. | 770 // Find a pivot as the median of first, last and middle element. |
770 var v0 = a[from]; | 771 var v0 = a[from]; |
771 var v1 = a[to - 1]; | 772 var v1 = a[to - 1]; |
772 var middle_index = from + ((to - from) >> 1); | 773 var middle_index = from + ((to - from) >> 1); |
773 var v2 = a[middle_index]; | 774 var v2 = a[middle_index]; |
774 var c01 = %_CallFunction(global_receiver, v0, v1, comparefn); | 775 var c01 = %_CallFunction(receiver, v0, v1, comparefn); |
775 if (c01 > 0) { | 776 if (c01 > 0) { |
776 // v1 < v0, so swap them. | 777 // v1 < v0, so swap them. |
777 var tmp = v0; | 778 var tmp = v0; |
778 v0 = v1; | 779 v0 = v1; |
779 v1 = tmp; | 780 v1 = tmp; |
780 } // v0 <= v1. | 781 } // v0 <= v1. |
781 var c02 = %_CallFunction(global_receiver, v0, v2, comparefn); | 782 var c02 = %_CallFunction(receiver, v0, v2, comparefn); |
782 if (c02 >= 0) { | 783 if (c02 >= 0) { |
783 // v2 <= v0 <= v1. | 784 // v2 <= v0 <= v1. |
784 var tmp = v0; | 785 var tmp = v0; |
785 v0 = v2; | 786 v0 = v2; |
786 v2 = v1; | 787 v2 = v1; |
787 v1 = tmp; | 788 v1 = tmp; |
788 } else { | 789 } else { |
789 // v0 <= v1 && v0 < v2 | 790 // v0 <= v1 && v0 < v2 |
790 var c12 = %_CallFunction(global_receiver, v1, v2, comparefn); | 791 var c12 = %_CallFunction(receiver, v1, v2, comparefn); |
791 if (c12 > 0) { | 792 if (c12 > 0) { |
792 // v0 <= v2 < v1 | 793 // v0 <= v2 < v1 |
793 var tmp = v1; | 794 var tmp = v1; |
794 v1 = v2; | 795 v1 = v2; |
795 v2 = tmp; | 796 v2 = tmp; |
796 } | 797 } |
797 } | 798 } |
798 // v0 <= v1 <= v2 | 799 // v0 <= v1 <= v2 |
799 a[from] = v0; | 800 a[from] = v0; |
800 a[to - 1] = v2; | 801 a[to - 1] = v2; |
801 var pivot = v1; | 802 var pivot = v1; |
802 var low_end = from + 1; // Upper bound of elements lower than pivot. | 803 var low_end = from + 1; // Upper bound of elements lower than pivot. |
803 var high_start = to - 1; // Lower bound of elements greater than pivot. | 804 var high_start = to - 1; // Lower bound of elements greater than pivot. |
804 a[middle_index] = a[low_end]; | 805 a[middle_index] = a[low_end]; |
805 a[low_end] = pivot; | 806 a[low_end] = pivot; |
806 | 807 |
807 // From low_end to i are elements equal to pivot. | 808 // From low_end to i are elements equal to pivot. |
808 // From i to high_start are elements that haven't been compared yet. | 809 // From i to high_start are elements that haven't been compared yet. |
809 partition: for (var i = low_end + 1; i < high_start; i++) { | 810 partition: for (var i = low_end + 1; i < high_start; i++) { |
810 var element = a[i]; | 811 var element = a[i]; |
811 var order = %_CallFunction(global_receiver, element, pivot, comparefn); | 812 var order = %_CallFunction(receiver, element, pivot, comparefn); |
812 if (order < 0) { | 813 if (order < 0) { |
813 %_SwapElements(a, i, low_end); | 814 %_SwapElements(a, i, low_end); |
814 low_end++; | 815 low_end++; |
815 } else if (order > 0) { | 816 } else if (order > 0) { |
816 do { | 817 do { |
817 high_start--; | 818 high_start--; |
818 if (high_start == i) break partition; | 819 if (high_start == i) break partition; |
819 var top_elem = a[high_start]; | 820 var top_elem = a[high_start]; |
820 order = %_CallFunction(global_receiver, top_elem, pivot, comparefn); | 821 order = %_CallFunction(receiver, top_elem, pivot, comparefn); |
821 } while (order > 0); | 822 } while (order > 0); |
822 %_SwapElements(a, i, high_start); | 823 %_SwapElements(a, i, high_start); |
823 if (order < 0) { | 824 if (order < 0) { |
824 %_SwapElements(a, i, low_end); | 825 %_SwapElements(a, i, low_end); |
825 low_end++; | 826 low_end++; |
826 } | 827 } |
827 } | 828 } |
828 } | 829 } |
829 QuickSort(a, from, low_end); | 830 QuickSort(a, from, low_end); |
830 QuickSort(a, high_start, to); | 831 QuickSort(a, high_start, to); |
(...skipping 528 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1359 InternalArray.prototype.join = getFunction("join", ArrayJoin); | 1360 InternalArray.prototype.join = getFunction("join", ArrayJoin); |
1360 InternalArray.prototype.pop = getFunction("pop", ArrayPop); | 1361 InternalArray.prototype.pop = getFunction("pop", ArrayPop); |
1361 InternalArray.prototype.push = getFunction("push", ArrayPush); | 1362 InternalArray.prototype.push = getFunction("push", ArrayPush); |
1362 InternalArray.prototype.toString = function() { | 1363 InternalArray.prototype.toString = function() { |
1363 return "Internal Array, length " + this.length; | 1364 return "Internal Array, length " + this.length; |
1364 }; | 1365 }; |
1365 } | 1366 } |
1366 | 1367 |
1367 | 1368 |
1368 SetupArray(); | 1369 SetupArray(); |
OLD | NEW |