php源码学习笔记(三)
0 / 1 / 创建于 1年前 /
徵羽宫 的个人博客
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 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号
推荐文章：