1 // Copyright 2009 The Chromium Authors
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 "base/containers/linked_list.h"
6
7 #include "base/test/gtest_util.h"
8 #include "testing/gtest/include/gtest/gtest.h"
9
10 namespace base {
11 namespace {
12
13 class Node : public LinkNode<Node> {
14 public:
Node(int id)15 explicit Node(int id) : id_(id) {}
16
id() const17 int id() const { return id_; }
18
19 private:
20 int id_;
21 };
22
23 class MultipleInheritanceNodeBase {
24 public:
MultipleInheritanceNodeBase()25 MultipleInheritanceNodeBase() : field_taking_up_space_(0) {}
26 int field_taking_up_space_;
27 };
28
29 class MultipleInheritanceNode : public MultipleInheritanceNodeBase,
30 public LinkNode<MultipleInheritanceNode> {
31 public:
32 MultipleInheritanceNode() = default;
33 };
34
35 class MovableNode : public LinkNode<MovableNode> {
36 public:
MovableNode(int id)37 explicit MovableNode(int id) : id_(id) {}
38
39 MovableNode(MovableNode&&) = default;
40
id() const41 int id() const { return id_; }
42
43 private:
44 int id_;
45 };
46
47 // Checks that when iterating |list| (either from head to tail, or from
48 // tail to head, as determined by |forward|), we get back |node_ids|,
49 // which is an array of size |num_nodes|.
ExpectListContentsForDirection(const LinkedList<Node> & list,int num_nodes,const int * node_ids,bool forward)50 void ExpectListContentsForDirection(const LinkedList<Node>& list,
51 int num_nodes, const int* node_ids, bool forward) {
52 int i = 0;
53 for (const LinkNode<Node>* node = (forward ? list.head() : list.tail());
54 node != list.end();
55 node = (forward ? node->next() : node->previous())) {
56 ASSERT_LT(i, num_nodes);
57 int index_of_id = forward ? i : num_nodes - i - 1;
58 EXPECT_EQ(node_ids[index_of_id], node->value()->id());
59 ++i;
60 }
61 EXPECT_EQ(num_nodes, i);
62 }
63
ExpectListContents(const LinkedList<Node> & list,int num_nodes,const int * node_ids)64 void ExpectListContents(const LinkedList<Node>& list,
65 int num_nodes,
66 const int* node_ids) {
67 {
68 SCOPED_TRACE("Iterating forward (from head to tail)");
69 ExpectListContentsForDirection(list, num_nodes, node_ids, true);
70 }
71 {
72 SCOPED_TRACE("Iterating backward (from tail to head)");
73 ExpectListContentsForDirection(list, num_nodes, node_ids, false);
74 }
75 }
76
TEST(LinkedList,Empty)77 TEST(LinkedList, Empty) {
78 LinkedList<Node> list;
79 EXPECT_EQ(list.end(), list.head());
80 EXPECT_EQ(list.end(), list.tail());
81 ExpectListContents(list, 0, nullptr);
82 }
83
TEST(LinkedList,Append)84 TEST(LinkedList, Append) {
85 LinkedList<Node> list;
86 ExpectListContents(list, 0, nullptr);
87
88 Node n1(1);
89 list.Append(&n1);
90
91 EXPECT_EQ(&n1, list.head());
92 EXPECT_EQ(&n1, list.tail());
93 {
94 const int expected[] = {1};
95 ExpectListContents(list, std::size(expected), expected);
96 }
97
98 Node n2(2);
99 list.Append(&n2);
100
101 EXPECT_EQ(&n1, list.head());
102 EXPECT_EQ(&n2, list.tail());
103 {
104 const int expected[] = {1, 2};
105 ExpectListContents(list, std::size(expected), expected);
106 }
107
108 Node n3(3);
109 list.Append(&n3);
110
111 EXPECT_EQ(&n1, list.head());
112 EXPECT_EQ(&n3, list.tail());
113 {
114 const int expected[] = {1, 2, 3};
115 ExpectListContents(list, std::size(expected), expected);
116 }
117 }
118
TEST(LinkedList,RemoveFromList)119 TEST(LinkedList, RemoveFromList) {
120 LinkedList<Node> list;
121
122 Node n1(1);
123 Node n2(2);
124 Node n3(3);
125 Node n4(4);
126 Node n5(5);
127
128 list.Append(&n1);
129 list.Append(&n2);
130 list.Append(&n3);
131 list.Append(&n4);
132 list.Append(&n5);
133
134 EXPECT_EQ(&n1, list.head());
135 EXPECT_EQ(&n5, list.tail());
136 {
137 const int expected[] = {1, 2, 3, 4, 5};
138 ExpectListContents(list, std::size(expected), expected);
139 }
140
141 // Remove from the middle.
142 n3.RemoveFromList();
143
144 EXPECT_EQ(&n1, list.head());
145 EXPECT_EQ(&n5, list.tail());
146 {
147 const int expected[] = {1, 2, 4, 5};
148 ExpectListContents(list, std::size(expected), expected);
149 }
150
151 // Remove from the tail.
152 n5.RemoveFromList();
153
154 EXPECT_EQ(&n1, list.head());
155 EXPECT_EQ(&n4, list.tail());
156 {
157 const int expected[] = {1, 2, 4};
158 ExpectListContents(list, std::size(expected), expected);
159 }
160
161 // Remove from the head.
162 n1.RemoveFromList();
163
164 EXPECT_EQ(&n2, list.head());
165 EXPECT_EQ(&n4, list.tail());
166 {
167 const int expected[] = {2, 4};
168 ExpectListContents(list, std::size(expected), expected);
169 }
170
171 // Empty the list.
172 n2.RemoveFromList();
173 n4.RemoveFromList();
174
175 ExpectListContents(list, 0, nullptr);
176 EXPECT_EQ(list.end(), list.head());
177 EXPECT_EQ(list.end(), list.tail());
178
179 // Fill the list once again.
180 list.Append(&n1);
181 list.Append(&n2);
182 list.Append(&n3);
183 list.Append(&n4);
184 list.Append(&n5);
185
186 EXPECT_EQ(&n1, list.head());
187 EXPECT_EQ(&n5, list.tail());
188 {
189 const int expected[] = {1, 2, 3, 4, 5};
190 ExpectListContents(list, std::size(expected), expected);
191 }
192 }
193
TEST(LinkedList,InsertBefore)194 TEST(LinkedList, InsertBefore) {
195 LinkedList<Node> list;
196
197 Node n1(1);
198 Node n2(2);
199 Node n3(3);
200 Node n4(4);
201
202 list.Append(&n1);
203 list.Append(&n2);
204
205 EXPECT_EQ(&n1, list.head());
206 EXPECT_EQ(&n2, list.tail());
207 {
208 const int expected[] = {1, 2};
209 ExpectListContents(list, std::size(expected), expected);
210 }
211
212 n3.InsertBefore(&n2);
213
214 EXPECT_EQ(&n1, list.head());
215 EXPECT_EQ(&n2, list.tail());
216 {
217 const int expected[] = {1, 3, 2};
218 ExpectListContents(list, std::size(expected), expected);
219 }
220
221 n4.InsertBefore(&n1);
222
223 EXPECT_EQ(&n4, list.head());
224 EXPECT_EQ(&n2, list.tail());
225 {
226 const int expected[] = {4, 1, 3, 2};
227 ExpectListContents(list, std::size(expected), expected);
228 }
229 }
230
TEST(LinkedList,InsertAfter)231 TEST(LinkedList, InsertAfter) {
232 LinkedList<Node> list;
233
234 Node n1(1);
235 Node n2(2);
236 Node n3(3);
237 Node n4(4);
238
239 list.Append(&n1);
240 list.Append(&n2);
241
242 EXPECT_EQ(&n1, list.head());
243 EXPECT_EQ(&n2, list.tail());
244 {
245 const int expected[] = {1, 2};
246 ExpectListContents(list, std::size(expected), expected);
247 }
248
249 n3.InsertAfter(&n2);
250
251 EXPECT_EQ(&n1, list.head());
252 EXPECT_EQ(&n3, list.tail());
253 {
254 const int expected[] = {1, 2, 3};
255 ExpectListContents(list, std::size(expected), expected);
256 }
257
258 n4.InsertAfter(&n1);
259
260 EXPECT_EQ(&n1, list.head());
261 EXPECT_EQ(&n3, list.tail());
262 {
263 const int expected[] = {1, 4, 2, 3};
264 ExpectListContents(list, std::size(expected), expected);
265 }
266 }
267
TEST(LinkedList,MultipleInheritanceNode)268 TEST(LinkedList, MultipleInheritanceNode) {
269 MultipleInheritanceNode node;
270 EXPECT_EQ(&node, node.value());
271 }
272
TEST(LinkedList,EmptyListIsEmpty)273 TEST(LinkedList, EmptyListIsEmpty) {
274 LinkedList<Node> list;
275 EXPECT_TRUE(list.empty());
276 }
277
TEST(LinkedList,NonEmptyListIsNotEmpty)278 TEST(LinkedList, NonEmptyListIsNotEmpty) {
279 LinkedList<Node> list;
280
281 Node n(1);
282 list.Append(&n);
283
284 EXPECT_FALSE(list.empty());
285 }
286
TEST(LinkedList,EmptiedListIsEmptyAgain)287 TEST(LinkedList, EmptiedListIsEmptyAgain) {
288 LinkedList<Node> list;
289
290 Node n(1);
291 list.Append(&n);
292 n.RemoveFromList();
293
294 EXPECT_TRUE(list.empty());
295 }
296
TEST(LinkedList,NodesCanBeReused)297 TEST(LinkedList, NodesCanBeReused) {
298 LinkedList<Node> list1;
299 LinkedList<Node> list2;
300
301 Node n(1);
302 list1.Append(&n);
303 n.RemoveFromList();
304 list2.Append(&n);
305
306 EXPECT_EQ(list2.head()->value(), &n);
307 }
308
TEST(LinkedList,RemovedNodeHasNullNextPrevious)309 TEST(LinkedList, RemovedNodeHasNullNextPrevious) {
310 LinkedList<Node> list;
311
312 Node n(1);
313 list.Append(&n);
314 n.RemoveFromList();
315
316 EXPECT_EQ(nullptr, n.next());
317 EXPECT_EQ(nullptr, n.previous());
318 }
319
TEST(LinkedList,NodeMoveConstructor)320 TEST(LinkedList, NodeMoveConstructor) {
321 LinkedList<MovableNode> list;
322
323 MovableNode n1(1);
324 MovableNode n2(2);
325 MovableNode n3(3);
326
327 list.Append(&n1);
328 list.Append(&n2);
329 list.Append(&n3);
330
331 EXPECT_EQ(&n1, n2.previous());
332 EXPECT_EQ(&n2, n1.next());
333 EXPECT_EQ(&n3, n2.next());
334 EXPECT_EQ(&n2, n3.previous());
335 EXPECT_EQ(2, n2.id());
336
337 MovableNode n2_new(std::move(n2));
338
339 EXPECT_EQ(nullptr, n2.next());
340 EXPECT_EQ(nullptr, n2.previous());
341
342 EXPECT_EQ(&n1, n2_new.previous());
343 EXPECT_EQ(&n2_new, n1.next());
344 EXPECT_EQ(&n3, n2_new.next());
345 EXPECT_EQ(&n2_new, n3.previous());
346 EXPECT_EQ(2, n2_new.id());
347 }
348
TEST(LinkedListDeathTest,ChecksOnInsertBeforeWhenInList)349 TEST(LinkedListDeathTest, ChecksOnInsertBeforeWhenInList) {
350 LinkedList<Node> list1;
351 LinkedList<Node> list2;
352
353 Node n1(1);
354 Node n2(2);
355 Node n3(3);
356
357 list1.Append(&n1);
358
359 list2.Append(&n2);
360 list2.Append(&n3);
361
362 EXPECT_CHECK_DEATH(n1.InsertBefore(&n3));
363 }
364
TEST(LinkedListDeathTest,ChecksOnInsertAfterWhenInList)365 TEST(LinkedListDeathTest, ChecksOnInsertAfterWhenInList) {
366 LinkedList<Node> list1;
367 LinkedList<Node> list2;
368
369 Node n1(1);
370 Node n2(2);
371 Node n3(3);
372
373 list1.Append(&n1);
374
375 list2.Append(&n2);
376 list2.Append(&n3);
377
378 EXPECT_CHECK_DEATH(n1.InsertAfter(&n2));
379 }
380
381 } // namespace
382 } // namespace base
383