PHP7源碼之array_unique函數分析
- 2019 年 10 月 23 日
- 筆記
以下源碼基於 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 底層調用了快排演算法，加大了函數運行的時間開銷，當數據量很大時，會導致整個函數的運行較慢。
