Copyright 2013 -> 2014

[folly.git] / folly / ConcurrentSkipList.h

diff --git a/folly/ConcurrentSkipList.h b/folly/ConcurrentSkipList.h
index c52238499729db87cbb7ead839d0def43f858e13..3752e69d17061e78cb1432854a7309a64a48cbc4 100644 (file)
--- a/folly/ConcurrentSkipList.h
+++ b/folly/ConcurrentSkipList.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -129,7 +129,7 @@ Sample usage:
 #include <thread>
 #include <boost/iterator/iterator_facade.hpp>
 #include <boost/scoped_ptr.hpp>
-#include <boost/shared_ptr.hpp>
+#include <memory>
 
 #include <glog/logging.h>
 #include "folly/ConcurrentSkipList-inl.h"
@@ -145,11 +145,11 @@ class ConcurrentSkipList {
   // being treated as a scalar in the compiler).
   static_assert(MAX_HEIGHT >= 2 && MAX_HEIGHT < 64,
       "MAX_HEIGHT can only be in the range of [2, 64)");
-  typedef detail::SkipListNode<T> NodeType;
   typedef std::unique_lock<folly::MicroSpinLock> ScopedLocker;
   typedef ConcurrentSkipList<T, Comp, MAX_HEIGHT> SkipListType;
 
  public:
+  typedef detail::SkipListNode<T> NodeType;
   typedef T value_type;
   typedef T key_type;
 
@@ -166,19 +166,23 @@ class ConcurrentSkipList {
   }
 
   // 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 std::shared_ptr<SkipListType> createInstance(int height=1) {
+    return std::shared_ptr<SkipListType>(new SkipListType(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));
   }
 
+
   //===================================================================
   // Below are implementation details.
   // Please see ConcurrentSkipList::Accessor for stdlib-like APIs.
   //===================================================================
 
   ~ConcurrentSkipList() {
-    LOG_IF(FATAL, recycler_.refs() > 0)
-      << "number of accessors is not 0, " << recycler_.refs() << " instead!"
-      << " This shouldn't have happened!";
+    CHECK_EQ(recycler_.refs(), 0);
     while (NodeType* current = head_.load(std::memory_order_relaxed)) {
       NodeType* tmp = current->skip(0);
       NodeType::destroy(current);
@@ -352,7 +356,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;
@@ -381,7 +386,7 @@ class ConcurrentSkipList {
       }
 
       // locks acquired and all valid, need to modify the links under the locks.
-      newNode = NodeType::create(nodeHeight, data);
+      newNode = NodeType::create(nodeHeight, std::forward<U>(data));
       for (int layer = 0; layer < nodeHeight; ++layer) {
         newNode->setSkip(layer, succs[layer]);
         preds[layer]->setSkip(layer, newNode);
@@ -547,7 +552,7 @@ class ConcurrentSkipList {
     { // 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)) {
@@ -588,7 +593,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();
@@ -644,8 +649,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); }
@@ -697,7 +704,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.
@@ -749,7 +756,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();
   }