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