X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2Ftest%2FConcurrentSkipListTest.cpp;h=2e578e5aa9ed58429c8271ae075c9f931f20b500;hb=dc1c3dcc04baa70029d16351d4424af4a7ef4385;hp=23c3edbc05f41ffee3d53f33201ee96995f56411;hpb=a88ef0bed6c4b28a89d141e4349d4a2b16ed212d;p=folly.git

diff --git a/folly/test/ConcurrentSkipListTest.cpp b/folly/test/ConcurrentSkipListTest.cpp
index 23c3edbc..2e578e5a 100644
--- a/folly/test/ConcurrentSkipListTest.cpp
+++ b/folly/test/ConcurrentSkipListTest.cpp
@@ -1,5 +1,5 @@
 /*
- * Copyright 2013 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,6 +16,9 @@
 
 // @author: Xin Liu <xliux@fb.com>
 
+#include <folly/ConcurrentSkipList.h>
+
+#include <atomic>
 #include <memory>
 #include <set>
 #include <vector>
@@ -23,16 +26,47 @@
 #include <system_error>
 
 #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/Arena.h>
+#include <folly/Foreach.h>
+#include <folly/Memory.h>
+#include <folly/String.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 folly {
+template <>
+struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
+}
+
+namespace {
+
 using namespace folly;
 using std::vector;
 
@@ -104,8 +138,8 @@ TEST(ConcurrentSkipList, SequentialAccess) {
     LOG(INFO) << "nodetype size=" << sizeof(SkipListNodeType);
 
     auto skipList(SkipListType::create(kHeadHeight));
-    EXPECT_TRUE(skipList.first() == NULL);
-    EXPECT_TRUE(skipList.last() == NULL);
+    EXPECT_TRUE(skipList.first() == nullptr);
+    EXPECT_TRUE(skipList.last() == nullptr);
 
     skipList.add(3);
     EXPECT_TRUE(skipList.contains(3));
@@ -184,8 +218,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;
     }
   }
 
@@ -273,7 +307,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 +418,86 @@ TEST(ConcurrentSkipList, ConcurrentAccess) {
   testConcurrentAccess(1000000, 100000, kMaxValue);
 }
 
+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();
 }