快捷導(dǎo)航

PHP 源代碼分析 Zend HashTable詳解

更新時間：2009年08月10日 10:51:09 作者：

在PHP的Zend引擎中，有一個數(shù)據(jù)結(jié)構(gòu)非常重要，它無處不在，是PHP數(shù)據(jù)存儲的核心，各種常量、變量、函數(shù)、類、對象等都用它來組織，這個數(shù)據(jù)結(jié)構(gòu)就是HashTable。

因為這個函數(shù)是使用字符串作為鍵名來插入數(shù)據(jù)的，因此它首先檢查nKeyLength的值是否大于0，如果不是的話就直接退出。然后計算arKey對應(yīng)的hash值h，將其與nTableMask按位與后得到一個無符號整數(shù)nIndex。這個nIndex就是將要插入的Bucket在arBuckets數(shù)組中的索引位置。
現(xiàn)在已經(jīng)有了arBuckets數(shù)組的一個索引，我們知道它包括的數(shù)據(jù)是一個指向Bucket的雙向鏈表的指針。如果這個雙向鏈表不為空的話我們首先檢查這個雙向鏈表中是否已經(jīng)包含了用字符串a(chǎn)rKey指定的鍵名的Bucket，這樣的Bucket如果存在，并且我們要做的操作是插入新Bucket(通過flag標識)，這時就應(yīng)該報錯 – 因為在HashTable中鍵名不可以重復(fù)。如果存在，并且是修改操作，則使用在HashTable中指定了析構(gòu)函數(shù)pDestructor對原來的pData指向的數(shù)據(jù)進行析構(gòu)操作；然后將用新的數(shù)據(jù)替換原來的數(shù)據(jù)即可成功返回修改操作。
如果在HashTable中沒有找到鍵名指定的數(shù)據(jù)，就將該數(shù)據(jù)封裝到Bucket中，然后插入HashTable。這里要注意的是如下的兩個宏：
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)
前者是將該Bucket插入到指定索引的Bucket雙向鏈表中，后者是插入到整個HashTable的Bucket雙向鏈表中。兩者的插入方式也不同，前者是將該Bucket插入到雙向鏈表的最前面，后者是插入到雙向鏈表的最末端。
下面是第二種插入或修改Bucket的方法，即使用索引的方法：

復(fù)制代碼代碼如下:

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]; 
// 檢查是否含有相應(yīng)的數(shù)據(jù) 
while (p != NULL) { 
if ((p->nKeyLength == 0) && (p->h == h)) { 
if (flag & HASH_NEXT_INSERT || flag & HASH_ADD) { 
return FAILURE; 
} 
// 
//　...... 修改Bucket數(shù)據(jù)，略 
// 
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; 
}

flag標志指明當前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)還是HASH_UPDATE(指定索引修改)。由于這些操作的實現(xiàn)代碼基本相同，因此統(tǒng)一合并成了一個函數(shù)，再用flag加以區(qū)分。
本函數(shù)基本與前一個相同，不同的是如果確定插入到arBuckets數(shù)組中的索引的方法。如果操作是HASH_NEXT_INSERT，則直接使用nNextFreeElement作為插入的索引。注意nNextFreeElement的值是如何使用和更新的。
3 訪問元素
同樣，HashTable用兩種方式來訪問元素，一種是使用字符串a(chǎn)rKey的zend_hash_find()；另一種是使用索引的訪問方式zend_hash_index_find()。由于其實現(xiàn)的代碼很簡單，分析工作就留給讀者自已完成。
4 刪除元素
HashTable刪除數(shù)據(jù)均使用zend_hash_del_key_or_index()函數(shù)來完成，其代碼也較為簡單，這里也不再詳細分析。需要的是注意如何根據(jù)arKey或h來計算出相應(yīng)的下標，以及兩個雙向鏈表的指針的處理。
5 遍歷元素

復(fù)制代碼代碼如下:

/* 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); 
}

因為HashTable中所有Bucket都可以通過pListHead指向的雙向鏈表來訪問，因此遍歷HashTable的實現(xiàn)也比較簡單。這里值得一提的是對當前遍歷到的Bucket的處理使用了一個apply_func_t類型的回調(diào)函數(shù)。根據(jù)實際需要，該回調(diào)函數(shù)返回下面值之一：
ZEND_HASH_APPLY_KEEP
ZEND_HASH_APPLY_STOP
ZEND_HASH_APPLY_REMOVE
它們分別表示繼續(xù)遍歷，停止遍歷或刪除相應(yīng)元素后繼續(xù)遍歷。
還有一個要注意的問題就是遍歷時的防止遞歸的問題，也就是防止對同一個HashTable同時進行多次遍歷。這是用下面兩個宏來實現(xiàn)的：
HASH_PROTECT_RECURSION(ht)
HASH_UNPROTECT_RECURSION(ht)
其主要原理是如果遍歷保護標志bApplyProtection為真，則每次進入遍歷函數(shù)時將nApplyCount值加1，退出遍歷函數(shù)時將nApplyCount值減1。開始遍歷之前如果發(fā)現(xiàn)nApplyCount > 3就直接報告錯誤信息并退出遍歷。
上面的apply_func_t不帶參數(shù)。HashTable還提供帶一個參數(shù)或可變參數(shù)的回調(diào)方式，對應(yīng)的遍歷函數(shù)分別為:

復(fù)制代碼代碼如下:

 
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, ...); 

除了上面提供的幾種提供外，還有許多其它操作HashTable的API。如排序、HashTable的拷貝與合并等等。只要充分理解了上述HashTable的數(shù)據(jù)結(jié)構(gòu)，理解這些代碼并不困難。

您可能感興趣的文章: