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的结构：
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);
其中:
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);
然后遍历双链表，将双链表的每个节点存储到临时空间（c数组，每个元素是个bucket *）中：
p = ht->plisthead;i = 0;while (p) { artmp[i] = p; p = p->plistnext; i++;}
现在，可以调用排序函数对数组进行排序了：
(*sort_func)((void *) artmp, i, sizeof(bucket *), compar tsrmls_cc);
实际上是：
zend_qsort((void *) artmp, i, sizeof(bucket *), compar tsrmls_cc);
排序之后，双链表中节点的位置发生了变化，因而需要调整指针的指向。首先调整plisthead，并设置plisttail为null:
ht->plisthead = artmp[0];ht->plisttail = null;
然后遍历数组，分别设置每一个节点的plistlast和plistnext:
artmp[0]->plistlast = null;if (i > 1) { artmp[0]->plistnext = artmp[1]; for (j = 1; 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：
ht->plisttail = artmp[i-1];
排序过程如下所示：
排序之后，调整指针走向之后的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 1; _zend_qsort_swap(begin, begin + (offset - (offset % siz)), siz); seg1 = begin + siz; seg2 = end; while (1) { /* 从左向右找 */ for (; seg1 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) 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_function(array_merge){ php_array_merge_or_replace_wrapper(internal_function_param_passthru, 0, 0);}
因此，实际上是通过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) 确定初始化数组的大小（使用元素最多的数组的大小作为结果数组的初始大小），初始化数组：
for (i = 0; i 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 a,1 =>'a');$b = array('index' => b,1 =>'b');print_r(array_merge($a, $b));
更多的数组操作函数我们不再一一介绍，只要知道了hashtable的结构，要理解这些实现，并不困难。
由于写作匆忙，本文难免会有错误之处，敬请批评指正。
ps: 近期正在补习c语言/操作系统的相关基础，尤其是指针/内存管理这一块，有一起的同学，欢迎交流。
   三、参考文献http://blog.csdn.net/a600423444/article/details/7073854http://www.nowamagic.net/librarys/veda/detail/1455http://www.nowamagic.net/librarys/veda/detail/1474http://www.phppan.com/2010/01/php-source-code5-array/