php 的数组

今天跳过了字符串，也跳过了各种变量声明的 token 和 opcodes 的研究。 因为数组的实现真的特别有意思，研究了一下午加一晚上最后终于才悟了。激动之情溢于言表，熬夜记录一下。

首先 array 的实现是一个 哈希表 ，php 将数组的 key 哈希成一个整型 h， value 存到 bucket 中， h 和 bucket 有一个对应关系。 通过 h 就能找到 bucket。 但是不同的字符串有可能 hash 出来的 h 相同， 也就是说会出现哈希冲突。 哈希冲突也很好解决，就是把冲突的 bucket 存放在一个链表里。查找的时候先通过 h 找到链表 slot, 然后再遍历 slot 通过 key 找到正确的 bucket。

php5 的实现中， arBuckets(php7的arData) 那里是一个 bucket 指针。 bucket 里面有多个字段实现了一个双向链表，并且有局部链表和全局链表之分，一共是四个字段， pNext pLast pListNext pListLast。还有一个指针 pData 指向 data 的地址。

下面是 php8 的源码（php7就已经是这样了）arData 是一个 Bucket 类型的动态数组。 但是 bucket 发生了很大的改变，bucket 只剩下了 zval 类型的 val， 还有 h 和 key。

我看到这里的时候一脸懵逼，因为没有全局链表和局部链表，就没法像之前那样先找 h ， 然后冲突的再找 key 了, 而且 zval 之前也看了里面简单的不能再简单，只有一个next支持链表的操作。原来双向链表的功能它也做不到啊。

然后仔细看书，原来 php7 使用一个数组就实现了之前全局链表和局部链表的操作，然后又因为是动态数组，在内存上是连续的所以可以通过索引快速定位到 bucket，就不需要原来耗时的遍历了。大家先看下面神奇的代码， 想一想怎么实现的。

typedef struct _Bucket {
    zval              val;
    zend_ulong        h;                /* hash value (or numeric index)   */
    zend_string      *key;              /* string key or NULL for numerics */
} Bucket;

typedef struct _zend_array HashTable;

struct _zend_array {
    zend_refcounted_h gc;
    union {
        struct {
            ZEND_ENDIAN_LOHI_4(
                zend_uchar    flags,
                zend_uchar    _unused,
                zend_uchar    nIteratorsCount,
                zend_uchar    _unused2)
        } v;
        uint32_t flags;
    } u;
    uint32_t          nTableMask; // 这个数是一个负数 
    Bucket           *arData; 
    uint32_t          nNumUsed; // bucket数量
    uint32_t          nNumOfElements; // 有效bucket数量
    uint32_t          nTableSize; // table size 
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

php7 在 arData 做了一个很神奇的操作。 正常动态数组，需要分配的大小是 单个数组项的大小乘以成员数量， 比如假设 php7 的 bucket 是 24 字节，那么我要声明一个包含 8 个项的数组应该是 192 个字节大小。现在 php7 的 arData 会占用 192 + 4 * slot 数量个内存大小，比如数字 key 不存在哈希冲突的情况下就是 192 + 4 * 8 个 内存大小。多出来的 32 用来创建索引。通过索引能直接指向到某个 bucket 地址。

书上用下面这个图说明这个内存结构。说实话其实对我产生了误导，这里它把负数索引放到了内存头部，其实 c 负数索引代表数组从后往前数的项。 所以实际上索引数组应该在内存空间的尾部。

它的实现逻辑其实就是通过转换 arData 的指针类型，使得操作数组时单个数组项占用的空间发生了变化。 比如我用 Bucket 类型的指针拿 占用了 192 + 32 内存空间的动态数组，那么 它就是有 （192 + 32）/ 24 个元素的数组。 用 unit_t 类型的指针拿 那么就是 （192 + 32)/4 个元素的数组。 因为内存总的大小是设计好的。 所以两种类型的数组就可以存放在一个动态数组空间里互不影响。负数索引是通过与 nTableMask 按位或实现的。

真的太帅了，大佬们真的太强了。

下面是我研究的时候写的 demo.

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct _Bucket {
    char            val;
    unsigned long   h; 
    char            *key; 
} Bucket;

typedef struct _zend_array HashTable;

struct _zend_array {
    uint32_t          nTableMask;
    Bucket           *arData;
    uint32_t          nTableSize;
};

int main(){
    // 首先创建结构体， 初始化参数
    struct _zend_array arr;
    arr.nTableSize = 8;
    arr.nTableMask = -8;

    // 分配数组空间
    unsigned long size = -1 * arr.nTableMask * sizeof(uint32_t) +  arr.nTableSize * sizeof(Bucket);
    printf("%ld, %ld, %ld \r\n", size, -1 * arr.nTableMask * sizeof(uint32_t), arr.nTableSize * sizeof(Bucket));
    Bucket *dynamicArray = (Bucket *)malloc(size);
    // 
    arr.arData = dynamicArray;

    // 查找第一个索引
    printf("%p\r\n", &((uint32_t *)(arr.arData))[-1]);
    // 查找第一个bucket 
    printf("%p\r\n", &((Bucket *)(arr.arData))[0]);
    free(dynamicArray);
    return 0;
}

224, 32, 192
0x562912b126ac
0x562912b126b0

本作品采用《CC 协议》，转载必须注明作者和本文链接