xref: /PHP-8.0/Zend/zend_sort.c (revision f07fbfb8)
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 
zend_sort_2(void * a,void * b,compare_func_t cmp,swap_func_t swp)24 static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
25 	if (cmp(a, b) > 0) {
26 		swp(a, b);
27 	}
28 }
29 /* }}} */
30 
zend_sort_3(void * a,void * b,void * c,compare_func_t cmp,swap_func_t swp)31 static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
32 	if (!(cmp(a, b) > 0)) {
33 		if (!(cmp(b, c) > 0)) {
34 			return;
35 		}
36 		swp(b, c);
37 		if (cmp(a, b) > 0) {
38 			swp(a, b);
39 		}
40 		return;
41 	}
42 	if (!(cmp(c, b) > 0)) {
43 		swp(a, c);
44 		return;
45 	}
46 	swp(a, b);
47 	if (cmp(b, c) > 0) {
48 		swp(b, c);
49 	}
50 }
51 /* }}} */
52 
zend_sort_4(void * a,void * b,void * c,void * d,compare_func_t cmp,swap_func_t swp)53 static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
54 	zend_sort_3(a, b, c, cmp, swp);
55 	if (cmp(c, d) > 0) {
56 		swp(c, d);
57 		if (cmp(b, c) > 0) {
58 			swp(b, c);
59 			if (cmp(a, b) > 0) {
60 				swp(a, b);
61 			}
62 		}
63 	}
64 }
65 /* }}} */
66 
zend_sort_5(void * a,void * b,void * c,void * d,void * e,compare_func_t cmp,swap_func_t swp)67 static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ {
68 	zend_sort_4(a, b, c, d, cmp, swp);
69 	if (cmp(d, e) > 0) {
70 		swp(d, e);
71 		if (cmp(c, d) > 0) {
72 			swp(c, d);
73 			if (cmp(b, c) > 0) {
74 				swp(b, c);
75 				if (cmp(a, b) > 0) {
76 					swp(a, b);
77 				}
78 			}
79 		}
80 	}
81 }
82 /* }}} */
83 
zend_insert_sort(void * base,size_t nmemb,size_t siz,compare_func_t cmp,swap_func_t swp)84 ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{
85 	switch (nmemb) {
86 		case 0:
87 		case 1:
88 			break;
89 		case 2:
90 			zend_sort_2(base, (char *)base + siz, cmp, swp);
91 			break;
92 		case 3:
93 			zend_sort_3(base, (char *)base + siz, (char *)base + siz + siz, cmp, swp);
94 			break;
95 		case 4:
96 			{
97 				size_t siz2 = siz + siz;
98 				zend_sort_4(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, cmp, swp);
99 			}
100 			break;
101 		case 5:
102 			{
103 				size_t siz2 = siz + siz;
104 				zend_sort_5(base, (char *)base + siz, (char *)base + siz2, (char *)base + siz + siz2, (char *)base + siz2 + siz2, cmp, swp);
105 			}
106 			break;
107 		default:
108 			{
109 				char *i, *j, *k;
110 				char *start = (char *)base;
111 				char *end = start + (nmemb * siz);
112 				size_t siz2= siz + siz;
113 				char *sentry = start + (6 * siz);
114 				for (i = start + siz; i < sentry; i += siz) {
115 					j = i - siz;
116 					if (!(cmp(j, i) > 0)) {
117 						continue;
118 					}
119 					while (j != start) {
120 						j -= siz;
121 						if (!(cmp(j, i) > 0)) {
122 							j += siz;
123 							break;
124 						}
125 					}
126 					for (k = i; k > j; k -= siz) {
127 						swp(k, k - siz);
128 					}
129 				}
130 				for (i = sentry; i < end; i += siz) {
131 					j = i - siz;
132 					if (!(cmp(j, i) > 0)) {
133 						continue;
134 					}
135 					do {
136 						j -= siz2;
137 						if (!(cmp(j, i) > 0)) {
138 							j += siz;
139 							if (!(cmp(j, i) > 0)) {
140 								j += siz;
141 							}
142 							break;
143 						}
144 						if (j == start) {
145 							break;
146 						}
147 						if (j == start + siz) {
148 							j -= siz;
149 							if (cmp(i, j) > 0) {
150 								j += siz;
151 							}
152 							break;
153 						}
154 					} while (1);
155 					for (k = i; k > j; k -= siz) {
156 						swp(k, k - siz);
157 					}
158 				}
159 			}
160 			break;
161 	}
162 }
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  */
zend_sort(void * base,size_t nmemb,size_t siz,compare_func_t cmp,swap_func_t swp)248 ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp)
249 {
250 	while (1) {
251 		if (nmemb <= 16) {
252 			zend_insert_sort(base, nmemb, siz, cmp, swp);
253 			return;
254 		} else {
255 			char *i, *j;
256 			char *start = (char *)base;
257 			char *end = start + (nmemb * siz);
258 			size_t offset = (nmemb >> Z_L(1));
259 			char *pivot = start + (offset * siz);
260 
261 			if ((nmemb >> Z_L(10))) {
262 				size_t delta = (offset >> Z_L(1)) * siz;
263 				zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp);
264 			} else {
265 				zend_sort_3(start, pivot, end - siz, cmp, swp);
266 			}
267 			swp(start + siz, pivot);
268 			pivot = start + siz;
269 			i = pivot + siz;
270 			j = end - siz;
271 			while (1) {
272 				while (cmp(pivot, i) > 0) {
273 					i += siz;
274 					if (UNEXPECTED(i == j)) {
275 						goto done;
276 					}
277 				}
278 				j -= siz;
279 				if (UNEXPECTED(j == i)) {
280 					goto done;
281 				}
282 				while (cmp(j, pivot) > 0) {
283 					j -= siz;
284 					if (UNEXPECTED(j == i)) {
285 						goto done;
286 					}
287 				}
288 				swp(i, j);
289 				i += siz;
290 				if (UNEXPECTED(i == j)) {
291 					goto done;
292 				}
293 			}
294 done:
295 			swp(pivot, i - siz);
296 			if ((i - siz) - start < end - i) {
297 				zend_sort(start, (i - start)/siz - 1, siz, cmp, swp);
298 				base = i;
299 				nmemb = (end - i)/siz;
300 			} else {
301 				zend_sort(i, (end - i)/siz, siz, cmp, swp);
302 				nmemb = (i - start)/siz - 1;
303 			}
304 		}
305 	}
306 }
307 /* }}} */
308