PHP源码阅读strtr

发表于

strtr

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

1
2
3
4
echo strtr('hello world', 'hw', 'ab'); // 第一种 aello borld
echo strtr('hello world', 'hw', 'a'); // 第二种 aello world
echo strtr('hello world', ['hello' => 'hi']); // 第三种 hi world
echo strtr('hello world', ['he' => 'th', 'hello' => 'hi']); // 第四种 hi world

时间复杂度

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

源码

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

1
2
3
4
5
6
7
8
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的相应位置的字符。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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)

1
2
3
4
5
6
7
8
9
10
11
// 搜索被替换的字符串的所有位置
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)++;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
// 先构造所有 被替换的字符串
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语言代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
$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;