上一节(PHP内核探索之变量（3）- hash table),我们已经知道，数组在PHP的底层实际上是HashTable（链接法解决冲突），本文将对最常用的函数系列-数组操作的相关函数做进一步的跟踪。

本文主要内容：

1. PHP中提供的数组操作函数
2. 数组操作函数的实现
3. 结语参考文献

可以说，数组是PHP中使用最广泛的数据结构之一，正因如此，PHP为开发者提供了丰富的数组操作函数（参见http://cn2.php.net/manual/en/ref.array.php ）， 大约有80个，这对于绝大多数的数组操作而言，已经足够了。如果按照数组操作的类别来分，这些函数大致可以分为如下几类（不完全分类）：

1. 数组遍历相关函数：如PRev, next, current, end,reset, each等
2. 数组排序相关：如sort, rsort, asort, arsort, ksort, krsort, uasort, uksort
3. 数组查找相关: 如in_array, array_search, array_key_exists等
4. 数组分割、合并相关： array_slice, array_splice, implode, array_chunk, array_combine等
5. 数组交并差：如array_merge, array_diff, array_diff_*, array_intersect, array_intersect_*
6. 作为stack/queue容器的数组： 如array_push, array_pop, array_shift
7. 其他的数组操作：array_fill, array_flip, array_sum, array_reverse等

PHP中，数组相关的操作有如下特点：

1. 数组操作函数是通过扩展的形式(ext/standard/array.c)提供的,因此也会经历扩展的MINIT, RINIT, RSHUTDOWN, MSHUTDOWN等过程。
2. 在底层，定义PHP函数的方式是PHP_FUNCTION(function_name)，例如数组操作函数array_merge在底层是PHP_FUNCTION(array_merge)
3. 由于数组的底层实现是HashTable，因而数组的绝大多数操作实际上都是针对HashTable的操作，这是通过HashTable API实现的。

接下来，我们以几个具体的函数为例，深入探索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:

Z_TYPE_P(arg) = 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);来实现的，具体来说，先找到数组的当前位置或指针:

HashPosition *current = pos ? pos : &ht->pInternalPointer

然后访问这个指针的pListLast找到上一个元素：

*current = (*current)->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 ?                  string_case_compare_function : string_compare_function;            break;        case PHP_SORT_NATURAL:            ARRAYG(compare_func) = sort_type & PHP_SORT_FLAG_CASE ?                  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(Z_ARRVAL_P(array), zend_qsort, php_array_data_compare, 1 TSRMLS_CC);

zend_hash_sort的函数签名是：

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

其中:

1. HashTable * ht 指向HashTable的指针
2. Sort_func_t sort_func 用于排序的函数，因此，实际上是调用zend_qsort来完成排序。
3. Compare_func_t compar: 用于排序的比较函数，前一步骤已经设置。

我们首先跟踪zend_hash_sort的基本过程，而后再追踪zend_qsort的具体实现。

由于数组排序并不会改变数组中的元素，而只是改变了数组中