Зачем skiplist в leveldb нужно использовать `prev-> next` при вставке? - PullRequest
Новая
       139

Зачем skiplist в leveldb нужно использовать `prev-> next` при вставке?

0 голосов
/ 02 апреля 2020

Я просто вставляю исходный код Inert ниже: 

template <typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const 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);

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

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    // 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_ (nullptr), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since nullptr sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.store(height, std::memory_order_relaxed);
  }

  x = NewNode(key, height);
  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);
  }
}

Я запутался, зачем нужен x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));. Я думал, что prev[i]->NoBarrier_Next(i) равно x в x = FindGreaterOrEqual(key, prev))

Почему бы просто: 

template<typename Key, class Comparator>
void SkipList<Key, Comparator>::Insert(const Key &key) {
  Node *prev[kMaxHeight];
  /* 
   * original version:
   * Node *x = FindGreaterOrEqual(key, prev);
   */
  Node *next = FindGreaterOrEqual(key, prev);

  int height = RandomHeight();
  if (GetMaxHeight() < height) {
    for (int i = GetMaxHeight(); i < height; ++i) {
      head_->SetNext(i, next);
    }
    max_height_.store(height, std::memory_order_relaxed);
  }

  Node* curr = NewNode(key, height);
  for (int i = 0; i < height; ++i) {
    /* 
     * original version:
     * x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
     */ 
    curr->NoBarrier_SetNext(i, next);
    prev[i]->SetNext(i, curr);
  }
}

При каких обстоятельствах эти две переменные будут различаться?

...