PHP カーネルで調べる変数 (4) - 配列操作-PHPチュートリアル-php.cn

PHP カーネルによって探索される変数 (4) - 配列操作

前のセクション (PHP カーネルによって探索される変数 (3) - ハッシュテーブル) では、配列が実際には配列の下部にある HashTable であることがすでにわかりました。 PHP (競合を解決するためのリンク方法) について、この記事では、配列操作の最も一般的に使用される関数シリーズ関連の関数をさらに追跡します。

この記事の主な内容:

PHP で提供される配列演算関数
配列演算関数の実装
まとめ参考文献

1. PHP で提供される配列演算関数

配列は PHP で最も広く使用されているデータ構造の 1 つであると言えます。このため、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_*
スタック/キューコンテナとしての配列: 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 での配列関数の実装を詳しく調べるために、いくつかの特定の関数を例として取り上げます。

2. 配列演算の実装

配列演算は実際には 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;

ログイン後にコピー

対応する構造図:

次に、具体的な演算の実装を確認するために、例としていくつかの配列演算関数を取り上げます。

1. 配列の定義と初期化

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

ログイン後にコピー

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

ログイン後にコピー

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

ログイン後にコピー

の後、HashTable は _zend_hash_init 関数によって初期化され、引数の zval タイプが IS_ARRAY に設定されます:

Z_TYPE_P(arg) = IS_ARRAY;

ログイン後にコピー

( 2) zend_hash_init は前のセクションで紹介されているため、ここでは繰り返しません

2. 配列の走査前、次、および現在の

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

ログイン後にコピー

其中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常量有：

<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

ログイン後にコピー

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

ログイン後にコピー

其中:

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 < 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：

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

ログイン後にコピー

排序过程如下所示：

排序之后，调整指针走向之后的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);

ログイン後にコピー

这实际上是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>

ログイン後にコピー

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

ログイン後にコピー

结果是：

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

ログイン後にコピー

那么，对于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)<span style="color: #008000;">;</span>

ログイン後にコピー

注意传入的参数,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 < 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语言/操作系统的相关基础，尤其是指针/内存管理这一块，有一起的同学，欢迎交流。

三、参考文献

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/