2 * Copyright 2013 Facebook, Inc.
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
8 * http://www.apache.org/licenses/LICENSE-2.0
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.
17 // @author: Xin Liu <xliux@fb.com>
19 #ifndef FOLLY_CONCURRENTSKIPLIST_INL_H_
20 #define FOLLY_CONCURRENTSKIPLIST_INL_H_
25 #include <boost/random.hpp>
27 #include <glog/logging.h>
28 #include "folly/SmallLocks.h"
29 #include "folly/ThreadLocal.h"
31 namespace folly { namespace detail {
33 template<typename ValT, typename NodeT> class csl_iterator;
36 class SkipListNode : boost::noncopyable {
39 MARKED_FOR_REMOVAL = (1 << 1),
40 FULLY_LINKED = (1 << 2),
46 typename=typename std::enable_if<std::is_convertible<U, T>::value>::type>
47 static SkipListNode* create(int height, U&& data, bool isHead = false) {
48 DCHECK(height >= 1 && height < 64) << height;
50 size_t size = sizeof(SkipListNode) +
51 height * sizeof(std::atomic<SkipListNode*>);
52 auto* node = static_cast<SkipListNode*>(malloc(size));
54 new (node) SkipListNode(height, std::forward<U>(data), isHead);
58 static void destroy(SkipListNode* node) {
59 node->~SkipListNode();
63 // copy the head node to a new head node assuming lock acquired
64 SkipListNode* copyHead(SkipListNode* node) {
65 DCHECK(node != nullptr && height_ > node->height_);
66 setFlags(node->getFlags());
67 for (int i = 0; i < node->height_; ++i) {
68 setSkip(i, node->skip(i));
73 inline SkipListNode* skip(int layer) const {
74 DCHECK_LT(layer, height_);
75 return skip_[layer].load(std::memory_order_consume);
78 // next valid node as in the linked list
79 SkipListNode* next() {
82 (node != nullptr && node->markedForRemoval());
83 node = node->skip(0)) {}
87 void setSkip(uint8_t h, SkipListNode* next) {
88 DCHECK_LT(h, height_);
89 skip_[h].store(next, std::memory_order_release);
92 value_type& data() { return data_; }
93 const value_type& data() const { return data_; }
94 int maxLayer() const { return height_ - 1; }
95 int height() const { return height_; }
97 std::unique_lock<MicroSpinLock> acquireGuard() {
98 return std::unique_lock<MicroSpinLock>(spinLock_);
101 bool fullyLinked() const { return getFlags() & FULLY_LINKED; }
102 bool markedForRemoval() const { return getFlags() & MARKED_FOR_REMOVAL; }
103 bool isHeadNode() const { return getFlags() & IS_HEAD_NODE; }
105 void setIsHeadNode() {
106 setFlags(getFlags() | IS_HEAD_NODE);
108 void setFullyLinked() {
109 setFlags(getFlags() | FULLY_LINKED);
111 void setMarkedForRemoval() {
112 setFlags(getFlags() | MARKED_FOR_REMOVAL);
116 // Note! this can only be called from create() as a placement new.
118 SkipListNode(uint8_t height, U&& data, bool isHead) :
119 height_(height), data_(std::forward<U>(data)) {
122 if (isHead) setIsHeadNode();
123 // need to explicitly init the dynamic atomic pointer array
124 for (uint8_t i = 0; i < height_; ++i) {
125 new (&skip_[i]) std::atomic<SkipListNode*>(nullptr);
130 for (uint8_t i = 0; i < height_; ++i) {
135 uint16_t getFlags() const {
136 return flags_.load(std::memory_order_consume);
138 void setFlags(uint16_t flags) {
139 flags_.store(flags, std::memory_order_release);
142 // TODO(xliu): on x86_64, it's possible to squeeze these into
143 // skip_[0] to maybe save 8 bytes depending on the data alignments.
144 // NOTE: currently this is x86_64 only anyway, due to the
146 std::atomic<uint16_t> flags_;
147 const uint8_t height_;
148 MicroSpinLock spinLock_;
152 std::atomic<SkipListNode*> skip_[0];
155 class SkipListRandomHeight {
156 enum { kMaxHeight = 64 };
158 // make it a singleton.
159 static SkipListRandomHeight *instance() {
160 static SkipListRandomHeight instance_;
164 int getHeight(int maxHeight) const {
165 DCHECK_LE(maxHeight, kMaxHeight) << "max height too big!";
166 double p = randomProb();
167 for (int i = 0; i < maxHeight; ++i) {
168 if (p < lookupTable_[i]) {
175 size_t getSizeLimit(int height) const {
176 DCHECK_LT(height, kMaxHeight);
177 return sizeLimitTable_[height];
182 SkipListRandomHeight() { initLookupTable(); }
184 void initLookupTable() {
185 // set skip prob = 1/E
186 static const double kProbInv = exp(1);
187 static const double kProb = 1.0 / kProbInv;
188 static const size_t kMaxSizeLimit = std::numeric_limits<size_t>::max();
190 double sizeLimit = 1;
191 double p = lookupTable_[0] = (1 - kProb);
192 sizeLimitTable_[0] = 1;
193 for (int i = 1; i < kMaxHeight - 1; ++i) {
195 sizeLimit *= kProbInv;
196 lookupTable_[i] = lookupTable_[i - 1] + p;
197 sizeLimitTable_[i] = sizeLimit > kMaxSizeLimit ?
199 static_cast<size_t>(sizeLimit);
201 lookupTable_[kMaxHeight - 1] = 1;
202 sizeLimitTable_[kMaxHeight - 1] = kMaxSizeLimit;
205 static double randomProb() {
206 static ThreadLocal<boost::lagged_fibonacci2281> rng_;
210 double lookupTable_[kMaxHeight];
211 size_t sizeLimitTable_[kMaxHeight];
216 #endif // FOLLY_CONCURRENTSKIPLIST_INL_H_