PHP内核探索之变量（四）- 数组操作-PHP Tutorial-php.cn

PHP内核探索之变量（4）- 数组操作

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

本文主要内容：

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

一、PHP中提供的数组操作函数

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

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

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

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

接下来，我们以几个具体的函数为例，深入探索PHP中数组函数的实现。

二、数组操作的实现

由于数组的操作实际上是对HashTable的相关操作，因而，我们再次贴出HashTable的结构和结构图，以便参考。

HashTable的结构：

<span style="color: #000000;">typedef struct _hashtable {    uint nTableSize;    uint nTableMask;    uint nNumOfElements;    ulong nNextFreeElement;    Bucket </span>*pInternalPointer;   <span style="color: #008000;">/*</span><span style="color: #008000;"> Used for element traversal </span><span style="color: #008000;">*/</span><span style="color: #000000;">    Bucket </span>*<span style="color: #000000;">pListHead;    Bucket </span>*<span style="color: #000000;">pListTail;    Bucket </span>**<span style="color: #000000;">arBuckets;    dtor_func_t pDestructor;    zend_bool persistent;    unsigned char nApplyCount;    zend_bool bApplyProtection;</span><span style="color: #008000;">#</span><span style="color: #008000;">if ZEND_DEBUG</span><span style="color: #000000;">    int inconsistent;</span><span style="color: #008000;">#</span><span style="color: #008000;">endif</span>} HashTable;

Copy after login

对应的结构图：

接下来，我们以几个数组操作函数为例，来查看具体的操作实现。

1.　　数组定义和初始化

<span style="font-size: 14px;">在高级语言中，一条简单的语句往往需要在底层中经过很多的操作步骤才能实现，对于数组的操作亦是如此，例如：$arr = array(1, 2, 3);这样的赋值语句，实际上会经历数组初始化(array_init)、添加数组元素(ADD_ARRAY_ELEMENT)、赋值这些步骤才会实现。</span>

Copy after login

<span style="font-size: 14px;">（1）数组的初始化<br>这是通过<span style="color: #0000ff;">array_init</span>来实现的,实际上是调用<span style="color: #0000ff;">_array_init</span>来完成数组的初始化：<br></span>

Copy after login

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;}

Copy after login

其中zval *arg即为我们要初始化的数组，第一句ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg));宏展开后，实际上是：

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

Copy after login

之后则通过_zend_hash_init函数实现初始化HashTable,并把arg的zval类型设置为IS_ARRAY:

Z_TYPE_P(arg) = IS_ARRAY;

Copy after login

（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;

Copy after login

我们知道，HashTable结构体中，有一个成员pInternalPointer, 这个成员便是控制数组的访问指针的。以prev函数为例，对HashTable的遍历实现如下：

（1）将访问指针移动一步

这是通过zend_hash_move_backwards(array);来实现的，具体来说，先找到数组的当前位置或指针:

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

Copy after login

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

*current = (*current)->pListLast;

Copy after login

移动指针的过程如下(可以看出，在不传递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;}

Copy after login

（2）如果需要返回值，由于访问指针已经移动到了适当的位置，则直接获取当前指针指向的元素：

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

Copy after login

获取当前指针指向的元素是通过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;    }}

Copy after login

知道了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);    }}

Copy after login

3.　　数组排序 asort，arsort,ksort等

php中提供了大量的函数用于数组的排序，如用于普通排序的sort函数，用于逆序排序的rsort函数，用于按照键名排序的函数ksort和krsort, 用于自定义比较函数的usort和uksort等，可以说非常丰富。我们以sort函数的实现为例，探索PHP中排序算法的实现。

sort函数的签名为：

bool <span style="color: #008080;">sort</span> ( <span style="color: #0000ff;">array</span> &<span style="color: #800080;">$array</span> [, int <span style="color: #800080;">$sort_flags</span> = SORT_REGULAR ] )

Copy after login

其中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;    }}

Copy after login

switch (sort_type & ~PHP_SORT_FLAG_CASE)这是什么意思呢？首先，PHP针对排序设置的sort_type常量有：

<span style="color: #0000ff;">#define</span> PHP_SORT_REGULAR                0<span style="color: #0000ff;">#define</span> PHP_SORT_NUMERIC                1<span style="color: #0000ff;">#define</span> PHP_SORT_STRING                 2<span style="color: #0000ff;">#define</span> PHP_SORT_DESC                   3<span style="color: #0000ff;">#define</span> PHP_SORT_ASC                    4<span style="color: #0000ff;">#define</span> PHP_SORT_LOCALE_STRING          5<span style="color: #0000ff;">#define</span> PHP_SORT_NATURAL                6<span style="color: #0000ff;">#define</span> PHP_SORT_FLAG_CASE              8

Copy after login

其次，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);

Copy after login

zend_hash_sort的函数签名是：

ZEND_API <span style="color: #0000ff;">int</span> zend_hash_sort(HashTable *ht, sort_func_t sort_func, compare_func_t compar, <span style="color: #0000ff;">int</span> renumber TSRMLS_DC);

Copy after login

其中:

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

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

由于数组排序并不会改变数组中的元素，而只是改变了数组中元素的位置，因而，对底层而言，实际上只是对全局的双链表进行排序，这显然需要n个额外的空间（n是数组元素个数）：

arTmp = (Bucket **) pemalloc(ht->nNumOfElements * sizeof(Bucket *), ht->persistent);

Copy after login

然后遍历双链表，将双链表的每个节点存储到临时空间（c数组，每个元素是个bucket *）中：

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

Copy after login

现在，可以调用排序函数对数组进行排序了：

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

Copy after login

实际上是：

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

排序之后，双链表中节点的位置发生了变化，因而需要调整指针的指向。首先调整pListHead，并设置pListTail为NULL:

ht->pListHead = arTmp[0];ht->pListTail = NULL;

Copy after login

然后遍历数组，分别设置每一个节点的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;}

Copy after login

最后设置HashTable的pListTail：

ht->pListTail = arTmp[i-1];

Copy after login

排序过程如下所示：

排序之后，调整指针走向之后的HashTable：

现在，已经知道zend_hash_sort的基本过程了，我们接着跟踪一下zend_qsort的实现(函数位于Zend/zend_qsort.c)，该函数的签名为：

ZEND_API <span style="color: #0000ff;">void</span> zend_qsort(<span style="color: #0000ff;">void</span> *<span style="color: #0000ff;">base</span>, size_t nmemb, size_t siz, compare_func_t compare TSRMLS_DC);

Copy after login

这实际上是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)为步长, 交换指针指向的值:

<span style="color: #0000ff;">for</span> (i = <span style="color: #0000ff;">sizeof</span>(<span style="color: #0000ff;">int</span>); i <= siz; i += <span style="color: #0000ff;">sizeof</span>(<span style="color: #0000ff;">int</span><span style="color: #000000;">)) {    t_i </span>= *<span style="color: #000000;">tmp_a_int;    </span>*tmp_a_int++ = *<span style="color: #000000;">tmp_b_int;    </span>*tmp_b_int++ =<span style="color: #000000;"> t_i;}</span>

Copy after login

这个循环执行完毕后，有两种可能的情况：一种是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;}

Copy after login

这样就完成了交换。

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;			}		}	}}

Copy after login

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));

Copy after login

结果是：

<span style="color: #000000;">Array(    </span><span style="color: #800000; font-weight: bold;">[</span><span style="color: #800000;">index</span><span style="color: #800000; font-weight: bold;">]</span> =<span style="color: #000000;">> b    </span><span style="color: #800000; font-weight: bold;">[</span><span style="color: #800000;">0</span><span style="color: #800000; font-weight: bold;">]</span> =<span style="color: #000000;">> a    </span><span style="color: #800000; font-weight: bold;">[</span><span style="color: #800000;">1</span><span style="color: #800000; font-weight: bold;">]</span> =<span style="color: #000000;">> b)</span>

Copy after login

那么，对于array_merge, PHP底层是如何处理字符串索引和数字索引的呢？

PHP_FUNCTION(array_merge){    php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTHRU, 0, 0);}

Copy after login

因此，实际上是通过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)<span style="color: #008000;">;</span>

Copy after login

注意传入的参数,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

Copy after login

array_merge的基本过程是：

(1) 确定初始化数组的大小（使用元素最多的数组的大小作为结果数组的初始大小），初始化数组：

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);

Copy after login

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);    }}

Copy after login

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;}

Copy after login

上述代码表明：对于字符串索引，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));

Copy after login

更多的数组操作函数我们不再一一介绍，只要知道了HashTable的结构，要理解这些实现，并不困难。

由于写作匆忙，本文难免会有错误之处，敬请批评指正。

ps: 近期正在补习C语言/操作系统的相关基础，尤其是指针/内存管理这一块，有一起的同学，欢迎交流。

三、参考文献

http://blog.csdn.net/a600423444/article/details/7073854
http://www.nowamagic.net/librarys/veda/detail/1455
http://www.nowamagic.net/librarys/veda/detail/1474
http://www.phppan.com/2010/01/php-source-code5-array/

Related labels：

array hashtable php sort zend

source：php.cn

Previous article：gvim用着不知道按到哪里出现的提示语不是中文了，如何改回中文，请各路大神帮帮忙，多谢！ Next article：php遇到中文分割有关问题

Statement of this Website

The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn