1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
|
/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
* 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/. */
#ifndef ds_Sort_h
#define ds_Sort_h
#include "jstypes.h"
namespace js {
namespace detail {
template<typename T>
MOZ_ALWAYS_INLINE void
CopyNonEmptyArray(T* dst, const T* src, size_t nelems)
{
MOZ_ASSERT(nelems != 0);
const T* end = src + nelems;
do {
*dst++ = *src++;
} while (src != end);
}
/* Helper function for MergeSort. */
template<typename T, typename Comparator>
MOZ_ALWAYS_INLINE bool
MergeArrayRuns(T* dst, const T* src, size_t run1, size_t run2, Comparator c)
{
MOZ_ASSERT(run1 >= 1);
MOZ_ASSERT(run2 >= 1);
/* Copy runs already in sorted order. */
const T* b = src + run1;
bool lessOrEqual;
if (!c(b[-1], b[0], &lessOrEqual))
return false;
if (!lessOrEqual) {
/* Runs are not already sorted, merge them. */
for (const T* a = src;;) {
if (!c(*a, *b, &lessOrEqual))
return false;
if (lessOrEqual) {
*dst++ = *a++;
if (!--run1) {
src = b;
break;
}
} else {
*dst++ = *b++;
if (!--run2) {
src = a;
break;
}
}
}
}
CopyNonEmptyArray(dst, src, run1 + run2);
return true;
}
} /* namespace detail */
/*
* Sort the array using the merge sort algorithm. The scratch should point to
* a temporary storage that can hold nelems elements.
*
* The comparator must provide the () operator with the following signature:
*
* bool operator()(const T& a, const T& a, bool* lessOrEqualp);
*
* It should return true on success and set *lessOrEqualp to the result of
* a <= b operation. If it returns false, the sort terminates immediately with
* the false result. In this case the content of the array and scratch is
* arbitrary.
*/
template<typename T, typename Comparator>
[[nodiscard]] bool
MergeSort(T* array, size_t nelems, T* scratch, Comparator c)
{
const size_t INS_SORT_LIMIT = 3;
if (nelems <= 1)
return true;
/*
* Apply insertion sort to small chunks to reduce the number of merge
* passes needed.
*/
for (size_t lo = 0; lo < nelems; lo += INS_SORT_LIMIT) {
size_t hi = lo + INS_SORT_LIMIT;
if (hi >= nelems)
hi = nelems;
for (size_t i = lo + 1; i != hi; i++) {
for (size_t j = i; ;) {
bool lessOrEqual;
if (!c(array[j - 1], array[j], &lessOrEqual))
return false;
if (lessOrEqual)
break;
T tmp = array[j - 1];
array[j - 1] = array[j];
array[j] = tmp;
if (--j == lo)
break;
}
}
}
T* vec1 = array;
T* vec2 = scratch;
for (size_t run = INS_SORT_LIMIT; run < nelems; run *= 2) {
for (size_t lo = 0; lo < nelems; lo += 2 * run) {
size_t hi = lo + run;
if (hi >= nelems) {
detail::CopyNonEmptyArray(vec2 + lo, vec1 + lo, nelems - lo);
break;
}
size_t run2 = (run <= nelems - hi) ? run : nelems - hi;
if (!detail::MergeArrayRuns(vec2 + lo, vec1 + lo, run, run2, c))
return false;
}
T* swap = vec1;
vec1 = vec2;
vec2 = swap;
}
if (vec1 == scratch)
detail::CopyNonEmptyArray(array, scratch, nelems);
return true;
}
} /* namespace js */
#endif /* ds_Sort_h */
|
