关于PHP源代码中Zend HashTable的解析

typedef struct bucket {
ulong h;       /* Used for numeric indexing */
uint nKeyLength;     /* key 长度 */
void *pData;      /* 指向Bucket中保存的数据的指针 */
void *pDataPtr;     /* 指针数据 */
struct bucket *pListNext;   /* 指向HashTable桶列中下一个元素 */
struct bucket *pListLast;    /* 指向HashTable桶列中前一个元素 */
struct bucket *pNext;    /* 指向具有同一个hash值的桶列的后一个元素 */
struct bucket *pLast;    /* 指向具有同一个hash值的桶列的前一个元素 */
char arKey[1];      /* 必须是最后一个成员，key名称*/
} 
Bucket;

typedef struct _hashtable {
uint nTableSize;
uint nTableMask;
uint nNumOfElements;
ulong nNextFreeElement;
Bucket *pInternalPointer;
Bucket *pListHead;Bucket *pListTail;
Bucket **arBuckets;
dtor_func_t pDestructor;zend_bool persistent;
unsigned char nApplyCount;zend_bool bApplyProtection; 
#if ZEND_DEBUGint inconsistent;
#endif
} HashTable;

typedef struct _zend_hash_key {
char *arKey;      /* hash元素key名称 */
uint nKeyLength;     /* hash 元素key长度 */
ulong h;       /* key计算出的hash值或直接指定的数值下标 */
} 
zend_hash_key;

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); 
if (nSize >= 0×80000000) {
/* prevent overflow */
ht->
nTableSize = 0×80000000;
} else {
while ((1U << i) < nSize) { /* 自动调整nTableSize至2的n次方 */ i++; } ht->nTableSize = 1 << i;/* i的最小值为3，因此HashTable大小最小为8 */ } 
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; 
/* 根据persistent使用不同方式分配arBuckets内存，并将其所有指针初始化为NULL*/
/* 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;
}

ZEND_API int _zend_hash_add_or_update(HashTable *ht, 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函数计算arKey的hash值 */ 
h = zend_inline_hash_func(arKey, nKeyLength); 
/* 将hash值和nTableMask按位与后生成该元素在arBuckets中的索引。让它和 * nTableMask按位与是保证不会产生一个使得arBuckets越界的数组下标。 */ nIndex = h & ht->nTableMask; 
p = ht->arBuckets[nIndex];   
/* 取得相应索引对应的Bucket的指针 */ 
/* 检查对应的桶列中是否包含有数据元素(key, hash) */
while (p != NULL) {
if ((p->h == h) && (p->nKeyLength == nKeyLength)) {
if (!memcmp(p->arKey, arKey, nKeyLength)) {
if (flag & HASH_ADD) {
return FAILURE; // 对应的数据元素已存在，不能进行插入操作}
HANDLE_BLOCK_INTERRUPTIONS();
#if ZEND_DEBUGif (p->pData == pData) {
ZEND_PUTS(”Fatal error in zend_hash_update: p->pData == pData\n”);
HANDLE_UNBLOCK_INTERRUPTIONS();
return FAILURE;}
#endifif (ht->pDestructor) {
/* 如果数据元素存在，对原来的数据进行析构操作 */
ht->pDestructor(p->pData);}
/* 用新的数据来更新原来的数据 */
UPDATE_DATA(ht, p, pData, nDataSize);
if (pDest) {*pDest = p->pData;}HANDLE_UNBLOCK_INTERRUPTIONS();return SUCCESS;}}p = p->pNext;} /* HashTable中没有key对应的数据，新增一个Bucket　*/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;//　将Bucket加入到相应的桶列中CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]);if (pDest) {*pDest = p->pData;} 
HANDLE_BLOCK_INTERRUPTIONS();//　将Bucket 加入到HashTable的双向链表中CONNECT_TO_GLOBAL_DLLIST(p, ht);ht->arBuckets[nIndex] = p;HANDLE_UNBLOCK_INTERRUPTIONS(); 
ht->nNumOfElements++;// 如果HashTable已满，重新调整HashTable的大小。ZEND_HASH_IF_FULL_DO_RESIZE(ht);   /* If the Hash table is full, resize it */return SUCCESS;}

ZEND_API int _zend_hash_index_update_or_next_insert(HashTable *ht, ulong h, void *pData, uint nDataSize, void **pDest, int flag ZEND_FILE_LINE_DC){uint nIndex;Bucket *p; 
IS_CONSISTENT(ht); if (flag & HASH_NEXT_INSERT) {h = ht->nNextFreeElement;}nIndex = h & ht->nTableMask; 
p = ht->arBuckets[nIndex]; // 检查是否含有相应的数据while (p != NULL) {if ((p->nKeyLength == 0) && (p->h == h)) {if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) {return FAILURE;}////　…… 修改Bucket数据，略//if ((long)h >= (long)ht->nNextFreeElement) {ht->nNextFreeElement = h + 1;}if (pDest) {*pDest = p->pData;}return SUCCESS;}p = p->pNext;}p = (Bucket *) pemalloc_rel(sizeof(Bucket) - 1, ht->persistent);if (!p) {return FAILURE;}p->nKeyLength = 0; /* Numeric indices are marked by making the nKeyLength == 0 */p->h = h;INIT_DATA(ht, p, pData, nDataSize);if (pDest) {*pDest = p->pData;} 
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex]); 
HANDLE_BLOCK_INTERRUPTIONS();ht->arBuckets[nIndex] = p;CONNECT_TO_GLOBAL_DLLIST(p, ht);HANDLE_UNBLOCK_INTERRUPTIONS(); if ((long)h >= (long)ht->nNextFreeElement) {ht->nNextFreeElement = h + 1;}ht->nNumOfElements++;ZEND_HASH_IF_FULL_DO_RESIZE(ht);return SUCCESS;}

/* This is used to recurse elements and selectively delete certain entries
* from a hashtable. apply_func() receives the data and decides if the entry
* should be deleted or recursion should be stopped. The following three
* return codes are possible:
* ZEND_HASH_APPLY_KEEP   - continue
* ZEND_HASH_APPLY_STOP   - stop iteration
* ZEND_HASH_APPLY_REMOVE - delete the element, combineable with the former
*/ 
ZEND_API void zend_hash_apply(HashTable *ht, apply_func_t apply_func TSRMLS_DC){Bucket *p; 
IS_CONSISTENT(ht); 
HASH_PROTECT_RECURSION(ht);p = ht->pListHead;while (p != NULL) {int result = apply_func(p->pData TSRMLS_CC); if (result & ZEND_HASH_APPLY_REMOVE) {p = zend_hash_apply_deleter(ht, p);} else {p = p->pListNext;}if (result & ZEND_HASH_APPLY_STOP) {break;}}HASH_UNPROTECT_RECURSION(ht);}

typedef int (*apply_func_arg_t)(void *pDest,void *argument TSRMLS_DC);void zend_hash_apply_with_argument(HashTable *ht,apply_func_arg_t apply_func, void *data TSRMLS_DC); typedef int (*apply_func_args_t)(void *pDest,int num_args, va_list args, zend_hash_key *hash_key);void zend_hash_apply_with_arguments(HashTable *ht,apply_func_args_t apply_func, int numargs, …);