1 /*
2 * Copyright (c) 2021 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "gtest/gtest.h"
17 #include "utils/list.h"
18 #include <list>
19
20 using namespace panda;
21
22 using std::cerr;
23 using std::endl;
24
25 struct TestNode : public ListNode {
26 TestNode() = default;
TestNodeTestNode27 explicit TestNode(int v) : value(v) {}
28 int value {0};
29 };
30
operator ==(const TestNode & lhs,const TestNode & rhs)31 bool operator==(const TestNode &lhs, const TestNode &rhs)
32 {
33 return lhs.value == rhs.value;
34 }
35
36 class ListTest : public ::testing::Test {
37 public:
ListTest()38 ListTest()
39 {
40 nodes_.reserve(1000U);
41 }
42
43 virtual ~ListTest() = default;
44
45 template <typename... Args>
NewNode(Args &&...args)46 TestNode *NewNode(Args &&... args)
47 {
48 // Vector allocation is unacceptable
49 ASSERT(nodes_.size() < nodes_.capacity());
50
51 nodes_.emplace_back(std::forward<Args>(args)...);
52 return &nodes_.back();
53 }
54
IsEqual(const List<TestNode> & list1,std::initializer_list<TestNode> list2) const55 bool IsEqual(const List<TestNode> &list1, std::initializer_list<TestNode> list2) const
56 {
57 if (GetListSize(list1) != list2.size()) {
58 return false;
59 }
60 return std::equal(list1.begin(), list1.end(), list2.begin());
61 }
62
GetListSize(const List<TestNode> & list) const63 size_t GetListSize(const List<TestNode> &list) const
64 {
65 size_t size = 0;
66 for (auto it : list) {
67 size++;
68 }
69 return size;
70 }
71
72 private:
73 std::vector<TestNode> nodes_;
74 };
75
TEST_F(ListTest,Common)76 TEST_F(ListTest, Common)
77 {
78 ListIterator<TestNode> it;
79 List<TestNode> list;
80 List<TestNode> list2;
81
82 ASSERT_TRUE(list.Empty());
83
84 TestNode *node = NewNode(1);
85 list.PushFront(*node);
86
87 ASSERT_FALSE(list.Empty());
88 ASSERT_EQ(node, &list.Front());
89 ASSERT_EQ(node, &*list.begin());
90 ASSERT_EQ(++list.begin(), list.end());
91
92 ASSERT_TRUE(IsEqual(list, {TestNode(1)}));
93
94 list.PushFront(*NewNode(2));
95
96 ASSERT_TRUE(IsEqual(list, {TestNode(2), TestNode(1)}));
97
98 list.PopFront();
99 ASSERT_TRUE(IsEqual(list, {TestNode(1)}));
100
101 list.InsertAfter(list.begin(), *NewNode(2));
102 ASSERT_TRUE(IsEqual(list, {TestNode(1), TestNode(2)}));
103
104 list.PushFront(*NewNode(0));
105 ASSERT_TRUE(IsEqual(list, {TestNode(0), TestNode(1), TestNode(2)}));
106
107 list.EraseAfter(list.begin() + 1);
108 ASSERT_TRUE(IsEqual(list, {TestNode(0), TestNode(1)}));
109
110 it = list.begin() + 1;
111 for (int i = 0; i < 8; i++) {
112 it = list.InsertAfter(it, *NewNode(i + 2));
113 }
114 ASSERT_TRUE(IsEqual(list, {TestNode(0), TestNode(1), TestNode(2), TestNode(3), TestNode(4), TestNode(5),
115 TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
116
117 list2.Splice(list2.before_begin(), list);
118 ASSERT_TRUE(list.Empty());
119 ASSERT_TRUE(IsEqual(list2, {TestNode(0), TestNode(1), TestNode(2), TestNode(3), TestNode(4), TestNode(5),
120 TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
121
122 list.Splice(list.before_begin(), list2, list2.before_begin() + 5, list2.end());
123 ASSERT_TRUE(IsEqual(list, {TestNode(5), TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
124 ASSERT_TRUE(IsEqual(list2, {TestNode(0), TestNode(1), TestNode(2), TestNode(3), TestNode(4)}));
125
126 list.Splice(list.before_begin(), list2);
127 ASSERT_TRUE(list2.Empty());
128 ASSERT_TRUE(IsEqual(list, {TestNode(0), TestNode(1), TestNode(2), TestNode(3), TestNode(4), TestNode(5),
129 TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
130
131 list2.Splice(list2.before_begin(), list, list.begin() + 1, list.begin() + 5);
132 ASSERT_TRUE(
133 IsEqual(list, {TestNode(0), TestNode(1), TestNode(5), TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
134 ASSERT_TRUE(IsEqual(list2, {TestNode(2), TestNode(3), TestNode(4)}));
135
136 list2.Splice(list2.begin(), list, list.before_begin());
137 ASSERT_TRUE(IsEqual(list, {TestNode(1), TestNode(5), TestNode(6), TestNode(7), TestNode(8), TestNode(9)}));
138 ASSERT_TRUE(IsEqual(list2, {TestNode(2), TestNode(0), TestNode(3), TestNode(4)}));
139
140 list.Remove(TestNode(9));
141 ASSERT_TRUE(IsEqual(list, {TestNode(1), TestNode(5), TestNode(6), TestNode(7), TestNode(8)}));
142
143 list.EraseAfter(list.begin() + 1, list.begin() + 4);
144 ASSERT_TRUE(IsEqual(list, {TestNode(1), TestNode(5), TestNode(8)}));
145 }
146
147 struct DTestNode : public DListNode {
148 DTestNode() = default;
DTestNodeDTestNode149 explicit DTestNode(int v) : value(v) {}
150 int value {0};
151 };
152
153 class DListTest : public ::testing::Test {
154 public:
DListTest()155 DListTest()
156 {
157 nodes_.reserve(1000U);
158 }
159
160 virtual ~DListTest() = default;
161
162 template <typename... Args>
NewNode(Args &&...args)163 DTestNode *NewNode(Args &&... args)
164 {
165 // Vector allocation is unacceptable
166 ASSERT(nodes_.size() < nodes_.capacity());
167
168 nodes_.emplace_back(std::forward<Args>(args)...);
169 return &nodes_.back();
170 }
171
IsEqual(const DList & list1,std::list<DTestNode> list2) const172 bool IsEqual(const DList &list1, std::list<DTestNode> list2) const
173 {
174 if (list1.size() != list2.size()) {
175 return false;
176 }
177
178 auto it1 = list1.begin();
179 auto it2 = list2.begin();
180 for (; it1 != list1.end(); it1++, it2++) {
181 auto *node = reinterpret_cast<const DTestNode *>(&(*it1));
182 if (node->value != (*it2).value) {
183 return false;
184 }
185 }
186 it1 = list1.begin();
187 it2 = list2.begin();
188 for (; it2 != list2.end(); ++it1, ++it2) {
189 auto *node = reinterpret_cast<const DTestNode *>(&(*it1));
190 if (node->value != (*it2).value) {
191 return false;
192 }
193 }
194
195 auto it3 = list1.rbegin();
196 auto it4 = list2.rbegin();
197 for (; it3 != list1.rend(); it3++, it4++) {
198 auto *node = reinterpret_cast<const DTestNode *>(&(*it3));
199 if (node->value != (*it4).value) {
200 return false;
201 }
202 }
203 it3 = list1.rbegin();
204 it4 = list2.rbegin();
205 for (; it4 != list2.rend(); ++it3, ++it4) {
206 auto *node = reinterpret_cast<const DTestNode *>(&(*it3));
207 if (node->value != (*it4).value) {
208 return false;
209 }
210 }
211 return true;
212 }
213
214 private:
215 std::vector<DTestNode> nodes_;
216 };
217
TEST_F(DListTest,Common)218 TEST_F(DListTest, Common)
219 {
220 DList list1;
221 std::list<DTestNode> list2;
222 for (uint32_t i = 0; i < 20; i++) {
223 auto *node = NewNode(i);
224 list1.push_back(node);
225 list2.push_back(DTestNode(i));
226 }
227 ASSERT_TRUE(IsEqual(list1, list2));
228
229 auto it1 = list1.begin();
230 auto it2 = list2.begin();
231 for (uint32_t i = 0; i < 20; i++) {
232 if (i % 3 == 0) {
233 it1 = list1.erase(it1);
234 it2 = list2.erase(it2);
235 } else {
236 it1++;
237 it2++;
238 }
239 }
240 ASSERT_TRUE(IsEqual(list1, list2));
241
242 list1.clear();
243 list2.clear();
244 ASSERT_TRUE(IsEqual(list1, list2));
245
246 for (uint32_t i = 30; i < 50; i++) {
247 auto *node = NewNode(i);
248 list1.insert(list1.begin(), node);
249 list2.insert(list2.begin(), DTestNode(i));
250 }
251 ASSERT_TRUE(IsEqual(list1, list2));
252
253 list1.remove_if([](DListNode *node) { return reinterpret_cast<const DTestNode *>(node)->value < 41; });
254 list2.remove_if([](DTestNode &node) { return node.value < 41; });
255 ASSERT_TRUE(IsEqual(list1, list2));
256 }
257