com php-src: Add zend_qsort_r & use it in strtr : Zend/zend_qsort.c Zend/zend_qsort.h ext/stand ard/string.c

Commit: 22390d33935d72d897a1c97158ce2848f8551cc1 Author: Gustavo Lopes <gustavo@icemobile.com> Mon, 14 Jan 2013 17:24:16 +0100 Parents: 1ce5a225899c19b79c64451e830cd3940ee2bff3 Branches: PHP-5.5 master Link: http://git.php.net/?p=php-src.git;a=commitdiff;h=22390d33935d72d897a1c97158ce2848f8551cc1 Log: Add zend_qsort_r & use it in strtr Changed paths: M Zend/zend_qsort.c M Zend/zend_qsort.h M ext/standard/string.c Diff: diff --git a/Zend/zend_qsort.c b/Zend/zend_qsort.c index bf17990..128c48d 100644 --- a/Zend/zend_qsort.c +++ b/Zend/zend_qsort.c @@ -19,6 +19,7 @@ /* $Id$ */ #include "zend.h" +#include "zend_qsort.h" #include <limits.h> @@ -53,7 +54,7 @@ static void _zend_qsort_swap(void *a, void *b, size_t siz) } } -ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC) +ZEND_API void zend_qsort_r(void *base, size_t nmemb, size_t siz, compare_r_func_t compare, void *arg TSRMLS_DC) { void *begin_stack[QSORT_STACK_SIZE]; void *end_stack[QSORT_STACK_SIZE]; @@ -80,10 +81,10 @@ ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t co seg2 = end; while (1) { - for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0; + for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC, arg) > 0; seg1 += siz); - for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0; + for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC, arg) > 0; seg2 -= siz); if (seg1 >= seg2) @@ -117,6 +118,11 @@ ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t co } } +ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC) +{ + zend_qsort_r(base, nmemb, siz, (compare_r_func_t)compare, NULL TSRMLS_CC); +} + /* * Local Variables: * c-basic-offset: 4 diff --git a/Zend/zend_qsort.h b/Zend/zend_qsort.h index 58c99f2..0ce32a7 100644 --- a/Zend/zend_qsort.h +++ b/Zend/zend_qsort.h @@ -22,7 +22,9 @@ #define ZEND_QSORT_H BEGIN_EXTERN_C() +typedef int (*compare_r_func_t)(const void *, const void * TSRMLS_DC, void *); ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC); +ZEND_API void zend_qsort_r(void *base, size_t nmemb, size_t siz, compare_r_func_t compare, void *arg TSRMLS_DC); END_EXTERN_C() #endif /* ZEND_QSORT_H */ diff --git a/ext/standard/string.c b/ext/standard/string.c index 735a613..8f7ef31 100644 --- a/ext/standard/string.c +++ b/ext/standard/string.c @@ -2847,7 +2847,7 @@ static inline void php_strtr_populate_shift(PATNREPL *patterns, int patnum, int } /* }}} */ /* {{{ php_strtr_compare_hash_suffix */ -static int php_strtr_compare_hash_suffix(const void *a, const void *b, void *ctx_g) +static int php_strtr_compare_hash_suffix(const void *a, const void *b TSRMLS_DC, void *ctx_g) { const PPRES *res = ctx_g; const PATNREPL *pnr_a = a, @@ -2873,62 +2873,6 @@ static int php_strtr_compare_hash_suffix(const void *a, const void *b, void *ctx } } /* }}} */ -/* {{{ Sorting (no zend_qsort_r in this PHP version) */ -#define HS_LEFT(i) ((i) * 2 + 1) -#define HS_RIGHT(i) ((i) * 2 + 2) -#define HS_PARENT(i) (((i) - 1) / 2); -#define HS_OFF(data, i) ((void *)(&((data)->arr)[i])) -#define HS_CMP_CALL(data, i1, i2) \ - (php_strtr_compare_hash_suffix(HS_OFF((data), (i1)), HS_OFF((data), (i2)), (data)->res)) -struct hs_data { - PATNREPL *arr; - size_t nel; - size_t heapel; - PPRES *res; -}; -static inline void php_strtr_swap(PATNREPL *a, PATNREPL *b) -{ - PATNREPL tmp = *a; - *a = *b; - *b = tmp; -} -static inline void php_strtr_fix_heap(struct hs_data *data, size_t i) -{ - size_t li = HS_LEFT(i), - ri = HS_RIGHT(i), - largei; - if (li < data->heapel && HS_CMP_CALL(data, li, i) > 0) { - largei = li; - } else { - largei = i; - } - if (ri < data->heapel && HS_CMP_CALL(data, ri, largei) > 0) { - largei = ri; - } - if (largei != i) { - php_strtr_swap(HS_OFF(data, i), HS_OFF(data, largei)); - php_strtr_fix_heap(data, largei); - } -} -static inline void php_strtr_build_heap(struct hs_data *data) -{ - size_t i; - for (i = data->nel / 2; i > 0; i--) { - php_strtr_fix_heap(data, i - 1); - } -} -static inline void php_strtr_heapsort(PATNREPL *arr, size_t nel, PPRES *res) -{ - struct hs_data data = { arr, nel, nel, res }; - size_t i; - php_strtr_build_heap(&data); - for (i = nel; i > 1; i--) { - php_strtr_swap(arr, HS_OFF(&data, i - 1)); - data.heapel--; - php_strtr_fix_heap(&data, 0); - } -} -/* }}} */ /* {{{ php_strtr_free_strp */ static void php_strtr_free_strp(void *strp) { @@ -3026,7 +2970,13 @@ static PPRES *php_strtr_array_prepare(STR *text, PATNREPL *patterns, int patnum, res->patterns = safe_emalloc(patnum, sizeof(*res->patterns), 0); memcpy(res->patterns, patterns, sizeof(*patterns) * patnum); - php_strtr_heapsort(res->patterns, patnum, res); +#ifdef ZTS + zend_qsort_r(res->patterns, patnum, sizeof(*res->patterns), + php_strtr_compare_hash_suffix, res, NULL); /* tsrmls not needed */ +#else + zend_qsort_r(res->patterns, patnum, sizeof(*res->patterns), + php_strtr_compare_hash_suffix, res); +#endif res->prefix = safe_emalloc(patnum, sizeof(*res->prefix), 0); for (i = 0; i < patnum; i++) {