一边学习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;
}
(持续更新中……)