Detailed explanation of the use of strtr function in php

strtr

Convert specific characters in a string, but this function can be used in many ways.

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

##Time complexity

O(n), the worst is O(n*m)

Source code

The source code is analyzed one by one according to each situation.

The first and second types are also the most commonly used, but in the second type, only 'h' is converted to 'a', and 'w' is not processed. In this method of substitution, the shorter one will prevail. If one of from and to is an empty string, the original string will be returned directly.

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

Next, we mainly look at the php_strtr_ex method and how to achieve character conversion. The source code is implemented using a hash table. The hash table maps each character of from to the corresponding character of 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]];
    }
}

The third and fourth from are arrays. If from is an array, the situation is not a one-to-one character conversion, it is a character conversion. String to string conversion, convert the entire key string into a value string.

The third type, the from array has only one key-value pair. The implementation idea is to search the position of the key (replaced string) in the main string according to the kmp algorithm. If found, replace it with value. . The efficiency of kmp itself is O(n), so if m times are replaced in the string, in this case the efficiency of strtr will be 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)++;
}

The fourth method is to replace multiple strings through arrays. This is the least efficient in various situations.

// 先构造所有 被替换的字符串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'，最先匹配到hellowhile (len >= minlen) {// 如果从长度hash表里面匹配到被替换的字符串里可能的长度，就从from数组里面找到替换的键值对zend_hash_str_findif ((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++;
}

This situation is a bit complicated. The following PHP pseudo code Translate the above C language code

$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;

The above is the detailed content of Detailed explanation of the use of strtr function in php. For more information, please follow other related articles on the PHP Chinese website!