diff options
Diffstat (limited to 'Zend')
| -rw-r--r-- | Zend/Makefile.am | 2 | ||||
| -rw-r--r-- | Zend/tests/methods-on-non-objects-usort.phpt | 13 | ||||
| -rw-r--r-- | Zend/zend_API.c | 4 | ||||
| -rw-r--r-- | Zend/zend_hash.c | 47 | ||||
| -rw-r--r-- | Zend/zend_hash.h | 8 | ||||
| -rw-r--r-- | Zend/zend_ini.c | 4 | ||||
| -rw-r--r-- | Zend/zend_llist.c | 14 | ||||
| -rw-r--r-- | Zend/zend_qsort.c | 133 | ||||
| -rw-r--r-- | Zend/zend_sort.c | 377 | ||||
| -rw-r--r-- | Zend/zend_sort.h (renamed from Zend/zend_qsort.h) | 12 | ||||
| -rw-r--r-- | Zend/zend_ts_hash.c | 2 | ||||
| -rw-r--r-- | Zend/zend_types.h | 3 |
12 files changed, 457 insertions, 162 deletions
diff --git a/Zend/Makefile.am b/Zend/Makefile.am index 09018a0d3d..416f82a401 100644 --- a/Zend/Makefile.am +++ b/Zend/Makefile.am @@ -13,7 +13,7 @@ libZend_la_SOURCES=\ zend_vm_opcodes.c zend_opcode.c zend_operators.c zend_ptr_stack.c zend_stack.c \ zend_variables.c zend.c zend_API.c zend_extensions.c zend_hash.c \ zend_list.c zend_indent.c zend_builtin_functions.c zend_sprintf.c \ - zend_ini.c zend_qsort.c zend_objects.c zend_object_handlers.c \ + zend_ini.c zend_sort.c zend_objects.c zend_object_handlers.c \ zend_objects_API.c zend_ts_hash.c zend_stream.c \ zend_default_classes.c \ zend_iterators.c zend_interfaces.c zend_exceptions.c \ diff --git a/Zend/tests/methods-on-non-objects-usort.phpt b/Zend/tests/methods-on-non-objects-usort.phpt index 760d481b27..fb1869c1c8 100644 --- a/Zend/tests/methods-on-non-objects-usort.phpt +++ b/Zend/tests/methods-on-non-objects-usort.phpt @@ -23,21 +23,16 @@ int(4096) string(43) "Call to a member function compare() on null" int(4096) string(43) "Call to a member function compare() on null" -int(4096) -string(43) "Call to a member function compare() on null" -int(4096) -string(43) "Call to a member function compare() on null" array(5) { [0]=> - int(-1) + int(1) [1]=> - int(3) + int(4) [2]=> int(2) [3]=> - int(4) + int(3) [4]=> - int(1) + int(-1) } Alive - diff --git a/Zend/zend_API.c b/Zend/zend_API.c index ef7012d5ea..dc9de77e21 100644 --- a/Zend/zend_API.c +++ b/Zend/zend_API.c @@ -1715,7 +1715,7 @@ static int zend_startup_module_zval(zval *zv) /* {{{ */ } /* }}} */ -static void zend_sort_modules(void *base, size_t count, size_t siz, compare_func_t compare) /* {{{ */ +static void zend_sort_modules(void *base, size_t count, size_t siz, compare_func_t compare, swap_func_t swp) /* {{{ */ { Bucket *b1 = base; Bucket *b2; @@ -1821,7 +1821,7 @@ ZEND_API void zend_collect_module_handlers(void) /* {{{ */ ZEND_API int zend_startup_modules(void) /* {{{ */ { - zend_hash_sort(&module_registry, zend_sort_modules, NULL, 0); + zend_hash_sort_ex(&module_registry, zend_sort_modules, NULL, 0); zend_hash_apply(&module_registry, zend_startup_module_zval); return SUCCESS; } diff --git a/Zend/zend_hash.c b/Zend/zend_hash.c index fd0d27fb07..92ee7098a5 100644 --- a/Zend/zend_hash.c +++ b/Zend/zend_hash.c @@ -1663,8 +1663,47 @@ ZEND_API zval *zend_hash_get_current_data_ex(HashTable *ht, HashPosition *pos) } } -ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, - compare_func_t compar, zend_bool renumber) +ZEND_API void zend_hash_bucket_swap(Bucket *p, Bucket *q) { + zval val; + zend_ulong h; + zend_string *key; + + ZVAL_COPY_VALUE(&val, &p->val); + h = p->h; + key = p->key; + + ZVAL_COPY_VALUE(&p->val, &q->val); + p->h = q->h; + p->key = q->key; + + ZVAL_COPY_VALUE(&q->val, &val); + q->h = h; + q->key = key; +} + +ZEND_API void zend_hash_bucket_renum_swap(Bucket *p, Bucket *q) { + zval val; + + ZVAL_COPY_VALUE(&val, &p->val); + ZVAL_COPY_VALUE(&p->val, &q->val); + ZVAL_COPY_VALUE(&q->val, &val); +} + +ZEND_API void zend_hash_bucket_packed_swap(Bucket *p, Bucket *q) { + zval val; + zend_ulong h; + + ZVAL_COPY_VALUE(&val, &p->val); + h = p->h; + + ZVAL_COPY_VALUE(&p->val, &q->val); + p->h = q->h; + + ZVAL_COPY_VALUE(&q->val, &val); + q->h = h; +} + +ZEND_API int zend_hash_sort_ex(HashTable *ht, sort_func_t sort, compare_func_t compar, zend_bool renumber) { Bucket *p; uint32_t i, j; @@ -1688,7 +1727,9 @@ ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, } } - (*sort_func)((void *) ht->arData, i, sizeof(Bucket), compar); + sort((void *)ht->arData, i, sizeof(Bucket), compar, + (swap_func_t)(renumber? zend_hash_bucket_renum_swap : + ((ht->u.flags & HASH_FLAG_PACKED) ? zend_hash_bucket_packed_swap : zend_hash_bucket_swap))); HANDLE_BLOCK_INTERRUPTIONS(); ht->nNumUsed = i; diff --git a/Zend/zend_hash.h b/Zend/zend_hash.h index 09c5fb546a..2484f953d6 100644 --- a/Zend/zend_hash.h +++ b/Zend/zend_hash.h @@ -201,13 +201,19 @@ typedef struct _HashPointer { ZEND_API void zend_hash_copy(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor); ZEND_API void _zend_hash_merge(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, zend_bool overwrite ZEND_FILE_LINE_DC); ZEND_API void zend_hash_merge_ex(HashTable *target, HashTable *source, copy_ctor_func_t pCopyConstructor, merge_checker_func_t pMergeSource, void *pParam); -ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber); +ZEND_API void zend_hash_bucket_swap(Bucket *p, Bucket *q); +ZEND_API void zend_hash_bucket_renum_swap(Bucket *p, Bucket *q); +ZEND_API void zend_hash_bucket_packed_swap(Bucket *p, Bucket *q); +ZEND_API int zend_hash_sort_ex(HashTable *ht, sort_func_t sort_func, compare_func_t compare_func, zend_bool renumber); ZEND_API int zend_hash_compare(HashTable *ht1, HashTable *ht2, compare_func_t compar, zend_bool ordered); ZEND_API zval *zend_hash_minmax(const HashTable *ht, compare_func_t compar, uint32_t flag); #define zend_hash_merge(target, source, pCopyConstructor, overwrite) \ _zend_hash_merge(target, source, pCopyConstructor, overwrite ZEND_FILE_LINE_CC) +#define zend_hash_sort(ht, compare_func, renumber) \ + zend_hash_sort_ex(ht, zend_sort, compare_func, renumber) + #define zend_hash_num_elements(ht) \ (ht)->nNumOfElements diff --git a/Zend/zend_ini.c b/Zend/zend_ini.c index 186777aa82..6904739d3a 100644 --- a/Zend/zend_ini.c +++ b/Zend/zend_ini.c @@ -19,7 +19,7 @@ /* $Id$ */ #include "zend.h" -#include "zend_qsort.h" +#include "zend_sort.h" #include "zend_API.h" #include "zend_ini.h" #include "zend_alloc.h" @@ -202,7 +202,7 @@ static int ini_key_compare(const void *a, const void *b) /* {{{ */ ZEND_API void zend_ini_sort_entries(void) /* {{{ */ { - zend_hash_sort(EG(ini_directives), zend_qsort, ini_key_compare, 0); + zend_hash_sort(EG(ini_directives), ini_key_compare, 0); } /* }}} */ diff --git a/Zend/zend_llist.c b/Zend/zend_llist.c index 1634327921..737e50d237 100644 --- a/Zend/zend_llist.c +++ b/Zend/zend_llist.c @@ -21,7 +21,7 @@ #include "zend.h" #include "zend_llist.h" -#include "zend_qsort.h" +#include "zend_sort.h" ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor, unsigned char persistent) { @@ -33,7 +33,6 @@ ZEND_API void zend_llist_init(zend_llist *l, size_t size, llist_dtor_func_t dtor l->persistent = persistent; } - ZEND_API void zend_llist_add_element(zend_llist *l, void *element) { zend_llist_element *tmp = pemalloc(sizeof(zend_llist_element)+l->size-1, l->persistent); @@ -186,6 +185,14 @@ ZEND_API void zend_llist_apply(zend_llist *l, llist_apply_func_t func) } } +static void zend_llist_swap(zend_llist_element **p, zend_llist_element **q) +{ + zend_llist_element *t; + t = *p; + *p = *q; + *q = t; +} + ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func) { size_t i; @@ -205,7 +212,8 @@ ZEND_API void zend_llist_sort(zend_llist *l, llist_compare_func_t comp_func) *ptr++ = element; } - zend_qsort(elements, l->count, sizeof(zend_llist_element *), (compare_func_t) comp_func); + zend_sort(elements, l->count, sizeof(zend_llist_element *), + (compare_func_t) comp_func, (swap_func_t) zend_llist_swap); l->head = elements[0]; elements[0]->prev = NULL; diff --git a/Zend/zend_qsort.c b/Zend/zend_qsort.c deleted file mode 100644 index 84561e09e0..0000000000 --- a/Zend/zend_qsort.c +++ /dev/null @@ -1,133 +0,0 @@ -/* - +----------------------------------------------------------------------+ - | 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> | - +----------------------------------------------------------------------+ -*/ - -/* $Id$ */ - -#include "zend.h" -#include "zend_qsort.h" - -#include <limits.h> - -#define QSORT_STACK_SIZE (sizeof(size_t) * CHAR_BIT) - -static void _zend_qsort_swap(void *a, void *b, size_t siz) -{ - register char *tmp_a_char; - register char *tmp_b_char; - register int *tmp_a_int; - register int *tmp_b_int; - register size_t i; - int t_i; - char t_c; - - tmp_a_int = (int *) a; - tmp_b_int = (int *) b; - - for (i = sizeof(int); i <= siz; i += sizeof(int)) { - t_i = *tmp_a_int; - *tmp_a_int++ = *tmp_b_int; - *tmp_b_int++ = t_i; - } - - tmp_a_char = (char *) tmp_a_int; - tmp_b_char = (char *) tmp_b_int; - - for (i = i - sizeof(int) + 1; i <= siz; ++i) { - t_c = *tmp_a_char; - *tmp_a_char++ = *tmp_b_char; - *tmp_b_char++ = t_c; - } -} - -ZEND_API void zend_qsort_r(void *base, size_t nmemb, size_t siz, compare_r_func_t compare, void *arg) -{ - 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); - _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz); - - seg1 = begin + siz; - seg2 = end; - - while (1) { - for (; seg1 < seg2 && compare(begin, seg1, arg) > 0; - seg1 += siz); - - for (; seg2 >= seg1 && compare(seg2, begin, arg) > 0; - seg2 -= siz); - - if (seg1 >= seg2) - break; - - _zend_qsort_swap(seg1, seg2, siz); - - seg1 += siz; - seg2 -= siz; - } - - _zend_qsort_swap(begin, seg2, siz); - - 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; - } - } - } -} - -ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare) -{ - zend_qsort_r(base, nmemb, siz, (compare_r_func_t)compare, NULL); -} - -/* - * Local Variables: - * c-basic-offset: 4 - * tab-width: 4 - * End: - * vim600: fdm=marker - * vim: noet sw=4 ts=4 - */ diff --git a/Zend/zend_sort.c b/Zend/zend_sort.c new file mode 100644 index 0000000000..fcd97f46af --- /dev/null +++ b/Zend/zend_sort.c @@ -0,0 +1,377 @@ +/* + +----------------------------------------------------------------------+ + | 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> | + +----------------------------------------------------------------------+ +*/ + +/* $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 --git a/Zend/zend_qsort.h b/Zend/zend_sort.h index babccafd8e..fac9f78bef 100644 --- a/Zend/zend_qsort.h +++ b/Zend/zend_sort.h @@ -18,16 +18,16 @@ /* $Id$ */ -#ifndef ZEND_QSORT_H -#define ZEND_QSORT_H +#ifndef ZEND_SORT_H +#define ZEND_SORT_H BEGIN_EXTERN_C() -typedef int (*compare_r_func_t)(const void *, const void *, void *); -ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare); -ZEND_API void zend_qsort_r(void *base, size_t nmemb, size_t siz, compare_r_func_t compare, void *arg); +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_QSORT_H */ +#endif /* ZEND_SORT_H */ /* * Local variables: diff --git a/Zend/zend_ts_hash.c b/Zend/zend_ts_hash.c index 5a5daa4c44..0d4cb43d77 100644 --- a/Zend/zend_ts_hash.c +++ b/Zend/zend_ts_hash.c @@ -281,7 +281,7 @@ ZEND_API int zend_ts_hash_sort(TsHashTable *ht, sort_func_t sort_func, compare_f int retval; begin_write(ht); - retval = zend_hash_sort(TS_HASH(ht), sort_func, compare_func, renumber); + retval = zend_hash_sort_ex(TS_HASH(ht), sort_func, compare_func, renumber); end_write(ht); return retval; diff --git a/Zend/zend_types.h b/Zend/zend_types.h index 0345c4dd7c..78baec0671 100644 --- a/Zend/zend_types.h +++ b/Zend/zend_types.h @@ -84,7 +84,8 @@ typedef struct _zend_ast_ref zend_ast_ref; typedef struct _zend_ast zend_ast; typedef int (*compare_func_t)(const void *, const void *); -typedef void (*sort_func_t)(void *, size_t, size_t, compare_func_t); +typedef void (*swap_func_t)(void *, void *); +typedef void (*sort_func_t)(void *, size_t, size_t, compare_func_t, swap_func_t); typedef void (*dtor_func_t)(zval *pDest); typedef void (*copy_ctor_func_t)(zval *pElement); |