信息與計算科學畢業(yè)論文通用數(shù)據(jù)庫的c語言實現(xiàn)

1、<p><b>　　本科畢業(yè)論文</b></p><p><b>　?。?0 屆）</b></p><p>　　通用數(shù)據(jù)庫的C語言實現(xiàn)</p><p>　　所在學院 </p><p>　　專業(yè)班級 信息與計算科學

2、 </p><p>　　學生姓名 學號 </p><p>　　指導教師 職稱 </p><p>　　完成日期 年 月 </p><p><b>　　摘要</b></p>

3、<p>　　Dbm是在UNIX系統(tǒng)中很流行的數(shù)據(jù)庫函數(shù)庫, 其主要的兩個特點是動態(tài)散列算法和鍵值查找方式. 至今, dbm有許多版本, 許多的不足的得到了改進. 但是, 這些實現(xiàn)都有一個根本的缺點，就是它們都沒有提供并發(fā)控制(如記錄鎖). 本文就是針對dbm數(shù)據(jù)庫函數(shù)庫的這點不足, 開發(fā)一個類似的dbm庫--MyDbm, 增加了并發(fā)控制機制, 從而允許多進程同時更新同一數(shù)據(jù)庫. 具體并發(fā)控制策略主要有兩個部分: 一是采用進

4、程非集中式訪問數(shù)據(jù)庫; 二是對文件加鎖時, 采用細瑣, 即加鎖鎖定的區(qū)域為文件中的某個字節(jié)段而非整個文件, 從而在理論上能提供更高的并發(fā)度.</p><p>　　關(guān)鍵字: dbm數(shù)據(jù)庫函數(shù)庫; 并發(fā); 非集中式訪問; 文件鎖</p><p><b>　　Abstract</b></p><p>　　dbm is very popular dat

5、abase library in the UNIX system. Two main features of dbm are the dynamic hashing algorithm and the search fashion of key value. So far, there are many Dbm versions, many of the shortage have been improved. However, one

6、 fundamental drawback of the existing implementations is that they can not provide concurrency control (such as record locks). With respect to the shortcoming of dbm database, in the thesis, a kind of dbm library, MyDbm,

7、 is developed. In the new dbm library</p><p>　　Keywords: DBM database library; Concurrent control; Non-centralized access; File lock</p><p><b>　　目錄</b></p><p><b>　

8、　中文摘要I</b></p><p>　　英文摘要錯誤!未定義書簽。</p><p><b>　　1前言1</b></p><p><b>　　2并發(fā)2</b></p><p><b>　　2.1 讀鎖2</b></p><p>&

9、lt;b>　　2.2 寫鎖2</b></p><p><b>　　2.3 粗鎖2</b></p><p><b>　　2.4 細鎖2</b></p><p>　　3進程訪問數(shù)據(jù)庫的方式4</p><p>　　3.1 集中式訪問數(shù)據(jù)庫4</p><p&g

10、t;　　3.2 非集中式訪問數(shù)據(jù)庫4</p><p><b>　　4實現(xiàn)概述6</b></p><p><b>　　5具體實現(xiàn)9</b></p><p>　　5.1 MyDbm_Open9</p><p>　　5.2 MyDbm_Close錯誤!未定義書簽。</p><

11、p>　　5.3 MyDbm_Select10</p><p>　　5.4 MyDbm_Insert12</p><p>　　5.5 MyDbm_Update, MyDbm_Rewind和MyDbm_NextRecord13</p><p><b>　　6性能分析15</b></p><p>　　6.1 單進

12、程的結(jié)果16</p><p>　　6.2 多進程的結(jié)果17</p><p><b>　　7小結(jié)18</b></p><p><b>　　參考文獻19</b></p><p>　　致謝錯誤!未定義書簽。</p><p><b>　　附件20</b&g

13、t;</p><p><b>　　前言</b></p><p>　　dbm是在UNIX系統(tǒng)中很流行的數(shù)據(jù)庫函數(shù)庫, 它是由Ken Thompson開發(fā)的, 當時使用了動態(tài)散列結(jié)構(gòu). 最初, dbm與V7系統(tǒng)一起提供, 并在所有的BSD版本中出現(xiàn), 其中也包含在SVR4的BSD兼容函數(shù)庫中[AT&T 1990c]. BSD的開發(fā)者擴充了dbm函數(shù)庫, 并將其改名

14、為ndbm. ndbm函數(shù)庫包括在BSD和SVR4中. ndbm函數(shù)被標準化后成為Single UNIX Specification的XSI擴展部分[1]. 而在Linux系統(tǒng)上, 開發(fā)者們用gdbm庫來支持dbm函數(shù)庫和ndbm函數(shù)庫[1]. dbm函數(shù)庫所管理的數(shù)據(jù)庫是一個輕量級的數(shù)據(jù)庫, 不是標準意義上的數(shù)據(jù)庫, 不支持SQL(不過可以在它的基礎(chǔ)上開發(fā)), 純粹以二進制儲存的一種數(shù)據(jù)庫, 常用于系統(tǒng)底層的數(shù)據(jù)庫, 在其他一些很少更

15、新內(nèi)容的地方也可以使用[2]. </p><p>　　dbm函數(shù)庫主要的兩個特點是動態(tài)散列算法和鍵值查找方式. Seltzer和Yigit在文中詳細介紹了dbm函數(shù)庫使用的動態(tài)散列結(jié)構(gòu)的歷史. 采用動態(tài)散列算法時在查找數(shù)據(jù)時非?？焖? 當然其付出的代價就是插入數(shù)據(jù)異常的緩慢[1]. 另外對于鍵值查找方式, dbm數(shù)據(jù)庫是通過包括兩個基本元素數(shù)據(jù)塊, 一塊是想要保存起來的數(shù)據(jù), 另一塊是對其進行檢索時用做關(guān)鍵字的數(shù)

16、據(jù). 對于每個dbm數(shù)據(jù)庫而言, 保存在其中的每一個數(shù)據(jù)塊都必須有一個獨一無二的關(guān)鍵字. 對于關(guān)鍵字和數(shù)據(jù)本身倒沒有什么限制, 對使用超長數(shù)據(jù)或超長關(guān)鍵字的情況也沒有定義什么錯誤. 技術(shù)規(guī)范里倒是允許在具體實現(xiàn)時將關(guān)鍵字/數(shù)據(jù)對的最大長度限制在1024個字節(jié), 但這個限制通常并沒有什么意義, 因為具體實現(xiàn)出來的東西往往比技術(shù)規(guī)范的要求更靈活[2]. 關(guān)鍵字的取值被用做檢索儲存數(shù)據(jù)的索引, 就如同書簽一般. </p><

17、;p>　　至今, dbm有許多版本, 許多的不足的得到改進. 但是, 這些實現(xiàn)都有一個根本的缺點是: 他們都不支持多個進程對數(shù)據(jù)庫的并發(fā)更新. 它們都沒有提供并發(fā)控制(如記錄鎖). 絕大部分商用數(shù)據(jù)庫函數(shù)庫提供多進程同時更新數(shù)據(jù)庫所需要的并發(fā)控制[3]. 這些系統(tǒng)一般都使用建議記錄鎖, 不過, 它們也常常實現(xiàn)自己的鎖原語, 以避免為獲得一把無競爭的鎖而需的系統(tǒng)調(diào)用開銷[4]. 本文就是針對dbm數(shù)據(jù)庫函數(shù)庫的這點不足, 開發(fā)一個類

18、似的dbm庫MyDbm, 但增加了并發(fā)控制機制, 從而允許多進程同時更新同一數(shù)據(jù)庫. 具體并發(fā)控制主要有兩個部分, 一是采用進程非集中式訪問數(shù)據(jù)庫. 二是對文件加鎖時. </p><p>　　接下來, 本文將首先介紹進程訪問數(shù)據(jù)庫的兩種方式和文件加鎖的概念. </p><p><b>　　并發(fā)</b></p><p>　　并發(fā)控件的方式之一是對

19、進程要訪問的文件進行加鎖. 按訪問文件的方式來分, 可將鎖分為讀鎖和寫鎖:</p><p><b>　　讀鎖</b></p><p>　　讀鎖相對于文件的讀操作, 即文件必須從操作系統(tǒng)那獲取一把讀鎖, 才有權(quán)限來讀取文件的內(nèi)容[4]. 由于讀操作不影響文件內(nèi)容, 因而同一時間可以有多個進程獲取同一文件的讀鎖. 其數(shù)量僅由系統(tǒng)的限制進程數(shù)決定.</p>&

20、lt;p><b>　　寫鎖</b></p><p>　　寫鎖相對于文件的寫操作, 只有獲取了寫鎖, 進程才能修改文件的內(nèi)容[1]. 由于寫操作將修改文件內(nèi)容(不管你是否真的有修改過), 故同一時間只能有一個進程擁有寫鎖. 否則, 將導致文件內(nèi)容的不一致.</p><p>　　讀鎖與寫鎖的關(guān)系是互斥的, 即一個文件不能同時加上這兩把鎖[5]. 當文件首先被一個進程

21、加上讀鎖, 那么它將拒絕被加上寫鎖, 但可以被加上其他進程的讀鎖. 只有當文件上的所有讀鎖被釋放, 其它進程才有可能獲取該文件的寫鎖. 但文件若被一個進程加上寫鎖, 其他進程的讀鎖和寫鎖的申請都將失敗, 直到擁有該文件的進程釋放了其寫鎖. </p><p>　　從粒度粗細的角度, 鎖又可以被分為粗鎖和細鎖.</p><p><b>　　粗鎖</b></p>

22、<p>　　若獲取的文件鎖的鎖定范圍是整個文件, 就稱之為粗鎖[6]. 由于粗鎖鎖定了整個文件, 加上讀寫鎖的互斥性, 因而其在最大程度上限制了并發(fā)性. 以上對讀鎖和寫鎖的介紹就是基于粗鎖的, 因而可見其對進程并發(fā)度的限制.</p><p>　　假設(shè)要修改一個大文件的一小段內(nèi)容, 則在一個進程加了寫鎖之后, 文件的其他內(nèi)容就不允許其他進程進行讀取和修改, 這對于數(shù)據(jù)庫這樣的大型文件集是無法接受的.&

23、lt;/p><p><b>　　細鎖</b></p><p>　　細瑣就是為了改進粗鎖的并發(fā)性而提出來的. 其對文件加讀寫鎖時, 是針對文件的某一區(qū)域, 而非整個文件[3]. 因而, 在同一時間, 一個文件可以擁有多把讀鎖和寫鎖. 但對于同一區(qū)域, 依然體現(xiàn)讀寫鎖的互斥性.</p><p>　　從以上介紹可看出, 細瑣在進程并發(fā)性上相對于粗鎖有巨大

24、優(yōu)勢, 特別在于數(shù)據(jù)庫這種大型的結(jié)構(gòu)化文件中, 更加體現(xiàn)的淋漓盡致. 當然, 細瑣相對粗鎖實現(xiàn)起來更加復雜, 也需要更多的系統(tǒng)資源, 但相比其獲得的并發(fā)度, 這種交換是十分有意義的. 因而在實現(xiàn)MyDbm數(shù)據(jù)庫時, 采用了細瑣來實現(xiàn)并發(fā)控制.</p><p>　　這里對并發(fā)進行討論, 所依據(jù)的是對數(shù)據(jù)庫函數(shù)庫的簡單需求, 商業(yè)系統(tǒng)一般有更多的需要[7].</p><p>　　進程訪問數(shù)據(jù)庫

25、的方式</p><p>　　當多個進程訪問數(shù)據(jù)庫時, 可以采用集中式和非集中式這兩個方案來實現(xiàn)庫函數(shù)[8]. 使用這兩種方案的數(shù)據(jù)庫系統(tǒng)都有[8], 下面將分別介紹.</p><p><b>　　集中式訪問數(shù)據(jù)庫</b></p><p>　　其實現(xiàn)方式是, 讓一個進程作為管理數(shù)據(jù)庫的管理員, 只有它才能對數(shù)據(jù)庫文件進行訪問和相關(guān)操作, 其他進程

26、想要和數(shù)據(jù)庫通信只有通過IPC(進程間通信機制[6])機制和管理進程聯(lián)系, 從而間接的操作數(shù)據(jù)庫. 圖3.1描述了集中式訪問數(shù)據(jù)庫的過程.</p><p>　　圖3.1集中式訪問數(shù)據(jù)庫</p><p><b>　　非集中式訪問數(shù)據(jù)庫</b></p><p>　　每個進程通過庫函數(shù)獨立申請并發(fā)控制(加鎖), 然后再訪問數(shù)據(jù)庫文件[9]. 圖3.2

27、描述了非集中式訪問數(shù)據(jù)庫的過程.</p><p>　　圖3.2非集中式訪問數(shù)據(jù)庫</p><p>　　集中式訪問的優(yōu)點是能夠根據(jù)需要對操作模式進行調(diào)整. 例如, 管理進程通過給不同用戶進程分配不同的優(yōu)先級. 優(yōu)先級將影響管理進程對MyDbm數(shù)據(jù)庫接口的調(diào)用.</p><p>　　而非集中式訪問很難做到這一點, 在這種情況下只能依賴操作系統(tǒng)內(nèi)核的調(diào)度策略. 例如, 當

28、3個用戶進程同時調(diào)用MyDbm數(shù)據(jù)庫的調(diào)用接口對數(shù)據(jù)文件加鎖時, 誰會分配到鎖呢? 結(jié)果只能依賴操作系統(tǒng)在實際運行時調(diào)度. </p><p>　　集中式訪問的另一個優(yōu)點是, 復原要比非集中式方法容易[10]. 在集中式方法中, 所有狀態(tài)信息都集中保存在一個地方, 所以如若殺死了數(shù)據(jù)庫管理進程, 只需查看該處以識別需要解決的的未完成事務(wù), 然后將數(shù)據(jù)庫恢復到一致狀態(tài). </p><p>　　

29、但是非集中式在細鎖策略下, 并發(fā)度較好. 從上面2圖可看出, 由于集中式訪問數(shù)據(jù)庫是通過數(shù)據(jù)庫管理進程完成, 所以同一時間只有單進程訪問數(shù)據(jù)庫. 但非集中式訪問通過細鎖來鎖定文件的不同區(qū)域, 可實現(xiàn)較多進程同時訪問數(shù)據(jù)庫. 在多進程訪問數(shù)據(jù)庫時, 無疑非集中式比集中式具有優(yōu)勢. </p><p>　　還可以通過融合這兩種方式的優(yōu)點, 實現(xiàn)半集中式訪問數(shù)據(jù)庫的訪問[11]. 即數(shù)據(jù)庫管理進程數(shù)量擴充為多個, 他們采

30、用非集中式訪問數(shù)據(jù)庫, 用戶進程采用集中式方法, 通過IPC跟某一數(shù)據(jù)庫管理進程通信, 間接訪問數(shù)據(jù)庫. 由于這種方法實現(xiàn)起來比較復雜, 故暫時不采用. </p><p>　　綜上所述, MyDbm數(shù)據(jù)庫實現(xiàn)時采用非集中式訪問的方法. </p><p><b>　　實現(xiàn)概述</b></p><p>　　大多數(shù)訪問數(shù)據(jù)庫的函數(shù)庫使用兩個文件來存儲

31、信息: 一個索引文件和一個數(shù)據(jù)文件. 索引文件包含索引值(鍵)和指向數(shù)據(jù)文件中對應(yīng)數(shù)據(jù)記錄的指針. 有許多技術(shù)可用來組織索引文件, 以提高按鍵查詢的速度和效率. 這里采用固定大小的散列表來組織索引文件結(jié)構(gòu), 并采用鏈表來解決散列沖突. 在實現(xiàn)過程中, 用.idx后綴的文件作為索引文件, .dat后綴的文件作為數(shù)據(jù)文件(UNIX不以后綴來判別文件類型, 此后綴只為本程序識別文件所用). </p><p>　　索引文

32、件的基本單位: 索引, 由鍵和由null結(jié)尾的字符串組成. 這樣的好處是函數(shù)簡單, 也使數(shù)據(jù)庫文件在不同平臺間移植比較容易(如果采用二進制, 就會碰到不同平臺間二進制存儲格式不統(tǒng)一的問題). 當然其代價是更多的磁盤空間. </p><p>　　在本文的實現(xiàn)中, 每個索引的鍵, 只有一條對應(yīng)的記錄, 有些數(shù)據(jù)庫系統(tǒng)允許多條記錄使用相同的鍵, 并提供方法訪問與一個鍵有關(guān)的所用記錄. 另外, 由于只有一個索引文件, 所

33、以每條記錄只有一個鍵(不支持多鍵). 當然對于多鍵的支持, 只需添加索引文件, 每個鍵對應(yīng)一個索引文件, 當修改記錄時, 同時更新所用索引文件即可. </p><p>　　索引文件的結(jié)構(gòu)如圖4.1:</p><p>　　圖4.1 索引文件結(jié)構(gòu)</p><p>　　這里的指針是由4個ASCII字符組成, 這樣保證了可移植性. 指針由4個字符組成也限制了文件最大的字節(jié)數(shù)

34、為10000B, 當然這種限制可以修改指針的字符數(shù)加以解決. </p><p>　　空閑索引指針指向空閑鏈表. 當一條數(shù)據(jù)被刪除時, 對應(yīng)的索引記錄也被刪除, 其偏移量將被加到空閑鏈表中, 以重復利用此文件空間. </p><p>　　鏈表指針個數(shù)可是隨意定制的, 具有相同哈希值的鍵將被放入相同的鏈表中, 鏈表指針指向了鏈表的第一元素, 若其值為0, 表示該鏈表為空. </p>

35、<p>　　以上這兩個部分組成索引文件的第一行. 接下的內(nèi)容就是索引記錄, 索引記錄的結(jié)構(gòu)如圖4.2:</p><p>　　圖4.2 索引記錄結(jié)構(gòu)</p><p>　　鏈表指針指向同一鏈表的下一個元素, 若為0, 表示此記錄是該哈希鏈表的最后一條記錄. 通過這個區(qū)域, 可以訪問到這個鏈表的所有的記錄. </p><p>　　接下來是索引記錄長度, 由于

36、索引記錄接下的內(nèi)容數(shù)據(jù)長度是不定的, 必須通過這個區(qū)域來確定索引記錄的長度. </p><p>　　鍵是存儲鍵值查找中的鍵值, 這是索引文件的關(guān)鍵部分. </p><p>　　該結(jié)構(gòu)中的兩個分隔符是為了分離各個不定長的區(qū)域. </p><p>　　數(shù)據(jù)記錄的偏移量也是一個由字符組成的指針, 它指向了該記錄中的鍵所對應(yīng)的值, 在數(shù)據(jù)文件中的偏移量, 它和數(shù)據(jù)記錄的長度

37、就能確定數(shù)據(jù)記錄的內(nèi)容了. </p><p>　　數(shù)據(jù)文件的結(jié)構(gòu)比較簡單, 它只是簡單的由一系列數(shù)據(jù)記錄組成. 數(shù)據(jù)記錄的格式如圖4.3:</p><p>　　圖4.3數(shù)據(jù)記錄格式</p><p>　　定位數(shù)據(jù)和確定長度的信息都在索引文件中, 此文件主要負責的就是數(shù)據(jù)的存儲. </p><p>　　以上是對數(shù)據(jù)庫文件結(jié)構(gòu)的大概解釋, 更多細節(jié)

38、將在下文中介紹. </p><p>　　MyDbm的數(shù)據(jù)庫函數(shù)庫接口主要分為兩大類: 數(shù)據(jù)庫連接類和數(shù)據(jù)庫存取類(這里的類是類別, 非面對對象思想中的類). </p><p>　　數(shù)據(jù)庫連接類負責打開和關(guān)閉數(shù)據(jù)庫文件, 其功能不像ADO.NET的DbConnection負責與數(shù)據(jù)庫的通信. 其主要有兩個接口函數(shù)MyDbm_Open和MyDbm_Close. 其功能和c函數(shù)庫中的fopen和

39、fclose類似, 只負責數(shù)據(jù)文件的打開和關(guān)閉. 其實MyDbm_Open和MyDbm_Close只是重新封裝UNIX系統(tǒng)提供文件操作類API的open()和close(). </p><p>　　數(shù)據(jù)庫存取類提供對數(shù)據(jù)的更新, 插入, 檢索, 其對應(yīng)的函數(shù)接口分別是: MyDbm_Update , MyDbm_Insert , MyDbm_Select. 還可以通過MyDbm_Rewind和MyDbm_ Ne

40、xtRrecord來遍歷數(shù)據(jù)庫數(shù)據(jù). 由于采用散列算法, 所以對訪問類型的操作十分的快, 但存儲上則性能將偏低. </p><p>　　應(yīng)用進程通過數(shù)據(jù)庫函數(shù)庫訪問數(shù)據(jù)庫文件的過程如圖4.4:</p><p>　　圖4.4 應(yīng)用進程訪問數(shù)據(jù)庫過程</p><p>　　接下來闡述MyDbm的具體實現(xiàn)細節(jié). </p><p><b>　

41、　具體實現(xiàn)</b></p><p>　　系統(tǒng)首先定義了DBHANDLE類型為void *, DBHANDLE類型表示對數(shù)據(jù)庫的一個有效引用, 用于隔離應(yīng)用程序和數(shù)據(jù)庫的現(xiàn)實細節(jié), 函數(shù)庫對數(shù)據(jù)庫操作都是通過DBHANDLE進行的. </p><p>　　然后是數(shù)據(jù)庫結(jié)構(gòu)DB, 類似于C函數(shù)庫中的文件結(jié)構(gòu). 其中定義了索引文件號和數(shù)據(jù)文件號(UNIX系統(tǒng)訪問文件時, 都會配一個文

42、件號給進程), 索引記錄和數(shù)據(jù)記錄的緩沖區(qū)指針. 還有其它的一些狀態(tài)信息. </p><p>　　下面將通過介紹函數(shù)庫系統(tǒng)的接口函數(shù)來對整個函數(shù)庫做一個具體完整的介紹. 其中每個接口函數(shù)都會調(diào)用函數(shù)庫內(nèi)私有函數(shù)(除函數(shù)庫內(nèi)的函數(shù)外其它程序不能訪問), 私有函數(shù)的函數(shù)名前綴為一個下劃線.</p><p>　　MyDbm_Open</p><p>　　其函數(shù)原型為 DB

43、HANDLE MyDbm_Open(const char *pathName , int oflag , …);</p><p>　　其調(diào)用結(jié)構(gòu)如圖5.1:</p><p>　　圖5.1 MyDbm_Open 調(diào)用結(jié)構(gòu)</p><p>　　MyDbm_Open函數(shù)的參數(shù)與UNIX系統(tǒng)的Open調(diào)用相同. 如果調(diào)用者想要創(chuàng)建數(shù)據(jù)庫文件, 那么可選擇的第三個參數(shù)指

44、定文件權(quán)限. MyDbm_Open函數(shù)打開索引文件和數(shù)據(jù)文件, 在必要時初始化索引文件. 該函數(shù)調(diào)用_MyDbm_Alloc來為DB結(jié)構(gòu)分配空間, 并初始化此結(jié)構(gòu)并為其分配緩存. 調(diào)用者通過pathName參數(shù)指定數(shù)據(jù)庫文件名, 函數(shù)內(nèi)部添加后綴.idx以構(gòu)成數(shù)據(jù)庫索引文件的名字. </p><p>　　如果調(diào)用者要創(chuàng)建數(shù)據(jù)庫文件, 那么使用C函數(shù)庫<stdarg.h>中的可變參數(shù)函數(shù)以找到可選的第三

45、個參數(shù), 然后, 使用UNIX系統(tǒng)調(diào)用open來創(chuàng)建和打開索引文件和數(shù)據(jù)庫文件. 數(shù)據(jù)文件與索引文件的文件名是相同的, 只是后綴為.dat. 在建立數(shù)據(jù)庫的過程中, 函數(shù)會調(diào)用WriteLock(宏定義函數(shù))來數(shù)據(jù)庫文件加鎖. 并在創(chuàng)建結(jié)束后調(diào)用UnLock解鎖. 最后初始化索引文件相關(guān)內(nèi)容, 數(shù)據(jù)庫算創(chuàng)建完成. </p><p>　　如果在打開或創(chuàng)建任一數(shù)據(jù)文件時出錯, 則調(diào)用_MyDbm_Free清除DB結(jié)構(gòu)

46、, 然后對調(diào)用者返回NULL. 如果一切正常工作, 則函數(shù)會調(diào)用MyDbm_Rewind把數(shù)據(jù)庫重置到”起始狀態(tài)”, 將索引文件的文件偏移量定位在索引文件的一條索引記錄(今跟在散列表之后). 最后返回數(shù)據(jù)庫的引用指針. 供調(diào)用者與數(shù)據(jù)庫通信. </p><p>　　MyDbm_Close</p><p>　　其函數(shù)原型為void MyDbm_Close(DBHANDLE handle);&

47、lt;/p><p>　　其很簡單, 就是調(diào)用_MyDbm_Free, MyDbm_Close在這里的作用是作為一個類型轉(zhuǎn)換器, 將DBHANDLE轉(zhuǎn)換為DB結(jié)構(gòu)指針. </p><p>　　MyDbm_Open在打開索引文件和數(shù)據(jù)文件時如果發(fā)生錯誤, 也會調(diào)用MyDbm_Free. 該函數(shù)的作用是釋放所有DB結(jié)構(gòu)所分配到的內(nèi)存緩存, 并關(guān)閉索引和數(shù)據(jù)文件, 如果它們還是處于打開狀態(tài). <

48、/p><p>　　MyDbm_Select</p><p>　　其函數(shù)原型為char * MyDbm_Select(DBHANDLE handle , const char *key);</p><p>　　函數(shù)MyDbm_Select根據(jù)給定的鍵來讀取一條記錄. 它首先調(diào)用_MyDbm_FindAndLock在數(shù)據(jù)庫中查找記錄, 若不能找到記錄, 則將返回NULL值,

49、 由于從_MyDbm_FindAndLock時, 數(shù)據(jù)庫索引文件是加鎖的, 所以要先解鎖, 然后再返回. </p><p>　　如果找到了記錄, 則調(diào)用_MyDBm_ReadDat讀取相應(yīng)的數(shù)據(jù)記錄. 在返回前, 調(diào)用UnLock對索引文件解鎖, 然后, 返回所找到的記錄的指針. </p><p>　　_MyDbm_FindAndLock函數(shù)原型為:</p><p>

50、;　　static int _MyDbm_FindAndLock(DB *db , const char *key , int writelock)</p><p>　　其作用是在函數(shù)庫內(nèi)部用于按給定的鍵查找記錄, 在搜索記錄時, 如果想在索引文件上加一把寫鎖, 則將writelock參數(shù)設(shè)置為非0, 如果將其設(shè)置為0, 則在搜索記錄時, 在索引文件上加讀鎖. </p><p>　　_My

51、Dbm_FindAndLock中準備遍歷散列鏈是, 通過_MyDbm_Hash將鍵變換為散列值, 用其計算在文件中相應(yīng)散列鏈的起始地址. 在遍歷散列鏈前, 等待獲得鎖. 該鎖為細瑣, 只鎖定散列鏈開始處的第1個字節(jié), 這種方式允許多個進程同時搜索不同的散列鏈, 因此增加了并發(fā)性. 然后再while循環(huán)內(nèi)遍歷散列鏈的每一條索引記錄, 并比較鍵. 如果沒有找到記錄則返回-1, 找到數(shù)據(jù)則返回0, 并將相關(guān)信息填入db所指中DB結(jié)構(gòu)中. &l

52、t;/p><p>　　_MyDbm_Hash根據(jù)給定的鍵計算散列值, 它將鍵中的每一個ASCII字符乘以這個字符在字符串中以1開始的索引號, 將這些結(jié)果加起來, 除以散列記錄項數(shù), 將余數(shù)作為這個鍵的散列值. 散列表記錄項通常為素數(shù), 素數(shù)散列通常提供良好的分布特性. </p><p>　　在_MyDbm_FindAndLock循環(huán)內(nèi)遍歷散列鏈的每一條索引記錄時, 會用到兩個內(nèi)部函數(shù)_MyDb

53、m_ReadPtr和_MyDbm_ReadIdx</p><p>　　_MyDbm_ReadPtr函數(shù)讀取以下三種不同鏈表指針中的任意一種:(1)索引文件最開始處指向空閑鏈表中第一條索引記錄的指針；(2) 散列表中指向散列鏈的第一條索引記錄的指針；(3)存放在每條索引記錄開始處、指向下一條記錄的指針(這里的索引記錄既可以處于一條散列鏈中, 也可以處于空閑鏈表中). 返回前, 會將指針從ASCII形式變換為長整型.

54、 </p><p>　　_MyDbm_ReadIdx函數(shù)用于從索引文件的指定編譯量處讀取索引記錄. 如果成功, 該函數(shù)將返回鏈表中下一條記錄的偏移量. 并將相關(guān)信息填入DB結(jié)構(gòu)的許多字段中. </p><p>　　MyDbm_Delete</p><p>　　其函數(shù)原型為int MyDbm_Delete(DBHANDLE handle , const char *k

55、ey);</p><p>　　MyDbm_Delete函數(shù)用于刪除與給定鍵匹配的一條記錄. 首先調(diào)用_MyDbm_FindAndLock判斷在數(shù)據(jù)庫中該記錄是否存在, 如果存在, 則調(diào)用_MyDBm_ DoDelete函數(shù)執(zhí)行刪除該記錄的操作. _MyDbm_FindAndLock的第3個參數(shù)控制對散列鏈是加讀鎖, 還是寫鎖. </p><p>　　_MyDB_DoDelete函數(shù)執(zhí)行從數(shù)

56、據(jù)庫中刪除一條記錄的所有操作. 此函數(shù)的大部分工作僅僅是更新兩個鏈表:空閑鏈表以及與鍵對應(yīng)的散列鏈. 當一條記錄被刪除后, 將其鍵和數(shù)據(jù)記錄設(shè)為空. </p><p>　　在更新空閑鏈表是, 先對空閑鏈表進行加寫鎖, 這樣能防止兩個進程同時刪除不同散列鏈上的記錄時產(chǎn)生相互影響, 因為要將被刪除的記錄移到空閑鏈表上, 這將改變空閑鏈表指針, 而一次只能有一個進程能這樣做. </p><p>

57、　　_MyDBm_DoDelete會調(diào)用函數(shù)_MyDbm_WriteDat清空數(shù)據(jù)記錄, 此時_MyDBm_WriteDat無需對數(shù)據(jù)文件加寫鎖, 因為MyDbm_Delete對這條記錄的散列鏈已經(jīng)加了寫鎖, 這便保證不再會有其他進程能夠讀寫該記錄. </p><p>　　要刪除的記錄通過_MyDbm_WriteDat清空數(shù)據(jù)后, 會將其偏移地址加入到空閑鏈中, 還在其原來的散列鏈中, 其前面的記錄會將指針修改為

58、其后記錄的偏移量, 這樣記錄就被刪除了. </p><p>　　MyDbm_Insert</p><p>　　其函數(shù)原型為int MyDbm_Insert(DBHANDEL handle , const char *key , const char *data );</p><p>　　MyDbm_Insert函數(shù)用于將一條記錄加到數(shù)據(jù)庫中. 首先查明數(shù)據(jù)記錄長度是

59、否有效, 如果無效, 則返回一個出錯狀態(tài). 然后調(diào)用_MyDbm_FindAndLock以查看這個記錄是否已經(jīng)存在. 如果記錄存在(通過比較鍵值), 也將返回一個出錯狀態(tài). 因為MyDbm_Insert要修改散列鏈, 所以用MyDbm_FindAndLock時, 最后一個參數(shù)要指明要對散列鏈加寫鎖. </p><p>　　在調(diào)用_MyDbm_FindAndLock后, 程序分成兩種情況. </p>

60、<p>　　情況一:在調(diào)用_MyDbm_FindFree時, 在空閑鏈表中搜索一條已刪除的記錄, 它的鍵長度和數(shù)據(jù)長度與要添加key和data相同. 這時會將空記錄從空閑鏈表上移下來, 寫入新的索引記錄和數(shù)據(jù)記錄. 然后將新紀錄加到對應(yīng)的散列鏈的鏈首. </p><p>　　情況二:沒有找到對應(yīng)大小的記錄. 這意味著要將這條記錄添加到索引文件和數(shù)據(jù)文件的末尾. 調(diào)用_MyDbm_WriteDat寫數(shù)據(jù)部

61、分,調(diào)用_MyDbm_WriteIdx寫索引部分, 再調(diào)用_MyDbm_WritePtr將新記錄加到對應(yīng)的散列鏈的鏈首. </p><p>　　在正常情況下, 設(shè)置表示成功的返回碼, 然后進入公共返回邏輯. 對散列鏈解鎖(這把鎖是由調(diào)用(MyDbm_FindAndLock而加上的), 然后返回調(diào)用者. </p><p>　　_MyDbm_FindFree函數(shù)試圖找到一個指定大小的空閑索引記

62、錄和相關(guān)的數(shù)據(jù)記錄. _MyDbm_FindFree需要對空閑鏈表加寫鎖以避免與其他使用空閑鏈表的進程戶型干擾. 在對空閑鏈表加寫鎖后, 得到空閑鏈表鏈首的指針地址. </p><p>　　_MyDbm_FindFree會在循環(huán)中遍歷空閑鏈表, 以搜尋一個有匹配鍵長度和數(shù)據(jù)長度的記錄項. 在這個簡單的現(xiàn)實中, 只有當一個已刪除記錄的鍵長度及數(shù)據(jù)長度與要加入的新記錄的鍵長度及數(shù)據(jù)長度一樣時, 才重用已刪除記錄的空間

63、. 其他更好的重用刪除空間的方法一般更復雜. 如果找不到具有所要求的鍵長度和數(shù)據(jù)長度的可用記錄, 則設(shè)置表示失敗的返回碼. 否則, 將已找到的記錄的下一個鏈表指針值寫至前一記錄的鏈表指針, 這樣就從空閑鏈表中移除了該記錄. </p><p>　　一旦結(jié)束對空閑鏈表的操作, 就釋放寫鎖, 然后對調(diào)用者返回狀態(tài)碼. </p><p>　　MyDbm_Update, MyDbm_Rewind和M

64、yDbm_NextRecord</p><p>　　其函數(shù)原型為int MyDbm_Update(DBHANDEL handle , const char *key , const char *data );</p><p>　　MyDbm_Updatet函數(shù)用于將一條記錄按要求更新. 首先查明數(shù)據(jù)記錄長度是否有效, 如果無效, 則返回一個出錯狀態(tài). 然后調(diào)用_MyDbm_FindAndL

65、ock以查看這個記錄是否已經(jīng)存在. 如果記錄不存在(通過比較鍵值), 也將返回一個出錯狀態(tài). 因為MyDbm_Updatet不要修改散列鏈, 所以用MyDbm_FindAndLock時, 最后一個參數(shù)資源只需要加讀鎖. </p><p>　　在調(diào)用_MyDbm_FindAndLock后, 要替換的數(shù)據(jù)存在, 而新數(shù)據(jù)記錄的長度與以存在記錄的長度不一樣. 先調(diào)用_MyDbm_DoDelete將老記錄刪除, 該記錄將

66、放在空閑鏈表的鏈首. 然后, 調(diào)用_MyDbm_WriteDat和_MyDbm_WrtieIdx將新記錄添加到索引文件和數(shù)據(jù)文件的末尾(也可以用其他方法, 如可以再查找是否有數(shù)據(jù)大小正好的以刪除的記錄項). 最后調(diào)用_MyDbm_WritePtr將新記錄加到對應(yīng)的散列鏈的鏈首. </p><p>　　如果要替換的數(shù)據(jù)記錄的長度與已存在的記錄的長度恰好一樣. 這是最容易的情況, 只需要重寫數(shù)據(jù)記錄即可. <

67、/p><p>　　在正常情況下, 設(shè)置表示成功的返回碼, 然后進入公共返回邏輯. 對散列鏈解鎖(這把鎖是由調(diào)用(MyDbm_FindAndLock而加上的), 然后返回調(diào)用者. </p><p>　　MyDbm_Rewind</p><p>　　其函數(shù)原型為 void MyDbm_Rewind(DBHANDLE handle);</p><p>

68、;　　MyDbm_Rewind函數(shù)用于把數(shù)據(jù)庫重置到”起始狀態(tài)”, 將索引文件的文件偏移量定位在索引文件的第一條索引記錄(緊跟在散列表之后). </p><p>　　MyDbm_NextRecord</p><p>　　其函數(shù)原型為 char * MyDbm_NextRecord(DBHANDLE handle , char *key);</p><p>　　MyD

69、bm_NextRecord函數(shù)返回數(shù)據(jù)庫的下一條記錄, 返回值是指向數(shù)據(jù)緩沖的指針. 如果調(diào)用值提供的Key參數(shù)非空, 那么相應(yīng)鍵復制到該緩沖中. 調(diào)用者負責分配可以存放鍵的足夠大的緩沖. 記錄按它們在數(shù)據(jù)庫文件中存放的順序逐一返回. 因此, 記錄并不按鍵值的大小排列. 另外, MyDbm_NextRecord并不跟隨散列鏈表, 所以也可能讀到已刪除的記錄, 只是不向調(diào)用者返回這種以刪除記錄. </p><p>

70、　　以上就是MyDbm數(shù)據(jù)庫對外的接口函數(shù), 在介紹它們的同時, 也附加介紹了它們所依賴的內(nèi)部私有函數(shù). 接下就該數(shù)據(jù)庫函數(shù)庫性能分析. </p><p><b>　　性能分析</b></p><p>　　為了測試這個數(shù)據(jù)庫函數(shù)庫, 也為了獲得一些與典型應(yīng)用的數(shù)據(jù)訪問模式有關(guān)的時間測試數(shù)據(jù), 本文應(yīng)用了[3]中的一個測試程序. 該程序接受兩個命令行參數(shù): 要創(chuàng)建的子進

71、程的個數(shù)以及每個進程向數(shù)據(jù)庫寫的數(shù)據(jù)庫記錄的條數(shù)(records), 然后創(chuàng)建一個空的數(shù)據(jù)庫(通過調(diào)用MyDbm_Open), 通過forks創(chuàng)建指定數(shù)據(jù)的子進程, 并等待所有子進程結(jié)束. 每個子進程執(zhí)行以下步驟:</p><p>　　(1) 向數(shù)據(jù)庫寫records條記錄. </p><p>　　(2) 通過鍵值讀回records條記錄. </p><p>　　(

72、3) 執(zhí)行下面的循環(huán)records*5次.</p><p>　　(a) 每循環(huán)37次, 隨機刪除一條記錄. </p><p>　　(b) 每循環(huán)11次, 添加一條新記錄并讀回這條記錄. </p><p>　　(c) 每循環(huán)17次, 隨機替換一條記錄為新記錄. 在連續(xù)兩次替換中, 一次用同樣大 小的記錄替換, 一次用比以前更長的記錄替換.</p>

73、<p>　　(4) 將此子進程寫的所有記錄刪除. 每刪除一條記錄, 隨機尋找10條記錄.</p><p>　　隨機讀一條記錄. 當records為500時, 每個子進程的較典型的操作數(shù)表6.1. </p><p>　　表6.1 當records為500時, 每個子進程的較典型的操作數(shù)表</p><p>　　讀取的次數(shù)大約是存儲或刪除的10倍, 這可能是許多

74、數(shù)據(jù)庫應(yīng)用程序的典型情況. </p><p>　　每個子進程只對孩子進程所寫的記錄執(zhí)行這些操作(讀取,儲存和刪除). 由于所有的子進程對同一數(shù)據(jù)庫進行操作(雖然對不同的記錄), 所以會使用并發(fā)控制. 數(shù)據(jù)庫中的記錄總條數(shù)與子進程數(shù)成比例增加. (當只有一個子進程時, 一開始有records條記錄寫入數(shù)據(jù)庫, 當有兩個子進程是, 一開始有records*2條記錄寫入數(shù)據(jù)庫, 依次類推. )</p>&

75、lt;p>　　通過運行測試程序來測試三個不同版本的MyDbm函數(shù)庫來比較加粗鎖和加細瑣提供的并發(fā), 并且比較三種不同的加鎖方式(不加鎖, 建議性鎖和強制鎖). 第一個版本加細鎖, 采用本文的源代碼; 第二個版本通過改變加鎖調(diào)用而使用粗鎖; 第三個版本將所有加鎖調(diào)用均去掉, 這樣可以計算加鎖的開銷. </p><p><b>　　單進程的結(jié)果</b></p><p&g

76、t;　　表6.2顯示了只有一個子進程運行時的結(jié)果, records分別為500,1000和2000.</p><p>　　表6.2 單子進程, 不同的records和不同的加鎖方法</p><p>　　最后12列顯示的是以秒為單位的時間. 在所有的情況下, 用戶CPU時間加上系統(tǒng)CPU時間都近似地等于時鐘時間. 這一組測試受CPU限制而不是受磁盤操作限制. </p><

77、p>　　中間6列(建議性鎖)對加粗鎖和加細鎖的結(jié)果基本一樣. 這是可以理解的, 因為對于單個進程來說加粗鎖和加細瑣并沒有區(qū)別. </p><p>　　比較不加鎖和加建議性鎖, 可以看到加鎖調(diào)用在系統(tǒng)CPU時間上增加了2%~31%. 即使這些鎖實際上并沒有使用過(由于只有一個進程). 另外, 注意到用戶CPU時間對于四種不同的加鎖方案基本上一樣, 這是因為用戶代碼基本上是一樣的. </p>&l

78、t;p>　　最后的測試時嘗試有多個子進程的不加鎖的程序. 與預想的一樣, 結(jié)果是隨機的錯誤. 一般情況包括:加入到數(shù)據(jù)庫的記錄找不到, 測試程序異常退出等等. 幾乎每次運行測試程序, 就有不同的錯誤發(fā)生. 這是典型的競爭狀態(tài)—多個進程在沒有任何加鎖的情況下修改同一個文件, 錯誤情況不可預測. </p><p><b>　　多進程的結(jié)果</b></p><p>　

79、　下一組測試主要查看粗鎖和細瑣的不同. 前面說過, 由于加細瑣時數(shù)據(jù)庫的各個部分被其他進程鎖住的時間比加粗鎖少, 所以憑直覺加細瑣應(yīng)該能夠提供更好到并發(fā)性. 表6.3顯示了對nrec取500, 子進程數(shù)目從1到12的測試結(jié)果. </p><p>　　表6.3 records=500時, 不同加鎖方法的比較</p><p>　　所有的用戶時間, 系統(tǒng)時間和時鐘時間的單位均為秒, 所有這些時間

80、均為父進程與所有子進程的總和. </p><p>　　第8列(標志為“△Clock”)是加建議粗鎖與加建議細瑣的時鐘時間的時間差, 從該度量中可以看出使用細瑣得到了多大的并發(fā)度. 在運行測試測試程序的系統(tǒng)上, 當并發(fā)進程數(shù)不多于7時, 加粗鎖與加細瑣的效果大致相當；即使多于7個進程, 使用細瑣的時間減少也不大(一般少于3%). </p><p>　　我們希望從粗鎖到細瑣時鐘時間會減少, 最

81、后也確實如此, 對粗鎖而言, 保持這種鎖的時間比較長, 于是增加了其他進程因這種鎖而阻塞的可能性；而對細瑣而言, 由于加鎖的時間較短, 于是進程為此而阻塞的機會也就比較少. 如果分析運行12個數(shù)據(jù)庫進程的系統(tǒng)行為, 將會看到加粗鎖時的進程切換次數(shù)是加細瑣時的3倍. 這就意味著在使用細瑣時, 進程在鎖上阻塞的機會要少的多. </p><p>　　最后一列是從加建議細瑣到強制細瑣的系統(tǒng)CPU時間的百分比增量. 這與在

82、表6.2看到的強制性鎖顯著增加系統(tǒng)時間是一致的. </p><p><b>　　小結(jié)</b></p><p>　　本文是在dbm數(shù)據(jù)庫函數(shù)庫的基礎(chǔ)上通過添加并發(fā)控制機制, 是dbm能在多進程的環(huán)境下被用戶安全使用. </p><p>　　MyDbm數(shù)據(jù)庫函數(shù)庫數(shù)據(jù)庫采用的是非集中式方式, 加鎖的策略來盡可能的提高數(shù)據(jù)庫函數(shù)并發(fā)性. 從最后的性能

83、分析上也看出了這點. 當然, 運行的進程越多, 其并發(fā)優(yōu)越性更能體現(xiàn). </p><p>　　雖然MyDbm與商業(yè)級別的數(shù)據(jù)相比, 相距甚遠. 但是對于那些輕量級的應(yīng)用完全足夠[11]. 由于其是一種文件數(shù)據(jù)儲存數(shù)據(jù), 采用哈希結(jié)構(gòu)進行連接, 因此與普通文本數(shù)據(jù)庫相比, 具有穩(wěn)定, 檢索速度快和支持量大的優(yōu)點. 由于MyDbm是從Unix系統(tǒng)中移植來的, 因此在UNIX系統(tǒng)中優(yōu)點比較明顯, 加之其多進程訪問能力,

84、 更加發(fā)揮出UNIX環(huán)境的優(yōu)勢. </p><p>　　當然MyDbm也存在一些不足的地方需要改進. 比如重用刪除空間的算法過于簡單呆板, 使刪除空間重用率降低, 可以采用更好的算法提高之.</p><p><b>　　參考文獻</b></p><p>　　(美)W.Richard Stevens, Setphen A Rago. Advanc

85、ed Programming in the UNIX Environment [M]. 人民郵電出版社, 2006: 709-750.</p><p>　　(英)Neil Matthew, Richard Stones著, 楊曉云等譯. Linux程序設(shè)計(第二版) [M]. 機械工業(yè)出版社, 2002:100-120.</p><p>　　薩師煊, 王珊. 數(shù)據(jù)庫系統(tǒng)概論(第四版) [M

86、]. 高等教育出版社, 2006: 1-20.</p><p>　　王珊, 孟小峰. 數(shù)據(jù)庫系統(tǒng)導論(第七版) [M]. 機械工業(yè)出版社, 2000: 50-80.</p><p>　　Abnhrmx Silbersehaa. 數(shù)據(jù)庫系統(tǒng)概念 [M]. 機械工業(yè)出版, 2006: 130-160.</p><p>　　(美)沃爾特, 本-甘, 薩卡. Microso

87、ft SQL Server 2005技術(shù)內(nèi)幕-T-SQL程序設(shè)計 [M]. 北京:電子工業(yè)出版社, 2007: 50-80.</p><p>　　微軟公司著. 熊盛新, 許志慶, 李欽譯. Visual C# .NET語言參考手冊 [M]. 北京:清華大學出版社, 2002年: 160-180.</p><p>　　(美)Kaili Watson . C#2005數(shù)據(jù)庫編程經(jīng)典教程 [M

88、]. 人民郵電出版社, 2007: 90-120.</p><p>　　劉乃麗. 精通ASP.NET2.0+SQLServer 2005項目開發(fā) [M]. 北京:人民郵電出版社, 2007: 100-150.</p><p>　　Craig Hunt. Linux Sendmail Administration (Craig Hunt Linux Library) [M]. Sybex,

89、 2001-2.</p><p>　　歐立奇, 康祥順, 馬煜編著. Visual C# .NET 案例開發(fā)集錦 [M]. 北京:電子工業(yè)出版社, 2006: 233-245.</p><p><b>　　附件</b></p><p>　　以下給出本函數(shù)庫的文件，其中包括MyDbm.h(函數(shù)庫的頭文件), MyDbm.c(函數(shù)庫的實現(xiàn)文件,這里

90、只顯示對外的幾個函數(shù)).</p><p>　　MyDbm.h文件的代碼如下:</p><p>　　#ifndef _MYDBM_H</p><p>　　#define _MYDBM_H</p><p>　　typedef void * DBHANDLE;</p><p>　　DBHANDLE MyDbm_Open(

91、const char *pathName, int oflag, ...);</p><p>　　void MyDbm_Close(DBHANDLE handle);</p><p>　　char *MyDbm_Select(DBHANDLE handle , const char *key);</p><p>　　int MyDbm_

92、Update(DBHANDLE handle , const char *key , const char *data);</p><p>　　int MyDbm_Insert(DBHANDLE handle , const char *key , const char *data);</p><p>　　int MyDbm_Delete(DBHANDLE, con

93、st char *);</p><p>　　void MyDbm_Rewind(DBHANDLE);</p><p>　　char *MyDbm_NextRecord(DBHANDLE, char *);</p><p><b>　　/*</b></p><p><b>　　* 系統(tǒng)限制<

94、;/b></p><p><b>　　*/</b></p><p>　　#define IDXLEN_MIN 6 /* key, sep, start, sep, length, \n */</p><p>　　#define IDXLEN_MAX 1024 /* arbitrary */</p>&l

95、t;p>　　#define DATLEN_MIN 2 /* data byte, newline */</p><p>　　#define DATLEN_MAX 1024 /* arbitrary */</p><p><b>　　/*</b></p><p>　　* 鎖函數(shù)和在其基礎(chǔ)上構(gòu)建的各種宏</p>

96、;<p><b>　　*/</b></p><p>　　int lock_reg(int, int, int, off_t, int, off_t);</p><p>　　#define read_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETL

97、K, F_RDLCK, (offset), (whence), (len))</p><p>　　#define readw_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLKW, F_RDLCK, (offset), (whence), (len))</p><p>　　#define

98、write_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLK, F_WRLCK, (offset), (whence), (len))</p><p>　　#define writew_lock(fd, offset, whence, len) \</p><p>　　lock_reg(

99、(fd), F_SETLKW, F_WRLCK, (offset), (whence), (len))</p><p>　　#define un_lock(fd, offset, whence, len) \</p><p>　　lock_reg((fd), F_SETLK, F_UNLCK, (offset), (whence), (len))</p><p>　

100、　#endif /* MyDbm_H */</p><p>　　MyDbm.c的文件如下：</p><p>　　#include "MyDbm.h"</p><p>　　#include <stdio.h></p><p>　　#include <unistd.h></p><p

101、>　　#include <fcntl.h></p><p>　　#include <stdarg.h></p><p>　　#include <errno.h></p><p>　　#include <sys/uio.h></p><p><b>　　/*</b>&l

102、t;/p><p><b>　　* 符號定義</b></p><p>　　* 這些定義的符號將用在索引文件和數(shù)據(jù)文件中</p><p><b>　　*/</b></p><p>　　#define IDXLEN_SZ 4 /* 索引指針長度 */</p><p>　

103、　#define SEP ':' /* 索引記錄分隔符 */</p><p>　　#define SPACE ' ' /* 空格符 */</p><p>　　#define NEWLINE '\n' /* 換行符 */</p><p><b>　　/*

104、</b></p><p>　　*哈希鏈和空閑鏈表的定義</p><p><b>　　*/</b></p><p>　　#define PTR_SZ 6 /* 鏈指針長度*/</p><p>　　#define PTR_MAX 999999 /* 最大文件位移10

105、的PTR_SZ次-1 */</p><p>　　#define NHASH_DEF 137 /* 默認的哈希數(shù)組長度 */</p><p>　　#define FREE_OFF 0 /* 空閑指針域的文件位移 */</p><p>　　#define HASH_OFF PTR_SZ /* 哈希表在索引文件

106、的位移 */</p><p>　　typedef unsigned long DBHASH; /* 哈希表類型*/</p><p>　　typedef unsigned long COUNT; /* 計數(shù)器類型*/</p><p><b>　　/*</b></p><p>　　* 數(shù)據(jù)庫描述符，類似文件描述符&

107、lt;/p><p><b>　　*/</b></p><p>　　typedef struct {</p><p>　　int idxfd; /* 索引文件文件描述符 */</p><p>　　int datfd; /* 數(shù)據(jù)文件文件描述符 */</p><p>　　char *id

108、xbuf; /* 索引記錄緩沖 */</p><p>　　char *datbuf; /* 數(shù)據(jù)記錄緩沖 */</p><p>　　char *name; /* 打開的數(shù)據(jù)庫名 */</p><p>　　off_t idxoff; /* 索引記錄在索引文件的位移*/</p><p>　　size_t idxlen; /* 索引記錄長

109、度 */</p><p>　　off_t datoff; /* 數(shù)據(jù)記錄在數(shù)據(jù)文件的位移*/</p><p>　　size_t datlen; /* 數(shù)據(jù)記錄長度 */</p><p>　　off_t ptrval; /* 索引項的內(nèi)容 */</p><p>　　off_t ptroff; /* 索引指針的值 */</p>

110、<p>　　off_t chainoff; /* 索引記錄所在哈希鏈的位移*/</p><p>　　off_t hashoff; /* 哈希表在索引文件的位移*/</p><p>　　DBHASH nhash; /* 當前數(shù)據(jù)庫的哈希表大小 */</p><p><b>　　} DB;</b></p>&l

111、t;p><b>　　/*</b></p><p><b>　　* 內(nèi)部私有函數(shù)</b></p><p><b>　　*/</b></p><p>　　static DB *_MyDbm_Alloc(int);</p><p>　　static void _M

112、yDbm_DoDelete(DB *);</p><p>　　static int _MyDbm_FindAndLock(DB *, const char *, int);</p><p>　　static int _MyDbm_Findfree(DB *, int, int);</p><p>　　static void _MyDbm_Fre