1 //////////////////////////////////////////////////////////////////////////////
2 //
3 // (C) Copyright Ion Gaztanaga 2004-2013. 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/container for documentation.
8 //
9 //////////////////////////////////////////////////////////////////////////////
10
11 #include <boost/container/detail/config_begin.hpp>
12 #include <set>
13 #include <boost/container/flat_set.hpp>
14 #include <boost/container/allocator.hpp>
15 #include <boost/container/node_allocator.hpp>
16 #include <boost/container/adaptive_pool.hpp>
17
18 #include "print_container.hpp"
19 #include "dummy_test_allocator.hpp"
20 #include "movable_int.hpp"
21 #include "set_test.hpp"
22 #include "propagate_allocator_test.hpp"
23 #include "emplace_test.hpp"
24 #include "container_common_tests.hpp"
25 #include <vector>
26 #include <boost/container/detail/flat_tree.hpp>
27 #include "../../intrusive/test/iterator_test.hpp"
28
29 using namespace boost::container;
30
31 namespace boost {
32 namespace container {
33
34 //Explicit instantiation to detect compilation errors
35
36 //flat_set
37 template class flat_set
38 < test::movable_and_copyable_int
39 , std::less<test::movable_and_copyable_int>
40 , test::dummy_test_allocator<test::movable_and_copyable_int>
41 >;
42
43 template class flat_set
44 < test::movable_and_copyable_int
45 , std::less<test::movable_and_copyable_int>
46 , test::simple_allocator<test::movable_and_copyable_int>
47 >;
48
49 template class flat_set
50 < test::movable_and_copyable_int
51 , std::less<test::movable_and_copyable_int>
52 , std::allocator<test::movable_and_copyable_int>
53 >;
54
55 template class flat_set
56 < test::movable_and_copyable_int
57 , std::less<test::movable_and_copyable_int>
58 , allocator<test::movable_and_copyable_int>
59 >;
60
61 template class flat_set
62 < test::movable_and_copyable_int
63 , std::less<test::movable_and_copyable_int>
64 , adaptive_pool<test::movable_and_copyable_int>
65 >;
66
67 template class flat_set
68 < test::movable_and_copyable_int
69 , std::less<test::movable_and_copyable_int>
70 , node_allocator<test::movable_and_copyable_int>
71 >;
72
73 //flat_multiset
74 template class flat_multiset
75 < test::movable_and_copyable_int
76 , std::less<test::movable_and_copyable_int>
77 , test::dummy_test_allocator<test::movable_and_copyable_int>
78 >;
79
80 template class flat_multiset
81 < test::movable_and_copyable_int
82 , std::less<test::movable_and_copyable_int>
83 , test::simple_allocator<test::movable_and_copyable_int>
84 >;
85
86 template class flat_multiset
87 < test::movable_and_copyable_int
88 , std::less<test::movable_and_copyable_int>
89 , std::allocator<test::movable_and_copyable_int>
90 >;
91
92 template class flat_multiset
93 < test::movable_and_copyable_int
94 , std::less<test::movable_and_copyable_int>
95 , allocator<test::movable_and_copyable_int>
96 >;
97
98 template class flat_multiset
99 < test::movable_and_copyable_int
100 , std::less<test::movable_and_copyable_int>
101 , adaptive_pool<test::movable_and_copyable_int>
102 >;
103
104 template class flat_multiset
105 < test::movable_and_copyable_int
106 , std::less<test::movable_and_copyable_int>
107 , node_allocator<test::movable_and_copyable_int>
108 >;
109
110 namespace container_detail {
111
112 //Instantiate base class as previous instantiations don't instantiate inherited members
113 template class flat_tree
114 < test::movable_and_copyable_int
115 , test::movable_and_copyable_int
116 , identity<test::movable_and_copyable_int>
117 , std::less<test::movable_and_copyable_int>
118 , test::dummy_test_allocator<test::movable_and_copyable_int>
119 >;
120
121 template class flat_tree
122 < test::movable_and_copyable_int
123 , test::movable_and_copyable_int
124 , identity<test::movable_and_copyable_int>
125 , std::less<test::movable_and_copyable_int>
126 , test::simple_allocator<test::movable_and_copyable_int>
127 >;
128
129 template class flat_tree
130 < test::movable_and_copyable_int
131 , test::movable_and_copyable_int
132 , identity<test::movable_and_copyable_int>
133 , std::less<test::movable_and_copyable_int>
134 , std::allocator<test::movable_and_copyable_int>
135 >;
136
137 template class flat_tree
138 < test::movable_and_copyable_int
139 , test::movable_and_copyable_int
140 , identity<test::movable_and_copyable_int>
141 , std::less<test::movable_and_copyable_int>
142 , allocator<test::movable_and_copyable_int>
143 >;
144
145 template class flat_tree
146 < test::movable_and_copyable_int
147 , test::movable_and_copyable_int
148 , identity<test::movable_and_copyable_int>
149 , std::less<test::movable_and_copyable_int>
150 , adaptive_pool<test::movable_and_copyable_int>
151 >;
152
153 template class flat_tree
154 < test::movable_and_copyable_int
155 , test::movable_and_copyable_int
156 , identity<test::movable_and_copyable_int>
157 , std::less<test::movable_and_copyable_int>
158 , node_allocator<test::movable_and_copyable_int>
159 >;
160
161 } //container_detail {
162
163 //As flat container iterators are typedefs for vector::[const_]iterator,
164 //no need to explicit instantiate them
165
166 }} //boost::container
167
168 //Test recursive structures
169 class recursive_flat_set
170 {
171 public:
recursive_flat_set(const recursive_flat_set & c)172 recursive_flat_set(const recursive_flat_set &c)
173 : id_(c.id_), flat_set_(c.flat_set_)
174 {}
175
operator =(const recursive_flat_set & c)176 recursive_flat_set & operator =(const recursive_flat_set &c)
177 {
178 id_ = c.id_;
179 flat_set_= c.flat_set_;
180 return *this;
181 }
182 int id_;
183 flat_set<recursive_flat_set> flat_set_;
184 flat_set<recursive_flat_set>::iterator it_;
185 flat_set<recursive_flat_set>::const_iterator cit_;
186 flat_set<recursive_flat_set>::reverse_iterator rit_;
187 flat_set<recursive_flat_set>::const_reverse_iterator crit_;
188
operator <(const recursive_flat_set & a,const recursive_flat_set & b)189 friend bool operator< (const recursive_flat_set &a, const recursive_flat_set &b)
190 { return a.id_ < b.id_; }
191 };
192
193
194 //Test recursive structures
195 class recursive_flat_multiset
196 {
197 public:
recursive_flat_multiset(const recursive_flat_multiset & c)198 recursive_flat_multiset(const recursive_flat_multiset &c)
199 : id_(c.id_), flat_multiset_(c.flat_multiset_)
200 {}
201
operator =(const recursive_flat_multiset & c)202 recursive_flat_multiset & operator =(const recursive_flat_multiset &c)
203 {
204 id_ = c.id_;
205 flat_multiset_= c.flat_multiset_;
206 return *this;
207 }
208 int id_;
209 flat_multiset<recursive_flat_multiset> flat_multiset_;
210 flat_multiset<recursive_flat_multiset>::iterator it_;
211 flat_multiset<recursive_flat_multiset>::const_iterator cit_;
212 flat_multiset<recursive_flat_multiset>::reverse_iterator rit_;
213 flat_multiset<recursive_flat_multiset>::const_reverse_iterator crit_;
214
operator <(const recursive_flat_multiset & a,const recursive_flat_multiset & b)215 friend bool operator< (const recursive_flat_multiset &a, const recursive_flat_multiset &b)
216 { return a.id_ < b.id_; }
217 };
218
219
220 template<class C>
test_move()221 void test_move()
222 {
223 //Now test move semantics
224 C original;
225 C move_ctor(boost::move(original));
226 C move_assign;
227 move_assign = boost::move(move_ctor);
228 move_assign.swap(original);
229 }
230
231 namespace boost{
232 namespace container {
233 namespace test{
234
flat_tree_ordered_insertion_test()235 bool flat_tree_ordered_insertion_test()
236 {
237 using namespace boost::container;
238 const std::size_t NumElements = 100;
239
240 //Ordered insertion multiset
241 {
242 std::multiset<int> int_mset;
243 for(std::size_t i = 0; i != NumElements; ++i){
244 int_mset.insert(static_cast<int>(i));
245 }
246 //Construction insertion
247 flat_multiset<int> fmset(ordered_range, int_mset.begin(), int_mset.end());
248 if(!CheckEqualContainers(int_mset, fmset))
249 return false;
250 //Insertion when empty
251 fmset.clear();
252 fmset.insert(ordered_range, int_mset.begin(), int_mset.end());
253 if(!CheckEqualContainers(int_mset, fmset))
254 return false;
255 //Re-insertion
256 fmset.insert(ordered_range, int_mset.begin(), int_mset.end());
257 std::multiset<int> int_mset2(int_mset);
258 int_mset2.insert(int_mset.begin(), int_mset.end());
259 if(!CheckEqualContainers(int_mset2, fmset))
260 return false;
261 //Re-re-insertion
262 fmset.insert(ordered_range, int_mset2.begin(), int_mset2.end());
263 std::multiset<int> int_mset4(int_mset2);
264 int_mset4.insert(int_mset2.begin(), int_mset2.end());
265 if(!CheckEqualContainers(int_mset4, fmset))
266 return false;
267 //Re-re-insertion of even
268 std::multiset<int> int_even_mset;
269 for(std::size_t i = 0; i < NumElements; i+=2){
270 int_mset.insert(static_cast<int>(i));
271 }
272 fmset.insert(ordered_range, int_even_mset.begin(), int_even_mset.end());
273 int_mset4.insert(int_even_mset.begin(), int_even_mset.end());
274 if(!CheckEqualContainers(int_mset4, fmset))
275 return false;
276
277 //Re-re-insertion using in-place merge
278 fmset.reserve(fmset.size() + int_mset2.size());
279 fmset.insert(ordered_range, int_mset2.begin(), int_mset2.end());
280 std::multiset<int> int_mset5(int_mset2);
281 int_mset4.insert(int_mset5.begin(), int_mset5.end());
282 if(!CheckEqualContainers(int_mset4, fmset))
283 return false;
284 //Re-re-insertion of even
285 std::multiset<int> int_even_mset2;
286 for(std::size_t i = 0; i < NumElements; i+=2){
287 int_even_mset2.insert(static_cast<int>(i));
288 }
289 fmset.reserve(fmset.size() + int_even_mset2.size());
290 fmset.insert(ordered_range, int_even_mset2.begin(), int_even_mset2.end());
291 int_mset4.insert(int_even_mset2.begin(), int_even_mset2.end());
292 if(!CheckEqualContainers(int_mset4, fmset))
293 return false;
294 }
295
296 //Ordered insertion set
297 {
298 std::set<int> int_set;
299 for(std::size_t i = 0; i != NumElements; ++i){
300 int_set.insert(static_cast<int>(i));
301 }
302 //Construction insertion
303 flat_set<int> fset(ordered_unique_range, int_set.begin(), int_set.end());
304 if(!CheckEqualContainers(int_set, fset))
305 return false;
306 //Insertion when empty
307 fset.clear();
308 fset.insert(ordered_unique_range, int_set.begin(), int_set.end());
309 if(!CheckEqualContainers(int_set, fset))
310 return false;
311 //Re-insertion
312 fset.insert(ordered_unique_range, int_set.begin(), int_set.end());
313 std::set<int> int_set2(int_set);
314 int_set2.insert(int_set.begin(), int_set.end());
315 if(!CheckEqualContainers(int_set2, fset))
316 return false;
317 //Re-re-insertion
318 fset.insert(ordered_unique_range, int_set2.begin(), int_set2.end());
319 std::set<int> int_set4(int_set2);
320 int_set4.insert(int_set2.begin(), int_set2.end());
321 if(!CheckEqualContainers(int_set4, fset))
322 return false;
323 //Re-re-insertion of even
324 std::set<int> int_even_set;
325 for(std::size_t i = 0; i < NumElements; i+=2){
326 int_even_set.insert(static_cast<int>(i));
327 }
328 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
329 int_set4.insert(int_even_set.begin(), int_even_set.end());
330 if(!CheckEqualContainers(int_set4, fset))
331 return false;
332 //Partial Re-re-insertion of even
333 int_even_set.clear();
334 for(std::size_t i = 0; i < NumElements; i+=4){
335 int_even_set.insert(static_cast<int>(i));
336 }
337 fset.clear();
338 int_set4.clear();
339 //insert 0,4,8,12...
340 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
341 int_set4.insert(int_even_set.begin(), int_even_set.end());
342 if(!CheckEqualContainers(int_set4, fset))
343 return false;
344 for(std::size_t i = 2; i < NumElements; i+=4){
345 int_even_set.insert(static_cast<int>(i));
346 }
347 //insert 0,2,4,6,8,10,12...
348 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
349 int_set4.insert(int_even_set.begin(), int_even_set.end());
350 if(!CheckEqualContainers(int_set4, fset))
351 return false;
352 int_even_set.clear();
353 for(std::size_t i = 0; i < NumElements; i+=8){
354 int_even_set.insert(static_cast<int>(i));
355 }
356 fset.clear();
357 int_set4.clear();
358 //insert 0,8,16...
359 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
360 int_set4.insert(int_even_set.begin(), int_even_set.end());
361 if(!CheckEqualContainers(int_set4, fset))
362 return false;
363 for(std::size_t i = 0; i < NumElements; i+=2){
364 int_even_set.insert(static_cast<int>(i));
365 }
366 //insert 0,2,4,6,8,10,12...
367 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
368 int_set4.insert(int_even_set.begin(), int_even_set.end());
369 if(!CheckEqualContainers(int_set4, fset))
370 return false;
371
372
373 int_even_set.clear();
374 for(std::size_t i = 0; i < NumElements; i+=8){
375 int_even_set.insert(static_cast<int>(i));
376 int_even_set.insert(static_cast<int>(i+2));
377 }
378 int_even_set.insert(static_cast<int>(NumElements-2));
379 fset.clear();
380 int_set4.clear();
381 //insert 0,2,8,10...
382 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
383 int_set4.insert(int_even_set.begin(), int_even_set.end());
384 if(!CheckEqualContainers(int_set4, fset))
385 return false;
386 for(std::size_t i = 0; i < NumElements; i+=2){
387 int_even_set.insert(static_cast<int>(i));
388 }
389 //insert 0,2,4,6,8,10,12...
390 fset.insert(ordered_unique_range, int_even_set.begin(), int_even_set.end());
391 int_set4.insert(int_even_set.begin(), int_even_set.end());
392 if(!CheckEqualContainers(int_set4, fset))
393 return false;
394 }
395
396 return true;
397 }
398
399 }}}
400
401
402 template<class VoidAllocator>
403 struct GetAllocatorSet
404 {
405 template<class ValueType>
406 struct apply
407 {
408 typedef flat_set < ValueType
409 , std::less<ValueType>
410 , typename allocator_traits<VoidAllocator>
411 ::template portable_rebind_alloc<ValueType>::type
412 > set_type;
413
414 typedef flat_multiset < ValueType
415 , std::less<ValueType>
416 , typename allocator_traits<VoidAllocator>
417 ::template portable_rebind_alloc<ValueType>::type
418 > multiset_type;
419 };
420 };
421
422 template<class VoidAllocator>
test_set_variants()423 int test_set_variants()
424 {
425 typedef typename GetAllocatorSet<VoidAllocator>::template apply<int>::set_type MySet;
426 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::movable_int>::set_type MyMoveSet;
427 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::movable_and_copyable_int>::set_type MyCopyMoveSet;
428 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::copyable_int>::set_type MyCopySet;
429
430 typedef typename GetAllocatorSet<VoidAllocator>::template apply<int>::multiset_type MyMultiSet;
431 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::movable_int>::multiset_type MyMoveMultiSet;
432 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::movable_and_copyable_int>::multiset_type MyCopyMoveMultiSet;
433 typedef typename GetAllocatorSet<VoidAllocator>::template apply<test::copyable_int>::multiset_type MyCopyMultiSet;
434
435 typedef std::set<int> MyStdSet;
436 typedef std::multiset<int> MyStdMultiSet;
437
438 if (0 != test::set_test<
439 MySet
440 ,MyStdSet
441 ,MyMultiSet
442 ,MyStdMultiSet>()){
443 std::cout << "Error in set_test<MyBoostSet>" << std::endl;
444 return 1;
445 }
446
447 if (0 != test::set_test<
448 MyMoveSet
449 ,MyStdSet
450 ,MyMoveMultiSet
451 ,MyStdMultiSet>()){
452 std::cout << "Error in set_test<MyBoostSet>" << std::endl;
453 return 1;
454 }
455
456 if (0 != test::set_test<
457 MyCopyMoveSet
458 ,MyStdSet
459 ,MyCopyMoveMultiSet
460 ,MyStdMultiSet>()){
461 std::cout << "Error in set_test<MyBoostSet>" << std::endl;
462 return 1;
463 }
464
465 if (0 != test::set_test<
466 MyCopySet
467 ,MyStdSet
468 ,MyCopyMultiSet
469 ,MyStdMultiSet>()){
470 std::cout << "Error in set_test<MyBoostSet>" << std::endl;
471 return 1;
472 }
473
474 return 0;
475 }
476
477
478 template<typename FlatSetType>
test_support_for_initialization_list_for()479 bool test_support_for_initialization_list_for()
480 {
481 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
482 const std::initializer_list<int> il
483 = {1, 2};
484
485 const FlatSetType expected(il.begin(), il.end());
486 {
487 const FlatSetType sil = il;
488 if (sil != expected)
489 return false;
490
491 const FlatSetType sil_ordered(ordered_unique_range, il);
492 if(sil_ordered != expected)
493 return false;
494
495 FlatSetType sil_assign = {99};
496 sil_assign = il;
497 if(sil_assign != expected)
498 return false;
499 }
500 {
501 FlatSetType sil;
502 sil.insert(il);
503 if(sil != expected)
504 return false;
505 }
506 return true;
507 #endif
508 return true;
509 }
510
511 struct boost_container_flat_set;
512 struct boost_container_flat_multiset;
513
514 namespace boost {
515 namespace container {
516 namespace test {
517
518 template<>
519 struct alloc_propagate_base<boost_container_flat_set>
520 {
521 template <class T, class Allocator>
522 struct apply
523 {
524 typedef boost::container::flat_set<T, std::less<T>, Allocator> type;
525 };
526 };
527
528 template<>
529 struct alloc_propagate_base<boost_container_flat_multiset>
530 {
531 template <class T, class Allocator>
532 struct apply
533 {
534 typedef boost::container::flat_multiset<T, std::less<T>, Allocator> type;
535 };
536 };
537
538 }}} //boost::container::test
539
main()540 int main()
541 {
542 using namespace boost::container::test;
543
544 //Allocator argument container
545 {
546 flat_set<int> set_((flat_set<int>::allocator_type()));
547 flat_multiset<int> multiset_((flat_multiset<int>::allocator_type()));
548 }
549 //Now test move semantics
550 {
551 test_move<flat_set<recursive_flat_set> >();
552 test_move<flat_multiset<recursive_flat_multiset> >();
553 }
554 //Now test nth/index_of
555 {
556 flat_set<int> set;
557 flat_multiset<int> mset;
558
559 set.insert(0);
560 set.insert(1);
561 set.insert(2);
562 mset.insert(0);
563 mset.insert(1);
564 mset.insert(2);
565 if(!boost::container::test::test_nth_index_of(set))
566 return 1;
567 if(!boost::container::test::test_nth_index_of(mset))
568 return 1;
569 }
570
571 ////////////////////////////////////
572 // Ordered insertion test
573 ////////////////////////////////////
574 if(!flat_tree_ordered_insertion_test()){
575 return 1;
576 }
577
578 ////////////////////////////////////
579 // Testing allocator implementations
580 ////////////////////////////////////
581 // std::allocator
582 if(test_set_variants< std::allocator<void> >()){
583 std::cerr << "test_set_variants< std::allocator<void> > failed" << std::endl;
584 return 1;
585 }
586 // boost::container::allocator
587 if(test_set_variants< allocator<void> >()){
588 std::cerr << "test_set_variants< allocator<void> > failed" << std::endl;
589 return 1;
590 }
591 // boost::container::node_allocator
592 if(test_set_variants< node_allocator<void> >()){
593 std::cerr << "test_set_variants< node_allocator<void> > failed" << std::endl;
594 return 1;
595 }
596 // boost::container::adaptive_pool
597 if(test_set_variants< adaptive_pool<void> >()){
598 std::cerr << "test_set_variants< adaptive_pool<void> > failed" << std::endl;
599 return 1;
600 }
601
602 ////////////////////////////////////
603 // Emplace testing
604 ////////////////////////////////////
605 const test::EmplaceOptions SetOptions = (test::EmplaceOptions)(test::EMPLACE_HINT | test::EMPLACE_ASSOC);
606
607 if(!boost::container::test::test_emplace<flat_set<test::EmplaceInt>, SetOptions>())
608 return 1;
609 if(!boost::container::test::test_emplace<flat_multiset<test::EmplaceInt>, SetOptions>())
610 return 1;
611
612 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<flat_set<int> >())
613 return 1;
614
615 if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<flat_multiset<int> >())
616 return 1;
617
618 ////////////////////////////////////
619 // Allocator propagation testing
620 ////////////////////////////////////
621 if(!boost::container::test::test_propagate_allocator<boost_container_flat_set>())
622 return 1;
623
624 if(!boost::container::test::test_propagate_allocator<boost_container_flat_multiset>())
625 return 1;
626
627 ////////////////////////////////////
628 // Iterator testing
629 ////////////////////////////////////
630 {
631 typedef boost::container::flat_set<int> cont_int;
632 cont_int a; a.insert(0); a.insert(1); a.insert(2);
633 boost::intrusive::test::test_iterator_random< cont_int >(a);
634 if(boost::report_errors() != 0) {
635 return 1;
636 }
637 }
638 {
639 typedef boost::container::flat_multiset<int> cont_int;
640 cont_int a; a.insert(0); a.insert(1); a.insert(2);
641 boost::intrusive::test::test_iterator_random< cont_int >(a);
642 if(boost::report_errors() != 0) {
643 return 1;
644 }
645 }
646
647 return 0;
648 }
649
650 #include <boost/container/detail/config_end.hpp>
651
652