用于管理文件方法和數(shù)據(jù)結(jié)構(gòu)案例分析

用于將文件截?cái)酁橹付ㄩL(zhǎng)度，超出長(zhǎng)度的內(nèi)容將被刪除，一般情況下，都通過(guò)文件描述符filedes指定要截?cái)嗟奈募?，其函?shù)原型如下：

其中，filedes為文件句柄，length為新的文件長(zhǎng)度，如果length小于原文件長(zhǎng)度，文件將被截?cái)?。返回值為AW_OK時(shí)，表示截?cái)喑晒?，否則，表示截?cái)嗍?。如將fs_test.txt文件長(zhǎng)度截?cái)酁?4，以刪除結(jié)尾的字符串："0123456789"，則范例程序詳見(jiàn)程序清單11.14。

程序清單11.14 截?cái)辔募独绦?/span>

在程序清單11.14中，截?cái)嘁粋€(gè)文件主要分為3步：打開(kāi)文件、截?cái)辔募?、關(guān)閉文件。為了簡(jiǎn)化截?cái)辔募牟僮?，AWorks提供了另外一個(gè)功能相同的接口，但其通過(guò)文件名指定要截?cái)嗟奈募?，使用起?lái)更加便捷，其函數(shù)原型為：

其中，path為文件的路徑，length為新的文件長(zhǎng)度。用戶無(wú)需在截?cái)辔募按蜷_(kāi)文件，該函數(shù)將在內(nèi)部打開(kāi)文件，截?cái)嗪箨P(guān)閉文件。如使用該接口，則一行代碼即可實(shí)現(xiàn)與程序清單11.14相同的功能，即：

8. 修改文件名

該函數(shù)用于修改指定文件的文件名，函數(shù)原型為：

其中，oldpath為原文件名，newpath為新文件名。返回值為AW_OK時(shí)表示更名成功，否則表示更名失敗。修改"/test/fs_test.txt"為"/test/fs_test3.txt"的范例程序詳見(jiàn)程序清單11.15。

程序清單11.15 修改文件名范例程序

注意，若newpath指定的文件已存在，則該文件將會(huì)被覆蓋。特別地，若newpath與oldpath相同，則函數(shù)不做任何處理，直接返回成功。

9. 同步文件

通常情況下，在操作文件的過(guò)程中，文件相關(guān)的數(shù)據(jù)并不會(huì)立即寫入到存儲(chǔ)設(shè)備中，而是保存在內(nèi)存中，這樣可以在一定程度上提高數(shù)據(jù)讀寫的效率。在關(guān)閉文件時(shí)，再將該文件相關(guān)的所有數(shù)據(jù)保存到存儲(chǔ)設(shè)備中。在一些比較耗時(shí)的文件操作過(guò)程中，為了避免中途突然掉電導(dǎo)致數(shù)據(jù)丟失，也可以通過(guò)aw_fsync()函數(shù)立即執(zhí)行回寫操作，使文件相關(guān)的數(shù)據(jù)保存到存儲(chǔ)設(shè)備中。這就類似于在編寫一個(gè)Word文檔的過(guò)程中，需要時(shí)常點(diǎn)擊保存按鈕，避免突然掉電導(dǎo)致部分?jǐn)?shù)據(jù)丟失。其函數(shù)原型為：

其中，filedes為文件句柄。返回值為AW_OK時(shí)表示同步成功，否則，表示同步失敗。范例程序詳見(jiàn)程序清單11.16。

程序清單11.16 同步文件范例程序

10. 刪除文件

當(dāng)一個(gè)文件不再使用，可以刪除該文件，刪除指定文件的函數(shù)原型為：

其中，path為文件的路徑。返回值為AW_OK時(shí)表示刪除成功，否則，表示刪除失敗。范例程序詳見(jiàn)程序清單11.17。

程序清單11.17 刪除文件范例程序

11. 獲取文件狀態(tài)信息

對(duì)于一個(gè)文件，除基本數(shù)據(jù)外（使用讀寫接口操作的數(shù)據(jù)），還具有一些與文件相關(guān)的其它信息，比如：文件實(shí)際大小、文件占用大小、修改時(shí)間、訪問(wèn)權(quán)限等。這些信息統(tǒng)一被稱為狀態(tài)信息，可以通過(guò)aw_fstat()接口獲取文件的狀態(tài)信息，其函數(shù)原型為：

其中，fildes為文件句柄，buf為文件狀態(tài)信息的緩存。返回值為AW_OK時(shí)表示獲取成功，否則，表示獲取失敗。文件狀態(tài)信息的類型為struct aw_stat，其完整定義如下（io/sys/aw_stat.h）：

其中的絕大部分成員在當(dāng)前系統(tǒng)中并未使用，預(yù)留給后續(xù)擴(kuò)展。這里僅簡(jiǎn)要介紹幾個(gè)常用的數(shù)據(jù)成員：st_mode、st_size、st_atim、st_mtim和st_ctim。

st_mode包含了文件類型及權(quán)限相關(guān)的信息，權(quán)限相關(guān)信息與創(chuàng)建文件時(shí)指定的mode參數(shù)一致。

st_size表示文件的實(shí)際長(zhǎng)度。通常情況下，文件占用的磁盤空間會(huì)大于該值。如在FAT文件系統(tǒng)中，存儲(chǔ)文件的基本單元為“簇”，即使文件小于基本的存儲(chǔ)單元大小，也會(huì)占用一個(gè)完整的存儲(chǔ)單元。文件占用的磁盤空間可由st_blksize和st_blocks獲得，st_blksize表示存儲(chǔ)單元的大小，st_blocks表示文件占用的存儲(chǔ)單元個(gè)數(shù)，兩者的乘積則表示文件占用的空間大小。

st_atim、st_mtim、st_ctim表示文件相關(guān)的時(shí)間，st_atim為最后訪問(wèn)文件的時(shí)間，st_mtim為最后修改文件內(nèi)容的時(shí)間，st_ctim為最后修改文件狀態(tài)的時(shí)間。在部分平臺(tái)中，可能沒(méi)有嚴(yán)格細(xì)分這些時(shí)間，而是統(tǒng)一的使用一個(gè)時(shí)間表示，此時(shí)，各個(gè)時(shí)間的值將是相同的。這些時(shí)間的類型為struct timespec，其表示精確日歷時(shí)間，即：

精確日歷時(shí)間中包含了秒和納秒信息?？梢酝ㄟ^(guò)將該時(shí)間轉(zhuǎn)換為細(xì)分時(shí)間，得到年、月、日、時(shí)、分、秒等信息。獲取文件狀態(tài)信息的范例程序詳見(jiàn)程序清單11.18。

程序清單11.18 獲取文件狀態(tài)信息的范例程序

和截?cái)辔募愃?，AWorks也提供了另外一個(gè)功能相同的接口，可以通過(guò)文件名指定要獲取狀態(tài)信息的文件，使用起來(lái)更加便捷，其函數(shù)原型為：

其中，path為文件路徑，buf為文件狀態(tài)信息的緩存。返回AW_OK時(shí)表示獲取成功，否則，表示獲取失敗?？梢允褂迷摻涌诤?jiǎn)化程序清單11.18的第21、22、29共計(jì)3含代碼，使用一行代碼代替，即：

12. 修改文件時(shí)間

一個(gè)文件的存取和修改時(shí)間可以用 aw_utime() 函數(shù)更改，其函數(shù)原型為：

其中，path為文件的路徑，times為設(shè)置的時(shí)間。struct aw_utimbuf類型的定義（io/aw_utime.h）如下：

其中，actime表示文件最近一次的訪問(wèn)時(shí)間，modtime表示文件最近一次的內(nèi)容修改時(shí)間，它們的類型均為time_t，time_t是日歷之間類型，即actime和modtime均使用日歷時(shí)間表示。返回AW_OK時(shí)，表示時(shí)間設(shè)置成功，否則，表示時(shí)間設(shè)置失敗。如設(shè)置文件訪問(wèn)時(shí)間和文件修改時(shí)間均為2016年8月26日09:32:30，則范例程序詳見(jiàn)程序清單11.19。

程序清單11.19 修改文件時(shí)間的范例程序

程序中，首先使用aw_utime()修改了文件時(shí)間，然后使用aw_stat()獲取文件的狀態(tài)信息，以查看時(shí)間是否設(shè)置成功。

11.4 目錄基本操作

目錄相關(guān)的操作主要包括創(chuàng)建目錄、打開(kāi)目錄、讀取目錄、關(guān)閉目錄、刪除目錄等。相關(guān)接口的原型詳見(jiàn)表11.5。

表11.5 目錄基本操作相關(guān)接口

1. 創(chuàng)建目錄

創(chuàng)建一個(gè)空目錄，其函數(shù)原型為：

其中，path是待創(chuàng)建目錄的完整路徑，包括待創(chuàng)建目錄的父目錄和新目錄的名字，如需在"/test"目錄下創(chuàng)建一個(gè)"newdir"目錄，則path為"/test/newdir"，注意，必須保證父目錄已存在，且父目錄下不存在即將創(chuàng)建的同名目錄。mode指定目錄相關(guān)的權(quán)限，默認(rèn)使用0777。

返回值為標(biāo)準(zhǔn)的錯(cuò)誤號(hào)，若返回AW_OK，表示新目錄創(chuàng)建成功，否則，表示新目錄創(chuàng)建失敗。如在"/test"目錄下創(chuàng)建一個(gè)"newdir"目錄，則范例程序詳見(jiàn)程序清單11.20。

程序清單11.20 創(chuàng)建目錄范例程序

若程序運(yùn)行成功，則在TF卡中創(chuàng)建了一個(gè)newdir目錄。為了驗(yàn)證操作是否成功，可以拔下TF卡，將TF卡通過(guò)讀卡器連接到PC上（Windows系統(tǒng)），通過(guò)PC查看TF卡中的內(nèi)容，TF卡目錄的內(nèi)容詳見(jiàn)圖11.4 (a)，其中新增了newdir目錄，且newdir當(dāng)前是一個(gè)空目錄，詳見(jiàn)圖11.4(b)。

圖11.4 通過(guò)PC查看TF卡的內(nèi)容（2）

可以嘗試在newdir目錄中新建文件，例如：

2. 打開(kāi)目錄

在目錄操作中，遍歷已存在的一個(gè)目錄是一種常見(jiàn)的操作，即遍歷一個(gè)目錄下所有的子項(xiàng)（包括文件和子目錄）。遍歷過(guò)程主要分為3個(gè)步驟：打開(kāi)目錄、讀取目錄、關(guān)閉目錄。

在遍歷一個(gè)目錄前，首先需要打開(kāi)該目錄，其函數(shù)原型為：

其中，dirname為目錄名，如需打開(kāi)根目錄下的test目錄，則其值為"/test"。返回值為指向一個(gè)目錄對(duì)象的指針，目錄類型struct aw_dir 在io/aw_dirent.h文件中定義，其具體定義用戶無(wú)需掌握，僅需保存下該指針，后續(xù)使用該指針代表打開(kāi)的目錄即可，特別地，若返回值為NULL，則表示目錄打開(kāi)失敗。打開(kāi)目錄的范例程序詳見(jiàn)程序清單11.21。

程序清單11.21 打開(kāi)目錄范例程序

3. 讀取目錄

打開(kāi)目錄后，即可依次讀取該目錄中的各個(gè)子項(xiàng)（文件或子目錄），獲得它們的名字等信息，其函數(shù)原型為：

其中，dirp為指向目錄對(duì)象的指針，可通過(guò)打開(kāi)目錄獲得。返回值為目錄項(xiàng)指針，即為本次讀取的一條目錄項(xiàng)，其類型struct aw_dirent的定義如下：

其中，d_ino為項(xiàng)目序列號(hào)，其值為一個(gè)整數(shù)，每個(gè)子項(xiàng)都有一個(gè)對(duì)應(yīng)的序列號(hào)，在一個(gè)目錄中，若共計(jì)有10個(gè)子項(xiàng)，則各子項(xiàng)的序列號(hào)依次為0 ~ 9。d_name為該子項(xiàng)的名字。

打開(kāi)目錄后首次調(diào)用讀取目錄接口，獲得的子項(xiàng)序列號(hào)為0，要獲取一個(gè)目錄下所有的子項(xiàng)，可以多次調(diào)用讀取目錄接口，每次調(diào)用結(jié)束后，都會(huì)將序列號(hào)加1，下次讀取時(shí)將讀取到下一個(gè)子項(xiàng)。特別地，若讀取目錄的返回值為NULL，表示讀取結(jié)束。讀取一個(gè)目錄下所有子項(xiàng)的范例程序詳見(jiàn)程序清單11.22。

程序清單11.22 讀取目錄范例程序（1）

aw_readdir()接口通過(guò)返回值返回一個(gè)指向讀取目錄子項(xiàng)的指針，該指針指向的實(shí)際內(nèi)存是由系統(tǒng)內(nèi)部分配的靜態(tài)內(nèi)存，在多任務(wù)環(huán)境中，這份內(nèi)存是共享的，因此，該接口不是線程安全的，例如，在一個(gè)任務(wù)中讀取了一次目錄，則靜態(tài)內(nèi)存中存放了本次讀取的結(jié)果，其地址返回給用戶，用戶通過(guò)指針訪問(wèn)讀取目錄的結(jié)果。若在這個(gè)過(guò)程中，另外一個(gè)任務(wù)也讀取了一次目錄，則內(nèi)存中的數(shù)據(jù)將發(fā)生改變，這將覆蓋前一個(gè)任務(wù)讀取目錄的結(jié)果。由此可見(jiàn)，當(dāng)多個(gè)任務(wù)同時(shí)訪問(wèn)一個(gè)目錄時(shí)，必須使用互斥機(jī)制。

為此，AWorks提供了另外一個(gè)線程安全的接口：aw_readdir_r()，它們?cè)诠δ苌鲜峭耆粯拥?，唯一的不同是，使用該接口讀取目錄時(shí)，讀取結(jié)果存儲(chǔ)在用戶提供的一段內(nèi)存中，其原型為：

其中， dirp為指向目錄對(duì)象的指針，可通過(guò)打開(kāi)目錄獲得；entry為存儲(chǔ)讀取結(jié)果的緩存，result為一個(gè)二維指針，即一個(gè)指針的地址，程序執(zhí)行結(jié)束后，指針的值即被設(shè)置為指向本次讀取目錄的結(jié)果。

若返回值為AW_OK，則讀取成功，否則，讀取失敗。值得注意的是，當(dāng)目錄讀取未達(dá)結(jié)尾，成功讀取到一個(gè)子項(xiàng)時(shí)，由于讀取的結(jié)果存儲(chǔ)在entry指向的內(nèi)存中，因此，result的值被設(shè)置為entry（即：*result=entry），當(dāng)目錄讀取達(dá)到結(jié)尾時(shí)，result的值將被設(shè)置為NULL（即：*result=NULL）。范例程序詳見(jiàn)程序清單11.23。

程序清單11.23 讀取目錄范例程序（2）

4. 關(guān)閉目錄

若讀取目錄完畢，或不再需要讀取目錄時(shí)，則可以關(guān)閉目錄，其函數(shù)原型為：

其中，dirp為指向目錄對(duì)象的指針，可通過(guò)打開(kāi)目錄獲得。返回值為AW_OK時(shí)表示關(guān)閉成功，否則，表示關(guān)閉失敗。

綜合打開(kāi)目錄、讀取目錄、關(guān)閉目錄三個(gè)接口，遍歷一個(gè)目錄下所有子項(xiàng)的范例程序詳見(jiàn)程序清單11.24。

程序清單11.24 遍歷目錄范例程序

5. 刪除目錄

當(dāng)一個(gè)目錄不再使用，可以刪除該目錄，刪除指定目錄的函數(shù)原型為：

其中，path為目錄的路徑。返回值為AW_OK時(shí)表示刪除成功，否則，表示刪除失敗。該函數(shù)僅可用于刪除一個(gè)空目錄，若目錄非空，則刪除失敗。范例程序詳見(jiàn)程序清單11.25。

程序清單11.25 刪除目錄范例程序

11.5 微型數(shù)據(jù)庫(kù)

AWorks提供了一個(gè)基于文件系統(tǒng)實(shí)現(xiàn)的微型數(shù)據(jù)庫(kù)，用以管理信息記錄，每條記錄由“關(guān)鍵字”和“值”兩部分構(gòu)成，關(guān)鍵字可用于記錄的查找、刪除等。微型數(shù)據(jù)庫(kù)是基于哈希表原理實(shí)現(xiàn)的，具有簡(jiǎn)潔、高效的特點(diǎn)。為了便于理解，本節(jié)首先對(duì)哈希表進(jìn)行簡(jiǎn)要介紹，然后再介紹微型數(shù)據(jù)庫(kù)的各個(gè)接口。

11.5.1 哈希表

在數(shù)據(jù)存儲(chǔ)應(yīng)用中，存儲(chǔ)的記錄往往都具有唯一的關(guān)鍵字，以便于管理。例如，為了管理學(xué)生信息（包含姓名、性別、身高、體重等），會(huì)為每個(gè)學(xué)生分配一個(gè)學(xué)號(hào)，通過(guò)學(xué)號(hào)就可以唯一的定位一個(gè)學(xué)生，這里的學(xué)號(hào)即為關(guān)鍵字。常見(jiàn)的身份證號(hào)也具有類似的作用。

假設(shè)需要設(shè)計(jì)一個(gè)信息管理系統(tǒng)，用于管理學(xué)生信息，可以將每條學(xué)生信息看作一條記錄。

一條記錄包含學(xué)號(hào)、姓名、性別、身高、體重等信息，可定義與學(xué)生記錄對(duì)應(yīng)的結(jié)構(gòu)體類型，詳見(jiàn)程序清單11.26。

程序清單11.26 學(xué)生信息類型定義

作為一個(gè)信息管理系統(tǒng)，首先要能夠?qū)崿F(xiàn)學(xué)生記錄的存儲(chǔ)，基于文件系統(tǒng)接口可以很容易實(shí)現(xiàn)：直接將記錄寫入到文件中即可。增加一條學(xué)生記錄的范例程序詳見(jiàn)程序清單11.27。

程序清單11.27 增加一條學(xué)生記錄

程序中，假定了存儲(chǔ)學(xué)生記錄的文件名為："/test/students.txt"，這就要求系統(tǒng)中，將/test目錄掛載到特定的存儲(chǔ)器，比如SD卡或U盤等。增加一條記錄的實(shí)現(xiàn)非常簡(jiǎn)單，僅僅是將p_info指向的學(xué)生記錄順序的存入了文件尾部，因此，使用這種方法增加學(xué)生記錄的效率還是比較高的。

如果使用student_add()函數(shù)增加了若干學(xué)生記錄，將學(xué)生記錄存儲(chǔ)在了文件中，接下來(lái)，最常見(jiàn)的操作就是根據(jù)學(xué)號(hào)查詢學(xué)生信息。基于學(xué)生信息的存儲(chǔ)方式，可以實(shí)現(xiàn)一個(gè)學(xué)生信息查詢函數(shù)，范例程序詳見(jiàn)程序清單11.28。

程序清單11.28 根據(jù)學(xué)號(hào)查詢學(xué)生記錄

由此可見(jiàn)，程序僅僅從文件頭部順序讀取文件學(xué)生記錄，逐一與待查找的學(xué)號(hào)進(jìn)行比對(duì)，直到查找到與學(xué)號(hào)完全一致的學(xué)生記錄。

上述簡(jiǎn)單的范例程序?qū)崿F(xiàn)了記錄的添加和查找。由于查找學(xué)生記錄是采用順序查找的方式，隨著學(xué)生記錄的增加，查找效率將逐步降低。例如，一所大學(xué)往往有幾萬(wàn)學(xué)生，則使用該系統(tǒng)管理學(xué)生記錄時(shí)，一次簡(jiǎn)單的查找則可能要順序?qū)Ρ壬先f(wàn)次學(xué)號(hào)，顯然，效率不高。

如何以更高的效率實(shí)現(xiàn)查找呢？在查找算法中，非常經(jīng)典高效的算法是“二分法查找”，按10000條記錄算，最多也只需要比較14次（log210000）。但是，使用“二分法查找”的前提是信息必須有序排列，即要求學(xué)生記錄必須按照學(xué)號(hào)從大到小或從小到大的順序進(jìn)行存儲(chǔ)，這就導(dǎo)致在添加學(xué)生信息時(shí)，必須將學(xué)生記錄按照學(xué)號(hào)順序，插入到指定位置，而不能像程序清單11.27那樣，簡(jiǎn)單的將信息添加至文件尾部。對(duì)于文件操作來(lái)講，插入操作是非常繁瑣的，若已經(jīng)有大量學(xué)生記錄按學(xué)號(hào)順序存儲(chǔ)在文件中，在此基礎(chǔ)上再插入一條記錄到這些記錄的中間某個(gè)位置，則需要將其后的所有記錄后移，以預(yù)留出一條記錄的存儲(chǔ)空間，這意味著需要將后續(xù)所有記錄讀出，再重新寫入到其后的地址中。由此可見(jiàn)，雖然使用這種方法可以提高查找效率，卻犧牲了添加信息的效率。

“順序查找”管理方式犧牲了查找記錄的效率，“二分法查找”犧牲了寫入記錄的效率。能否將二者折中一下呢？“二分法查找”的本質(zhì)是每次縮小一半的查找范圍，基于縮小查找范圍的思想，可以嘗試縮小每次“順序查找”的范圍。同樣以10000條記錄為例，為了縮小每次“順序查找”的范圍，將記錄分為兩個(gè)部分，例如，制定以下規(guī)則：學(xué)號(hào)小于某一值時(shí)，作為第一部分存儲(chǔ)在某一文件中；反之，作為第二部分存儲(chǔ)在另外一個(gè)文件中。

如此一來(lái)，在寫入記錄時(shí)，只需要多一條判斷語(yǔ)句，對(duì)性能并沒(méi)太大影響。而在查找時(shí)，只要根據(jù)學(xué)號(hào)判斷出記錄應(yīng)存儲(chǔ)在哪一個(gè)文件中，然后按照順序查找的方式進(jìn)行查找即可。此時(shí)，若用于分界的學(xué)號(hào)選擇恰當(dāng)，使兩個(gè)部分的學(xué)生記錄數(shù)量基本相同，則順序查找需要比較的次數(shù)就從最大的10000次降低到了約5000次。由此可見(jiàn)，通過(guò)一個(gè)簡(jiǎn)單的方法，將信息分別存儲(chǔ)在兩個(gè)文件中，就可以明顯地提高查找效率。

為了繼續(xù)提高查找的效率，還可以將記錄分為更多的部分，比如，分成250個(gè)部分，序號(hào)為0~ 249，若劃分規(guī)則恰當(dāng)，使各個(gè)部分的學(xué)生記錄數(shù)量基本相同，則每個(gè)部分的記錄數(shù)目就約為40條，此時(shí)，順序查找需要比較的次數(shù)就僅需約40次即可！示意圖詳見(jiàn)圖11.5。

圖11.5 將記錄分為多個(gè)部分

圖11.5可以看作大小為250的“哈希表”，“哈希表”的每個(gè)表項(xiàng)對(duì)應(yīng)了一部分記錄。哈希表的核心思想是將一個(gè)很大范圍的關(guān)鍵字空間（例如，學(xué)號(hào)為6字節(jié)，6字節(jié)數(shù)據(jù)共計(jì)48位，其表示的數(shù)值空間大小為：248，約280萬(wàn)億，是一個(gè)相當(dāng)大的范圍），映射到一個(gè)較小的空間（范圍序號(hào)：0 ~ 249，大小為250）。由于是大范圍映射到小范圍，因此可能有一部分關(guān)鍵字（學(xué)號(hào)）映射到同一個(gè)表項(xiàng)中，也就是每個(gè)表項(xiàng)可能包含多條記錄。

哈希表的關(guān)鍵是確定映射關(guān)系，即如何將關(guān)鍵字（學(xué)號(hào)）映射到表項(xiàng)的序號(hào)，也就是將所有記錄劃分為多個(gè)部分的具體規(guī)則。當(dāng)寫入或查找一條記錄時(shí)，可以通過(guò)映射關(guān)系確定該記錄屬于哪一部分。這個(gè)映射關(guān)系對(duì)應(yīng)的函數(shù)即為“哈希函數(shù)”，其作用就是將學(xué)號(hào)轉(zhuǎn)換為哈希表的表項(xiàng)序號(hào)。例如，假定學(xué)號(hào)是均勻分布的，則可以將6字節(jié)學(xué)號(hào)直接求和再對(duì)250取余，進(jìn)而得到一個(gè)0 ~ 249的數(shù)，范例程序詳見(jiàn)程序清單11.29。

程序清單11.29 映射關(guān)系——通過(guò)學(xué)號(hào)得到分組索引

db_id_to_idx()函數(shù)就是“哈希函數(shù)”，哈希函數(shù)的結(jié)果（分組索引）稱之為“哈希值”。

“哈希函數(shù)”是整個(gè)哈希表的關(guān)鍵，哈希函數(shù)應(yīng)盡可能確保記錄均勻的分布到各個(gè)表項(xiàng)中，不能差異太大，極端地，若哈希函數(shù)選擇有誤，將所有記錄分布到了一個(gè)表項(xiàng)中，那這樣的哈希表將沒(méi)有任何意義，因?yàn)槊看尾檎矣涗浻只氐搅俗畛醯臓顟B(tài)：遍歷所有記錄。

實(shí)際應(yīng)用中，記錄往往是動(dòng)態(tài)管理的，可以隨時(shí)動(dòng)態(tài)添加、刪除。因此，每一部分（哈希表的表項(xiàng)）包含的記錄數(shù)也會(huì)動(dòng)態(tài)增加或減少。為了便于動(dòng)態(tài)管理每一部分的記錄，各部分可以使用鏈表管理該部分中可能存在的多條記錄，示意圖詳見(jiàn)圖11.6，圖中所示的鏈?zhǔn)焦１斫Y(jié)構(gòu)就是AWorks中微型數(shù)據(jù)庫(kù)原理。

圖11.6 鏈?zhǔn)焦１斫Y(jié)構(gòu)

11.5.2 微型數(shù)據(jù)庫(kù)接口

前面簡(jiǎn)要介紹了哈希表的原理，AWorks提供了一個(gè)基于哈希表思想實(shí)現(xiàn)的微型數(shù)據(jù)庫(kù)，提供了增加、刪除、查找等接口，相關(guān)接口的原型詳見(jiàn)表11.6。

表11.6 微型數(shù)據(jù)庫(kù)接口（aw_db_micro_hash_kv.h）

微型數(shù)據(jù)庫(kù)相關(guān)的文件和接口以“aw_db_micro_hash_kv”作為命名空間，其中，“aw_”表示AWorks，“db”表示數(shù)據(jù)庫(kù)（data base），“micro”表示微型，hash_kv表示基于的是hash關(guān)鍵字和值的思想。

1. 定義數(shù)據(jù)庫(kù)實(shí)例

所有接口的第一個(gè)參數(shù)均為aw_db_micro_hash_kv_t類型的指針，用于指向待操作的數(shù)據(jù)庫(kù)實(shí)例。該類型的具體定義（如具體包含哪些成員）用戶無(wú)需關(guān)心，僅需在使用微型數(shù)據(jù)庫(kù)前，使用該類型定義一個(gè)數(shù)據(jù)庫(kù)實(shí)例即可，例如：

其中，students_db的地址即可作為各個(gè)接口p_db參數(shù)的實(shí)參傳遞。

2. 初始化

在使用數(shù)據(jù)庫(kù)前，需要完成數(shù)據(jù)庫(kù)的初始化，以指定哈希表大小、關(guān)鍵字長(zhǎng)度、值長(zhǎng)度以及存儲(chǔ)整個(gè)數(shù)據(jù)庫(kù)的文件名等信息。其函數(shù)原型為：

其中，p_db指向待初始化的數(shù)據(jù)庫(kù)實(shí)例。size表示哈希表的大小，即表項(xiàng)的數(shù)目，如需設(shè)計(jì)圖11.6所示的哈希表，由于其哈希表的大小為250，則該值應(yīng)設(shè)置為250。key_size為關(guān)鍵字長(zhǎng)度，例如，以學(xué)號(hào)為關(guān)鍵字，由于學(xué)號(hào)的長(zhǎng)度為6字節(jié)，則該值應(yīng)設(shè)置為6。

value_size表示記錄中值的長(zhǎng)度，以學(xué)生記錄為例，一條學(xué)生記錄包含學(xué)號(hào)、姓名、性別、身高、體重等信息。最初的學(xué)生記錄對(duì)應(yīng)的結(jié)構(gòu)體類型詳見(jiàn)程序清單11.26。在使用微型數(shù)據(jù)庫(kù)時(shí)，關(guān)鍵字和值是不同的兩個(gè)部分，均會(huì)被存儲(chǔ)到文件中。因此，可以將關(guān)鍵字學(xué)號(hào)分離出來(lái)，剩余的信息作為一條學(xué)生記錄的“值”。詳見(jiàn)程序清單11.30。

程序清單11.30 學(xué)生記錄信息類型（不包括關(guān)鍵字——學(xué)號(hào)）

基于此，value_size的值則應(yīng)設(shè)置為：sizeof(student_t)。

pfn_hash用于指定一個(gè)哈希函數(shù)，其作用是將關(guān)鍵字轉(zhuǎn)換為一個(gè)哈希值，哈希值即為哈希表的索引。其類型aw_db_micro_hash_kv_func_t定義如下：

該類型為一個(gè)函數(shù)指針類型，其指向函數(shù)的形參為關(guān)鍵字，返回值為哈希值（類型為無(wú)符號(hào)整數(shù)），哈希值將作為哈希表的索引。通過(guò)對(duì)哈希表的介紹可知，哈希函數(shù)的選擇直接決定了記錄的分布，必須盡可能地確保所有記錄均勻地分布在各個(gè)表項(xiàng)中。不同的關(guān)鍵字?jǐn)?shù)據(jù)具有不同的分布特性，因此，哈希函數(shù)需要由用戶根據(jù)實(shí)際情況提供，簡(jiǎn)單的實(shí)現(xiàn)可以將關(guān)鍵字按字節(jié)求和后再對(duì)哈希表大小取余，詳見(jiàn)程序清單11.31。

程序清單11.31 簡(jiǎn)易的哈希函數(shù)實(shí)現(xiàn)

其中，函數(shù)名hash_func_id_to_idx即可作為pfn_hash的實(shí)參傳遞。

file_name用于指定存儲(chǔ)該數(shù)據(jù)庫(kù)信息及所有記錄的文件名，若一個(gè)系統(tǒng)中存在多個(gè)數(shù)據(jù)庫(kù)（定義了多個(gè)數(shù)據(jù)庫(kù)實(shí)例），則在初始化各個(gè)數(shù)據(jù)庫(kù)時(shí)，為各個(gè)數(shù)據(jù)庫(kù)指定的文件名應(yīng)該不同，以使各個(gè)數(shù)據(jù)庫(kù)使用不同的文件存儲(chǔ)數(shù)據(jù)。在程序清單11.27和程序清單11.28所示的簡(jiǎn)易范例程序中，每次寫入記錄或查找記錄前，都會(huì)執(zhí)行一次打開(kāi)文件操作，并在寫入或查找結(jié)束后關(guān)閉文件。在實(shí)際應(yīng)用中，可能會(huì)頻繁的執(zhí)行寫入、查找等操作，這樣就會(huì)導(dǎo)致頻繁的打開(kāi)、關(guān)閉文件，降低了程序運(yùn)行的效率，為此，AWorks提供的數(shù)據(jù)庫(kù)僅僅在初始化時(shí)打開(kāi)文件，后續(xù)其它操作均無(wú)需再執(zhí)行打開(kāi)文件操作。若初始化時(shí)指定的文件名對(duì)應(yīng)文件已經(jīng)存在，則僅僅打開(kāi)該文件，然后再該文件的基礎(chǔ)上進(jìn)行記錄的管理（添加、刪除等）；若文件名對(duì)應(yīng)文件不存在，則創(chuàng)建該文件，以建立一個(gè)全新的數(shù)據(jù)庫(kù)（數(shù)據(jù)庫(kù)中沒(méi)有任何有效記錄）。初始化數(shù)據(jù)庫(kù)的范例程序詳見(jiàn)程序清單11.32。

程序清單11.32 初始化數(shù)據(jù)庫(kù)范例程序

3. 增加一條記錄

該函數(shù)用于向數(shù)據(jù)庫(kù)中增加一條記錄，其函數(shù)原型為：

其中，p_db指向已經(jīng)初始化的數(shù)據(jù)庫(kù)實(shí)例。p_key指向本次增加記錄的關(guān)鍵字，其長(zhǎng)度必須與初始化指定的key_size一致。p_value指向本次增加記錄的具體“值”。例如，待增加一條學(xué)生記錄，其各項(xiàng)信息詳見(jiàn)表11.7。

表11.7 待增加的學(xué)生信息舉例

則向數(shù)據(jù)庫(kù)中增加該學(xué)生記錄的范例程序詳見(jiàn)程序清單11.33。

程序清單11.33 增加記錄范例程序

4. 根據(jù)關(guān)鍵字查找記錄

向數(shù)據(jù)庫(kù)中添加記錄后，可以根據(jù)關(guān)鍵字查找記錄的詳細(xì)信息，查找記錄的函數(shù)原型為：

其中，p_db指向數(shù)據(jù)庫(kù)實(shí)例。p_key為輸入?yún)?shù)，指向本次查找記錄的關(guān)鍵字，關(guān)鍵字長(zhǎng)度必須與初始化時(shí)指定的key_size一致。p_value為輸出參數(shù)，返回本次查找到的記錄。

例如，若使用程序清單11.33所示的范例程序增加了一條學(xué)生記錄，作為測(cè)試，可以使用查找記錄接口查找學(xué)號(hào)為201644700239的記錄，以查看其對(duì)應(yīng)的“值”信息是否與寫入的信息一致。范例程序詳見(jiàn)程序清單11.34。

程序清單11.34 根據(jù)關(guān)鍵字查找記錄的范例程序

程序中，為了避免使用aw_kprintf()打印浮點(diǎn)數(shù)，將身高和體重分為整數(shù)部分和小數(shù)部分打印，最終等效于保留2位小數(shù)的浮點(diǎn)數(shù)打印效果。

5. 刪除一條記錄

通過(guò)該接口可以刪除數(shù)據(jù)庫(kù)中的一條記錄，其函數(shù)原型為：

其中，p_db指向數(shù)據(jù)庫(kù)實(shí)例。p_key指向本次需要?jiǎng)h除記錄的關(guān)鍵字，關(guān)鍵字長(zhǎng)度必須與初始化時(shí)指定的key_size一致。

例如，若使用程序清單11.33所示的范例程序增加了一條學(xué)生記錄，作為測(cè)試，可以將學(xué)號(hào)為201644700239的記錄刪除。范例程序詳見(jiàn)程序清單11.35。

程序清單11.35 根據(jù)關(guān)鍵字刪除記錄的范例程序

使用程序清單11.35所示程序刪除記錄后，若再查找學(xué)號(hào)為201644700239的記錄，將會(huì)查找失敗。

6. 解初始化

與數(shù)據(jù)庫(kù)初始化函數(shù)對(duì)應(yīng)。當(dāng)暫時(shí)不使用一個(gè)數(shù)據(jù)庫(kù)時(shí)，可以執(zhí)行該函數(shù)，以釋放相關(guān)資源。注意，解初始化后，數(shù)據(jù)庫(kù)中已經(jīng)存儲(chǔ)的內(nèi)容保持不變。解初始化函數(shù)的原型為：

其中，p_db指向數(shù)據(jù)庫(kù)實(shí)例。例如，在一次應(yīng)用中，添加了100個(gè)學(xué)生記錄，添加結(jié)束后，暫時(shí)不再使用該數(shù)據(jù)庫(kù)，則可以解初始化該數(shù)據(jù)庫(kù)，范例程序詳見(jiàn)程序清單11.36。

程序清單11.36 解初始化范例程序

在初始化函數(shù)的介紹中提到，為了避免頻繁的打開(kāi)文件和關(guān)閉文件，在初始化時(shí)打開(kāi)了文件，使得在添加記錄、刪除記錄、查找記錄時(shí)，無(wú)需再打開(kāi)文件。與初始化函數(shù)對(duì)應(yīng)，在解初始化函數(shù)中，關(guān)閉了文件。關(guān)閉文件后，文件中的內(nèi)容保持不變。如需再次使用該數(shù)據(jù)庫(kù)，則應(yīng)該重新執(zhí)行一次初始化操作。

上面介紹了各個(gè)接口的使用方法，基于這些接口，可以實(shí)現(xiàn)一個(gè)學(xué)生記錄管理的綜合范例程序，詳見(jiàn)程序清單11.37。

程序清單11.37 微型數(shù)據(jù)庫(kù)綜合范例程序

測(cè)試程序主要由test_db_micro_hash_kv()完成，在aw_min()主程序中，僅僅是簡(jiǎn)單調(diào)用了該函數(shù)。在test_db_micro_hash_kv()函數(shù)中，首先初始化了一個(gè)數(shù)據(jù)庫(kù)，然后向其中添加了100個(gè)學(xué)生記錄（為了快捷產(chǎn)生這些記錄，以隨機(jī)數(shù)的方式自動(dòng)生成，隨機(jī)數(shù)無(wú)實(shí)際意義，僅供測(cè)試使用。同時(shí)，為了保證添加的學(xué)生學(xué)號(hào)唯一，在添加記錄前，通過(guò)搜索接口查看是否存在該學(xué)號(hào)的學(xué)生，若存在，則不再重復(fù)添加）。接著測(cè)試了查找接口，查找最后添加的學(xué)生記錄。然后測(cè)試刪除接口，刪除了最后添加的學(xué)生記錄，刪除成功后，再次查找將會(huì)失敗。最后，所有操作執(zhí)行完畢，解初始化數(shù)據(jù)庫(kù)。