Question about SkipList Insert
- 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
Assessment
This issue has not been assessed yet.