隊(duì)列（Queue）是一種很常用的數(shù)據(jù)結(jié)構(gòu)。之前我都是在運(yùn)行內(nèi)存中使用這種數(shù)據(jù)結(jié)構(gòu)司顿。但是如果需要一個(gè)可以持久化的隊(duì)列緩存芒粹，僅僅是使用內(nèi)存中的隊(duì)列數(shù)據(jù)結(jié)構(gòu)就不行了，因?yàn)楹?jiǎn)單對(duì)隊(duì)列對(duì)象進(jìn)行序列化和反序列化處理免猾，又顯的不夠高效是辕，所以就考慮到使用文件系統(tǒng)（File System）來實(shí)現(xiàn)一個(gè)隊(duì)列數(shù)據(jù)結(jié)構(gòu)。
1. 基本需求
- 要滿足隊(duì)列最基本的特征：“先進(jìn)先出”（FIFO）以及一些標(biāo)準(zhǔn)的操作
- 隊(duì)列中的元素可以是任意數(shù)據(jù)類型
- 可以隨時(shí)對(duì)隊(duì)列中數(shù)據(jù)進(jìn)行讀取和寫入
2. 實(shí)現(xiàn)思路
我查閱的一些資料后猎提，發(fā)現(xiàn)了一個(gè) Java 版的實(shí)現(xiàn) 基本可以滿足需求获三。因?yàn)槲乙?iOS 中使用這個(gè)隊(duì)列，所以要用 Objective-C 改寫一下锨苏。在改寫完成下面把使用文件系統(tǒng)實(shí)現(xiàn)隊(duì)列的基本思路和要點(diǎn)記錄下來疙教，這樣以后用其他語言也都能實(shí)現(xiàn)了。
先介紹一下文件結(jié)構(gòu)：
隊(duì)列文件結(jié)構(gòu)：頭文件 + 數(shù)據(jù)段（包含很多個(gè)元素）伞租。
元素文件結(jié)構(gòu)：元素頭文件 + 元素?cái)?shù)據(jù)段贞谓。
2.1 隊(duì)列文件的頭文件
這個(gè)頭文件是用來描述整個(gè)隊(duì)列，我們需要定義以下這些值：
- 文件長(zhǎng)度葵诈，用于在新插入一個(gè)元素時(shí)裸弦，判斷是否需要增加這個(gè)文件的長(zhǎng)度
- 元素個(gè)數(shù)，方便的實(shí)現(xiàn)查詢隊(duì)列中元素個(gè)數(shù)
- 第一個(gè)元素?cái)?shù)據(jù)段開始位置作喘，用于實(shí)現(xiàn)
peek操作 - 最后一個(gè)元素?cái)?shù)據(jù)段的開始理疙，用于實(shí)現(xiàn)
Add操作
這幾個(gè)數(shù)據(jù)都是int 類型，這樣頭文件就是固定長(zhǎng)度泞坦。在讀取文件時(shí)窖贤，在固定位置就能讀到相應(yīng)的值。
代碼：
-(void)readFileHeader
{
[self.fh seekToFileOffset:0];
NSData *data = [self.fh readDataOfLength:HEADER_LENGTH];
self.headBuffer = [NSMutableData dataWithData:data];
self.fileLength = [self readInt:self.headBuffer Offset:0];
self.elementCount = [self readInt:self.headBuffer Offset:4];
int firstPos = [self readInt:self.headBuffer Offset:8];
self.first = [self readElement:firstPos];
int lastPos = [self readInt:self.headBuffer Offset:12];
self.last = [self readElement:lastPos];
}
2.2 元素頭文件
描述元素本身的頭文件包括的數(shù)據(jù)有：
- 元素自身開始的位置
- 元素?cái)?shù)據(jù)長(zhǎng)度
就像這樣：
typedef struct
{
int position;
int length;
}QueueElement;
由于頭文件長(zhǎng)度固定贰锁，通過這兩個(gè)文件就可以讀取到這個(gè)元素的數(shù)據(jù)赃梧，已及下一元素開始的位置。
2.3 實(shí)現(xiàn) Peek 操作
Peek 操作就是讀取隊(duì)列中的第一個(gè)元素豌熄。由于在隊(duì)列頭文件中保存了第一個(gè)元素?cái)?shù)據(jù)的段的開始位置授嘀。再加上元素頭文件的信息，我們就可以順利讀出第一個(gè)元素房轿。
第一個(gè)元素的數(shù)據(jù)開始的位置 = 第一個(gè)元素開始的位置 + 元素頭文件長(zhǎng)度粤攒。
再加上已知數(shù)據(jù)的長(zhǎng)度所森，這樣的就可以順利讀出數(shù)據(jù)了。如果數(shù)據(jù)只是增加夯接，也就是文件長(zhǎng)度一值在增長(zhǎng)焕济，這種讀取方式就夠了。但是盔几，實(shí)際情況是晴弃，有可能我們會(huì)移除隊(duì)列中的元素，為能夠重復(fù)利用空間逊拍，新加入的元素可能會(huì)利用到已刪除元素的空間上鞠，所以在讀取的時(shí)候也要考慮到這種情況，這就是環(huán)形讀刃旧ァ（ring read）芍阎。
2.2.1 環(huán)形讀取
第一種情況：當(dāng)元素?cái)?shù)據(jù)段開始位置加上元素?cái)?shù)據(jù)段長(zhǎng)度小于隊(duì)列文件長(zhǎng)度，只需要正常讀取缨恒。
第二種情況谴咸，當(dāng)元素?cái)?shù)據(jù)段開始位置加上元素?cái)?shù)據(jù)段長(zhǎng)度大于隊(duì)列文件長(zhǎng)度，這就說明骗露，數(shù)據(jù)段并沒有完全寫在文件物理位置的尾端岭佳，而是可能還有一部分寫在的物理位置的前端，所以在讀取時(shí)需要考慮到這兩部分的數(shù)據(jù)萧锉。
代碼：
-(NSData *)ringRead:(int)startPos DataLength:(int)dLength
{
startPos = [self wrapPosition:startPos];
if (startPos + dLength <= self.fileLength)
{
[self.fh seekToFileOffset:startPos];
NSData *data = [self.fh readDataOfLength:dLength];
return data;
}
else
{
int countBeforeEOF = self.fileLength - startPos;
[self.fh seekToFileOffset:startPos];
NSData *beforeDataRead = [self.fh readDataOfLength:countBeforeEOF];//讀取尾端數(shù)據(jù)
NSMutableData *readData = [NSMutableData dataWithData:beforeDataRead];
int countAfterEOF = dLength - countBeforeEOF;
[self.fh seekToFileOffset:HEADER_LENGTH];
NSData *afterDataRead = [self.fh readDataOfLength:countAfterEOF];//讀取前端數(shù)據(jù)
[readData appendData:afterDataRead];
return readData;
}
}
2.4 實(shí)現(xiàn) Add 操作
向隊(duì)列中添加一個(gè)元素珊随，這個(gè)元素需要添加在當(dāng)前最后一個(gè)元素的后面，同樣考慮到重復(fù)利用空間的問題柿隙，我們需要考慮環(huán)形寫入（ring write）叶洞。
2.4.1 環(huán)形寫入
第一種情況：當(dāng)需要寫入的元素?cái)?shù)據(jù)段開始位置加上元素?cái)?shù)據(jù)段長(zhǎng)度小于隊(duì)列文件長(zhǎng)度，直接從最后一個(gè)元素的尾端開始寫入就行禀崖。
第二種情況：當(dāng)需要寫入的元素?cái)?shù)據(jù)段開始位置加上元素?cái)?shù)據(jù)段長(zhǎng)度小于隊(duì)列文件長(zhǎng)度京办，這時(shí)就需要考慮當(dāng)前文件空閑空間的大小，如果空閑空間足夠帆焕，利用空閑空間進(jìn)行寫入，如果空間不夠就把文件長(zhǎng)度加大到足夠大再進(jìn)行寫入不恭。
代碼：
-(void)ringWrite:(int)startPos DataToWrite:(NSData *)data
{
startPos = [self wrapPosition:startPos];
if (startPos + [data length] <= self.fileLength)
{
[self.fh seekToFileOffset:startPos];
[self.fh writeData:data];
[self.fh synchronizeFile];
}
else
{
int countBeforeEOF = self.fileLength - startPos;
NSData *beforeDataToWrite
= [data subdataWithRange:NSMakeRange(0, countBeforeEOF)];
[self.fh seekToFileOffset:startPos];
[self.fh writeData:beforeDataToWrite];
int countAfterEOF = (int)([data length] - countBeforeEOF);
NSData *afterDataToWrite
= [data subdataWithRange:NSMakeRange(countBeforeEOF, countAfterEOF)];
[self.fh seekToFileOffset:HEADER_LENGTH];
[self.fh writeData:afterDataToWrite];
[self.fh synchronizeFile];
}
}
在增加文件長(zhǎng)度的時(shí)候叶雹，為保障在寫入文件時(shí)數(shù)據(jù)正確，就要使最后一個(gè)元素后有足夠的連續(xù)空間换吧，這樣就需要把元素在物理上從前到后進(jìn)行連續(xù)排列折晦。
代碼：
-(void)expandFileLengthIfNecessary:(int)dataLength
{
int lengthToWrite = ELEMENT_HEADER_LENGTH + dataLength;
int remainLength = [self getRemainLengthInFile];
if (remainLength >= lengthToWrite)
{
return;
}
else
{
NSLog(@"Expand!");
int previousLength = self.fileLength;
int newLength;
do
{
remainLength += previousLength;
newLength = previousLength << 1;
previousLength = newLength;
} while (remainLength < lengthToWrite);
[self.fh truncateFileAtOffset:newLength]; //增加文件長(zhǎng)度
[self.fh seekToFileOffset:0];
// If the buffer is split, we need to make it contiguous. //保證空間連續(xù)性，對(duì)空間元素進(jìn)行物理上的排序
if(self.last.position < self.first.position)
{
[self.fh seekToFileOffset:0];
NSData *fileData = [self.fh readDataToEndOfFile];
NSMutableData *newFileData = [NSMutableData dataWithData:fileData];
int moveLength = (self.last.position + ELEMENT_HEADER_LENGTH + self.last.length) - HEADER_LENGTH;
NSData *dataToMove = [newFileData subdataWithRange:NSMakeRange(HEADER_LENGTH, moveLength)];
[newFileData replaceBytesInRange:NSMakeRange(self.fileLength, moveLength) withBytes:[dataToMove bytes]];
[self.fh writeData:newFileData];
int newLastElementPos = self.fileLength + self.last.position - HEADER_LENGTH;
QueueElement newLastElement;
newLastElement.position = newLastElementPos;
newLastElement.length = self.last.length;
self.last = newLastElement;
}
self.fileLength = newLength;
[self writeFileHeader:self.fileLength ElementCount:self.elementCount
FirstPos:self.first.position LastPos:self.last.position];
}
}
2.5 其他操作
其他操作無非就是對(duì)頭文件的更新和讀取沾瓦，在這里就不詳細(xì)描述了满着，具體代碼可以查看項(xiàng)目中的代碼谦炒。
3. 總結(jié)
總結(jié)下來使用文件系統(tǒng)實(shí)現(xiàn)這隊(duì)列的要點(diǎn)有這么幾個(gè)：
- 隊(duì)列數(shù)據(jù)結(jié)構(gòu)的特征
- 頭文件的定義
- 環(huán)形讀取和寫入
- 保持空間的連續(xù)性
