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
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:
MultipleInheritanceNode()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|.
ExpectListContentsForDirection(const LinkedList<Node> & list,int num_nodes,const int * node_ids,bool forward)37 void 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
ExpectListContents(const LinkedList<Node> & list,int num_nodes,const int * node_ids)51 void 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
TEST(LinkedList,Empty)64 TEST(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
TEST(LinkedList,Append)71 TEST(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
TEST(LinkedList,RemoveFromList)106 TEST(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
TEST(LinkedList,InsertBefore)181 TEST(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
TEST(LinkedList,InsertAfter)218 TEST(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
TEST(LinkedList,MultipleInheritanceNode)255 TEST(LinkedList, MultipleInheritanceNode) {
256 MultipleInheritanceNode node;
257 EXPECT_EQ(&node, node.value());
258 }
259
260 } // namespace
261 } // namespace base
262