LevelDB之Memtable

/**
     * 节点
     *
     * @param <K>
     * @param <V>
     */
    private static final class Node<K, V> implements Map.Entry<K, V> {


        final K key;


        V value;


        /**
         * 当前节点的层数
         */
        int level;


        /**
         * 多层的前向指针，其实就是多级索引，存放每一层的下一个节点
         * 最多和MAX_LEVEL一样
         */
        Node<K, V>[] forwards;


        @SuppressWarnings("unchecked")
        Node(K key, V value, int level) {
            super();
            this.key = key;
            this.value = value;
            this.level = level;
            this.forwards = new Node[MAX_LEVEL];
        }


        //其它方法略
    }

/**
 * 跳表
 *
 * @param <K> K值，用于排序
 * @param <V> V值，存放的值也可为null
 * @author chengzheng
 */
public final class SkipListMap<K extends Comparable<K>, V> implements Map<K, V>, Iterable<Map.Entry<K, V>> {


    /**
     * 最大层限制为16
     */
    private static final int MAX_LEVEL = 16;


    /**
     * 增长的概率为1/4，即当前层中平均插入4个节点就向上爬一层
     */
    private static final int BRANCH = 4;


    /**
     * 头节点
     */
    private final Node<K, V> dummyHead;


    /**
     * 当前跳表中最高的节点
     */
    private int currentMaxLevel;


    /**
     * 元素个数
     */
    private int size;


    public SkipListMap() {
        this.currentMaxLevel = 1;
        this.size = 0;
        this.dummyHead = new Node<>(null, null, 1);
    }
    //其它略
}

    /**
     * 获得新节点的level
     * @return 新节点的level
     */
    private int randomLevel() {
        //初始高度1
        int newLevel = 1;
        //通过随机数判断是否要爬高，newLevel为2有25%的概率，newLevel为3的概率为25% * 25%
        while (newLevel < MAX_LEVEL && ThreadLocalRandom.current().nextInt() % BRANCH == 0) {
            newLevel++;
        }
        //更新当前最大level
        if (newLevel > this.currentMaxLevel) {
            this.currentMaxLevel = newLevel;
        }
        return newLevel;
    }

    @Override
    public V get(Object key) {
        Objects.requireNonNull(key);
        //当前节点
        Node<K, V> c = dummyHead;
        //从当前跳表中最高层开始遍历，层越高，节点越稀疏
        for (int i = currentMaxLevel - 1; i >= 0; i--) {
            while (c.forwards[i] != null) {
                //当前节点的下一个节点和查询值比较
                @SuppressWarnings("unchecked") 
                final int cmp = c.forwards[i].key.compareTo((K) key);
                //当前节点的下一个节点小于查询值，当前节点向右移动
                if (cmp < 0) {
                    c = c.forwards[i];
                } else if (cmp == 0) {
                    //查询到了
                    return c.forwards[i].value;
                } else {
                    //当前节点的下一个节点大于查询值，当前节点向下移动
                    break;
                }
            }
        }
        //查询不到返回null
        return null;
    }

    @Override
    public V put(K key, V value) {
        Objects.requireNonNull(key);
        //新节点的高度
        final int newNodeLevel = randomLevel();
        Node<K, V> c = dummyHead;
        //新节点的后向结点（这里的后向是指小于新节点的方向），大小是新节点的高度，因为新节点的所有层都必须前后连接起来
        @SuppressWarnings("unchecked")
        Node<K, V>[] backwards = new Node[newNodeLevel];
        //从最高层开始向左下方遍历
        for (int i = currentMaxLevel - 1; i >= 0; i--) {
            while (c.forwards[i] != null) {
                final int cmp = c.forwards[i].key.compareTo(key);
                //当前节点的下一个节点小于要插入的节点K，更新当前节点，向左移动
                if (cmp < 0) {
                    c = c.forwards[i];
                } else if (cmp == 0) {
                    //等于的话，直接更新value即可返回
                    final V oldValue = c.forwards[i].value;
                    c.forwards[i].value = value;
                    return oldValue;
                } else {
                    break;
                }
            }
            //走到这里所以当前层的当前节点的下一个节点大于插入节点K了，所以把当节点为插入节点的上一个节点，保存之
            //但是当前层需要小于等新节点的层数才能保存，不然会越界，注意上面声明的大小
            if (i <= newNodeLevel - 1) {
                backwards[i] = c;
            }
        }
        //不存在，新建Node
        final Node<K, V> newNode = new Node<>(key, value, newNodeLevel);
        //依次连接每一层的索引（其实就是每一层的链表）
        for (int i = 0; i < newNodeLevel; i++) {
            newNode.forwards[i] = backwards[i].forwards[i];
            backwards[i].forwards[i] = newNode;
        }
        size++;
        return null;
    }

    @Override
    public Iterator<Map.Entry<K, V>> iterator() {
        return new SkipListMapIterator<>(0, this.dummyHead);
    }

    /**
     * 迭代器
     *
     * @param <K>
     * @param <V>
     */
    private static final class SkipListMapIterator<K, V> implements Iterator<Map.Entry<K, V>> {


        /**
         * 遍历的层级，一般全遍历就是0
         */
        private final int level;


        private Node<K, V> c;


        public SkipListMapIterator(int level, Node<K, V> dummyHead) {
            this.level = level;
            this.c = dummyHead;
        }


        @Override
        public boolean hasNext() {
            //下一个节点不为null即可继续
            return this.c.forwards[level] != null;
        }


        @Override
        public Entry<K, V> next() {
            //指向下一个节点，更新当前节点，返回
            Node<K, V> next = this.c.forwards[level];
            this.c = next;
            return next;
        }
    }

  // Iteration over the contents of a skip list
  class Iterator {
   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
  };

template <typename Key, class Comparator>
inline void SkipList<Key, Comparator>::Iterator::Seek(const Key& target) {
  node_ = list_->FindGreaterOrEqual(target, nullptr);
}


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)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != nullptr) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}