1 /**
2 * Copyright (c) 2021-2022 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 namespace globals {
26 constexpr const int DEFAULT_LIST_CAPACITY = 1000;
27 }
28
29 struct TestNode : public ListNode {
30 TestNode() = default;
TestNodeTestNode31 TestNode(int v) : value(v) {}
32 int value {0};
33 };
34
operator ==(const TestNode & lhs,const TestNode & rhs)35 bool operator==(const TestNode &lhs, const TestNode &rhs)
36 {
37 return lhs.value == rhs.value;
38 }
39
40 class ListTest : public ::testing::Test {
41 public:
ListTest()42 ListTest()
43 {
44 nodes_.reserve(globals::DEFAULT_LIST_CAPACITY);
45 }
46 virtual ~ListTest() = default;
47
48 template <typename... Args>
NewNode(Args &&...args)49 TestNode *NewNode(Args &&... args)
50 {
51 // Vector allocation is unacceptable
52 ASSERT(nodes_.size() < nodes_.capacity());
53
54 nodes_.emplace_back(std::forward<Args>(args)...);
55 return &nodes_.back();
56 }
57
IsEqual(const List<TestNode> & list1,std::initializer_list<TestNode> list2) const58 bool IsEqual(const List<TestNode> &list1, std::initializer_list<TestNode> list2) const
59 {
60 if (GetListSize(list1) != list2.size()) {
61 return false;
62 }
63 return std::equal(list1.begin(), list1.end(), list2.begin());
64 }
65
GetListSize(const List<TestNode> & list) const66 size_t GetListSize(const List<TestNode> &list) const
67 {
68 size_t size = 0;
69 for (auto it : list)
70 size++;
71 return size;
72 }
73
74 private:
75 std::vector<TestNode> nodes_;
76 };
77
TEST_F(ListTest,Common)78 TEST_F(ListTest, Common)
79 {
80 TestNode *node;
81 ListIterator<TestNode> it;
82 List<TestNode> list;
83 List<TestNode> list2;
84
85 ASSERT_TRUE(list.Empty());
86
87 node = NewNode(1);
88 list.PushFront(*node);
89
90 ASSERT_FALSE(list.Empty());
91 ASSERT_EQ(node, &list.Front());
92 ASSERT_EQ(node, &*list.begin());
93 ASSERT_EQ(++list.begin(), list.end());
94
95 ASSERT_TRUE(IsEqual(list, {1}));
96
97 list.PushFront(*NewNode(2));
98
99 ASSERT_TRUE(IsEqual(list, {2, 1}));
100
101 list.PopFront();
102 ASSERT_TRUE(IsEqual(list, {1}));
103
104 list.InsertAfter(list.begin(), *NewNode(2));
105 ASSERT_TRUE(IsEqual(list, {1, 2}));
106
107 list.PushFront(*NewNode(0));
108 ASSERT_TRUE(IsEqual(list, {0, 1, 2}));
109
110 list.EraseAfter(list.begin() + 1);
111 ASSERT_TRUE(IsEqual(list, {0, 1}));
112
113 it = list.begin() + 1;
114 for (int i = 0; i < 8; i++)
115 it = list.InsertAfter(it, *NewNode(i + 2));
116 ASSERT_TRUE(IsEqual(list, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}));
117
118 list2.Splice(list2.before_begin(), list);
119 ASSERT_TRUE(list.Empty());
120 ASSERT_TRUE(IsEqual(list2, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}));
121
122 list.Splice(list.before_begin(), list2, list2.before_begin() + 5, list2.end());
123 ASSERT_TRUE(IsEqual(list, {5, 6, 7, 8, 9}));
124 ASSERT_TRUE(IsEqual(list2, {0, 1, 2, 3, 4}));
125
126 list.Splice(list.before_begin(), list2);
127 ASSERT_TRUE(list2.Empty());
128 ASSERT_TRUE(IsEqual(list, {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}));
129
130 list2.Splice(list2.before_begin(), list, list.begin() + 1, list.begin() + 5);
131 ASSERT_TRUE(IsEqual(list, {0, 1, 5, 6, 7, 8, 9}));
132 ASSERT_TRUE(IsEqual(list2, {2, 3, 4}));
133
134 list2.Splice(list2.begin(), list, list.before_begin());
135 ASSERT_TRUE(IsEqual(list, {1, 5, 6, 7, 8, 9}));
136 ASSERT_TRUE(IsEqual(list2, {2, 0, 3, 4}));
137
138 list.Remove(9);
139 ASSERT_TRUE(IsEqual(list, {1, 5, 6, 7, 8}));
140
141 list.EraseAfter(list.begin() + 1, list.begin() + 4);
142 ASSERT_TRUE(IsEqual(list, {1, 5, 8}));
143 }
144
145 struct DTestNode : public DListNode {
146 DTestNode() = default;
DTestNodeDTestNode147 DTestNode(int v) : value(v) {}
148 int value {0};
149 };
150
151 class DListTest : public ::testing::Test {
152 public:
DListTest()153 DListTest()
154 {
155 nodes_.reserve(globals::DEFAULT_LIST_CAPACITY);
156 }
157 virtual ~DListTest() = default;
158
159 template <typename... Args>
NewNode(Args &&...args)160 DTestNode *NewNode(Args &&... args)
161 {
162 // Vector allocation is unacceptable
163 ASSERT(nodes_.size() < nodes_.capacity());
164
165 nodes_.emplace_back(std::forward<Args>(args)...);
166 return &nodes_.back();
167 }
168
IsEqual(const DList & list1,std::list<DTestNode> list2) const169 bool IsEqual(const DList &list1, std::list<DTestNode> list2) const
170 {
171 if (list1.size() != list2.size()) {
172 return false;
173 }
174
175 auto it1 = list1.begin();
176 auto it2 = list2.begin();
177 for (; it1 != list1.end(); it1++, it2++) {
178 auto *node = reinterpret_cast<const DTestNode *>(&(*it1));
179 if (node->value != (*it2).value) {
180 return false;
181 }
182 }
183 it1 = list1.begin();
184 it2 = list2.begin();
185 for (; it2 != list2.end(); ++it1, ++it2) {
186 auto *node = reinterpret_cast<const DTestNode *>(&(*it1));
187 if (node->value != (*it2).value) {
188 return false;
189 }
190 }
191
192 auto it3 = list1.rbegin();
193 auto it4 = list2.rbegin();
194 for (; it3 != list1.rend(); it3++, it4++) {
195 auto *node = reinterpret_cast<const DTestNode *>(&(*it3));
196 if (node->value != (*it4).value) {
197 return false;
198 }
199 }
200 it3 = list1.rbegin();
201 it4 = list2.rbegin();
202 for (; it4 != list2.rend(); ++it3, ++it4) {
203 auto *node = reinterpret_cast<const DTestNode *>(&(*it3));
204 if (node->value != (*it4).value) {
205 return false;
206 }
207 }
208 return true;
209 }
210
211 private:
212 std::vector<DTestNode> nodes_;
213 };
214
TEST_F(DListTest,Common)215 TEST_F(DListTest, Common)
216 {
217 DList list1;
218 std::list<DTestNode> list2;
219 for (uint32_t i = 0; i < 20; i++) {
220 auto *node = NewNode(i);
221 list1.push_back(node);
222 list2.push_back(i);
223 }
224 ASSERT_TRUE(IsEqual(list1, list2));
225
226 auto it1 = list1.begin();
227 auto it2 = list2.begin();
228 for (uint32_t i = 0; i < 20; i++) {
229 if (i % 3 == 0) {
230 it1 = list1.erase(it1);
231 it2 = list2.erase(it2);
232 } else {
233 it1++;
234 it2++;
235 }
236 }
237 ASSERT_TRUE(IsEqual(list1, list2));
238
239 list1.clear();
240 list2.clear();
241 ASSERT_TRUE(IsEqual(list1, list2));
242
243 for (uint32_t i = 30; i < 50; i++) {
244 auto *node = NewNode(i);
245 list1.insert(list1.begin(), node);
246 list2.insert(list2.begin(), i);
247 }
248 ASSERT_TRUE(IsEqual(list1, list2));
249
250 list1.remove_if([](DListNode *node) { return reinterpret_cast<const DTestNode *>(node)->value < 41; });
251 list2.remove_if([](DTestNode &node) { return node.value < 41; });
252 ASSERT_TRUE(IsEqual(list1, list2));
253 }
254