X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FConcurrentSkipList.h;h=2f8f02549d90c29d5ad911b3cb76e7865f42de66;hb=4c7d52264b25ade4758be7631aca68721a2704d5;hp=3299d75c7ba1ba38c78fe1bf89019b01ef13113c;hpb=51f060fec3b7da5ee9630d62e1f9c895fcbacccc;p=folly.git

diff --git a/folly/ConcurrentSkipList.h b/folly/ConcurrentSkipList.h
index 3299d75c..2f8f0254 100644
--- a/folly/ConcurrentSkipList.h
+++ b/folly/ConcurrentSkipList.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2016 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -117,28 +117,29 @@ Sample usage:
      }
 */
 
-#ifndef FOLLY_CONCURRENT_SKIP_LIST_H_
-#define FOLLY_CONCURRENT_SKIP_LIST_H_
+#pragma once
 
 #include <algorithm>
-#include <climits>
-#include <type_traits>
-#include <utility>
-#include <vector>
 #include <atomic>
-#include <thread>
+#include <limits>
+#include <memory>
+#include <type_traits>
 #include <boost/iterator/iterator_facade.hpp>
-#include <boost/scoped_ptr.hpp>
-#include <boost/shared_ptr.hpp>
-
 #include <glog/logging.h>
-#include "folly/ConcurrentSkipList-inl.h"
-#include "folly/Likely.h"
-#include "folly/SmallLocks.h"
+
+#include <folly/ConcurrentSkipList-inl.h>
+#include <folly/Likely.h>
+#include <folly/Memory.h>
+#include <folly/MicroSpinLock.h>
 
 namespace folly {
 
-template<typename T, typename Comp=std::less<T>, int MAX_HEIGHT=24>
+template<typename T,
+         typename Comp = std::less<T>,
+         // All nodes are allocated using provided SimpleAllocator,
+         // it should be thread-safe.
+         typename NodeAlloc = SysAlloc,
+         int MAX_HEIGHT = 24>
 class ConcurrentSkipList {
   // MAX_HEIGHT needs to be at least 2 to suppress compiler
   // warnings/errors (Werror=uninitialized tiggered due to preds_[1]
@@ -146,35 +147,47 @@ class ConcurrentSkipList {
   static_assert(MAX_HEIGHT >= 2 && MAX_HEIGHT < 64,
       "MAX_HEIGHT can only be in the range of [2, 64)");
   typedef std::unique_lock<folly::MicroSpinLock> ScopedLocker;
-  typedef ConcurrentSkipList<T, Comp, MAX_HEIGHT> SkipListType;
+  typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
 
  public:
   typedef detail::SkipListNode<T> NodeType;
   typedef T value_type;
   typedef T key_type;
 
-
   typedef detail::csl_iterator<value_type, NodeType> iterator;
   typedef detail::csl_iterator<const value_type, const NodeType> const_iterator;
 
   class Accessor;
   class Skipper;
 
-  // convenient function to get an Accessor to a new instance.
-  static Accessor create(int height=1) {
-    return Accessor(createInstance(height));
+  explicit ConcurrentSkipList(int height, const NodeAlloc& alloc)
+      : recycler_(alloc),
+        head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
+        size_(0) {}
+
+  explicit ConcurrentSkipList(int height)
+      : recycler_(),
+        head_(NodeType::create(recycler_.alloc(), height, value_type(), true)),
+        size_(0) {}
+
+  // Convenient function to get an Accessor to a new instance.
+  static Accessor create(int height, const NodeAlloc& alloc) {
+    return Accessor(createInstance(height, alloc));
   }
 
-  // create a shared_ptr skiplist object with initial head height.
-  static boost::shared_ptr<SkipListType> createInstance(int height=1) {
-    return boost::shared_ptr<SkipListType>(new SkipListType(height));
+  static Accessor create(int height = 1) {
+    return Accessor(createInstance(height));
   }
 
-  // create a unique_ptr skiplist object with initial head height.
-  static std::unique_ptr<SkipListType> createRawInstance(int height=1) {
-    return std::unique_ptr<SkipListType>(new SkipListType(height));
+  // Create a shared_ptr skiplist object with initial head height.
+  static std::shared_ptr<SkipListType> createInstance(int height,
+                                                      const NodeAlloc& alloc) {
+    return std::make_shared<ConcurrentSkipList>(height, alloc);
   }
 
+  static std::shared_ptr<SkipListType> createInstance(int height = 1) {
+    return std::make_shared<ConcurrentSkipList>(height);
+  }
 
   //===================================================================
   // Below are implementation details.
@@ -182,18 +195,18 @@ class ConcurrentSkipList {
   //===================================================================
 
   ~ConcurrentSkipList() {
-    LOG_IF(FATAL, recycler_.refs() > 0)
-      << "number of accessors is not 0, " << recycler_.refs() << " instead!"
-      << " This shouldn't have happened!";
-    while (NodeType* current = head_.load(std::memory_order_relaxed)) {
+    /* static */ if (NodeType::template destroyIsNoOp<NodeAlloc>()) {
+      // Avoid traversing the list if using arena allocator.
+      return;
+    }
+    for (NodeType* current = head_.load(std::memory_order_relaxed); current; ) {
       NodeType* tmp = current->skip(0);
-      NodeType::destroy(current);
-      head_.store(tmp, std::memory_order_relaxed);
+      NodeType::destroy(recycler_.alloc(), current);
+      current = tmp;
     }
   }
 
  private:
-
   static bool greater(const value_type &data, const NodeType *node) {
     return node && Comp()(node->data(), data);
   }
@@ -228,87 +241,12 @@ class ConcurrentSkipList {
     return foundLayer;
   }
 
-  struct Recycler : private boost::noncopyable {
-    Recycler() : refs_(0), dirty_(false) { lock_.init(); }
-
-    ~Recycler() {
-      if (nodes_) {
-        for (auto& node : *nodes_) {
-          NodeType::destroy(node);
-        }
-      }
-    }
-
-    void add(NodeType* node) {
-      std::lock_guard<MicroSpinLock> g(lock_);
-      if (nodes_.get() == nullptr) {
-        nodes_.reset(new std::vector<NodeType*>(1, node));
-      } else {
-        nodes_->push_back(node);
-      }
-      DCHECK_GT(refs(), 0);
-      dirty_.store(true, std::memory_order_relaxed);
-    }
-
-    int refs() const {
-      return refs_.load(std::memory_order_relaxed);
-    }
-
-    int addRef() {
-      return refs_.fetch_add(1, std::memory_order_relaxed);
-    }
-
-    int release() {
-      // We don't expect to clean the recycler immediately everytime it is OK
-      // to do so. Here, it is possible that multiple accessors all release at
-      // the same time but nobody would clean the recycler here. If this
-      // happens, the recycler will usually still get cleaned when
-      // such a race doesn't happen. The worst case is the recycler will
-      // eventually get deleted along with the skiplist.
-      if (LIKELY(!dirty_.load(std::memory_order_relaxed) || refs() > 1)) {
-        return refs_.fetch_add(-1, std::memory_order_relaxed);
-      }
-
-      boost::scoped_ptr<std::vector<NodeType*> > newNodes;
-      {
-        std::lock_guard<MicroSpinLock> g(lock_);
-        if (nodes_.get() == nullptr || refs() > 1) {
-          return refs_.fetch_add(-1, std::memory_order_relaxed);
-        }
-        // once refs_ reaches 1 and there is no other accessor, it is safe to
-        // remove all the current nodes in the recycler, as we already acquired
-        // the lock here so no more new nodes can be added, even though new
-        // accessors may be added after that.
-        newNodes.swap(nodes_);
-        dirty_.store(false, std::memory_order_relaxed);
-      }
-
-      // TODO(xliu) should we spawn a thread to do this when there are large
-      // number of nodes in the recycler?
-      for (auto& node : *newNodes) {
-        NodeType::destroy(node);
-      }
-
-      // decrease the ref count at the very end, to minimize the
-      // chance of other threads acquiring lock_ to clear the deleted
-      // nodes again.
-      return refs_.fetch_add(-1, std::memory_order_relaxed);
-    }
-
-   private:
-    boost::scoped_ptr<std::vector<NodeType*>> nodes_;
-    std::atomic<int32_t> refs_; // current number of visitors to the list
-    std::atomic<bool> dirty_; // whether *nodes_ is non-empty
-    MicroSpinLock lock_; // protects access to *nodes_
-  };  // class ConcurrentSkipList::Recycler
-
-  explicit ConcurrentSkipList(int height) :
-    head_(NodeType::create(height, value_type(), true)), size_(0) {}
-
   size_t size() const { return size_.load(std::memory_order_relaxed); }
+
   int height() const {
     return head_.load(std::memory_order_consume)->height();
   }
+
   int maxLayer() const { return height() - 1; }
 
   size_t incrementSize(int delta) {
@@ -358,7 +296,8 @@ class ConcurrentSkipList {
   //     list with the same key.
   //   pair.second stores whether the data is added successfully:
   //     0 means not added, otherwise reutrns the new size.
-  std::pair<NodeType*, size_t> addOrGetData(const value_type &data) {
+  template<typename U>
+  std::pair<NodeType*, size_t> addOrGetData(U &&data) {
     NodeType *preds[MAX_HEIGHT], *succs[MAX_HEIGHT];
     NodeType *newNode;
     size_t newSize;
@@ -387,10 +326,11 @@ class ConcurrentSkipList {
       }
 
       // locks acquired and all valid, need to modify the links under the locks.
-      newNode = NodeType::create(nodeHeight, data);
-      for (int layer = 0; layer < nodeHeight; ++layer) {
-        newNode->setSkip(layer, succs[layer]);
-        preds[layer]->setSkip(layer, newNode);
+      newNode =
+        NodeType::create(recycler_.alloc(), nodeHeight, std::forward<U>(data));
+      for (int k = 0; k < nodeHeight; ++k) {
+        newNode->setSkip(k, succs[k]);
+        preds[k]->setSkip(k, newNode);
       }
 
       newNode->setFullyLinked();
@@ -438,8 +378,8 @@ class ConcurrentSkipList {
         continue;  // this will unlock all the locks
       }
 
-      for (int layer = nodeHeight - 1; layer >= 0; --layer) {
-        preds[layer]->setSkip(layer, nodeToDelete->skip(layer));
+      for (int k = nodeHeight - 1; k >= 0; --k) {
+        preds[k]->setSkip(k, nodeToDelete->skip(k));
       }
 
       incrementSize(-1);
@@ -502,10 +442,11 @@ class ConcurrentSkipList {
     bool found = false;
     while (!found) {
       // stepping down
-      for (; ht > 0 && less(data, pred->skip(ht - 1)); --ht) {}
-      if (ht == 0) return std::make_pair(pred->skip(0), 0);  // not found
+      for (; ht > 0 && less(data, node = pred->skip(ht - 1)); --ht) {}
+      if (ht == 0) return std::make_pair(node, 0);  // not found
+      // node <= data now, but we need to fix up ht
+      --ht;
 
-      node = pred->skip(--ht);  // node <= data now
       // stepping right
       while (greater(data, node)) {
         pred = node;
@@ -548,17 +489,18 @@ class ConcurrentSkipList {
       return;
     }
 
-    NodeType* newHead = NodeType::create(height, value_type(), true);
+    NodeType* newHead =
+      NodeType::create(recycler_.alloc(), height, value_type(), true);
 
     { // need to guard the head node in case others are adding/removing
       // nodes linked to the head.
       ScopedLocker g = oldHead->acquireGuard();
-      newHead->promoteFrom(oldHead);
+      newHead->copyHead(oldHead);
       NodeType* expected = oldHead;
       if (!head_.compare_exchange_strong(expected, newHead,
           std::memory_order_release)) {
         // if someone has already done the swap, just return.
-        NodeType::destroy(newHead);
+        NodeType::destroy(recycler_.alloc(), newHead);
         return;
       }
       oldHead->setMarkedForRemoval();
@@ -570,15 +512,15 @@ class ConcurrentSkipList {
     recycler_.add(node);
   }
 
+  detail::NodeRecycler<NodeType, NodeAlloc> recycler_;
   std::atomic<NodeType*> head_;
-  Recycler recycler_;
   std::atomic<size_t> size_;
 };
 
-template<typename T, typename Comp, int MAX_HEIGHT>
-class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
+template<typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT>
+class ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT>::Accessor {
   typedef detail::SkipListNode<T> NodeType;
-  typedef ConcurrentSkipList<T, Comp, MAX_HEIGHT> SkipListType;
+  typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
  public:
   typedef T value_type;
   typedef T key_type;
@@ -594,7 +536,7 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
   typedef typename SkipListType::const_iterator const_iterator;
   typedef typename SkipListType::Skipper Skipper;
 
-  explicit Accessor(boost::shared_ptr<ConcurrentSkipList> skip_list)
+  explicit Accessor(std::shared_ptr<ConcurrentSkipList> skip_list)
     : slHolder_(std::move(skip_list))
   {
     sl_ = slHolder_.get();
@@ -618,7 +560,7 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
   Accessor& operator=(const Accessor &accessor) {
     if (this != &accessor) {
       slHolder_ = accessor.slHolder_;
-      sl_->recycler_.release();
+      sl_->recycler_.releaseRef();
       sl_ = accessor.sl_;
       sl_->recycler_.addRef();
     }
@@ -626,7 +568,7 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
   }
 
   ~Accessor() {
-    sl_->recycler_.release();
+    sl_->recycler_.releaseRef();
   }
 
   bool empty() const { return sl_->size() == 0; }
@@ -650,8 +592,10 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
   const_iterator cbegin() const { return begin(); }
   const_iterator cend() const { return end(); }
 
-  std::pair<iterator, bool> insert(const key_type &data) {
-    auto ret = sl_->addOrGetData(data);
+  template<typename U,
+    typename=typename std::enable_if<std::is_convertible<U, T>::value>::type>
+  std::pair<iterator, bool> insert(U&& data) {
+    auto ret = sl_->addOrGetData(std::forward<U>(data));
     return std::make_pair(iterator(ret.first), ret.second);
   }
   size_t erase(const key_type &data) { return remove(data); }
@@ -703,7 +647,7 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Accessor {
 
  private:
   SkipListType *sl_;
-  boost::shared_ptr<SkipListType> slHolder_;
+  std::shared_ptr<SkipListType> slHolder_;
 };
 
 // implements forward iterator concept.
@@ -743,10 +687,10 @@ class detail::csl_iterator :
 };
 
 // Skipper interface
-template<typename T, typename Comp, int MAX_HEIGHT>
-class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Skipper {
+template<typename T, typename Comp, typename NodeAlloc, int MAX_HEIGHT>
+class ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT>::Skipper {
   typedef detail::SkipListNode<T> NodeType;
-  typedef ConcurrentSkipList<T, Comp, MAX_HEIGHT> SkipListType;
+  typedef ConcurrentSkipList<T, Comp, NodeAlloc, MAX_HEIGHT> SkipListType;
   typedef typename SkipListType::Accessor Accessor;
 
  public:
@@ -755,7 +699,7 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Skipper {
   typedef T* pointer;
   typedef ptrdiff_t difference_type;
 
-  Skipper(const boost::shared_ptr<SkipListType>& skipList) :
+  Skipper(const std::shared_ptr<SkipListType>& skipList) :
     accessor_(skipList) {
     init();
   }
@@ -803,17 +747,17 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Skipper {
   }
 
   const value_type &data() const {
-    DCHECK(succs_[0] != NULL);
+    DCHECK(succs_[0] != nullptr);
     return succs_[0]->data();
   }
 
   value_type &operator *() const {
-    DCHECK(succs_[0] != NULL);
+    DCHECK(succs_[0] != nullptr);
     return succs_[0]->data();
   }
 
   value_type *operator->() {
-    DCHECK(succs_[0] != NULL);
+    DCHECK(succs_[0] != nullptr);
     return &succs_[0]->data();
   }
 
@@ -838,7 +782,8 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Skipper {
       findInsertionPoint(preds_[lyr], lyr, data, preds_, succs_);
     if (foundLayer < 0) return false;
 
-    DCHECK(succs_[0] != NULL) << "lyr=" << lyr << "; max_layer=" << max_layer;
+    DCHECK(succs_[0] != nullptr) << "lyr=" << lyr
+                                 << "; max_layer=" << max_layer;
     return !succs_[0]->markedForRemoval();
   }
 
@@ -854,5 +799,3 @@ class ConcurrentSkipList<T, Comp, MAX_HEIGHT>::Skipper {
 };
 
 } // namespace folly
-
-#endif  // FOLLY_CONCURRENT_SKIP_LIST_H_