1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2015-2015. Distributed under the Boost
4 // Software License, Version 1.0. (See accompanying file
5 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 //
7 // See http://www.boost.org/libs/intrusive for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #include <boost/intrusive/detail/iterator.hpp>
12 #include <boost/intrusive/detail/mpl.hpp>
13 #include <boost/static_assert.hpp>
14
15 namespace boost{ namespace intrusive { namespace test{
16
17 //////////////////////////////////////////////
18 //
19 // Some traits to avoid special cases with
20 // containers without bidirectional iterators
21 //
22 //////////////////////////////////////////////
23 template<class C>
24 struct has_member_reverse_iterator
25 {
26 typedef char yes_type;
27 struct no_type{ char _[2]; };
28
29 template<typename D> static no_type test(...);
30 template<typename D> static yes_type test(typename D::reverse_iterator const*);
31 static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
32 };
33
34 template<class C>
35 struct has_member_const_reverse_iterator
36 {
37 typedef char yes_type;
38 struct no_type{ char _[2]; };
39
40 template<typename D> static no_type test(...);
41 template<typename D> static yes_type test(typename D::const_reverse_iterator const*);
42 static const bool value = sizeof(test<C>(0)) == sizeof(yes_type);
43 };
44
45 template<class C, bool = has_member_reverse_iterator<C>::value>
46 struct get_reverse_iterator
47 {
48 typedef typename C::reverse_iterator type;
beginboost::intrusive::test::get_reverse_iterator49 static type begin(C &c) { return c.rbegin(); }
endboost::intrusive::test::get_reverse_iterator50 static type end(C &c) { return c.rend(); }
51 };
52
53 template<class C>
54 struct get_reverse_iterator<C, false>
55 {
56 typedef typename C::iterator type;
beginboost::intrusive::test::get_reverse_iterator57 static type begin(C &c) { return c.begin(); }
endboost::intrusive::test::get_reverse_iterator58 static type end(C &c) { return c.end(); }
59 };
60
61 template<class C, bool = has_member_const_reverse_iterator<C>::value>
62 struct get_const_reverse_iterator
63 {
64 typedef typename C::const_reverse_iterator type;
beginboost::intrusive::test::get_const_reverse_iterator65 static type begin(C &c) { return c.crbegin(); }
endboost::intrusive::test::get_const_reverse_iterator66 static type end(C &c) { return c.crend(); }
67 };
68
69 template<class C>
70 struct get_const_reverse_iterator<C, false>
71 {
72 typedef typename C::const_iterator type;
beginboost::intrusive::test::get_const_reverse_iterator73 static type begin(C &c) { return c.cbegin(); }
endboost::intrusive::test::get_const_reverse_iterator74 static type end(C &c) { return c.cend(); }
75 };
76
77 //////////////////////////////////////////////
78 //
79 // Iterator tests
80 //
81 //////////////////////////////////////////////
82
83 template<class I>
test_iterator_operations(I b,I e)84 void test_iterator_operations(I b, I e)
85 {
86 //Test the range is not empty
87 BOOST_TEST(b != e);
88 BOOST_TEST(!(b == e));
89 {
90 I i;
91 I i2(b); //CopyConstructible
92 i = i2; //Assignable
93 //Destructible
94 (void)i;
95 (void)i2;
96 }
97
98 typedef typename iterator_traits<I>::reference reference;
99 reference r = *b;
100 (void)r;
101 typedef typename iterator_traits<I>::pointer pointer;
102 pointer p = (iterator_arrow_result)(b);
103 (void)p;
104 I &ri= ++b;
105 (void)ri;
106 const I &cri= b++;
107 (void)cri;
108 }
109
110 template<class C>
test_iterator_compatible(C & c)111 void test_iterator_compatible(C &c)
112 {
113 typedef typename C::iterator iterator;
114 typedef typename C::const_iterator const_iterator;
115 typedef typename get_reverse_iterator<C>::type reverse_iterator;
116 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
117 //Basic operations
118 test_iterator_operations(c. begin(), c. end());
119 test_iterator_operations(c.cbegin(), c.cend());
120 test_iterator_operations(get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
121 test_iterator_operations(get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
122 //Make sure dangeous conversions are not possible
123 BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_iterator, iterator>::value));
124 BOOST_STATIC_ASSERT((!boost::intrusive::detail::is_convertible<const_reverse_iterator, reverse_iterator>::value));
125 //Test iterator conversions
126 {
127 const_iterator ci;
128 iterator i(c.begin());
129 ci = i;
130 (void)ci;
131 BOOST_ASSERT(ci == i);
132 BOOST_ASSERT(*ci == *i);
133 const_iterator ci2(i);
134 BOOST_ASSERT(ci2 == i);
135 BOOST_ASSERT(*ci2 == *i);
136 (void)ci2;
137 }
138 //Test reverse_iterator conversions
139 {
140 const_reverse_iterator cr;
141 reverse_iterator r(get_reverse_iterator<C>::begin(c));
142 cr = r;
143 BOOST_ASSERT(cr == r);
144 BOOST_ASSERT(*cr == *r);
145 const_reverse_iterator cr2(r);
146 BOOST_ASSERT(cr2 == r);
147 BOOST_ASSERT(*cr2 == *r);
148 (void)cr2;
149 }
150 }
151
152 template<class C>
test_iterator_input_and_compatible(C & c)153 void test_iterator_input_and_compatible(C &c)
154 {
155 typedef typename C::iterator iterator;
156 typedef typename C::const_iterator const_iterator;
157 typedef typename get_reverse_iterator<C>::type reverse_iterator;
158 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
159 typedef iterator_traits<iterator> nit_traits;
160 typedef iterator_traits<const_iterator> cit_traits;
161 typedef iterator_traits<reverse_iterator> rnit_traits;
162 typedef iterator_traits<const_reverse_iterator> crit_traits;
163
164 using boost::move_detail::is_same;
165 //Trivial typedefs
166 BOOST_STATIC_ASSERT((!is_same<iterator, const_iterator>::value));
167 BOOST_STATIC_ASSERT((!is_same<reverse_iterator, const_reverse_iterator>::value));
168 //difference_type
169 typedef typename C::difference_type difference_type;
170 BOOST_STATIC_ASSERT((is_same<difference_type, typename nit_traits::difference_type>::value));
171 BOOST_STATIC_ASSERT((is_same<difference_type, typename cit_traits::difference_type>::value));
172 BOOST_STATIC_ASSERT((is_same<difference_type, typename rnit_traits::difference_type>::value));
173 BOOST_STATIC_ASSERT((is_same<difference_type, typename crit_traits::difference_type>::value));
174 //value_type
175 typedef typename C::value_type value_type;
176 BOOST_STATIC_ASSERT((is_same<value_type, typename nit_traits::value_type>::value));
177 BOOST_STATIC_ASSERT((is_same<value_type, typename cit_traits::value_type>::value));
178 BOOST_STATIC_ASSERT((is_same<value_type, typename rnit_traits::value_type>::value));
179 BOOST_STATIC_ASSERT((is_same<value_type, typename crit_traits::value_type>::value));
180 //pointer
181 typedef typename C::pointer pointer;
182 typedef typename C::const_pointer const_pointer;
183 BOOST_STATIC_ASSERT((is_same<pointer, typename nit_traits::pointer>::value));
184 BOOST_STATIC_ASSERT((is_same<const_pointer, typename cit_traits::pointer>::value));
185 BOOST_STATIC_ASSERT((is_same<pointer, typename rnit_traits::pointer>::value));
186 BOOST_STATIC_ASSERT((is_same<const_pointer, typename crit_traits::pointer>::value));
187 //reference
188 typedef typename C::reference reference;
189 typedef typename C::const_reference const_reference;
190 BOOST_STATIC_ASSERT((is_same<reference, typename nit_traits::reference>::value));
191 BOOST_STATIC_ASSERT((is_same<const_reference, typename cit_traits::reference>::value));
192 BOOST_STATIC_ASSERT((is_same<reference, typename rnit_traits::reference>::value));
193 BOOST_STATIC_ASSERT((is_same<const_reference, typename crit_traits::reference>::value));
194 //Dynamic tests
195 test_iterator_compatible(c);
196 }
197
198 template<class C, class I>
test_iterator_forward_functions(C const & c,I const b,I const e)199 void test_iterator_forward_functions(C const &c, I const b, I const e)
200 {
201 typedef typename C::size_type size_type;
202 {
203 size_type i = 0;
204 I it = b;
205 for(I it2 = b; i != c.size(); ++it, ++i){
206 BOOST_TEST(it == it2++);
207 I ittmp(it);
208 I *iaddr = &ittmp;
209 BOOST_TEST(&(++ittmp) == iaddr);
210 BOOST_TEST(ittmp == it2);
211 }
212 BOOST_TEST(i == c.size());
213 BOOST_TEST(it == e);
214 }
215 }
216
217 template<class C>
test_iterator_forward_and_compatible(C & c)218 void test_iterator_forward_and_compatible(C &c)
219 {
220 test_iterator_input_and_compatible(c);
221 test_iterator_forward_functions(c, c.begin(), c.end());
222 test_iterator_forward_functions(c, c.cbegin(), c.cend());
223 test_iterator_forward_functions(c, get_reverse_iterator<C>::begin(c), get_reverse_iterator<C>::end(c));
224 test_iterator_forward_functions(c, get_const_reverse_iterator<C>::begin(c), get_const_reverse_iterator<C>::end(c));
225 }
226
227 template<class C, class I>
test_iterator_bidirectional_functions(C const & c,I const b,I const e)228 void test_iterator_bidirectional_functions(C const &c, I const b, I const e)
229 {
230 typedef typename C::size_type size_type;
231 {
232 size_type i = 0;
233 I it = e;
234 for(I it2 = e; i != c.size(); --it, ++i){
235 BOOST_TEST(it == it2--);
236 I ittmp(it);
237 I*iaddr = &ittmp;
238 BOOST_TEST(&(--ittmp) == iaddr);
239 BOOST_TEST(ittmp == it2);
240 BOOST_TEST((++ittmp) == it);
241 }
242 BOOST_TEST(i == c.size());
243 BOOST_TEST(it == b);
244 }
245 }
246
247 template<class C>
test_iterator_bidirectional_and_compatible(C & c)248 void test_iterator_bidirectional_and_compatible(C &c)
249 {
250 test_iterator_forward_and_compatible(c);
251 test_iterator_bidirectional_functions(c, c.begin(), c.end());
252 test_iterator_bidirectional_functions(c, c.cbegin(), c.cend());
253 test_iterator_bidirectional_functions(c, c.rbegin(), c.rend());
254 test_iterator_bidirectional_functions(c, c.crbegin(), c.crend());
255 }
256
257 template<class C, class I>
test_iterator_random_functions(C const & c,I const b,I const e)258 void test_iterator_random_functions(C const &c, I const b, I const e)
259 {
260 typedef typename C::size_type size_type;
261 {
262 I it = b;
263 for(size_type i = 0, m = c.size(); i != m; ++i, ++it){
264 BOOST_TEST(i == size_type(it - b));
265 BOOST_TEST(b[i] == *it);
266 BOOST_TEST(&b[i] == &*it);
267 BOOST_TEST((b + i) == it);
268 BOOST_TEST((i + b) == it);
269 BOOST_TEST(b == (it - i));
270 I tmp(b);
271 BOOST_TEST((tmp+=i) == it);
272 tmp = it;
273 BOOST_TEST(b == (tmp-=i));
274 }
275 BOOST_TEST(c.size() == size_type(e - b));
276 }
277 {
278 I it(b), itb(b);
279 if(b != e){
280 for(++it; it != e; ++it){
281 BOOST_TEST(itb < it);
282 BOOST_TEST(itb <= it);
283 BOOST_TEST(!(itb > it));
284 BOOST_TEST(!(itb >= it));
285 BOOST_TEST(it > itb);
286 BOOST_TEST(it >= itb);
287 BOOST_TEST(!(it < itb));
288 BOOST_TEST(!(it <= itb));
289 BOOST_TEST(it >= it);
290 BOOST_TEST(it <= it);
291 itb = it;
292 }
293 }
294 }
295 }
296
297 template<class C>
test_iterator_random_and_compatible(C & c)298 void test_iterator_random_and_compatible(C &c)
299 {
300 test_iterator_bidirectional_and_compatible(c);
301 test_iterator_random_functions(c, c.begin(), c.end());
302 test_iterator_random_functions(c, c.cbegin(), c.cend());
303 test_iterator_random_functions(c, c.rbegin(), c.rend());
304 test_iterator_random_functions(c, c.crbegin(), c.crend());
305 }
306
307 ////////////////////////
308
309 template<class C>
test_iterator_forward(C & c)310 void test_iterator_forward(C &c)
311 {
312 typedef typename C::iterator iterator;
313 typedef typename C::const_iterator const_iterator;
314 typedef typename get_reverse_iterator<C>::type reverse_iterator;
315 typedef typename get_const_reverse_iterator<C>::type const_reverse_iterator;
316 typedef iterator_traits<iterator> nit_traits;
317 typedef iterator_traits<const_iterator> cit_traits;
318 typedef iterator_traits<reverse_iterator> rnit_traits;
319 typedef iterator_traits<const_reverse_iterator> crit_traits;
320
321 using boost::intrusive::detail::is_same;
322 //iterator_category
323 BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename nit_traits::iterator_category>::value));
324 BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename cit_traits::iterator_category>::value));
325 BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename rnit_traits::iterator_category>::value));
326 BOOST_STATIC_ASSERT((is_same<std::forward_iterator_tag, typename crit_traits::iterator_category>::value));
327 //Test dynamic
328 test_iterator_forward_and_compatible(c);
329 }
330
331 template<class C>
test_iterator_bidirectional(C & c)332 void test_iterator_bidirectional(C &c)
333 {
334 typedef typename C::iterator iterator;
335 typedef typename C::const_iterator const_iterator;
336 typedef typename C::reverse_iterator reverse_iterator;
337 typedef typename C::const_reverse_iterator const_reverse_iterator;
338 typedef iterator_traits<iterator> nit_traits;
339 typedef iterator_traits<const_iterator> cit_traits;
340 typedef iterator_traits<reverse_iterator> rnit_traits;
341 typedef iterator_traits<const_reverse_iterator> crit_traits;
342
343 using boost::intrusive::detail::is_same;
344 //iterator_category
345 BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename nit_traits::iterator_category>::value));
346 BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename cit_traits::iterator_category>::value));
347 BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename rnit_traits::iterator_category>::value));
348 BOOST_STATIC_ASSERT((is_same<std::bidirectional_iterator_tag, typename crit_traits::iterator_category>::value));
349 //Test dynamic
350 test_iterator_bidirectional_and_compatible(c);
351 }
352
353 template<class C>
test_iterator_random(C & c)354 void test_iterator_random(C &c)
355 {
356 typedef typename C::iterator iterator;
357 typedef typename C::const_iterator const_iterator;
358 typedef typename C::reverse_iterator reverse_iterator;
359 typedef typename C::const_reverse_iterator const_reverse_iterator;
360 typedef iterator_traits<iterator> nit_traits;
361 typedef iterator_traits<const_iterator> cit_traits;
362 typedef iterator_traits<reverse_iterator> rnit_traits;
363 typedef iterator_traits<const_reverse_iterator> crit_traits;
364
365 using boost::intrusive::detail::is_same;
366 //iterator_category
367 BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename nit_traits::iterator_category>::value));
368 BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename cit_traits::iterator_category>::value));
369 BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename rnit_traits::iterator_category>::value));
370 BOOST_STATIC_ASSERT((is_same<std::random_access_iterator_tag, typename crit_traits::iterator_category>::value));
371 //Test dynamic
372 test_iterator_random_and_compatible(c);
373 }
374
375 }}} //boost::container::test
376