1 //===-- tsan_ilist_test.cpp -----------------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file is a part of ThreadSanitizer (TSan), a race detector.
10 //
11 //===----------------------------------------------------------------------===//
12 #include "tsan_ilist.h"
13 
14 #include "gtest/gtest.h"
15 
16 namespace __tsan {
17 
18 struct Node {
19   INode node1;
20   INode node2;
21 };
22 
23 struct Parent : Node {};
24 
25 TEST(IList, Empty) {
26   IList<Node, &Node::node1> list;
27   Node node;
28 
29   EXPECT_TRUE(list.Empty());
30   EXPECT_EQ(list.Size(), (size_t)0);
31   EXPECT_EQ(list.Back(), nullptr);
32   EXPECT_EQ(list.Front(), nullptr);
33   EXPECT_EQ(list.PopBack(), nullptr);
34   EXPECT_EQ(list.PopFront(), nullptr);
35   EXPECT_FALSE(list.Queued(&node));
36 }
37 
38 TEST(IList, OneNode) {
39   IList<Node, &Node::node1> list;
40   Node node;
41 
42   list.PushBack(&node);
43   EXPECT_FALSE(list.Empty());
44   EXPECT_EQ(list.Size(), (size_t)1);
45   EXPECT_EQ(list.Back(), &node);
46   EXPECT_EQ(list.Front(), &node);
47   EXPECT_TRUE(list.Queued(&node));
48   EXPECT_EQ(list.Prev(&node), nullptr);
49   EXPECT_EQ(list.Next(&node), nullptr);
50 
51   EXPECT_EQ(list.PopFront(), &node);
52   EXPECT_TRUE(list.Empty());
53   EXPECT_EQ(list.Size(), (size_t)0);
54   EXPECT_FALSE(list.Queued(&node));
55 }
56 
57 TEST(IList, MultipleNodes) {
58   IList<Node, &Node::node1> list;
59   Node nodes[3];
60 
61   list.PushBack(&nodes[1]);
62   list.PushBack(&nodes[0]);
63   list.PushFront(&nodes[2]);
64 
65   EXPECT_EQ(list.Size(), (size_t)3);
66   EXPECT_EQ(list.Back(), &nodes[0]);
67   EXPECT_EQ(list.Front(), &nodes[2]);
68 
69   EXPECT_EQ(list.Next(&nodes[0]), nullptr);
70   EXPECT_EQ(list.Prev(&nodes[0]), &nodes[1]);
71 
72   EXPECT_EQ(list.Next(&nodes[1]), &nodes[0]);
73   EXPECT_EQ(list.Prev(&nodes[1]), &nodes[2]);
74 
75   EXPECT_EQ(list.Next(&nodes[2]), &nodes[1]);
76   EXPECT_EQ(list.Prev(&nodes[2]), nullptr);
77 
78   EXPECT_EQ(list.PopBack(), &nodes[0]);
79   EXPECT_EQ(list.PopFront(), &nodes[2]);
80   EXPECT_EQ(list.PopFront(), &nodes[1]);
81   EXPECT_TRUE(list.Empty());
82 }
83 
84 TEST(IList, TwoLists) {
85   IList<Node, &Node::node1> list1;
86   IList<Node, &Node::node2, Parent> list2;
87   Parent nodes[3];
88 
89   list1.PushBack(&nodes[2]);
90   list1.PushBack(&nodes[1]);
91   list1.PushBack(&nodes[0]);
92 
93   list2.PushFront(&nodes[1]);
94 
95   EXPECT_EQ(list1.Size(), (size_t)3);
96   EXPECT_TRUE(list1.Queued(&nodes[0]));
97   EXPECT_TRUE(list1.Queued(&nodes[1]));
98   EXPECT_TRUE(list1.Queued(&nodes[2]));
99 
100   EXPECT_EQ(list2.Size(), (size_t)1);
101   EXPECT_FALSE(list2.Queued(&nodes[0]));
102   EXPECT_TRUE(list2.Queued(&nodes[1]));
103   EXPECT_FALSE(list2.Queued(&nodes[2]));
104 
105   EXPECT_EQ(list1.Next(&nodes[1]), &nodes[0]);
106   EXPECT_EQ(list1.Prev(&nodes[1]), &nodes[2]);
107 
108   EXPECT_EQ(list2.Next(&nodes[1]), nullptr);
109   EXPECT_EQ(list2.Prev(&nodes[1]), nullptr);
110 
111   list1.Remove(&nodes[1]);
112   EXPECT_EQ(list1.Size(), (size_t)2);
113   EXPECT_FALSE(list1.Queued(&nodes[1]));
114   EXPECT_EQ(list2.Size(), (size_t)1);
115   EXPECT_TRUE(list2.Queued(&nodes[1]));
116 
117   EXPECT_EQ(list1.PopBack(), &nodes[0]);
118   EXPECT_EQ(list1.PopBack(), &nodes[2]);
119   EXPECT_EQ(list1.Size(), (size_t)0);
120 
121   EXPECT_EQ(list2.PopBack(), &nodes[1]);
122   EXPECT_EQ(list2.Size(), (size_t)0);
123 }
124 
125 }  // namespace __tsan
126