上一節(PHP內核探索之變量（3）- hash table),我們已經知道，數組在PHP的底層實際上是HashTable（鏈接法解決沖突），本文將對最常用的函數系列-數組操作的相關函數做進一步的跟蹤。

本文主要內容：

可以說，數組是PHP中使用最廣泛的數據結構之一，正因如此，PHP為開發者提供了豐富的數組操作函數（參見http://cn2.php.net/manual/en/ref.array.php ）， 大約有80個，這對于絕大多數的數組操作而言，已經足夠了。如果按照數組操作的類別來分，這些函數大致可以分為如下幾類（不完全分類）：

PHP中，數組相關的操作有如下特點：

接下來，我們以幾個具體的函數為例，深入探索PHP中數組函數的實現。

由于數組的操作實際上是對HashTable的相關操作，因而，我們再次貼出HashTable的結構和結構圖，以便參考。

HashTable的結構：

typedef struct _hashtable {    uint nTableSize;    uint nTableMask;    uint nNumOfElements;    ulong nNextFreeElement;    Bucket *pInternalPointer;   /* Used for element traversal */    Bucket *pListHead;    Bucket *pListTail;    Bucket **arBuckets;    dtor_func_t pDestructor;    zend_bool persistent;    unsigned char nApplyCount;    zend_bool bApplyProtection;#if ZEND_DEBUG    int inconsistent;#endif} HashTable;

對應的結構圖：

接下來，我們以幾個數組操作函數為例，來查看具體的操作實現。

1.　　數組定義和初始化

在高級語言中，一條簡單的語句往往需要在底層中經過很多的操作步驟才能實現，對于數組的操作亦是如此，例如：$arr = array(1, 2, 3);這樣的賦值語句，實際上會經歷數組初始化(array_init)、添加數組元素(ADD_ARRAY_ELEMENT)、賦值這些步驟才會實現。

（1）數組的初始化這是通過array_init來實現的,實際上是調用_array_init來完成數組的初始化：

ZEND_API int _array_init(zval *arg, uint size ZEND_FILE_LINE_DC){    ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg));        _zend_hash_init(Z_ARRVAL_P(arg), size, NULL, ZVAL_PTR_DTOR, 0 ZEND_FILE_LINE_RELAY_CC);    Z_TYPE_P(arg) = IS_ARRAY;    return SUCCESS;}

其中zval *arg即為我們要初始化的數組，第一句ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg));宏展開后，實際上是：

(*arg).value.ht = (HashTable *) emalloc_rel(sizeof(HashTable));

之后則通過_zend_hash_init函數實現初始化HashTable,并把arg的zval類型設置為IS_ARRAY:

（2） zend_hash_init 上一節已經介紹過，這里不再贅述

2.　　數組遍歷 prev, next和current

在PHP中，我們可以使用prev, next，current等完成對數組的訪問，例如：

$traverse = array('one', 'after', 'another'); $cur = current($traverse);echo "cur:", $cur.PHP_EOL; $next = next($traverse);echo "next: ", $next.PHP_EOL; $nextnext = next($traverse);echo "nextnext: ", $nextnext.PHP_EOL; $prev = prev($traverse);echo "prev: ", $prev.PHP_EOL;

我們知道，HashTable結構體中，有一個成員pInternalPointer, 這個成員便是控制數組的訪問指針的。以prev函數為例，對HashTable的遍歷實現如下：

（1）將訪問指針移動一步

這是通過zend_hash_move_backwards(array);來實現的，具體來說，先找到數組的當前位置或指針:

然后訪問這個指針的pListLast找到上一個元素：

移動指針的過程如下(可以看出，在不傳遞pos參數時，實際上移動的是ht-> pInternalPointer這個指針)：

ZEND_API int zend_hash_move_backwards_ex(HashTable *ht, HashPosition *pos){        HashPosition *current = pos ? pos : &ht->pInternalPointer;    IS_CONSISTENT(ht);      if (*current) {        *current = (*current)->pListLast;        return SUCCESS;    } else        return FAILURE;}

（2）如果需要返回值，由于訪問指針已經移動到了適當的位置，則直接獲取當前指針指向的元素：

if (return_value_used) {　　if (zend_hash_get_current_data(array, (void **) &entry) == FAILURE) {    RETURN_FALSE;　　}　　RETURN_ZVAL(*entry, 1, 0);}

獲取當前指針指向的元素是通過zend_hash_get_current_data來實現的：

#define zend_hash_get_current_data(ht, pData)     zend_hash_get_current_data_ex(ht, pData, NULL) ZEND_API int zend_hash_get_current_data_ex(HashTable *ht, void **pData, HashPosition *pos){        Bucket *p;         /* 獲取當前指針 */    p = pos ? (*pos) : ht->pInternalPointer;    IS_CONSISTENT(ht);     if (p) {        *pData = p->pData;        return SUCCESS;    } else {        return FAILURE;    }}

知道了prev函數的原理，我們不難想象next, current, reset等函數的實現機制。

prev函數的源碼：

PHP_FUNCTION(prev){    HashTable *array;    zval **entry;     if (zend_parse_parameters(ZEND_NUM_ARGS() TSRMLS_CC, "H", &array) == FAILURE) {        return;    }     zend_hash_move_backwards(array);     if (return_value_used) {        if (zend_hash_get_current_data(array, (void **) &entry) == FAILURE) {            RETURN_FALSE;        }        RETURN_ZVAL(*entry, 1, 0);    }}

3.　　數組排序 asort，arsort,ksort等

php中提供了大量的函數用于數組的排序，如用于普通排序的sort函數，用于逆序排序的rsort函數，用于按照鍵名排序的函數ksort和krsort, 用于自定義比較函數的usort和uksort等，可以說非常豐富。我們以sort函數的實現為例，探索PHP中排序算法的實現。

sort函數的簽名為：

bool sort ( array &$array [, int $sort_flags = SORT_REGULAR ] )

其中sort_flags會影響排序的結果，該值可以是：SORT_REGULAR，SORT_NUMERIC，SORT_STRING，SORT_LOCALE_STRING，SORT_NATURAL等

（ http://cn2.php.net/manual/zh/function.sort.php ）

sort函數的實現過程如下：

（1）由于sort_flags會影響比較函數的行為，因此首先需要根據sort_type確定用于元素比較的函數（自然排序，整數排序，還是字符串排序，區分大小寫還是不區分）。這是通過php_set_compare_func來實現的：

static void php_set_compare_func(int sort_type TSRMLS_DC){         switch (sort_type & ~PHP_SORT_FLAG_CASE) {        case PHP_SORT_NUMERIC:            ARRAYG(compare_func) = numeric_compare_function;            break;         case PHP_SORT_STRING:            ARRAYG(compare_func) = sort_type & PHP_SORT_FLAG_CASE ? <br>                 string_case_compare_function : string_compare_function;            break;         case PHP_SORT_NATURAL:            ARRAYG(compare_func) = sort_type & PHP_SORT_FLAG_CASE ? <br>                 string_natural_case_compare_function : string_natural_compa     re_function;            break; #if HAVE_STRCOLL        case PHP_SORT_LOCALE_STRING:            ARRAYG(compare_func) = string_locale_compare_function;            break;#endif         case PHP_SORT_REGULAR:        default:            ARRAYG(compare_func) = compare_function;//默認使用compare_function            break;    }}

switch (sort_type & ~PHP_SORT_FLAG_CASE)這是什么意思呢？首先，PHP針對排序設置的sort_type常量有：

#define PHP_SORT_REGULAR                0#define PHP_SORT_NUMERIC                1#define PHP_SORT_STRING                 2#define PHP_SORT_DESC                   3#define PHP_SORT_ASC                    4#define PHP_SORT_LOCALE_STRING          5#define PHP_SORT_NATURAL                6#define PHP_SORT_FLAG_CASE              8

其次，sort函數的第二個參數可以設置為SORT_NATURAL | SORT_FLAG_CASE或者SORT_STRING | SORT_FLAG_CASE. 因此sort_type & ~PHP_SORT_FLAG_CASE的含義為：排除PHP_SORT_FLAG_CASE標志之后的值，得到的值可以是PHP_SORT_NUMERIC，PHP_SORT_STRING，PHP_SORT_NATURAL，PHP_SORT_LOCALE_STRING，PHP_SORT_REGULAR。而在PHP_SORT_STRING和PHP_SORT_NATURAL中，還需要通過sort_type & PHP_SORT_FLAG_CASE來判斷是否是不區分大小寫的排序（即是否使用了SORT_FLAG_CASE標志）。

(2) 設置完sort_type之后，調用zend_hash_sort完成實際的排序：

zend_hash_sort的函數簽名是：

ZEND_API int zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compar, int renumber TSRMLS_DC);

其中:

我們首先跟蹤zend_hash_sort的基本過程，而后再追蹤zend_qsort的具體實現。

由于數組排序并不會改變數組中的元素，而只是改變了數組中元素的位置，因而，對底層而言，實際上只是對全局的雙鏈表進行排序，這顯然需要n個額外的空間（n是數組元素個數）：

然后遍歷雙鏈表，將雙鏈表的每個節點存儲到臨時空間（c數組，每個元素是個bucket *）中：

p = ht->pListHead;i = 0;while (p) {    arTmp[i] = p;    p = p->pListNext;    i++;}

現在，可以調用排序函數對數組進行排序了：

實際上是：

zend_qsort((void *) arTmp, i, sizeof(Bucket *), compar TSRMLS_CC);

排序之后，雙鏈表中節點的位置發生了變化，因而需要調整指針的指向。首先調整pListHead，并設置pListTail為NULL:

然后遍歷數組，分別設置每一個節點的pListLast和pListNext:

arTmp[0]->pListLast = NULL;if (i > 1) {    arTmp[0]->pListNext = arTmp[1];    for (j = 1; j < i-1; j++) {        arTmp[j]->pListLast = arTmp[j-1];        arTmp[j]->pListNext = arTmp[j+1];    }    arTmp[j]->pListLast = arTmp[j-1];    arTmp[j]->pListNext = NULL;} else {    arTmp[0]->pListNext = NULL;}

最后設置HashTable的pListTail：

排序過程如下所示：

排序之后，調整指針走向之后的HashTable：

現在，已經知道zend_hash_sort的基本過程了，我們接著跟蹤一下zend_qsort的實現(函數位于Zend/zend_qsort.c)，該函數的簽名為：

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC);

這實際上是Zend實現的快速排序算法，主要包括兩個部分：

1. _zend_qsort_swap(void *a, void *b, size_t siz) 用于交換任意類型的兩個值，與我們經常使用的swap(int *a ,int *b), 或者swap(char *a, char *b), _zend_qsort_swap有更好的通用性，因而它的實現也略微復雜， 具體交換過程為：

(1) . 以sizeof(int)為步長, 交換指針指向的值:

for (i = sizeof(int); i <= siz; i += sizeof(int)) {    t_i = *tmp_a_int;    *tmp_a_int++ = *tmp_b_int;    *tmp_b_int++ = t_i;}

這個循環執行完畢后，有兩種可能的情況：一種是siz剛好是sizeof(int)的整倍數,那么交換就已經完成了，因為指針a和指針b指向的內存空間的值已經完全得到了交換。另一種情況是, siz并不是sizeof(int)的整倍數,那么實際上上述交換步驟多交換了一些字節的值(例如對于sizeof(int)=4的情況，可能多交換了1,2,3個字節的內存的值)，那么對于這多交換出來的一部分，還需要交換回去。怎么做呢？

(2). 使用char指針一個一個字節的交換：

tmp_a_char = (char *) tmp_a_int;tmp_b_char = (char *) tmp_b_int; for (i = i - sizeof(int) + 1; i <= siz; ++i) {//i控制交換次數    t_c = *tmp_a_char;    *tmp_a_char++ = *tmp_b_char;    *tmp_b_char++ = t_c;}

這樣就完成了交換。

2. zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC). 快速排序算法，與常見的快速排序算法不同，這是非遞歸版本的快速排序。算法的基本思想是：使用QSORT_STACK_SIZE大小的棧（實際上是數組，不過每次都取數組的末尾元素，當做棧使用）存儲快排的開始索引和結束索引(指針）,從而將遞歸的快排過程轉換為非遞歸的。

綜上,我們可以得出PHP排序函數的一般特點：

　　a. 需要額外的空間，空間復雜度是O(n), 因而應該盡量避免對很大的數組排序.

　　b. 底層使用快速排序，平均時間復雜度是O（n*lgn）

zend_qsort的 實現代碼（有興趣的童鞋可以研究一下實現細節）：

ZEND_API void zend_qsort(void *base, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC){    /* 存儲開始和結束指針的棧 */    void           *begin_stack[QSORT_STACK_SIZE];    void           *end_stack[QSORT_STACK_SIZE];    register char  *begin;    register char  *end;    register char  *seg1;    register char  *seg2;         /* partition index */    register char  *seg2p;    register int    loop;         /* pivot index */    uint            offset;         begin_stack[0] = (char *) base;    end_stack[0]   = (char *) base + ((nmemb - 1) * siz);     for (loop = 0; loop >= 0; --loop) {        begin = begin_stack[loop];        end   = end_stack[loop];                 /* partition的過程 */        while (begin < end) {        　　offset = (end - begin) >> 1;        　　_zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz);         　　seg1 = begin + siz;        　　seg2 = end;         　　while (1) {            /* 從左向右找 */            for (; seg1 < seg2 && compare(begin, seg1 TSRMLS_CC) > 0;        　　　　 　　seg1 += siz);                             　　/* 從右向左找 */            　　for (; seg2 >= seg1 && compare(seg2, begin TSRMLS_CC) > 0;            　　　　seg2 -= siz);                             　　if (seg1 >= seg2)                break;                             　　/* 交換seg1和seg2指向的值 */            　　_zend_qsort_swap(seg1, seg2, siz);                             　　/* 指針移動，每次都是siz步長 */            　　seg1 += siz;            　　seg2 -= siz;            }             _zend_qsort_swap(begin, seg2, siz);             seg2p = seg2;                         /* 右半部分 */            if ((seg2p - begin) <= (end - seg2p)) {                if ((seg2p + siz) < end) {                　　begin_stack[loop] = seg2p + siz;                　　end_stack[loop++] = end;                }                end = seg2p - siz;            }            else { /* 左半部分 */                if ((seg2p - siz) > begin) {                    begin_stack[loop] = begin;                    end_stack[loop++] = seg2p - siz;                }                begin = seg2p + siz;            }        }    }}

4. 數組合并 array_merge

array_merge用于合并兩個或者多個數組（實際上，array_merge可以僅傳入一個數組參數如array_merge($a) ）例如:

$a = array('index' => "a",1 =>'a');$b = array('index' => "b",1 =>'b');print_r(array_merge($a, $b));

結果是：

Array(    [index] => b    [0] => a    [1] => b)

那么，對于array_merge, PHP底層是如何處理字符串索引和數字索引的呢？

因此，實際上是通過php_array_merge_or_replace_wrapper來完成的，繼續查看php_array_merge_or_replace_wrapper的實現:

static void php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAMETERS, int recursive, int replace);

注意傳入的參數,recursive=0, replace=0 ( 不遞歸merge,數字索引不替換 ) ，而INTERNAL_FUNCTION_PARAMETERS是：

#define INTERNAL_FUNCTION_PARAMETERS int ht, zval *return_value, zval **return_value_ptr, zval *this_ptr, int return_value_used     TSRMLS_DC

array_merge的基本過程是：

(1) 確定初始化數組的大?。ㄊ褂迷刈疃嗟臄到M的大小作為結果數組的初始大小），初始化數組：

for (i = 0; i < argc; i++) {      /* 不是數組 */    if (Z_TYPE_PP(args[i]) != IS_ARRAY) {        php_error_docref(NULL TSRMLS_CC, E_WARNING, "Argument #%d is not an array", i + 1);        efree(args);        RETURN_NULL();    } else {        int num = zend_hash_num_elements(Z_ARRVAL_PP(args[i]));                            /* 使用元素最多的數組的大小作為init_size的大小 */        if (num > init_size) {            init_size = num;        }    }} array_init_size(return_value, init_size);

return_value是個zval *, 它指向返回值的zval

(2) 對array_merge參數中的每個數組，依次執行php_array_merge(由于replace=0和recursive=0)， 我們只看第一個分支：

for (i = 0; i < argc; i++) {SEPARATE_ZVAL(args[i]); if (!replace) {        php_array_merge(Z_ARRVAL_P(return_value), Z_ARRVAL_PP(args[i]), recursive TSRMLS_CC);    }}

SEPARATE_ZVAL用于創建一個與原始數據相同的zval，避免在操作的過程中修改參數的值（參數是非引用傳遞的情況下）。而真正的merge過程是通過php_array_merge來實現的。

(3) merge的過程

由于PHP數組中包含字符串索引和數字索引，對于這兩類不同的索引，merge的處理是不同的（replace=0, recursive=0，只看對應的分支）：

switch (zend_hash_get_current_key_ex(src, &string_key, &string_key_len, &num_key, 0, &pos)){    case HASH_KEY_IS_STRING:        Z_ADDREF_PP(src_entry);        zend_hash_update(dest, string_key, string_key_len, src_entry, sizeof(zval *), NULL);    break;     case HASH_KEY_IS_LONG:        Z_ADDREF_PP(src_entry);        zend_hash_next_index_insert(dest, src_entry, sizeof(zval *), NULL);    break;}

上述代碼表明：對于字符串索引，PHP在執行array_merge的時候，會更新字符串索引的值，其結果就是參數靠后數組的值會覆蓋靠前的數組的值。而對于數字型索引，PHP執行的zend_hash_next_index_insert操作，也就是插入一個新的元素，這同時也更改了鍵（例如原來的key=2, array_merge之后，可能變成了0）。這也解釋了最開始array_merge腳本的輸出：

$a = array('index' => "a",1 =>'a');$b = array('index' => "b",1 =>'b');print_r(array_merge($a, $b));

更多的數組操作函數我們不再一一介紹，只要知道了HashTable的結構，要理解這些實現，并不困難。

由于寫作匆忙，本文難免會有錯誤之處，敬請批評指正。

ps: 近期正在補習C語言/操作系統的相關基礎，尤其是指針/內存管理這一塊，有一起的同學，歡迎交流。

鄭重聲明：本文版權歸原作者所有，轉載文章僅為傳播更多信息之目的，如作者信息標記有誤，請第一時間聯系我們修改或刪除，多謝。