From c7100c4a1a39d6e1bd9227aa3cb78ec0e492c1fa Mon Sep 17 00:00:00 2001 From: Andrei Zmievski Date: Wed, 12 Apr 2000 19:39:02 +0000 Subject: [PATCH] Added natural comparison/sorting routines using code from Martin Pool. @- Added natural comparison/sorting routines strnatcmp(), strnatcasecmp(), @ natsort(), and natcasesort(). These are useful for comparing and sorting @ strings that contain numbers. Based on the code from Martin Pool @ . See http://www.linuxcare.com.au/projects/natsort/ @ for more info on natural sorting. (Andrei) --- ext/standard/Makefile.in | 3 +- ext/standard/array.c | 93 +++++++++++++++++++++++++ ext/standard/basic_functions.c | 4 ++ ext/standard/php_array.h | 2 + ext/standard/php_string.h | 8 +++ ext/standard/string.c | 26 +++++++ ext/standard/strnatcmp.c | 121 +++++++++++++++++++++++++++++++++ 7 files changed, 256 insertions(+), 1 deletion(-) create mode 100644 ext/standard/strnatcmp.c diff --git a/ext/standard/Makefile.in b/ext/standard/Makefile.in index 0cf973de56..254129a758 100644 --- a/ext/standard/Makefile.in +++ b/ext/standard/Makefile.in @@ -11,7 +11,8 @@ LTLIBRARY_SOURCES=\ formatted_print.c fsock.c head.c html.c image.c info.c iptc.c lcg.c \ link.c mail.c math.c md5.c metaphone.c microtime.c pack.c pageinfo.c \ parsedate.c quot_print.c rand.c reg.c soundex.c string.c \ - syslog.c type.c uniqid.c url.c url_scanner.c var.c output.c assert.c + syslog.c type.c uniqid.c url.c url_scanner.c var.c output.c assert.c \ + strnatcmp.c include $(topsrcdir)/build/ltlib.mk diff --git a/ext/standard/array.c b/ext/standard/array.c index 741c8133f5..26afd5a0b9 100644 --- a/ext/standard/array.c +++ b/ext/standard/array.c @@ -39,6 +39,7 @@ #include "php_globals.h" #include "php_array.h" #include "basic_functions.h" +#include "php_string.h" #ifdef ZTS int array_globals_id; @@ -253,6 +254,98 @@ static int array_reverse_data_compare(const void *a, const void *b) return array_data_compare(a,b)*-1; } +static int array_natural_general_compare(const void *a, const void *b, int fold_case) +{ + Bucket *f, *s; + zval *fval, *sval; + zval first, second; + int result; + + f = *((Bucket **) a); + s = *((Bucket **) b); + + fval = *((pval **) f->pData); + sval = *((pval **) s->pData); + first = *fval; + second = *sval; + if (fval->type != IS_STRING) { + zval_copy_ctor(&first); + convert_to_string(&first); + } + if (sval->type != IS_STRING) { + zval_copy_ctor(&first); + convert_to_string(&second); + } + + result = strnatcmp_ex(first.value.str.val, first.value.str.len, + second.value.str.val, second.value.str.len, fold_case); + + if (fval->type != IS_STRING) + zval_dtor(&first); + if (sval->type != IS_STRING) + zval_dtor(&second); + + return result; +} + +static int array_natural_compare(const void *a, const void *b) +{ + return array_natural_general_compare(a, b, 0); +} + +static int array_natural_case_compare(const void *a, const void *b) +{ + return array_natural_general_compare(a, b, 1); +} + +static void php_natsort(INTERNAL_FUNCTION_PARAMETERS, int fold_case) +{ + zval **array; + HashTable *target_hash; + + if (ARG_COUNT(ht) != 1 || zend_get_parameters_ex(1, &array) == FAILURE) { + WRONG_PARAM_COUNT; + } + + target_hash = HASH_OF(*array); + if (!target_hash) { + php_error(E_WARNING, "Wrong datatype in %s() call", + get_active_function_name()); + return; + } + + if (fold_case) { + if (zend_hash_sort(target_hash, qsort, array_natural_case_compare, 0) == FAILURE) { + return; + } + } else { + if (zend_hash_sort(target_hash, qsort, array_natural_compare, 0) == FAILURE) { + return; + } + } + + RETURN_TRUE; +} + + +/* {{{ proto void natsort(array array_arg) + Sort an array using natural sort */ +PHP_FUNCTION(natsort) +{ + php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0); +} +/* }}} */ + + +/* {{{ proto void natcasesort(array array_arg) + Sort an array using case-insensitive natural sort */ +PHP_FUNCTION(natcasesort) +{ + php_natsort(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1); +} +/* }}} */ + + /* {{{ proto void asort(array array_arg) Sort an array and maintain index association */ PHP_FUNCTION(asort) diff --git a/ext/standard/basic_functions.c b/ext/standard/basic_functions.c index 8ec8e48271..8168f940e3 100644 --- a/ext/standard/basic_functions.c +++ b/ext/standard/basic_functions.c @@ -120,6 +120,8 @@ function_entry basic_functions[] = { PHP_FE(php_logo_guid, NULL) PHP_FE(zend_logo_guid, NULL) + PHP_FE(strnatcmp, NULL) + PHP_FE(strnatcasecmp, NULL) PHP_FE(strspn, NULL) PHP_FE(strcspn, NULL) PHP_FE(strtok, NULL) @@ -446,6 +448,8 @@ function_entry basic_functions[] = { /* functions from array.c */ PHP_FE(ksort, first_arg_force_ref) PHP_FE(krsort, first_arg_force_ref) + PHP_FE(natsort, first_arg_force_ref) + PHP_FE(natcasesort, first_arg_force_ref) PHP_FE(asort, first_arg_force_ref) PHP_FE(arsort, first_arg_force_ref) PHP_FE(sort, first_arg_force_ref) diff --git a/ext/standard/php_array.h b/ext/standard/php_array.h index 46f67b38bf..033953839a 100644 --- a/ext/standard/php_array.h +++ b/ext/standard/php_array.h @@ -29,6 +29,8 @@ PHP_MSHUTDOWN_FUNCTION(array); PHP_FUNCTION(ksort); PHP_FUNCTION(krsort); +PHP_FUNCTION(natsort); +PHP_FUNCTION(natcasesort); PHP_FUNCTION(asort); PHP_FUNCTION(arsort); PHP_FUNCTION(sort); diff --git a/ext/standard/php_string.h b/ext/standard/php_string.h index 467e85789e..81d703553d 100644 --- a/ext/standard/php_string.h +++ b/ext/standard/php_string.h @@ -82,6 +82,14 @@ PHP_FUNCTION(similar_text); PHP_FUNCTION(strip_tags); PHP_FUNCTION(str_repeat); PHP_FUNCTION(substr_replace); +PHP_FUNCTION(strnatcmp); +PHP_FUNCTION(strnatcasecmp); + +#define strnatcmp(a, b) \ + strnatcmp_ex(a, strlen(a), b, strlen(b), 0) +#define strnatcasecmp(a, b) \ + strnatcmp_ex(a, strlen(a), b, strlen(b), 1) +PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case); PHPAPI char *php_strtoupper(char *s, size_t len); PHPAPI char *php_strtolower(char *s, size_t len); diff --git a/ext/standard/string.c b/ext/standard/string.c index dda667df4c..03930d85bc 100644 --- a/ext/standard/string.c +++ b/ext/standard/string.c @@ -2456,3 +2456,29 @@ PHP_FUNCTION(count_chars) } } /* }}} */ + +static void php_strnatcmp(INTERNAL_FUNCTION_PARAMETERS, int fold_case) +{ + zval **s1, **s2; + + if (ARG_COUNT(ht)!=2 || zend_get_parameters_ex(2, &s1, &s2) == FAILURE) { + WRONG_PARAM_COUNT; + } + + convert_to_string_ex(s1); + convert_to_string_ex(s2); + + RETURN_LONG(strnatcmp_ex((*s1)->value.str.val, (*s1)->value.str.len, + (*s2)->value.str.val, (*s2)->value.str.len, + fold_case)); +} + +PHP_FUNCTION(strnatcmp) +{ + php_strnatcmp(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0); +} + +PHP_FUNCTION(strnatcasecmp) +{ + php_strnatcmp(INTERNAL_FUNCTION_PARAM_PASSTHRU, 1); +} diff --git a/ext/standard/strnatcmp.c b/ext/standard/strnatcmp.c new file mode 100644 index 0000000000..2700ef69e0 --- /dev/null +++ b/ext/standard/strnatcmp.c @@ -0,0 +1,121 @@ +/* -*- mode: c; c-file-style: "k&r" -*- + + Modified for PHP by Andrei Zmievski + + strnatcmp.c -- Perform 'natural order' comparisons of strings in C. + Copyright (C) 2000 by Martin Pool + + This software is provided 'as-is', without any express or implied + warranty. In no event will the authors be held liable for any damages + arising from the use of this software. + + Permission is granted to anyone to use this software for any purpose, + including commercial applications, and to alter it and redistribute it + freely, subject to the following restrictions: + + 1. The origin of this software must not be misrepresented; you must not + claim that you wrote the original software. If you use this software + in a product, an acknowledgment in the product documentation would be + appreciated but is not required. + 2. Altered source versions must be plainly marked as such, and must not be + misrepresented as being the original software. + 3. This notice may not be removed or altered from any source distribution. +*/ + +#include +#include +#include +#include + +#include "php.h" +#include "php_string.h" + +#if defined(__GNUC__) +# define UNUSED __attribute__((__unused__)) +#endif + +static char const *version UNUSED = + "$Id$"; + +PHPAPI int strnatcmp_ex(char const *a, size_t a_len, char const *b, size_t b_len, int fold_case) +{ + int ai, bi; + char ca, cb; + const char *aend = a + a_len, + *bend = b + b_len; + + if (a_len == 0 || b_len == 0) + return a_len - b_len; + + assert(a && b); + ai = bi = 0; + while (1) { + ca = a[ai]; cb = b[bi]; + + /* skip over leading spaces or zeros */ + while (isspace(ca) || ca == '0') + ca = a[++ai]; + + while (isspace(cb) || cb == '0') + cb = b[++bi]; + + /* process run of digits */ + if (isdigit(ca) && isdigit(cb)) { + int bias = 0; + /* The longest run of digits (stripping off leading + zeros) wins. That aside, the greatest value wins, + but we can't know that it will until we've scanned + both numbers to know that they have the same + magnitude, so we remember it in BIAS. */ + while (1) { + if (!isdigit(ca) && !isdigit(cb)) + goto done_number; + else if (!isdigit(ca)) + return -1; + else if (!isdigit(cb)) + return +1; + else if (ca < cb) { + if (!bias) + bias = -1; + } else if (ca > cb) { + if (!bias) + bias = +1; + } + + ++ai; ++bi; + if (a + ai == aend && b + bi == bend) + /* Return the current bias if at the end of both strings. */ + return bias; + else if (a + ai == aend) + return -1; + else if (b + bi == bend) + return 1; + + ca = a[ai]; cb = b[bi]; + } +done_number: + if (bias) + return bias; + } + + if (fold_case) { + ca = toupper(ca); + cb = toupper(cb); + } + + if (ca < cb) + return -1; + else if (ca > cb) + return +1; + + ++ai; ++bi; + if (a + ai == aend && b + bi == bend) + /* The strings compare the same. Perhaps the caller + will want to call strcmp to break the tie. */ + return 0; + else if (a + ai == aend) + return -1; + else if (b + bi == bend) + return 1; + } +} -- 2.50.1