Array-Implementierung: PHP5 VS PHP7

// PHP 5 中 hashtable 的数据结构定义
typedef struct bucket {
    ulong h;  /*对于索引数组，存储 key 的原始值；对于关联数组，存储 key 的 hash 之后的值*/
    uint nKeyLength; /*关联数组时存储 key 的长度，索引数组此值为 0*/
    void *pData; /*指向数组 value 的地址*/
    void *pDataPtr; /*如果 value 为指针，则由 pDataPtr 记录 vlaue，pData 则指向 pDataPtr*/
    // PHP 5 中数组元素的顺序是固定的，无论什么时候遍历，数组元素总是与插入时的顺序一致
    // PHP 5 中使用双向链表来保证数组元素的顺序，pListNext 和 pListLast 分别按照
    // 元素插入顺序记录当前 bucket 的下一个和上一个 bucket
    struct bucket *pListNext;
    struct bucket *pListLast;
    // PHP 5 使用拉链法解决 hash 碰撞，pNext 和 pLast 分别存储当前 bucket
    // 在冲突的双向链表中的下一个和上一个相邻的 bucket
    struct bucket *pNext;
    struct bucket *pLast;
    const char *arKey; /*关联数组是存储 key 的原始值*/
} Bucket;

typedef struct _hashtable {
    uint nTableSize; /*当前 ht 所分配的 bucket 的总数，2^n*/
    uint nTableMask; /*nTableSize - 1，用于计算索引*/
    uint nNumOfElements; /*实际存储的元素的数量*/
    ulong nNextFreeElement; /*下一个可以被使用的整数 key*/
    Bucket *pInternalPointer; /*数组遍历时，记录当前 bucket 的地址*/
    Bucket *pListHead;
    Bucket *pListTail;
    Bucket **arBuckets; /*记录 bucket 的 C 语言数组*/
    dtor_func_t pDestructor; /*删除数组元素时内部调用的函数*/
    zend_bool persistent; /*标识 ht 是否永久有效*/
    unsigned char nApplyCount; /*ht 允许的最大递归深度*/
    zend_bool bApplyProtection; /*是否启用递归保护*/
#if ZEND_DEBUG
    int inconsistent;
#endif
} HashTable;

// PHP 7 中 hashtable 的数据结构
// PHP 7 中个子版本以及阶段版本中对 hashtable 的数据结构的定义会有微小的差别，这里使用的是 PHP 7.4.0 中的定义 
struct _zend_string { 
    zend_refcounted_h gc;
    zend_ulong        h;  /*字符串 key 的 hash 值*/
    size_t            len;  /*字符串 key 的长度*/
    char              val[1]; /*存储字符串的值，利用了 struct hack*/
};

typedef struct _Bucket {
    zval              val;  /*内嵌 zval 结构，存储数组的 value 值*/
    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; /*作用与 PHP 5 中 hashtable 中 nTableMask 作用相同，但实现逻辑稍有变化*/
    Bucket           *arData; /*存储 bucket 相关的信息*/
    uint32_t          nNumUsed; /*ht 中已经使用的 bucket 的数量，在 nNumOfElements 的基础上加上删除的 key*/
    uint32_t          nNumOfElements;
    uint32_t          nTableSize;
    uint32_t          nInternalPointer;
    zend_long         nNextFreeElement;
    dtor_func_t       pDestructor;
};

// nTableMask 为 -2 倍的 nTableSize 的无符号表示
#define HT_SIZE_TO_MASK(nTableSize) \
    ((uint32_t)(-((nTableSize) + (nTableSize))))

// 在通过 idx 查找 Bucket 时，data 默认为 Bucket 类型，加 idx 表示向右偏移 idx 个 Bucket 位置
# define HT_HASH_TO_BUCKET_EX(data, idx) \
    ((data) + (idx))

// 在通过 nIndex 查找 idx 时，
// (uint32_t*)(data) 首先将 data 转换成了 uint32_t* 类型的数组
// 然后将 nIndex 转换成有符号数（负数），然后以数组的方式查找 idx 的值
#define HT_HASH_EX(data, idx) \
    ((uint32_t*)(data))[(int32_t)(idx)]

nIndex = h | ht->nTableMask;
idx = HT_HASH_EX(arData, nIndex);
p = HT_HASH_TO_BUCKET_EX(arData, idx);

// hash 碰撞双向链表的维护
#define CONNECT_TO_BUCKET_DLLIST(element, list_head)        \
    (element)->pNext = (list_head);                         \
    (element)->pLast = NULL;                                \
    if ((element)->pNext) {                                 \
        (element)->pNext->pLast = (element);                \
    }

#define CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, last, next)\
    (element)->pListLast = (last);                          \
    (element)->pListNext = (next);                          \
    if ((last) != NULL) {                                   \
        (last)->pListNext = (element);                      \
    } else {                                                \
        (ht)->pListHead = (element);                        \
    }                                                       \
    if ((next) != NULL) {                                   \
        (next)->pListLast = (element);                      \
    } else {                                                \
        (ht)->pListTail = (element);                        \
    }                                                       \
// 数组元素插入顺序双向链表的维护
#define CONNECT_TO_GLOBAL_DLLIST(element, ht)                                   \
    CONNECT_TO_GLOBAL_DLLIST_EX(element, ht, (ht)->pListTail, (Bucket *) NULL); \
    if ((ht)->pInternalPointer == NULL) {                                       \
        (ht)->pInternalPointer = (element);                                     \
    }
// 数组元素的更新
#define UPDATE_DATA(ht, p, pData, nDataSize)                                            \
    if (nDataSize == sizeof(void*)) {                                                   \
        // 值为指针类型的元素的更新                                                         \
        if ((p)->pData != &(p)->pDataPtr) {                                             \
            pefree_rel((p)->pData, (ht)->persistent);                                   \
        }                                                                               \
        // pDataPtr 存储元素值的地址，pData 存储 pDataPtr 的地址                             \
        memcpy(&(p)->pDataPtr, pData, sizeof(void *));                                  \
        (p)->pData = &(p)->pDataPtr;                                                    \
    } else {                                                                            \
        // 如果数组元素为值类型，则存入 pData，此时 pDataPtr 为 Null                          \
        if ((p)->pData == &(p)->pDataPtr) {                                             \
            (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);            \
            (p)->pDataPtr=NULL;                                                         \
        } else {                                                                        \
            (p)->pData = (void *) perealloc_rel((p)->pData, nDataSize, (ht)->persistent);   \
            /* (p)->pDataPtr is already NULL so no need to initialize it */             \
        }                                                                               \
        memcpy((p)->pData, pData, nDataSize);                                           \
    }
// 数组元素的初始化
#define INIT_DATA(ht, p, _pData, nDataSize);                                \
    if (nDataSize == sizeof(void*)) {                                   \
        // 指针类型元素的初始化                                            \
        memcpy(&(p)->pDataPtr, (_pData), sizeof(void *));                   \
        (p)->pData = &(p)->pDataPtr;                                    \
    } else {                                                            \
        // 值类型元素的初始化                                                \
        (p)->pData = (void *) pemalloc_rel(nDataSize, (ht)->persistent);\
        memcpy((p)->pData, (_pData), nDataSize);                            \
        (p)->pDataPtr=NULL;                                             \
    }
// hashtable 初始化校验，如果没有初始化，则初始化 hashtable
#define CHECK_INIT(ht) do {                                             \
    if (UNEXPECTED((ht)->nTableMask == 0)) {                                \
        (ht)->arBuckets = (Bucket **) pecalloc((ht)->nTableSize, sizeof(Bucket *), (ht)->persistent);   \
        (ht)->nTableMask = (ht)->nTableSize - 1;                        \
    }                                                                   \
} while (0)
// 数组元素的新增或更新（精简掉了一些宏调用和代码片段)
ZEND_API int _zend_hash_add_or_update(HashTable *ht, const char *arKey, uint nKeyLength, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC)
{
    ulong h;
    uint nIndex;
    Bucket *p;

    CHECK_INIT(ht);
    
    h = zend_inline_hash_func(arKey, nKeyLength);
    nIndex = h & ht->nTableMask;

    p = ht->arBuckets[nIndex];
    while (p != NULL) {
        if (p->arKey == arKey ||
            ((p->h == h) && (p->nKeyLength == nKeyLength) && !memcmp(p->arKey, arKey, nKeyLength))) {
                // 数组元素更新逻辑
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                ZEND_ASSERT(p->pData != pData);
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                UPDATE_DATA(ht, p, pData, nDataSize);
                if (pDest) {
                    *pDest = p->pData;
                }
                return SUCCESS;
        }
        p = p->pNext;
    }    
    // 数组元素新增逻辑
    if (IS_INTERNED(arKey)) {
        p = (Bucket *) pemalloc(sizeof(Bucket), ht->persistent);
        p->arKey = arKey;
    } else {
        p = (Bucket *) pemalloc(sizeof(Bucket) + nKeyLength, ht->persistent);
        p->arKey = (const char*)(p + 1);
        memcpy((char*)p->arKey, arKey, nKeyLength);
    }    
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h; 
    // hash 碰撞链表维护
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
    if (pDest) {
        *pDest = p->pData;
    }
    // 数组元素写入顺序维护
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    ht->arBuckets[nIndex] = p;

    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
    return SUCCESS;
}

#define Z_NEXT(zval)                (zval).u2.next
#define HT_HASH_EX(data, idx) \
    ((uint32_t*)(data))[(int32_t)(idx)]
# define HT_IDX_TO_HASH(idx) \
    ((idx) * sizeof(Bucket))

// PHP 7 中数组添加/修改元素（精简了部分代码）
static zend_always_inline zval *_zend_hash_add_or_update_i(HashTable *ht, zend_string *key, zval *pData, uint32_t flag)
{
	zend_ulong h;
	uint32_t nIndex;
	uint32_t idx;
	Bucket *p, *arData;

	/*... ...*/

	ZEND_HASH_IF_FULL_DO_RESIZE(ht);		/* If the Hash table is full, resize it */

add_to_hash:
	idx = ht->nNumUsed++;
	ht->nNumOfElements++;
	arData = ht->arData;
	p = arData + idx;
	p->key = key;
	p->h = h = ZSTR_H(key);
	nIndex = h | ht->nTableMask;
	Z_NEXT(p->val) = HT_HASH_EX(arData, nIndex);
	HT_HASH_EX(arData, nIndex) = HT_IDX_TO_HASH(idx);
	ZVAL_COPY_VALUE(&p->val, pData);

	return &p->val;
}