2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
20 #include <folly/AtomicLinkedList.h>
21 #include <folly/portability/GTest.h>
23 class TestIntrusiveObject {
25 explicit TestIntrusiveObject(size_t id__) : id_(id__) {}
31 folly::AtomicIntrusiveLinkedListHook<TestIntrusiveObject> hook_;
35 using List = folly::AtomicIntrusiveLinkedList<
37 &TestIntrusiveObject::hook_>;
40 TEST(AtomicIntrusiveLinkedList, Basic) {
41 TestIntrusiveObject a(1), b(2), c(3);
43 TestIntrusiveObject::List list;
45 EXPECT_TRUE(list.empty());
48 EXPECT_TRUE(list.insertHead(&a));
49 EXPECT_FALSE(list.insertHead(&b));
51 EXPECT_FALSE(list.empty());
55 [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
57 EXPECT_TRUE(list.empty());
60 // Try re-inserting the same item (b) and a new item (c)
62 EXPECT_TRUE(list.insertHead(&b));
63 EXPECT_FALSE(list.insertHead(&c));
65 EXPECT_FALSE(list.empty());
69 [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
71 EXPECT_TRUE(list.empty());
74 TestIntrusiveObject::List movedList = std::move(list);
77 TEST(AtomicIntrusiveLinkedList, ReverseSweep) {
78 TestIntrusiveObject a(1), b(2), c(3);
79 TestIntrusiveObject::List list;
83 size_t next_expected_id = 3;
84 list.reverseSweep([&](TestIntrusiveObject* obj) {
85 EXPECT_EQ(next_expected_id--, obj->id());
87 EXPECT_TRUE(list.empty());
88 // Test that we can still insert
90 EXPECT_FALSE(list.empty());
91 list.reverseSweep([](TestIntrusiveObject*) {});
94 TEST(AtomicIntrusiveLinkedList, Move) {
95 TestIntrusiveObject a(1), b(2);
97 TestIntrusiveObject::List list1;
99 EXPECT_TRUE(list1.insertHead(&a));
100 EXPECT_FALSE(list1.insertHead(&b));
102 EXPECT_FALSE(list1.empty());
104 TestIntrusiveObject::List list2(std::move(list1));
106 EXPECT_TRUE(list1.empty());
107 EXPECT_FALSE(list2.empty());
109 TestIntrusiveObject::List list3;
111 EXPECT_TRUE(list3.empty());
113 list3 = std::move(list2);
115 EXPECT_TRUE(list2.empty());
116 EXPECT_FALSE(list3.empty());
120 [&](TestIntrusiveObject* obj) mutable { EXPECT_EQ(++id, obj->id()); });
123 TEST(AtomicIntrusiveLinkedList, Stress) {
124 constexpr size_t kNumThreads = 32;
125 constexpr size_t kNumElements = 100000;
127 std::vector<TestIntrusiveObject> elements;
128 for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
129 elements.emplace_back(i);
132 TestIntrusiveObject::List list;
134 std::vector<std::thread> threads;
135 for (size_t threadId = 0; threadId < kNumThreads; ++threadId) {
136 threads.emplace_back(
137 [threadId, kNumThreads, kNumElements, &list, &elements]() {
138 for (size_t id = 0; id < kNumElements; ++id) {
139 list.insertHead(&elements[threadId + kNumThreads * id]);
144 std::vector<size_t> ids;
145 TestIntrusiveObject* prev{nullptr};
147 while (ids.size() < kNumThreads * kNumElements) {
148 list.sweep([&](TestIntrusiveObject* current) {
149 ids.push_back(current->id());
151 if (prev && prev->id() % kNumThreads == current->id() % kNumThreads) {
152 EXPECT_EQ(prev->id() + kNumThreads, current->id());
159 std::sort(ids.begin(), ids.end());
161 for (size_t i = 0; i < kNumThreads * kNumElements; ++i) {
162 EXPECT_EQ(i, ids[i]);
165 for (auto& thread : threads) {
172 TestObject(size_t id__, const std::shared_ptr<void>& ptr)
173 : id_(id__), ptr_(ptr) {}
181 std::shared_ptr<void> ptr_;
184 TEST(AtomicLinkedList, Basic) {
185 constexpr size_t kNumElements = 10;
187 using List = folly::AtomicLinkedList<TestObject>;
190 std::shared_ptr<void> ptr = std::make_shared<int>(42);
192 for (size_t id = 0; id < kNumElements; ++id) {
193 list.insertHead({id, ptr});
198 list.sweep([&](TestObject object) {
199 EXPECT_EQ(counter, object.id());
201 EXPECT_EQ(1 + kNumElements - counter, ptr.use_count());
206 EXPECT_TRUE(ptr.unique());