ceph/src/boost/libs/container/test/flat_set_test.cpp

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