// 返回层级最前的节点，该节点位于键的位置或之后。如果没有这样的节点，返回nullptr。如果prev不是空的，则在[0...max_height_1]中的每一级，将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。
template <typename Key, class Comparator>
typename SkipList<Key, Comparator>::Node*
SkipList<Key, Comparator>::FindGreaterOrEqual(const Key& key,
Node** prev) const {
  Node* x = head_;
  // 防止无限for循环
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // 如果当前节点在层级之后，则查找下一个链表节点
      x = next;
    } else {
      if (prev != nullptr) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // 层级下沉
        level--;
      }
    }
  }
}

template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key& key) {
  // 因为前置节点最多有kMaxHeight层，所以直接使用kMaxHeight 简单粗暴
  Node* prev[kMaxHeight];
  // 返回层级最前的节点，该节点位于键的位置或之后。如果没有这样的节点，返回nullptr。如果prev不是空的，则在[0...max_height_1]中的每一级，将prev[level]的指针填充到前一个 节点的指针来填充[0...max_height_1]中的每一级的 "level"。
  Node* x = FindGreaterOrEqual(key, prev);
  // 不允许进行重复插入操作（同步加锁）
  assert(x == nullptr || !Equal(key, x->key));
  // **新增层级选举**，使用随机函数和最高层级限制，按照类似抛硬币的规则选择是否新增层级。
  // 随机获取一个 level 值
  int height = RandomHeight();
  // 当前随机level是否大于 当前点跳表层数
  if (height > GetMaxHeight()) {
    // 头指针下探到最低层
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    /*
    这部分建议多读读原注释。
    机器翻译：在没有任何同步的情况下突变max_height_是可以的。与并发读取器之间没有任何同步。一个并发的读者在观察到的新值的并发读者将看到max_height_的旧值。的新水平指针（nullptr），或者在下面的循环中设置一个新的值。下面的循环中设置的新值。在前一种情况下，读者将立即下降到下一个级别，因为nullptr会在所有的键之后。在后一种情况下，读取器将使用新的节点
    理解：意思是说这一步不需要并发加锁，这是因为并发读读取到更新的跳表层数，哪怕现在这个节点没有插入，也会返回nullptr，在leveldb的比较器当中的nullpt会在最前面，默认看作比所有的key都要大，所以会往下继续找，这样就可以保证写入和读取都是符合预期的。
    */
    max_height_.store(height, std::memory_order_relaxed);
  }
  // 新增跳表节点
  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
  // NoBarrier_SetNext()就够了，因为当我们在prev[i]中发布一个指针 "x "时，我们会添加一个障碍。我们在prev[i]中发布一个指向 "x "的指针。
    // 更新指针引用
    // 为了保证并发读的准确性，需要先设置节点指针然后再设置原始表的prev 指针
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    // 内部会强制进行同步
    prev[i]->SetNext(i, x);
  }
}

template <typename Key, class Comparator>
int SkipList<Key, Comparator>::RandomHeight() {
  // 在kBranching中以1的概率增加高度
  static const unsigned int kBranching = 4;
  int height = 1;
  // rnd_.OneIn(kBranching):"1/n "的时间会返回真没其他情况会返回假
  // 相当于层数会按照4 的倍数减小， 4层是3层的4分之一，简单理解为 每次加一层概率就要乘一个 1/4。
  while (height < kMaxHeight && rnd_.OneIn(kBranching)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxHeight);
  return height;
}

// 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();

// Return the latest node with a key < key.
// Return head_ if there is no such node.
Node* FindLessThan(const Key& key) const;
// Return the last node in the list.
// Return head_ if list is empty.
Node* FindLast() const;