• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright (c) 2016 Google Inc.
2 //
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 #include <memory>
16 #include <vector>
17 
18 #include "gmock/gmock.h"
19 
20 #include "source/opt/iterator.h"
21 #include "source/util/make_unique.h"
22 
23 namespace spvtools {
24 namespace opt {
25 namespace {
26 
27 using ::testing::ContainerEq;
28 
TEST(Iterator,IncrementDeref)29 TEST(Iterator, IncrementDeref) {
30   const int count = 100;
31   std::vector<std::unique_ptr<int>> data;
32   for (int i = 0; i < count; ++i) {
33     data.emplace_back(new int(i));
34   }
35 
36   UptrVectorIterator<int> it(&data, data.begin());
37   UptrVectorIterator<int> end(&data, data.end());
38 
39   EXPECT_EQ(*data[0], *it);
40   for (int i = 1; i < count; ++i) {
41     EXPECT_NE(end, it);
42     EXPECT_EQ(*data[i], *(++it));
43   }
44   EXPECT_EQ(end, ++it);
45 }
46 
TEST(Iterator,DecrementDeref)47 TEST(Iterator, DecrementDeref) {
48   const int count = 100;
49   std::vector<std::unique_ptr<int>> data;
50   for (int i = 0; i < count; ++i) {
51     data.emplace_back(new int(i));
52   }
53 
54   UptrVectorIterator<int> begin(&data, data.begin());
55   UptrVectorIterator<int> it(&data, data.end());
56 
57   for (int i = count - 1; i >= 0; --i) {
58     EXPECT_NE(begin, it);
59     EXPECT_EQ(*data[i], *(--it));
60   }
61   EXPECT_EQ(begin, it);
62 }
63 
TEST(Iterator,PostIncrementDeref)64 TEST(Iterator, PostIncrementDeref) {
65   const int count = 100;
66   std::vector<std::unique_ptr<int>> data;
67   for (int i = 0; i < count; ++i) {
68     data.emplace_back(new int(i));
69   }
70 
71   UptrVectorIterator<int> it(&data, data.begin());
72   UptrVectorIterator<int> end(&data, data.end());
73 
74   for (int i = 0; i < count; ++i) {
75     EXPECT_NE(end, it);
76     EXPECT_EQ(*data[i], *(it++));
77   }
78   EXPECT_EQ(end, it);
79 }
80 
TEST(Iterator,PostDecrementDeref)81 TEST(Iterator, PostDecrementDeref) {
82   const int count = 100;
83   std::vector<std::unique_ptr<int>> data;
84   for (int i = 0; i < count; ++i) {
85     data.emplace_back(new int(i));
86   }
87 
88   UptrVectorIterator<int> begin(&data, data.begin());
89   UptrVectorIterator<int> end(&data, data.end());
90   UptrVectorIterator<int> it(&data, data.end());
91 
92   EXPECT_EQ(end, it--);
93   for (int i = count - 1; i >= 1; --i) {
94     EXPECT_EQ(*data[i], *(it--));
95   }
96   // Decrementing .begin() is undefined behavior.
97   EXPECT_EQ(*data[0], *it);
98 }
99 
TEST(Iterator,Access)100 TEST(Iterator, Access) {
101   const int count = 100;
102   std::vector<std::unique_ptr<int>> data;
103   for (int i = 0; i < count; ++i) {
104     data.emplace_back(new int(i));
105   }
106 
107   UptrVectorIterator<int> it(&data, data.begin());
108 
109   for (int i = 0; i < count; ++i) EXPECT_EQ(*data[i], it[i]);
110 }
111 
TEST(Iterator,Comparison)112 TEST(Iterator, Comparison) {
113   const int count = 100;
114   std::vector<std::unique_ptr<int>> data;
115   for (int i = 0; i < count; ++i) {
116     data.emplace_back(new int(i));
117   }
118 
119   UptrVectorIterator<int> it(&data, data.begin());
120   UptrVectorIterator<int> end(&data, data.end());
121 
122   for (int i = 0; i < count; ++i, ++it) EXPECT_TRUE(it < end);
123   EXPECT_EQ(end, it);
124 }
125 
TEST(Iterator,InsertBeginEnd)126 TEST(Iterator, InsertBeginEnd) {
127   const int count = 100;
128 
129   std::vector<std::unique_ptr<int>> data;
130   std::vector<int> expected;
131   std::vector<int> actual;
132 
133   for (int i = 0; i < count; ++i) {
134     data.emplace_back(new int(i));
135     expected.push_back(i);
136   }
137 
138   // Insert at the beginning
139   expected.insert(expected.begin(), -100);
140   UptrVectorIterator<int> begin(&data, data.begin());
141   auto insert_point = begin.InsertBefore(MakeUnique<int>(-100));
142   for (int i = 0; i < count + 1; ++i) {
143     actual.push_back(*(insert_point++));
144   }
145   EXPECT_THAT(actual, ContainerEq(expected));
146 
147   // Insert at the end
148   expected.push_back(-42);
149   expected.push_back(-36);
150   expected.push_back(-77);
151   UptrVectorIterator<int> end(&data, data.end());
152   end = end.InsertBefore(MakeUnique<int>(-77));
153   end = end.InsertBefore(MakeUnique<int>(-36));
154   end = end.InsertBefore(MakeUnique<int>(-42));
155 
156   actual.clear();
157   begin = UptrVectorIterator<int>(&data, data.begin());
158   for (int i = 0; i < count + 4; ++i) {
159     actual.push_back(*(begin++));
160   }
161   EXPECT_THAT(actual, ContainerEq(expected));
162 }
163 
TEST(Iterator,InsertMiddle)164 TEST(Iterator, InsertMiddle) {
165   const int count = 100;
166 
167   std::vector<std::unique_ptr<int>> data;
168   std::vector<int> expected;
169   std::vector<int> actual;
170 
171   for (int i = 0; i < count; ++i) {
172     data.emplace_back(new int(i));
173     expected.push_back(i);
174   }
175 
176   const int insert_pos = 42;
177   expected.insert(expected.begin() + insert_pos, -100);
178   expected.insert(expected.begin() + insert_pos, -42);
179 
180   UptrVectorIterator<int> it(&data, data.begin());
181   for (int i = 0; i < insert_pos; ++i) ++it;
182   it = it.InsertBefore(MakeUnique<int>(-100));
183   it = it.InsertBefore(MakeUnique<int>(-42));
184   auto begin = UptrVectorIterator<int>(&data, data.begin());
185   for (int i = 0; i < count + 2; ++i) {
186     actual.push_back(*(begin++));
187   }
188   EXPECT_THAT(actual, ContainerEq(expected));
189 }
190 
TEST(IteratorRange,Interface)191 TEST(IteratorRange, Interface) {
192   const uint32_t count = 100;
193 
194   std::vector<std::unique_ptr<uint32_t>> data;
195 
196   for (uint32_t i = 0; i < count; ++i) {
197     data.emplace_back(new uint32_t(i));
198   }
199 
200   auto b = UptrVectorIterator<uint32_t>(&data, data.begin());
201   auto e = UptrVectorIterator<uint32_t>(&data, data.end());
202   auto range = IteratorRange<decltype(b)>(b, e);
203 
204   EXPECT_EQ(b, range.begin());
205   EXPECT_EQ(e, range.end());
206   EXPECT_FALSE(range.empty());
207   EXPECT_EQ(count, range.size());
208   EXPECT_EQ(0u, *range.begin());
209   EXPECT_EQ(99u, *(--range.end()));
210 
211   // IteratorRange itself is immutable.
212   ++b, --e;
213   EXPECT_EQ(count, range.size());
214   ++range.begin(), --range.end();
215   EXPECT_EQ(count, range.size());
216 }
217 
TEST(Iterator,FilterIterator)218 TEST(Iterator, FilterIterator) {
219   struct Placeholder {
220     int val;
221   };
222   std::vector<Placeholder> data = {{1}, {2}, {3}, {4}, {5},
223                                    {6}, {7}, {8}, {9}, {10}};
224 
225   // Predicate to only consider odd values.
226   struct Predicate {
227     bool operator()(const Placeholder& data) { return data.val % 2; }
228   };
229   Predicate pred;
230 
231   auto filter_range = MakeFilterIteratorRange(data.begin(), data.end(), pred);
232 
233   EXPECT_EQ(filter_range.begin().Get(), data.begin());
234   EXPECT_EQ(filter_range.end(), filter_range.begin().GetEnd());
235 
236   for (Placeholder& data : filter_range) {
237     EXPECT_EQ(data.val % 2, 1);
238   }
239 
240   for (auto it = filter_range.begin(); it != filter_range.end(); it++) {
241     EXPECT_EQ(it->val % 2, 1);
242     EXPECT_EQ((*it).val % 2, 1);
243   }
244 
245   for (auto it = filter_range.begin(); it != filter_range.end(); ++it) {
246     EXPECT_EQ(it->val % 2, 1);
247     EXPECT_EQ((*it).val % 2, 1);
248   }
249 
250   EXPECT_EQ(MakeFilterIterator(data.begin(), data.end(), pred).Get(),
251             data.begin());
252   EXPECT_EQ(MakeFilterIterator(data.end(), data.end(), pred).Get(), data.end());
253   EXPECT_EQ(MakeFilterIterator(data.begin(), data.end(), pred).GetEnd(),
254             MakeFilterIterator(data.end(), data.end(), pred));
255   EXPECT_NE(MakeFilterIterator(data.begin(), data.end(), pred),
256             MakeFilterIterator(data.end(), data.end(), pred));
257 
258   // Empty range: no values satisfies the predicate.
259   auto empty_range = MakeFilterIteratorRange(
260       data.begin(), data.end(),
261       [](const Placeholder& data) { return data.val > 10; });
262   EXPECT_EQ(empty_range.begin(), empty_range.end());
263 }
264 
265 }  // namespace
266 }  // namespace opt
267 }  // namespace spvtools
268