• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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