OLD | NEW |
(Empty) | |
| 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/linked_list.h" |
| 6 #include "base/basictypes.h" |
| 7 #include "testing/gtest/include/gtest/gtest.h" |
| 8 |
| 9 namespace base { |
| 10 namespace { |
| 11 |
| 12 class 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 |
| 22 // Checks that when iterating |list| (either from head to tail, or from |
| 23 // tail to head, as determined by |forward|), we get back |node_ids|, |
| 24 // which is an array of size |num_nodes|. |
| 25 void ExpectListContentsForDirection(const LinkedList<Node>& list, |
| 26 int num_nodes, const int* node_ids, bool forward) { |
| 27 int i = 0; |
| 28 for (const LinkNode<Node>* node = (forward ? list.head() : list.tail()); |
| 29 node != list.end(); |
| 30 node = (forward ? node->next() : node->previous())) { |
| 31 ASSERT_LT(i, num_nodes); |
| 32 int index_of_id = forward ? i : num_nodes - i - 1; |
| 33 EXPECT_EQ(node_ids[index_of_id], node->value()->id()); |
| 34 ++i; |
| 35 } |
| 36 EXPECT_EQ(num_nodes, i); |
| 37 } |
| 38 |
| 39 void ExpectListContents(const LinkedList<Node>& list, |
| 40 int num_nodes, |
| 41 const int* node_ids) { |
| 42 { |
| 43 SCOPED_TRACE("Iterating forward (from head to tail)"); |
| 44 ExpectListContentsForDirection(list, num_nodes, node_ids, true); |
| 45 } |
| 46 { |
| 47 SCOPED_TRACE("Iterating backward (from tail to head)"); |
| 48 ExpectListContentsForDirection(list, num_nodes, node_ids, false); |
| 49 } |
| 50 } |
| 51 |
| 52 TEST(LinkedList, Empty) { |
| 53 LinkedList<Node> list; |
| 54 EXPECT_EQ(list.end(), list.head()); |
| 55 EXPECT_EQ(list.end(), list.tail()); |
| 56 ExpectListContents(list, 0, NULL); |
| 57 } |
| 58 |
| 59 |
| 60 TEST(LinkedList, Append) { |
| 61 LinkedList<Node> list; |
| 62 ExpectListContents(list, 0, NULL); |
| 63 |
| 64 Node n1(1); |
| 65 list.Append(&n1); |
| 66 |
| 67 EXPECT_EQ(&n1, list.head()); |
| 68 EXPECT_EQ(&n1, list.tail()); |
| 69 { |
| 70 const int expected[] = {1}; |
| 71 ExpectListContents(list, arraysize(expected), expected); |
| 72 } |
| 73 |
| 74 Node n2(2); |
| 75 list.Append(&n2); |
| 76 |
| 77 EXPECT_EQ(&n1, list.head()); |
| 78 EXPECT_EQ(&n2, list.tail()); |
| 79 { |
| 80 const int expected[] = {1, 2}; |
| 81 ExpectListContents(list, arraysize(expected), expected); |
| 82 } |
| 83 |
| 84 Node n3(3); |
| 85 list.Append(&n3); |
| 86 |
| 87 EXPECT_EQ(&n1, list.head()); |
| 88 EXPECT_EQ(&n3, list.tail()); |
| 89 { |
| 90 const int expected[] = {1, 2, 3}; |
| 91 ExpectListContents(list, arraysize(expected), expected); |
| 92 } |
| 93 } |
| 94 |
| 95 TEST(LinkedList, RemoveFromList) { |
| 96 LinkedList<Node> list; |
| 97 |
| 98 Node n1(1); |
| 99 Node n2(2); |
| 100 Node n3(3); |
| 101 Node n4(4); |
| 102 Node n5(5); |
| 103 |
| 104 list.Append(&n1); |
| 105 list.Append(&n2); |
| 106 list.Append(&n3); |
| 107 list.Append(&n4); |
| 108 list.Append(&n5); |
| 109 |
| 110 EXPECT_EQ(&n1, list.head()); |
| 111 EXPECT_EQ(&n5, list.tail()); |
| 112 { |
| 113 const int expected[] = {1, 2, 3, 4, 5}; |
| 114 ExpectListContents(list, arraysize(expected), expected); |
| 115 } |
| 116 |
| 117 // Remove from the middle. |
| 118 n3.RemoveFromList(); |
| 119 |
| 120 EXPECT_EQ(&n1, list.head()); |
| 121 EXPECT_EQ(&n5, list.tail()); |
| 122 { |
| 123 const int expected[] = {1, 2, 4, 5}; |
| 124 ExpectListContents(list, arraysize(expected), expected); |
| 125 } |
| 126 |
| 127 // Remove from the tail. |
| 128 n5.RemoveFromList(); |
| 129 |
| 130 EXPECT_EQ(&n1, list.head()); |
| 131 EXPECT_EQ(&n4, list.tail()); |
| 132 { |
| 133 const int expected[] = {1, 2, 4}; |
| 134 ExpectListContents(list, arraysize(expected), expected); |
| 135 } |
| 136 |
| 137 // Remove from the head. |
| 138 n1.RemoveFromList(); |
| 139 |
| 140 EXPECT_EQ(&n2, list.head()); |
| 141 EXPECT_EQ(&n4, list.tail()); |
| 142 { |
| 143 const int expected[] = {2, 4}; |
| 144 ExpectListContents(list, arraysize(expected), expected); |
| 145 } |
| 146 |
| 147 // Empty the list. |
| 148 n2.RemoveFromList(); |
| 149 n4.RemoveFromList(); |
| 150 |
| 151 ExpectListContents(list, 0, NULL); |
| 152 EXPECT_EQ(list.end(), list.head()); |
| 153 EXPECT_EQ(list.end(), list.tail()); |
| 154 |
| 155 // Fill the list once again. |
| 156 list.Append(&n1); |
| 157 list.Append(&n2); |
| 158 list.Append(&n3); |
| 159 list.Append(&n4); |
| 160 list.Append(&n5); |
| 161 |
| 162 EXPECT_EQ(&n1, list.head()); |
| 163 EXPECT_EQ(&n5, list.tail()); |
| 164 { |
| 165 const int expected[] = {1, 2, 3, 4, 5}; |
| 166 ExpectListContents(list, arraysize(expected), expected); |
| 167 } |
| 168 } |
| 169 |
| 170 TEST(LinkedList, InsertBefore) { |
| 171 LinkedList<Node> list; |
| 172 |
| 173 Node n1(1); |
| 174 Node n2(2); |
| 175 Node n3(3); |
| 176 Node n4(4); |
| 177 |
| 178 list.Append(&n1); |
| 179 list.Append(&n2); |
| 180 |
| 181 EXPECT_EQ(&n1, list.head()); |
| 182 EXPECT_EQ(&n2, list.tail()); |
| 183 { |
| 184 const int expected[] = {1, 2}; |
| 185 ExpectListContents(list, arraysize(expected), expected); |
| 186 } |
| 187 |
| 188 n3.InsertBefore(&n2); |
| 189 |
| 190 EXPECT_EQ(&n1, list.head()); |
| 191 EXPECT_EQ(&n2, list.tail()); |
| 192 { |
| 193 const int expected[] = {1, 3, 2}; |
| 194 ExpectListContents(list, arraysize(expected), expected); |
| 195 } |
| 196 |
| 197 n4.InsertBefore(&n1); |
| 198 |
| 199 EXPECT_EQ(&n4, list.head()); |
| 200 EXPECT_EQ(&n2, list.tail()); |
| 201 { |
| 202 const int expected[] = {4, 1, 3, 2}; |
| 203 ExpectListContents(list, arraysize(expected), expected); |
| 204 } |
| 205 } |
| 206 |
| 207 TEST(LinkedList, InsertAfter) { |
| 208 LinkedList<Node> list; |
| 209 |
| 210 Node n1(1); |
| 211 Node n2(2); |
| 212 Node n3(3); |
| 213 Node n4(4); |
| 214 |
| 215 list.Append(&n1); |
| 216 list.Append(&n2); |
| 217 |
| 218 EXPECT_EQ(&n1, list.head()); |
| 219 EXPECT_EQ(&n2, list.tail()); |
| 220 { |
| 221 const int expected[] = {1, 2}; |
| 222 ExpectListContents(list, arraysize(expected), expected); |
| 223 } |
| 224 |
| 225 n3.InsertAfter(&n2); |
| 226 |
| 227 EXPECT_EQ(&n1, list.head()); |
| 228 EXPECT_EQ(&n3, list.tail()); |
| 229 { |
| 230 const int expected[] = {1, 2, 3}; |
| 231 ExpectListContents(list, arraysize(expected), expected); |
| 232 } |
| 233 |
| 234 n4.InsertAfter(&n1); |
| 235 |
| 236 EXPECT_EQ(&n1, list.head()); |
| 237 EXPECT_EQ(&n3, list.tail()); |
| 238 { |
| 239 const int expected[] = {1, 4, 2, 3}; |
| 240 ExpectListContents(list, arraysize(expected), expected); |
| 241 } |
| 242 } |
| 243 |
| 244 } // namespace |
| 245 } // namespace base |
OLD | NEW |