Re: cvs: php4 / NEWS /ext/standard string.c
| From: | Andi Gutmans | Date: | Fri, 20 Jul 2001 07:10:40 +0000 |
| Subject: | Re: cvs: php4 / NEWS /ext/standard string.c | ||
| References: | 1 | Groups: | php.cvs |
| Request: | Send a blank email to php-cvs+get-6276@lists.php.net to get a copy of this message | ||
Sascha,
Is there any reason to leave the old algorithm? I don't really like the optional argument. Why not always use Boyer-Moore as it's probably faster? Or does it support less than the old str_replacE()?
Andi
At 01:22 AM 7/20/2001 +0000, Sascha Schumann wrote:
sas Thu Jul 19 21:22:29 2001 EDTModified files:/php4 NEWS /php4/ext/standard string.cLog: Add optional support for using boyer-moore to str_replace. Index: php4/NEWS diff -u php4/NEWS:1.714 php4/NEWS:1.715--- php4/NEWS:1.714 Thu Jul 19 00:58:44 2001+++ php4/NEWS Thu Jul 19 21:22:28 2001 @@ -1,6 +1,7 @@ PHP4.0 NEWS||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| ?? ??? 200?, Version 4.0.7-dev +- Added optional use of Boyer-Moore algorithm to str_replace() (Sascha) - Fixed and improved shared-memory session storage module (Sascha) - Add config option (always_populate_raw_post_data) which when enabled will always populate $HTTP_RAW_POST_DATA regardless of the post mime Index: php4/ext/standard/string.c diff -u php4/ext/standard/string.c:1.205 php4/ext/standard/string.c:1.206--- php4/ext/standard/string.c:1.205 Mon Jul 9 13:44:07 2001+++ php4/ext/standard/string.c Thu Jul 19 21:22:29 2001 @@ -18,7 +18,7 @@+----------------------------------------------------------------------+*/ -/* $Id: string.c,v 1.205 2001/07/09 17:44:07 sas Exp $ */ +/* $Id: string.c,v 1.206 2001/07/20 01:22:29 sas Exp $ */ /* Synced with php 3.0 revision 1.193 1999-06-16 [ssb] */ @@ -2386,6 +2386,86 @@ } /* }}} */ +/* {{{ boyer_str_to_str */ +static char *boyer_str_to_str(char *haystack, int length,+ char *needle, int needle_len, char *str, + int str_len, int *new_length)+{+ char *p, *pe, *cursor, *end, *r; + int off; + char jump_table[256]; + smart_str result = {0};++ /* + * We implement only the first half of the Boyer-Moore algorithm, + * because the second half is too expensive to compute during run-time. + * TODO: Split matching into compile-/match-stage. + */++ /* Prepare the jump_table which contains the skip offsets */ + memset(jump_table, needle_len, 256);++ off = needle_len - 1;++ /* Calculate the default start where each comparison starts */ + pe = needle + off;++ /* Assign skip offsets based on the pattern */ + for (p = needle; p <= pe; p++) + jump_table[(unsigned char) *p] = off--;++ /* Start to look at the first possible position for the pattern */ + cursor = haystack + needle_len - 1;++ /* The cursor must not cross this limit */ + end = haystack + length;++ /* Start to copy at haystack */ + r = haystack;+ +nextiter:+ while (cursor < end) { + p = pe; /* Compare from right to left */ + while (*p == *cursor) { + if (--p < needle) { /* Found the pattern */++ /* Append whatever was not matched */ + smart_str_appendl(&result, r, cursor - r);++ /* Append replacement string */ + smart_str_appendl(&result, str, str_len);++ /* Update copy pointer */ + r = cursor + needle_len;++ /* needle_len was substracted from cursor for + * this comparison, add it back. Also add + * needle_len - 1 which is the default search + * offset. + */ + cursor += (needle_len << 1) - 1;++ /* Next iteration */ + goto nextiter; + } + cursor--; + }++ cursor += jump_table[(unsigned char) *cursor]; + }++ if (r < end) /* Copy the remaining data */ + smart_str_appendl(&result, r, end - r);++ smart_str_0(&result); /* NUL-ify result */++ if (new_length) + *new_length = result.len;++ return result.c;+} +/* }}} */ + /* {{{ php_str_to_str */ PHPAPI char *php_str_to_str(char *haystack, int length, @@ -2395,7 +2475,7 @@char *r; char *end = haystack + length; smart_str result = {0};- +for (p = haystack; (r = php_memnstr(p, needle, needle_len, end)); p = r + needle_len) {@@ -2416,14 +2496,17 @@ /* {{{ php_str_replace_in_subject */ -static void php_str_replace_in_subject(zval *search, zval *replace, zval **subject, zval *result) +static void php_str_replace_in_subject(zval *search, zval *replace, zval **subject, zval *result, int boyer) {zval **search_entry, **replace_entry = NULL, temp_result; char *replace_value = NULL; int replace_len = 0; + char *(*str_to_str)(char *, int, char *, int, char *, int, int *);+ str_to_str = boyer ? boyer_str_to_str : php_str_to_str;+/* Make sure we're dealing with strings. */ convert_to_string_ex(subject); Z_TYPE_P(result) = IS_STRING;@@ -2484,7 +2567,7 @@replace_len,&temp_result);} else if (Z_STRLEN_PP(search_entry) > 1) { - Z_STRVAL(temp_result) = php_str_to_str(Z_STRVAL_P(result), Z_STRLEN_P(result), + Z_STRVAL(temp_result) = str_to_str(Z_STRVAL_P(result), Z_STRLEN_P(result),Z_STRVAL_PP(search_entry), Z_STRLEN_PP(search_entry), replace_value, replace_len, &Z_STRLEN(temp_result));}@@ -2504,7 +2587,7 @@Z_STRLEN_P(replace), result); } else if (Z_STRLEN_P(search) > 1) { - Z_STRVAL_P(result) = php_str_to_str(Z_STRVAL_PP(subject), Z_STRLEN_PP(subject), + Z_STRVAL_P(result) = str_to_str(Z_STRVAL_PP(subject), Z_STRLEN_PP(subject),Z_STRVAL_P(search), Z_STRLEN_P(search), Z_STRVAL_P(replace), Z_STRLEN_P(replace), &Z_STRLEN_P(result));} else {@@ -2515,20 +2598,31 @@ } /* }}} */ -/* {{{ proto mixed str_replace(mixed search, mixed replace, mixed subject) +/* {{{ proto mixed str_replace(mixed search, mixed replace, mixed subject[, bool boyer])Replace all occurrences of search in haystack with replace */PHP_FUNCTION(str_replace) {- zval **subject, **search, **replace, **subject_entry; + zval **subject, **search, **replace, **subject_entry, **pboyer; zval *result; char *string_key; ulong string_key_len, num_key; + int boyer = 0;- if(ZEND_NUM_ARGS() != 3 || - zend_get_parameters_ex(3, &search, &replace, &subject) == FAILURE) { + if(ZEND_NUM_ARGS() < 3 || + ZEND_NUM_ARGS() > 4 || + zend_get_parameters_ex(ZEND_NUM_ARGS(), &search, + &replace, &subject, &pboyer) == FAILURE) { WRONG_PARAM_COUNT; }+ switch (ZEND_NUM_ARGS()) { + case 4: + convert_to_boolean_ex(pboyer); + if (Z_BVAL_PP(pboyer)) + boyer = 1; + break; + }+SEPARATE_ZVAL(search); SEPARATE_ZVAL(replace); SEPARATE_ZVAL(subject);@@ -2549,7 +2643,7 @@and add the result to the return_value array. */ while (zend_hash_get_current_data(Z_ARRVAL_PP(subject), (void **)&subject_entry) == SUCCESS) { MAKE_STD_ZVAL(result); - php_str_replace_in_subject(*search, *replace, subject_entry, result); + php_str_replace_in_subject(*search, *replace, subject_entry, result, boyer); /* Add to return array */switch(zend_hash_get_current_key_ex(Z_ARRVAL_PP(subject), &string_key, &string_key_len, &num_key, 0, NULL)) { @@ -2565,7 +2659,7 @@zend_hash_move_forward(Z_ARRVAL_PP(subject)); } } else { /* if subject is not an array */ - php_str_replace_in_subject(*search, *replace, subject, return_value); + php_str_replace_in_subject(*search, *replace, subject, return_value, boyer); }} /* }}} */ -- PHP CVS Mailing List (http://www.php.net/) To unsubscribe, e-mail: php-cvs-unsubscribe@lists.php.net For additional commands, e-mail: php-cvs-help@lists.php.net To contact the list administrators, e-mail: php-list-admin@lists.php.net