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