From cc86cd35792f320d4111fac91ca88f1733266a8a Mon Sep 17 00:00:00 2001
From: Marcelo Juchem <marcelo@fb.com>
Date: Mon, 7 Jan 2013 19:05:53 -0800
Subject: [PATCH] Implementing unique/shared_ptr for custom allocators (like
 Arena) in folly

Summary:
- moving simple allocator *_ptr and convenience functions to folly
- getting rid of arena_new - it encourages manually constructing smart pointers when folly::allocate_* should be used instead
- using std::allocate_shared to construct shared_ptrs, thus properly using the allocator for the ref-counter too
- fixing forwarding of parameters in the convenience functions
- uniform allocation of smart pointers using both stl and non stl-like allocators

Test Plan:
- build + tests of existing client code
- basic unit tests for arena smart pointers

Reviewed By: delong.j@fb.com

FB internal diff: D672818
---
 folly/StlAllocator.h                 | 137 ++++++++++++++++++++-
 folly/Traits.h                       |  70 ++++++++++-
 folly/test/ArenaSmartPtrTest.cpp     | 178 +++++++++++++++++++++++++++
 folly/test/HasMemberFnTraitsTest.cpp | 122 ++++++++++++++++++
 4 files changed, 502 insertions(+), 5 deletions(-)
 create mode 100644 folly/test/ArenaSmartPtrTest.cpp
 create mode 100644 folly/test/HasMemberFnTraitsTest.cpp

diff --git a/folly/StlAllocator.h b/folly/StlAllocator.h
index 3848343d..629d8fec 100644
--- a/folly/StlAllocator.h
+++ b/folly/StlAllocator.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2013 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -17,14 +17,22 @@
 #ifndef FOLLY_STLALLOCATOR_H_
 #define FOLLY_STLALLOCATOR_H_
 
+#include "folly/Traits.h"
+
 #include <memory>
+#include <limits>
+#include <utility>
+#include <exception>
+#include <stdexcept>
+
+#include <cstddef>
 
 namespace folly {
 
 /**
- * Wrap a simple allocator into a STL-compliant allocator.
+ * Wrap a SimpleAllocator into a STL-compliant allocator.
  *
- * The simple allocator must provide two methods:
+ * The SimpleAllocator must provide two methods:
  *    void* allocate(size_t size);
  *    void deallocate(void* ptr, size_t size);
  * which, respectively, allocate a block of size bytes (aligned to the maximum
@@ -45,6 +53,8 @@ namespace folly {
  *     free(p);
  *   }
  * };
+ *
+ * author: Tudor Bosman <tudorb@fb.com>
  */
 
 // This would be so much simpler with std::allocator_traits, but gcc 4.6.2
@@ -128,7 +138,126 @@ class StlAllocator {
   Alloc* alloc_;
 };
 
+/*
+ * Helper classes/functions for creating a unique_ptr using a custom allocator
+ *
+ * @author: Marcelo Juchem <marcelo@fb.com>
+ */
+
+// A deleter implementation based on std::default_delete,
+// which uses a custom allocator to free memory
+template <typename Allocator>
+class allocator_delete {
+  typedef typename std::remove_reference<Allocator>::type allocator_type;
+
+public:
+  allocator_delete() = default;
+
+  explicit allocator_delete(const allocator_type& allocator):
+    allocator_(allocator)
+  {}
+
+  explicit allocator_delete(allocator_type&& allocator):
+    allocator_(std::move(allocator))
+  {}
+
+  template <typename U>
+  allocator_delete(const allocator_delete<U>& other):
+    allocator_(other.get_allocator())
+  {}
+
+  allocator_type& get_allocator() const {
+    return allocator_;
+  }
+
+  void operator()(typename allocator_type::pointer p) const {
+    if (!p) {
+      return;
+    }
+
+    allocator_.destroy(p);
+    allocator_.deallocate(p, 1);
+  }
+
+private:
+  mutable allocator_type allocator_;
+};
+
+template <typename T, typename Allocator>
+class is_simple_allocator {
+  FOLLY_CREATE_HAS_MEMBER_FN_TRAITS(has_destroy, destroy);
+
+  typedef typename std::remove_const<
+    typename std::remove_reference<Allocator>::type
+  >::type allocator;
+  typedef T value_type;
+  typedef value_type* pointer;
+
+public:
+  constexpr static bool value = !has_destroy<allocator, void(pointer)>::value
+    && !has_destroy<allocator, void(void*)>::value;
+};
+
+template <typename T, typename Allocator>
+typename std::enable_if<
+  is_simple_allocator<T, Allocator>::value,
+  folly::StlAllocator<typename std::remove_reference<Allocator>::type, T>
+>::type make_stl_allocator(Allocator&& allocator) {
+  return folly::StlAllocator<
+    typename std::remove_reference<Allocator>::type, T
+  >(&allocator);
+}
+
+template <typename T, typename Allocator>
+typename std::enable_if<
+  !is_simple_allocator<T, Allocator>::value,
+  typename std::remove_reference<Allocator>::type
+>::type make_stl_allocator(Allocator&& allocator) {
+  return std::move(allocator);
+}
+
+template <typename T, typename Allocator>
+struct AllocatorUniquePtr {
+  typedef std::unique_ptr<T,
+    folly::allocator_delete<
+      typename std::conditional<
+        is_simple_allocator<T, Allocator>::value,
+        folly::StlAllocator<typename std::remove_reference<Allocator>::type, T>,
+        typename std::remove_reference<Allocator>::type
+      >::type
+    >
+  > type;
+};
+
+template <typename T, typename Allocator, typename ...Args>
+typename AllocatorUniquePtr<T, Allocator>::type allocate_unique(
+  Allocator&& allocator, Args&&... args
+) {
+  auto stlAllocator = folly::make_stl_allocator<T>(
+    std::forward<Allocator>(allocator)
+  );
+  auto p = stlAllocator.allocate(1);
+
+  try {
+    stlAllocator.construct(p, std::forward<Args>(args)...);
+
+    return {p,
+      folly::allocator_delete<decltype(stlAllocator)>(std::move(stlAllocator))
+    };
+  } catch (...) {
+    stlAllocator.deallocate(p, 1);
+    throw;
+  }
+}
+
+template <typename T, typename Allocator, typename ...Args>
+std::shared_ptr<T> allocate_shared(Allocator&& allocator, Args&&... args) {
+  return std::allocate_shared<T>(
+    folly::make_stl_allocator<T>(std::forward<Allocator>(allocator)),
+    std::forward<Args>(args)...
+  );
+}
+
 }  // namespace folly
 
 #endif /* FOLLY_STLALLOCATOR_H_ */
-
diff --git a/folly/Traits.h b/folly/Traits.h
index 7432dec5..d2fad50e 100644
--- a/folly/Traits.h
+++ b/folly/Traits.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2013 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -292,4 +292,72 @@ FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(std::function);
 // Boost
 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(boost::shared_ptr);
 
+#define FOLLY_CREATE_HAS_MEMBER_FN_TRAITS_IMPL(classname, func_name, cv_qual) \
+  template <typename TTheClass_, typename RTheReturn_, typename... TTheArgs_> \
+  class classname<TTheClass_, RTheReturn_(TTheArgs_...) cv_qual> { \
+    template < \
+      typename UTheClass_, RTheReturn_ (UTheClass_::*)(TTheArgs_...) cv_qual \
+    > struct sfinae {}; \
+    template <typename UTheClass_> \
+    constexpr static bool test(sfinae<UTheClass_, &UTheClass_::func_name>*) \
+    { return true; } \
+    template <typename> \
+    constexpr static bool test(...) { return false; } \
+  public: \
+    constexpr static bool value = test<TTheClass_>(nullptr); \
+  }
+
+/*
+ * The FOLLY_CREATE_HAS_MEMBER_FN_TRAITS is used to create traits
+ * classes that check for the existence of a member function with
+ * a given name and signature. It currently does not support
+ * checking for inherited members.
+ *
+ * Such classes receive two template parameters: the class to be checked
+ * and the signature of the member function. A static boolean field
+ * named `value` (which is also constexpr) tells whether such member
+ * function exists.
+ *
+ * Each traits class created is bound only to the member name, not to
+ * its signature nor to the type of the class containing it.
+ *
+ * Say you need to know if a given class has a member function named
+ * `test` with the following signature:
+ *
+ *    int test() const;
+ *
+ * You'd need this macro to create a traits class to check for a member
+ * named `test`, and then use this traits class to check for the signature:
+ *
+ * namespace {
+ *
+ * FOLLY_CREATE_HAS_MEMBER_FN_TRAITS(has_test_traits, test);
+ *
+ * } // unnamed-namespace
+ *
+ * void some_func() {
+ *   cout << "Does class Foo have a member int test() const? "
+ *     << boolalpha << has_test_traits<Foo, int() const>::value;
+ * }
+ *
+ * You can use the same traits class to test for a completely different
+ * signature, on a completely different class, as long as the member name
+ * is the same:
+ *
+ * void some_func() {
+ *   cout << "Does class Foo have a member int test()? "
+ *     << boolalpha << has_test_traits<Foo, int()>::value;
+ *   cout << "Does class Foo have a member int test() const? "
+ *     << boolalpha << has_test_traits<Foo, int() const>::value;
+ *   cout << "Does class Bar have a member double test(const string&, long)? "
+ *     << boolalpha << has_test_traits<Bar, double(const string&, long)>::value;
+ * }
+ */
+#define FOLLY_CREATE_HAS_MEMBER_FN_TRAITS(classname, func_name) \
+  template <typename, typename> class classname; \
+  FOLLY_CREATE_HAS_MEMBER_FN_TRAITS_IMPL(classname, func_name, ); \
+  FOLLY_CREATE_HAS_MEMBER_FN_TRAITS_IMPL(classname, func_name, const); \
+  FOLLY_CREATE_HAS_MEMBER_FN_TRAITS_IMPL(classname, func_name, volatile); \
+  FOLLY_CREATE_HAS_MEMBER_FN_TRAITS_IMPL(classname, func_name, volatile const)
+
 #endif //FOLLY_BASE_TRAITS_H_
diff --git a/folly/test/ArenaSmartPtrTest.cpp b/folly/test/ArenaSmartPtrTest.cpp
new file mode 100644
index 00000000..56534116
--- /dev/null
+++ b/folly/test/ArenaSmartPtrTest.cpp
@@ -0,0 +1,178 @@
+/*
+ * Copyright 2013 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * @author: Marcelo Juchem <marcelo@fb.com>
+ */
+
+#include "folly/StlAllocator.h"
+#include "folly/Arena.h"
+
+#include <gtest/gtest.h>
+
+using namespace folly;
+
+struct global_counter {
+  global_counter(): count_(0) {}
+
+  void increase() { ++count_; }
+  void decrease() {
+    EXPECT_GT(count_, 0);
+    --count_;
+  }
+
+  unsigned count() const { return count_; }
+
+private:
+  unsigned count_;
+};
+
+struct Foo {
+  explicit Foo(global_counter& counter):
+    counter_(counter)
+  {
+    counter_.increase();
+  }
+
+  ~Foo() {
+    counter_.decrease();
+  }
+
+private:
+  global_counter& counter_;
+};
+
+template <typename Allocator>
+void unique_ptr_test(Allocator& allocator) {
+  typedef typename AllocatorUniquePtr<Foo, Allocator>::type ptr_type;
+
+  global_counter counter;
+  EXPECT_EQ(counter.count(), 0);
+
+  Foo* foo = nullptr;
+
+  {
+    auto p = folly::allocate_unique<Foo>(allocator, counter);
+    EXPECT_EQ(counter.count(), 1);
+
+    p.reset();
+    EXPECT_EQ(counter.count(), 0);
+
+    p = folly::allocate_unique<Foo>(allocator, counter);
+    EXPECT_EQ(counter.count(), 1);
+
+    foo = p.release();
+    EXPECT_EQ(counter.count(), 1);
+  }
+  EXPECT_EQ(counter.count(), 1);
+
+  {
+    auto p = folly::allocate_unique<Foo>(allocator, counter);
+    EXPECT_EQ(counter.count(), 2);
+
+    [&](ptr_type g) {
+      EXPECT_EQ(counter.count(), 2);
+      g.reset();
+      EXPECT_EQ(counter.count(), 1);
+    }(std::move(p));
+  }
+  EXPECT_EQ(counter.count(), 1);
+
+  StlAllocator<Allocator, Foo>().destroy(foo);
+  EXPECT_EQ(counter.count(), 0);
+}
+
+TEST(ArenaSmartPtr, unique_ptr_SysArena) {
+  SysArena arena;
+  unique_ptr_test(arena);
+}
+
+TEST(ArenaSmartPtr, unique_ptr_StlAlloc_SysArena) {
+  SysArena arena;
+  StlAllocator<SysArena, Foo> alloc(&arena);
+  unique_ptr_test(alloc);
+}
+
+template <typename Allocator>
+void shared_ptr_test(Allocator& allocator) {
+  typedef std::shared_ptr<Foo> ptr_type;
+
+  global_counter counter;
+  EXPECT_EQ(counter.count(), 0);
+
+  ptr_type foo;
+  EXPECT_EQ(counter.count(), 0);
+  EXPECT_EQ(foo.use_count(), 0);
+
+  {
+    auto p = folly::allocate_shared<Foo>(allocator, counter);
+    EXPECT_EQ(counter.count(), 1);
+    EXPECT_EQ(p.use_count(), 1);
+
+    p.reset();
+    EXPECT_EQ(counter.count(), 0);
+    EXPECT_EQ(p.use_count(), 0);
+
+    p = folly::allocate_shared<Foo>(allocator, counter);
+    EXPECT_EQ(counter.count(), 1);
+    EXPECT_EQ(p.use_count(), 1);
+
+    foo = p;
+    EXPECT_EQ(p.use_count(), 2);
+  }
+  EXPECT_EQ(counter.count(), 1);
+  EXPECT_EQ(foo.use_count(), 1);
+
+  {
+    auto p = foo;
+    EXPECT_EQ(counter.count(), 1);
+    EXPECT_EQ(p.use_count(), 2);
+
+    [&](ptr_type g) {
+      EXPECT_EQ(counter.count(), 1);
+      EXPECT_EQ(p.use_count(), 3);
+      EXPECT_EQ(g.use_count(), 3);
+      g.reset();
+      EXPECT_EQ(counter.count(), 1);
+      EXPECT_EQ(p.use_count(), 2);
+      EXPECT_EQ(g.use_count(), 0);
+    }(p);
+    EXPECT_EQ(counter.count(), 1);
+    EXPECT_EQ(p.use_count(), 2);
+  }
+  EXPECT_EQ(counter.count(), 1);
+  EXPECT_EQ(foo.use_count(), 1);
+
+  foo.reset();
+  EXPECT_EQ(counter.count(), 0);
+  EXPECT_EQ(foo.use_count(), 0);
+}
+
+TEST(ArenaSmartPtr, shared_ptr_SysArena) {
+  SysArena arena;
+  shared_ptr_test(arena);
+}
+
+TEST(ArenaSmartPtr, shared_ptr_StlAlloc_SysArena) {
+  SysArena arena;
+  StlAllocator<SysArena, Foo> alloc(&arena);
+  shared_ptr_test(alloc);
+}
+
+int main(int argc, char *argv[]) {
+  testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}
diff --git a/folly/test/HasMemberFnTraitsTest.cpp b/folly/test/HasMemberFnTraitsTest.cpp
new file mode 100644
index 00000000..50efce83
--- /dev/null
+++ b/folly/test/HasMemberFnTraitsTest.cpp
@@ -0,0 +1,122 @@
+/*
+ * Copyright 2013 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+/*
+ * @author: Marcelo Juchem <marcelo@fb.com>
+ */
+
+#include "folly/Traits.h"
+
+#include <gtest/gtest.h>
+#include <glog/logging.h>
+
+#include <string>
+
+using namespace std;
+using namespace folly;
+
+FOLLY_CREATE_HAS_MEMBER_FN_TRAITS(has_test, test);
+
+struct Foo {
+  int test();
+  int test() const;
+  string test(const string&) const;
+};
+
+struct Bar {
+  int test();
+  double test(int,long);
+  long test(int) const;
+};
+
+struct Gaz {
+  void test();
+  void test() const;
+  void test() volatile;
+  void test() const volatile;
+};
+
+struct NoCV {
+  void test();
+};
+
+struct Const {
+  void test() const;
+};
+
+struct Volatile {
+  void test() volatile;
+};
+
+struct CV {
+  void test() const volatile;
+};
+
+#define LOG_VALUE(x) []() { \
+  LOG(INFO) << #x << ": " << boolalpha << (x); \
+  return x; \
+}()
+
+TEST(HasMemberFnTraits, DirectMembers) {
+  EXPECT_TRUE(LOG_VALUE((has_test<Foo, int()>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Foo, int() const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Foo, double(int, long)>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Foo, string(const string&) const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Foo, long(int) const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Foo, string(string) const>::value)));
+
+  EXPECT_TRUE(LOG_VALUE((has_test<Bar, int()>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Bar, int() const>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Bar, double(int, long)>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Bar, string(const string&) const>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Bar, long(int) const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Bar, string(string) const>::value)));
+
+  EXPECT_TRUE(LOG_VALUE((has_test<Gaz, void()>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Gaz, void() const>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Gaz, void() volatile>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Gaz, void() const volatile>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Gaz, void() volatile const>::value)));
+
+  EXPECT_TRUE(LOG_VALUE((has_test<NoCV, void()>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<NoCV, void() const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<NoCV, void() volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<NoCV, void() const volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<NoCV, void() volatile const>::value)));
+
+  EXPECT_FALSE(LOG_VALUE((has_test<Const, void()>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Const, void() const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Const, void() volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Const, void() const volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Const, void() volatile const>::value)));
+
+  EXPECT_FALSE(LOG_VALUE((has_test<Volatile, void()>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Volatile, void() const>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<Volatile, void() volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Volatile, void() const volatile>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<Volatile, void() volatile const>::value)));
+
+  EXPECT_FALSE(LOG_VALUE((has_test<CV, void()>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<CV, void() const>::value)));
+  EXPECT_FALSE(LOG_VALUE((has_test<CV, void() volatile>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<CV, void() const volatile>::value)));
+  EXPECT_TRUE(LOG_VALUE((has_test<CV, void() volatile const>::value)));
+}
+
+int main(int argc, char *argv[]) {
+  testing::InitGoogleTest(&argc, argv);
+  return RUN_ALL_TESTS();
+}
-- 
2.34.1