HashTable是Zend引擎中最重要、使用最廣泛的數(shù)據(jù)結(jié)構(gòu)，它被用來存儲(chǔ)幾乎所有的東西。
1.2.1 數(shù)據(jù)結(jié)構(gòu)
HashTable數(shù)據(jù)結(jié)構(gòu)定義如下：

總的來說，Zend的HashTable是一種鏈表散列，同時(shí)也為線性遍歷進(jìn)行了優(yōu)化，圖示如下：

HashTable中包含兩種數(shù)據(jù)結(jié)構(gòu)，一個(gè)鏈表散列和一個(gè)雙向鏈表，前者用于進(jìn)行快速鍵-值查詢，后者方便線性遍歷和排序，一個(gè)Bucket同時(shí)存在于這兩個(gè)數(shù)據(jù)結(jié)構(gòu)中。
關(guān)于該數(shù)據(jù)結(jié)構(gòu)的幾點(diǎn)解釋：
鏈表散列中為什么使用雙向鏈表？
一般的鏈表散列只需要按key進(jìn)行操作，只需要單鏈表就夠了。但是，Zend有時(shí)需要從鏈表散列中刪除給定的Bucket，使用雙鏈表可以非常高效的實(shí)現(xiàn)。
nTableMask是干什么的？
這個(gè)值用于hash值到arBuckets數(shù)組下標(biāo)的轉(zhuǎn)換。當(dāng)初始化一個(gè)HashTable，Zend首先為arBuckets數(shù)組分配nTableSize大小的內(nèi)存，nTableSize取不小于用戶指定大小的最小的2^n，即二進(jìn)制的10*。nTableMask = nTableSize – 1，即二進(jìn)制的01*，此時(shí)h & nTableMask就恰好落在 [0, nTableSize – 1] 里，Zend就以其為index來訪問arBuckets數(shù)組。
pDataPtr是干什么的？
通常情況下，當(dāng)用戶插入一個(gè)鍵值對(duì)時(shí)，Zend會(huì)將value復(fù)制一份，并將pData指向value副本。復(fù)制操作需要調(diào)用Zend內(nèi)部例程 emalloc來分配內(nèi)存，這是個(gè)非常耗時(shí)的操作，并且會(huì)消耗比value大的一塊內(nèi)存（多出的內(nèi)存用于存放cookie），如果value很小的話，將會(huì)造成較大的浪費(fèi)?？紤]到HashTable多用于存放指針值，于是Zend引入pDataPtr，當(dāng)value小到和指針一樣長(zhǎng)時(shí)，Zend就直接將其復(fù)制到pDataPtr里，并且將pData指向pDataPtr。這就避免了emalloc操作，同時(shí)也有利于提高Cache命中率。
arKey大小為什么只有1？為什么不使用指針管理key？
arKey是存放key的數(shù)組，但其大小卻只有1，并不足以放下key。在HashTable的初始化函數(shù)里可以找到如下代碼：

可見，Zend為一個(gè)Bucket分配了一塊足夠放下自己和key的內(nèi)存，上半部分是Bucket，下半部分是key，而arKey“恰好”是Bucket的最后一個(gè)元素，于是就可以使用arKey來訪問key了。這種手法在內(nèi)存管理例程中最為常見，當(dāng)分配內(nèi)存時(shí)，實(shí)際上是分配了比指定大小要大的內(nèi)存，多出的上半部分通常被稱為cookie，它存儲(chǔ)了這塊內(nèi)存的信息，比如塊大小、上一塊指針、下一塊指針等，baidu的Transmit程序就使用了這種方法。
不用指針管理key，是為了減少一次emalloc操作，同時(shí)也可以提高Cache命中率。另一個(gè)必需的理由是，key絕大部分情況下是固定不變的，不會(huì)因?yàn)閗ey變長(zhǎng)了而導(dǎo)致重新分配整個(gè)Bucket。這同時(shí)也解釋了為什么不把value也一起作為數(shù)組分配了——因?yàn)関alue是可變的。

1.2.2 PHP數(shù)組
關(guān)于HashTable還有一個(gè)疑問沒有回答，就是nNextFreeElement是干什么的？
不同于一般的散列，Zend的HashTable允許用戶直接指定hash值，而忽略key，甚至可以不指定key（此時(shí)，nKeyLength為0）。同時(shí)，HashTable也支持append操作，用戶連hash值也不用指定，只需要提供value，此時(shí)，Zend就用nNextFreeElement作為hash，之后將nNextFreeElement遞增。
HashTable的這種行為看起來很奇怪，因?yàn)檫@將無法按key訪問value，已經(jīng)完全不是個(gè)散列了。理解問題的關(guān)鍵在于，PHP數(shù)組就是使用HashTable實(shí)現(xiàn)的——關(guān)聯(lián)數(shù)組使用正常的k-v映射將元素加入HashTable，其key為用戶指定的字符串；非關(guān)聯(lián)數(shù)組則直接使用數(shù)組下標(biāo)作為hash值，不存在key；而當(dāng)在一個(gè)數(shù)組中混合使用關(guān)聯(lián)和非關(guān)聯(lián)時(shí)，或者使用array_push操作時(shí)，就需要用nNextFreeElement了。
再來看value，PHP數(shù)組的value直接使用了zval這個(gè)通用結(jié)構(gòu)，pData指向的是zval*，按照上一節(jié)的介紹，這個(gè)zval*將直接存儲(chǔ)在pDataPtr里。由于直接使用了zval，數(shù)組的元素可以是任意PHP類型。
數(shù)組的遍歷操作，即foreach、each等，是通過HashTable的雙向鏈表來進(jìn)行的，pInternalPointer作為游標(biāo)記錄了當(dāng)前位置。

1.2.3 變量符號(hào)表
除了數(shù)組，HashTable還被用來存儲(chǔ)許多其他數(shù)據(jù)，比如，PHP函數(shù)、變量符號(hào)、加載的模塊、類成員等。
一個(gè)變量符號(hào)表就相當(dāng)于一個(gè)關(guān)聯(lián)數(shù)組，其key是變量名（可見，使用很長(zhǎng)的變量名并不是個(gè)好主意），value是zval*。
在任一時(shí)刻PHP代碼都可以看見兩個(gè)變量符號(hào)表——symbol_table和active_symbol_table——前者用于存儲(chǔ)全局變量，稱為全局符號(hào)表；后者是個(gè)指針，指向當(dāng)前活動(dòng)的變量符號(hào)表，通常情況下就是全局符號(hào)表。但是，當(dāng)每次進(jìn)入一個(gè)PHP函數(shù)時(shí)（此處指的是用戶使用PHP代碼創(chuàng)建的函數(shù)），Zend都會(huì)創(chuàng)建函數(shù)局部的變量符號(hào)表，并將active_symbol_table指向局部符號(hào)表。Zend總是使用active_symbol_table來訪問變量，這樣就實(shí)現(xiàn)了局部變量的作用域控制。
但如果在函數(shù)局部訪問標(biāo)記為global的變量，Zend會(huì)進(jìn)行特殊處理——在active_symbol_table中創(chuàng)建symbol_table中同名變量的引用，如果symbol_table中沒有同名變量則會(huì)先創(chuàng)建。

1.3 內(nèi)存和文件
程序擁有的資源一般包括內(nèi)存和文件，對(duì)于通常的程序，這些資源是面向進(jìn)程的，當(dāng)進(jìn)程結(jié)束后，操作系統(tǒng)或C庫會(huì)自動(dòng)回收那些我們沒有顯式釋放的資源。
但是，PHP程序有其特殊性，它是基于頁面的，一個(gè)頁面運(yùn)行時(shí)同樣也會(huì)申請(qǐng)內(nèi)存或文件這樣的資源，然而當(dāng)頁面運(yùn)行結(jié)束后，操作系統(tǒng)或C庫也許不會(huì)知道需要進(jìn)行資源回收。比如，我們將php作為模塊編譯到apache里，并且以prefork或worker模式運(yùn)行apache。這種情況下apache進(jìn)程或線程是復(fù)用的，php頁面分配的內(nèi)存將永駐內(nèi)存直到出core。
為了解決這種問題，Zend提供了一套內(nèi)存分配API，它們的作用和C中相應(yīng)函數(shù)一樣，不同的是這些函數(shù)從Zend自己的內(nèi)存池中分配內(nèi)存，并且它們可以實(shí)現(xiàn)基于頁面的自動(dòng)回收。在我們的模塊中，為頁面分配的內(nèi)存應(yīng)該使用這些API，而不是C例程，否則Zend會(huì)在頁面結(jié)束時(shí)嘗試efree掉我們的內(nèi)存，其結(jié)果通常就是crush。
emalloc()
efree()
estrdup()
estrndup()
ecalloc()
erealloc()
另外，Zend還提供了一組形如VCWD_xxx的宏用于替代C庫和操作系統(tǒng)相應(yīng)的文件API，這些宏能夠支持PHP的虛擬工作目錄，在模塊代碼中應(yīng)該總是使用它們。宏的具體定義參見PHP源代碼”TSRM/tsrm_virtual_cwd.h”?？赡苣銜?huì)注意到，所有那些宏中并沒有提供close操作，這是因?yàn)閏lose的對(duì)象是已打開的資源，不涉及到文件路徑，因此可以直接使用C或操作系統(tǒng)例程；同理，read/write之類的操作也是直接使用C或操作系統(tǒng)的例程。

最新評(píng)論