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.
112 #ifndef incl_HPHP_SAFESORT_H_
113 #define incl_HPHP_SAFESORT_H_
120 template <class GtCompT
, class IterT
>
121 void sort3(IterT x
, IterT y
, IterT z
, GtCompT gt
) {
142 template <class GtCompT
, class IterT
>
143 void sort4(IterT x1
, IterT x2
, IterT x3
, IterT x4
, GtCompT gt
) {
145 sort3
<GtCompT
>(x1
, x2
, x3
, gt
);
157 template <class GtCompT
, class IterT
>
158 void sort5(IterT x1
, IterT x2
, IterT x3
, IterT x4
, IterT x5
, GtCompT gt
) {
160 sort4
<GtCompT
>(x1
, x2
, x3
, x4
, gt
);
175 template <class GtCompT
, class IterT
>
176 void insertion_sort(IterT first
, IterT last
, GtCompT gt
) {
177 typedef typename
std::iterator_traits
<IterT
>::value_type value_type
;
178 typedef typename
std::iterator_traits
<IterT
>::difference_type
180 difference_type len
= last
- first
;
182 // If there aren't at least 2 elements, we're done
185 // Loop over the first six elements
188 IterT l
= (len
< 6) ? last
: first
+6;
189 for (; i
!= l
; ++i
) {
192 // If this element is not less than the element
193 // immediately before it, then we can leave this
194 // element where it is for now
197 // Scan backward one element at a time looking
198 // for the earliest element that *i is less than
211 for (IterT k
= i
; k
!= j
; --k
) {
216 // Loop over the remaining elements
217 IterT second
= first
;
219 for (; i
!= last
; ++i
) {
222 // If this element is not less than the element
223 // immediately before it, then we can leave this
224 // element where it is for now
227 // Scan backward two elements at a time looking
228 // for the earliest element that *i is less than
230 // Invariant: j >= first && *i < *j
232 // j points to first or second, so we have
233 // reached the end of the loop
235 // If j points to second, we need to test
236 // if *i is less than *first
245 // Move backward by two
248 // If (*i < *k) is false, we know that *(k+1) or
249 // *(k+2) is the element we are looking for.
259 // Move *i to temporary t, move the elements in the
260 // range [j,i) over to the right one position, and
263 for (IterT m
= i
; m
!= j
; --m
) {
270 template <class GtCompT
, class IterT
>
271 void sort(IterT first
, IterT last
, GtCompT gt
) {
272 typedef typename
std::iterator_traits
<IterT
>::difference_type
276 difference_type len
= last
- first
;
277 // For small numbers of elements, use insertion sort
279 insertion_sort
<GtCompT
>(first
, last
, gt
);
286 difference_type delta
= len
/2;
287 pivot
= first
+ delta
;
289 // Compute the median of 5
291 sort5
<GtCompT
>(first
, first
+ delta
, pivot
, pivot
+delta
, lm1
, gt
);
293 // Compute the median of 3
294 sort3
<GtCompT
>(first
, pivot
, lm1
, gt
);
296 // Temporarily move the pivot to the second position
297 swap(*(first
+1), *pivot
);
300 // Split the elements into two partitions (excluding the pivot);
301 // we don't have to inspect the first element and last element
302 // because they've already been put in the right place by the
303 // call to sort3/sort5 above
307 while (gt(*pivot
, *i
)) {
309 if (UNLIKELY(i
== j
)) {
314 if (UNLIKELY(i
== j
)) {
317 while (gt(*j
, *pivot
)) {
319 if (UNLIKELY(i
== j
)) {
325 if (UNLIKELY(i
== j
)) {
330 // Put the pivot in between the left partition and right partition
331 swap(*pivot
, *(i
-1));
332 // We now have the left partition in [first,i-1) and we have the
333 // right parition in [i,last). Sort smaller partition with recursive
334 // call and sort the larger partition with tail recursion elimination
335 if ((i
-1) - first
< last
- i
) {
336 sort
<GtCompT
>(first
, i
-1, gt
);
339 sort
<GtCompT
>(i
, last
, gt
);
348 #endif // incl_HPHP_SAFESORT_H_