本文将对最常用的函数系列-数组操作的相关函数做进一步的跟踪。本文主要内容：PHP中提供的数组操作函数数组操作函数的实现结语参考文献一、PHP
中提供的数组操作函数可以说，数组是PHP中使用最广泛的数据结构之一，正因如此，PHP为开发者提供了丰富的数组操作函数（参见http
://cn2.php.net/manual/en/ref.array.phphttp://cn2.php.net/manual/e
n/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等数组分割、合并相关：arra
y_slice,array_splice,implode,array_chunk,array_combine等数组交并差：
如array_merge,array_diff,array_diff_,array_intersect,array_in
tersect_作为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(functio
n_name)，例如数组操作函数array_merge在底层是PHP_FUNCTION(array_merge)由于数组的底层实现
是HashTable，因而数组的绝大多数操作实际上都是针对HashTable的操作，这是通过HashTableAPI实现的。接下
来，我们以几个具体的函数为例，深入探索PHP中数组函数的实现。二、数组操作的实现由于数组的操作实际上是对HashTable的相关操
作，因而，我们再次贴出HashTable的结构和结构图，以便参考。HashTable的结构：typedefstruct_has
htable{uintnTableSize;uintnTableMask;uintnNumOfElements;u
longnNextFreeElement;BucketpInternalPointer;/Usedforeleme
nttraversal/BucketpListHead;BucketpListTail;Bucketar
Buckets;dtor_func_tpDestructor;zend_boolpersistent;unsigned
charnApplyCount;zend_boolbApplyProtection;#ifZEND_DEBUGinti
nconsistent;#endif}HashTable;对应的结构图：?接下来，我们以几个数组操作函数为例，来查看具体的操作实
现。1.数组定义和初始化在高级语言中，一条简单的语句往往需要在底层中经过很多的操作步骤才能实现，对于数组的操作亦是如此，例如：$
arr=array(1,2,3);这样的赋值语句，实际上会经历数组初始化(array_init)、添加数组元素(ADD_A
RRAY_ELEMENT)、赋值这些步骤才会实现。（1）数组的初始化这是通过array_init来实现的,实际上是调用_array
_init来完成数组的初始化：ZEND_APIint_array_init(zvalarg,uintsizeZEND
_FILE_LINE_DC){ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg));_zend_hash
_init(Z_ARRVAL_P(arg),size,NULL,ZVAL_PTR_DTOR,0ZEND_FILE_LIN
E_RELAY_CC);Z_TYPE_P(arg)=IS_ARRAY;returnSUCCESS;}其中zvalar
g即为我们要初始化的数组，第一句ALLOC_HASHTABLE_REL(Z_ARRVAL_P(arg));宏展开后，实际上是：(
arg).value.ht=(HashTable)emalloc_rel(sizeof(HashTable));之后则通
过_zend_hash_init函数实现初始化HashTable,并把arg的zval类型设置为IS_ARRAY:1Z_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);ec
ho"cur:",$cur.PHP_EOL;$next=next($traverse);echo"next:",$
next.PHP_EOL;$nextnext=next($traverse);echo"nextnext:",$nex
tnext.PHP_EOL;$prev=prev($traverse);echo"prev:",$prev.PHP_E
OL;我们知道，HashTable结构体中，有一个成员pInternalPointer,这个成员便是控制数组的访问指针的。以pr
ev函数为例，对HashTable的遍历实现如下：（1）将访问指针移动一步这是通过zend_hash_move_backwards
(array);来实现的，具体来说，先找到数组的当前位置或指针:1HashPositioncurrent=pos?po
s:&ht->pInternalPointer然后访问这个指针的pListLast找到上一个元素：1current=(
current)->pListLast;移动指针的过程如下(可以看出，在不传递pos参数时，实际上移动的是ht->pIntern
alPointer这个指针)：ZEND_APIintzend_hash_move_backwards_ex(HashTable
ht,HashPositionpos){HashPositioncurrent=pos?pos:&ht
->pInternalPointer;IS_CONSISTENT(ht);if(current){current
=(current)->pListLast;returnSUCCESS;}elsereturnFAILURE;}
（2）如果需要返回值，由于访问指针已经移动到了适当的位置，则直接获取当前指针指向的元素：if(return_value_used
){if(zend_hash_get_current_data(array,(void)&entry)==FA
ILURE){RETURN_FALSE;}RETURN_ZVAL(entry,1,0);}获取当前指针指向的元素是通
过zend_hash_get_current_data来实现的：#definezend_hash_get_current_dat
a(ht,pData)\zend_hash_get_current_data_ex(ht,pData,NULL)ZEN
D_APIintzend_hash_get_current_data_ex(HashTableht,voidpDa
ta,HashPositionpos){Bucketp;/获取当前指针/p=pos?(pos)
:ht->pInternalPointer;IS_CONSISTENT(ht);if(p){pData=p-
>pData;returnSUCCESS;}else{returnFAILURE;}}知道了prev函数的原理，我
们不难想象next,?current,?reset等函数的实现机制。prev函数的源码：PHP_FUNCTION(prev){H
ashTablearray;zvalentry;if(zend_parse_parameters(ZEND_NU
M_ARGS()TSRMLS_CC,"H",&array)==FAILURE){return;}zend_ha
sh_move_backwards(array);if(return_value_used){if(zend_hash
_get_current_data(array,(void)&entry)==FAILURE){RETURN_F
ALSE;}RETURN_ZVAL(entry,1,0);}}3.数组排序asort，arsort,ksort等p
hp中提供了大量的函数用于数组的排序，如用于普通排序的sort函数，用于逆序排序的rsort函数，用于按照键名排序的函数ksort
和krsort,用于自定义比较函数的usort和uksort等，可以说非常丰富。我们以sort函数的实现为例，探索PHP中排序算
法的实现。sort函数的签名为：boolsort(array&$array[,int$sort_flags=SO
RT_REGULAR])其中sort_flags会影响排序的结果，该值可以是：SORT_REGULAR，SORT_NUMERI
C，SORT_STRING，SORT_LOCALE_STRING，SORT_NATURAL等（?http://cn2.php.ne
t/manual/zh/function.sort.phphttp://cn2.php.net/manual/zh/functio
n.sort.php?）sort函数的实现过程如下：（1）由于sort_flags会影响比较函数的行为，因此首先需要根据sort_
type确定用于元素比较的函数（自然排序，整数排序，还是字符串排序，区分大小写还是不区分）。这是通过php_set_compare
_func来实现的：staticvoidphp_set_compare_func(intsort_typeTSRMLS_D
C){switch(sort_type&~PHP_SORT_FLAG_CASE){casePHP_SORT_NUME
RIC:ARRAYG(compare_func)=numeric_compare_function;break;cas
ePHP_SORT_STRING:ARRAYG(compare_func)=sort_type&PHP_SORT_FL
AG_CASE?
string_case_compare_function:string_compare_func
tion;break;casePHP_SORT_NATURAL:ARRAYG(compare_func)=sort_
type&PHP_SORT_FLAG_CASE?
string_natural_case_compare_func
tion:string_natural_compare_function;break;#ifHAVE_STRC
OLLcasePHP_SORT_LOCALE_STRING:ARRAYG(compare_func)=string_lo
cale_compare_function;break;#endifcasePHP_SORT_REGULAR:defau
lt:ARRAYG(compare_func)=compare_function;//默认使用compare_functio
nbreak;}}switch(sort_type&~PHP_SORT_FLAG_CASE)这是什么意思呢？首先，PHP
针对排序设置的sort_type常量有：#definePHP_SORT_REGULAR0#def
inePHP_SORT_NUMERIC1#definePHP_SORT_STRING
2#definePHP_SORT_DESC3#definePHP
_SORT_ASC4#definePHP_SORT_LOCALE_STRING
5#definePHP_SORT_NATURAL6#definePHP_SORT_F
LAG_CASE8其次，sort函数的第二个参数可以设置为SORT_NATURAL|SORT_FL
AG_CASE或者SORT_STRING|SORT_FLAG_CASE.因此sort_type&~PHP_SORT_FL
AG_CASE的含义为：排除PHP_SORT_FLAG_CASE标志之后的值，得到的值可以是PHP_SORT_NUMERIC，PH
P_SORT_STRING，PHP_SORT_NATURAL，PHP_SORT_LOCALE_STRING，PHP_SORT_RE
GULAR。而在PHP_SORT_STRING和PHP_SORT_NATURAL中，还需要通过sort_type&PHP_SO
RT_FLAG_CASE来判断是否是不区分大小写的排序（即是否使用了SORT_FLAG_CASE标志）。(2)设置完sort_t
ype之后，调用zend_hash_sort完成实际的排序：1zend_hash_sort(Z_ARRVAL_P(array),
www.mntuku.cnzend_qsort,php_array_data_compare,1TSRMLS_CC);ze
nd_hash_sort的函数签名是：ZEND_APIintzend_hash_sort(HashTableht,sor
t_func_tsort_func,compare_func_tcompar,intrenumberTSRMLS_DC
);其中:HashTableht?指向HashTable的指针Sort_func_tsort_func?用于排序的函数
，因此，实际上是调用zend_qsort来完成排序。Compare_func_tcompar:用于排序的比较函数，前一步骤已经
设置。我们首先跟踪zend_hash_sort的基本过程，而后再追踪zend_qsort的具体实现。由于数组排序并不会改变数组中的
元素，而只是改变了数组中元素的位置，因而，对底层而言，实际上只是对全局的双链表进行排序，这显然需要n个额外的空间（n是数组元素个数
）：1arTmp=(Bucket)pemalloc(ht->nNumOfElements?sizeof(Bucke
t),ht->persistent);然后遍历双链表，将双链表的每个节点存储到临时空间（c数组，每个元素是个bucket
）中：p=ht->pListHead;i=0;while(p){arTmp[i]=p;p=p->pList
Next;i++;}现在，可以调用排序函数对数组进行排序了：1(sort_func)((void)arTmp,i,?s
izeof(Bucket),comparTSRMLS_CC);实际上是：zend_qsort((void?)arTmp
,i,?sizeof(Bucket),comparTSRMLS_CC);排序之后，双链表中节点的位置发生了变化，因而需要
调整指针的指向。首先调整pListHead，并设置pListTail为NULL:12ht->pListHead=arTmp[0
];ht->pListTail=NULL;然后遍历数组，分别设置每一个节点的pListLast和pListNext:arTmp
[0]->pListLast=NULL;if(i>1){arTmp[0]->pListNext=arTmp[1]
;for(j=1;jpListLast=arTmp[j-1];a
rTmp[j]->pListNext=arTmp[j+1];}arTmp[j]->pListLast=arTmp[j-
1];arTmp[j]->pListNext=NULL;}else{arTmp[0]->pListNext=NUL
L;}最后设置HashTable的pListTail：1ht->pListTail=arTmp[i-1];排序过程如下所示：?
排序之后，调整指针走向之后的HashTable：?现在，已经知道zend_hash_sort的基本过程了，我们接着跟踪一下zend
_qsort的实现(函数位于Zend/zend_qsort.c)，该函数的签名为：ZEND_APIvoidzend_qsort
(voidbase,size_tnmemb,size_tsiz,compare_func_tcompareTSR
MLS_DC);这实际上是Zend实现的快速排序算法，主要包括两个部分：1._zend_qsort_swap(voida,
voidb,size_tsiz)用于交换任意类型的两个值，与我们经常使用的swap(inta,intb),或
者swap(chara,charb),_zend_qsort_swap有更好的通用性，因而它的实现也略微复杂，具体交
换过程为：(1).以sizeof(int)为步长,交换指针指向的值:for(i=sizeof(int);i<=s
iz;i+=sizeof(int)){t_i=tmp_a_int;tmp_a_int++=tmp_b_i
nt;tmp_b_int++=t_i;}这个循环执行完毕后，有两种可能的情况：一种是siz刚好是sizeof(int)的整
倍数,那么交换就已经完成了，因为指针a和指针b指向的内存空间的值已经完全得到了交换。另一种情况是,siz并不是sizeof(in
t)的整倍数,那么实际上上述交换步骤多交换了一些字节的值(例如对于sizeof(int)=4的情况，可能多交换了1,2,3个字节的
内存的值)，那么对于这多交换出来的一部分，还需要交换回去。怎么做呢？(2).使用char指针一个一个字节的交换：tmp_a_ch
ar=(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.?z
end_qsort(void?base,?size_t?nmemb,?size_t?siz,?compare_func_t?co
mpareTSRMLS_DC).快速排序算法，与常见的快速排序算法不同，这是非递归版本的快速排序。算法的基本思想是：使用QSO
RT_STACK_SIZE大小的栈（实际上是数组，不过每次都取数组的末尾元素，当做栈使用）存储快排的开始索引和结束索引(指针）,从
而将递归的快排过程转换为非递归的。综上,我们可以得出PHP排序函数的一般特点：a.需要额外的空间，空间复杂度是O(n),因而
应该尽量避免对很大的数组排序.b.底层使用快速排序，平均时间复杂度是O（nlgn）zend_qsort的实现代码（有兴趣的
童鞋可以研究一下实现细节）：ZEND_APIvoidzend_qsort(voidbase,size_tnmemb,
size_tsiz,compare_func_tcompareTSRMLS_DC){/存储开始和结束指针的栈/
voidbegin_stack[QSORT_STACK_SIZE];voiden
d_stack[QSORT_STACK_SIZE];registercharbegin;registerchar
end;registercharseg1;registercharseg2;/partitioni
ndex/registercharseg2p;registerintloop;/pivotin
dex/uintoffset;begin_stack[0]=(char)base;e
nd_stack[0]=(char)base+((nmemb-1)siz);for(loop=
0;loop>=0;--loop){begin=begin_stack[loop];end=end_s
tack[loop];/partition的过程/while(beginend-begin)>>1;_zend_qsort_swap(begin,begin+(offset-(of
fset%siz)),siz);seg1=begin+siz;seg2=end;while(1
){/从左向右找/for(;seg1CC)>0;seg1+=siz);/从右向左找/for(;seg2>=seg1&&c
ompare(seg2,beginTSRMLS_CC)>0;seg2-=siz);if(seg1>=s
eg2)break;/交换seg1和seg2指向的值/_zend_qsort_swap(seg1,seg2,
siz);/指针移动，每次都是siz步长/seg1+=siz;seg2-=siz;}_zen
d_qsort_swap(begin,seg2,siz);seg2p=seg2;/右半部分/if((s
eg2p-begin)<=(end-seg2p)){if((seg2p+siz)in_stack[loop]=seg2p+siz;end_stack[loop++]=end;}end=s
eg2p-siz;}else{/左半部分/if((seg2p-siz)>begin){begi
n_stack[loop]=begin;end_stack[loop++]=seg2p-siz;}begin=
seg2p+siz;}}}}4.?数组合并array_mergearray_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)那么，对于ar
ray_merge,PHP底层是如何处理字符串索引和数字索引的呢？1234PHP_FUNCTION(array_merge){?
php_array_merge_or_replace_wrapper(INTERNAL_FUNCTION_PARAM_PASSTH
RU,0,0);}因此，实际上是通过php_array_merge_or_replace_wrapper来完成的，继续查看ph
p_array_merge_or_replace_wrapper的实现:staticvoidphp_array_merge_o
r_replace_wrapper(INTERNAL_FUNCTION_PARAMETERS,intrecursive,in
treplace);注意传入的参数,recursive=0,replace=0?(不递归merge,数字索引不替换)，而
INTERNAL_FUNCTION_PARAMETERS是：#defineINTERNAL_FUNCTION_PARAMETER
Sintht,zvalreturn_value,zvalreturn_value_ptr,zvalthis
_ptr,intreturn_value_usedTSRMLS_DCarray_merge的基本过程是：(1)确定初
始化数组的大小（使用元素最多的数组的大小作为结果数组的初始大小），初始化数组：for(i=0;i{/不是数组/if(Z_TYPE_PP(args[i])!=IS_ARRAY){php_error_doc
ref(NULLTSRMLS_CC,E_WARNING,"Argument#%disnotanarray",i
+1);efree(args);RETURN_NULL();}else{intnum=zend_hash_nu
m_elements(Z_ARRVAL_PP(args[i]));/使用元素最多的数组的大小作为init_size的大小
/if(num>init_size){init_size=num;}}}array_init_size(r
eturn_value,init_size);return_value是个zval,它指向返回值的zval(2)对arra
y_merge参数中的每个数组，依次执行php_array_merge(由于replace=0和recursive=0)，我们只
看第一个分支：for(i=0;ieplace){php_array_merge(Z_ARRVAL_P(return_value),Z_ARRVAL_PP(a
rgs[i]),recursiveTSRMLS_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)){caseHASH_KEY_IS_STRING:Z_ADDREF_PP(src_entry);zend_hash_update(dest,string_key,string_key_len,src_entry,sizeof(zval),NULL);break;caseHASH_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语言/操作系统的相关基础，尤其是指针/内存管理这一块，有一起的同学，欢迎交流。 |
|
