Dec 7, 2025

[C++][Data structure] concurrent skip list.

Here SkipListNode initialize the size to size of SkipListNode + hight of the skiplist node.
https://github.com/facebook/folly/blob/d2e6fe65dfd6b30a9d504d0409ac733cbaa73125/folly/ConcurrentSkipList-inl.h#L66

size_t size =
	sizeof(SkipListNode) + height * sizeof(std::atomic<SkipListNode*>);

This is the clever trick used in C, while SkipListNode has the last data member declared of size 0 array. i.e. if the hight of the SkipListNode is 5, the size of SkipListNode is
SkipListNode + 5 * sizeof(std::atomic),
thus we could access skip_[4] without out-of-idx-bound.
std::atomic<SkipListNode*> skip_[0];
https://github.com/facebook/folly/blob/d2e6fe65dfd6b30a9d504d0409ac733cbaa73125/folly/ConcurrentSkipList-inl.h#L173

Hense std::atomic skip_[0] is malloc not through constructor, when SkipListNode is destructed, should call `skip_[i].~atomic()` manually. (i.e. destruct atomic before its memory being deallocated.)
~SkipListNode() {
	for (uint8_t i = 0; i < height_; ++i) {
      skip_[i].~atomic();
    }
}

No comments:

Post a Comment

Note: Only a member of this blog may post a comment.