Line data Source code
1 : // Copyright 2018 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include <iterator>
6 :
7 : #include "src/v8.h"
8 :
9 : #include "src/base/threaded-list.h"
10 : #include "testing/gtest-support.h"
11 :
12 : namespace v8 {
13 : namespace base {
14 :
15 : struct ThreadedListTestNode {
16 81 : ThreadedListTestNode() : next_(nullptr), other_next_(nullptr) {}
17 :
18 : ThreadedListTestNode** next() { return &next_; }
19 :
20 : ThreadedListTestNode* next_;
21 :
22 : struct OtherTraits {
23 : static ThreadedListTestNode** start(ThreadedListTestNode** h) { return h; }
24 : static ThreadedListTestNode* const* start(ThreadedListTestNode* const* h) {
25 : return h;
26 : }
27 : static ThreadedListTestNode** next(ThreadedListTestNode* t) {
28 : return t->other_next();
29 : }
30 : };
31 :
32 : ThreadedListTestNode** other_next() { return &other_next_; }
33 :
34 : ThreadedListTestNode* other_next_;
35 : };
36 :
37 13 : struct ThreadedListTest : public ::testing::Test {
38 : static const size_t INIT_NODES = 5;
39 91 : ThreadedListTest() {}
40 :
41 13 : void SetUp() override {
42 78 : for (size_t i = 0; i < INIT_NODES; i++) {
43 65 : nodes[i] = ThreadedListTestNode();
44 : }
45 :
46 65 : for (size_t i = 0; i < INIT_NODES; i++) {
47 65 : list.Add(&nodes[i]);
48 : normal_next_list.Add(&nodes[i]);
49 : }
50 :
51 : // Verify if setup worked
52 13 : CHECK(list.Verify());
53 13 : CHECK_EQ(list.LengthForTest(), INIT_NODES);
54 13 : CHECK(normal_next_list.Verify());
55 13 : CHECK_EQ(normal_next_list.LengthForTest(), INIT_NODES);
56 :
57 13 : extra_test_node_0 = ThreadedListTestNode();
58 13 : extra_test_node_1 = ThreadedListTestNode();
59 13 : extra_test_node_2 = ThreadedListTestNode();
60 :
61 13 : extra_test_list.Add(&extra_test_node_0);
62 13 : extra_test_list.Add(&extra_test_node_1);
63 13 : extra_test_list.Add(&extra_test_node_2);
64 13 : CHECK_EQ(extra_test_list.LengthForTest(), 3);
65 13 : CHECK(extra_test_list.Verify());
66 :
67 : normal_extra_test_list.Add(&extra_test_node_0);
68 : normal_extra_test_list.Add(&extra_test_node_1);
69 : normal_extra_test_list.Add(&extra_test_node_2);
70 13 : CHECK_EQ(normal_extra_test_list.LengthForTest(), 3);
71 13 : CHECK(normal_extra_test_list.Verify());
72 13 : }
73 :
74 13 : void TearDown() override {
75 : // Check if the normal list threaded through next is still untouched.
76 13 : CHECK(normal_next_list.Verify());
77 13 : CHECK_EQ(normal_next_list.LengthForTest(), INIT_NODES);
78 26 : CHECK_EQ(normal_next_list.AtForTest(0), &nodes[0]);
79 26 : CHECK_EQ(normal_next_list.AtForTest(4), &nodes[4]);
80 13 : CHECK(normal_extra_test_list.Verify());
81 13 : CHECK_EQ(normal_extra_test_list.LengthForTest(), 3);
82 26 : CHECK_EQ(normal_extra_test_list.AtForTest(0), &extra_test_node_0);
83 26 : CHECK_EQ(normal_extra_test_list.AtForTest(2), &extra_test_node_2);
84 :
85 : list.Clear();
86 : extra_test_list.Clear();
87 : }
88 :
89 : ThreadedListTestNode nodes[INIT_NODES];
90 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits> list;
91 : ThreadedList<ThreadedListTestNode> normal_next_list;
92 :
93 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits>
94 : extra_test_list;
95 : ThreadedList<ThreadedListTestNode> normal_extra_test_list;
96 : ThreadedListTestNode extra_test_node_0;
97 : ThreadedListTestNode extra_test_node_1;
98 : ThreadedListTestNode extra_test_node_2;
99 : };
100 :
101 15129 : TEST_F(ThreadedListTest, Add) {
102 1 : CHECK_EQ(list.LengthForTest(), 5);
103 : ThreadedListTestNode new_node;
104 : // Add to existing list
105 : list.Add(&new_node);
106 1 : list.Verify();
107 1 : CHECK_EQ(list.LengthForTest(), 6);
108 1 : CHECK_EQ(list.AtForTest(5), &new_node);
109 :
110 : list.Clear();
111 1 : CHECK_EQ(list.LengthForTest(), 0);
112 :
113 1 : new_node = ThreadedListTestNode();
114 : // Add to empty list
115 : list.Add(&new_node);
116 1 : list.Verify();
117 1 : CHECK_EQ(list.LengthForTest(), 1);
118 1 : CHECK_EQ(list.AtForTest(0), &new_node);
119 1 : }
120 :
121 15129 : TEST_F(ThreadedListTest, AddFront) {
122 1 : CHECK_EQ(list.LengthForTest(), 5);
123 : ThreadedListTestNode new_node;
124 : // AddFront to existing list
125 : list.AddFront(&new_node);
126 1 : list.Verify();
127 1 : CHECK_EQ(list.LengthForTest(), 6);
128 1 : CHECK_EQ(list.first(), &new_node);
129 :
130 : list.Clear();
131 1 : CHECK_EQ(list.LengthForTest(), 0);
132 :
133 1 : new_node = ThreadedListTestNode();
134 : // AddFront to empty list
135 : list.AddFront(&new_node);
136 1 : list.Verify();
137 1 : CHECK_EQ(list.LengthForTest(), 1);
138 1 : CHECK_EQ(list.first(), &new_node);
139 1 : }
140 :
141 15129 : TEST_F(ThreadedListTest, DropHead) {
142 3 : CHECK_EQ(extra_test_list.LengthForTest(), 3);
143 2 : CHECK_EQ(extra_test_list.first(), &extra_test_node_0);
144 : extra_test_list.DropHead();
145 1 : extra_test_list.Verify();
146 2 : CHECK_EQ(extra_test_list.first(), &extra_test_node_1);
147 1 : CHECK_EQ(extra_test_list.LengthForTest(), 2);
148 1 : }
149 :
150 15129 : TEST_F(ThreadedListTest, Append) {
151 2 : auto initial_extra_list_end = extra_test_list.end();
152 1 : CHECK_EQ(list.LengthForTest(), 5);
153 : list.Append(std::move(extra_test_list));
154 1 : list.Verify();
155 1 : extra_test_list.Verify();
156 1 : CHECK(extra_test_list.is_empty());
157 1 : CHECK_EQ(list.LengthForTest(), 8);
158 2 : CHECK_EQ(list.AtForTest(4), &nodes[4]);
159 2 : CHECK_EQ(list.AtForTest(5), &extra_test_node_0);
160 2 : CHECK_EQ(list.end(), initial_extra_list_end);
161 1 : }
162 :
163 15129 : TEST_F(ThreadedListTest, AppendOutOfScope) {
164 : ThreadedListTestNode local_extra_test_node_0;
165 1 : CHECK_EQ(list.LengthForTest(), 5);
166 : {
167 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits>
168 : scoped_extra_test_list;
169 :
170 : list.Append(std::move(scoped_extra_test_list));
171 : }
172 : list.Add(&local_extra_test_node_0);
173 :
174 1 : list.Verify();
175 1 : CHECK_EQ(list.LengthForTest(), 6);
176 2 : CHECK_EQ(list.AtForTest(4), &nodes[4]);
177 1 : CHECK_EQ(list.AtForTest(5), &local_extra_test_node_0);
178 1 : }
179 :
180 15129 : TEST_F(ThreadedListTest, Prepend) {
181 2 : CHECK_EQ(list.LengthForTest(), 5);
182 1 : list.Prepend(std::move(extra_test_list));
183 1 : list.Verify();
184 1 : extra_test_list.Verify();
185 1 : CHECK(extra_test_list.is_empty());
186 1 : CHECK_EQ(list.LengthForTest(), 8);
187 2 : CHECK_EQ(list.first(), &extra_test_node_0);
188 2 : CHECK_EQ(list.AtForTest(2), &extra_test_node_2);
189 2 : CHECK_EQ(list.AtForTest(3), &nodes[0]);
190 1 : }
191 :
192 15129 : TEST_F(ThreadedListTest, Clear) {
193 1 : CHECK_NE(list.LengthForTest(), 0);
194 : list.Clear();
195 1 : CHECK_EQ(list.LengthForTest(), 0);
196 1 : CHECK_NULL(list.first());
197 1 : }
198 :
199 15129 : TEST_F(ThreadedListTest, MoveAssign) {
200 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits> m_list;
201 1 : CHECK_EQ(extra_test_list.LengthForTest(), 3);
202 : m_list = std::move(extra_test_list);
203 :
204 1 : m_list.Verify();
205 1 : CHECK_EQ(m_list.first(), &extra_test_node_0);
206 1 : CHECK_EQ(m_list.LengthForTest(), 3);
207 :
208 : // move assign from empty list
209 : extra_test_list.Clear();
210 1 : CHECK_EQ(extra_test_list.LengthForTest(), 0);
211 : m_list = std::move(extra_test_list);
212 1 : CHECK_EQ(m_list.LengthForTest(), 0);
213 :
214 1 : m_list.Verify();
215 1 : CHECK_NULL(m_list.first());
216 1 : }
217 :
218 15129 : TEST_F(ThreadedListTest, MoveCtor) {
219 1 : CHECK_EQ(extra_test_list.LengthForTest(), 3);
220 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits> m_list(
221 : std::move(extra_test_list));
222 :
223 1 : m_list.Verify();
224 1 : CHECK_EQ(m_list.LengthForTest(), 3);
225 1 : CHECK_EQ(m_list.first(), &extra_test_node_0);
226 :
227 : // move construct from empty list
228 : extra_test_list.Clear();
229 1 : CHECK_EQ(extra_test_list.LengthForTest(), 0);
230 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits> m_list2(
231 : std::move(extra_test_list));
232 1 : CHECK_EQ(m_list2.LengthForTest(), 0);
233 :
234 1 : m_list2.Verify();
235 1 : CHECK_NULL(m_list2.first());
236 1 : }
237 :
238 15129 : TEST_F(ThreadedListTest, Remove) {
239 5 : CHECK_EQ(list.LengthForTest(), 5);
240 :
241 : // Remove first
242 2 : CHECK_EQ(list.first(), &nodes[0]);
243 1 : list.Remove(&nodes[0]);
244 1 : list.Verify();
245 2 : CHECK_EQ(list.first(), &nodes[1]);
246 1 : CHECK_EQ(list.LengthForTest(), 4);
247 :
248 : // Remove middle
249 1 : list.Remove(&nodes[2]);
250 1 : list.Verify();
251 1 : CHECK_EQ(list.LengthForTest(), 3);
252 1 : CHECK_EQ(list.first(), &nodes[1]);
253 2 : CHECK_EQ(list.AtForTest(1), &nodes[3]);
254 :
255 : // Remove last
256 1 : list.Remove(&nodes[4]);
257 1 : list.Verify();
258 1 : CHECK_EQ(list.LengthForTest(), 2);
259 1 : CHECK_EQ(list.first(), &nodes[1]);
260 1 : CHECK_EQ(list.AtForTest(1), &nodes[3]);
261 :
262 : // Remove rest
263 1 : list.Remove(&nodes[1]);
264 1 : list.Remove(&nodes[3]);
265 1 : list.Verify();
266 1 : CHECK_EQ(list.LengthForTest(), 0);
267 :
268 : // Remove not found
269 1 : list.Remove(&nodes[4]);
270 1 : list.Verify();
271 1 : CHECK_EQ(list.LengthForTest(), 0);
272 1 : }
273 :
274 15129 : TEST_F(ThreadedListTest, Rewind) {
275 1 : CHECK_EQ(extra_test_list.LengthForTest(), 3);
276 3 : for (auto iter = extra_test_list.begin(); iter != extra_test_list.end();
277 : ++iter) {
278 3 : if (*iter == &extra_test_node_2) {
279 : extra_test_list.Rewind(iter);
280 : break;
281 : }
282 : }
283 1 : CHECK_EQ(extra_test_list.LengthForTest(), 2);
284 : auto iter = extra_test_list.begin();
285 1 : CHECK_EQ(*iter, &extra_test_node_0);
286 : std::advance(iter, 1);
287 1 : CHECK_EQ(*iter, &extra_test_node_1);
288 :
289 : extra_test_list.Rewind(extra_test_list.begin());
290 1 : CHECK_EQ(extra_test_list.LengthForTest(), 0);
291 1 : }
292 :
293 15129 : TEST_F(ThreadedListTest, IterComp) {
294 : ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits> c_list =
295 : std::move(extra_test_list);
296 : bool found_first;
297 5 : for (auto iter = c_list.begin(); iter != c_list.end(); ++iter) {
298 : // This triggers the operator== on the iterator
299 : if (iter == c_list.begin()) {
300 : found_first = true;
301 : }
302 : }
303 : CHECK(found_first);
304 1 : }
305 :
306 15129 : TEST_F(ThreadedListTest, ConstIterComp) {
307 : const ThreadedList<ThreadedListTestNode, ThreadedListTestNode::OtherTraits>
308 : c_list = std::move(extra_test_list);
309 : bool found_first;
310 5 : for (auto iter = c_list.begin(); iter != c_list.end(); ++iter) {
311 : // This triggers the operator== on the iterator
312 : if (iter == c_list.begin()) {
313 : found_first = true;
314 : }
315 : }
316 : CHECK(found_first);
317 1 : }
318 :
319 : } // namespace base
320 9075 : } // namespace v8
|
