欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

PHP 源代碼分析 Zend HashTable詳解第3/3頁

 更新時(shí)間：2009年08月10日 10:51:09   作者：  
在PHP的Zend引擎中，有一個(gè)數(shù)據(jù)結(jié)構(gòu)非常重要，它無處不在，是PHP數(shù)據(jù)存儲(chǔ)的核心，各種常量、變量、函數(shù)、類、對象等都用它來組織，這個(gè)數(shù)據(jù)結(jié)構(gòu)就是HashTable。

因?yàn)檫@個(gè)函數(shù)是使用字符串作為鍵名來插入數(shù)據(jù)的，因此它首先檢查nKeyLength的值是否大于0，如果不是的話就直接退出。然后計(jì)算arKey對應(yīng)的hash值h，將其與nTableMask按位與后得到一個(gè)無符號整數(shù)nIndex。這個(gè)nIndex就是將要插入的Bucket在arBuckets數(shù)組中的索引位置。
現(xiàn)在已經(jīng)有了arBuckets數(shù)組的一個(gè)索引，我們知道它包括的數(shù)據(jù)是一個(gè)指向Bucket的雙向鏈表的指針。如果這個(gè)雙向鏈表不為空的話我們首先檢查這個(gè)雙向鏈表中是否已經(jīng)包含了用字符串a(chǎn)rKey指定的鍵名的Bucket，這樣的Bucket如果存在，并且我們要做的操作是插入新Bucket(通過flag標(biāo)識)，這時(shí)就應(yīng)該報(bào)錯(cuò) – 因?yàn)樵贖ashTable中鍵名不可以重復(fù)。如果存在，并且是修改操作，則使用在HashTable中指定了析構(gòu)函數(shù)pDestructor對原來的pData指向的數(shù)據(jù)進(jìn)行析構(gòu)操作；然后將用新的數(shù)據(jù)替換原來的數(shù)據(jù)即可成功返回修改操作。
如果在HashTable中沒有找到鍵名指定的數(shù)據(jù)，就將該數(shù)據(jù)封裝到Bucket中，然后插入HashTable。這里要注意的是如下的兩個(gè)宏：
CONNECT_TO_BUCKET_DLLIST(p, ht->arBuckets[nIndex])
CONNECT_TO_GLOBAL_DLLIST(p, ht)
前者是將該Bucket插入到指定索引的Bucket雙向鏈表中，后者是插入到整個(gè)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標(biāo)志指明當(dāng)前操作是HASH_NEXT_INSERT(不指定索引插入或修改), HASH_ADD(指定索引插入)還是HASH_UPDATE(指定索引修改)。由于這些操作的實(shí)現(xiàn)代碼基本相同，因此統(tǒng)一合并成了一個(gè)函數(shù)，再用flag加以區(qū)分。
本函數(shù)基本與前一個(gè)相同，不同的是如果確定插入到arBuckets數(shù)組中的索引的方法。如果操作是HASH_NEXT_INSERT，則直接使用nNextFreeElement作為插入的索引。注意nNextFreeElement的值是如何使用和更新的。
3 訪問元素
同樣，HashTable用兩種方式來訪問元素，一種是使用字符串a(chǎn)rKey的zend_hash_find()；另一種是使用索引的訪問方式zend_hash_index_find()。由于其實(shí)現(xiàn)的代碼很簡單，分析工作就留給讀者自已完成。
4 刪除元素
HashTable刪除數(shù)據(jù)均使用zend_hash_del_key_or_index()函數(shù)來完成，其代碼也較為簡單，這里也不再詳細(xì)分析。需要的是注意如何根據(jù)arKey或h來計(jì)算出相應(yīng)的下標(biāo)，以及兩個(gè)雙向鏈表的指針的處理。
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);
}

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

相關(guān)文章

最新評論