levelDBソース分析-Skiplist


ここでは主にlevelDBにおけるSkipListの実現について紹介します.SkipListの紹介については「SkipList」を参照してください.ここでは引用しません.
        levelDBでの使用:
        levelDBのMemtableにはコアのデータ構造Skiplistがあり、具体的に実現されるコードは少し違っていますが、基本原理は一致しています.        levelDBのSkiplistはテンプレートクラスと定義されています.
       
// description:   
// Thread safety
// Writes require external synchronization, most likely a mutex.
// Reads require a guarantee that the SkipList will not be destroyed while the read is in progress.  Apart from that, reads progress  without any internal locking or synchronization.
//
// Invariants:
// (1) Allocated nodes are never deleted until the SkipList is destroyed.  This is trivially guaranteed by the code since we never delete any skip list nodes.
// (2) The contents of a Node except for the next/prev pointers are immutable after the Node has been linked into the SkipList.  Only Insert() modifies the list, and it is careful to initialize a node and use release-stores to publish the nodes in one or more lists.

    template<typename Key, class Comparator>
    class SkipList {
        private:
             struct Node;

        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);						//     key Skiplist 
        // Returns true iff an entry that compares equal to key is in the list.
        bool Contains(const Key& key) const;					// Skiplist key       

        private:
           enum { kMaxHeight = 12 };						//   level

        // Immutable after construction
        Comparator const compare_;						// key      ,           (        ,  key,     )
        Arena* const arena_;    // Arena used for allocations of nodes		// levelDB    Arena     
        Node* const head_;							// Skiplist   

        // Modified only by Insert().  Read racily by readers, but stale
        // values are ok.
        port::AtomicPointer max_height_;   // Height of the entire list		// Skiplist  

        inline int GetMaxHeight() const {						//   Skiplist   
            return reinterpret_cast<intptr_t>(max_height_.NoBarrier_Load());
        }

        // Read/written only by Insert().
        Random rnd_;								//    ,     level  

        Node* NewNode(const Key& key, int height);				//     level=height,  key   
        int RandomHeight();							//       level  
        bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); } 	//   2 key    

        // Return true if key is greater than the data stored in "n"
        bool KeyIsAfterNode(const Key& key, Node* n) const;			//   key Node n  key,  key   

        // Return the earliest node that comes at or after key.
        // Return NULL if there is no such node.
        // If prev is non-NULL, fills prev[level] with pointer to previous
        // node at "level" for every level in [0..max_height_-1].
        Node* FindGreaterOrEqual(const Key& key, Node** prev) const;	//   key   Node  key     Node

        // Return the latest node with a key < key, return head_ if there is no such node.
        Node* FindLessThan(const Key& key) const;				//   key     Node

        // Return the last node in the list.
        // Return head_ if list is empty.
        Node* FindLast() const;							// Skiplist    Node

        // No copying allowed
        SkipList(const SkipList&);						//               
        void operator=(const SkipList&);
        };

    // Implementation details follow
    template<typename Key, class Comparator>
    struct SkipList<Key,Comparator>::Node {					// Skiplist  Node  
        explicit Node(const Key& k) : key(k) { }
        Key const key;
        // Accessors/mutators for links.  Wrapped in methods so we can add the appropriate barriers as necessary.
        Node* Next(int n) {
            assert(n >= 0);
            // Use an 'acquire load' so that we observe a fully initialized version of the returned Node.
            return reinterpret_cast<Node*>(next_[n].Acquire_Load());
        }
        void SetNext(int n, Node* x) {
            assert(n >= 0);
            // Use a 'release store' so that anybody who reads through this pointer observes a fully initialized version of the inserted node.
            next_[n].Release_Store(x);
        }

        // No-barrier variants that can be safely used in a few locations.
        Node* NoBarrier_Next(int n) {
            assert(n >= 0);
            return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
        }
        void NoBarrier_SetNext(int n, Node* x) {
            assert(n >= 0);
            next_[n].NoBarrier_Store(x);
        }
        private:
        // Array of length equal to the node height.  next_[0] is lowest level link.
        port::AtomicPointer next_[1];							// forward    
        };

    template<typename Key, class Comparator>
    typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::NewNode(const Key& key, int height) {	//     Node  (  key level  )
        char* mem = arena_->AllocateAligned(sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
        return new (mem) Node(key);   //     new
    }
     template<typename Key, class Comparator>
    SkipList<Key,Comparator>::SkipList(Comparator cmp, Arena* arena)							//     
    : compare_(cmp),
    arena_(arena),
    head_(NewNode(0 /* any key will do */, kMaxHeight)),									//     key    
    max_height_(reinterpret_cast<void*>(1)),
    rnd_(0xdeadbeef) {
        for (int i = 0; i < kMaxHeight; i++) {
            head_->SetNext(i, NULL);                //       
        }
    }
    
    template<typename Key, class Comparator>
    int SkipList<Key,Comparator>::RandomHeight() {										 //       (Skiplist        )
        // Increase height with probability 1 in kBranching
        static const unsigned int kBranching = 4;
        int height = 1;
        while (height < kMaxHeight && ((rnd_.Next() % kBranching) == 0)) {	//?           ?        ?
            height++;
        }
        assert(height > 0);
        assert(height <= kMaxHeight);
        return height;
    }

    template<typename Key, class Comparator>
    bool SkipList<Key,Comparator>::KeyIsAfterNode(const Key& key, Node* n) const { 	 				// Return true if key is greater than the key stored in "n"
        // NULL n is considered infinite,NULL      (         NIL)
        return (n != NULL) && (compare_(n->key, key) < 0);
    }

    template<typename Key, class Comparator>
    typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)   const {     // 
        Node* x = head_;
        int level = GetMaxHeight() - 1;
        while (true) {
            Node* next = x->Next(level);
            if (KeyIsAfterNode(key, next)) {  				// key next    ,    true,    next  NULL
                // Keep searching in this list
                x = next;
            } else {
                if (prev != NULL)   prev[level] = x;  				//   level ,x   >=key    ,        ,        
                if (level == 0) {
                    return next;
               } else {
                    // Switch to next list( low level link list)
                    level--;
                }
            }
        }
    }

    template<typename Key, class Comparator>
    typename SkipList<Key,Comparator>::Node*  SkipList<Key,Comparator>::FindLessThan(const Key& key) const {   // Return the latest node with a key < key, return head_ if there is no such node.
        Node* x = head_;
        int level = GetMaxHeight() - 1;
        while (true) {
            assert(x == head_ || compare_(x->key, key) < 0);			// 
            Node* next = x->Next(level);
            if (next == NULL || compare_(next->key, key) >= 0) {			//    level            
                //   key>   key , next   ,level--,  level=0
                if (level == 0) {
                    return x;
                    } else {
                    // Switch to next list
                    level--;                        //           
              }
          } else {
                x = next;
            }
        }
    }
    template<typename Key, class Comparator>
    typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindLast() const {		//     level   ,    level     ,   level=0
        Node* x = head_;
        int level = GetMaxHeight() - 1;
        while (true) {
            Node* next = x->Next(level);
            if (next == NULL) {
                if (level == 0) {
                    return x;
                } else {
                    // Switch to next list
                    level--;
                }
          } else {
                x = next;
        }
     }
    }

    template<typename Key, class Comparator>
    void SkipList<Key,Comparator>::Insert(const Key& key) {							//   key  
        // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
        // here since Insert() is externally synchronized.
        Node* prev[kMaxHeight];
        Node* x = FindGreaterOrEqual(key, prev);								// prev    level      

        // Our data structure does not allow duplicate insertion
        assert(x == NULL || !Equal(key, x->key));

        int height = RandomHeight();
        if (height > GetMaxHeight()) {
            for (int i = GetMaxHeight(); i < height; i++) {
                prev[i] = head_;
            }
            //fprintf(stderr, "Change height from %d to %d
", 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<void*>(height)); } x = NewNode(key, height); // Node for (int i = 0; i < height; i++) { // level , level // 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); } } template<typename Key, class Comparator> bool SkipList<Key,Comparator>::Contains(const Key& key) const { // Skiplist key Node* x = FindGreaterOrEqual(key, NULL); // key if (x != NULL && Equal(key, x->key)) { // , , return true; } else { return false; } } // Iteration over the contents of a skiplist template<typename Key, class Comparator> class SkipList<Key,Comparator>::Iterator { // Skiplist public: // Initialize an iterator over the specified list. // The returned iterator is not valid. explicit Iterator(const SkipList* list); // Returns true iff the iterator is positioned at a valid node. bool Valid() const; // Returns the key at the current position. // REQUIRES: Valid() const Key& key() const; // Advances to the next position. // REQUIRES: Valid() void Next(); // Advances to the previous position. // REQUIRES: Valid() void Prev(); // Advance to the first entry with a key >= target void Seek(const Key& target); // Position at the first entry in list. // Final state of iterator is Valid() iff list is not empty. void SeekToFirst(); // Position at the last entry in list. // Final state of iterator is Valid() iff list is not empty. void SeekToLast(); private: const SkipList* list_; Node* node_; // Intentionally copyable copy , }; template<typename Key, class Comparator> inline SkipList<Key,Comparator>::Iterator::Iterator(const SkipList* list) { // , iterator list_ = list; node_ = NULL; } template<typename Key, class Comparator> inline bool SkipList<Key,Comparator>::Iterator::Valid() const { // Returns true iff the iterator is positioned at a valid node. return node_ != NULL; } template<typename Key, class Comparator> inline const Key& SkipList<Key,Comparator>::Iterator::key() const { // Returns the key at the current position. assert(Valid()); return node_->key; } template<typename Key, class Comparator> inline void SkipList<Key,Comparator>::Iterator::Next() { // Advances to the next position. assert(Valid()); node_ = node_->Next(0); // level 0 } template<typename Key, class Comparator> inline void SkipList<Key,Comparator>::Iterator::Prev() { // Advances to the previous position. // Instead of using explicit "prev" links, we just search for the // last node that falls before key. assert(Valid()); node_ = list_->FindLessThan(node_->key); // , head_, NULL if (node_ == list_->head_) { node_ = NULL; } } template<typename Key, class Comparator> inline void SkipList<Key,Comparator>::Iterator::Seek(const Key& target) { // Advance to the first entry with a key >= target node_ = list_->FindGreaterOrEqual(target, NULL); } // template<typename Key, class Comparator> inline void SkipList<Key,Comparator>::Iterator::SeekToFirst() { // Position at the first entry in list. node_ = list_->head_->Next(0); } template<typename Key, class Comparator> inline void SkipList<Key,Comparator>::Iterator::SeekToLast() { // Position at the last entry in list. node_ = list_->FindLast(); // , , null if (node_ == list_->head_) { node_ = NULL; } }
結論        簡単なデータ構造として,SkipListアルゴリズムは非常に実現しやすい.ほとんどの応用においては、SkipListは平衡樹の代わりに、SkipListと最適化されたバランスツリーは同じ高性能であり、性能は非最適なバランス二叉樹をはるかに超える.
   
       コードプログラミングの技術:内部クラスまたは友達クラスの定義を使用することができます.