Fix copyright lines for Bits.h and move BitsBenchmark.cpp

[folly.git] / folly / test / ConcurrentSkipListTest.cpp

diff --git a/folly/test/ConcurrentSkipListTest.cpp b/folly/test/ConcurrentSkipListTest.cpp
index f3c9c9723ba359b96b890a4c9c2776cfbc024fa2..c6c0a8acdbe1957b2efc900fa70e2da65b9a6581 100644 (file)
--- a/folly/test/ConcurrentSkipListTest.cpp
+++ b/folly/test/ConcurrentSkipListTest.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
@@ -16,23 +16,57 @@
 
 // @author: Xin Liu <xliux@fb.com>
 
+#include <folly/ConcurrentSkipList.h>
+
+#include <atomic>
 #include <memory>
 #include <set>
-#include <vector>
-#include <thread>
 #include <system_error>
+#include <thread>
+#include <vector>
 
 #include <glog/logging.h>
-#include <gflags/gflags.h>
-#include "folly/ConcurrentSkipList.h"
-#include "folly/Foreach.h"
-#include "folly/String.h"
-#include <gtest/gtest.h>
+
+#include <folly/Memory.h>
+#include <folly/String.h>
+#include <folly/container/Foreach.h>
+#include <folly/memory/Arena.h>
+#include <folly/portability/GFlags.h>
+#include <folly/portability/GTest.h>
 
 DEFINE_int32(num_threads, 12, "num concurrent threads to test");
 
 namespace {
 
+template <typename ParentAlloc>
+struct ParanoidArenaAlloc {
+  explicit ParanoidArenaAlloc(ParentAlloc* arena) : arena_(arena) {}
+
+  void* allocate(size_t size) {
+    void* result = arena_->allocate(size);
+    allocated_.insert(result);
+    return result;
+  }
+
+  void deallocate(void* ptr) {
+    EXPECT_EQ(1, allocated_.erase(ptr));
+    arena_->deallocate(ptr);
+  }
+
+  bool isEmpty() const { return allocated_.empty(); }
+
+  ParentAlloc* arena_;
+  std::set<void*> allocated_;
+};
+} // namespace
+
+namespace folly {
+template <>
+struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
+} // namespace folly
+
+namespace {
+
 using namespace folly;
 using std::vector;
 
@@ -81,7 +115,9 @@ static void concurrentSkip(const vector<ValueType> *values,
   int64_t sum = 0;
   SkipListAccessor::Skipper skipper(skipList);
   FOR_EACH(it, *values) {
-    if (skipper.to(*it)) sum += *it;
+    if (skipper.to(*it)) {
+      sum += *it;
+    }
   }
   VLOG(20) << "sum = " << sum;
 }
@@ -184,8 +220,8 @@ TEST(ConcurrentSkipList, SequentialAccess) {
     skipList.add(3);
     CHECK(skipList.contains(3));
     int pos = 0;
-    FOR_EACH(it, skipList) {
-      LOG(INFO) << "pos= " << pos++ << " value= " << *it;
+    for (auto entry : skipList) {
+      LOG(INFO) << "pos= " << pos++ << " value= " << entry;
     }
   }
 
@@ -232,8 +268,12 @@ TEST(ConcurrentSkipList, TestStringType) {
 struct UniquePtrComp {
   bool operator ()(
       const std::unique_ptr<int> &x, const std::unique_ptr<int> &y) const {
-    if (!x) return false;
-    if (!y) return true;
+    if (!x) {
+      return false;
+    }
+    if (!y) {
+      return true;
+    }
     return *x < *y;
   }
 };
@@ -246,7 +286,7 @@ TEST(ConcurrentSkipList, TestMovableData) {
 
   static const int N = 10;
   for (int i = 0; i < N; ++i) {
-    accessor.insert(std::unique_ptr<int>(new int(i)));
+    accessor.insert(std::make_unique<int>(i));
   }
 
   for (int i = 0; i < N; ++i) {
@@ -273,7 +313,7 @@ void testConcurrentAdd(int numThreads) {
       << ": could only create " << threads.size() << " threads out of "
       << numThreads;
   }
-  for (int i = 0; i < threads.size(); ++i) {
+  for (size_t i = 0; i < threads.size(); ++i) {
     threads[i].join();
   }
 
@@ -384,12 +424,86 @@ TEST(ConcurrentSkipList, ConcurrentAccess) {
   testConcurrentAccess(1000000, 100000, kMaxValue);
 }
 
-}  // namespace
+struct NonTrivialValue {
+  static std::atomic<int> InstanceCounter;
+  static const int kBadPayLoad;
+
+  NonTrivialValue() : payload_(kBadPayLoad) { ++InstanceCounter; }
+
+  explicit NonTrivialValue(int payload) : payload_(payload) {
+    ++InstanceCounter;
+  }
+
+  NonTrivialValue(const NonTrivialValue& rhs) : payload_(rhs.payload_) {
+    ++InstanceCounter;
+  }
+
+  NonTrivialValue& operator=(const NonTrivialValue& rhs) {
+    payload_ = rhs.payload_;
+    return *this;
+  }
+
+  ~NonTrivialValue() { --InstanceCounter; }
+
+  bool operator<(const NonTrivialValue& rhs) const {
+    EXPECT_NE(kBadPayLoad, payload_);
+    EXPECT_NE(kBadPayLoad, rhs.payload_);
+    return payload_ < rhs.payload_;
+  }
+
+ private:
+  int payload_;
+};
+
+std::atomic<int> NonTrivialValue::InstanceCounter(0);
+const int NonTrivialValue::kBadPayLoad = 0xDEADBEEF;
+
+template <typename SkipListPtrType>
+void TestNonTrivialDeallocation(SkipListPtrType& list) {
+  {
+    auto accessor = typename SkipListPtrType::element_type::Accessor(list);
+    static const size_t N = 10000;
+    for (size_t i = 0; i < N; ++i) {
+      accessor.add(NonTrivialValue(i));
+    }
+    list.reset();
+  }
+  EXPECT_EQ(0, NonTrivialValue::InstanceCounter);
+}
+
+template <typename ParentAlloc>
+void NonTrivialDeallocationWithParanoid() {
+  using Alloc = ParanoidArenaAlloc<ParentAlloc>;
+  using ParanoidSkipListType =
+      ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, Alloc>;
+  ParentAlloc parentAlloc;
+  Alloc paranoidAlloc(&parentAlloc);
+  auto list = ParanoidSkipListType::createInstance(10, paranoidAlloc);
+  TestNonTrivialDeallocation(list);
+  EXPECT_TRUE(paranoidAlloc.isEmpty());
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysAlloc) {
+  NonTrivialDeallocationWithParanoid<SysAlloc>();
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithParanoidSysArena) {
+  NonTrivialDeallocationWithParanoid<SysArena>();
+}
+
+TEST(ConcurrentSkipList, NonTrivialDeallocationWithSysArena) {
+  using SysArenaSkipListType =
+      ConcurrentSkipList<NonTrivialValue, std::less<NonTrivialValue>, SysArena>;
+  auto list = SysArenaSkipListType::createInstance(10);
+  TestNonTrivialDeallocation(list);
+}
+
+} // namespace
 
 int main(int argc, char* argv[]) {
   testing::InitGoogleTest(&argc, argv);
   google::InitGoogleLogging(argv[0]);
-  google::ParseCommandLineFlags(&argc, &argv, true);
+  gflags::ParseCommandLineFlags(&argc, &argv, true);
 
   return RUN_ALL_TESTS();
 }