1 /*
2 +----------------------------------------------------------------------+
3 | Zend Engine |
4 +----------------------------------------------------------------------+
5 | Copyright (c) 1998-2016 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 /* $Id$ */
21
22 #include "zend.h"
23 #include "zend_sort.h"
24 #include <limits.h>
25
26 #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT)
27
28 ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */
29 {
30 void *begin_stack[QSORT_STACK_SIZE];
31 void *end_stack[QSORT_STACK_SIZE];
32 register char *begin;
33 register char *end;
34 register char *seg1;
35 register char *seg2;
36 register char *seg2p;
37 register int loop;
38 size_t offset;
39
40 begin_stack[0] = (char *) base;
41 end_stack[0] = (char *) base + ((nmemb - 1) * siz);
42
43 for (loop = 0; loop >= 0; --loop) {
44 begin = begin_stack[loop];
45 end = end_stack[loop];
46
47 while (begin < end) {
48 offset = (end - begin) >> Z_L(1);
49 swp(begin, begin + (offset - (offset % siz)));
50
51 seg1 = begin + siz;
52 seg2 = end;
53
54 while (1) {
55 for (; seg1 < seg2 && compare(begin, seg1) > 0;
56 seg1 += siz);
57
58 for (; seg2 >= seg1 && compare(seg2, begin) > 0;
59 seg2 -= siz);
60
61 if (seg1 >= seg2)
62 break;
63
64 swp(seg1, seg2);
65
66 seg1 += siz;
67 seg2 -= siz;
68 }
69
70 swp(begin, seg2);
71
72 seg2p = seg2;
73
74 if ((seg2p - begin) <= (end - seg2p)) {
75 if ((seg2p + siz) < end) {
76 begin_stack[loop] = seg2p + siz;
77 end_stack[loop++] = end;
78 }
79 end = seg2p - siz;
80 }
81 else {
82 if ((seg2p - siz) > begin) {
83 begin_stack[loop] = begin;
84 end_stack[loop++] = seg2p - siz;
85 }
86 begin = seg2p + siz;
87 }
88 }
89 }
90 }
91 /* }}} */
92
93 static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
94 if (cmp(a, b) > 0) {
95 swp(a, b);
96 }
97 }
98 /* }}} */
99
100 static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
101 if (!(cmp(a, b) > 0)) {
102 if (!(cmp(b, c) > 0)) {
103 return;
104 }
105 swp(b, c);
106 if (cmp(a, b) > 0) {
107 swp(a, b);
108 }
109 return;
110 }
111 if (!(cmp(c, b) > 0)) {
112 swp(a, c);
113 return;
114 }
115 swp(a, b);
116 if (cmp(b, c) > 0) {
117 swp(b, c);
118 }
119 }
120 /* }}} */
121
122 static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
123 zend_sort_3(a, b, c, cmp, swp);
124 if (cmp(c, d) > 0) {
125 swp(c, d);
126 if (cmp(b, c) > 0) {
127 swp(b, c);
128 if (cmp(a, b) > 0) {
129 swp(a, b);
130 }
131 }
132 }
133 }
134 /* }}} */
135
136 static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
137 zend_sort_4(a, b, c, d, cmp, swp);
138 if (cmp(d, e) > 0) {
139 swp(d, e);
140 if (cmp(c, d) > 0) {
141 swp(c, d);
142 if (cmp(b, c) > 0) {
143 swp(b, c);
144 if (cmp(a, b) > 0) {
145 swp(a, b);
146 }
147 }
148 }
149 }
150 }
151 /* }}} */
152
153 ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{
154 switch (nmemb) {
155 case 0:
156 case 1:
157 break;
158 case 2:
159 zend_sort_2(base, (char *)base + siz, cmp, swp);
160 break;
161 case 3:
162 zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);
163 break;
164 case 4:
165 {
166 size_t siz2 = siz + siz;
167 zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);
168 }
169 break;
170 case 5:
171 {
172 size_t siz2 = siz + siz;
173 zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);
174 }
175 break;
176 default:
177 {
178 char *i, *j, *k;
179 char *start = (char *)base;
180 char *end = start + (nmemb * siz);
181 size_t siz2= siz + siz;
182 char *sentry = start + (6 * siz);
183 for (i = start + siz; i < sentry; i += siz) {
184 j = i - siz;
185 if (!(cmp(j, i) > 0)) {
186 continue;
187 }
188 while (j != start) {
189 j -= siz;
190 if (!(cmp(j, i) > 0)) {
191 j += siz;
192 break;
193 }
194 }
195 for (k = i; k > j; k -= siz) {
196 swp(k, k - siz);
197 }
198 }
199 for (i = sentry; i < end; i += siz) {
200 j = i - siz;
201 if (!(cmp(j, i) > 0)) {
202 continue;
203 }
204 do {
205 j -= siz2;
206 if (!(cmp(j, i) > 0)) {
207 j += siz;
208 if (!(cmp(j, i) > 0)) {
209 j += siz;
210 }
211 break;
212 }
213 if (j == start) {
214 break;
215 }
216 if (j == start + siz) {
217 j -= siz;
218 if (cmp(i, j) > 0) {
219 j += siz;
220 }
221 break;
222 }
223 } while (1);
224 for (k = i; k > j; k -= siz) {
225 swp(k, k - siz);
226 }
227 }
228 }
229 break;
230 }
231 }
232 /* }}} */
233
234 /* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
235 *
236 * Derived from LLVM's libc++ implementation of std::sort.
237 *
238 * ===========================================================================
239 * libc++ License
240 * ===========================================================================
241 *
242 * The libc++ library is dual licensed under both the University of Illinois
243 * "BSD-Like" license and the MIT license. As a user of this code you may
244 * choose to use it under either license. As a contributor, you agree to allow
245 * your code to be used under both.
246 *
247 * Full text of the relevant licenses is included below.
248 *
249 * ===========================================================================
250 *
251 * University of Illinois/NCSA
252 * Open Source License
253 *
254 * Copyright (c) 2009-2012 by the contributors listed at
255 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
256 *
257 * All rights reserved.
258 *
259 * Developed by:
260 *
261 * LLVM Team
262 *
263 * University of Illinois at Urbana-Champaign
264 *
265 * http://llvm.org
266 *
267 * Permission is hereby granted, free of charge, to any person obtaining a copy
268 * of this software and associated documentation files (the "Software"), to
269 * deal with the Software without restriction, including without limitation the
270 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
271 * sell copies of the Software, and to permit persons to whom the Software is
272 * furnished to do so, subject to the following conditions:
273 *
274 * * Redistributions of source code must retain the above copyright notice,
275 * this list of conditions and the following disclaimers.
276 *
277 * * Redistributions in binary form must reproduce the above copyright
278 * notice, this list of conditions and the following disclaimers in the
279 * documentation and/or other materials provided with the distribution.
280 *
281 * * Neither the names of the LLVM Team, University of Illinois at
282 * Urbana-Champaign, nor the names of its contributors may be used to
283 * endorse or promote products derived from this Software without
284 * specific prior written permission.
285 *
286 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
287 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
288 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
289 * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
290 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
291 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
292 * WITH THE SOFTWARE.
293 *
294 * ===========================================================================
295 *
296 * Copyright (c) 2009-2012 by the contributors listed at
297 * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT
298 *
299 * Permission is hereby granted, free of charge, to any person obtaining a copy
300 * of this software and associated documentation files (the "Software"), to
301 * deal in the Software without restriction, including without limitation the
302 * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
303 * sell copies of the Software, and to permit persons to whom the Software is
304 * furnished to do so, subject to the following conditions:
305 *
306 * The above copyright notice and this permission notice shall be included in
307 * all copies or substantial portions of the Software.
308 *
309 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
310 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
311 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
312 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
313 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
314 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
315 * IN THE SOFTWARE.
316 */
317 ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
318 {
319 while (1) {
320 if (nmemb <= 16) {
321 zend_insert_sort(base, nmemb, siz, cmp, swp);
322 return;
323 } else {
324 char *i, *j;
325 char *start = (char *)base;
326 char *end = start + (nmemb * siz);
327 size_t offset = (nmemb >> Z_L(1));
328 char *pivot = start + (offset * siz);
329
330 if ((nmemb >> Z_L(10))) {
331 size_t delta = (offset >> Z_L(1)) * siz;
332 zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
333 } else {
334 zend_sort_3(start, pivot, end - siz, cmp, swp);
335 }
336 swp(start + siz, pivot);
337 pivot = start + siz;
338 i = pivot + siz;
339 j = end - siz;
340 while (1) {
341 while (cmp(pivot, i) > 0) {
342 i += siz;
343 if (UNEXPECTED(i == j)) {
344 goto done;
345 }
346 }
347 j -= siz;
348 if (UNEXPECTED(j == i)) {
349 goto done;
350 }
351 while (cmp(j, pivot) > 0) {
352 j -= siz;
353 if (UNEXPECTED(j == i)) {
354 goto done;
355 }
356 }
357 swp(i, j);
358 i += siz;
359 if (UNEXPECTED(i == j)) {
360 goto done;
361 }
362 }
363 done:
364 swp(pivot, i - siz);
365 if ((i - siz) - start < end - i) {
366 zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
367 base = i;
368 nmemb = (end - i)/siz;
369 } else {
370 zend_sort(i, (end - i)/siz, siz, cmp, swp);
371 nmemb = (i - start)/siz - 1;
372 }
373 }
374 }
375 }
376 /* }}} */
377
378 /*
379 * Local Variables:
380 * c-basic-offset: 4
381 * tab-width: 4
382 * End:
383 * vim600: fdm=marker
384 * vim: noet sw=4 ts=4
385 */