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 | |
24 | This implements a sorted associative container that supports only |
25 | unique keys. (Similar to std::set.) |
26 | |
27 | Features: |
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 | |
61 | Caveats: |
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 | |
80 | Sample 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 | |
136 | namespace folly { |
137 | |
138 | template < |
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> |
145 | class 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 | |
544 | template <typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT> |
545 | class 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. |
711 | template <typename ValT, typename NodeT> |
712 | class 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 |
759 | template <typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT> |
760 | class 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 | |