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