linked_list_unittest.cc 7.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382
  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. #include "base/containers/linked_list.h"
  5. #include "base/test/gtest_util.h"
  6. #include "testing/gtest/include/gtest/gtest.h"
  7. namespace base {
  8. namespace {
  9. class Node : public LinkNode<Node> {
  10. public:
  11. explicit Node(int id) : id_(id) {}
  12. int id() const { return id_; }
  13. private:
  14. int id_;
  15. };
  16. class MultipleInheritanceNodeBase {
  17. public:
  18. MultipleInheritanceNodeBase() : field_taking_up_space_(0) {}
  19. int field_taking_up_space_;
  20. };
  21. class MultipleInheritanceNode : public MultipleInheritanceNodeBase,
  22. public LinkNode<MultipleInheritanceNode> {
  23. public:
  24. MultipleInheritanceNode() = default;
  25. };
  26. class MovableNode : public LinkNode<MovableNode> {
  27. public:
  28. explicit MovableNode(int id) : id_(id) {}
  29. MovableNode(MovableNode&&) = default;
  30. int id() const { return id_; }
  31. private:
  32. int id_;
  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. void ExpectListContents(const LinkedList<Node>& list,
  51. int num_nodes,
  52. const int* node_ids) {
  53. {
  54. SCOPED_TRACE("Iterating forward (from head to tail)");
  55. ExpectListContentsForDirection(list, num_nodes, node_ids, true);
  56. }
  57. {
  58. SCOPED_TRACE("Iterating backward (from tail to head)");
  59. ExpectListContentsForDirection(list, num_nodes, node_ids, false);
  60. }
  61. }
  62. TEST(LinkedList, Empty) {
  63. LinkedList<Node> list;
  64. EXPECT_EQ(list.end(), list.head());
  65. EXPECT_EQ(list.end(), list.tail());
  66. ExpectListContents(list, 0, nullptr);
  67. }
  68. TEST(LinkedList, Append) {
  69. LinkedList<Node> list;
  70. ExpectListContents(list, 0, nullptr);
  71. Node n1(1);
  72. list.Append(&n1);
  73. EXPECT_EQ(&n1, list.head());
  74. EXPECT_EQ(&n1, list.tail());
  75. {
  76. const int expected[] = {1};
  77. ExpectListContents(list, std::size(expected), expected);
  78. }
  79. Node n2(2);
  80. list.Append(&n2);
  81. EXPECT_EQ(&n1, list.head());
  82. EXPECT_EQ(&n2, list.tail());
  83. {
  84. const int expected[] = {1, 2};
  85. ExpectListContents(list, std::size(expected), expected);
  86. }
  87. Node n3(3);
  88. list.Append(&n3);
  89. EXPECT_EQ(&n1, list.head());
  90. EXPECT_EQ(&n3, list.tail());
  91. {
  92. const int expected[] = {1, 2, 3};
  93. ExpectListContents(list, std::size(expected), expected);
  94. }
  95. }
  96. TEST(LinkedList, RemoveFromList) {
  97. LinkedList<Node> list;
  98. Node n1(1);
  99. Node n2(2);
  100. Node n3(3);
  101. Node n4(4);
  102. Node n5(5);
  103. list.Append(&n1);
  104. list.Append(&n2);
  105. list.Append(&n3);
  106. list.Append(&n4);
  107. list.Append(&n5);
  108. EXPECT_EQ(&n1, list.head());
  109. EXPECT_EQ(&n5, list.tail());
  110. {
  111. const int expected[] = {1, 2, 3, 4, 5};
  112. ExpectListContents(list, std::size(expected), expected);
  113. }
  114. // Remove from the middle.
  115. n3.RemoveFromList();
  116. EXPECT_EQ(&n1, list.head());
  117. EXPECT_EQ(&n5, list.tail());
  118. {
  119. const int expected[] = {1, 2, 4, 5};
  120. ExpectListContents(list, std::size(expected), expected);
  121. }
  122. // Remove from the tail.
  123. n5.RemoveFromList();
  124. EXPECT_EQ(&n1, list.head());
  125. EXPECT_EQ(&n4, list.tail());
  126. {
  127. const int expected[] = {1, 2, 4};
  128. ExpectListContents(list, std::size(expected), expected);
  129. }
  130. // Remove from the head.
  131. n1.RemoveFromList();
  132. EXPECT_EQ(&n2, list.head());
  133. EXPECT_EQ(&n4, list.tail());
  134. {
  135. const int expected[] = {2, 4};
  136. ExpectListContents(list, std::size(expected), expected);
  137. }
  138. // Empty the list.
  139. n2.RemoveFromList();
  140. n4.RemoveFromList();
  141. ExpectListContents(list, 0, nullptr);
  142. EXPECT_EQ(list.end(), list.head());
  143. EXPECT_EQ(list.end(), list.tail());
  144. // Fill the list once again.
  145. list.Append(&n1);
  146. list.Append(&n2);
  147. list.Append(&n3);
  148. list.Append(&n4);
  149. list.Append(&n5);
  150. EXPECT_EQ(&n1, list.head());
  151. EXPECT_EQ(&n5, list.tail());
  152. {
  153. const int expected[] = {1, 2, 3, 4, 5};
  154. ExpectListContents(list, std::size(expected), expected);
  155. }
  156. }
  157. TEST(LinkedList, InsertBefore) {
  158. LinkedList<Node> list;
  159. Node n1(1);
  160. Node n2(2);
  161. Node n3(3);
  162. Node n4(4);
  163. list.Append(&n1);
  164. list.Append(&n2);
  165. EXPECT_EQ(&n1, list.head());
  166. EXPECT_EQ(&n2, list.tail());
  167. {
  168. const int expected[] = {1, 2};
  169. ExpectListContents(list, std::size(expected), expected);
  170. }
  171. n3.InsertBefore(&n2);
  172. EXPECT_EQ(&n1, list.head());
  173. EXPECT_EQ(&n2, list.tail());
  174. {
  175. const int expected[] = {1, 3, 2};
  176. ExpectListContents(list, std::size(expected), expected);
  177. }
  178. n4.InsertBefore(&n1);
  179. EXPECT_EQ(&n4, list.head());
  180. EXPECT_EQ(&n2, list.tail());
  181. {
  182. const int expected[] = {4, 1, 3, 2};
  183. ExpectListContents(list, std::size(expected), expected);
  184. }
  185. }
  186. TEST(LinkedList, InsertAfter) {
  187. LinkedList<Node> list;
  188. Node n1(1);
  189. Node n2(2);
  190. Node n3(3);
  191. Node n4(4);
  192. list.Append(&n1);
  193. list.Append(&n2);
  194. EXPECT_EQ(&n1, list.head());
  195. EXPECT_EQ(&n2, list.tail());
  196. {
  197. const int expected[] = {1, 2};
  198. ExpectListContents(list, std::size(expected), expected);
  199. }
  200. n3.InsertAfter(&n2);
  201. EXPECT_EQ(&n1, list.head());
  202. EXPECT_EQ(&n3, list.tail());
  203. {
  204. const int expected[] = {1, 2, 3};
  205. ExpectListContents(list, std::size(expected), expected);
  206. }
  207. n4.InsertAfter(&n1);
  208. EXPECT_EQ(&n1, list.head());
  209. EXPECT_EQ(&n3, list.tail());
  210. {
  211. const int expected[] = {1, 4, 2, 3};
  212. ExpectListContents(list, std::size(expected), expected);
  213. }
  214. }
  215. TEST(LinkedList, MultipleInheritanceNode) {
  216. MultipleInheritanceNode node;
  217. EXPECT_EQ(&node, node.value());
  218. }
  219. TEST(LinkedList, EmptyListIsEmpty) {
  220. LinkedList<Node> list;
  221. EXPECT_TRUE(list.empty());
  222. }
  223. TEST(LinkedList, NonEmptyListIsNotEmpty) {
  224. LinkedList<Node> list;
  225. Node n(1);
  226. list.Append(&n);
  227. EXPECT_FALSE(list.empty());
  228. }
  229. TEST(LinkedList, EmptiedListIsEmptyAgain) {
  230. LinkedList<Node> list;
  231. Node n(1);
  232. list.Append(&n);
  233. n.RemoveFromList();
  234. EXPECT_TRUE(list.empty());
  235. }
  236. TEST(LinkedList, NodesCanBeReused) {
  237. LinkedList<Node> list1;
  238. LinkedList<Node> list2;
  239. Node n(1);
  240. list1.Append(&n);
  241. n.RemoveFromList();
  242. list2.Append(&n);
  243. EXPECT_EQ(list2.head()->value(), &n);
  244. }
  245. TEST(LinkedList, RemovedNodeHasNullNextPrevious) {
  246. LinkedList<Node> list;
  247. Node n(1);
  248. list.Append(&n);
  249. n.RemoveFromList();
  250. EXPECT_EQ(nullptr, n.next());
  251. EXPECT_EQ(nullptr, n.previous());
  252. }
  253. TEST(LinkedList, NodeMoveConstructor) {
  254. LinkedList<MovableNode> list;
  255. MovableNode n1(1);
  256. MovableNode n2(2);
  257. MovableNode n3(3);
  258. list.Append(&n1);
  259. list.Append(&n2);
  260. list.Append(&n3);
  261. EXPECT_EQ(&n1, n2.previous());
  262. EXPECT_EQ(&n2, n1.next());
  263. EXPECT_EQ(&n3, n2.next());
  264. EXPECT_EQ(&n2, n3.previous());
  265. EXPECT_EQ(2, n2.id());
  266. MovableNode n2_new(std::move(n2));
  267. EXPECT_EQ(nullptr, n2.next());
  268. EXPECT_EQ(nullptr, n2.previous());
  269. EXPECT_EQ(&n1, n2_new.previous());
  270. EXPECT_EQ(&n2_new, n1.next());
  271. EXPECT_EQ(&n3, n2_new.next());
  272. EXPECT_EQ(&n2_new, n3.previous());
  273. EXPECT_EQ(2, n2_new.id());
  274. }
  275. TEST(LinkedListDeathTest, ChecksOnInsertBeforeWhenInList) {
  276. LinkedList<Node> list1;
  277. LinkedList<Node> list2;
  278. Node n1(1);
  279. Node n2(2);
  280. Node n3(3);
  281. list1.Append(&n1);
  282. list2.Append(&n2);
  283. list2.Append(&n3);
  284. EXPECT_CHECK_DEATH(n1.InsertBefore(&n3));
  285. }
  286. TEST(LinkedListDeathTest, ChecksOnInsertAfterWhenInList) {
  287. LinkedList<Node> list1;
  288. LinkedList<Node> list2;
  289. Node n1(1);
  290. Node n2(2);
  291. Node n3(3);
  292. list1.Append(&n1);
  293. list2.Append(&n2);
  294. list2.Append(&n3);
  295. EXPECT_CHECK_DEATH(n1.InsertAfter(&n2));
  296. }
  297. } // namespace
  298. } // namespace base