现在的位置: 首页 > 综合 > 正文

LevelDB源码之SkipList原理 LevelDB源码之SkipList原理

2017年09月29日 ⁄ 综合 ⁄ 共 14776字 ⁄ 字号 小 中 大 ⁄ 评论关闭

LevelDB源码之SkipList原理

分类： LevelDB源码系列2013-08-15
22:01 374人阅读 评论(0) 收藏 举报
LevelDB源码系列

感觉SkipList只要搞清楚高度就好了.下面是随机生成高度的函数RandomHeight()

[cpp] view
plaincopy

  1. template<typename Key, class Comparator>  
  2. int SkipList<Key,Comparator>::RandomHeight() {  
  3.   // Increase height with probability 1 in kBranching  
  4.   static const unsigned int kBranching = 4;  
  5.   int height = 1;  
  6.   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
  7.     height++;  
  8.   }  
  9.   assert(height > 0);  
  10.   assert(height <= kMaxHeight);  
  11.   return height;  
  12. }  

插入操作：

[cpp] view
plaincopy

  1. template<typename Key, class Comparator>  
  2. void SkipList<Key,Comparator>::Insert(const Key& key) {  
  3.   // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  
  4.   // here since Insert() is externally synchronized.  
  5.   //prev为各层的前置节点  
  6.   Node* prev[kMaxHeight];  
  7.   //查找插入的节点  
  8.   Node* x = FindGreaterOrEqual(key, prev);  
  9.   
  10.   // Our data structure does not allow duplicate insertion  
  11.   assert(x == NULL || !Equal(key, x->key));  
  12.   //随机生成节点高度  
  13.   int height = RandomHeight();  
  14.   if (height > GetMaxHeight()) {  
  15.     for (int i = GetMaxHeight(); i < height; i++) {  
  16.       prev[i] = head_;  
  17.     }  
  18.     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
  19.   
  20.     // It is ok to mutate max_height_ without any synchronization  
  21.     // with concurrent readers.  A concurrent reader that observes  
  22.     // the new value of max_height_ will see either the old value of  
  23.     // new level pointers from head_ (NULL), or a new value set in  
  24.     // the loop below.  In the former case the reader will  
  25.     // immediately drop to the next level since NULL sorts after all  
  26.     // keys.  In the latter case the reader will use the new node.  
  27.     //设置最大高度  
  28.     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
  29.   }  
  30.   //生成一个新的Node  
  31.   x = NewNode(key, height);  
  32.   for (int i = 0; i < height; i++) {  
  33.     // NoBarrier_SetNext() suffices since we will add a barrier when  
  34.     // we publish a pointer to "x" in prev[i].  
  35.     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
  36.     prev[i]->SetNext(i, x);  
  37.   }  
  38. }  

查找操作：

[cpp] view
plaincopy

  1. template<typename Key, class Comparator>  
  2. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  
  3.     const {  
  4.   Node* x = head_;  
  5.   //从最顶层开始查找  
  6.   int level = GetMaxHeight() - 1;  
  7.   while (true) {  
  8.     Node* next = x->Next(level);  
  9.     //向右查找  
  10.     if (KeyIsAfterNode(key, next)) {  
  11.       // Keep searching in this list  
  12.       x = next;  
  13.     } else {  
  14.         //向下查找  
  15.       if (prev != NULL) prev[level] = x;  
  16.       if (level == 0) {  
  17.         return next;  
  18.       } else {  
  19.         // Switch to next list  
  20.         level--;  
  21.       }  
  22.     }  
  23.   }  
  24. }  

整个SkipList.h源码：

[cpp] view
plaincopy

  1. // Copyright (c) 2011 The LevelDB Authors. All rights reserved.  
  2. // Use of this source code is governed by a BSD-style license that can be  
  3. // found in the LICENSE file. See the AUTHORS file for names of contributors.  
  4. //  
  5. // Thread safety  
  6. // -------------  
  7. //  
  8. // Writes require external synchronization, most likely a mutex.  
  9. // Reads require a guarantee that the SkipList will not be destroyed  
  10. // while the read is in progress.  Apart from that, reads progress  
  11. // without any internal locking or synchronization.  
  12. //  
  13. // Invariants:  
  14. //  
  15. // (1) Allocated nodes are never deleted until the SkipList is  
  16. // destroyed.  This is trivially guaranteed by the code since we  
  17. // never delete any skip list nodes.  
  18. //  
  19. // (2) The contents of a Node except for the next/prev pointers are  
  20. // immutable after the Node has been linked into the SkipList.  
  21. // Only Insert() modifies the list, and it is careful to initialize  
  22. // a node and use release-stores to publish the nodes in one or  
  23. // more lists.  
  24. //  
  25. // ... prev vs. next pointer ordering ...  
  26.   
  27. #include <assert.h>  
  28. #include <stdlib.h>  
  29. #include "port/port.h"  
  30. #include "util/arena.h"  
  31. #include "util/random.h"  
  32. /** 
  33.  * SkipList应用概率来保证平衡，平衡树采用严格的旋转来保证平衡 
  34.  * 使用SkipList是的查找特定值得时间复杂度是O(logN)，与平衡树有着相同的复杂度，节省空间，每个检点平均1.33个指针 
  35.  * leveldb的最高层数为12，只允许插入和修改，Record的key不允许重复，添加一个Sequene Num 
  36.  * 规范：参数使用引用，返回值使用指针 
  37.  * 
  38.  */  
  39. namespace leveldb {  
  40.   
  41. class Arena;  
  42.   
  43. template<typename Key, class Comparator>  
  44. class SkipList {  
  45.  private:  
  46.   struct Node;  
  47.   
  48.  public:  
  49.   // Create a new SkipList object that will use "cmp" for comparing keys,  
  50.   // and will allocate memory using "*arena".  Objects allocated in the arena  
  51.   // must remain allocated for the lifetime of the skiplist object.  
  52.   explicit SkipList(Comparator cmp, Arena* arena);  
  53.   
  54.   // Insert key into the list.  
  55.   // REQUIRES: nothing that compares equal to key is currently in the list.  
  56.   void Insert(const Key& key);  
  57.   
  58.   // Returns true iff an entry that compares equal to key is in the list.  
  59.   bool Contains(const Key& key) const;  
  60.   
  61.   // Iteration over the contents of a skip list  
  62.   class Iterator {  
  63.    public:  
  64.     // Initialize an iterator over the specified list.  
  65.     // The returned iterator is not valid.  
  66.     explicit Iterator(const SkipList* list);  
  67.   
  68.     // Returns true iff the iterator is positioned at a valid node.  
  69.     bool Valid() const;  
  70.   
  71.     // Returns the key at the current position.  
  72.     // REQUIRES: Valid()  
  73.     const Key& key() const;  
  74.   
  75.     // Advances to the next position.  
  76.     // REQUIRES: Valid()  
  77.     void Next();  
  78.   
  79.     // Advances to the previous position.  
  80.     // REQUIRES: Valid()  
  81.     void Prev();  
  82.   
  83.     // Advance to the first entry with a key >= target  
  84.     void Seek(const Key& target);  
  85.   
  86.     // Position at the first entry in list.  
  87.     // Final state of iterator is Valid() iff list is not empty.  
  88.     void SeekToFirst();  
  89.   
  90.     // Position at the last entry in list.  
  91.     // Final state of iterator is Valid() iff list is not empty.  
  92.     void SeekToLast();  
  93.   
  94.    private:  
  95.     const SkipList* list_;  
  96.     Node* node_;  
  97.     // Intentionally copyable  
  98.   };  
  99.   
  100.   //跳表的最高level数  
  101.  private:  
  102.   enum { kMaxHeight = 12 };  
  103.   
  104.   // Immutable(不可变) after construction  
  105.   Comparator const compare_;  
  106.   //舞台，竞技场，场所（只负责申请空间的内存池）  
  107.   Arena* const arena_;    // Arena used for allocations of nodes  
  108.   
  109.   Node* const head_;  
  110.   
  111.   // Modified only by Insert().  Read racily by readers, but stale  
  112.   // values are ok.  
  113.   port::AtomicPointer max_height_;   // Height of the entire list  
  114.   
  115.   inline int GetMaxHeight() const {  
  116.     return static_cast<int>(  
  117.         reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load()));  
  118.   }  
  119.   
  120.   // Read/written only by Insert().  
  121.   Random rnd_;  
  122.   
  123.   Node* NewNode(const Key& key, int height);  
  124.   int RandomHeight();  
  125.   bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }  
  126.   
  127.   // Return true if key is greater than the data stored in "n"  
  128.   bool KeyIsAfterNode(const Key& key, Node* n) const;  
  129.   
  130.   // Return the earliest node that comes at or after key.  
  131.   // Return NULL if there is no such node.  
  132.   //  
  133.   // If prev is non-NULL, fills prev[level] with pointer to previous  
  134.   // node at "level" for every level in [0..max_height_-1].  
  135.   Node* FindGreaterOrEqual(const Key& key, Node** prev) const;  
  136.   
  137.   // Return the latest node with a key < key.  
  138.   // Return head_ if there is no such node.  
  139.   Node* FindLessThan(const Key& key) const;  
  140.   
  141.   // Return the last node in the list.  
  142.   // Return head_ if list is empty.  
  143.   Node* FindLast() const;  
  144.   
  145.   // No copying allowed  
  146.   SkipList(const SkipList&);  
  147.   void operator=(const SkipList&);  
  148. };  
  149.   
  150. // Implementation details follow  
  151. template<typename Key, class Comparator>  
  152. struct SkipList<Key,Comparator>::Node {  
  153.   explicit Node(const Key& k) : key(k) { }  
  154.   
  155.   Key const key;  
  156.   
  157.   // Accessors/mutators for links.  Wrapped in methods so we can  
  158.   // add the appropriate barriers as necessary.  
  159.   Node* Next(int n) {  
  160.     assert(n >= 0);  
  161.     // Use an 'acquire load' so that we observe a fully initialized  
  162.     // version of the returned Node.  
  163.     return reinterpret_cast<Node*>(next_[n].Acquire_Load());  
  164.   }  
  165.   void SetNext(int n, Node* x) {  
  166.     assert(n >= 0);  
  167.     // Use a 'release store' so that anybody who reads through this  
  168.     // pointer observes a fully initialized version of the inserted node.  
  169.     next_[n].Release_Store(x);  
  170.   }  
  171.   
  172.   // No-barrier variants that can be safely used in a few locations.  
  173.   Node* NoBarrier_Next(int n) {  
  174.     assert(n >= 0);  
  175.     return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());  
  176.   }  
  177.   void NoBarrier_SetNext(int n, Node* x) {  
  178.     assert(n >= 0);  
  179.     next_[n].NoBarrier_Store(x);  
  180.   }  
  181.   
  182.  private:  
  183.   // Array of length equal to the node height.  next_[0] is lowest level link.  
  184.   port::AtomicPointer next_[1];  
  185. };  
  186.   
  187. template<typename Key, class Comparator>  
  188. typename SkipList<Key,Comparator>::Node*  
  189. SkipList<Key,Comparator>::NewNode(const Key& key, int height) {  
  190.   char* mem = arena_->AllocateAligned(  
  191.       sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));  
  192.   return new (mem) Node(key);  
  193. }  
  194.   
  195. template<typename Key, class Comparator>  
  196. inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) {  
  197.   list_ = list;  
  198.   node_ = NULL;  
  199. }  
  200.   
  201. template<typename Key, class Comparator>  
  202. inline bool SkipList<Key,Comparator>::Iterator::Valid() const {  
  203.   return node_ != NULL;  
  204. }  
  205.   
  206. template<typename Key, class Comparator>  
  207. inline const Key& SkipList<Key,Comparator>::Iterator::key() const {  
  208.   assert(Valid());  
  209.   return node_->key;  
  210. }  
  211.   
  212. template<typename Key, class Comparator>  
  213. inline void SkipList<Key,Comparator>::Iterator::Next() {  
  214.   assert(Valid());  
  215.   node_ = node_->Next(0);  
  216. }  
  217.   
  218. template<typename Key, class Comparator>  
  219. inline void SkipList<Key,Comparator>::Iterator::Prev() {  
  220.   // Instead of using explicit "prev" links, we just search for the  
  221.   // last node that falls before key.  
  222.   assert(Valid());  
  223.   node_ = list_->FindLessThan(node_->key);  
  224.   if (node_ == list_->head_) {  
  225.     node_ = NULL;  
  226.   }  
  227. }  
  228.   
  229. template<typename Key, class Comparator>  
  230. inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) {  
  231.   node_ = list_->FindGreaterOrEqual(target, NULL);  
  232. }  
  233.   
  234. template<typename Key, class Comparator>  
  235. inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() {  
  236.   node_ = list_->head_->Next(0);  
  237. }  
  238.   
  239. template<typename Key, class Comparator>  
  240. inline void SkipList<Key,Comparator>::Iterator::SeekToLast() {  
  241.   node_ = list_->FindLast();  
  242.   if (node_ == list_->head_) {  
  243.     node_ = NULL;  
  244.   }  
  245. }  
  246.   
  247. template<typename Key, class Comparator>  
  248. int SkipList<Key,Comparator>::RandomHeight() {  
  249.   // Increase height with probability 1 in kBranching  
  250.   static const unsigned int kBranching = 4;  
  251.   int height = 1;  
  252.   while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {  
  253.     height++;  
  254.   }  
  255.   assert(height > 0);  
  256.   assert(height <= kMaxHeight);  
  257.   return height;  
  258. }  
  259.   
  260. template<typename Key, class Comparator>  
  261. bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const {  
  262.   // NULL n is considered infinite  
  263.   return (n != NULL) && (compare_(n->key, key) < 0);  
  264. }  
  265. /** 
  266.  * 查找，从左向右，从上向下查找 
  267.  */  
  268. template<typename Key, class Comparator>  
  269. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)  
  270.     const {  
  271.   Node* x = head_;  
  272.   //从最顶层开始查找  
  273.   int level = GetMaxHeight() - 1;  
  274.   while (true) {  
  275.     Node* next = x->Next(level);  
  276.     //向右查找  
  277.     if (KeyIsAfterNode(key, next)) {  
  278.       // Keep searching in this list  
  279.       x = next;  
  280.     } else {  
  281.         //向下查找  
  282.       if (prev != NULL) prev[level] = x;  
  283.       if (level == 0) {  
  284.         return next;  
  285.       } else {  
  286.         // Switch to next list  
  287.         level--;  
  288.       }  
  289.     }  
  290.   }  
  291. }  
  292.   
  293. template<typename Key, class Comparator>  
  294. typename SkipList<Key,Comparator>::Node*  
  295. SkipList<Key,Comparator>::FindLessThan(const Key& key) const {  
  296.   Node* x = head_;  
  297.   int level = GetMaxHeight() - 1;  
  298.   while (true) {  
  299.     assert(x == head_ || compare_(x->key, key) < 0);  
  300.     Node* next = x->Next(level);  
  301.     if (next == NULL || compare_(next->key, key) >= 0) {  
  302.       if (level == 0) {  
  303.         return x;  
  304.       } else {  
  305.         // Switch to next list  
  306.         level--;  
  307.       }  
  308.     } else {  
  309.       x = next;  
  310.     }  
  311.   }  
  312. }  
  313.   
  314. template<typename Key, class Comparator>  
  315. typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast()  
  316.     const {  
  317.   Node* x = head_;  
  318.   int level = GetMaxHeight() - 1;  
  319.   while (true) {  
  320.     Node* next = x->Next(level);  
  321.     if (next == NULL) {  
  322.       if (level == 0) {  
  323.         return x;  
  324.       } else {  
  325.         // Switch to next list  
  326.         level--;  
  327.       }  
  328.     } else {  
  329.       x = next;  
  330.     }  
  331.   }  
  332. }  
  333. /** 
  334.  * SkipList初始化 
  335.  * 
  336.  */  
  337. template<typename Key, class Comparator>  
  338. SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)  
  339.     : compare_(cmp),  
  340.       arena_(arena),  
  341.       head_(NewNode(0 /* any key will do */, kMaxHeight)),  
  342.       max_height_(reinterpret_cast<void*>(1)),  
  343.       rnd_(0xdeadbeef) {  
  344.   for (int i = 0; i < kMaxHeight; i++) {  
  345.     head_->SetNext(i, NULL);  
  346.   }  
  347. }  
  348. /** 
  349.  * 插入一个新的key 
  350.  * 
  351.  */  
  352. template<typename Key, class Comparator>  
  353. void SkipList<Key,Comparator>::Insert(const Key& key) {  
  354.   // TODO(opt): We can use a barrier-free（(屏蔽，障碍/无障碍） variant(变种) of FindGreaterOrEqual()  
  355.   // here since Insert() is externally synchronized.  
  356.   //prev为各层的前置节点  
  357.   Node* prev[kMaxHeight];  
  358.   //查找插入的节点  
  359.   Node* x = FindGreaterOrEqual(key, prev);  
  360.   
  361.   // Our data structure does not allow duplicate insertion  
  362.   assert(x == NULL || !Equal(key, x->key));  
  363.   //随机生成节点高度  
  364.   int height = RandomHeight();  
  365.   if (height > GetMaxHeight()) {  
  366.     for (int i = GetMaxHeight(); i < height; i++) {  
  367.       prev[i] = head_;  
  368.     }  
  369.     //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);  
  370.   
  371.     // It is ok to mutate max_height_ without any synchronization  
  372.     // with concurrent readers.  A concurrent reader that observes  
  373.     // the new value of max_height_ will see either the old value of  
  374.     // new level pointers from head_ (NULL), or a new value set in  
  375.     // the loop below.  In the former case the reader will  
  376.     // immediately drop to the next level since NULL sorts after all  
  377.     // keys.  In the latter case the reader will use the new node.  
  378.     //设置最大高度  
  379.     max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));  
  380.   }  
  381.   //生成一个新的Node  
  382.   x = NewNode(key, height);  
  383.   for (int i = 0; i < height; i++) {  
  384.     // NoBarrier_SetNext() suffices since we will add a barrier when  
  385.     // we publish a pointer to "x" in prev[i].  
  386.     x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));  
  387.     prev[i]->SetNext(i, x);  
  388.   }  
  389. }  
  390. /** 
  391.  * 包含 
  392.  */  
  393. template<typename Key, class Comparator>  
  394. bool SkipList<Key,Comparator>::Contains(const Key& key) const {  
  395.   Node* x = FindGreaterOrEqual(key, NULL);  
  396.   if (x != NULL && Equal(key, x->key)) {  
  397.     return true;  
  398.   } else {  
  399.     return false;  
  400.   }  
  401. }  
  402.   
  403. }  // namespace leveldb  
返回
【上篇】
【下篇】

作者:

抱歉!评论已关闭.

返回首页

Copyright © 2013-2018 学步园  保留所有权利.
软文销售 QQ客服：2265327166 点击这里给我发消息（其他合作也可洽谈）
必威体育
必威电竞