當(dāng)前位置:首頁 > 芯聞號 > 充電吧
[導(dǎo)讀]一.原理先看一個例子,我們?yōu)闀陮懸粋€管理圖書的程序,書店里有許多書Book,每個書架(BookShelf)上有多本書。類結(jié)構(gòu)如下所示:class?Book?{ private: ?string?bo

一.原理

先看一個例子,我們?yōu)闀陮懸粋€管理圖書的程序,書店里有許多書Book,每個書架(BookShelf)上有多本書。
類結(jié)構(gòu)如下所示:

class?Book?{
private:
?string?book_name_;
};
class?Shelf?{
?private:
??vectorbooks_;
};

如何遍歷書架上所有的書呢?一種實現(xiàn)方法是:

vector&?GetBooks()?const?{
??return?books_;
}

這樣的實現(xiàn)暴漏了內(nèi)部太多的細節(jié),調(diào)用者根本就不需要知道Shelf存儲Book的方式,僅僅需要遍歷所有的數(shù)據(jù)即可。而且這樣當(dāng)我們換用另外一種數(shù)據(jù)結(jié)構(gòu)存儲Book時,客戶端的代碼就需要進行修改。但是如果使用Iterator模式則沒有這個問題。

具體的我們需要遍歷書店中所有的書,現(xiàn)在應(yīng)該如何實現(xiàn)呢?
一種實現(xiàn)方式是,由BookStore負責(zé)保存中間狀態(tài),包括當(dāng)前遍歷到了哪個書架,遍歷到了書架上的哪本書。

class?BookStore?{
?Iterator*?NewIterator()?const;
?private:
??vectorshelf_;
??vector::iterator?shelf_iter_;
??vector::iterator?book_iter_;
};

這種實現(xiàn)方法對外是干凈的,但是對于BookStore的維護者來說卻是不友好的,Iterator的中間狀態(tài)不是BookStore的成員,邏輯上不應(yīng)該由BookStore維護。而且當(dāng)兩個甚至多個用戶同時遍歷書店時BookStore得同時維護多個中間狀態(tài),極其容易出錯。更好的一種實現(xiàn)方式是,把遍歷Iterator相關(guān)的代碼和狀態(tài)封裝成一個類,有兩個層級Shelf 和 Book,這個類的名字我們叫做TwoLevelIteator。

在雙層迭代器中,level1中的迭代器指向的是一個容器,level2中的迭代器才指向真正的元素。對應(yīng)到書店,level1指向書架(對圖書進行分類),level2指向圖書。當(dāng)要查找某本書時,先要定位到書架,再在該書架中根據(jù)書的編號找到具體的書。


二.LevelDB中的實現(xiàn)

1.頭文件


class?TwoLevelIterator:?public?Iterator?{
?public:
??TwoLevelIterator(
????Iterator*?index_iter,
????BlockFunction?block_function,
????void*?arg,
????const?ReadOptions&?options);

??virtual?~TwoLevelIterator();

??virtual?void?Seek(const?Slice&?target);
??virtual?void?SeekToFirst();
??virtual?void?SeekToLast();
??virtual?void?Next();
??virtual?void?Prev();

??virtual?bool?Valid()?const?{
????return?data_iter_.Valid();
??}
??virtual?Slice?key()?const?{
????assert(Valid());
????return?data_iter_.key();
??}
??virtual?Slice?value()?const?{
????assert(Valid());
????return?data_iter_.value();
??}
??virtual?Status?status()?const?{
????//?It'd?be?nice?if?status()?returned?a?const?Status&?instead?of?a?Status
????if?(!index_iter_.status().ok())?{
??????return?index_iter_.status();
????}?else?if?(data_iter_.iter()?!=?NULL?&&?!data_iter_.status().ok())?{
??????return?data_iter_.status();
????}?else?{
??????return?status_;
????}
??}

?private:
??void?SaveError(const?Status&?s)?{
????if?(status_.ok()?&&?!s.ok())?status_?=?s;
??}
??void?SkipEmptyDataBlocksForward();
??void?SkipEmptyDataBlocksBackward();
??void?SetDataIterator(Iterator*?data_iter);
??void?InitDataBlock();

??BlockFunction?block_function_;//生成Data?Block中block_data字段的迭代器
??void*?arg_;
??const?ReadOptions?options_;
??Status?status_;
??IteratorWrapper?index_iter_;//第一層迭代器,Index?Block的block_data字段迭代器的代理
??IteratorWrapper?data_iter_;?//第二層迭代器,Data?Block的block_data字段迭代器的代理
??//?If?data_iter_?is?non-NULL,?then?"data_block_handle_"?holds?the
??//?"index_value"?passed?to?block_function_?to?create?the?data_iter_.
??std::string?data_block_handle_;//handle中間變量
};

這里需要注意的是,兩層迭代器都是IteratorWrapper類型而不是iter,主要是為了緩存key和valid,避免每次都要調(diào)用iterator->key()和iterator->valid(),因為虛函數(shù)調(diào)的頻繁調(diào)用,有一定的性能消耗。至于為何有性能損耗,可參考:

C++中虛函數(shù)(virtual function)到底有多慢

為什么 C++ 中使用虛函數(shù)時會影響效率?

2.迭代器的初始化


void?TwoLevelIterator::InitDataBlock()?{
??if?(!index_iter_.Valid())?{
	//?當(dāng)index_iter_無效時,讓data_iter_也無效
????SetDataIterator(NULL);
??}?else?{
????//?index_iter_是Index?Block中block_data字段迭代器的代理
????//?handle是對應(yīng)的Data?Block的偏移和該Data?Block的block_data字段大小編碼后的結(jié)果
????Slice?handle?=?index_iter_.value();
????if?(data_iter_.iter()?!=?NULL?&&?handle.compare(data_block_handle_)?==?0)?{
????//?如果data_iter_已經(jīng)創(chuàng)建了,什么都不用干,這可以防止InitDataBlock被多次調(diào)用
????}?else?{
??????//?創(chuàng)建Data?Block中block_data字段的迭代器
??????Iterator*?iter?=?(*block_function_)(arg_,?options_,?handle);
??????//?將handle轉(zhuǎn)化為data_block_handle_
??????data_block_handle_.assign(handle.data(),?handle.size());
??????//?將iter傳給其代理data_inter_
??????SetDataIterator(iter);
????}
??}
}

3.迭代器的各種操作

//?Index?Block的block_data字段中,每一條記錄的key都滿足:
//?大于上一個Data?Block的所有key,并且小于后面所有Data?Block的key
//?因為Seek是查找key>=target的第一條記錄,所以當(dāng)index_iter_找到時,
//?該index_inter_對應(yīng)的data_iter_所管理的Data?Block中所有記錄的
//?key都小于target,需要在下一個Data?Block中seek,而下一個Data?Block
//?中的第一條記錄就滿足key>=target
void?TwoLevelIterator::Seek(const?Slice&?target)?{
??index_iter_.Seek(target);
??InitDataBlock();
??//?data_iter_.Seek(target)必然會找不到,此時data_iter_.Valid()為false
??//?然后調(diào)用SkipEmptyDataBlocksForward定位到下一個Data?Block,并定位到
??//?該Data?Block的第一條記錄,這條記錄剛好就是要查找的那條記錄
??if?(data_iter_.iter()?!=?NULL)?data_iter_.Seek(target);
??SkipEmptyDataBlocksForward();
}
//?因為index_block_options.block_restart_interval?=?1
//?所以這里是解析第一個Block?Data的第一條記錄
void?TwoLevelIterator::SeekToFirst()?{
??index_iter_.SeekToFirst();
??InitDataBlock();
??if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToFirst();
??SkipEmptyDataBlocksForward();
}
//?因為index_block_options.block_restart_interval?=?1
//?所以這里是解析最后一個Block?Data的最后一條記錄
void?TwoLevelIterator::SeekToLast()?{
??index_iter_.SeekToLast();
??InitDataBlock();
??if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToLast();
??SkipEmptyDataBlocksBackward();
}

void?TwoLevelIterator::Next()?{
??assert(Valid());
??data_iter_.Next();
??SkipEmptyDataBlocksForward();
}

void?TwoLevelIterator::Prev()?{
??assert(Valid());
??data_iter_.Prev();
??SkipEmptyDataBlocksBackward();
}


void?TwoLevelIterator::SkipEmptyDataBlocksForward()?{
??//?1.如果data_iter_.iter()為NULL,說明index_iter_.Valid()為為NULL時調(diào)用了
??//???SetDataIterator(NULL),此時直接返回,因為沒數(shù)據(jù)可讀啦
??//?2.如果data_iter_.Valid()為false,說明當(dāng)前Data?Block的block_data字段讀完啦
??//???開始讀下一個Data?Block的block_data字段(從block_data第一條記錄開始讀)
??while?(data_iter_.iter()?==?NULL?||?!data_iter_.Valid())?{
????//?Move?to?next?block
????if?(!index_iter_.Valid())?{
??????SetDataIterator(NULL);
??????return;
????}
????index_iter_.Next();
????InitDataBlock();
????if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToFirst();
??}
}

void?TwoLevelIterator::SkipEmptyDataBlocksBackward()?{
??while?(data_iter_.iter()?==?NULL?||?!data_iter_.Valid())?{
????//?Move?to?next?block
????if?(!index_iter_.Valid())?{
??????SetDataIterator(NULL);
??????return;
????}
????index_iter_.Prev();
????InitDataBlock();
????if?(data_iter_.iter()?!=?NULL)?data_iter_.SeekToLast();
??}
}

注釋還是寫的比較詳細的,備忘足矣。block_function_是BlockFunction類型的函數(shù)指針,實參在Table類中,名為BlockReader。關(guān)于Table,詳見:LevelDB源碼分析之十三:table



本站聲明: 本文章由作者或相關(guān)機構(gòu)授權(quán)發(fā)布,目的在于傳遞更多信息,并不代表本站贊同其觀點,本站亦不保證或承諾內(nèi)容真實性等。需要轉(zhuǎn)載請聯(lián)系該專欄作者,如若文章內(nèi)容侵犯您的權(quán)益,請及時聯(lián)系本站刪除。
換一批
延伸閱讀

9月2日消息,不造車的華為或?qū)⒋呱龈蟮莫毥谦F公司,隨著阿維塔和賽力斯的入局,華為引望愈發(fā)顯得引人矚目。

關(guān)鍵字: 阿維塔 塞力斯 華為

加利福尼亞州圣克拉拉縣2024年8月30日 /美通社/ -- 數(shù)字化轉(zhuǎn)型技術(shù)解決方案公司Trianz今天宣布,該公司與Amazon Web Services (AWS)簽訂了...

關(guān)鍵字: AWS AN BSP 數(shù)字化

倫敦2024年8月29日 /美通社/ -- 英國汽車技術(shù)公司SODA.Auto推出其旗艦產(chǎn)品SODA V,這是全球首款涵蓋汽車工程師從創(chuàng)意到認證的所有需求的工具,可用于創(chuàng)建軟件定義汽車。 SODA V工具的開發(fā)耗時1.5...

關(guān)鍵字: 汽車 人工智能 智能驅(qū)動 BSP

北京2024年8月28日 /美通社/ -- 越來越多用戶希望企業(yè)業(yè)務(wù)能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務(wù)中斷的風(fēng)險,如企業(yè)系統(tǒng)復(fù)雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務(wù)連續(xù)性,提升韌性,成...

關(guān)鍵字: 亞馬遜 解密 控制平面 BSP

8月30日消息,據(jù)媒體報道,騰訊和網(wǎng)易近期正在縮減他們對日本游戲市場的投資。

關(guān)鍵字: 騰訊 編碼器 CPU

8月28日消息,今天上午,2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會開幕式在貴陽舉行,華為董事、質(zhì)量流程IT總裁陶景文發(fā)表了演講。

關(guān)鍵字: 華為 12nm EDA 半導(dǎo)體

8月28日消息,在2024中國國際大數(shù)據(jù)產(chǎn)業(yè)博覽會上,華為常務(wù)董事、華為云CEO張平安發(fā)表演講稱,數(shù)字世界的話語權(quán)最終是由生態(tài)的繁榮決定的。

關(guān)鍵字: 華為 12nm 手機 衛(wèi)星通信

要點: 有效應(yīng)對環(huán)境變化,經(jīng)營業(yè)績穩(wěn)中有升 落實提質(zhì)增效舉措,毛利潤率延續(xù)升勢 戰(zhàn)略布局成效顯著,戰(zhàn)新業(yè)務(wù)引領(lǐng)增長 以科技創(chuàng)新為引領(lǐng),提升企業(yè)核心競爭力 堅持高質(zhì)量發(fā)展策略,塑強核心競爭優(yōu)勢...

關(guān)鍵字: 通信 BSP 電信運營商 數(shù)字經(jīng)濟

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學(xué)會聯(lián)合牽頭組建的NVI技術(shù)創(chuàng)新聯(lián)盟在BIRTV2024超高清全產(chǎn)業(yè)鏈發(fā)展研討會上宣布正式成立。 活動現(xiàn)場 NVI技術(shù)創(chuàng)新聯(lián)...

關(guān)鍵字: VI 傳輸協(xié)議 音頻 BSP

北京2024年8月27日 /美通社/ -- 在8月23日舉辦的2024年長三角生態(tài)綠色一體化發(fā)展示范區(qū)聯(lián)合招商會上,軟通動力信息技術(shù)(集團)股份有限公司(以下簡稱"軟通動力")與長三角投資(上海)有限...

關(guān)鍵字: BSP 信息技術(shù)
關(guān)閉
關(guān)閉