LevelDB中的skiplist實現(xiàn)方式基本上和中的實現(xiàn)方式類似。它向外暴露接口非常簡單,如下:
public: ??//?Create?a?new?SkipList?object?that?will?use?"cmp"?for?comparing?keys, ??//?and?will?allocate?memory?using?"*arena".??Objects?allocated?in?the?arena ??//?must?remain?allocated?for?the?lifetime?of?the?skiplist?object. ??explicit?SkipList(Comparator?cmp,?Arena*?arena); ??//?Insert?key?into?the?list. ??//?REQUIRES:?nothing?that?compares?equal?to?key?is?currently?in?the?list. ??void?Insert(const?Key&?key); ??//?Returns?true?iff?an?entry?that?compares?equal?to?key?is?in?the?list. ??bool?Contains(const?Key&?key)?const
private成員變量:
private: ??enum?{?kMaxHeight?=?12?}; ??//?Immutable?after?construction ??Comparator?const?compare_; ??Arena*?const?arena_;????//?Arena?used?for?allocations?of?nodes ??Node*?const?head_; ??//?Modified?only?by?Insert().??Read?racily?by?readers,?but?stale ??//?values?are?ok. ??port::AtomicPointer?max_height_;??? ??//?Read/written?only?by?Insert(). ??Random?rnd_;
一.構(gòu)造函數(shù)
templateSkipList::SkipList(Comparator?cmp,?Arena*?arena) ????:?compare_(cmp), ??????arena_(arena), ??????head_(NewNode(0?/*?any?key?will?do?*/,?kMaxHeight)), ??????max_height_(reinterpret_cast(1)), ??????rnd_(0xdeadbeef)?{ ??for?(int?i?=?0;?i?<?kMaxHeight;?i++)?{ ????head_->SetNext(i,?NULL); ??} }
重點注意下head_和rnd_的初始化,NewNode方法如下。
templatetypename?SkipList::Node* SkipList::NewNode(const?Key&?key,?int?height)?{ ??char*?mem?=?arena_->AllocateAligned( ??????sizeof(Node)?+?sizeof(port::AtomicPointer)?*?(height?-?1)); ??return?new?(mem)?Node(key); }
這里為什么是“height-1”詳見:LevelDb源碼分析之五:skiplist(1)。
new (mem) Node(key)使用了placement new技巧,詳見:C++中使用placement new
rnd_是一個Random類型的變量,使用0xdeadbeef進行初始化,Random詳見LevelDB源碼分析之七:Random
二.插入函數(shù)
templatevoid?SkipList::Insert(const?Key&?key)?{ ??//?TODO(opt):?We?can?use?a?barrier-free?variant?of?FindGreaterOrEqual() ??//?here?since?Insert()?is?externally?synchronized. ??//?prev記錄的是查詢路徑,下面需要使用prev來修改新生成結(jié)點的指針?? ??//?prev相當于LevelDb源碼分析之五:skiplist(1)中的update ??//?整個流程與LevelDb源碼分析之五:skiplist(1)相似,這里不再詳細解釋 ??Node*?prev[kMaxHeight]; ??//?返回大于等于key的結(jié)點或者NULL,原因詳見FindGreaterOrEqual的分析 ??Node*?x?=?FindGreaterOrEqual(key,?prev); ??//?Our?data?structure?does?not?allow?duplicate?insertion ??//?不允許插入重復(fù)的值?? ??assert(x?==?NULL?||?!Equal(key,?x->key)); ??//?產(chǎn)生一個隨機層數(shù)height ??int?height?=?RandomHeight(); ??//?如果height大于原最大層數(shù),則更新prev,并更新最大層數(shù) ??if?(height?>?GetMaxHeight())?{ ????for?(int?i?=?GetMaxHeight();?i?<?height;?i++)?{ ??????prev[i]?=?head_; ????} ????//fprintf(stderr,?"Change?height?from?%d?to?%dn",?max_height_,?height); ????//?It?is?ok?to?mutate?max_height_?without?any?synchronization ????//?with?concurrent?readers.??A?concurrent?reader?that?observes ????//?the?new?value?of?max_height_?will?see?either?the?old?value?of ????//?new?level?pointers?from?head_?(NULL),?or?a?new?value?set?in ????//?the?loop?below.??In?the?former?case?the?reader?will ????//?immediately?drop?to?the?next?level?since?NULL?sorts?after?all ????//?keys.??In?the?latter?case?the?reader?will?use?the?new?node. ????max_height_.NoBarrier_Store(reinterpret_cast(height)); ??} ??//?創(chuàng)建一個待插入的結(jié)點x,從低到高一層層插入 ??x?=?NewNode(key,?height); ??//?逐層更新結(jié)點的指針,和普通鏈表插入一樣? ??for?(int?i?=?0;?i?<?height;?i++)?{ ????//?NoBarrier_SetNext()?suffices?since?we?will?add?a?barrier?when ????//?we?publish?a?pointer?to?"x"?in?prev[i]. ????x->NoBarrier_SetNext(i,?prev[i]->NoBarrier_Next(i)); ????prev[i]->SetNext(i,?x); ??} }
插入函數(shù)里調(diào)用了私有函數(shù)FindGreaterOrEqual。FindGreaterOrEqual中完成查詢操作,就是向下(level控制)和向右(x控制)移動過程,并不斷將經(jīng)過路徑保存到參數(shù)prev中。
templatetypename?SkipList::Node*?SkipList::FindGreaterOrEqual(const?Key&?key,?Node**?prev) ????const?{ ??Node*?x?=?head_; ??int?level?=?GetMaxHeight()?-?1; ??//?從最高層往下,每層都查找插入位置,當遍歷到該層的尾部(x->next[level]==NULL)?? ??//?也沒有找到比key大的結(jié)點時,將該層的最后一個結(jié)點的指針放到prev[level]中。?? ??//?如果在某層中找到了比key大或等于key的結(jié)點時,將該結(jié)點之前的那個比key小的結(jié)點的指針?? ??//?放到prev[level]中。?? ??while?(true)?{ ????Node*?next?=?x->Next(level); ????if?(KeyIsAfterNode(key,?next))?{ ??????//?Keep?searching?in?this?list ??????x?=?next; ????}?else?{ ??????if?(prev?!=?NULL)?prev[level]?=?x; ??//?當查到第一層時,有兩種情況: ??//?1.第一層中有滿足要求的結(jié)點,此時next剛好是不小于key的那個結(jié)點 ??//?2.第一層中沒有滿足要求的結(jié)點,此時實際上到了尾部,next=NULL ??????if?(level?==?0)?{ ????????return?next; ??????}?else?{ ????????//?Switch?to?next?list ????????level--; ??????} ????} ??} }
三.查找函數(shù)
查找操作基本上就是調(diào)用函數(shù)上面的函數(shù)FindGreaterOrEqual實現(xiàn)。
templatebool?SkipList::Contains(const?Key&?key)?const?{ ??Node*?x?=?FindGreaterOrEqual(key,?NULL); ??if?(x?!=?NULL?&&?Equal(key,?x->key))?{ ????return?true; ??}?else?{ ????return?false; ??} }
需要注意的是,LevelDB中沒有提供顯式的刪除節(jié)點操作,但實際上是可以刪除的,因為當我們插入數(shù)據(jù)時,key的形式為key:value,當刪除數(shù)據(jù)時,則插入key:deleted類似刪除的標記,等到Compaction再刪除。