當前位置:首頁 > 芯聞號 > 充電吧
[導讀]閱讀本文可參考: LevelDB源碼分析之一:coding LevelDB源碼分析之二:comparator LevelDB源碼分析之三:arena LevelDB源碼分析之四:AtomicPoint

閱讀本文可參考:

LevelDB源碼分析之一:coding

LevelDB源碼分析之二:comparator

LevelDB源碼分析之三:arena

LevelDB源碼分析之四:AtomicPointer

LevelDb源碼分析之五:skiplist(1)

LevelDB源碼分析之七:Random

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ù)
template
SkipList::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方法如下。
template
typename 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ù)

template
void 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
  // 不允許插入重復的值  
  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中。

template
typename 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)。

template
bool 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再刪除。

參考鏈接:http://blog.csdn.net/xuqianghit/article/details/6948554













本站聲明: 本文章由作者或相關(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è)務能7×24不間斷運行,同時企業(yè)卻面臨越來越多業(yè)務中斷的風險,如企業(yè)系統(tǒng)復雜性的增加,頻繁的功能更新和發(fā)布等。如何確保業(yè)務連續(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 半導體

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

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

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

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

北京2024年8月27日 /美通社/ -- 8月21日,由中央廣播電視總臺與中國電影電視技術(shù)學會聯(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)閉