/src/php-src/Zend/zend_sort.c
Line | Count | Source (jump to first uncovered line) |
1 | | /* |
2 | | +----------------------------------------------------------------------+ |
3 | | | Zend Engine | |
4 | | +----------------------------------------------------------------------+ |
5 | | | Copyright (c) Zend Technologies Ltd. (http://www.zend.com) | |
6 | | +----------------------------------------------------------------------+ |
7 | | | This source file is subject to version 2.00 of the Zend license, | |
8 | | | that is bundled with this package in the file LICENSE, and is | |
9 | | | available through the world-wide-web at the following url: | |
10 | | | http://www.zend.com/license/2_00.txt. | |
11 | | | If you did not receive a copy of the Zend license and are unable to | |
12 | | | obtain it through the world-wide-web, please send a note to | |
13 | | | license@zend.com so we can mail you a copy immediately. | |
14 | | +----------------------------------------------------------------------+ |
15 | | | Authors: Xinchen Hui <laruence@php.net> | |
16 | | | Sterling Hughes <sterling@php.net> | |
17 | | +----------------------------------------------------------------------+ |
18 | | */ |
19 | | |
20 | | #include "zend.h" |
21 | | #include "zend_sort.h" |
22 | | #include <limits.h> |
23 | | |
24 | 5.39k | static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ { |
25 | 5.39k | if (cmp(a, b) > 0) { |
26 | 3.28k | swp(a, b); |
27 | 3.28k | } |
28 | 5.39k | } |
29 | | /* }}} */ |
30 | | |
31 | 133k | static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ { |
32 | 133k | if (!(cmp(a, b) > 0)) { |
33 | 43.5k | if (!(cmp(b, c) > 0)) { |
34 | 23.0k | return; |
35 | 23.0k | } |
36 | 20.5k | swp(b, c); |
37 | 20.5k | if (cmp(a, b) > 0) { |
38 | 9.09k | swp(a, b); |
39 | 9.09k | } |
40 | 20.5k | return; |
41 | 43.5k | } |
42 | 89.9k | if (!(cmp(c, b) > 0)) { |
43 | 9.47k | swp(a, c); |
44 | 9.47k | return; |
45 | 9.47k | } |
46 | 80.5k | swp(a, b); |
47 | 80.5k | if (cmp(b, c) > 0) { |
48 | 41.5k | swp(b, c); |
49 | 41.5k | } |
50 | 80.5k | } |
51 | | /* }}} */ |
52 | | |
53 | 19.2k | static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ { |
54 | 19.2k | zend_sort_3(a, b, c, cmp, swp); |
55 | 19.2k | if (cmp(c, d) > 0) { |
56 | 12.8k | swp(c, d); |
57 | 12.8k | if (cmp(b, c) > 0) { |
58 | 4.31k | swp(b, c); |
59 | 4.31k | if (cmp(a, b) > 0) { |
60 | 2.24k | swp(a, b); |
61 | 2.24k | } |
62 | 4.31k | } |
63 | 12.8k | } |
64 | 19.2k | } |
65 | | /* }}} */ |
66 | | |
67 | 12.6k | static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ { |
68 | 12.6k | zend_sort_4(a, b, c, d, cmp, swp); |
69 | 12.6k | if (cmp(d, e) > 0) { |
70 | 10.9k | swp(d, e); |
71 | 10.9k | if (cmp(c, d) > 0) { |
72 | 10.3k | swp(c, d); |
73 | 10.3k | if (cmp(b, c) > 0) { |
74 | 1.57k | swp(b, c); |
75 | 1.57k | if (cmp(a, b) > 0) { |
76 | 864 | swp(a, b); |
77 | 864 | } |
78 | 1.57k | } |
79 | 10.3k | } |
80 | 10.9k | } |
81 | 12.6k | } |
82 | | /* }}} */ |
83 | | |
84 | 109k | ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{ |
85 | 109k | switch (nmemb) { |
86 | 0 | case 0: |
87 | 4.34k | case 1: |
88 | 4.34k | break; |
89 | 5.39k | case 2: |
90 | 5.39k | zend_sort_2(base, (char *)base + siz, cmp, swp); |
91 | 5.39k | break; |
92 | 10.1k | case 3: |
93 | 10.1k | zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp); |
94 | 10.1k | break; |
95 | 6.65k | case 4: |
96 | 6.65k | { |
97 | 6.65k | size_t siz2 = siz + siz; |
98 | 6.65k | zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp); |
99 | 6.65k | } |
100 | 6.65k | break; |
101 | 11.5k | case 5: |
102 | 11.5k | { |
103 | 11.5k | size_t siz2 = siz + siz; |
104 | 11.5k | zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp); |
105 | 11.5k | } |
106 | 11.5k | break; |
107 | 71.7k | default: |
108 | 71.7k | { |
109 | 71.7k | char *i, *j, *k; |
110 | 71.7k | char *start = (char *)base; |
111 | 71.7k | char *end = start + (nmemb * siz); |
112 | 71.7k | size_t siz2= siz + siz; |
113 | 71.7k | char *sentry = start + (6 * siz); |
114 | 430k | for (i = start + siz; i < sentry; i += siz) { |
115 | 358k | j = i - siz; |
116 | 358k | if (!(cmp(j, i) > 0)) { |
117 | 146k | continue; |
118 | 146k | } |
119 | 458k | while (j != start) { |
120 | 375k | j -= siz; |
121 | 375k | if (!(cmp(j, i) > 0)) { |
122 | 130k | j += siz; |
123 | 130k | break; |
124 | 130k | } |
125 | 375k | } |
126 | 670k | for (k = i; k > j; k -= siz) { |
127 | 458k | swp(k, k - siz); |
128 | 458k | } |
129 | 212k | } |
130 | 451k | for (i = sentry; i < end; i += siz) { |
131 | 379k | j = i - siz; |
132 | 379k | if (!(cmp(j, i) > 0)) { |
133 | 81.8k | continue; |
134 | 81.8k | } |
135 | 708k | do { |
136 | 708k | j -= siz2; |
137 | 708k | if (!(cmp(j, i) > 0)) { |
138 | 247k | j += siz; |
139 | 247k | if (!(cmp(j, i) > 0)) { |
140 | 155k | j += siz; |
141 | 155k | } |
142 | 247k | break; |
143 | 247k | } |
144 | 461k | if (j == start) { |
145 | 13.9k | break; |
146 | 13.9k | } |
147 | 447k | if (j == start + siz) { |
148 | 36.7k | j -= siz; |
149 | 36.7k | if (cmp(i, j) > 0) { |
150 | 19.7k | j += siz; |
151 | 19.7k | } |
152 | 36.7k | break; |
153 | 36.7k | } |
154 | 447k | } while (1); |
155 | 1.62M | for (k = i; k > j; k -= siz) { |
156 | 1.32M | swp(k, k - siz); |
157 | 1.32M | } |
158 | 297k | } |
159 | 71.7k | } |
160 | 71.7k | break; |
161 | 109k | } |
162 | 109k | } |
163 | | /* }}} */ |
164 | | |
165 | | /* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) |
166 | | * |
167 | | * Derived from LLVM's libc++ implementation of std::sort. |
168 | | * |
169 | | * =========================================================================== |
170 | | * libc++ License |
171 | | * =========================================================================== |
172 | | * |
173 | | * The libc++ library is dual licensed under both the University of Illinois |
174 | | * "BSD-Like" license and the MIT license. As a user of this code you may |
175 | | * choose to use it under either license. As a contributor, you agree to allow |
176 | | * your code to be used under both. |
177 | | * |
178 | | * Full text of the relevant licenses is included below. |
179 | | * |
180 | | * =========================================================================== |
181 | | * |
182 | | * University of Illinois/NCSA |
183 | | * Open Source License |
184 | | * |
185 | | * Copyright (c) 2009-2012 by the contributors listed at |
186 | | * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT |
187 | | * |
188 | | * All rights reserved. |
189 | | * |
190 | | * Developed by: |
191 | | * |
192 | | * LLVM Team |
193 | | * |
194 | | * University of Illinois at Urbana-Champaign |
195 | | * |
196 | | * http://llvm.org |
197 | | * |
198 | | * Permission is hereby granted, free of charge, to any person obtaining a copy |
199 | | * of this software and associated documentation files (the "Software"), to |
200 | | * deal with the Software without restriction, including without limitation the |
201 | | * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or |
202 | | * sell copies of the Software, and to permit persons to whom the Software is |
203 | | * furnished to do so, subject to the following conditions: |
204 | | * |
205 | | * * Redistributions of source code must retain the above copyright notice, |
206 | | * this list of conditions and the following disclaimers. |
207 | | * |
208 | | * * Redistributions in binary form must reproduce the above copyright |
209 | | * notice, this list of conditions and the following disclaimers in the |
210 | | * documentation and/or other materials provided with the distribution. |
211 | | * |
212 | | * * Neither the names of the LLVM Team, University of Illinois at |
213 | | * Urbana-Champaign, nor the names of its contributors may be used to |
214 | | * endorse or promote products derived from this Software without |
215 | | * specific prior written permission. |
216 | | * |
217 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
218 | | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
219 | | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
220 | | * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
221 | | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
222 | | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
223 | | * WITH THE SOFTWARE. |
224 | | * |
225 | | * =========================================================================== |
226 | | * |
227 | | * Copyright (c) 2009-2012 by the contributors listed at |
228 | | * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT |
229 | | * |
230 | | * Permission is hereby granted, free of charge, to any person obtaining a copy |
231 | | * of this software and associated documentation files (the "Software"), to |
232 | | * deal in the Software without restriction, including without limitation the |
233 | | * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or |
234 | | * sell copies of the Software, and to permit persons to whom the Software is |
235 | | * furnished to do so, subject to the following conditions: |
236 | | * |
237 | | * The above copyright notice and this permission notice shall be included in |
238 | | * all copies or substantial portions of the Software. |
239 | | * |
240 | | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
241 | | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
242 | | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE |
243 | | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
244 | | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
245 | | * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS |
246 | | * IN THE SOFTWARE. |
247 | | */ |
248 | | ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) |
249 | 109k | { |
250 | 215k | while (1) { |
251 | 215k | if (nmemb <= 16) { |
252 | 109k | zend_insert_sort(base, nmemb, siz, cmp, swp); |
253 | 109k | return; |
254 | 109k | } else { |
255 | 105k | char *i, *j; |
256 | 105k | char *start = (char *)base; |
257 | 105k | char *end = start + (nmemb * siz); |
258 | 105k | size_t offset = (nmemb >> Z_L(1)); |
259 | 105k | char *pivot = start + (offset * siz); |
260 | | |
261 | 105k | if ((nmemb >> Z_L(10))) { |
262 | 1.08k | size_t delta = (offset >> Z_L(1)) * siz; |
263 | 1.08k | zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp); |
264 | 104k | } else { |
265 | 104k | zend_sort_3(start, pivot, end - siz, cmp, swp); |
266 | 104k | } |
267 | 105k | swp(start + siz, pivot); |
268 | 105k | pivot = start + siz; |
269 | 105k | i = pivot + siz; |
270 | 105k | j = end - siz; |
271 | 812k | while (1) { |
272 | 6.15M | while (cmp(pivot, i) > 0) { |
273 | 5.40M | i += siz; |
274 | 5.40M | if (UNEXPECTED(i == j)) { |
275 | 63.7k | goto done; |
276 | 63.7k | } |
277 | 5.40M | } |
278 | 748k | j -= siz; |
279 | 748k | if (UNEXPECTED(j == i)) { |
280 | 13.3k | goto done; |
281 | 13.3k | } |
282 | 3.64M | while (cmp(j, pivot) > 0) { |
283 | 2.92M | j -= siz; |
284 | 2.92M | if (UNEXPECTED(j == i)) { |
285 | 17.4k | goto done; |
286 | 17.4k | } |
287 | 2.92M | } |
288 | 717k | swp(i, j); |
289 | 717k | i += siz; |
290 | 717k | if (UNEXPECTED(i == j)) { |
291 | 10.7k | goto done; |
292 | 10.7k | } |
293 | 717k | } |
294 | 105k | done: |
295 | 105k | swp(pivot, i - siz); |
296 | 105k | if ((i - siz) - start < end - i) { |
297 | 42.6k | zend_sort(start, (i - start)/siz - 1, siz, cmp, swp); |
298 | 42.6k | base = i; |
299 | 42.6k | nmemb = (end - i)/siz; |
300 | 62.5k | } else { |
301 | 62.5k | zend_sort(i, (end - i)/siz, siz, cmp, swp); |
302 | 62.5k | nmemb = (i - start)/siz - 1; |
303 | 62.5k | } |
304 | 105k | } |
305 | 215k | } |
306 | 109k | } |
307 | | /* }}} */ |