1. 云栖社区>
  2. PHP教程>
  3. 正文

PHP源码阅读strtr

作者:用户 来源:互联网 时间:2017-12-01 20:54:36

php阅读源码strtr

PHP源码阅读strtr - 摘要: 本文讲的是PHP源码阅读strtr, strtr 转换字符串中特定的字符,但是这个函数使用的方式多种。 echo strtr('hello world', 'hw', 'ab'); // 第一种 aello borldecho strtr('hello world', 'hw

strtr

转换字符串中特定的字符,但是这个函数使用的方式多种。

echo strtr('hello world', 'hw', 'ab'); // 第一种 aello borldecho strtr('hello world', 'hw', 'a'); // 第二种 aello worldecho strtr('hello world', ['hello' => 'hi']); // 第三种 hi worldecho strtr('hello world', ['he' => 'th', 'hello' => 'hi']); // 第四种 hi world


时间复杂度

O(n),最差是O(n*m)

源码

以下根据每种情况逐一分析源码。
第一种、第二种,也是最常用的,但第二种,只有’h’转换成’a’,’w’没有被处理。这种方式的替换,会以短的一方为准。如果from和to其中一个是空串,会直接返回原字符串。

RETURN_STR(php_strtr_ex(str,          Z_STRVAL_P(from),          to,          MIN(Z_STRLEN_P(from), to_len)));// 从源码MIN(Z_STRLEN_P(from), to_len))可以看出来,以from、to两个字符串短的为准,剩余的会被忽略掉,所以可以解释第二种情况'w'被忽略掉// 同理,以下to中的'b'也会被忽略掉strtr('hello world', 'h', 'ab'); // aello world

接着,我们主要看下php_strtr_ex方法,是怎么实现字符转换。源码是使用hash表实现,hash表把from的每个字符,一一对应为to的相应位置的字符。

static zend_string *php_strtr_ex(zend_string *str, char *str_from, char *str_to, size_t trlen){    // trlen的值就是MIN(Z_STRLEN_P(from), to_len))    // 先构建一个hash表,用php伪代码来解释第一种情况构建好的hash表    // array('g'=>'g','h'=>'a','i'=>'i','w'=>'b')    unsigned char xlat[256], j = 0;    do { xlat[j] = j; } while (++j != 256);    for (i = 0; i < trlen; i++) {        xlat[(size_t)(unsigned char) str_from[i]] = str_to[i];    }        // 接着遍历字符串,从hash表中找到转换的字符    for (i = 0; i < ZSTR_LEN(str); i++) {        if (ZSTR_VAL(str)[i] != xlat[(size_t)(unsigned char) ZSTR_VAL(str)[i]]) {            new_str = zend_string_alloc(ZSTR_LEN(str), 0);            memcpy(ZSTR_VAL(new_str), ZSTR_VAL(str), i);            // 从hash表中找到转换的字符            ZSTR_VAL(new_str)[i] = xlat[(size_t)(unsigned char) ZSTR_VAL(str)[i]];            break;        }    }    for (;i < ZSTR_LEN(str); i++) {        // 从hash表中找到转换的字符        ZSTR_VAL(new_str)[i] = xlat[(size_t)(unsigned char) ZSTR_VAL(str)[i]];    }}


第三种、第四种from是个数组,如果from是数组,情况就不是一对一的字符转换,是字符串对字符串的转换了,把key整个字符串转换成value字符串。

第三种,from数组只有一对键值对,实现思路是,根据kmp算法在主串中搜索key(被替换的字符串)的位置,如果找到,就使用value替换掉。kmp本身的效率是O(n),所以如果字符串内进行了m次替换,这种情况下strtr效率会是O(n*m)

// 搜索被替换的字符串的所有位置e = s = ZSTR_VAL(new_str);end = ZSTR_VAL(haystack) + ZSTR_LEN(haystack);// php_memnstr搜索 被替换的字符串 的所有位置,并替换掉for (p = ZSTR_VAL(haystack); (r = (char*)php_memnstr(p, needle, needle_len, end)); p = r + needle_len) {    memcpy(e, p, r - p);    e += r - p;    memcpy(e, str, str_len);    e += str_len;    (*replace_count)++;}

第四种,通过数组替换多个字符串,这种是各种情况效率最差的

// 先构造所有 被替换的字符串ZEND_HASH_FOREACH_STR_KEY(pats, str_key) {    len = ZSTR_LEN(str_key);    // 计算所有 被替换的字符串 最长和最短值    if (len > maxlen) {        maxlen = len;    }    if (len < minlen) {        minlen = len;    }    // 记录每个key长度值的hash值    num_bitset[len / sizeof(zend_ulong)] |= Z_UL(1) << (len % sizeof(zend_ulong));    // 记录每个key首字符的hash值    bitset[((unsigned char)ZSTR_VAL(str_key)[0]) / sizeof(zend_ulong)] |= Z_UL(1) << (((unsigned char)ZSTR_VAL(str_key)[0]) % sizeof(zend_ulong));    } ZEND_HASH_FOREACH_END();// 辅助两个hash表,替换的字符串old_pos = pos = 0;while (pos <= slen - minlen) {    key = str + pos;    // 如果从首字符的hash表匹配到,表示以key[0]字符开头的有可能是被替换的字符串    if (bitset[((unsigned char)key[0]) / sizeof(zend_ulong)] & (Z_UL(1) << (((unsigned char)key[0]) % sizeof(zend_ulong)))) {        len = maxlen;        if (len > slen - pos) {            len = slen - pos;        }        // key从maxlen循环到minlen,所以,第四种'hello'和'he',最先匹配到hello        while (len >= minlen) {            // 如果从长度hash表里面匹配到被替换的字符串里可能的长度,就从from数组里面找到替换的键值对zend_hash_str_find            if ((num_bitset[len / sizeof(zend_ulong)] & (Z_UL(1) << (len % sizeof(zend_ulong))))) {                entry = zend_hash_str_find(pats, key, len);                if (entry != NULL) {                    zend_string *s = zval_get_string(entry);                    smart_str_appendl(&result, str + old_pos, pos - old_pos);                    smart_str_append(&result, s);                    old_pos = pos + len;                    pos = old_pos - 1;                    zend_string_release(s);                    break;                }            }            len--;        }    }    pos++;}


这种情况有点复杂,下面的php伪代码翻译一下以上的C语言代码

$bitset = array_fill(0, 255, 0); // 首字符的hash表$num_bitset = array_fill(0, 255, 0); // key长度值的hash值$min_len = PHP_INT_MAX;$max_len = 0;$len = 0;// echo strtr('hello world', ['he' => 'th', 'hello' => 'hi']);$pats = ['he', 'hello'];foreach($pats as $v){    $len = strlen($v);    if($len > $max_len) {        $max_len = $len;    }    if($len < $min_len) {        $min_len = $len;    }    $num_bitset[intdiv($len,8)] |= 1 << ($len%8);    $bitset[intdiv(ord($v[0]),8)] |= 1 << (ord($v[0])%8);}// print_r(array_unique($num_bitset));// print_r(array_unique($bitset));// 例如我们匹配hello,首字符是h,长度5// 以下两行就是以上C语言的while循环里面两个if判断echo $bitset[intdiv(ord('h'),8)] & 1 << (ord('h')%8),PHP_EOL;echo $num_bitset[intdiv(5,8)] & 1 << (5%8),PHP_EOL;

本文链接:JC博客--PHP源码阅读strtr

原创文章,转载请注明来源

 

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索php , 阅读 , 源码 strtr ,以便于您获取更多的相关知识。