From 43a97878ce14b72f0981164f87f2e35e14151312 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 11:22:09 +0200 Subject: Adding upstream version 110.0.1. Signed-off-by: Daniel Baumann --- js/src/builtin/Sorting.js | 215 ++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 215 insertions(+) create mode 100644 js/src/builtin/Sorting.js (limited to 'js/src/builtin/Sorting.js') diff --git a/js/src/builtin/Sorting.js b/js/src/builtin/Sorting.js new file mode 100644 index 0000000000..faa31349c0 --- /dev/null +++ b/js/src/builtin/Sorting.js @@ -0,0 +1,215 @@ +/* This Source Code Form is subject to the terms of the Mozilla Public + * License, v. 2.0. If a copy of the MPL was not distributed with this + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ + +// We use varying sorts across the self-hosted codebase. All sorts are +// consolidated here to avoid confusion and re-implementation of existing +// algorithms. + +// For sorting small arrays. +function InsertionSort(array, from, to, comparefn) { + let item, swap, i, j; + for (i = from + 1; i <= to; i++) { + item = array[i]; + for (j = i - 1; j >= from; j--) { + swap = array[j]; + if (callContentFunction(comparefn, undefined, swap, item) <= 0) { + break; + } + array[j + 1] = swap; + } + array[j + 1] = item; + } +} + +// A helper function for MergeSort. +// +// Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end], +// storing the merged sequence in out[start..<=end]. +function Merge(list, out, start, mid, end, comparefn) { + // Skip lopsided runs to avoid doing useless work. + // Skip calling the comparator if the sub-list is already sorted. + if ( + mid >= end || + callContentFunction(comparefn, undefined, list[mid], list[mid + 1]) <= 0 + ) { + for (var i = start; i <= end; i++) { + DefineDataProperty(out, i, list[i]); + } + return; + } + + var i = start; + var j = mid + 1; + var k = start; + while (i <= mid && j <= end) { + var lvalue = list[i]; + var rvalue = list[j]; + if (callContentFunction(comparefn, undefined, lvalue, rvalue) <= 0) { + DefineDataProperty(out, k++, lvalue); + i++; + } else { + DefineDataProperty(out, k++, rvalue); + j++; + } + } + + // Empty out any remaining elements. + while (i <= mid) { + DefineDataProperty(out, k++, list[i++]); + } + while (j <= end) { + DefineDataProperty(out, k++, list[j++]); + } +} + +// Helper function for overwriting a sparse array with a +// dense array, filling remaining slots with holes. +function MoveHoles(sparse, sparseLen, dense, denseLen) { + for (var i = 0; i < denseLen; i++) { + sparse[i] = dense[i]; + } + for (var j = denseLen; j < sparseLen; j++) { + delete sparse[j]; + } +} + +// Iterative, bottom up, mergesort. +function MergeSort(array, len, comparefn) { + assert(IsPackedArray(array), "array is packed"); + assert(array.length === len, "length mismatch"); + assert(len > 0, "array should be non-empty"); + + // Insertion sort for small arrays, where "small" is defined by performance + // testing. + if (len < 24) { + InsertionSort(array, 0, len - 1, comparefn); + return array; + } + + // We do all of our allocating up front + var lBuffer = array; + var rBuffer = []; + + // Use insertion sort for initial ranges. + var windowSize = 4; + for (var start = 0; start < len - 1; start += windowSize) { + var end = std_Math_min(start + windowSize - 1, len - 1); + InsertionSort(lBuffer, start, end, comparefn); + } + + for (; windowSize < len; windowSize = 2 * windowSize) { + for (var start = 0; start < len; start += 2 * windowSize) { + // The midpoint between the two subarrays. + var mid = start + windowSize - 1; + + // To keep from going over the edge. + var end = std_Math_min(start + 2 * windowSize - 1, len - 1); + + Merge(lBuffer, rBuffer, start, mid, end, comparefn); + } + + // Swap both lists. + var swap = lBuffer; + lBuffer = rBuffer; + rBuffer = swap; + } + return lBuffer; +} + +// A helper function for MergeSortTypedArray. +// +// Merge comparefn-sorted slices list[start..<=mid] and list[mid+1..<=end], +// storing the merged sequence in out[start..<=end]. +function MergeTypedArray(list, out, start, mid, end, comparefn) { + // Skip lopsided runs to avoid doing useless work. + // Skip calling the comparator if the sub-list is already sorted. + if ( + mid >= end || + callContentFunction(comparefn, undefined, list[mid], list[mid + 1]) <= 0 + ) { + for (var i = start; i <= end; i++) { + out[i] = list[i]; + } + return; + } + + var i = start; + var j = mid + 1; + var k = start; + while (i <= mid && j <= end) { + var lvalue = list[i]; + var rvalue = list[j]; + if (callContentFunction(comparefn, undefined, lvalue, rvalue) <= 0) { + out[k++] = lvalue; + i++; + } else { + out[k++] = rvalue; + j++; + } + } + + // Empty out any remaining elements. + while (i <= mid) { + out[k++] = list[i++]; + } + while (j <= end) { + out[k++] = list[j++]; + } +} + +// Iterative, bottom up, mergesort. Optimized version for TypedArrays. +function MergeSortTypedArray(array, len, comparefn) { + assert( + IsPossiblyWrappedTypedArray(array), + "MergeSortTypedArray works only with typed arrays." + ); + + // Use the same TypedArray kind for the buffer. + var C = ConstructorForTypedArray(array); + + var lBuffer = new C(len); + + // Copy all elements into a temporary buffer, so that any modifications + // when calling |comparefn| are ignored. + for (var i = 0; i < len; i++) { + lBuffer[i] = array[i]; + } + + // Insertion sort for small arrays, where "small" is defined by performance + // testing. + if (len < 8) { + InsertionSort(lBuffer, 0, len - 1, comparefn); + + return lBuffer; + } + + // We do all of our allocating up front. + var rBuffer = new C(len); + + // Use insertion sort for the initial ranges. + var windowSize = 4; + for (var start = 0; start < len - 1; start += windowSize) { + var end = std_Math_min(start + windowSize - 1, len - 1); + InsertionSort(lBuffer, start, end, comparefn); + } + + for (; windowSize < len; windowSize = 2 * windowSize) { + for (var start = 0; start < len; start += 2 * windowSize) { + // The midpoint between the two subarrays. + var mid = start + windowSize - 1; + + // To keep from going over the edge. + var end = std_Math_min(start + 2 * windowSize - 1, len - 1); + + MergeTypedArray(lBuffer, rBuffer, start, mid, end, comparefn); + } + + // Swap both lists. + var swap = lBuffer; + lBuffer = rBuffer; + rBuffer = swap; + } + + return lBuffer; +} -- cgit v1.2.3