folly/ConcurrentSkipList-inl.h

   1 /*
   2  * Copyright 2012 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   static SkipListNode* create(int height,
  46       const value_type& data, bool isHead = false) {
  47     DCHECK(height >= 1 && height < 64) << height;
  48
  49     size_t size = sizeof(SkipListNode) + height * sizeof(SkipListNode*);
  50     auto* node = static_cast<SkipListNode*>(malloc(size));
  51     new (node) SkipListNode(height);
  52
  53     node->spinLock_.init();
  54     node->setFlags(0);
  55
  56     if (isHead) {
  57       node->setIsHeadNode();
  58     } else {
  59       new (&(node->data_)) value_type(data);
  60     }
  61     return node;
  62   }
  63
  64   static void destroy(SkipListNode* node) {
  65     if (!node->isHeadNode()) {
  66       node->data_.~value_type();
  67     }
  68     node->~SkipListNode();
  69     free(node);
  70   }
  71
  72   // assuming lock acquired
  73   SkipListNode* promoteFrom(const SkipListNode* node) {
  74     DCHECK(node != nullptr && height_ > node->height_);
  75     setFlags(node->getFlags());
  76     if (!isHeadNode()) {
  77       new (&(data_)) value_type(node->data());
  78     }
  79     for (int i = 0; i < node->height_; ++i) {
  80       setSkip(i, node->skip(i));
  81     }
  82     return this;
  83   }
  84
  85   inline SkipListNode* skip(int layer) const {
  86     DCHECK_LT(layer, height_);
  87     return skip_[layer].load(std::memory_order_consume);
  88   }
  89
  90   // next valid node as in the linked list
  91   SkipListNode* next() {
  92     SkipListNode* node;
  93     for (node = skip(0);
  94         (node != nullptr && node->markedForRemoval());
  95         node = node->skip(0)) {}
  96     return node;
  97   }
  98
  99   void setSkip(uint8_t h, SkipListNode* next) {
 100     DCHECK_LT(h, height_);
 101     skip_[h].store(next, std::memory_order_release);
 102   }
 103
 104   value_type& data() { return data_; }
 105   const value_type& data() const { return data_; }
 106   int maxLayer() const { return height_ - 1; }
 107   int height() const { return height_; }
 108
 109   std::unique_lock<MicroSpinLock> acquireGuard() {
 110     return std::unique_lock<MicroSpinLock>(spinLock_);
 111   }
 112
 113   bool fullyLinked() const      { return getFlags() & FULLY_LINKED; }
 114   bool markedForRemoval() const { return getFlags() & MARKED_FOR_REMOVAL; }
 115   bool isHeadNode() const       { return getFlags() & IS_HEAD_NODE; }
 116
 117   void setIsHeadNode() {
 118     setFlags(getFlags() | IS_HEAD_NODE);
 119   }
 120   void setFullyLinked() {
 121     setFlags(getFlags() | FULLY_LINKED);
 122   }
 123   void setMarkedForRemoval() {
 124     setFlags(getFlags() | MARKED_FOR_REMOVAL);
 125   }
 126
 127  private:
 128   ~SkipListNode() {
 129     for (uint8_t i = 0; i < height_; ++i) {
 130       skip_[i].~atomic();
 131     }
 132   }
 133   explicit SkipListNode(uint8_t height) : height_(height) {
 134     for (uint8_t i = 0; i < height_; ++i) {
 135       new (&skip_[i]) std::atomic<SkipListNode*>(nullptr);
 136     }
 137   }
 138
 139   uint16_t getFlags() const {
 140     return flags_.load(std::memory_order_consume);
 141   }
 142   void setFlags(uint16_t flags) {
 143     flags_.store(flags, std::memory_order_release);
 144   }
 145
 146   // TODO(xliu): on x86_64, it's possible to squeeze these into
 147   // skip_[0] to maybe save 8 bytes depending on the data alignments.
 148   // NOTE: currently this is x86_64 only anyway, due to the
 149   // MicroSpinLock.
 150   std::atomic<uint16_t> flags_;
 151   const uint8_t height_;
 152   MicroSpinLock spinLock_;
 153
 154   value_type data_;
 155
 156   std::atomic<SkipListNode*> skip_[0];
 157 };
 158
 159 class SkipListRandomHeight {
 160   enum { kMaxHeight = 64 };
 161  public:
 162   // make it a singleton.
 163   static SkipListRandomHeight *instance() {
 164     static SkipListRandomHeight instance_;
 165     return &instance_;
 166   }
 167
 168   int getHeight(int maxHeight) const {
 169     DCHECK_LE(maxHeight, kMaxHeight) << "max height too big!";
 170     double p = randomProb();
 171     for (int i = 0; i < maxHeight; ++i) {
 172       if (p < lookupTable_[i]) {
 173         return i + 1;
 174       }
 175     }
 176     return maxHeight;
 177   }
 178
 179   size_t getSizeLimit(int height) const {
 180     DCHECK_LT(height, kMaxHeight);
 181     return sizeLimitTable_[height];
 182   }
 183
 184  private:
 185
 186   SkipListRandomHeight() { initLookupTable(); }
 187
 188   void initLookupTable() {
 189     // set skip prob = 1/E
 190     static const double kProbInv = exp(1);
 191     static const double kProb = 1.0 / kProbInv;
 192     static const size_t kMaxSizeLimit = std::numeric_limits<size_t>::max();
 193
 194     double sizeLimit = 1;
 195     double p = lookupTable_[0] = (1 - kProb);
 196     sizeLimitTable_[0] = 1;
 197     for (int i = 1; i < kMaxHeight - 1; ++i) {
 198       p *= kProb;
 199       sizeLimit *= kProbInv;
 200       lookupTable_[i] = lookupTable_[i - 1] + p;
 201       sizeLimitTable_[i] = sizeLimit > kMaxSizeLimit ?
 202         kMaxSizeLimit :
 203         static_cast<size_t>(sizeLimit);
 204     }
 205     lookupTable_[kMaxHeight - 1] = 1;
 206     sizeLimitTable_[kMaxHeight - 1] = kMaxSizeLimit;
 207   }
 208
 209   static double randomProb() {
 210     static ThreadLocal<boost::lagged_fibonacci2281> rng_;
 211     return (*rng_)();
 212   }
 213
 214   double lookupTable_[kMaxHeight];
 215   size_t sizeLimitTable_[kMaxHeight];
 216 };
 217
 218 }}
 219
 220 #endif  // FOLLY_CONCURRENTSKIPLIST_INL_H_