OLD | NEW |
---|---|
1 // Copyright 2006-2008 the V8 project authors. All rights reserved. | 1 // Copyright 2006-2008 the V8 project authors. All rights reserved. |
Karl Klose
2010/12/20 14:28:43
-2010
Lasse Reichstein
2010/12/20 15:00:59
Will do.
| |
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 |
11 // with the distribution. | 11 // with the distribution. |
(...skipping 658 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 <= 13) { | 680 if (to - from <= 10) { |
681 InsertionSort(a, from, to); | 681 InsertionSort(a, from, to); |
682 return; | 682 return; |
683 } | 683 } |
684 | |
685 // Find a pivot as the median of first, last and middle element. | 684 // Find a pivot as the median of first, last and middle element. |
686 var v0 = a[from]; | 685 var v0 = a[from]; |
687 var v1 = a[to - 1]; | 686 var v1 = a[to - 1]; |
688 var middle_index = from + ((to - from) >> 1); | 687 var middle_index = from + ((to - from) >> 1); |
689 var v2 = a[middle_index]; | 688 var v2 = a[middle_index]; |
690 var c01 = comparefn(v0, v1); | 689 var c01 = %_CallFunction(global_receiver, v0, v1, comparefn); |
691 if (c01 > 0) { | 690 if (c01 > 0) { |
692 // v1 < v0, so swap them. | 691 // v1 < v0, so swap them. |
693 var tmp = v0; | 692 var tmp = v0; |
694 v0 = v1; | 693 v0 = v1; |
695 v1 = tmp; | 694 v1 = tmp; |
696 } // v0 <= v1. | 695 } // v0 <= v1. |
697 var c02 = comparefn(v0, v2); | 696 var c02 = %_CallFunction(global_receiver, v0, v2, comparefn); |
698 if (c02 >= 0) { | 697 if (c02 >= 0) { |
699 // v2 <= v0 <= v1. | 698 // v2 <= v0 <= v1. |
700 var tmp = v0; | 699 var tmp = v0; |
701 v0 = v2; | 700 v0 = v2; |
702 v2 = v1; | 701 v2 = v1; |
703 v1 = tmp; | 702 v1 = tmp; |
704 } else { | 703 } else { |
705 // v0 <= v1 && v0 < v2 | 704 // v0 <= v1 && v0 < v2 |
706 var c12 = comparefn(v1, v2); | 705 var c12 = %_CallFunction(global_receiver, v1, v2, comparefn); |
707 if (c12 > 0) { | 706 if (c12 > 0) { |
708 // v0 <= v2 < v1 | 707 // v0 <= v2 < v1 |
709 var tmp = v1; | 708 var tmp = v1; |
710 v1 = v2; | 709 v1 = v2; |
711 v2 = tmp; | 710 v2 = tmp; |
712 } | 711 } |
713 } | 712 } |
714 // v0 <= v1 <= v2 | 713 // v0 <= v1 <= v2 |
715 a[from] = v0; | 714 a[from] = v0; |
716 a[to - 1] = v2; | 715 a[to - 1] = v2; |
717 var pivot = v1; | 716 var pivot = v1; |
718 var low_end = from + 1; // Upper bound of the elements lower than pivot. | 717 var low_end = from + 1; // Upper bound of elements lower than pivot. |
719 var high_start = to - 1; // Lower bound of the elements greater than pivot. | 718 var high_start = to - 1; // Lower bound of elements greater than pivot. |
720 a[middle_index] = a[low_end]; | 719 a[middle_index] = a[low_end]; |
721 a[low_end] = pivot; | 720 a[low_end] = pivot; |
722 | 721 |
723 // From low_end to i are elements equal to pivot. | 722 // From low_end to i are elements equal to pivot. |
724 // From i to high_start are elements that haven't been compared yet. | 723 // From i to high_start are elements that haven't been compared yet. |
725 for (var i = low_end + 1; i < high_start; ) { | 724 partition: for (var i = low_end + 1; i < high_start; ) { |
Karl Klose
2010/12/20 14:28:43
Increase i here instead of at the end of the loop?
Lasse Reichstein
2010/12/20 15:00:59
Good point!
| |
726 var element = a[i]; | 725 var element = a[i]; |
727 var order = %_CallFunction(global_receiver, element, pivot, comparefn); | 726 var order = %_CallFunction(global_receiver, element, pivot, comparefn); |
728 if (order < 0) { | 727 if (order < 0) { |
729 %_SwapElements(a, i, low_end); | 728 %_SwapElements(a, i, low_end); |
730 i++; | |
731 low_end++; | 729 low_end++; |
732 } else if (order > 0) { | 730 } else if (order > 0) { |
733 high_start--; | 731 do { |
732 high_start--; | |
733 if (high_start == i) break partition; | |
734 var top_elem = a[high_start]; | |
735 order = %_CallFunction(global_receiver, top_elem, pivot, comparefn); | |
736 } while (order > 0); | |
734 %_SwapElements(a, i, high_start); | 737 %_SwapElements(a, i, high_start); |
735 } else { // order == 0 | 738 if (order < 0) { |
736 i++; | 739 %_SwapElements(a, i, low_end); |
740 low_end++; | |
741 } | |
737 } | 742 } |
743 i++; | |
738 } | 744 } |
739 QuickSort(a, from, low_end); | 745 QuickSort(a, from, low_end); |
740 QuickSort(a, high_start, to); | 746 QuickSort(a, high_start, to); |
741 } | 747 } |
742 | 748 |
743 // Copy elements in the range 0..length from obj's prototype chain | 749 // Copy elements in the range 0..length from obj's prototype chain |
744 // to obj itself, if obj has holes. Return one more than the maximal index | 750 // to obj itself, if obj has holes. Return one more than the maximal index |
745 // of a prototype property. | 751 // of a prototype property. |
746 function CopyFromPrototype(obj, length) { | 752 function CopyFromPrototype(obj, length) { |
747 var max = 0; | 753 var max = 0; |
(...skipping 456 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1204 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), | 1210 "lastIndexOf", getFunction("lastIndexOf", ArrayLastIndexOf, 1), |
1205 "reduce", getFunction("reduce", ArrayReduce, 1), | 1211 "reduce", getFunction("reduce", ArrayReduce, 1), |
1206 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) | 1212 "reduceRight", getFunction("reduceRight", ArrayReduceRight, 1) |
1207 )); | 1213 )); |
1208 | 1214 |
1209 %FinishArrayPrototypeSetup($Array.prototype); | 1215 %FinishArrayPrototypeSetup($Array.prototype); |
1210 } | 1216 } |
1211 | 1217 |
1212 | 1218 |
1213 SetupArray(); | 1219 SetupArray(); |
OLD | NEW |