PHP7源码之array_unique函数分析

以下源码基于 PHP 7.3.8

array array_unique ( array $array [, int $sort_flags = SORT_STRING ] )
(PHP 4 >= 4.0.1, PHP 5, PHP 7)
array_unique — 移除数组中重复的值

参数说明：
array：输入的数组。
sort_flag：（可选）排序类型标记，用于修改排序行为，主要有以下值：

SORT_REGULAR - 按照通常方法比较（不修改类型）
SORT_NUMERIC - 按照数字形式比较
SORT_STRING - 按照字符串形式比较
SORT_LOCALE_STRING - 根据当前的本地化设置，按照字符串比较。

array_unique 函数的源代码在 /ext/standard/array.c 文件中。由于

PHP_FUNCTION(array_unique){ 
    // code...
}

篇幅过长，完整代码不在这里贴出来了，可以参见 GitHub 贴出的源代码。

定义变量

????zval?*array;
????uint32_t?idx;
????Bucket?*p;
????struct?bucketindex?*arTmp,?*cmpdata,?*lastkept;
????unsigned?int?i;
????zend_long?sort_type?=?PHP_SORT_STRING; // 默认的排序规则
????compare_func_t?cmp;

首先是定义变量，array_unique 函数默认使用 PHP_SORT_STRING 排序，PHP_SORT_STRING 在 /ext/standard/php_array.h 头文件中定义。

#define?PHP_SORT_STRING?????????????2

可以看到和开头PHP函数的 sort_flag 参数默认的预定义常量 SORT_STRING 很像。

compare_func_t cmp 这行代码没看懂，不清楚是做什么的。compare_func_t 在 /Zend/zend_types.h 中定义：

typedef?int??(*compare_func_t)(const?void?*,?const?void?*);

应该是定义了一个指向 int 型返回值且带有两个指针常量参数的函数指针类型，没有查到相关资料，先搁着，继续往下看。

参数解析

    ZEND_PARSE_PARAMETERS_START(1,?2)
        Z_PARAM_ARRAY(array)
????????Z_PARAM_OPTIONAL
????????Z_PARAM_LONG(sort_type)
????ZEND_PARSE_PARAMETERS_END();

ZEND_PARSE_PARAMETERS_START(1,?2)，第一个参数表示必传参数个数，第二个参数表示最多参数个数，即该函数参数范围是 1-2 个。

数组元素个数判断

    if?(Z_ARRVAL_P(array)->nNumOfElements?<=?1)?{??/*?nothing?to?do?*/
????????ZVAL_COPY(return_value,?array);
????????return;
????}

这段代码很容易看懂，当数组为空或只有 1 个元素时，无需去重操作，直接将 array 拷贝到新数组 return_value来返回即可。

分配持久化内存

这一步只有当 sort_type 为 PHP_SORT_STRING 时才执行。在下面可以看到调用 zend_hash_init 初始化了 array，调用 zend_hash_destroy 释放持久化的 内存。

????if?(sort_type?==?PHP_SORT_STRING)?{
????????HashTable?seen;
????????zend_long?num_key;
????????zend_string?*str_key;
????????zval?*val;
        // 初始化HashTable
????????zend_hash_init(&seen,?zend_hash_num_elements(Z_ARRVAL_P(array)),?NULL,?NULL,?0);
        // 初始化数组
????????array_init(return_value);
        // 遍历数组
????????ZEND_HASH_FOREACH_KEY_VAL_IND(Z_ARRVAL_P(array),?num_key,?str_key,?val)?{
????????????zval?*retval;
            // 如果数组元素值是字符串
????????????if?(Z_TYPE_P(val)?==?IS_STRING)?{
????????????????retval?=?zend_hash_add_empty_element(&seen,?Z_STR_P(val));
????????????}?else?{
????????????????zend_string?*tmp_str_val;
????????????????zend_string?*str_val?=?zval_get_tmp_string(val,?&tmp_str_val);
????????????????retval?=?zend_hash_add_empty_element(&seen,?str_val);
????????????????zend_tmp_string_release(tmp_str_val);
????????????}
????????????if?(retval)?{
????????????????/*?First?occurrence?of?the?value?*/
????????????????if?(UNEXPECTED(Z_ISREF_P(val)?&&?Z_REFCOUNT_P(val)?==?1))?{
????????????????????ZVAL_DEREF(val);
????????????????}
????????????????Z_TRY_ADDREF_P(val);
????????????????if?(str_key)?{
????????????????????zend_hash_add_new(Z_ARRVAL_P(return_value),?str_key,?val);
????????????????}?else?{
????????????????????zend_hash_index_add_new(Z_ARRVAL_P(return_value),?num_key,?val);
????????????????}
????????????}
????????}?ZEND_HASH_FOREACH_END();
        // 释放哈希内存
????????zend_hash_destroy(&seen);
????????return;
????}

设置比较函数

????cmp?=?php_get_data_compare_func(sort_type,?0);
    // 将数组拷贝到返回数组中
    RETVAL_ARR(zend_array_dup(Z_ARRVAL_P(array)));

进行具体比较顺序控制的函数指针是 cmp，是通过向 php_get_data_compare_func 传入 sort_type 和 0 得到的，sort_type 也就是 SORT_STRING 这样的标记。

php_get_data_compare_func 在 array.c 文件中定义（即与 array_unique 函数同一文件），代码过长，这里只贴出默认标记为 SORT_STRING 的代码：

static?compare_func_t?php_get_data_compare_func(zend_long?sort_type,?int?reverse)?/*?{{{?*/
{
    switch?(sort_type?&?~PHP_SORT_FLAG_CASE)?{
????????case?PHP_SORT_NUMERIC:
????????????// code...
????????case?PHP_SORT_STRING:
????????????if?(sort_type?&?PHP_SORT_FLAG_CASE)?{
????????????????if?(reverse)?{
????????????????????return?php_array_reverse_data_compare_string_case;
????????????????}?else?{
????????????????????return?php_array_data_compare_string_case;
????????????????}
????????????}?else?{
????????????????if?(reverse)?{
????????????????????return?php_array_reverse_data_compare_string;
????????????????}?else?{
????????????????????return?php_array_data_compare_string;
????????????????}
????????????}
????????????break;
    // code...

在前面的代码中，我们可以看到，cmp?=?php_get_data_compare_func(sort_type,?0); 的第二个参数，即参数 reverse 的值为 0，也就是当 sort_type 为 PHP_SORT_STRING 时，调用的是 php_array_data_compare_string 函数，即 SORT_STRING 采用 php_array_data_compare_string 进行比较。继续展开 php_array_data_compare_string 函数：

static?int?php_array_data_compare_string(const?void?*a,?const?void?*b)?/*?{{{?*/
{
????Bucket?*f;
????Bucket?*s;
????zval?*first;
????zval?*second;
????f?=?(Bucket?*)?a;
????s?=?(Bucket?*)?b;
????first?=?&f->val;
????second?=?&s->val;
????if?(UNEXPECTED(Z_TYPE_P(first)?==?IS_INDIRECT))?{
????????first?=?Z_INDIRECT_P(first);
????}
????if?(UNEXPECTED(Z_TYPE_P(second)?==?IS_INDIRECT))?{
????????second?=?Z_INDIRECT_P(second);
????}
????return?string_compare_function(first,?second);
}
/*?}}}?*/

可以得到这样一条调用链：

SORT_STRING -> php_get_data_compare_func -> php_array_data_compare_string -> string_compare_function;

string_compare_function 是一个 ZEND API，在 /Zend/zend_operators.c 中定义：

ZEND_API?int?ZEND_FASTCALL?string_compare_function(zval?*op1,?zval?*op2)?/*?{{{?*/
{
????if?(EXPECTED(Z_TYPE_P(op1)?==?IS_STRING)?&&
????????EXPECTED(Z_TYPE_P(op2)?==?IS_STRING))?{
????????if?(Z_STR_P(op1)?==?Z_STR_P(op2))?{
????????????return?0;
????????}?else?{
????????????return?zend_binary_strcmp(Z_STRVAL_P(op1),?Z_STRLEN_P(op1),?Z_STRVAL_P(op2),?Z_STRLEN_P(op2));
????????}
????}?else?{
????????zend_string?*tmp_str1,?*tmp_str2;
????????zend_string?*str1?=?zval_get_tmp_string(op1,?&tmp_str1);
????????zend_string?*str2?=?zval_get_tmp_string(op2,?&tmp_str2);
????????int?ret?=?zend_binary_strcmp(ZSTR_VAL(str1),?ZSTR_LEN(str1),?ZSTR_VAL(str2),?ZSTR_LEN(str2));
????????zend_tmp_string_release(tmp_str1);
????????zend_tmp_string_release(tmp_str2);
????????return?ret;
????}
}
/*?}}}?*/

可以看到，SORT_STRING 使用 zend_binary_strcmp 函数进行字符串比较。下面的代码是 zend_binary_strcmp 的实现（也在 /Zend/zend_operators.c 中）：

ZEND_API?int?ZEND_FASTCALL?zend_binary_strcmp(const?char?*s1,?size_t?len1,?const?char?*s2,?size_t?len2)?/*?{{{?*/
{
????int?retval;
????if?(s1?==?s2)?{
????????return?0;
????}
????retval?=?memcmp(s1,?s2,?MIN(len1,?len2));
????if?(!retval)?{
????????return?(int)(len1?-?len2);
????}?else?{
????????return?retval;
????}
}
/*?}}}?*/

上面的代码是比较两个字符串。也就是 SORT_STRING 排序方式的底层实现是 C 语言的 memcmp，即它对两个字符串从前往后，按照逐个字节比较，一旦字节有差异，就终止并比较出大小。

数组排序

????/*?create?and?sort?array?with?pointers?to?the?target_hash?buckets?*/
    // 根据 target_hash buckets 的指针创建数组并排序
????arTmp?=?(struct?bucketindex?*)?pemalloc((Z_ARRVAL_P(array)->nNumOfElements?+?1)?*?sizeof(struct?bucketindex),?GC_FLAGS(Z_ARRVAL_P(array))?&?IS_ARRAY_PERSISTENT);
????for?(i?=?0,?idx?=?0;?idx?<?Z_ARRVAL_P(array)->nNumUsed;?idx++)?{
????????p?=?Z_ARRVAL_P(array)->arData?+?idx;
????????if?(Z_TYPE(p->val)?==?IS_UNDEF)?continue;
????????if?(Z_TYPE(p->val)?==?IS_INDIRECT?&&?Z_TYPE_P(Z_INDIRECT(p->val))?==?IS_UNDEF)?continue;
????????arTmp[i].b?=?*p;
????????arTmp[i].i?=?i;
????????i++;
????}
????ZVAL_UNDEF(&arTmp[i].b.val);
????zend_sort((void?*)?arTmp,?i,?sizeof(struct?bucketindex),
????????????cmp,?(swap_func_t)array_bucketindex_swap);

这段代码初始化一个新的数组，然后将值拷贝到新数组，然后调用 zend_sort 排序函数对数组进行排序。排序算法在 /Zend/zend_sort.c 中实现，备注有这样一句话：

Derived?from?LLVM‘s?libc++?implementation?of?std::sort.

这个排序算法是基于 LLVM 的 libc++ 中的 std::sort 实现的，算是快排的优化版，当元素数小于等于16时有特殊的优化，当元素数小于等于 5 时直接通过 if else 嵌套判断排序。代码就不贴出来了。

数组去重

回到 array_unique 上，继续看代码：

/*?go?through?the?sorted?array?and?delete?duplicates?from?the?copy?*/
????lastkept?=?arTmp;
????for?(cmpdata?=?arTmp?+?1;?Z_TYPE(cmpdata->b.val)?!=?IS_UNDEF;?cmpdata++)?{
????????if?(cmp(lastkept,?cmpdata))?{
????????????lastkept?=?cmpdata;
????????}?else?{
????????????if?(lastkept->i?>?cmpdata->i)?{
????????????????p?=?&lastkept->b;
????????????????lastkept?=?cmpdata;
????????????}?else?{
????????????????p?=?&cmpdata->b;
????????????}
????????????if?(p->key?==?NULL)?{
????????????????zend_hash_index_del(Z_ARRVAL_P(return_value),?p->h);
????????????}?else?{
????????????????if?(Z_ARRVAL_P(return_value)?==?&EG(symbol_table))?{
????????????????????zend_delete_global_variable(p->key);
????????????????}?else?{
????????????????????zend_hash_del(Z_ARRVAL_P(return_value),?p->key);
????????????????}
????????????}
????????}
????}
????pefree(arTmp,?GC_FLAGS(Z_ARRVAL_P(array))?&?IS_ARRAY_PERSISTENT);

遍历排序好的数组，然后删除重复的元素。

众周所知，快排的时间复杂度是O(nlogn)，因此，array_unique 函数的时间复杂度是O(nlogn)。array_unique 底层调用了快排算法，加大了函数运行的时间开销，当数据量很大时，会导致整个函数的运行较慢。

PHP7源码之array_unique函数分析

原文：https://www.cnblogs.com/sunshineliulu/p/11723624.html