base/containers/linked_list_unittest.cc

   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/basictypes.h"
   6 #include "base/containers/linked_list.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 TEST(LinkedList, EmptyListIsEmpty) {
 261   LinkedList<Node> list;
 262   EXPECT_TRUE(list.empty());
 263 }
 264
 265 TEST(LinkedList, NonEmptyListIsNotEmpty) {
 266   LinkedList<Node> list;
 267
 268   Node n(1);
 269   list.Append(&n);
 270
 271   EXPECT_FALSE(list.empty());
 272 }
 273
 274 TEST(LinkedList, EmptiedListIsEmptyAgain) {
 275   LinkedList<Node> list;
 276
 277   Node n(1);
 278   list.Append(&n);
 279   n.RemoveFromList();
 280
 281   EXPECT_TRUE(list.empty());
 282 }
 283
 284 TEST(LinkedList, NodesCanBeReused) {
 285   LinkedList<Node> list1;
 286   LinkedList<Node> list2;
 287
 288   Node n(1);
 289   list1.Append(&n);
 290   n.RemoveFromList();
 291   list2.Append(&n);
 292
 293   EXPECT_EQ(list2.head()->value(), &n);
 294 }
 295
 296 TEST(LinkedList, RemovedNodeHasNullNextPrevious) {
 297   LinkedList<Node> list;
 298
 299   Node n(1);
 300   list.Append(&n);
 301   n.RemoveFromList();
 302
 303   EXPECT_EQ(NULL, n.next());
 304   EXPECT_EQ(NULL, n.previous());
 305 }
 306
 307 }  // namespace
 308 }  // namespace base