1 /**
2 * Copyright (c) Glow Contributors. See CONTRIBUTORS file.
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 // This file tests the basic functionality of the float16 type.
18 // This is by no mean a test to show the IEEE 754 compliance!
19
20 #include "glow/Base/TaggedList.h"
21 #include "gtest/gtest.h"
22
23 #include <iterator>
24
25 using namespace glow;
26
27 namespace {
28 class Node : public TaggedListNode<Node> {
29 public:
Node(int id)30 Node(int id) : id(id) {}
31 int id;
32 int adds = 0;
33 };
34 } // namespace
35
36 struct ListTraits : TaggedListTraits<Node> {
addNodeToListListTraits37 void addNodeToList(Node *node) { node->adds++; }
removeNodeFromListListTraits38 void removeNodeFromList(Node *node) { node->adds--; }
39 };
40
41 using List = TaggedList<Node, ListTraits>;
42
TEST(TaggedList,empty)43 TEST(TaggedList, empty) {
44 List ls;
45 EXPECT_TRUE(ls.empty());
46 EXPECT_EQ(ls.size(), 0);
47 EXPECT_TRUE(ls.begin() == ls.end());
48 EXPECT_FALSE(ls.begin() != ls.end());
49 }
50
TEST(TaggedList,empty_const)51 TEST(TaggedList, empty_const) {
52 const List ls;
53 EXPECT_TRUE(ls.empty());
54 EXPECT_EQ(ls.size(), 0);
55 EXPECT_TRUE(ls.begin() == ls.end());
56 EXPECT_FALSE(ls.begin() != ls.end());
57 }
58
TEST(TaggedList,insert)59 TEST(TaggedList, insert) {
60 List ls;
61 Node n7(7);
62 auto ins = ls.insert(ls.end(), &n7);
63
64 EXPECT_EQ(ls.size(), 1);
65 EXPECT_FALSE(ls.empty());
66 EXPECT_TRUE(ls.begin() == ins);
67 EXPECT_FALSE(ls.begin() != ins);
68 EXPECT_TRUE(ins != ls.end());
69 EXPECT_FALSE(ins == ls.end());
70 EXPECT_TRUE(&*ins == &n7);
71 EXPECT_EQ(ins->id, 7);
72
73 // Trait callback.
74 EXPECT_EQ(n7.adds, 1);
75
76 // Insert before a real elem: [n8 n7]
77 Node n8(8);
78 auto in2 = ls.insert(ins, &n8);
79 EXPECT_EQ(ls.size(), 2);
80 EXPECT_TRUE(&*in2 == &n8);
81 EXPECT_TRUE(ls.begin() == in2);
82 EXPECT_TRUE(ls.begin() != ins);
83 EXPECT_EQ(ins->id, 7);
84 EXPECT_EQ(in2->id, 8);
85
86 // Insert in the middle: [n8 n9 n7]
87 Node n9(9);
88 auto in3 = ls.insert(ins, &n9);
89 EXPECT_TRUE(ls.begin() != in3);
90 EXPECT_TRUE(ls.end() != in3);
91 EXPECT_EQ(in3->id, 9);
92
93 // Iterate over the list in both directions.
94 auto i = ls.begin();
95 EXPECT_EQ(i->id, 8);
96 ++i;
97 EXPECT_EQ(i++->id, 9);
98 EXPECT_EQ(i->id, 7);
99 ++i;
100 EXPECT_TRUE(i == ls.end());
101 EXPECT_EQ((--i)->id, 7);
102 --i;
103 EXPECT_EQ((i--)->id, 9);
104 EXPECT_EQ(i->id, 8);
105 EXPECT_TRUE(i == ls.begin());
106
107 // Same, with const_iterator.
108 {
109 const auto &cls = ls;
110 auto i = cls.begin();
111 EXPECT_EQ(i->id, 8);
112 ++i;
113 EXPECT_EQ(i++->id, 9);
114 EXPECT_EQ(i->id, 7);
115 ++i;
116 EXPECT_TRUE(i == cls.end());
117 EXPECT_EQ((--i)->id, 7);
118 --i;
119 EXPECT_EQ((i--)->id, 9);
120 EXPECT_EQ(i->id, 8);
121 EXPECT_TRUE(i == cls.begin());
122 }
123
124 // Destructor crashes trying to delete stack nodes.
125 ls.clearAndLeakNodesUnsafely();
126 }
127
TEST(TaggedList,remove)128 TEST(TaggedList, remove) {
129 List ls;
130 Node n1(1), n2(2), n3(3);
131 auto i1 = ls.insert(ls.end(), &n1);
132 ls.insert(ls.end(), &n2);
133 auto i3 = ls.insert(ls.end(), &n3);
134 EXPECT_EQ(ls.size(), 3);
135 EXPECT_EQ(n1.adds, 1);
136 EXPECT_EQ(n2.adds, 1);
137 EXPECT_EQ(n3.adds, 1);
138 EXPECT_TRUE(n1.inTaggedList());
139
140 // Remove from the middle.
141 EXPECT_EQ(ls.remove(n2.getIterator()), &n2);
142 EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end()));
143 EXPECT_EQ(n1.adds, 1);
144 EXPECT_EQ(n2.adds, 0);
145 EXPECT_EQ(n3.adds, 1);
146
147 // Remove from back.
148 EXPECT_EQ(ls.remove(i3), &n3);
149 EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end()));
150 EXPECT_EQ(n1.adds, 1);
151 EXPECT_EQ(n2.adds, 0);
152 EXPECT_EQ(n3.adds, 0);
153
154 // Remove from front.
155 EXPECT_EQ(ls.remove(i1), &n1);
156 EXPECT_EQ(ls.size(), std::distance(ls.begin(), ls.end()));
157 EXPECT_EQ(n1.adds, 0);
158 EXPECT_EQ(n2.adds, 0);
159 EXPECT_EQ(n3.adds, 0);
160 EXPECT_FALSE(n1.inTaggedList());
161
162 EXPECT_TRUE(ls.empty());
163 }
164
TEST(TaggedList,reinsert)165 TEST(TaggedList, reinsert) {
166 List ls;
167 Node n1(1);
168
169 EXPECT_FALSE(n1.inTaggedList());
170 ls.push_back(&n1);
171 EXPECT_TRUE(n1.inTaggedList());
172 ls.remove(&n1);
173 EXPECT_FALSE(n1.inTaggedList());
174 ls.push_back(&n1);
175 EXPECT_TRUE(n1.inTaggedList());
176 ls.remove(&n1);
177 }
178
TEST(TaggedList,reverse_iterator)179 TEST(TaggedList, reverse_iterator) {
180 List ls;
181 Node n1(1), n2(2), n3(3);
182 ls.push_front(&n1);
183 ls.push_back(&n2);
184 ls.push_back(&n3);
185
186 EXPECT_EQ(ls.size(), std::distance(ls.rbegin(), ls.rend()));
187
188 auto i = ls.rbegin();
189 EXPECT_EQ(i->id, 3);
190 ++i;
191 EXPECT_EQ(i->id, 2);
192 i++;
193 EXPECT_EQ(i->id, 1);
194 EXPECT_TRUE(++i == ls.rend());
195
196 EXPECT_EQ((--i)->id, 1);
197 EXPECT_EQ((i--)->id, 1);
198 EXPECT_EQ(i->id, 2);
199 --i;
200 EXPECT_EQ(i->id, 3);
201 EXPECT_TRUE(i == ls.rbegin());
202
203 // Same, with const_reverse_iterator.
204 {
205 const auto &cls = ls;
206 auto i = cls.rbegin();
207 EXPECT_EQ(i->id, 3);
208 ++i;
209 EXPECT_EQ(i->id, 2);
210 i++;
211 EXPECT_EQ(i->id, 1);
212 EXPECT_TRUE(++i == cls.rend());
213
214 EXPECT_EQ((--i)->id, 1);
215 EXPECT_EQ((i--)->id, 1);
216 EXPECT_EQ(i->id, 2);
217 --i;
218 EXPECT_EQ(i->id, 3);
219 EXPECT_TRUE(i == cls.rbegin());
220 }
221
222 ls.clearAndLeakNodesUnsafely();
223 }
224
TEST(TaggedList,clearAndLeakNodesUnsafely)225 TEST(TaggedList, clearAndLeakNodesUnsafely) {
226 List ls;
227 Node n1(1), n2(2), n3(3);
228 ls.insert(ls.end(), &n1);
229 ls.insert(ls.end(), &n2);
230 ls.insert(ls.end(), &n3);
231
232 EXPECT_EQ(ls.size(), 3);
233 EXPECT_EQ(n1.adds, 1);
234 EXPECT_EQ(n2.adds, 1);
235 EXPECT_EQ(n3.adds, 1);
236
237 ls.clearAndLeakNodesUnsafely();
238
239 EXPECT_TRUE(ls.begin() == ls.end());
240 EXPECT_EQ(ls.size(), 0);
241 EXPECT_EQ(n1.adds, 1);
242 EXPECT_EQ(n2.adds, 1);
243 EXPECT_EQ(n3.adds, 1);
244 }
245
TEST(TaggedList,clear)246 TEST(TaggedList, clear) {
247 List ls;
248 Node *n1 = new Node(1);
249 Node *n2 = new Node(2);
250 Node *n3 = new Node(3);
251 ls.insert(ls.end(), n1);
252 ls.insert(ls.end(), n2);
253 ls.insert(ls.end(), n3);
254
255 EXPECT_EQ(ls.size(), 3);
256 EXPECT_EQ(n1->adds, 1);
257 EXPECT_EQ(n2->adds, 1);
258 EXPECT_EQ(n3->adds, 1);
259
260 ls.clear();
261
262 EXPECT_TRUE(ls.empty());
263 EXPECT_TRUE(ls.begin() == ls.end());
264 }
265
TEST(TaggedList,pop)266 TEST(TaggedList, pop) {
267 List ls;
268 ls.push_front(new Node(1));
269 ls.push_back(new Node(2));
270 ls.pop_back();
271 EXPECT_EQ(ls.front().id, 1);
272 EXPECT_EQ(ls.back().id, 1);
273 ls.pop_front();
274 EXPECT_TRUE(ls.empty());
275 EXPECT_TRUE(ls.begin() == ls.end());
276 }
277
TEST(TaggedList,inequality)278 TEST(TaggedList, inequality) {
279 List ls;
280
281 EXPECT_FALSE(ls.begin() < ls.begin());
282 EXPECT_TRUE(ls.begin() <= ls.begin());
283 EXPECT_FALSE(ls.begin() > ls.begin());
284 EXPECT_TRUE(ls.begin() >= ls.begin());
285
286 ls.push_front(new Node(1));
287 ls.push_back(new Node(2));
288
289 auto i1 = ls.begin();
290 auto i2 = ls.back().getIterator();
291
292 EXPECT_TRUE(i1 < i2);
293 EXPECT_TRUE(i1 <= i2);
294 EXPECT_FALSE(i1 > i2);
295 EXPECT_FALSE(i1 >= i2);
296 EXPECT_FALSE(i2 < i1);
297 EXPECT_FALSE(i2 <= i1);
298 EXPECT_TRUE(i2 > i1);
299 EXPECT_TRUE(i2 >= i1);
300
301 EXPECT_TRUE(i1 < ls.end());
302 EXPECT_TRUE(i1 <= ls.end());
303 EXPECT_FALSE(i1 > ls.end());
304 EXPECT_FALSE(i1 >= ls.end());
305 EXPECT_FALSE(ls.end() < i1);
306 EXPECT_FALSE(ls.end() <= i1);
307 EXPECT_TRUE(ls.end() > i1);
308 EXPECT_TRUE(ls.end() >= i1);
309
310 // Same thing for reverse iterators.
311 auto r1 = ls.rbegin();
312 auto r2 = ls.front().getReverseIterator();
313
314 EXPECT_TRUE(r1 < r2);
315 EXPECT_TRUE(r1 <= r2);
316 EXPECT_FALSE(r1 > r2);
317 EXPECT_FALSE(r1 >= r2);
318 EXPECT_FALSE(r2 < r1);
319 EXPECT_FALSE(r2 <= r1);
320 EXPECT_TRUE(r2 > r1);
321 EXPECT_TRUE(r2 >= r1);
322
323 EXPECT_TRUE(r1 < ls.rend());
324 EXPECT_TRUE(r1 <= ls.rend());
325 EXPECT_FALSE(r1 > ls.rend());
326 EXPECT_FALSE(r1 >= ls.rend());
327 EXPECT_FALSE(ls.rend() < r1);
328 EXPECT_FALSE(ls.rend() <= r1);
329 EXPECT_TRUE(ls.rend() > r1);
330 EXPECT_TRUE(ls.rend() >= r1);
331 }
332
TEST(TaggedList,sequencing)333 TEST(TaggedList, sequencing) {
334 List ls;
335
336 for (unsigned i = 0; i < 10000; i++)
337 ls.push_back(new Node(i));
338
339 // Verify iterator ordering forwards and backwards.
340 for (auto i1 = ls.begin(); i1 != ls.end();) {
341 auto i0 = i1++;
342 EXPECT_TRUE(i0 < i1);
343 }
344 for (auto i1 = ls.rbegin(); i1 != ls.rend();) {
345 auto i0 = i1++;
346 EXPECT_TRUE(i0 < i1);
347 }
348
349 Node &middle = ls.front();
350 for (unsigned i = 0; i < 10000; i++)
351 ls.push_front(new Node(i + 10000));
352
353 for (auto i1 = ls.begin(); i1 != ls.end();) {
354 auto i0 = i1++;
355 EXPECT_TRUE(i0 < i1);
356 }
357 for (auto i1 = ls.rbegin(); i1 != ls.rend();) {
358 auto i0 = i1++;
359 EXPECT_TRUE(i0 < i1);
360 }
361
362 for (unsigned i = 0; i < 10000; i++)
363 ls.insert(middle.getIterator(), new Node(i + 20000));
364
365 for (auto i1 = ls.begin(); i1 != ls.end();) {
366 auto i0 = i1++;
367 EXPECT_TRUE(i0 < i1);
368 }
369 for (auto i1 = ls.rbegin(); i1 != ls.rend();) {
370 auto i0 = i1++;
371 EXPECT_TRUE(i0 < i1);
372 }
373 }
374