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