1 | //===- unittests/ADT/IListBaseTest.cpp - ilist_base unit tests ------------===// |
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 | #include "llvm/ADT/ilist_base.h" |
10 | #include "gtest/gtest.h" |
11 | |
12 | using namespace llvm; |
13 | |
14 | namespace { |
15 | |
16 | // Test fixture. |
17 | template <typename T> class IListBaseTest : public ::testing::Test {}; |
18 | |
19 | // Test variants with the same test. |
20 | typedef ::testing::Types<ilist_base<false>, ilist_base<true>> |
21 | IListBaseTestTypes; |
22 | TYPED_TEST_SUITE(IListBaseTest, IListBaseTestTypes, ); |
23 | |
24 | TYPED_TEST(IListBaseTest, insertBeforeImpl) { |
25 | typedef TypeParam list_base_type; |
26 | typedef typename list_base_type::node_base_type node_base_type; |
27 | |
28 | node_base_type S, A, B; |
29 | |
30 | // [S] <-> [S] |
31 | S.setPrev(&S); |
32 | S.setNext(&S); |
33 | |
34 | // [S] <-> A <-> [S] |
35 | list_base_type::insertBeforeImpl(S, A); |
36 | EXPECT_EQ(&A, S.getPrev()); |
37 | EXPECT_EQ(&S, A.getPrev()); |
38 | EXPECT_EQ(&A, S.getNext()); |
39 | EXPECT_EQ(&S, A.getNext()); |
40 | |
41 | // [S] <-> A <-> B <-> [S] |
42 | list_base_type::insertBeforeImpl(S, B); |
43 | EXPECT_EQ(&B, S.getPrev()); |
44 | EXPECT_EQ(&A, B.getPrev()); |
45 | EXPECT_EQ(&S, A.getPrev()); |
46 | EXPECT_EQ(&A, S.getNext()); |
47 | EXPECT_EQ(&B, A.getNext()); |
48 | EXPECT_EQ(&S, B.getNext()); |
49 | } |
50 | |
51 | TYPED_TEST(IListBaseTest, removeImpl) { |
52 | typedef TypeParam list_base_type; |
53 | typedef typename list_base_type::node_base_type node_base_type; |
54 | |
55 | node_base_type S, A, B; |
56 | |
57 | // [S] <-> A <-> B <-> [S] |
58 | S.setPrev(&S); |
59 | S.setNext(&S); |
60 | list_base_type::insertBeforeImpl(S, A); |
61 | list_base_type::insertBeforeImpl(S, B); |
62 | |
63 | // [S] <-> B <-> [S] |
64 | list_base_type::removeImpl(A); |
65 | EXPECT_EQ(&B, S.getPrev()); |
66 | EXPECT_EQ(&S, B.getPrev()); |
67 | EXPECT_EQ(&B, S.getNext()); |
68 | EXPECT_EQ(&S, B.getNext()); |
69 | EXPECT_EQ(nullptr, A.getPrev()); |
70 | EXPECT_EQ(nullptr, A.getNext()); |
71 | |
72 | // [S] <-> [S] |
73 | list_base_type::removeImpl(B); |
74 | EXPECT_EQ(&S, S.getPrev()); |
75 | EXPECT_EQ(&S, S.getNext()); |
76 | EXPECT_EQ(nullptr, B.getPrev()); |
77 | EXPECT_EQ(nullptr, B.getNext()); |
78 | } |
79 | |
80 | TYPED_TEST(IListBaseTest, removeRangeImpl) { |
81 | typedef TypeParam list_base_type; |
82 | typedef typename list_base_type::node_base_type node_base_type; |
83 | |
84 | node_base_type S, A, B, C, D; |
85 | |
86 | // [S] <-> A <-> B <-> C <-> D <-> [S] |
87 | S.setPrev(&S); |
88 | S.setNext(&S); |
89 | list_base_type::insertBeforeImpl(S, A); |
90 | list_base_type::insertBeforeImpl(S, B); |
91 | list_base_type::insertBeforeImpl(S, C); |
92 | list_base_type::insertBeforeImpl(S, D); |
93 | |
94 | // [S] <-> A <-> D <-> [S] |
95 | list_base_type::removeRangeImpl(B, D); |
96 | EXPECT_EQ(&D, S.getPrev()); |
97 | EXPECT_EQ(&A, D.getPrev()); |
98 | EXPECT_EQ(&S, A.getPrev()); |
99 | EXPECT_EQ(&A, S.getNext()); |
100 | EXPECT_EQ(&D, A.getNext()); |
101 | EXPECT_EQ(&S, D.getNext()); |
102 | EXPECT_EQ(nullptr, B.getPrev()); |
103 | EXPECT_EQ(nullptr, C.getNext()); |
104 | } |
105 | |
106 | TYPED_TEST(IListBaseTest, removeRangeImplAllButSentinel) { |
107 | typedef TypeParam list_base_type; |
108 | typedef typename list_base_type::node_base_type node_base_type; |
109 | |
110 | node_base_type S, A, B; |
111 | |
112 | // [S] <-> A <-> B <-> [S] |
113 | S.setPrev(&S); |
114 | S.setNext(&S); |
115 | list_base_type::insertBeforeImpl(S, A); |
116 | list_base_type::insertBeforeImpl(S, B); |
117 | |
118 | // [S] <-> [S] |
119 | list_base_type::removeRangeImpl(A, S); |
120 | EXPECT_EQ(&S, S.getPrev()); |
121 | EXPECT_EQ(&S, S.getNext()); |
122 | EXPECT_EQ(nullptr, A.getPrev()); |
123 | EXPECT_EQ(nullptr, B.getNext()); |
124 | } |
125 | |
126 | TYPED_TEST(IListBaseTest, transferBeforeImpl) { |
127 | typedef TypeParam list_base_type; |
128 | typedef typename list_base_type::node_base_type node_base_type; |
129 | |
130 | node_base_type S1, S2, A, B, C, D, E; |
131 | |
132 | // [S1] <-> A <-> B <-> C <-> [S1] |
133 | S1.setPrev(&S1); |
134 | S1.setNext(&S1); |
135 | list_base_type::insertBeforeImpl(S1, A); |
136 | list_base_type::insertBeforeImpl(S1, B); |
137 | list_base_type::insertBeforeImpl(S1, C); |
138 | |
139 | // [S2] <-> D <-> E <-> [S2] |
140 | S2.setPrev(&S2); |
141 | S2.setNext(&S2); |
142 | list_base_type::insertBeforeImpl(S2, D); |
143 | list_base_type::insertBeforeImpl(S2, E); |
144 | |
145 | // [S1] <-> C <-> [S1] |
146 | list_base_type::transferBeforeImpl(D, A, C); |
147 | EXPECT_EQ(&C, S1.getPrev()); |
148 | EXPECT_EQ(&S1, C.getPrev()); |
149 | EXPECT_EQ(&C, S1.getNext()); |
150 | EXPECT_EQ(&S1, C.getNext()); |
151 | |
152 | // [S2] <-> A <-> B <-> D <-> E <-> [S2] |
153 | EXPECT_EQ(&E, S2.getPrev()); |
154 | EXPECT_EQ(&D, E.getPrev()); |
155 | EXPECT_EQ(&B, D.getPrev()); |
156 | EXPECT_EQ(&A, B.getPrev()); |
157 | EXPECT_EQ(&S2, A.getPrev()); |
158 | EXPECT_EQ(&A, S2.getNext()); |
159 | EXPECT_EQ(&B, A.getNext()); |
160 | EXPECT_EQ(&D, B.getNext()); |
161 | EXPECT_EQ(&E, D.getNext()); |
162 | EXPECT_EQ(&S2, E.getNext()); |
163 | } |
164 | |
165 | } // end namespace |
166 | |