folly/ConcurrentSkipList-inl.h

   1 /*
   2  * Copyright 2013 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 #ifndef FOLLY_CONCURRENTSKIPLIST_INL_H_
  20 #define FOLLY_CONCURRENTSKIPLIST_INL_H_
  21
  22 #include <algorithm>
  23 #include <climits>
  24 #include <cmath>
  25 #include <boost/random.hpp>
  26
  27 #include <glog/logging.h>
  28 #include "folly/SmallLocks.h"
  29 #include "folly/ThreadLocal.h"
  30
  31 namespace folly { namespace detail {
  32
  33 template<typename ValT, typename NodeT> class csl_iterator;
  34
  35 template<typename T>
  36 class SkipListNode : boost::noncopyable {
  37   enum {
  38     IS_HEAD_NODE = 1,
  39     MARKED_FOR_REMOVAL = (1 << 1),
  40     FULLY_LINKED = (1 << 2),
  41   };
  42  public:
  43   typedef T value_type;
  44
  45   template<typename U,
  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;
  49
  50     size_t size = sizeof(SkipListNode) +
  51       height * sizeof(std::atomic<SkipListNode*>);
  52     auto* node = static_cast<SkipListNode*>(malloc(size));
  53     // do placement new
  54     new (node) SkipListNode(height, std::forward<U>(data), isHead);
  55     return node;
  56   }
  57
  58   static void destroy(SkipListNode* node) {
  59     node->~SkipListNode();
  60     free(node);
  61   }
  62
  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));
  69     }
  70     return this;
  71   }
  72
  73   inline SkipListNode* skip(int layer) const {
  74     DCHECK_LT(layer, height_);
  75     return skip_[layer].load(std::memory_order_consume);
  76   }
  77
  78   // next valid node as in the linked list
  79   SkipListNode* next() {
  80     SkipListNode* node;
  81     for (node = skip(0);
  82         (node != nullptr && node->markedForRemoval());
  83         node = node->skip(0)) {}
  84     return node;
  85   }
  86
  87   void setSkip(uint8_t h, SkipListNode* next) {
  88     DCHECK_LT(h, height_);
  89     skip_[h].store(next, std::memory_order_release);
  90   }
  91
  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_; }
  96
  97   std::unique_lock<MicroSpinLock> acquireGuard() {
  98     return std::unique_lock<MicroSpinLock>(spinLock_);
  99   }
 100
 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; }
 104
 105   void setIsHeadNode() {
 106     setFlags(getFlags() | IS_HEAD_NODE);
 107   }
 108   void setFullyLinked() {
 109     setFlags(getFlags() | FULLY_LINKED);
 110   }
 111   void setMarkedForRemoval() {
 112     setFlags(getFlags() | MARKED_FOR_REMOVAL);
 113   }
 114
 115  private:
 116   // Note! this can only be called from create() as a placement new.
 117   template<typename U>
 118   SkipListNode(uint8_t height, U&& data, bool isHead) :
 119       height_(height), data_(std::forward<U>(data)) {
 120     spinLock_.init();
 121     setFlags(0);
 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);
 126     }
 127   }
 128
 129   ~SkipListNode() {
 130     for (uint8_t i = 0; i < height_; ++i) {
 131       skip_[i].~atomic();
 132     }
 133   }
 134
 135   uint16_t getFlags() const {
 136     return flags_.load(std::memory_order_consume);
 137   }
 138   void setFlags(uint16_t flags) {
 139     flags_.store(flags, std::memory_order_release);
 140   }
 141
 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
 145   // MicroSpinLock.
 146   std::atomic<uint16_t> flags_;
 147   const uint8_t height_;
 148   MicroSpinLock spinLock_;
 149
 150   value_type data_;
 151
 152   std::atomic<SkipListNode*> skip_[0];
 153 };
 154
 155 class SkipListRandomHeight {
 156   enum { kMaxHeight = 64 };
 157  public:
 158   // make it a singleton.
 159   static SkipListRandomHeight *instance() {
 160     static SkipListRandomHeight instance_;
 161     return &instance_;
 162   }
 163
 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]) {
 169         return i + 1;
 170       }
 171     }
 172     return maxHeight;
 173   }
 174
 175   size_t getSizeLimit(int height) const {
 176     DCHECK_LT(height, kMaxHeight);
 177     return sizeLimitTable_[height];
 178   }
 179
 180  private:
 181
 182   SkipListRandomHeight() { initLookupTable(); }
 183
 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();
 189
 190     double sizeLimit = 1;
 191     double p = lookupTable_[0] = (1 - kProb);
 192     sizeLimitTable_[0] = 1;
 193     for (int i = 1; i < kMaxHeight - 1; ++i) {
 194       p *= kProb;
 195       sizeLimit *= kProbInv;
 196       lookupTable_[i] = lookupTable_[i - 1] + p;
 197       sizeLimitTable_[i] = sizeLimit > kMaxSizeLimit ?
 198         kMaxSizeLimit :
 199         static_cast<size_t>(sizeLimit);
 200     }
 201     lookupTable_[kMaxHeight - 1] = 1;
 202     sizeLimitTable_[kMaxHeight - 1] = kMaxSizeLimit;
 203   }
 204
 205   static double randomProb() {
 206     static ThreadLocal<boost::lagged_fibonacci2281> rng_;
 207     return (*rng_)();
 208   }
 209
 210   double lookupTable_[kMaxHeight];
 211   size_t sizeLimitTable_[kMaxHeight];
 212 };
 213
 214 }}
 215
 216 #endif  // FOLLY_CONCURRENTSKIPLIST_INL_H_