?? 16.htm
字號(hào):
<p>off_t offset, int whence, off_t ptrval) </p>
<p>{ </p>
<p>struct iovec iov[2]; </p>
<p>char asciiptrlen[PTR_SZ + IDXLEN_SZ +1]; </p>
<p>int len; </p>
<p>if ( (db->ptrval = ptrval) < 0 || ptrval > PTR_MAX) </p>
<p>err_quit("invalid ptr: %d", ptrval); </p>
<p>sprintf(db->idxbuf, "%s%c%d%c%d\n", </p>
<p>key, SEP, db->datoff, SEP, db->datlen); </p>
<p>if ( (len = strlen(db->idxbuf)) < IDXLEN_MIN || len > IDXLEN_MAX) </p>
<p>err_dump("invalid length"); </p>
<p>sprintf(asciiptrlen, "%*d%*d", PTR_SZ, ptrval, IDXLEN_SZ, len); </p>
<p>/* If we're appending, we have to lock before doing the lseek() </p>
<p>and write() to make the two an atomic operation. If we're </p>
<p>overwriting an existing record, we don't have to lock. */ </p>
<p>if (whence == SEEK_END) /* we're appending */ </p>
<p>if (writew_lock(db->idxfd, ((db->nhash+1)*PTR_SZ)+1, </p>
<p>SEEK_SET, 0) < 0) </p>
<p>err_dump("writew_lock error"); </p>
<p>/* Position the index file and record the offset */ </p>
<p>if ( (db->idxoff = lseek(db->idxfd, offset, whence)) == -1) </p>
<p>err_dump("lseek error"); </p>
<p>iov[0].iov_base = asciiptrlen; </p>
<p>iov[0].iov_len = PTR_SZ + IDXLEN_SZ; </p>
<p>iov[1].iov_base = db->idxbuf; </p>
<p>iov[1].iov_len = len; </p>
<p>if (writev(db->idxfd, &iov[0], 2) != PTR_SZ + IDXLEN_SZ + len) </p>
<p>err_dump("writev error of index record"); </p>
<p>if (whence == SEEK_END) </p>
<p>if (un_lock(db->idxfd, ((db->nhash+1)*PTR_SZ)+1, SEEK_SET, 0) < 0) </p>
<p>err_dump("un_lock error"); </p>
<p>} </p>
<p>程序16.16 _db_writeidx函數(shù) </p>
<p>_db_dodelete調(diào)用的最后一個(gè)函數(shù)是_db_writeptr（程序16.17）。它被調(diào)用 </p>
<p>兩次--一次用來(lái)寫空閑鏈表指針，一次用來(lái)寫Hash鏈表指針（指向被刪除索引記錄
</p>
<p>的指針）。 </p>
<p>#include "db.h" </p>
<p>/* Write a chain ptr field somewhere in the index file: </p>
<p>* the free list, the hash table, or in an index record. */ </p>
<p>void </p>
<p>_db_writeptr(DB *db, off_t offset, off_t ptrval) </p>
<p>{ </p>
<p>char asciiptr[PTR_SZ + 1]; </p>
<p>if (ptrval < 0 || ptrval > PTR_MAX) </p>
<p>err_quit("invalid ptr: %d", ptrval); </p>
<p>sprintf(asciiptr, "%*d", PTR_SZ, ptrval); </p>
<p>if (lseek(db->idxfd, offset, SEEK_SET) == -1) </p>
<p>err_dump("lseek error to ptr field"); </p>
<p>if (write(db->idxfd, asciiptr, PTR_SZ) != PTR_SZ) </p>
<p>err_dump("write error of ptr field"); </p>
<p>} </p>
<p>程序16.17 _db_writeptr函數(shù) </p>
<p>在程序16.18中列出了我們最長(zhǎng)的數(shù)據(jù)庫(kù)函數(shù)db_store。它從調(diào)用_db_find開(kāi)
</p>
<p>始，以查看這個(gè)記錄是否存在。如果記錄存在且標(biāo)志為DB_REPLACE，或記錄不存在
</p>
<p>且標(biāo)志為DB_INSERT，這些都是允許的。替換一條已存在的記錄，指的是該記錄的
</p>
<p>主鍵一樣，而數(shù)據(jù)很可能不一樣。 </p>
<p>注意到因?yàn)閐b_store可能會(huì)改變Hash鏈，所以調(diào)用_db_find的最后一條參數(shù)說(shuō)
</p>
<p>明要對(duì)Hash鏈加寫鎖。 </p>
<p>如果我們要加一條新記錄到數(shù)據(jù)庫(kù)，我們調(diào)用函數(shù)_db_findfree（程序16.19
</p>
<p>）在空閑鏈表中搜索一個(gè)有同樣主鍵大小和同樣數(shù)據(jù)大小的已刪除的記錄。
</p>
<p>_db_findfree中的while循環(huán)遍歷空閑鏈表以搜尋一個(gè)有對(duì)應(yīng)主鍵大小和數(shù)據(jù)
</p>
<p>大小的索引記錄項(xiàng)。在我們這個(gè)簡(jiǎn)單的實(shí)現(xiàn)中，只有當(dāng)一個(gè)已刪除記錄的的主鍵大
</p>
<p>小及數(shù)據(jù)大小與新加入的記錄的主鍵大小及數(shù)據(jù)大小一樣時(shí)才重用已刪除的記錄的
</p>
<p>空間。其它更好的算法一般更復(fù)雜。 </p>
<p>_db_findfree需要對(duì)空閑鏈表加寫鎖以避免與其它使用空閑鏈表的進(jìn)程互相影
</p>
<p>響。當(dāng)一條記錄從空閑鏈表上取下來(lái)后，就可以打開(kāi)這個(gè)寫鎖。_db_dodelete也要
</p>
<p>修改空閑鏈表。 </p>
<p>#include "db.h" </p>
<p>/* Store a record in the database. </p>
<p>* Return 0 if OK, 1 if record exists and DB_INSERT specified, </p>
<p>* -1 if record doesn't exist and DB_REPLACE specified. */ </p>
<p>int </p>
<p>db_store(DB *db, const char *key, const char *data, int flag) </p>
<p>{ </p>
<p>/* An empty record of the correct size was not found. </p>
<p>We have to append the new record to the ends of </p>
<p>the index and data files */ </p>
<p>_db_writedat(db, data, 0, SEEK_END); </p>
<p>_db_writeidx(db, key, 0, SEEK_END, ptrval); </p>
<p>/* db->idxoff was set by _db_writeidx(). The new </p>
<p>record goes to the front of the hash chain. */ </p>
<p>_db_writeptr(db, db->chainoff, db->idxoff); </p>
<p>db->cnt_stor1++; </p>
<p>} else { </p>
<p>/* We can reuse an empty record. </p>
<p>_db_findfree() removed the record from the free </p>
<p>list and set both db->datoff and db->idxoff. */ </p>
<p>_db_writedat(db, data, db->datoff, SEEK_SET); </p>
<p>_db_writeidx(db, key, db->idxoff, SEEK_SET, ptrval); </p>
<p>/* reused record goes to the front of the hash chain. */ </p>
<p>_db_writeptr(db, db->chainoff, db->idxoff); </p>
<p>db->cnt_stor2++; </p>
<p>} </p>
<p>} else { /* record found */ </p>
<p>if (flag & DB_INSERT) { </p>
<p>rc = 1; </p>
<p>db->cnt_storerr++; </p>
<p>goto doreturn; /* error, record already in db */ </p>
<p>} </p>
<p>/* We are replacing an existing record. We know the new </p>
<p>key equals the existing key, but we need to check if </p>
<p>the data records are the same size. */ </p>
<p>if (datlen != db->datlen) { </p>
<p>_db_dodelete(db); /* delete the existing record */ </p>
<p>/* Reread the chain ptr in the hash table </p>
<p>(it may change with the deletion). */ </p>
<p>ptrval = _db_readptr(db, db->chainoff); </p>
<p>/* append new index and data records to end of files */ </p>
<p>_db_writedat(db, data, 0, SEEK_END); </p>
<p>_db_writeidx(db, key, 0, SEEK_END, ptrval); </p>
<p>/* new record goes to the front of the hash chain. */ </p>
<p>_db_writeptr(db, db->chainoff, db->idxoff); </p>
<p>db->cnt_stor3++; </p>
<p>} else { </p>
<p>/* same size data, just replace data record */ </p>
<p>_db_writedat(db, data, db->datoff, SEEK_SET); </p>
<p>db->cnt_stor4++; </p>
<p>} </p>
<p>} </p>
<p>rc = 0; /* OK */ </p>
<p>doreturn: /* unlock the hash chain that _db_find() locked */ </p>
<p>if (un_lock(db->idxfd, db->chainoff, SEEK_SET, 1) < 0) </p>
<p>err_dump("un_lock error"); </p>
<p>return(rc); </p>
<p>} </p>
<p>程序16.18 db_store函數(shù) </p>
<p>#include "db.h" </p>
<p>/* Try to find a free index record and accompanying data record </p>
<p>* of the correct sizes. We're only called by db_store(). */ </p>
<p>int </p>
<p>_db_findfree(DB *db, int keylen, int datlen) </p>
<p>{ </p>
<p>int rc; </p>
<p>off_t offset, nextoffset, saveoffset; </p>
<p>/* Lock the free list */ </p>
<p>if (writew_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0) </p>
<p>err_dump("writew_lock error"); </p>
<p>/* Read the free list pointer */ </p>
<p>saveoffset = FREE_OFF; </p>
<p>offset = _db_readptr(db, saveoffset); </p>
<p>while (offset != 0) { </p>
<p>nextoffset = _db_readidx(db, offset); </p>
<p>if (strlen(db->idxbuf) == keylen && db->datlen == datlen) </p>
<p>break; /* found a match */ </p>
<p>saveoffset = offset; </p>
<p>offset = nextoffset; </p>
<p>} </p>
<p>if (offset == 0) </p>
<p>rc = -1; /* no match found */ </p>
<p>else { </p>
<p>/* Found a free record with matching sizes. </p>
<p>The index record was read in by _db_readidx() above, </p>
<p>which sets db->ptrval. Also, saveoffset points to </p>
<p>the chain ptr that pointed to this empty record on </p>
<p>the free list. We set this chain ptr to db->ptrval, </p>
<p>which removes the empty record from the free list. */ </p>
<p>_db_writeptr(db, saveoffset, db->ptrval); </p>
<p>rc = 0; </p>
<p>/* Notice also that _db_readidx() set both db->idxoff </p>
<p>and db->datoff. This is used by the caller, db_store(), </p>
<p>to write the new index record and data record. */ </p>
<p>} </p>
<p>/* Unlock the free list */ </p>
<p>if (un_lock(db->idxfd, FREE_OFF, SEEK_SET, 1) < 0) </p>
<p>err_dump("un_lock error"); </p>
<p>return(rc); </p>
<p>} </p>
<p>程序16.19 _db_findfree函數(shù) </p>
<p>回到函數(shù)db_store，在調(diào)用_db_find后，有四種可能： </p>
<p>1. 加入一條新的記錄，而_db_findfree沒(méi)有找到對(duì)應(yīng)大小的空閑記錄。這意味著
</p>
<p>我們要將這條新記錄添加到索引文件和數(shù)據(jù)文件的末尾。通過(guò)調(diào)用_db_writeptr將
</p>
<p>新記錄加到對(duì)應(yīng)的Hash鏈的鏈?zhǔn)住?</p>
<p>2. 加入一條新的記錄，且_db_findfree找到對(duì)應(yīng)大小的空閑記錄。這條空閑記錄
</p>
<p>被_db_findfree從空閑鏈表上移下來(lái)，新的索引記錄和數(shù)據(jù)記錄被寫入，然后通過(guò)
</p>
<p>調(diào)用_db_writeptr將新記錄加到對(duì)應(yīng)的Hash鏈的鏈?zhǔn)住?</p>
<p>3.
要替換一條記錄，而新數(shù)據(jù)記錄的長(zhǎng)度與已存在的記錄的長(zhǎng)度不一樣。我們調(diào)
</p>
<p>用_db_dodelete將老記錄刪除，然后將新記錄添加到索引文件和數(shù)據(jù)文件的末尾（
</p>
<p>也可以用其他方法，如我們可以再找一找是否有適當(dāng)大小的已刪除的記錄項(xiàng)）。最
</p>
<p>后調(diào)用_db_writeptr將新記錄加到對(duì)應(yīng)的Hash鏈的鏈?zhǔn)住?</p>
<p>4.
要替換一條記錄，而新數(shù)據(jù)記錄的長(zhǎng)度與已存在的記錄的長(zhǎng)度恰好一樣。這是
</p>
<p>最容易的情況，我們只需要重寫記錄即可。 </p>
<p>在向文件的末尾添加索引記錄或數(shù)據(jù)記錄時(shí)，需要加鎖（回憶我們?cè)诔绦?2.
</p>
<p>6中遇到的相對(duì)文件尾加鎖問(wèn)題）。在上面四種可能的第1和第3種情況，db_store
</p>
<p>調(diào)用_db_writeidx和_db_writedat時(shí)，第3個(gè)參數(shù)為0，第4個(gè)參數(shù)為SEEK_END。這
</p>
<p>里，第4個(gè)參數(shù)作為一個(gè)標(biāo)志用來(lái)告訴這兩個(gè)函數(shù)，新的記錄將被添加到文件的末
</p>
<p>尾。_db_writeidx用到的技術(shù)是對(duì)索引文件加寫鎖，加鎖的范圍從Hash鏈的末尾到
</p>
<p>文件的末尾。這不會(huì)影響其他數(shù)據(jù)庫(kù)的讀用戶和寫用戶（這些用戶將對(duì)Hash鏈加鎖
</p>
<p>），但如果其他用戶此時(shí)調(diào)用db_store來(lái)添加數(shù)據(jù)則會(huì)被鎖住。_db_writedat使用
</p>
<p>的方法是對(duì)整個(gè)數(shù)據(jù)文件加寫鎖。同樣這也不會(huì)影響其他數(shù)據(jù)庫(kù)的讀用戶和寫用戶
</p>
<p>（它們甚至不對(duì)數(shù)據(jù)文件加鎖），但如果其他用戶此時(shí)調(diào)用db_store來(lái)向數(shù)據(jù)文件
</p>
<p>添加數(shù)據(jù)則會(huì)被鎖住（見(jiàn)Exercise 16.3）。 </p>
<p>最后兩個(gè)函數(shù)是db_nextrec和db_rewind，這兩個(gè)函數(shù)用來(lái)讀取數(shù)據(jù)庫(kù)的所有
</p>
<p>記錄。通常在下列形式的循環(huán)中的使用這兩個(gè)函數(shù)： </p>
<p>db_rewind(db) ; </p>
<p>while( (ptr = db_nextrec(db, key)) != NULL) { </p>
<p>/* process record */ </p>
<p>} </p>
<p>我們前面警告過(guò)，這里記錄的返回沒(méi)有一定的次序--它們并不按主鍵的順序。
</p>
<p>函數(shù)db_rewind（程序16.20）將索引文件定位在第一條索引記錄（緊跟在Has
</p>
<p>h表后面）。 </p>
<p>#include "db.h" </p>
<p>/* Rewind the index file for db_nextrec(). </p>
<p>* Automatically called by db_open(). </p>
<p>* Must be called before first db_nextrec(). </p>
<p>*/ </p>
<p>void </p>
<p>db_rewind(DB *db) </p>
<p>{ </p>
<p>off_t offset; </p>
<p>offset = (db->nhash + 1) * PTR_SZ; /* +1 for free list ptr */ </p>
<p>/* We're just setting the file offset for this process </p>
<p>to the start of the index records; no need to lock. </p>
<p>+1 below for?? 快捷鍵說(shuō)明
復(fù)制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號(hào)
Ctrl + =
減小字號(hào)
Ctrl + -