/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2011-present 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 <system_error>
+#include <thread>
#include <vector>
-#include <boost/thread.hpp>
#include <glog/logging.h>
-#include <gflags/gflags.h>
-#include "folly/ConcurrentSkipList.h"
-#include "folly/Foreach.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;
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;
}
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));
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;
}
}
}
+static std::string makeRandomeString(int len) {
+ std::string s;
+ for (int j = 0; j < len; j++) {
+ s.push_back((rand() % 26) + 'A');
+ }
+ return s;
+}
+
+TEST(ConcurrentSkipList, TestStringType) {
+ typedef folly::ConcurrentSkipList<std::string> SkipListT;
+ std::shared_ptr<SkipListT> skip = SkipListT::createInstance();
+ SkipListT::Accessor accessor(skip);
+ {
+ for (int i = 0; i < 100000; i++) {
+ std::string s = makeRandomeString(7);
+ accessor.insert(s);
+ }
+ }
+ EXPECT_TRUE(std::is_sorted(accessor.begin(), accessor.end()));
+}
+
+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;
+ }
+ return *x < *y;
+ }
+};
+
+TEST(ConcurrentSkipList, TestMovableData) {
+ typedef folly::ConcurrentSkipList<std::unique_ptr<int>, UniquePtrComp>
+ SkipListT;
+ auto sl = SkipListT::createInstance() ;
+ SkipListT::Accessor accessor(sl);
+
+ static const int N = 10;
+ for (int i = 0; i < N; ++i) {
+ accessor.insert(std::make_unique<int>(i));
+ }
+
+ for (int i = 0; i < N; ++i) {
+ EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(i))) !=
+ accessor.end());
+ }
+ EXPECT_TRUE(accessor.find(std::unique_ptr<int>(new int(N))) ==
+ accessor.end());
+}
+
void testConcurrentAdd(int numThreads) {
auto skipList(SkipListType::create(kHeadHeight));
- vector<boost::thread> threads;
+ vector<std::thread> threads;
vector<SetType> verifiers(numThreads);
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(boost::thread(
- &randomAdding, 100, skipList, &verifiers[i], kMaxValue));
+ try {
+ for (int i = 0; i < numThreads; ++i) {
+ threads.push_back(std::thread(
+ &randomAdding, 100, skipList, &verifiers[i], kMaxValue));
+ }
+ } catch (const std::system_error& e) {
+ LOG(WARNING)
+ << "Caught " << exceptionStr(e)
+ << ": 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();
}
skipList.add(i);
}
- vector<boost::thread> threads;
+ vector<std::thread> threads;
vector<SetType > verifiers(numThreads);
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(boost::thread(
- &randomRemoval, 100, skipList, &verifiers[i], maxValue));
+ try {
+ for (int i = 0; i < numThreads; ++i) {
+ threads.push_back(std::thread(
+ &randomRemoval, 100, skipList, &verifiers[i], maxValue));
+ }
+ } catch (const std::system_error& e) {
+ LOG(WARNING)
+ << "Caught " << exceptionStr(e)
+ << ": could only create " << threads.size() << " threads out of "
+ << numThreads;
}
FOR_EACH(t, threads) {
(*t).join();
std::sort(skipValues[i].begin(), skipValues[i].end());
}
- vector<boost::thread> threads;
+ vector<std::thread> threads;
for (int i = 0; i < FLAGS_num_threads; ++i) {
switch (i % 8) {
case 0:
case 1:
- threads.push_back(boost::thread(
+ threads.push_back(std::thread(
randomAdding, numInsertions, skipList, &verifiers[i], maxValue));
break;
case 2:
- threads.push_back(boost::thread(
+ threads.push_back(std::thread(
randomRemoval, numDeletions, skipList, &verifiers[i], maxValue));
break;
case 3:
- threads.push_back(boost::thread(
+ threads.push_back(std::thread(
concurrentSkip, &skipValues[i], skipList));
break;
default:
- threads.push_back(boost::thread(sumAllValues, skipList, &sums[i]));
+ threads.push_back(std::thread(sumAllValues, skipList, &sums[i]));
break;
}
}
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();
}
projects / folly.git / blobdiff