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\n");
#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\n");
                    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;
}
           

（持續更新中……）