diff options
author | Daniel Erat <derat@google.com> | 2015-07-06 13:18:13 -0600 |
---|---|---|
committer | Daniel Erat <derat@google.com> | 2015-07-07 08:49:02 -0600 |
commit | b8cf94937c52feb53b55c39e3f82094d27de464c (patch) | |
tree | 20cd8f9867dfe9c0c2510899346c744605425b75 /base/containers/linked_list_unittest.cc | |
parent | 5bb0a2e04cf1346d5a2819f277381c0415549600 (diff) | |
download | libchrome-b8cf94937c52feb53b55c39e3f82094d27de464c.tar.gz |
Add upstream code as of Chromium r334380.
Copy the unchanged source from
https://chromium.googlesource.com/chromium/src/base/ as of
r334380 (really r334285 a.k.a. 23911a0c in the base/
subtree).
Also add MODULE_LICENSE_BSD and copy Chromium's current
LICENSE file to NOTICE.
Bug: 22317122
Change-Id: I89863bfeca67b3a1ff05e6078f2f9ee4e31c5c99
Diffstat (limited to 'base/containers/linked_list_unittest.cc')
-rw-r--r-- | base/containers/linked_list_unittest.cc | 308 |
1 files changed, 308 insertions, 0 deletions
diff --git a/base/containers/linked_list_unittest.cc b/base/containers/linked_list_unittest.cc new file mode 100644 index 0000000000..93a9f38508 --- /dev/null +++ b/base/containers/linked_list_unittest.cc @@ -0,0 +1,308 @@ +// 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/basictypes.h" +#include "base/containers/linked_list.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() {} +}; + +// 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, NULL); +} + +TEST(LinkedList, Append) { + LinkedList<Node> list; + ExpectListContents(list, 0, NULL); + + 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, NULL); + 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(NULL, n.next()); + EXPECT_EQ(NULL, n.previous()); +} + +} // namespace +} // namespace base |