/*
- * 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.
// @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/Memory.h>
#include <folly/String.h>
-#include <gtest/gtest.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 folly {
+template <>
+struct IsArenaAllocator<ParanoidArenaAlloc<SysArena>> : std::true_type {};
+}
+
+namespace {
+
using namespace folly;
using std::vector;
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;
}
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;
}
}
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;
}
};
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) {
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);