37 template<
typename Key,
class Comparator>
108 return static_cast<int>(
143 template<
typename Key,
class Comparator>
155 return reinterpret_cast<Node*
>(next_[n].Acquire_Load());
161 next_[n].Release_Store(x);
167 return reinterpret_cast<Node*
>(next_[n].NoBarrier_Load());
171 next_[n].NoBarrier_Store(x);
179 template<
typename Key,
class Comparator>
182 char*
mem = arena_->AllocateAligned(
187 template<
typename Key,
class Comparator>
193 template<
typename Key,
class Comparator>
195 return node_ != NULL;
198 template<
typename Key,
class Comparator>
204 template<
typename Key,
class Comparator>
207 node_ = node_->Next(0);
210 template<
typename Key,
class Comparator>
215 node_ =
list_->FindLessThan(node_->key);
216 if (node_ ==
list_->head_) {
221 template<
typename Key,
class Comparator>
223 node_ =
list_->FindGreaterOrEqual(target, NULL);
226 template<
typename Key,
class Comparator>
228 node_ =
list_->head_->Next(0);
231 template<
typename Key,
class Comparator>
233 node_ =
list_->FindLast();
234 if (node_ ==
list_->head_) {
239 template<
typename Key,
class Comparator>
242 static const unsigned int kBranching = 4;
252 template<
typename Key,
class Comparator>
258 template<
typename Key,
class Comparator>
269 if (prev != NULL) prev[level] = x;
280 template<
typename Key,
class Comparator>
288 if (next == NULL ||
compare_(next->
key, key) >= 0) {
301 template<
typename Key,
class Comparator>
321 template<
typename Key,
class Comparator>
333 template<
typename Key,
class Comparator>
338 Node* x = FindGreaterOrEqual(key, prev);
341 assert(x == NULL || !Equal(key, x->
key));
343 int height = RandomHeight();
344 if (height > GetMaxHeight()) {
345 for (
int i = GetMaxHeight(); i < height; i++) {
357 max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
360 x = NewNode(key, height);
361 for (
int i = 0; i < height; i++) {
369 template<
typename Key,
class Comparator>
371 Node* x = FindGreaterOrEqual(key, NULL);
372 if (x != NULL && Equal(key, x->
key)) {
void Seek(const Key &target)
void SetNext(int n, Node *x)
bool Equal(const Key &a, const Key &b) const
Node * NoBarrier_Next(int n)
void * NoBarrier_Load() const
SkipList(Comparator cmp, Arena *arena)
port::AtomicPointer max_height_
Node * FindGreaterOrEqual(const Key &key, Node **prev) const
void Insert(const Key &key)
Comparator const compare_
bool Contains(const Key &key) const
void NoBarrier_SetNext(int n, Node *x)
void operator=(const SkipList &)
bool KeyIsAfterNode(const Key &key, Node *n) const
Iterator(const SkipList *list)
Node * FindLessThan(const Key &key) const
Node * NewNode(const Key &key, int height)