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 #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
