123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382 |
- // 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/test/gtest_util.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, std::size(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, std::size(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, std::size(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, std::size(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, std::size(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, std::size(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, std::size(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, std::size(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, std::size(expected), expected);
- }
- n3.InsertBefore(&n2);
- EXPECT_EQ(&n1, list.head());
- EXPECT_EQ(&n2, list.tail());
- {
- const int expected[] = {1, 3, 2};
- ExpectListContents(list, std::size(expected), expected);
- }
- n4.InsertBefore(&n1);
- EXPECT_EQ(&n4, list.head());
- EXPECT_EQ(&n2, list.tail());
- {
- const int expected[] = {4, 1, 3, 2};
- ExpectListContents(list, std::size(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, std::size(expected), expected);
- }
- n3.InsertAfter(&n2);
- EXPECT_EQ(&n1, list.head());
- EXPECT_EQ(&n3, list.tail());
- {
- const int expected[] = {1, 2, 3};
- ExpectListContents(list, std::size(expected), expected);
- }
- n4.InsertAfter(&n1);
- EXPECT_EQ(&n1, list.head());
- EXPECT_EQ(&n3, list.tail());
- {
- const int expected[] = {1, 4, 2, 3};
- ExpectListContents(list, std::size(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());
- }
- TEST(LinkedListDeathTest, ChecksOnInsertBeforeWhenInList) {
- LinkedList<Node> list1;
- LinkedList<Node> list2;
- Node n1(1);
- Node n2(2);
- Node n3(3);
- list1.Append(&n1);
- list2.Append(&n2);
- list2.Append(&n3);
- EXPECT_CHECK_DEATH(n1.InsertBefore(&n3));
- }
- TEST(LinkedListDeathTest, ChecksOnInsertAfterWhenInList) {
- LinkedList<Node> list1;
- LinkedList<Node> list2;
- Node n1(1);
- Node n2(2);
- Node n3(3);
- list1.Append(&n1);
- list2.Append(&n2);
- list2.Append(&n3);
- EXPECT_CHECK_DEATH(n1.InsertAfter(&n2));
- }
- } // namespace
- } // namespace base
|