xref: /PHP-7.2/Zend/zend_sort.c (revision 902d39a3)
1 /*
2    +----------------------------------------------------------------------+
3    | Zend Engine                                                          |
4    +----------------------------------------------------------------------+
5    | Copyright (c) 1998-2018 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 
zend_qsort(void * base,size_t nmemb,size_t siz,compare_func_t compare,swap_func_t swp)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 
zend_sort_2(void * a,void * b,compare_func_t cmp,swap_func_t swp)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 
zend_sort_3(void * a,void * b,void * c,compare_func_t cmp,swap_func_t swp)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 
zend_sort_4(void * a,void * b,void * c,void * d,compare_func_t cmp,swap_func_t swp)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 
zend_sort_5(void * a,void * b,void * c,void * d,void * e,compare_func_t cmp,swap_func_t swp)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 
zend_insert_sort(void * base,size_t nmemb,size_t siz,compare_func_t cmp,swap_func_t swp)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  */
zend_sort(void * base,size_t nmemb,size_t siz,compare_func_t cmp,swap_func_t swp)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: sw=4 ts=4 fdm=marker
384  * vim<600: sw=4 ts=4
385  */
386