| 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 |