| // Copyright (c) 2009 The Chromium Authors. All rights reserved. | |
| // Use of this source code is governed by a BSD-style license that can be | |
| // found in the LICENSE file. | |
| #include "base/containers/linked_list.h" | |
| #include "base/macros.h" | |
| #include "testing/gtest/include/gtest/gtest.h" | |
| namespace base { | |
| namespace { | |
| class Node : public LinkNode<Node> { | |
| public: | |
| explicit Node(int id) : id_(id) {} | |
| int id() const { return id_; } | |
| private: | |
| int id_; | |
| }; | |
| class MultipleInheritanceNodeBase { | |
| public: | |
| MultipleInheritanceNodeBase() : field_taking_up_space_(0) {} | |
| int field_taking_up_space_; | |
| }; | |
| class MultipleInheritanceNode : public MultipleInheritanceNodeBase, | |
| public LinkNode<MultipleInheritanceNode> { | |
| public: | |
| MultipleInheritanceNode() = default; | |
| }; | |
| class MovableNode : public LinkNode<MovableNode> { | |
| public: | |
| explicit MovableNode(int id) : id_(id) {} | |
| MovableNode(MovableNode&&) = default; | |
| int id() const { return id_; } | |
| private: | |
| int id_; | |
| }; | |
| // Checks that when iterating |list| (either from head to tail, or from | |
| // tail to head, as determined by |forward|), we get back |node_ids|, | |
| // which is an array of size |num_nodes|. | |
| void ExpectListContentsForDirection(const LinkedList<Node>& list, | |
| int num_nodes, const int* node_ids, bool forward) { | |
| int i = 0; | |
| for (const LinkNode<Node>* node = (forward ? list.head() : list.tail()); | |
| node != list.end(); | |
| node = (forward ? node->next() : node->previous())) { | |
| ASSERT_LT(i, num_nodes); | |
| int index_of_id = forward ? i : num_nodes - i - 1; | |
| EXPECT_EQ(node_ids[index_of_id], node->value()->id()); | |
| ++i; | |
| } | |
| EXPECT_EQ(num_nodes, i); | |
| } | |
| void ExpectListContents(const LinkedList<Node>& list, | |
| int num_nodes, | |
| const int* node_ids) { | |
| { | |
| SCOPED_TRACE("Iterating forward (from head to tail)"); | |
| ExpectListContentsForDirection(list, num_nodes, node_ids, true); | |
| } | |
| { | |
| SCOPED_TRACE("Iterating backward (from tail to head)"); | |
| ExpectListContentsForDirection(list, num_nodes, node_ids, false); | |
| } | |
| } | |
| TEST(LinkedList, Empty) { | |
| LinkedList<Node> list; | |
| EXPECT_EQ(list.end(), list.head()); | |
| EXPECT_EQ(list.end(), list.tail()); | |
| ExpectListContents(list, 0, nullptr); | |
| } | |
| TEST(LinkedList, Append) { | |
| LinkedList<Node> list; | |
| ExpectListContents(list, 0, nullptr); | |
| Node n1(1); | |
| list.Append(&n1); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n1, list.tail()); | |
| { | |
| const int expected[] = {1}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| Node n2(2); | |
| list.Append(&n2); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n2, list.tail()); | |
| { | |
| const int expected[] = {1, 2}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| Node n3(3); | |
| list.Append(&n3); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n3, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 3}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| } | |
| TEST(LinkedList, RemoveFromList) { | |
| LinkedList<Node> list; | |
| Node n1(1); | |
| Node n2(2); | |
| Node n3(3); | |
| Node n4(4); | |
| Node n5(5); | |
| list.Append(&n1); | |
| list.Append(&n2); | |
| list.Append(&n3); | |
| list.Append(&n4); | |
| list.Append(&n5); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n5, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 3, 4, 5}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| // Remove from the middle. | |
| n3.RemoveFromList(); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n5, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 4, 5}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| // Remove from the tail. | |
| n5.RemoveFromList(); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n4, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 4}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| // Remove from the head. | |
| n1.RemoveFromList(); | |
| EXPECT_EQ(&n2, list.head()); | |
| EXPECT_EQ(&n4, list.tail()); | |
| { | |
| const int expected[] = {2, 4}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| // Empty the list. | |
| n2.RemoveFromList(); | |
| n4.RemoveFromList(); | |
| ExpectListContents(list, 0, nullptr); | |
| EXPECT_EQ(list.end(), list.head()); | |
| EXPECT_EQ(list.end(), list.tail()); | |
| // Fill the list once again. | |
| list.Append(&n1); | |
| list.Append(&n2); | |
| list.Append(&n3); | |
| list.Append(&n4); | |
| list.Append(&n5); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n5, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 3, 4, 5}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| } | |
| TEST(LinkedList, InsertBefore) { | |
| LinkedList<Node> list; | |
| Node n1(1); | |
| Node n2(2); | |
| Node n3(3); | |
| Node n4(4); | |
| list.Append(&n1); | |
| list.Append(&n2); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n2, list.tail()); | |
| { | |
| const int expected[] = {1, 2}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| n3.InsertBefore(&n2); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n2, list.tail()); | |
| { | |
| const int expected[] = {1, 3, 2}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| n4.InsertBefore(&n1); | |
| EXPECT_EQ(&n4, list.head()); | |
| EXPECT_EQ(&n2, list.tail()); | |
| { | |
| const int expected[] = {4, 1, 3, 2}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| } | |
| TEST(LinkedList, InsertAfter) { | |
| LinkedList<Node> list; | |
| Node n1(1); | |
| Node n2(2); | |
| Node n3(3); | |
| Node n4(4); | |
| list.Append(&n1); | |
| list.Append(&n2); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n2, list.tail()); | |
| { | |
| const int expected[] = {1, 2}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| n3.InsertAfter(&n2); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n3, list.tail()); | |
| { | |
| const int expected[] = {1, 2, 3}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| n4.InsertAfter(&n1); | |
| EXPECT_EQ(&n1, list.head()); | |
| EXPECT_EQ(&n3, list.tail()); | |
| { | |
| const int expected[] = {1, 4, 2, 3}; | |
| ExpectListContents(list, arraysize(expected), expected); | |
| } | |
| } | |
| TEST(LinkedList, MultipleInheritanceNode) { | |
| MultipleInheritanceNode node; | |
| EXPECT_EQ(&node, node.value()); | |
| } | |
| TEST(LinkedList, EmptyListIsEmpty) { | |
| LinkedList<Node> list; | |
| EXPECT_TRUE(list.empty()); | |
| } | |
| TEST(LinkedList, NonEmptyListIsNotEmpty) { | |
| LinkedList<Node> list; | |
| Node n(1); | |
| list.Append(&n); | |
| EXPECT_FALSE(list.empty()); | |
| } | |
| TEST(LinkedList, EmptiedListIsEmptyAgain) { | |
| LinkedList<Node> list; | |
| Node n(1); | |
| list.Append(&n); | |
| n.RemoveFromList(); | |
| EXPECT_TRUE(list.empty()); | |
| } | |
| TEST(LinkedList, NodesCanBeReused) { | |
| LinkedList<Node> list1; | |
| LinkedList<Node> list2; | |
| Node n(1); | |
| list1.Append(&n); | |
| n.RemoveFromList(); | |
| list2.Append(&n); | |
| EXPECT_EQ(list2.head()->value(), &n); | |
| } | |
| TEST(LinkedList, RemovedNodeHasNullNextPrevious) { | |
| LinkedList<Node> list; | |
| Node n(1); | |
| list.Append(&n); | |
| n.RemoveFromList(); | |
| EXPECT_EQ(nullptr, n.next()); | |
| EXPECT_EQ(nullptr, n.previous()); | |
| } | |
| TEST(LinkedList, NodeMoveConstructor) { | |
| LinkedList<MovableNode> list; | |
| MovableNode n1(1); | |
| MovableNode n2(2); | |
| MovableNode n3(3); | |
| list.Append(&n1); | |
| list.Append(&n2); | |
| list.Append(&n3); | |
| EXPECT_EQ(&n1, n2.previous()); | |
| EXPECT_EQ(&n2, n1.next()); | |
| EXPECT_EQ(&n3, n2.next()); | |
| EXPECT_EQ(&n2, n3.previous()); | |
| EXPECT_EQ(2, n2.id()); | |
| MovableNode n2_new(std::move(n2)); | |
| EXPECT_EQ(nullptr, n2.next()); | |
| EXPECT_EQ(nullptr, n2.previous()); | |
| EXPECT_EQ(&n1, n2_new.previous()); | |
| EXPECT_EQ(&n2_new, n1.next()); | |
| EXPECT_EQ(&n3, n2_new.next()); | |
| EXPECT_EQ(&n2_new, n3.previous()); | |
| EXPECT_EQ(2, n2_new.id()); | |
| } | |
| } // namespace | |
| } // namespace base |