1/*
2 * Copyright 2011-present Facebook, Inc.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17// @author: Xin Liu <xliux@fb.com>
18//
19// A concurrent skip list (CSL) implementation.
20// Ref: http://www.cs.tau.ac.il/~shanir/nir-pubs-web/Papers/OPODIS2006-BA.pdf
21
22/*
23
24This implements a sorted associative container that supports only
25unique keys. (Similar to std::set.)
26
27Features:
28
29 1. Small memory overhead: ~40% less memory overhead compared with
30 std::set (1.6 words per node versus 3). It has an minimum of 4
31 words (7 words if there nodes got deleted) per-list overhead
32 though.
33
34 2. Read accesses (count, find iterator, skipper) are lock-free and
35 mostly wait-free (the only wait a reader may need to do is when
36 the node it is visiting is in a pending stage, i.e. deleting,
37 adding and not fully linked). Write accesses (remove, add) need
38 to acquire locks, but locks are local to the predecessor nodes
39 and/or successor nodes.
40
41 3. Good high contention performance, comparable single-thread
42 performance. In the multithreaded case (12 workers), CSL tested
43 10x faster than a RWSpinLocked std::set for an averaged sized
44 list (1K - 1M nodes).
45
46 Comparable read performance to std::set when single threaded,
47 especially when the list size is large, and scales better to
48 larger lists: when the size is small, CSL can be 20-50% slower on
49 find()/contains(). As the size gets large (> 1M elements),
50 find()/contains() can be 30% faster.
51
52 Iterating through a skiplist is similar to iterating through a
53 linked list, thus is much (2-6x) faster than on a std::set
54 (tree-based). This is especially true for short lists due to
55 better cache locality. Based on that, it's also faster to
56 intersect two skiplists.
57
58 4. Lazy removal with GC support. The removed nodes get deleted when
59 the last Accessor to the skiplist is destroyed.
60
61Caveats:
62
63 1. Write operations are usually 30% slower than std::set in a single
64 threaded environment.
65
66 2. Need to have a head node for each list, which has a 4 word
67 overhead.
68
69 3. When the list is quite small (< 1000 elements), single threaded
70 benchmarks show CSL can be 10x slower than std:set.
71
72 4. The interface requires using an Accessor to access the skiplist.
73 (See below.)
74
75 5. Currently x64 only, due to use of MicroSpinLock.
76
77 6. Freed nodes will not be reclaimed as long as there are ongoing
78 uses of the list.
79
80Sample usage:
81
82 typedef ConcurrentSkipList<int> SkipListT;
83 shared_ptr<SkipListT> sl(SkipListT::createInstance(init_head_height);
84 {
85 // It's usually good practice to hold an accessor only during
86 // its necessary life cycle (but not in a tight loop as
87 // Accessor creation incurs ref-counting overhead).
88 //
89 // Holding it longer delays garbage-collecting the deleted
90 // nodes in the list.
91 SkipListT::Accessor accessor(sl);
92 accessor.insert(23);
93 accessor.erase(2);
94 for (auto &elem : accessor) {
95 // use elem to access data
96 }
97 ... ...
98 }
99
100 Another useful type is the Skipper accessor. This is useful if you
101 want to skip to locations in the way std::lower_bound() works,
102 i.e. it can be used for going through the list by skipping to the
103 node no less than a specified key. The Skipper keeps its location as
104 state, which makes it convenient for things like implementing
105 intersection of two sets efficiently, as it can start from the last
106 visited position.
107
108 {
109 SkipListT::Accessor accessor(sl);
110 SkipListT::Skipper skipper(accessor);
111 skipper.to(30);
112 if (skipper) {
113 CHECK_LE(30, *skipper);
114 }
115 ... ...
116 // GC may happen when the accessor gets destructed.
117 }
118*/
119
120#pragma once
121
122#include <algorithm>
123#include <atomic>
124#include <limits>
125#include <memory>
126#include <type_traits>
127
128#include <boost/iterator/iterator_facade.hpp>
129#include <glog/logging.h>
130
131#include <folly/ConcurrentSkipList-inl.h>
132#include <folly/Likely.h>
133#include <folly/Memory.h>
134#include <folly/synchronization/MicroSpinLock.h>
135
136namespace folly {
137
138template <
139 typename T,
140 typename Comp = std::less<T>,
141 // All nodes are allocated using provided SysAllocator,
142 // it should be thread-safe.
143 typename NodeAlloc = SysAllocator<void>,
144 int MAX_HEIGHT = 24>
145class ConcurrentSkipList {
146 // MAX_HEIGHT needs to be at least 2 to suppress compiler
147 // warnings/errors (Werror=uninitialized tiggered due to preds_[1]
148 // being treated as a scalar in the compiler).
149 static_assert(
150 MAX_HEIGHT >= 2 && MAX_HEIGHT < 64,
151 "MAX_HEIGHT can only be in the range of [2, 64)");
152 typedef std::unique_lock<folly::MicroSpinLock> ScopedLocker;
153 typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
154
155 public:
156 typedef detail::SkipListNode<T> NodeType;
157 typedef T value_type;
158 typedef T key_type;
159
160 typedef detail::csl_iterator<value_type, NodeType> iterator;
161 typedef detail::csl_iterator<const value_type, const NodeType> const_iterator;
162
163 class Accessor;
164 class Skipper;
165
166 explicit ConcurrentSkipList(int height, const NodeAlloc& alloc)
167 : recycler_(alloc),
168 head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
169 size_(0) {}
170
171 explicit ConcurrentSkipList(int height)
172 : recycler_(),
173 head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
174 size_(0) {}
175
176 // Convenient function to get an Accessor to a new instance.
177 static Accessor create(int height, const NodeAlloc& alloc) {
178 return Accessor(createInstance(height, alloc));
179 }
180
181 static Accessor create(int height = 1) {
182 return Accessor(createInstance(height));
183 }
184
185 // Create a shared_ptr skiplist object with initial head height.
186 static std::shared_ptr<SkipListType> createInstance(
187 int height,
188 const NodeAlloc& alloc) {
189 return std::make_shared<ConcurrentSkipList>(height, alloc);
190 }
191
192 static std::shared_ptr<SkipListType> createInstance(int height = 1) {
193 return std::make_shared<ConcurrentSkipList>(height);
194 }
195
196 //===================================================================
197 // Below are implementation details.
198 // Please see ConcurrentSkipList::Accessor for stdlib-like APIs.
199 //===================================================================
200
201 ~ConcurrentSkipList() {
202 if /* constexpr */ (NodeType::template DestroyIsNoOp<NodeAlloc>::value) {
203 // Avoid traversing the list if using arena allocator.
204 return;
205 }
206 for (NodeType* current = head_.load(std::memory_order_relaxed); current;) {
207 NodeType* tmp = current->skip(0);
208 NodeType::destroy(recycler_.alloc(), current);
209 current = tmp;
210 }
211 }
212
213 private:
214 static bool greater(const value_type& data, const NodeType* node) {
215 return node && Comp()(node->data(), data);
216 }
217
218 static bool less(const value_type& data, const NodeType* node) {
219 return (node == nullptr) || Comp()(data, node->data());
220 }
221
222 static int findInsertionPoint(
223 NodeType* cur,
224 int cur_layer,
225 const value_type& data,
226 NodeType* preds[],
227 NodeType* succs[]) {
228 int foundLayer = -1;
229 NodeType* pred = cur;
230 NodeType* foundNode = nullptr;
231 for (int layer = cur_layer; layer >= 0; --layer) {
232 NodeType* node = pred->skip(layer);
233 while (greater(data, node)) {
234 pred = node;
235 node = node->skip(layer);
236 }
237 if (foundLayer == -1 && !less(data, node)) { // the two keys equal
238 foundLayer = layer;
239 foundNode = node;
240 }
241 preds[layer] = pred;
242
243 // if found, succs[0..foundLayer] need to point to the cached foundNode,
244 // as foundNode might be deleted at the same time thus pred->skip() can
245 // return nullptr or another node.
246 succs[layer] = foundNode ? foundNode : node;
247 }
248 return foundLayer;
249 }
250
251 size_t size() const {
252 return size_.load(std::memory_order_relaxed);
253 }
254
255 int height() const {
256 return head_.load(std::memory_order_consume)->height();
257 }
258
259 int maxLayer() const {
260 return height() - 1;
261 }
262
263 size_t incrementSize(int delta) {
264 return size_.fetch_add(delta, std::memory_order_relaxed) + delta;
265 }
266
267 // Returns the node if found, nullptr otherwise.
268 NodeType* find(const value_type& data) {
269 auto ret = findNode(data);
270 if (ret.second && !ret.first->markedForRemoval()) {
271 return ret.first;
272 }
273 return nullptr;
274 }
275
276 // lock all the necessary nodes for changing (adding or removing) the list.
277 // returns true if all the lock acquried successfully and the related nodes
278 // are all validate (not in certain pending states), false otherwise.
279 bool lockNodesForChange(
280 int nodeHeight,
281 ScopedLocker guards[MAX_HEIGHT],
282 NodeType* preds[MAX_HEIGHT],
283 NodeType* succs[MAX_HEIGHT],
284 bool adding = true) {
285 NodeType *pred, *succ, *prevPred = nullptr;
286 bool valid = true;
287 for (int layer = 0; valid && layer < nodeHeight; ++layer) {
288 pred = preds[layer];
289 DCHECK(pred != nullptr) << "layer=" << layer << " height=" << height()
290 << " nodeheight=" << nodeHeight;
291 succ = succs[layer];
292 if (pred != prevPred) {
293 guards[layer] = pred->acquireGuard();
294 prevPred = pred;
295 }
296 valid = !pred->markedForRemoval() &&
297 pred->skip(layer) == succ; // check again after locking
298
299 if (adding) { // when adding a node, the succ shouldn't be going away
300 valid = valid && (succ == nullptr || !succ->markedForRemoval());
301 }
302 }
303
304 return valid;
305 }
306
307 // Returns a paired value:
308 // pair.first always stores the pointer to the node with the same input key.
309 // It could be either the newly added data, or the existed data in the
310 // list with the same key.
311 // pair.second stores whether the data is added successfully:
312 // 0 means not added, otherwise reutrns the new size.
313 template <typename U>
314 std::pair<NodeType*, size_t> addOrGetData(U&& data) {
315 NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
316 NodeType* newNode;
317 size_t newSize;
318 while (true) {
319 int max_layer = 0;
320 int layer = findInsertionPointGetMaxLayer(data, preds, succs, &max_layer);
321
322 if (layer >= 0) {
323 NodeType* nodeFound = succs[layer];
324 DCHECK(nodeFound != nullptr);
325 if (nodeFound->markedForRemoval()) {
326 continue; // if it's getting deleted retry finding node.
327 }
328 // wait until fully linked.
329 while (UNLIKELY(!nodeFound->fullyLinked())) {
330 }
331 return std::make_pair(nodeFound, 0);
332 }
333
334 // need to capped at the original height -- the real height may have grown
335 int nodeHeight =
336 detail::SkipListRandomHeight::instance()->getHeight(max_layer + 1);
337
338 ScopedLocker guards[MAX_HEIGHT];
339 if (!lockNodesForChange(nodeHeight, guards, preds, succs)) {
340 continue; // give up the locks and retry until all valid
341 }
342
343 // locks acquired and all valid, need to modify the links under the locks.
344 newNode = NodeType::create(
345 recycler_.alloc(), nodeHeight, std::forward<U>(data));
346 for (int k = 0; k < nodeHeight; ++k) {
347 newNode->setSkip(k, succs[k]);
348 preds[k]->setSkip(k, newNode);
349 }
350
351 newNode->setFullyLinked();
352 newSize = incrementSize(1);
353 break;
354 }
355
356 int hgt = height();
357 size_t sizeLimit =
358 detail::SkipListRandomHeight::instance()->getSizeLimit(hgt);
359
360 if (hgt < MAX_HEIGHT && newSize > sizeLimit) {
361 growHeight(hgt + 1);
362 }
363 CHECK_GT(newSize, 0);
364 return std::make_pair(newNode, newSize);
365 }
366
367 bool remove(const value_type& data) {
368 NodeType* nodeToDelete = nullptr;
369 ScopedLocker nodeGuard;
370 bool isMarked = false;
371 int nodeHeight = 0;
372 NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
373
374 while (true) {
375 int max_layer = 0;
376 int layer = findInsertionPointGetMaxLayer(data, preds, succs, &max_layer);
377 if (!isMarked && (layer < 0 || !okToDelete(succs[layer], layer))) {
378 return false;
379 }
380
381 if (!isMarked) {
382 nodeToDelete = succs[layer];
383 nodeHeight = nodeToDelete->height();
384 nodeGuard = nodeToDelete->acquireGuard();
385 if (nodeToDelete->markedForRemoval()) {
386 return false;
387 }
388 nodeToDelete->setMarkedForRemoval();
389 isMarked = true;
390 }
391
392 // acquire pred locks from bottom layer up
393 ScopedLocker guards[MAX_HEIGHT];
394 if (!lockNodesForChange(nodeHeight, guards, preds, succs, false)) {
395 continue; // this will unlock all the locks
396 }
397
398 for (int k = nodeHeight - 1; k >= 0; --k) {
399 preds[k]->setSkip(k, nodeToDelete->skip(k));
400 }
401
402 incrementSize(-1);
403 break;
404 }
405 recycle(nodeToDelete);
406 return true;
407 }
408
409 const value_type* first() const {
410 auto node = head_.load(std::memory_order_consume)->skip(0);
411 return node ? &node->data() : nullptr;
412 }
413
414 const value_type* last() const {
415 NodeType* pred = head_.load(std::memory_order_consume);
416 NodeType* node = nullptr;
417 for (int layer = maxLayer(); layer >= 0; --layer) {
418 do {
419 node = pred->skip(layer);
420 if (node) {
421 pred = node;
422 }
423 } while (node != nullptr);
424 }
425 return pred == head_.load(std::memory_order_relaxed) ? nullptr
426 : &pred->data();
427 }
428
429 static bool okToDelete(NodeType* candidate, int layer) {
430 DCHECK(candidate != nullptr);
431 return candidate->fullyLinked() && candidate->maxLayer() == layer &&
432 !candidate->markedForRemoval();
433 }
434
435 // find node for insertion/deleting
436 int findInsertionPointGetMaxLayer(
437 const value_type& data,
438 NodeType* preds[],
439 NodeType* succs[],
440 int* max_layer) const {
441 *max_layer = maxLayer();
442 return findInsertionPoint(
443 head_.load(std::memory_order_consume), *max_layer, data, preds, succs);
444 }
445
446 // Find node for access. Returns a paired values:
447 // pair.first = the first node that no-less than data value
448 // pair.second = 1 when the data value is founded, or 0 otherwise.
449 // This is like lower_bound, but not exact: we could have the node marked for
450 // removal so still need to check that.
451 std::pair<NodeType*, int> findNode(const value_type& data) const {
452 return findNodeDownRight(data);
453 }
454
455 // Find node by first stepping down then stepping right. Based on benchmark
456 // results, this is slightly faster than findNodeRightDown for better
457 // localality on the skipping pointers.
458 std::pair<NodeType*, int> findNodeDownRight(const value_type& data) const {
459 NodeType* pred = head_.load(std::memory_order_consume);
460 int ht = pred->height();
461 NodeType* node = nullptr;
462
463 bool found = false;
464 while (!found) {
465 // stepping down
466 for (; ht > 0 && less(data, node = pred->skip(ht - 1)); --ht) {
467 }
468 if (ht == 0) {
469 return std::make_pair(node, 0); // not found
470 }
471 // node <= data now, but we need to fix up ht
472 --ht;
473
474 // stepping right
475 while (greater(data, node)) {
476 pred = node;
477 node = node->skip(ht);
478 }
479 found = !less(data, node);
480 }
481 return std::make_pair(node, found);
482 }
483
484 // find node by first stepping right then stepping down.
485 // We still keep this for reference purposes.
486 std::pair<NodeType*, int> findNodeRightDown(const value_type& data) const {
487 NodeType* pred = head_.load(std::memory_order_consume);
488 NodeType* node = nullptr;
489 auto top = maxLayer();
490 int found = 0;
491 for (int layer = top; !found && layer >= 0; --layer) {
492 node = pred->skip(layer);
493 while (greater(data, node)) {
494 pred = node;
495 node = node->skip(layer);
496 }
497 found = !less(data, node);
498 }
499 return std::make_pair(node, found);
500 }
501
502 NodeType* lower_bound(const value_type& data) const {
503 auto node = findNode(data).first;
504 while (node != nullptr && node->markedForRemoval()) {
505 node = node->skip(0);
506 }
507 return node;
508 }
509
510 void growHeight(int height) {
511 NodeType* oldHead = head_.load(std::memory_order_consume);
512 if (oldHead->height() >= height) { // someone else already did this
513 return;
514 }
515
516 NodeType* newHead =
517 NodeType::create(recycler_.alloc(), height, value_type(), true);
518
519 { // need to guard the head node in case others are adding/removing
520 // nodes linked to the head.
521 ScopedLocker g = oldHead->acquireGuard();
522 newHead->copyHead(oldHead);
523 NodeType* expected = oldHead;
524 if (!head_.compare_exchange_strong(
525 expected, newHead, std::memory_order_release)) {
526 // if someone has already done the swap, just return.
527 NodeType::destroy(recycler_.alloc(), newHead);
528 return;
529 }
530 oldHead->setMarkedForRemoval();
531 }
532 recycle(oldHead);
533 }
534
535 void recycle(NodeType* node) {
536 recycler_.add(node);
537 }
538
539 detail::NodeRecycler<NodeType, NodeAlloc> recycler_;
540 std::atomic<NodeType*> head_;
541 std::atomic<size_t> size_;
542};
543
544template <typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT>
545class ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT>::Accessor {
546 typedef detail::SkipListNode<T> NodeType;
547 typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
548
549 public:
550 typedef T value_type;
551 typedef T key_type;
552 typedef T& reference;
553 typedef T* pointer;
554 typedef const T& const_reference;
555 typedef const T* const_pointer;
556 typedef size_t size_type;
557 typedef Comp key_compare;
558 typedef Comp value_compare;
559
560 typedef typename SkipListType::iterator iterator;
561 typedef typename SkipListType::const_iterator const_iterator;
562 typedef typename SkipListType::Skipper Skipper;
563
564 explicit Accessor(std::shared_ptr<ConcurrentSkipList> skip_list)
565 : slHolder_(std::move(skip_list)) {
566 sl_ = slHolder_.get();
567 DCHECK(sl_ != nullptr);
568 sl_->recycler_.addRef();
569 }
570
571 // Unsafe initializer: the caller assumes the responsibility to keep
572 // skip_list valid during the whole life cycle of the Acessor.
573 explicit Accessor(ConcurrentSkipList* skip_list) : sl_(skip_list) {
574 DCHECK(sl_ != nullptr);
575 sl_->recycler_.addRef();
576 }
577
578 Accessor(const Accessor& accessor)
579 : sl_(accessor.sl_), slHolder_(accessor.slHolder_) {
580 sl_->recycler_.addRef();
581 }
582
583 Accessor& operator=(const Accessor& accessor) {
584 if (this != &accessor) {
585 slHolder_ = accessor.slHolder_;
586 sl_->recycler_.releaseRef();
587 sl_ = accessor.sl_;
588 sl_->recycler_.addRef();
589 }
590 return *this;
591 }
592
593 ~Accessor() {
594 sl_->recycler_.releaseRef();
595 }
596
597 bool empty() const {
598 return sl_->size() == 0;
599 }
600 size_t size() const {
601 return sl_->size();
602 }
603 size_type max_size() const {
604 return std::numeric_limits<size_type>::max();
605 }
606
607 // returns end() if the value is not in the list, otherwise returns an
608 // iterator pointing to the data, and it's guaranteed that the data is valid
609 // as far as the Accessor is hold.
610 iterator find(const key_type& value) {
611 return iterator(sl_->find(value));
612 }
613 const_iterator find(const key_type& value) const {
614 return iterator(sl_->find(value));
615 }
616 size_type count(const key_type& data) const {
617 return contains(data);
618 }
619
620 iterator begin() const {
621 NodeType* head = sl_->head_.load(std::memory_order_consume);
622 return iterator(head->next());
623 }
624 iterator end() const {
625 return iterator(nullptr);
626 }
627 const_iterator cbegin() const {
628 return begin();
629 }
630 const_iterator cend() const {
631 return end();
632 }
633
634 template <
635 typename U,
636 typename =
637 typename std::enable_if<std::is_convertible<U, T>::value>::type>
638 std::pair<iterator, bool> insert(U&& data) {
639 auto ret = sl_->addOrGetData(std::forward<U>(data));
640 return std::make_pair(iterator(ret.first), ret.second);
641 }
642 size_t erase(const key_type& data) {
643 return remove(data);
644 }
645
646 iterator lower_bound(const key_type& data) const {
647 return iterator(sl_->lower_bound(data));
648 }
649
650 size_t height() const {
651 return sl_->height();
652 }
653
654 // first() returns pointer to the first element in the skiplist, or
655 // nullptr if empty.
656 //
657 // last() returns the pointer to the last element in the skiplist,
658 // nullptr if list is empty.
659 //
660 // Note: As concurrent writing can happen, first() is not
661 // guaranteed to be the min_element() in the list. Similarly
662 // last() is not guaranteed to be the max_element(), and both of them can
663 // be invalid (i.e. nullptr), so we name them differently from front() and
664 // tail() here.
665 const key_type* first() const {
666 return sl_->first();
667 }
668 const key_type* last() const {
669 return sl_->last();
670 }
671
672 // Try to remove the last element in the skip list.
673 //
674 // Returns true if we removed it, false if either the list is empty
675 // or a race condition happened (i.e. the used-to-be last element
676 // was already removed by another thread).
677 bool pop_back() {
678 auto last = sl_->last();
679 return last ? sl_->remove(*last) : false;
680 }
681
682 std::pair<key_type*, bool> addOrGetData(const key_type& data) {
683 auto ret = sl_->addOrGetData(data);
684 return std::make_pair(&ret.first->data(), ret.second);
685 }
686
687 SkipListType* skiplist() const {
688 return sl_;
689 }
690
691 // legacy interfaces
692 // TODO:(xliu) remove these.
693 // Returns true if the node is added successfully, false if not, i.e. the
694 // node with the same key already existed in the list.
695 bool contains(const key_type& data) const {
696 return sl_->find(data);
697 }
698 bool add(const key_type& data) {
699 return sl_->addOrGetData(data).second;
700 }
701 bool remove(const key_type& data) {
702 return sl_->remove(data);
703 }
704
705 private:
706 SkipListType* sl_;
707 std::shared_ptr<SkipListType> slHolder_;
708};
709
710// implements forward iterator concept.
711template <typename ValT, typename NodeT>
712class detail::csl_iterator : public boost::iterator_facade<
713 csl_iterator<ValT, NodeT>,
714 ValT,
715 boost::forward_traversal_tag> {
716 public:
717 typedef ValT value_type;
718 typedef value_type& reference;
719 typedef value_type* pointer;
720 typedef ptrdiff_t difference_type;
721
722 explicit csl_iterator(NodeT* node = nullptr) : node_(node) {}
723
724 template <typename OtherVal, typename OtherNode>
725 csl_iterator(
726 const csl_iterator<OtherVal, OtherNode>& other,
727 typename std::enable_if<
728 std::is_convertible<OtherVal, ValT>::value>::type* = nullptr)
729 : node_(other.node_) {}
730
731 size_t nodeSize() const {
732 return node_ == nullptr ? 0
733 : node_->height() * sizeof(NodeT*) + sizeof(*this);
734 }
735
736 bool good() const {
737 return node_ != nullptr;
738 }
739
740 private:
741 friend class boost::iterator_core_access;
742 template <class, class>
743 friend class csl_iterator;
744
745 void increment() {
746 node_ = node_->next();
747 }
748 bool equal(const csl_iterator& other) const {
749 return node_ == other.node_;
750 }
751 value_type& dereference() const {
752 return node_->data();
753 }
754
755 NodeT* node_;
756};
757
758// Skipper interface
759template <typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT>
760class ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT>::Skipper {
761 typedef detail::SkipListNode<T> NodeType;
762 typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
763 typedef typename SkipListType::Accessor Accessor;
764
765 public:
766 typedef T value_type;
767 typedef T& reference;
768 typedef T* pointer;
769 typedef ptrdiff_t difference_type;
770
771 Skipper(const std::shared_ptr<SkipListType>& skipList) : accessor_(skipList) {
772 init();
773 }
774
775 Skipper(const Accessor& accessor) : accessor_(accessor) {
776 init();
777 }
778
779 void init() {
780 // need to cache the head node
781 NodeType* head_node = head();
782 headHeight_ = head_node->height();
783 for (int i = 0; i < headHeight_; ++i) {
784 preds_[i] = head_node;
785 succs_[i] = head_node->skip(i);
786 }
787 int max_layer = maxLayer();
788 for (int i = 0; i < max_layer; ++i) {
789 hints_[i] = uint8_t(i + 1);
790 }
791 hints_[max_layer] = max_layer;
792 }
793
794 // advance to the next node in the list.
795 Skipper& operator++() {
796 preds_[0] = succs_[0];
797 succs_[0] = preds_[0]->skip(0);
798 int height = curHeight();
799 for (int i = 1; i < height && preds_[0] == succs_[i]; ++i) {
800 preds_[i] = succs_[i];
801 succs_[i] = preds_[i]->skip(i);
802 }
803 return *this;
804 }
805
806 bool good() const {
807 return succs_[0] != nullptr;
808 }
809
810 int maxLayer() const {
811 return headHeight_ - 1;
812 }
813
814 int curHeight() const {
815 // need to cap the height to the cached head height, as the current node
816 // might be some newly inserted node and also during the time period the
817 // head height may have grown.
818 return succs_[0] ? std::min(headHeight_, succs_[0]->height()) : 0;
819 }
820
821 const value_type& data() const {
822 DCHECK(succs_[0] != nullptr);
823 return succs_[0]->data();
824 }
825
826 value_type& operator*() const {
827 DCHECK(succs_[0] != nullptr);
828 return succs_[0]->data();
829 }
830
831 value_type* operator->() {
832 DCHECK(succs_[0] != nullptr);
833 return &succs_[0]->data();
834 }
835
836 /*
837 * Skip to the position whose data is no less than the parameter.
838 * (I.e. the lower_bound).
839 *
840 * Returns true if the data is found, false otherwise.
841 */
842 bool to(const value_type& data) {
843 int layer = curHeight() - 1;
844 if (layer < 0) {
845 return false; // reaches the end of the list
846 }
847
848 int lyr = hints_[layer];
849 int max_layer = maxLayer();
850 while (SkipListType::greater(data, succs_[lyr]) && lyr < max_layer) {
851 ++lyr;
852 }
853 hints_[layer] = lyr; // update the hint
854
855 int foundLayer = SkipListType::findInsertionPoint(
856 preds_[lyr], lyr, data, preds_, succs_);
857 if (foundLayer < 0) {
858 return false;
859 }
860
861 DCHECK(succs_[0] != nullptr)
862 << "lyr=" << lyr << "; max_layer=" << max_layer;
863 return !succs_[0]->markedForRemoval();
864 }
865
866 private:
867 NodeType* head() const {
868 return accessor_.skiplist()->head_.load(std::memory_order_consume);
869 }
870
871 Accessor accessor_;
872 int headHeight_;
873 NodeType *succs_[MAX_HEIGHT], *preds_[MAX_HEIGHT];
874 uint8_t hints_[MAX_HEIGHT];
875};
876
877} // namespace folly
878