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
