google / google/leveldb

Question about SkipList Insert

Open
#793 2 comments 0 reactions 0 assignees View on GitHub
Dominant language
C++
Stars
39.4k
Forks
8.2k
PR merge metrics
No merged PRs in 30d

Description

I'm wondering why the `SkipList::Insert` is not implemented as below
```diff
diff --git a/db/skiplist.h b/db/skiplist.h
index a59b45b..7982cdb 100644
--- a/db/skiplist.h
+++ b/db/skiplist.h
@@ -338,10 +338,10 @@ void SkipList::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);
+ Node* next = FindGreaterOrEqual(key, prev);

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

int height = RandomHeight();
if (height > GetMaxHeight()) {
@@ -358,12 +358,12 @@ void SkipList::Insert(const Key& key) {
max_height_.store(height, std::memory_order_relaxed);
}

- x = NewNode(key, height);
+ Node* curr = 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);
+ curr->NoBarrier_SetNext(i, next);
+ prev[i]->SetNext(i, curr);
}
}
```

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.