/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2014 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 <memory>
#include <set>
#include <vector>
#include <thread>
+#include <system_error>
#include <glog/logging.h>
#include <gflags/gflags.h>
-#include "folly/ConcurrentSkipList.h"
-#include "folly/Foreach.h"
-#include "gtest/gtest.h"
+#include <folly/ConcurrentSkipList.h>
+#include <folly/Foreach.h>
+#include <folly/String.h>
+#include <gtest/gtest.h>
DEFINE_int32(num_threads, 12, "num concurrent threads to test");
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));
}
+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::unique_ptr<int>(new 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<std::thread> threads;
vector<SetType> verifiers(numThreads);
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(std::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) {
threads[i].join();
vector<std::thread> threads;
vector<SetType > verifiers(numThreads);
- for (int i = 0; i < numThreads; ++i) {
- threads.push_back(std::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();