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