15821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Copyright (c) 2009 The Chromium Authors. All rights reserved. 25821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Use of this source code is governed by a BSD-style license that can be 35821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// found in the LICENSE file. 45821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 55821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/basictypes.h" 65821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "base/containers/linked_list.h" 75821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)#include "testing/gtest/include/gtest/gtest.h" 85821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 95821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace base { 105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)namespace { 115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class Node : public LinkNode<Node> { 135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) explicit Node(int id) : id_(id) {} 155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int id() const { return id_; } 175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) private: 195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int id_; 205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MultipleInheritanceNodeBase { 235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MultipleInheritanceNodeBase() : field_taking_up_space_(0) {} 255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int field_taking_up_space_; 265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)class MultipleInheritanceNode : public MultipleInheritanceNodeBase, 295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public LinkNode<MultipleInheritanceNode> { 305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) public: 315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MultipleInheritanceNode() {} 325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)}; 335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// Checks that when iterating |list| (either from head to tail, or from 355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// tail to head, as determined by |forward|), we get back |node_ids|, 365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)// which is an array of size |num_nodes|. 375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ExpectListContentsForDirection(const LinkedList<Node>& list, 385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_nodes, const int* node_ids, bool forward) { 395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int i = 0; 405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) for (const LinkNode<Node>* node = (forward ? list.head() : list.tail()); 415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node != list.end(); 425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) node = (forward ? node->next() : node->previous())) { 435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ASSERT_LT(i, num_nodes); 445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int index_of_id = forward ? i : num_nodes - i - 1; 455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(node_ids[index_of_id], node->value()->id()); 465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ++i; 475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(num_nodes, i); 495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)void ExpectListContents(const LinkedList<Node>& list, 525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) int num_nodes, 535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int* node_ids) { 545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCOPED_TRACE("Iterating forward (from head to tail)"); 565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContentsForDirection(list, num_nodes, node_ids, true); 575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) SCOPED_TRACE("Iterating backward (from tail to head)"); 605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContentsForDirection(list, num_nodes, node_ids, false); 615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, Empty) { 655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList<Node> list; 665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(list.end(), list.head()); 675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(list.end(), list.tail()); 685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, 0, NULL); 695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, Append) { 725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList<Node> list; 735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, 0, NULL); 745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n1(1); 765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n1); 775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.tail()); 805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1}; 825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n2(2); 865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n2); 875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.tail()); 905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2}; 925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n3(3); 965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n3); 975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n3, list.tail()); 1005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 3}; 1025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, RemoveFromList) { 1075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList<Node> list; 1085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n1(1); 1105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n2(2); 1115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n3(3); 1125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n4(4); 1135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n5(5); 1145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n1); 1165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n2); 1175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n3); 1185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n4); 1195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n5); 1205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 1225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n5, list.tail()); 1235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 3, 4, 5}; 1255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove from the middle. 1295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n3.RemoveFromList(); 1305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 1325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n5, list.tail()); 1335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 4, 5}; 1355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove from the tail. 1395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n5.RemoveFromList(); 1405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 1425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n4, list.tail()); 1435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 4}; 1455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Remove from the head. 1495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n1.RemoveFromList(); 1505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.head()); 1525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n4, list.tail()); 1535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {2, 4}; 1555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Empty the list. 1595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n2.RemoveFromList(); 1605821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n4.RemoveFromList(); 1615821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1625821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, 0, NULL); 1635821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(list.end(), list.head()); 1645821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(list.end(), list.tail()); 1655821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1665821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) // Fill the list once again. 1675821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n1); 1685821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n2); 1695821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n3); 1705821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n4); 1715821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n5); 1725821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1735821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 1745821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n5, list.tail()); 1755821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1765821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 3, 4, 5}; 1775821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1785821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1795821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 1805821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1815821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, InsertBefore) { 1825821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList<Node> list; 1835821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1845821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n1(1); 1855821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n2(2); 1865821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n3(3); 1875821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n4(4); 1885821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1895821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n1); 1905821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n2); 1915821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1925821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 1935821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.tail()); 1945821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 1955821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2}; 1965821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 1975821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 1985821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 1995821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n3.InsertBefore(&n2); 2005821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2015821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 2025821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.tail()); 2035821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2045821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 3, 2}; 2055821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 2065821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n4.InsertBefore(&n1); 2095821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2105821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n4, list.head()); 2115821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.tail()); 2125821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2135821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {4, 1, 3, 2}; 2145821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 2155821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2165821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2175821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2185821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, InsertAfter) { 2195821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) LinkedList<Node> list; 2205821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2215821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n1(1); 2225821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n2(2); 2235821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n3(3); 2245821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) Node n4(4); 2255821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2265821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n1); 2275821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) list.Append(&n2); 2285821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2295821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 2305821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n2, list.tail()); 2315821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2325821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2}; 2335821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 2345821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2355821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2365821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n3.InsertAfter(&n2); 2375821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2385821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 2395821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n3, list.tail()); 2405821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2415821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 2, 3}; 2425821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 2435821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2445821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2455821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) n4.InsertAfter(&n1); 2465821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2475821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n1, list.head()); 2485821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&n3, list.tail()); 2495821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) { 2505821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) const int expected[] = {1, 4, 2, 3}; 2515821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) ExpectListContents(list, arraysize(expected), expected); 2525821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) } 2535821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2545821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 2555821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)TEST(LinkedList, MultipleInheritanceNode) { 2565821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) MultipleInheritanceNode node; 2575821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) EXPECT_EQ(&node, node.value()); 2585821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} 2595821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles) 260116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTEST(LinkedList, EmptyListIsEmpty) { 261116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list; 262116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_TRUE(list.empty()); 263116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 264116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 265116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTEST(LinkedList, NonEmptyListIsNotEmpty) { 266116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list; 267116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 268116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node n(1); 269116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch list.Append(&n); 270116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 271116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_FALSE(list.empty()); 272116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 273116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 274116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTEST(LinkedList, EmptiedListIsEmptyAgain) { 275116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list; 276116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 277116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node n(1); 278116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch list.Append(&n); 279116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch n.RemoveFromList(); 280116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 281116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_TRUE(list.empty()); 282116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 283116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 284116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTEST(LinkedList, NodesCanBeReused) { 285116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list1; 286116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list2; 287116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 288116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node n(1); 289116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch list1.Append(&n); 290116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch n.RemoveFromList(); 291116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch list2.Append(&n); 292116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 293116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_EQ(list2.head()->value(), &n); 294116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 295116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 296116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTEST(LinkedList, RemovedNodeHasNullNextPrevious) { 297116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch LinkedList<Node> list; 298116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 299116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch Node n(1); 300116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch list.Append(&n); 301116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch n.RemoveFromList(); 302116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 303116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_EQ(NULL, n.next()); 304116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch EXPECT_EQ(NULL, n.previous()); 305116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} 306116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 3075821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace 3085821806d5e7f356e8fa4b058a389a808ea183019Torne (Richard Coles)} // namespace base 309