strstr
返回 haystack 字符串從 needle 第一次出現(xiàn)的位置開始到 haystack 結(jié)尾的字符串艺栈。
strstr( string $haystack, mixed $needle[, bool $before_needle = FALSE] ) : string
源碼實現(xiàn)
/* {{{ proto string strstr(string haystack, string needle[, bool part])
Finds first occurrence of a string within another */
PHP_FUNCTION(strstr)
{
zval *needle;
zend_string *haystack;
const char *found = NULL;
char needle_char[2];
zend_long found_offset;
zend_bool part = 0;
ZEND_PARSE_PARAMETERS_START(2, 3)
Z_PARAM_STR(haystack)
Z_PARAM_ZVAL(needle)
Z_PARAM_OPTIONAL
Z_PARAM_BOOL(part)
ZEND_PARSE_PARAMETERS_END();
if (Z_TYPE_P(needle) == IS_STRING) {
if (!Z_STRLEN_P(needle)) {
php_error_docref(NULL, E_WARNING, "Empty needle");
RETURN_FALSE;
}
found = php_memnstr(ZSTR_VAL(haystack), Z_STRVAL_P(needle), Z_STRLEN_P(needle), ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
} else {
//如果 needle 不是一個字符串湿右，那么它將被轉(zhuǎn)化為整型并且作為字符的序號來使用毅人。
if (php_needle_char(needle, needle_char) != SUCCESS) {
RETURN_FALSE;
}
needle_char[1] = 0;
php_error_docref(NULL, E_DEPRECATED,
"Non-string needles will be interpreted as strings in the future. " \
"Use an explicit chr() call to preserve the current behavior");
found = php_memnstr(ZSTR_VAL(haystack), needle_char, 1, ZSTR_VAL(haystack) + ZSTR_LEN(haystack));
}
if (found) {
found_offset = found - ZSTR_VAL(haystack);
if (part) {
RETURN_STRINGL(ZSTR_VAL(haystack), found_offset);
} else {
RETURN_STRINGL(found, ZSTR_LEN(haystack) - found_offset);
}
}
RETURN_FALSE;
}
/* }}} */
核心算法實現(xiàn)追蹤 php.h 文件： php_memnstr
#define php_memnstr zend_memnstr
追蹤 zend_operators.h ： zend_memnstr
static zend_always_inline const char *
zend_memnstr(const char *haystack, const char *needle, size_t needle_len, const char *end)
{
const char *p = haystack;
const char ne = needle[needle_len-1];
ptrdiff_t off_p;
size_t off_s;
if (needle_len == 1) {
return (const char *)memchr(p, *needle, (end-p));
}
off_p = end - haystack;
off_s = (off_p > 0) ? (size_t)off_p : 0;
if (needle_len > off_s) {
return NULL;
}
//當(dāng)輸入的字符串小于 1024字符或查找字符串長度小于9 的時候吭狡，使用系統(tǒng)庫 glibc memchr 查找
if (EXPECTED(off_s < 1024 || needle_len < 9)) { /* glibc memchr is faster when needle is too short */
end -= needle_len;
while (p <= end) {
if ((p = (const char *)memchr(p, *needle, (end-p+1))) && ne == p[needle_len-1]) {
if (!memcmp(needle+1, p+1, needle_len-2)) {
return p;
}
}
if (p == NULL) {
return NULL;
}
p++;
}
return NULL;
} else {
//使用 Sunday 算法查找
return zend_memnstr_ex(haystack, needle, needle_len, end);
}
}
zend_memnstr_ex 實現(xiàn)
ZEND_API const char* ZEND_FASTCALL zend_memnstr_ex(const char *haystack, const char *needle, size_t needle_len, const char *end) /* {{{ */
{
unsigned int td[256];
register size_t i;
register const char *p;
if (needle_len == 0 || (end - haystack) < needle_len) {
return NULL;
}
//前綴表
zend_memnstr_ex_pre(td, needle, needle_len, 0);
p = haystack;
end -= needle_len;
while (p <= end) {
for (i = 0; i < needle_len; i++) {
if (needle[i] != p[i]) {
break;
}
}
if (i == needle_len) {
return p;
}
if (UNEXPECTED(p == end)) {
return NULL;
}
p += td[(unsigned char)(p[needle_len])];
}
return NULL;
}
/* }}} */
zend_memnstr_ex_pre 實現(xiàn) （Sunday 字符串匹配算法划煮，速度最快的字符串匹配算法，）
- 如果字母表與模式的長度相比較大场刑，則算法平均執(zhí)行O（n / m）比較
/*
* String matching - Sunday algorithm
* http://www.iti.fh-flensburg.de/lang/algorithmen/pattern/sundayen.htm
*/
static zend_always_inline void zend_memnstr_ex_pre(unsigned int td[], const char *needle, size_t needle_len, int reverse) /* {{{ */ {
int i;
//生成256字符表
for (i = 0; i < 256; i++) {
td[i] = needle_len + 1;
}
if (reverse) {
for (i = needle_len - 1; i >= 0; i--){
// 整型 [ ASCII 碼] => X
td[(unsigned char)needle[i]] = i + 1;
}
} else {
size_t i;
for (i = 0; i < needle_len; i++) {
td[(unsigned char)needle[i]] = (int)needle_len - i;
}
}
}
/* }}} */
