From 0fd4f5795ab91a0c1d45fced6232f4f738a5a6e1 Mon Sep 17 00:00:00 2001
From: Philip Pronin <philipp@fb.com>
Date: Fri, 4 Apr 2014 21:50:27 -0700
Subject: [PATCH] make ConcurrentSkipList ctor public

Summary:
There is no reason to force heap allocation for
`ConcurrentSkipList`.

Test Plan: fbconfig -r unicorn/test && fbmake opt -j32

@override-unit-failures

Reviewed By: lucian@fb.com

FB internal diff: D1261183
---
 folly/ConcurrentSkipList.h | 40 ++++++++++++++------------------------
 1 file changed, 15 insertions(+), 25 deletions(-)

diff --git a/folly/ConcurrentSkipList.h b/folly/ConcurrentSkipList.h
index 01d3a2f1..42642b4b 100644
--- a/folly/ConcurrentSkipList.h
+++ b/folly/ConcurrentSkipList.h
@@ -121,17 +121,15 @@ Sample usage:
 #define FOLLY_CONCURRENT_SKIP_LIST_H_
 
 #include <algorithm>
+#include <atomic>
 #include <climits>
+#include <memory>
 #include <type_traits>
 #include <utility>
 #include <vector>
-#include <atomic>
-#include <thread>
 #include <boost/iterator/iterator_facade.hpp>
-#include <boost/scoped_ptr.hpp>
-#include <memory>
-
 #include <glog/logging.h>
+
 #include "folly/ConcurrentSkipList-inl.h"
 #include "folly/Likely.h"
 #include "folly/SmallLocks.h"
@@ -153,29 +151,25 @@ class ConcurrentSkipList {
   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)
+    : head_(NodeType::create(height, value_type(), true)), size_(0) { }
 
-  // create a shared_ptr skiplist object with initial head height.
-  static std::shared_ptr<SkipListType> createInstance(int height=1) {
-    return std::shared_ptr<SkipListType>(new SkipListType(height));
+  // Convenient function to get an Accessor to a new instance.
+  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 = 1) {
+    return std::make_shared<ConcurrentSkipList>(height);
   }
 
-
   //===================================================================
   // Below are implementation details.
   // Please see ConcurrentSkipList::Accessor for stdlib-like APIs.
@@ -183,15 +177,14 @@ class ConcurrentSkipList {
 
   ~ConcurrentSkipList() {
     CHECK_EQ(recycler_.refs(), 0);
-    while (NodeType* current = head_.load(std::memory_order_relaxed)) {
+    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);
+      current = tmp;
     }
   }
 
  private:
-
   static bool greater(const value_type &data, const NodeType *node) {
     return node && Comp()(node->data(), data);
   }
@@ -267,7 +260,7 @@ class ConcurrentSkipList {
         return refs_.fetch_add(-1, std::memory_order_relaxed);
       }
 
-      boost::scoped_ptr<std::vector<NodeType*> > newNodes;
+      std::unique_ptr<std::vector<NodeType*>> newNodes;
       {
         std::lock_guard<MicroSpinLock> g(lock_);
         if (nodes_.get() == nullptr || refs() > 1) {
@@ -294,15 +287,12 @@ class ConcurrentSkipList {
     }
 
    private:
-    boost::scoped_ptr<std::vector<NodeType*>> nodes_;
+    std::unique_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();
-- 
2.34.1