Zend引擎中对HashTable的各种操作

一边学习C，一边研究Zend引擎，边学习边总结。

HashTable的初始化：

ZEND_API int _zend_hash_init(HashTable *ht, uint nSize, hash_func_t pHashFunction, dtor_func_t pDestructor, zend_bool persistent ZEND_FILE_LINE_DC)
{
    uint i = 3;
    Bucket **tmp;


    SET_INCONSISTENT(HT_OK);


    // HashTable 长度最长为 0x80000000
    if (nSize >= 0x80000000) {
        /* prevent overflow */
        ht->nTableSize = 0x80000000;
    } else {
        // 为了 TableMask 起作用，所以 TableSize 必须为 2的幂次方
        // 找到适合条件的最小的幂
        while ((1U << i) < nSize) {
            i++;
        }
        ht->nTableSize = 1 << i;
    }


    // TableMask 为最高位为0，其他位均为1的数
    // Bucket 在 HashTable 中的位置，通过 Hash 值与 TableMask 来决定
    ht->nTableMask = ht->nTableSize - 1;
    // 存储指向解构函数的指针
    ht->pDestructor = pDestructor;
    ht->arBuckets = NULL;
    ht->pListHead = NULL;
    ht->pListTail = NULL;
    ht->nNumOfElements = 0;
    ht->nNextFreeElement = 0;
    ht->pInternalPointer = NULL;
    ht->persistent = persistent;
    ht->nApplyCount = 0;
    ht->bApplyProtection = 1;


    /* Uses ecalloc() so that Bucket* == NULL */
    if (persistent) {
        tmp = (Bucket **) calloc(ht->nTableSize, sizeof(Bucket *));
        if (!tmp) {
            return FAILURE;


        }
        ht->arBuckets = tmp;
    } else {
        tmp = (Bucket **) ecalloc_rel(ht->nTableSize, sizeof(Bucket *));
        if (tmp) {
            ht->arBuckets = tmp;
        }
    }


    return SUCCESS;
}

向HashTable中增加或更新元素：

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;


    IS_CONSISTENT(ht);


    if (nKeyLength <= 0) {
#if ZEND_DEBUG
        ZEND_PUTS("zend_hash_update: Can"t put in empty key
");
#endif
        return FAILURE;
    }


    // 根据键的名称和长度求出Hash值
    h = zend_inline_hash_func(arKey, nKeyLength);
    // 将Hash值与HashTable的Mask相与，得出该键值在HashTable中的存储位置为 nIndex
    nIndex = h & ht->nTableMask;


    // 将二维数组arBucket第一维下标为 nIndex 的 Bucket 数组赋值给 p
    p = ht->arBuckets[nIndex];


    // 循环这个数组，直到最后一个元素，循环结束后p处于 Bucket 数组的最后一个位置
    while (p != NULL) {
        // 如果存在和本键值Hash值一样并且键长度一样的元素，就判断是否存在重复的元素
        if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
            // 键值和要存储的键值完全一样
            if (!memcmp(p->arKey, arKey, nKeyLength)) {
                // 如果是新增的元素，就返回错误
                if (flag & HASH_ADD) {
                    return FAILURE;
                }
                HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUG
                if (p->pData == pData) {
                    ZEND_PUTS("Fatal error in zend_hash_update: p->pData == pData
");
                    HANDLE_UNBLOCK_INTERRUPTIONS();
                    return FAILURE;
                }


#endif
                // 程序没有在前面 return ，说明是更新已有元素
                // 将当前存储的数据解构
                if (ht->pDestructor) {
                    ht->pDestructor(p->pData);
                }
                // 更新数据
                UPDATE_DATA(ht, p, pData, nDataSize);
                // 如果需要返回更新后的数据，返回给pDest变量
                if (pDest) {
                    *pDest = p->pData;
                }
                HANDLE_UNBLOCK_INTERRUPTIONS();
                // 如果更新成功，返回
                return SUCCESS;
            }
        }
        // 移向 Bucket 数组的下一个元素
        p = p->pNext;
    }


    // 如果是新增，并且没有重复的元素，继续往下执行
    // 因为Bucket数组的最后一个元素是数组，所以可以实现可变长的存储
    // 由于 struct Bucket 在定义的时候 arKey 长度为1，所以先-1，然后再分配nKeyLength的长度
    p = (Bucket *) pemalloc(sizeof(Bucket) - 1 + nKeyLength, ht->persistent);
    if (!p) {
        return FAILURE;
    }
    // 赋值
    memcpy(p->arKey, arKey, nKeyLength);
    p->nKeyLength = nKeyLength;
    INIT_DATA(ht, p, pData, nDataSize);
    p->h = h;
    CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);
    if (pDest) {
        *pDest = p->pData;
    }




    HANDLE_BLOCK_INTERRUPTIONS();
    CONNECT_TO_GLOBAL_DLLIST(p, ht);
    ht->arBuckets[nIndex] = p;
    HANDLE_UNBLOCK_INTERRUPTIONS();


    // HashTable 存储的元素加1
    ht->nNumOfElements++;
    ZEND_HASH_IF_FULL_DO_RESIZE(ht);        /* If the Hash table is full, resize it */
    return SUCCESS;
}

（持续更新中……）