1 /////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2007-2013
4 //
5 // Distributed under the Boost Software License, Version 1.0.
6 // (See accompanying file LICENSE_1_0.txt or copy at
7 // http://www.boost.org/LICENSE_1_0.txt)
8 //
9 // See http://www.boost.org/libs/intrusive for documentation.
10 //
11 /////////////////////////////////////////////////////////////////////////////
12
13 #ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP
14 #define BOOST_INTRUSIVE_TEST_CONTAINER_HPP
15
16 #include <boost/detail/lightweight_test.hpp>
17 #include <boost/intrusive/detail/mpl.hpp>
18 #include <boost/intrusive/detail/simple_disposers.hpp>
19 #include <boost/intrusive/detail/iterator.hpp>
20 #include <boost/move/utility_core.hpp>
21 #include <boost/move/adl_move_swap.hpp>
22 #include <boost/intrusive/detail/mpl.hpp>
23 #include <boost/static_assert.hpp>
24 #include "iterator_test.hpp"
25 #include <cstdlib>
26
27 namespace boost {
28 namespace intrusive {
29 namespace test {
30
31 BOOST_INTRUSIVE_HAS_MEMBER_FUNC_CALLED(is_unordered, hasher)
32
33 template<class Container>
34 struct test_container_typedefs
35 {
36 typedef typename Container::value_type value_type;
37 typedef typename Container::iterator iterator;
38 typedef typename Container::const_iterator const_iterator;
39 typedef typename Container::reference reference;
40 typedef typename Container::const_reference const_reference;
41 typedef typename Container::pointer pointer;
42 typedef typename Container::const_pointer const_pointer;
43 typedef typename Container::difference_type difference_type;
44 typedef typename Container::size_type size_type;
45 typedef typename Container::value_traits value_traits;
46 };
47
48 template< class Container >
test_container(Container & c)49 void test_container( Container & c )
50 {
51 typedef typename Container::const_iterator const_iterator;
52 typedef typename Container::iterator iterator;
53 typedef typename Container::size_type size_type;
54
55 {test_container_typedefs<Container> dummy; (void)dummy;}
56 const size_type num_elem = c.size();
57 BOOST_TEST( c.empty() == (num_elem == 0) );
58 {
59 iterator it(c.begin()), itend(c.end());
60 size_type i;
61 for(i = 0; i < num_elem; ++i){
62 ++it;
63 }
64 BOOST_TEST( it == itend );
65 BOOST_TEST( c.size() == i );
66 }
67
68 //Check iterator conversion
69 BOOST_TEST(const_iterator(c.begin()) == c.cbegin() );
70 {
71 const_iterator it(c.cbegin()), itend(c.cend());
72 size_type i;
73 for(i = 0; i < num_elem; ++i){
74 ++it;
75 }
76 BOOST_TEST( it == itend );
77 BOOST_TEST( c.size() == i );
78 }
79 static_cast<const Container&>(c).check();
80 //Very basic test for comparisons
81 {
82 BOOST_TEST(c == c);
83 BOOST_TEST(!(c != c));
84 BOOST_TEST(!(c < c));
85 BOOST_TEST(c <= c);
86 BOOST_TEST(!(c > c));
87 BOOST_TEST(c >= c);
88 }
89 }
90
91
92 template< class Container, class Data >
test_sequence_container(Container & c,Data & d)93 void test_sequence_container(Container & c, Data & d)
94 {
95 assert( d.size() > 2 );
96 {
97 c.clear();
98
99 BOOST_TEST( c.size() == 0 );
100 BOOST_TEST( c.empty() );
101
102
103 {
104 typename Data::iterator i = d.begin();
105 c.insert( c.begin(), *i );
106 BOOST_TEST( &*c.iterator_to(*c.begin()) == &*i );
107 BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &*i );
108 BOOST_TEST( &*Container::s_iterator_to(*c.begin()) == &*i );
109 BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &*i );
110 c.insert( c.end(), *(++i) );
111 }
112 BOOST_TEST( c.size() == 2 );
113 BOOST_TEST( !c.empty() );
114
115 typename Container::iterator i;
116 i = c.erase( c.begin() );
117
118 BOOST_TEST( c.size() == 1 );
119 BOOST_TEST( !c.empty() );
120
121 i = c.erase( c.begin() );
122
123 BOOST_TEST( c.size() == 0 );
124 BOOST_TEST( c.empty() );
125
126 c.insert( c.begin(), *d.begin() );
127
128 BOOST_TEST( c.size() == 1 );
129 BOOST_TEST( !c.empty() );
130
131 {
132 typename Data::iterator di = d.begin();
133 ++++di;
134 c.insert( c.begin(), *(di) );
135 }
136
137 i = c.erase( c.begin(), c.end() );
138 BOOST_TEST( i == c.end() );
139
140 BOOST_TEST( c.empty() );
141
142 c.insert( c.begin(), *d.begin() );
143
144 BOOST_TEST( c.size() == 1 );
145
146 BOOST_TEST( c.begin() != c.end() );
147
148 i = c.erase_and_dispose( c.begin(), detail::null_disposer() );
149 BOOST_TEST( i == c.begin() );
150
151 c.assign(d.begin(), d.end());
152
153 BOOST_TEST( c.size() == d.size() );
154
155 c.clear();
156
157 BOOST_TEST( c.size() == 0 );
158 BOOST_TEST( c.empty() );
159 }
160 {
161 c.clear();
162 c.insert( c.begin(), d.begin(), d.end() );
163 Container move_c(::boost::move(c));
164 BOOST_TEST( move_c.size() == d.size() );
165 BOOST_TEST( c.empty());
166
167 c = ::boost::move(move_c);
168 BOOST_TEST( c.size() == d.size() );
169 BOOST_TEST( move_c.empty());
170 }
171 }
172
173 template< class Container, class Data >
test_common_unordered_and_associative_container(Container & c,Data & d,boost::intrusive::detail::true_ unordered)174 void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::true_ unordered)
175 {
176 (void)unordered;
177 typedef typename Container::size_type size_type;
178 typedef typename Container::key_of_value key_of_value;
179 typedef typename Container::iterator iterator;
180 typedef typename Container::const_iterator const_iterator;
181
182 assert( d.size() > 2 );
183
184 c.clear();
185 c.insert(d.begin(), d.end());
186
187 {
188 Container const &cc = c;
189 for( typename Data::const_iterator di = d.begin(), de = d.end();
190 di != de; ++di )
191 {
192 BOOST_TEST( cc.find(key_of_value()(*di), c.hash_function(), c.key_eq()) != cc.end() );
193 std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.hash_function(), c.key_eq());
194 BOOST_TEST(rdi.first != rdi.second);
195 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.hash_function(), c.key_eq()));
196 }
197
198 for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
199 {
200 BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
201 std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.hash_function(), c.key_eq());
202 BOOST_TEST(rci.first != rci.second);
203 size_type const sc = c.count(key_of_value()(*ci), c.hash_function(), c.key_eq());
204 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
205 BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.hash_function(), c.key_eq()));
206 ci = rci.second;
207 }
208 BOOST_TEST(c.empty());
209 }
210
211 c.clear();
212 c.insert(d.begin(), d.end());
213
214 typename Data::const_iterator db = d.begin();
215 typename Data::const_iterator da = db++;
216
217 size_type old_size = c.size();
218
219 c.erase(key_of_value()(*da), c.hash_function(), c.key_eq());
220 BOOST_TEST( c.size() == old_size-1 );
221 //This should not eras anyone
222 size_type second_erase = c.erase_and_dispose
223 ( key_of_value()(*da), c.hash_function(), c.key_eq(), detail::null_disposer() );
224 BOOST_TEST( second_erase == 0 );
225
226 BOOST_TEST( c.count(key_of_value()(*da), c.hash_function(), c.key_eq()) == 0 );
227 BOOST_TEST( c.count(key_of_value()(*db), c.hash_function(), c.key_eq()) != 0 );
228
229 BOOST_TEST( c.find(key_of_value()(*da), c.hash_function(), c.key_eq()) == c.end() );
230 BOOST_TEST( c.find(key_of_value()(*db), c.hash_function(), c.key_eq()) != c.end() );
231
232 BOOST_TEST( c.equal_range(key_of_value()(*db), c.hash_function(), c.key_eq()).first != c.end() );
233
234 c.clear();
235
236 BOOST_TEST( c.equal_range(key_of_value()(*da), c.hash_function(), c.key_eq()).first == c.end() );
237
238 //
239 //suggested_upper_bucket_count
240 //
241 //Maximum fallbacks to the highest possible value
242 typename Container::size_type sz = Container::suggested_upper_bucket_count(size_type(-1));
243 BOOST_TEST( sz > size_type(-1)/2 );
244 //In the rest of cases the upper bound is returned
245 sz = Container::suggested_upper_bucket_count(size_type(-1)/2);
246 BOOST_TEST( sz >= size_type(-1)/2 );
247 sz = Container::suggested_upper_bucket_count(size_type(-1)/4);
248 BOOST_TEST( sz >= size_type(-1)/4 );
249 sz = Container::suggested_upper_bucket_count(0);
250 BOOST_TEST( sz > 0 );
251 //
252 //suggested_lower_bucket_count
253 //
254 sz = Container::suggested_lower_bucket_count(size_type(-1));
255 BOOST_TEST( sz <= size_type(-1) );
256 //In the rest of cases the lower bound is returned
257 sz = Container::suggested_lower_bucket_count(size_type(-1)/2);
258 BOOST_TEST( sz <= size_type(-1)/2 );
259 sz = Container::suggested_lower_bucket_count(size_type(-1)/4);
260 BOOST_TEST( sz <= size_type(-1)/4 );
261 //Minimum fallbacks to the lowest possible value
262 sz = Container::suggested_upper_bucket_count(0);
263 BOOST_TEST( sz > 0 );
264 }
265
266 template< class Container, class Data >
test_common_unordered_and_associative_container(Container & c,Data & d,boost::intrusive::detail::false_ unordered)267 void test_common_unordered_and_associative_container(Container & c, Data & d, boost::intrusive::detail::false_ unordered)
268 {
269 (void)unordered;
270 typedef typename Container::size_type size_type;
271 typedef typename Container::key_of_value key_of_value;
272 typedef typename Container::iterator iterator;
273 typedef typename Container::const_iterator const_iterator;
274
275 assert( d.size() > 2 );
276
277 c.clear();
278 typename Container::reference r = *d.begin();
279 c.insert(d.begin(), ++d.begin());
280 BOOST_TEST( &*Container::s_iterator_to(*c.begin()) == &r );
281 BOOST_TEST( &*Container::s_iterator_to(*c.cbegin()) == &r );
282
283 c.clear();
284 c.insert(d.begin(), d.end());
285 {
286 Container const &cc = c;
287 for( typename Data::const_iterator di = d.begin(), de = d.end();
288 di != de; ++di )
289 {
290 BOOST_TEST( cc.find(key_of_value()(*di), c.key_comp()) != cc.end() );
291 std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di), c.key_comp());
292 BOOST_TEST(rdi.first != rdi.second);
293 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di), c.key_comp()));
294 }
295
296 for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
297 {
298 BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
299 std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci), c.key_comp());
300 BOOST_TEST(rci.first != rci.second);
301 size_type const sc = c.count(key_of_value()(*ci), c.key_comp());
302 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
303 BOOST_TEST(sc == c.erase(key_of_value()(*ci), c.key_comp()));
304 ci = rci.second;
305 }
306 BOOST_TEST(c.empty());
307 }
308
309 c.clear();
310 c.insert(d.begin(), d.end());
311
312 typename Data::const_iterator db = d.begin();
313 typename Data::const_iterator da = db++;
314
315 size_type old_size = c.size();
316
317 c.erase(key_of_value()(*da), c.key_comp());
318 BOOST_TEST( c.size() == old_size-1 );
319 //This should not erase any
320 size_type second_erase = c.erase_and_dispose( key_of_value()(*da), c.key_comp(), detail::null_disposer() );
321 BOOST_TEST( second_erase == 0 );
322
323 BOOST_TEST( c.count(key_of_value()(*da), c.key_comp()) == 0 );
324 BOOST_TEST( c.count(key_of_value()(*db), c.key_comp()) != 0 );
325 BOOST_TEST( c.find(key_of_value()(*da), c.key_comp()) == c.end() );
326 BOOST_TEST( c.find(key_of_value()(*db), c.key_comp()) != c.end() );
327 BOOST_TEST( c.equal_range(key_of_value()(*db), c.key_comp()).first != c.end() );
328 c.clear();
329 BOOST_TEST( c.equal_range(key_of_value()(*da), c.key_comp()).first == c.end() );
330 }
331
332 template< class Container, class Data >
test_common_unordered_and_associative_container(Container & c,Data & d)333 void test_common_unordered_and_associative_container(Container & c, Data & d)
334 {
335 typedef typename Container::size_type size_type;
336 typedef typename Container::key_of_value key_of_value;
337 typedef typename Container::iterator iterator;
338 typedef typename Container::const_iterator const_iterator;
339
340 {
341 assert( d.size() > 2 );
342
343 c.clear();
344 typename Container::reference r = *d.begin();
345 c.insert(d.begin(), ++d.begin());
346 BOOST_TEST( &*c.iterator_to(*c.begin()) == &r );
347 BOOST_TEST( &*c.iterator_to(*c.cbegin()) == &r );
348
349 c.clear();
350 c.insert(d.begin(), d.end());
351
352 Container const &cc = c;
353 for( typename Data::const_iterator di = d.begin(), de = d.end();
354 di != de; ++di )
355 {
356 BOOST_TEST( cc.find(key_of_value()(*di)) != cc.end() );
357 std::pair<const_iterator, const_iterator> rdi = cc.equal_range(key_of_value()(*di));
358 BOOST_TEST(rdi.first != rdi.second);
359 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rdi.first, rdi.second)) == cc.count(key_of_value()(*di)));
360 }
361
362 for( iterator ci = c.begin(), ce = c.end(); ci != ce; )
363 {
364 BOOST_TEST( c.find(key_of_value()(*ci)) != c.end() );
365 std::pair<iterator, iterator> rci = c.equal_range(key_of_value()(*ci));
366 BOOST_TEST(rci.first != rci.second);
367 size_type const sc = c.count(key_of_value()(*ci));
368 BOOST_TEST(size_type(boost::intrusive::iterator_distance(rci.first, rci.second)) == sc);
369 BOOST_TEST(sc == c.erase(key_of_value()(*ci)));
370 ci = rci.second;
371 }
372 BOOST_TEST(c.empty());
373 }
374 {
375 c.clear();
376 c.insert(d.begin(), d.end());
377
378 typename Data::const_iterator db = d.begin();
379 typename Data::const_iterator da = db++;
380
381 size_type old_size = c.size();
382
383 c.erase(key_of_value()(*da));
384 BOOST_TEST( c.size() == old_size-1 );
385 //This should erase nothing
386 size_type second_erase = c.erase_and_dispose( key_of_value()(*da), detail::null_disposer() );
387 BOOST_TEST( second_erase == 0 );
388
389 BOOST_TEST( c.count(key_of_value()(*da)) == 0 );
390 BOOST_TEST( c.count(key_of_value()(*db)) != 0 );
391
392 BOOST_TEST( c.find(key_of_value()(*da)) == c.end() );
393 BOOST_TEST( c.find(key_of_value()(*db)) != c.end() );
394
395 BOOST_TEST( c.equal_range(key_of_value()(*db)).first != c.end() );
396 BOOST_TEST( c.equal_range(key_of_value()(*da)).first == c.equal_range(key_of_value()(*da)).second );
397 }
398 {
399 c.clear();
400 c.insert( d.begin(), d.end() );
401 size_type orig_size = c.size();
402 Container move_c(::boost::move(c));
403 BOOST_TEST(orig_size == move_c.size());
404 BOOST_TEST( c.empty());
405 for( typename Data::const_iterator di = d.begin(), de = d.end();
406 di != de; ++di )
407 { BOOST_TEST( move_c.find(key_of_value()(*di)) != move_c.end() ); }
408
409 c = ::boost::move(move_c);
410 for( typename Data::const_iterator di = d.begin(), de = d.end();
411 di != de; ++di )
412 { BOOST_TEST( c.find(key_of_value()(*di)) != c.end() ); }
413 BOOST_TEST( move_c.empty());
414 }
415 typedef detail::bool_<is_unordered<Container>::value> enabler;
416 test_common_unordered_and_associative_container(c, d, enabler());
417 }
418
419 template< class Container, class Data >
test_associative_container_invariants(Container & c,Data & d)420 void test_associative_container_invariants(Container & c, Data & d)
421 {
422 typedef typename Container::const_iterator const_iterator;
423 typedef typename Container::key_of_value key_of_value;
424 for( typename Data::const_iterator di = d.begin(), de = d.end();
425 di != de; ++di)
426 {
427 const_iterator ci = c.find(key_of_value()(*di));
428 BOOST_TEST( ci != c.end() );
429 BOOST_TEST( ! c.value_comp()(*ci, *di) );
430 BOOST_TEST( ! c.key_comp()(key_of_value()(*ci), key_of_value()(*di)) );
431 const_iterator cil = c.lower_bound(key_of_value()(*di));
432 const_iterator ciu = c.upper_bound(key_of_value()(*di));
433 std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
434 BOOST_TEST( cil == er.first );
435 BOOST_TEST( ciu == er.second );
436 if(ciu != c.end()){
437 BOOST_TEST( c.value_comp()(*cil, *ciu) );
438 BOOST_TEST( c.key_comp()(key_of_value()(*cil), key_of_value()(*ciu)) );
439 }
440 if(c.count(key_of_value()(*di)) > 1){
441 const_iterator ci_next = cil; ++ci_next;
442 for( ; ci_next != ciu; ++cil, ++ci_next){
443 BOOST_TEST( !c.value_comp()(*ci_next, *cil) );
444 BOOST_TEST( !c.key_comp()(key_of_value()(*ci_next), key_of_value()(*cil)) );
445 }
446 }
447 }
448 }
449
450 template< class Container, class Data >
test_associative_container(Container & c,Data & d)451 void test_associative_container(Container & c, Data & d)
452 {
453 assert( d.size() > 2 );
454
455 c.clear();
456 c.insert(d.begin(),d.end());
457
458 test_associative_container_invariants(c, d);
459
460 const Container & cr = c;
461
462 test_associative_container_invariants(cr, d);
463 }
464
465 template< class Container, class Data >
test_unordered_associative_container_invariants(Container & c,Data & d)466 void test_unordered_associative_container_invariants(Container & c, Data & d)
467 {
468 typedef typename Container::size_type size_type;
469 typedef typename Container::const_iterator const_iterator;
470 typedef typename Container::key_of_value key_of_value;
471
472 for( typename Data::const_iterator di = d.begin(), de = d.end() ;
473 di != de ; ++di ){
474 const_iterator i = c.find(key_of_value()(*di));
475 size_type nb = c.bucket(key_of_value()(*i));
476 size_type bucket_elem = boost::intrusive::iterator_distance(c.begin(nb), c.end(nb));
477 BOOST_TEST( bucket_elem == c.bucket_size(nb) );
478 BOOST_TEST( &*c.local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
479 BOOST_TEST( &*c.local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
480 BOOST_TEST( &*Container::s_local_iterator_to(*c.find(key_of_value()(*di))) == &*i );
481 BOOST_TEST( &*Container::s_local_iterator_to(*const_cast<const Container &>(c).find(key_of_value()(*di))) == &*i );
482 std::pair<const_iterator, const_iterator> er = c.equal_range(key_of_value()(*di));
483 size_type cnt = boost::intrusive::iterator_distance(er.first, er.second);
484 BOOST_TEST( cnt == c.count(key_of_value()(*di)));
485 if(cnt > 1){
486 const_iterator n = er.first;
487 i = n++;
488 const_iterator e = er.second;
489 for(; n != e; ++i, ++n){
490 BOOST_TEST( c.key_eq()(key_of_value()(*i), key_of_value()(*n)) );
491 BOOST_TEST( (c.hash_function()(key_of_value()(*i))) == (c.hash_function()(key_of_value()(*n))) );
492 }
493 }
494 }
495
496 size_type blen = c.bucket_count();
497 size_type total_objects = 0;
498 for(size_type i = 0; i < blen; ++i){
499 total_objects += c.bucket_size(i);
500 }
501 BOOST_TEST( total_objects == c.size() );
502 }
503
504 template< class Container, class Data >
test_unordered_associative_container(Container & c,Data & d)505 void test_unordered_associative_container(Container & c, Data & d)
506 {
507 c.clear();
508 c.insert( d.begin(), d.end() );
509
510 test_unordered_associative_container_invariants(c, d);
511
512 const Container & cr = c;
513
514 test_unordered_associative_container_invariants(cr, d);
515 }
516
517 template< class Container, class Data >
test_unique_container(Container & c,Data & d)518 void test_unique_container(Container & c, Data & d)
519 {
520 //typedef typename Container::value_type value_type;
521 c.clear();
522 c.insert(d.begin(),d.end());
523 typename Container::size_type old_size = c.size();
524 //value_type v(*d.begin());
525 //c.insert(v);
526 Data d2(1);
527 (&d2.front())->value_ = (&d.front())->value_;
528 c.insert(d2.front());
529 BOOST_TEST( c.size() == old_size );
530 c.clear();
531 }
532
533 template< class Container, class Data >
test_non_unique_container(Container & c,Data & d)534 void test_non_unique_container(Container & c, Data & d)
535 {
536 //typedef typename Container::value_type value_type;
537 c.clear();
538 c.insert(d.begin(),d.end());
539 typename Container::size_type old_size = c.size();
540 //value_type v(*d.begin());
541 //c.insert(v);
542 Data d2(1);
543 (&d2.front())->value_ = (&d.front())->value_;
544 c.insert(d2.front());
545 BOOST_TEST( c.size() == (old_size+1) );
546 c.clear();
547 }
548
549 template< class Container, class Data >
test_maybe_unique_container(Container & c,Data & d,detail::false_)550 void test_maybe_unique_container(Container & c, Data & d, detail::false_)//is_unique
551 { test_unique_container(c, d); }
552
553 template< class Container, class Data >
test_maybe_unique_container(Container & c,Data & d,detail::true_)554 void test_maybe_unique_container(Container & c, Data & d, detail::true_)//!is_unique
555 { test_non_unique_container(c, d); }
556
557 template< class RandomIt >
random_shuffle(RandomIt first,RandomIt last)558 void random_shuffle( RandomIt first, RandomIt last )
559 {
560 typedef typename boost::intrusive::iterator_traits<RandomIt>::difference_type difference_type;
561 difference_type n = last - first;
562 for (difference_type i = n-1; i > 0; --i) {
563 difference_type j = std::rand() % (i+1);
564 if(j != i) {
565 boost::adl_move_swap(first[i], first[j]);
566 }
567 }
568 }
569
570 }}}
571
572 #endif //#ifndef BOOST_INTRUSIVE_TEST_CONTAINER_HPP
573