com php-src: Merge branch 'zend_sort' of https://gi thub.com/laruence/php-src: Zend/zend_hash.c Zend/ze nd_sort.c Zend/zend_sort.h
ext/standard/string.c
| From: | Xinchen Hui | Date: | Thu, 15 Jan 2015 03:15:41 +0000 |
| Subject: | com php-src: Merge branch 'zend_sort' of https://gi thub.com/laruence/php-src: Zend/zend_hash.c Zend/ze nd_sort.c Zend/zend_sort.h ext/standard/string.c |
||
| Groups: | php.cvs | ||
| Request: | Send a blank email to php-cvs+get-84099@lists.php.net to get a copy of this message | ||
Commit: 8a0bc38535f34d2e1063e9f3e3bf356300d07331
Author: Xinchen Hui <laruence@php.net> Wed, 14 Jan 2015 22:14:43 -0500
Parents: 8d26c53f7cd1aa51ac39f26d59bfbf673b260350 2193de0d185eb9d35e4dd7b93cf69d509b0526b9
Branches: master
Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=8a0bc38535f34d2e1063e9f3e3bf356300d07331
Log:
Merge branch 'zend_sort' of https://github.com/laruence/php-src
Changed paths:
MM Zend/zend_hash.c
AM Zend/zend_sort.c
AM Zend/zend_sort.h
MM ext/standard/string.c
diff --cc Zend/zend_sort.c index 0000000,fcd97f4..f9f9682 mode 000000,100644..100644 --- a/Zend/zend_sort.c +++ b/Zend/zend_sort.c @@@ -1,0 -1,377 +1,378 @@@ + /* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 2.00 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.zend.com/license/2_00.txt. | + | If you did not receive a copy of the Zend license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@zend.com so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ - | Authors: Sterling Hughes <sterling@php.net> | ++ | Authors: Xinchen Hui <laruence@php.net> | ++ | Sterling Hughes <sterling@php.net> | + +----------------------------------------------------------------------+ + */ + + /* $Id$ */ + + #include "zend.h" + #include "zend_sort.h" + #include <limits.h> + + #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT) + + ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */ + { + void *begin_stack[QSORT_STACK_SIZE]; + void *end_stack[QSORT_STACK_SIZE]; + register char *begin; + register char *end; + register char *seg1; + register char *seg2; + register char *seg2p; + register int loop; + uint offset; + + begin_stack[0] = (char *) base; + end_stack[0] = (char *) base + ((nmemb - 1) * siz); + + for (loop = 0; loop >= 0; --loop) { + begin = begin_stack[loop]; + end = end_stack[loop]; + + while (begin < end) { + offset = (end - begin) >> Z_L(1); + swp(begin, begin + (offset - (offset % siz))); + + seg1 = begin + siz; + seg2 = end; + + while (1) { + for (; seg1 < seg2 && compare(begin, seg1) > 0; + seg1 += siz); + + for (; seg2 >= seg1 && compare(seg2, begin) > 0; + seg2 -= siz); + + if (seg1 >= seg2) + break; + + swp(seg1, seg2); + + seg1 += siz; + seg2 -= siz; + } + + swp(begin, seg2); + + seg2p = seg2; + + if ((seg2p - begin) <= (end - seg2p)) { + if ((seg2p + siz) < end) { + begin_stack[loop] = seg2p + siz; + end_stack[loop++] = end; + } + end = seg2p - siz; + } + else { + if ((seg2p - siz) > begin) { + begin_stack[loop] = begin; + end_stack[loop++] = seg2p - siz; + } + begin = seg2p + siz; + } + } + } + } + /* }}} */ + + static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + if (cmp(a, b) <= 0) { + return; + } + swp(a, b); + } + /* }}} */ + + static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + if (cmp(a, b) <= 0) { + if (cmp(b, c) <= 0) { + return; + } + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + return; + } + if (cmp(b, c) >= 0) { + swp(a, c); + return; + } + swp(a, b); + if (cmp(b, c) > 0) { + swp(b, c); + } + } + /* }}} */ + + static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + zend_sort_3(a, b, c, cmp, swp); + if (cmp(c, d) > 0) { + swp(c, d); + if (cmp(b, c) > 0) { + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + } + } + } + /* }}} */ + + static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + zend_sort_4(a, b, c, d, cmp, swp); + if (cmp(d, e) > 0) { + swp(d, e); + if (cmp(c, d) > 0) { + swp(c, d); + if (cmp(b, c) > 0) { + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + } + } + } + } + /* }}} */ + + ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{ + switch (nmemb) { + case 0: + case 1: + break; + case 2: + zend_sort_2(base, base + siz, cmp, swp); + break; + case 3: + zend_sort_3(base, base + siz, base + siz + siz, cmp, swp); + break; + case 4: + zend_sort_4(base, base + siz, base + siz + siz, base + siz + siz + siz, cmp, swp); + break; + case 5: + zend_sort_5(base, base + siz, base + siz + siz, base + siz + siz + siz, base + (siz * 4), cmp, swp); + break; + default: + { + char *i, *j, *k; + char *start = (char *)base; + char *end = start + (nmemb * siz); + char *sentry = start + (6 * siz); + for (i = start + siz; i < sentry; i += siz) { + j = i - siz; + if (cmp(j, i) <= 0) { + continue; + } + while (j != start) { + j -= siz; + if (cmp(j, i) <= 0) { + j += siz; + break; + } + } + for (k = i; k > j; k -= siz) { + swp(k, k - siz); + } + } + for (i = sentry; i < end; i += siz) { + j = i - siz; + if (cmp(j, i) <= 0) { + continue; + } + do { + j -= siz * 2; + if (cmp(j, i) <= 0) { + j += siz; + if (cmp(j, i) <= 0) { + j += siz; + } + break; + } + if (j == start) { + break; + } + if (j == start + siz) { + j -= siz; + if (cmp(j, i) < 0) { + j += siz; + } + break; + } + } while (1); + for (k = i; k > j; k -= siz) { + swp(k, k - siz); + } + } + } + break; + } + } + /* }}} */ + + /* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) + * + * Derived from LLVM's libc++ implementation of std::sort. + * + * =========================================================================== + * libc++ License + * =========================================================================== + * + * The libc++ library is dual licensed under both the University of Illinois + * "BSD-Like" license and the MIT license. As a user of this code you may + * choose to use it under either license. As a contributor, you agree to allow + * your code to be used under both. + * + * Full text of the relevant licenses is included below. + * + * =========================================================================== + * + * University of Illinois/NCSA + * Open Source License + * + * Copyright (c) 2009-2012 by the contributors listed at + * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT + * + * All rights reserved. + * + * Developed by: + * + * LLVM Team + * + * University of Illinois at Urbana-Champaign + * + * http://llvm.org + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal with the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimers. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimers in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the names of the LLVM Team, University of Illinois at + * Urbana-Champaign, nor the names of its contributors may be used to + * endorse or promote products derived from this Software without + * specific prior written permission. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * WITH THE SOFTWARE. + * + * =========================================================================== + * + * Copyright (c) 2009-2012 by the contributors listed at + * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) + { + while (1) { + if (nmemb <= 16) { + return zend_insert_sort(base, nmemb, siz, cmp, swp); + } else { + char *i, *j; + char *start = (char *)base; + char *end = start + (nmemb * siz); + size_t offset = (nmemb >> Z_L(1)); + char *pivot = start + (offset * siz); + + if ((nmemb >> Z_L(10))) { + size_t delta = (offset >> Z_L(1)) * siz; + zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp); + } else { + zend_sort_3(start, pivot, end - siz, cmp, swp); + } + swp(start + siz, pivot); + pivot = start + siz; + i = pivot + siz; + j = end - siz; + while (1) { + while (cmp(i, pivot) < 0) { + i += siz; + if (UNEXPECTED(i == j)) { + goto done; + } + } + j -= siz; + if (UNEXPECTED(j == i)) { + goto done; + } + while (cmp(pivot, j) < 0) { + j -= siz; + if (UNEXPECTED(j == i)) { + goto done; + } + } + swp(i, j); + i += siz; + if (UNEXPECTED(i == j)) { + goto done; + } + } + done: + swp(pivot, i - siz); + if ((i - siz) - start < end - i) { + zend_sort(start, (i - start)/siz - 1, siz, cmp, swp); + base = i; + nmemb = (end - i)/siz; + } else { + zend_sort(i, (end - i)/siz, siz, cmp, swp); + nmemb = (i - start)/siz - 1; + } + } + } + } + /* }}} */ + + /* + * Local Variables: + * c-basic-offset: 4 + * tab-width: 4 + * End: + * vim600: fdm=marker + * vim: noet sw=4 ts=4 + */ diff --cc Zend/zend_sort.h index 0000000,fac9f78..018e9f9 mode 000000,100644..100644 --- a/Zend/zend_sort.h +++ b/Zend/zend_sort.h @@@ -1,0 -1,38 +1,39 @@@ + /* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 2.00 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.zend.com/license/2_00.txt. | + | If you did not receive a copy of the Zend license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@zend.com so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ - | Authors: Sterling Hughes <sterling@php.net> | ++ | Authors: Xinchen Hui <laruence@php.net> | ++ | Sterling Hughes <sterling@php.net> | + +----------------------------------------------------------------------+ + */ + + /* $Id$ */ + + #ifndef ZEND_SORT_H + #define ZEND_SORT_H + + BEGIN_EXTERN_C() + ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + END_EXTERN_C() + + #endif /* ZEND_SORT_H */ + + /* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --cc ext/standard/string.c index 95aebab,4b713c9..b19f130 --- a/ext/standard/string.c +++ b/ext/standard/string.c @@@ -3043,10 -2981,11 +3043,10 @@@ static void php_strtr_array(zval *retur len = zend_hash_num_elements(&num_hash); if ((maxlen - (minlen - 1) - len > 0) && /* smart algorithm, sort key lengths first */ - zend_hash_sort(&num_hash, zend_qsort, php_strtr_key_compare, 0) == SUCCESS) { + zend_hash_sort(&num_hash, php_strtr_key_compare, 0) == SUCCESS) { - pos = 0; + old_pos = pos = 0; while (pos <= slen - minlen) { - found = 0; key = str + pos; ZEND_HASH_FOREACH_NUM_KEY(&num_hash, len) { if (len > slen - pos) continue;
diff --cc Zend/zend_sort.c index 0000000,fcd97f4..f9f9682 mode 000000,100644..100644 --- a/Zend/zend_sort.c +++ b/Zend/zend_sort.c @@@ -1,0 -1,377 +1,378 @@@ + /* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 2.00 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.zend.com/license/2_00.txt. | + | If you did not receive a copy of the Zend license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@zend.com so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ - | Authors: Sterling Hughes <sterling@php.net> | ++ | Authors: Xinchen Hui <laruence@php.net> | ++ | Sterling Hughes <sterling@php.net> | + +----------------------------------------------------------------------+ + */ + + /* $Id$ */ + + #include "zend.h" + #include "zend_sort.h" + #include <limits.h> + + #define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT) + + ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */ + { + void *begin_stack[QSORT_STACK_SIZE]; + void *end_stack[QSORT_STACK_SIZE]; + register char *begin; + register char *end; + register char *seg1; + register char *seg2; + register char *seg2p; + register int loop; + uint offset; + + begin_stack[0] = (char *) base; + end_stack[0] = (char *) base + ((nmemb - 1) * siz); + + for (loop = 0; loop >= 0; --loop) { + begin = begin_stack[loop]; + end = end_stack[loop]; + + while (begin < end) { + offset = (end - begin) >> Z_L(1); + swp(begin, begin + (offset - (offset % siz))); + + seg1 = begin + siz; + seg2 = end; + + while (1) { + for (; seg1 < seg2 && compare(begin, seg1) > 0; + seg1 += siz); + + for (; seg2 >= seg1 && compare(seg2, begin) > 0; + seg2 -= siz); + + if (seg1 >= seg2) + break; + + swp(seg1, seg2); + + seg1 += siz; + seg2 -= siz; + } + + swp(begin, seg2); + + seg2p = seg2; + + if ((seg2p - begin) <= (end - seg2p)) { + if ((seg2p + siz) < end) { + begin_stack[loop] = seg2p + siz; + end_stack[loop++] = end; + } + end = seg2p - siz; + } + else { + if ((seg2p - siz) > begin) { + begin_stack[loop] = begin; + end_stack[loop++] = seg2p - siz; + } + begin = seg2p + siz; + } + } + } + } + /* }}} */ + + static inline void zend_sort_2(void *a, void *b, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + if (cmp(a, b) <= 0) { + return; + } + swp(a, b); + } + /* }}} */ + + static inline void zend_sort_3(void *a, void *b, void *c, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + if (cmp(a, b) <= 0) { + if (cmp(b, c) <= 0) { + return; + } + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + return; + } + if (cmp(b, c) >= 0) { + swp(a, c); + return; + } + swp(a, b); + if (cmp(b, c) > 0) { + swp(b, c); + } + } + /* }}} */ + + static void zend_sort_4(void *a, void *b, void *c, void *d, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + zend_sort_3(a, b, c, cmp, swp); + if (cmp(c, d) > 0) { + swp(c, d); + if (cmp(b, c) > 0) { + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + } + } + } + /* }}} */ + + static void zend_sort_5(void *a, void *b, void *c, void *d, void *e, compare_func_t cmp, swap_func_t swp) /* {{{ */ { + zend_sort_4(a, b, c, d, cmp, swp); + if (cmp(d, e) > 0) { + swp(d, e); + if (cmp(c, d) > 0) { + swp(c, d); + if (cmp(b, c) > 0) { + swp(b, c); + if (cmp(a, b) > 0) { + swp(a, b); + } + } + } + } + } + /* }}} */ + + ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) /* {{{ */{ + switch (nmemb) { + case 0: + case 1: + break; + case 2: + zend_sort_2(base, base + siz, cmp, swp); + break; + case 3: + zend_sort_3(base, base + siz, base + siz + siz, cmp, swp); + break; + case 4: + zend_sort_4(base, base + siz, base + siz + siz, base + siz + siz + siz, cmp, swp); + break; + case 5: + zend_sort_5(base, base + siz, base + siz + siz, base + siz + siz + siz, base + (siz * 4), cmp, swp); + break; + default: + { + char *i, *j, *k; + char *start = (char *)base; + char *end = start + (nmemb * siz); + char *sentry = start + (6 * siz); + for (i = start + siz; i < sentry; i += siz) { + j = i - siz; + if (cmp(j, i) <= 0) { + continue; + } + while (j != start) { + j -= siz; + if (cmp(j, i) <= 0) { + j += siz; + break; + } + } + for (k = i; k > j; k -= siz) { + swp(k, k - siz); + } + } + for (i = sentry; i < end; i += siz) { + j = i - siz; + if (cmp(j, i) <= 0) { + continue; + } + do { + j -= siz * 2; + if (cmp(j, i) <= 0) { + j += siz; + if (cmp(j, i) <= 0) { + j += siz; + } + break; + } + if (j == start) { + break; + } + if (j == start + siz) { + j -= siz; + if (cmp(j, i) < 0) { + j += siz; + } + break; + } + } while (1); + for (k = i; k > j; k -= siz) { + swp(k, k - siz); + } + } + } + break; + } + } + /* }}} */ + + /* {{{ ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) + * + * Derived from LLVM's libc++ implementation of std::sort. + * + * =========================================================================== + * libc++ License + * =========================================================================== + * + * The libc++ library is dual licensed under both the University of Illinois + * "BSD-Like" license and the MIT license. As a user of this code you may + * choose to use it under either license. As a contributor, you agree to allow + * your code to be used under both. + * + * Full text of the relevant licenses is included below. + * + * =========================================================================== + * + * University of Illinois/NCSA + * Open Source License + * + * Copyright (c) 2009-2012 by the contributors listed at + * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT + * + * All rights reserved. + * + * Developed by: + * + * LLVM Team + * + * University of Illinois at Urbana-Champaign + * + * http://llvm.org + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal with the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * * Redistributions of source code must retain the above copyright notice, + * this list of conditions and the following disclaimers. + * + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimers in the + * documentation and/or other materials provided with the distribution. + * + * * Neither the names of the LLVM Team, University of Illinois at + * Urbana-Champaign, nor the names of its contributors may be used to + * endorse or promote products derived from this Software without + * specific prior written permission. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * CONTRIBUTORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * WITH THE SOFTWARE. + * + * =========================================================================== + * + * Copyright (c) 2009-2012 by the contributors listed at + * http://llvm.org/svn/llvm-project/libcxx/trunk/CREDITS.TXT + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp) + { + while (1) { + if (nmemb <= 16) { + return zend_insert_sort(base, nmemb, siz, cmp, swp); + } else { + char *i, *j; + char *start = (char *)base; + char *end = start + (nmemb * siz); + size_t offset = (nmemb >> Z_L(1)); + char *pivot = start + (offset * siz); + + if ((nmemb >> Z_L(10))) { + size_t delta = (offset >> Z_L(1)) * siz; + zend_sort_5(start, start + delta, pivot, pivot + delta, end - siz, cmp, swp); + } else { + zend_sort_3(start, pivot, end - siz, cmp, swp); + } + swp(start + siz, pivot); + pivot = start + siz; + i = pivot + siz; + j = end - siz; + while (1) { + while (cmp(i, pivot) < 0) { + i += siz; + if (UNEXPECTED(i == j)) { + goto done; + } + } + j -= siz; + if (UNEXPECTED(j == i)) { + goto done; + } + while (cmp(pivot, j) < 0) { + j -= siz; + if (UNEXPECTED(j == i)) { + goto done; + } + } + swp(i, j); + i += siz; + if (UNEXPECTED(i == j)) { + goto done; + } + } + done: + swp(pivot, i - siz); + if ((i - siz) - start < end - i) { + zend_sort(start, (i - start)/siz - 1, siz, cmp, swp); + base = i; + nmemb = (end - i)/siz; + } else { + zend_sort(i, (end - i)/siz, siz, cmp, swp); + nmemb = (i - start)/siz - 1; + } + } + } + } + /* }}} */ + + /* + * Local Variables: + * c-basic-offset: 4 + * tab-width: 4 + * End: + * vim600: fdm=marker + * vim: noet sw=4 ts=4 + */ diff --cc Zend/zend_sort.h index 0000000,fac9f78..018e9f9 mode 000000,100644..100644 --- a/Zend/zend_sort.h +++ b/Zend/zend_sort.h @@@ -1,0 -1,38 +1,39 @@@ + /* + +----------------------------------------------------------------------+ + | Zend Engine | + +----------------------------------------------------------------------+ + | Copyright (c) 1998-2014 Zend Technologies Ltd. (http://www.zend.com) | + +----------------------------------------------------------------------+ + | This source file is subject to version 2.00 of the Zend license, | + | that is bundled with this package in the file LICENSE, and is | + | available through the world-wide-web at the following url: | + | http://www.zend.com/license/2_00.txt. | + | If you did not receive a copy of the Zend license and are unable to | + | obtain it through the world-wide-web, please send a note to | + | license@zend.com so we can mail you a copy immediately. | + +----------------------------------------------------------------------+ - | Authors: Sterling Hughes <sterling@php.net> | ++ | Authors: Xinchen Hui <laruence@php.net> | ++ | Sterling Hughes <sterling@php.net> | + +----------------------------------------------------------------------+ + */ + + /* $Id$ */ + + #ifndef ZEND_SORT_H + #define ZEND_SORT_H + + BEGIN_EXTERN_C() + ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + ZEND_API void zend_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + ZEND_API void zend_insert_sort(void *base, size_t nmemb, size_t siz, compare_func_t cmp, swap_func_t swp); + END_EXTERN_C() + + #endif /* ZEND_SORT_H */ + + /* + * Local variables: + * tab-width: 4 + * c-basic-offset: 4 + * indent-tabs-mode: t + * End: + */ diff --cc ext/standard/string.c index 95aebab,4b713c9..b19f130 --- a/ext/standard/string.c +++ b/ext/standard/string.c @@@ -3043,10 -2981,11 +3043,10 @@@ static void php_strtr_array(zval *retur len = zend_hash_num_elements(&num_hash); if ((maxlen - (minlen - 1) - len > 0) && /* smart algorithm, sort key lengths first */ - zend_hash_sort(&num_hash, zend_qsort, php_strtr_key_compare, 0) == SUCCESS) { + zend_hash_sort(&num_hash, php_strtr_key_compare, 0) == SUCCESS) { - pos = 0; + old_pos = pos = 0; while (pos <= slen - minlen) { - found = 0; key = str + pos; ZEND_HASH_FOREACH_NUM_KEY(&num_hash, len) { if (len > slen - pos) continue;