2 * ===========================================================================
4 * ===========================================================================
6 * The libc++ library is dual licensed under both the University of Illinois
7 * "BSD-Like" license and the MIT license. As a user of this code you may
8 * choose to use it under either license. As a contributor, you agree to allow
9 * your code to be used under both.
11 * Full text of the relevant licenses is included below.
13 * ===========================================================================
15 * University of Illinois/NCSA
18 * Copyright (c) 2009-2012 by the contributors listed at
19 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
21 * All rights reserved.
27 * University of Illinois at Urbana-Champaign
31 * Permission is hereby granted, free of charge, to any person obtaining a copy
32 * of this software and associated documentation files (the "Software"), to
33 * deal with the Software without restriction, including without limitation the
34 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
35 * sell copies of the Software, and to permit persons to whom the Software is
36 * furnished to do so, subject to the following conditions:
38 * * Redistributions of source code must retain the above copyright notice,
39 * this list of conditions and the following disclaimers.
41 * * Redistributions in binary form must reproduce the above copyright
42 * notice, this list of conditions and the following disclaimers in the
43 * documentation and/or other materials provided with the distribution.
45 * * Neither the names of the LLVM Team, University of Illinois at
46 * Urbana-Champaign, nor the names of its contributors may be used to
47 * endorse or promote products derived from this Software without
48 * specific prior written permission.
50 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
51 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
52 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
53 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
54 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
55 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
58 * ===========================================================================
60 * Copyright (c) 2009-2012 by the contributors listed at
61 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
63 * Permission is hereby granted, free of charge, to any person obtaining a copy
64 * of this software and associated documentation files (the "Software"), to
65 * deal in the Software without restriction, including without limitation the
66 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
67 * sell copies of the Software, and to permit persons to whom the Software is
68 * furnished to do so, subject to the following conditions:
70 * The above copyright notice and this permission notice shall be included in
71 * all copies or substantial portions of the Software.
73 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
74 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
75 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
76 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
77 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
78 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
85 * The safesort algorithm below is based on LLVM's libc++ implementation
88 * One key difference is that safesort is safe to use with a comparator
89 * that does not impose a strict weak ordering on the elements (whereas
90 * std::sort may crash or go into infinite loops for such comparators).
91 * Safesoft is also "exception safe", leaving the array in a consistent
92 * state in the event that the comparator throws. This is important for
93 * HHVM for several reasons. Some of the builtin comparators in PHP do
94 * not impose a strict weak ordereding (ex. SORT_REGULAR over strings).
95 * Also, user code can supply comparators that behave inconsistently or
98 * In cases where the comparator does not impose a strict weak ordering
99 * or the comparator throws, no guarantees are made about the order of
100 * the elements produced the sort algorithm, though the algorithm still
101 * upholds a weaker guarantee that the result will be some permutation
104 * Another import difference is that safesort assumes the comparator
105 * returns true if the left argument is GREATER than the right argument.
106 * This is the opposite of what the STL's sort implementation does, and
107 * we do it because it helps HHVM be more compatible with existing PHP
108 * programs that (inadvertently) depend on unspecified behavior of the
109 * PHP5 implementation.
119 template <class GtCompT
, class IterT
>
120 void sort3(IterT x
, IterT y
, IterT z
, GtCompT gt
) {
141 template <class GtCompT
, class IterT
>
142 void sort4(IterT x1
, IterT x2
, IterT x3
, IterT x4
, GtCompT gt
) {
144 sort3
<GtCompT
>(x1
, x2
, x3
, gt
);
156 template <class GtCompT
, class IterT
>
157 void sort5(IterT x1
, IterT x2
, IterT x3
, IterT x4
, IterT x5
, GtCompT gt
) {
159 sort4
<GtCompT
>(x1
, x2
, x3
, x4
, gt
);
174 template <class GtCompT
, class IterT
>
175 void insertion_sort(IterT first
, IterT last
, GtCompT gt
) {
176 typedef typename
std::iterator_traits
<IterT
>::value_type value_type
;
177 typedef typename
std::iterator_traits
<IterT
>::difference_type
179 difference_type len
= last
- first
;
181 // If there aren't at least 2 elements, we're done
184 // Loop over the first six elements
187 IterT l
= (len
< 6) ? last
: first
+6;
188 for (; i
!= l
; ++i
) {
191 // If this element is not less than the element
192 // immediately before it, then we can leave this
193 // element where it is for now
196 // Scan backward one element at a time looking
197 // for the earliest element that *i is less than
210 for (IterT k
= i
; k
!= j
; --k
) {
215 // Loop over the remaining elements
216 IterT second
= first
;
218 for (; i
!= last
; ++i
) {
221 // If this element is not less than the element
222 // immediately before it, then we can leave this
223 // element where it is for now
226 // Scan backward two elements at a time looking
227 // for the earliest element that *i is less than
229 // Invariant: j >= first && *i < *j
231 // j points to first or second, so we have
232 // reached the end of the loop
234 // If j points to second, we need to test
235 // if *i is less than *first
244 // Move backward by two
247 // If (*i < *k) is false, we know that *(k+1) or
248 // *(k+2) is the element we are looking for.
258 // Move *i to temporary t, move the elements in the
259 // range [j,i) over to the right one position, and
262 for (IterT m
= i
; m
!= j
; --m
) {
269 template <class GtCompT
, class IterT
>
270 void sort(IterT first
, IterT last
, GtCompT gt
) {
271 typedef typename
std::iterator_traits
<IterT
>::difference_type
275 difference_type len
= last
- first
;
276 // For small numbers of elements, use insertion sort
278 insertion_sort
<GtCompT
>(first
, last
, gt
);
285 difference_type delta
= len
/2;
286 pivot
= first
+ delta
;
288 // Compute the median of 5
290 sort5
<GtCompT
>(first
, first
+ delta
, pivot
, pivot
+delta
, lm1
, gt
);
292 // Compute the median of 3
293 sort3
<GtCompT
>(first
, pivot
, lm1
, gt
);
295 // Temporarily move the pivot to the second position
296 swap(*(first
+1), *pivot
);
299 // Split the elements into two partitions (excluding the pivot);
300 // we don't have to inspect the first element and last element
301 // because they've already been put in the right place by the
302 // call to sort3/sort5 above
306 while (gt(*pivot
, *i
)) {
308 if (UNLIKELY(i
== j
)) {
313 if (UNLIKELY(i
== j
)) {
316 while (gt(*j
, *pivot
)) {
318 if (UNLIKELY(i
== j
)) {
324 if (UNLIKELY(i
== j
)) {
329 // Put the pivot in between the left partition and right partition
330 swap(*pivot
, *(i
-1));
331 // We now have the left partition in [first,i-1) and we have the
332 // right parition in [i,last). Sort smaller partition with recursive
333 // call and sort the larger partition with tail recursion elimination
334 if ((i
-1) - first
< last
- i
) {
335 sort
<GtCompT
>(first
, i
-1, gt
);
338 sort
<GtCompT
>(i
, last
, gt
);