libs/container/test/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 #include <boost/container/detail/config_begin.hpp>
  11 #include <set>
  12 #include <boost/container/set.hpp>
  13 #include <boost/container/adaptive_pool.hpp>
  14
  15 #include "print_container.hpp"
  16 #include "movable_int.hpp"
  17 #include "dummy_test_allocator.hpp"
  18 #include "set_test.hpp"
  19 #include "propagate_allocator_test.hpp"
  20 #include "emplace_test.hpp"
  21 #include "../../intrusive/test/iterator_test.hpp"
  22
  23 using namespace boost::container;
  24
  25 namespace boost {
  26 namespace container {
  27
  28 //Explicit instantiation to detect compilation errors
  29
  30 //set
  31 template class set
  32    < test::movable_and_copyable_int
  33    , std::less<test::movable_and_copyable_int>
  34    , test::simple_allocator<test::movable_and_copyable_int>
  35    >;
  36
  37 template class set
  38    < test::movable_and_copyable_int
  39    , std::less<test::movable_and_copyable_int>
  40    , adaptive_pool<test::movable_and_copyable_int>
  41    >;
  42
  43 //multiset
  44 template class multiset
  45    < test::movable_and_copyable_int
  46    , std::less<test::movable_and_copyable_int>
  47    , test::simple_allocator<test::movable_and_copyable_int>
  48    >;
  49
  50 template class multiset
  51    < test::movable_and_copyable_int
  52    , std::less<test::movable_and_copyable_int>
  53    , adaptive_pool<test::movable_and_copyable_int>
  54    >;
  55
  56 namespace container_detail {
  57
  58 //Instantiate base class as previous instantiations don't instantiate inherited members
  59 template class tree
  60    < test::movable_and_copyable_int
  61    , identity<test::movable_and_copyable_int>
  62    , std::less<test::movable_and_copyable_int>
  63    , test::simple_allocator<test::movable_and_copyable_int>
  64    , tree_assoc_defaults
  65    >;
  66
  67 template class tree
  68    < test::movable_and_copyable_int
  69    , identity<test::movable_and_copyable_int>
  70    , std::less<test::movable_and_copyable_int>
  71    , std::allocator<test::movable_and_copyable_int>
  72    , tree_assoc_defaults
  73    >;
  74
  75 template class tree
  76    < test::movable_and_copyable_int
  77    , identity<test::movable_and_copyable_int>
  78    , std::less<test::movable_and_copyable_int>
  79    , adaptive_pool<test::movable_and_copyable_int>
  80    , tree_assoc_defaults
  81    >;
  82
  83 }  //container_detail {
  84
  85 }} //boost::container
  86
  87 //Test recursive structures
  88 class recursive_set
  89 {
  90 public:
  91    recursive_set & operator=(const recursive_set &x)
  92    {  id_ = x.id_;  set_ = x.set_; return *this; }
  93
  94    int id_;
  95    set<recursive_set> set_;
  96    set<recursive_set>::iterator it_;
  97    set<recursive_set>::const_iterator cit_;
  98    set<recursive_set>::reverse_iterator rit_;
  99    set<recursive_set>::const_reverse_iterator crit_;
 100
 101    friend bool operator< (const recursive_set &a, const recursive_set &b)
 102    {  return a.id_ < b.id_;   }
 103 };
 104
 105 //Test recursive structures
 106 class recursive_multiset
 107 {
 108    public:
 109    recursive_multiset & operator=(const recursive_multiset &x)
 110    {  id_ = x.id_;  multiset_ = x.multiset_; return *this;  }
 111
 112    int id_;
 113    multiset<recursive_multiset> multiset_;
 114    multiset<recursive_multiset>::iterator it_;
 115    multiset<recursive_multiset>::const_iterator cit_;
 116    multiset<recursive_multiset>::reverse_iterator rit_;
 117    multiset<recursive_multiset>::const_reverse_iterator crit_;
 118
 119    friend bool operator< (const recursive_multiset &a, const recursive_multiset &b)
 120    {  return a.id_ < b.id_;   }
 121 };
 122
 123 template<class C>
 124 void test_move()
 125 {
 126    //Now test move semantics
 127    C original;
 128    original.emplace();
 129    C move_ctor(boost::move(original));
 130    C move_assign;
 131    move_assign.emplace();
 132    move_assign = boost::move(move_ctor);
 133    move_assign.swap(original);
 134 }
 135
 136 bool node_type_test()
 137 {
 138    using namespace boost::container;
 139    {
 140       typedef set<test::movable_int> set_type;
 141       set_type src;
 142       {
 143          test::movable_int mv_1(1), mv_2(2), mv_3(3);
 144          src.emplace(boost::move(mv_1));
 145          src.emplace(boost::move(mv_2));
 146          src.emplace(boost::move(mv_3));
 147       }
 148       if(src.size() != 3)
 149          return false;
 150
 151       set_type dst;
 152       {
 153          test::movable_int mv_3(3);
 154          dst.emplace(boost::move(mv_3));
 155       }
 156
 157       if(dst.size() != 1)
 158          return false;
 159
 160       const test::movable_int mv_1(1);
 161       const test::movable_int mv_2(2);
 162       const test::movable_int mv_3(3);
 163       const test::movable_int mv_33(33);
 164       set_type::insert_return_type r;
 165
 166       r = dst.insert(src.extract(mv_33)); // Key version, try to insert empty node
 167       if(! (r.position == dst.end() && r.inserted == false && r.node.empty()) )
 168          return false;
 169       r = dst.insert(src.extract(src.find(mv_1))); // Iterator version, successful
 170       if(! (r.position == dst.find(mv_1) && r.inserted == true && r.node.empty()) )
 171          return false;
 172       r = dst.insert(dst.begin(), src.extract(mv_2)); // Key type version, successful
 173       if(! (r.position == dst.find(mv_2) && r.inserted == true && r.node.empty()) )
 174          return false;
 175       r = dst.insert(src.extract(mv_3)); // Key type version, unsuccessful
 176
 177       if(!src.empty())
 178          return false;
 179       if(dst.size() != 3)
 180          return false;
 181       if(! (r.position == dst.find(mv_3) && r.inserted == false && r.node.value() == mv_3) )
 182          return false;
 183    }
 184
 185    {
 186       typedef multiset<test::movable_int> multiset_type;
 187       multiset_type src;
 188       {
 189          test::movable_int mv_1(1), mv_2(2), mv_3(3), mv_3bis(3);
 190          src.emplace(boost::move(mv_1));
 191          src.emplace(boost::move(mv_2));
 192          src.emplace(boost::move(mv_3));
 193          src.emplace_hint(src.begin(), boost::move(mv_3bis));
 194       }
 195       if(src.size() != 4)
 196          return false;
 197
 198       multiset_type dst;
 199       {
 200          test::movable_int mv_3(3);
 201          dst.emplace(boost::move(mv_3));
 202       }
 203
 204       if(dst.size() != 1)
 205          return false;
 206
 207       const test::movable_int mv_1(1);
 208       const test::movable_int mv_2(2);
 209       const test::movable_int mv_3(3);
 210       const test::movable_int mv_4(4);
 211       multiset_type::iterator r;
 212
 213       multiset_type::node_type nt(src.extract(mv_3));
 214       r = dst.insert(dst.begin(), boost::move(nt));
 215       if(! (*r == mv_3 && dst.find(mv_3) == r && nt.empty()) )
 216          return false;
 217
 218       nt = src.extract(src.find(mv_1));
 219       r = dst.insert(boost::move(nt)); // Iterator version, successful
 220       if(! (*r == mv_1 && nt.empty()) )
 221          return false;
 222
 223       nt = src.extract(mv_2);
 224       r = dst.insert(boost::move(nt)); // Key type version, successful
 225       if(! (*r == mv_2 && nt.empty()) )
 226          return false;
 227
 228       r = dst.insert(src.extract(mv_3)); // Key type version, successful
 229       if(! (*r == mv_3 && r == --multiset_type::iterator(dst.upper_bound(mv_3)) && nt.empty()) )
 230          return false;
 231
 232       r = dst.insert(src.extract(mv_4)); // Key type version, unsuccessful
 233       if(! (r == dst.end()) )
 234          return false;
 235
 236       if(!src.empty())
 237          return false;
 238       if(dst.size() != 5)
 239          return false;
 240    }
 241    return true;
 242 }
 243
 244 struct boost_container_set;
 245 struct boost_container_multiset;
 246
 247 namespace boost {
 248 namespace container {
 249 namespace test {
 250
 251 template<>
 252 struct alloc_propagate_base<boost_container_set>
 253 {
 254    template <class T, class Allocator>
 255    struct apply
 256    {
 257       typedef boost::container::set<T, std::less<T>, Allocator> type;
 258    };
 259 };
 260
 261 template<>
 262 struct alloc_propagate_base<boost_container_multiset>
 263 {
 264    template <class T, class Allocator>
 265    struct apply
 266    {
 267       typedef boost::container::multiset<T, std::less<T>, Allocator> type;
 268    };
 269 };
 270
 271 }}}   //boost::container::test
 272
 273 template<class VoidAllocator, boost::container::tree_type_enum tree_type_value>
 274 struct GetAllocatorSet
 275 {
 276    template<class ValueType>
 277    struct apply
 278    {
 279       typedef set < ValueType
 280                   , std::less<ValueType>
 281                   , typename allocator_traits<VoidAllocator>
 282                      ::template portable_rebind_alloc<ValueType>::type
 283                   , typename boost::container::tree_assoc_options
 284                         < boost::container::tree_type<tree_type_value>
 285                         >::type
 286                   > set_type;
 287
 288       typedef multiset < ValueType
 289                   , std::less<ValueType>
 290                   , typename allocator_traits<VoidAllocator>
 291                      ::template portable_rebind_alloc<ValueType>::type
 292                   , typename boost::container::tree_assoc_options
 293                         < boost::container::tree_type<tree_type_value>
 294                         >::type
 295                   > multiset_type;
 296    };
 297 };
 298
 299 template<class VoidAllocator, boost::container::tree_type_enum tree_type_value>
 300 int test_set_variants()
 301 {
 302    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<int>::set_type MySet;
 303    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_int>::set_type MyMoveSet;
 304    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_and_copyable_int>::set_type MyCopyMoveSet;
 305    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::copyable_int>::set_type MyCopySet;
 306
 307    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<int>::multiset_type MyMultiSet;
 308    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_int>::multiset_type MyMoveMultiSet;
 309    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::movable_and_copyable_int>::multiset_type MyCopyMoveMultiSet;
 310    typedef typename GetAllocatorSet<VoidAllocator, tree_type_value>::template apply<test::copyable_int>::multiset_type MyCopyMultiSet;
 311
 312    typedef std::set<int>                                          MyStdSet;
 313    typedef std::multiset<int>                                     MyStdMultiSet;
 314
 315    if (0 != test::set_test<
 316                   MySet
 317                   ,MyStdSet
 318                   ,MyMultiSet
 319                   ,MyStdMultiSet>()){
 320       std::cout << "Error in set_test<MyBoostSet>" << std::endl;
 321       return 1;
 322    }
 323
 324    if (0 != test::set_test<
 325                   MyMoveSet
 326                   ,MyStdSet
 327                   ,MyMoveMultiSet
 328                   ,MyStdMultiSet>()){
 329       std::cout << "Error in set_test<MyBoostSet>" << std::endl;
 330       return 1;
 331    }
 332
 333    if (0 != test::set_test<
 334                   MyCopyMoveSet
 335                   ,MyStdSet
 336                   ,MyCopyMoveMultiSet
 337                   ,MyStdMultiSet>()){
 338       std::cout << "Error in set_test<MyBoostSet>" << std::endl;
 339       return 1;
 340    }
 341
 342    if (0 != test::set_test<
 343                   MyCopySet
 344                   ,MyStdSet
 345                   ,MyCopyMultiSet
 346                   ,MyStdMultiSet>()){
 347       std::cout << "Error in set_test<MyBoostSet>" << std::endl;
 348       return 1;
 349    }
 350
 351    return 0;
 352 }
 353
 354 void test_merge_from_different_comparison()
 355 {
 356    set<int> set1;
 357    set<int, std::greater<int> > set2;
 358    set1.merge(set2);
 359 }
 360
 361
 362 int main ()
 363 {
 364    //Recursive container instantiation
 365    {
 366       set<recursive_set> set_;
 367       multiset<recursive_multiset> multiset_;
 368    }
 369    //Allocator argument container
 370    {
 371       set<int> set_((set<int>::allocator_type()));
 372       multiset<int> multiset_((multiset<int>::allocator_type()));
 373    }
 374    //Now test move semantics
 375    {
 376       test_move<set<recursive_set> >();
 377       test_move<multiset<recursive_multiset> >();
 378    }
 379    //Test std::pair value type as tree has workarounds to make old std::pair
 380    //implementations movable that can break things
 381    {
 382       boost::container::set<std::pair<int,int> > s;
 383       std::pair<int,int> p(0, 0);
 384       s.insert(p);
 385       s.emplace(p);
 386    }
 387
 388    test_merge_from_different_comparison();
 389
 390    ////////////////////////////////////
 391    //    Testing allocator implementations
 392    ////////////////////////////////////
 393    //       std:allocator
 394    if(test_set_variants< std::allocator<void>, red_black_tree >()){
 395       std::cerr << "test_set_variants< std::allocator<void> > failed" << std::endl;
 396       return 1;
 397    }
 398    //       boost::container::adaptive_pool
 399    if(test_set_variants< adaptive_pool<void>, red_black_tree>()){
 400       std::cerr << "test_set_variants< adaptive_pool<void> > failed" << std::endl;
 401       return 1;
 402    }
 403
 404    ////////////////////////////////////
 405    //    Tree implementations
 406    ////////////////////////////////////
 407    //       AVL
 408    if(test_set_variants< std::allocator<void>, avl_tree >()){
 409       std::cerr << "test_set_variants< std::allocator<void>, avl_tree > failed" << std::endl;
 410       return 1;
 411    }
 412    //    SCAPEGOAT TREE
 413    if(test_set_variants< std::allocator<void>, scapegoat_tree >()){
 414       std::cerr << "test_set_variants< std::allocator<void>, scapegoat_tree > failed" << std::endl;
 415       return 1;
 416    }
 417    //    SPLAY TREE
 418    if(test_set_variants< std::allocator<void>, splay_tree >()){
 419       std::cerr << "test_set_variants< std::allocator<void>, splay_tree > failed" << std::endl;
 420       return 1;
 421    }
 422
 423    ////////////////////////////////////
 424    //    Emplace testing
 425    ////////////////////////////////////
 426    const test::EmplaceOptions SetOptions = (test::EmplaceOptions)(test::EMPLACE_HINT | test::EMPLACE_ASSOC);
 427    if(!boost::container::test::test_emplace<set<test::EmplaceInt>, SetOptions>())
 428       return 1;
 429    if(!boost::container::test::test_emplace<multiset<test::EmplaceInt>, SetOptions>())
 430       return 1;
 431
 432    ////////////////////////////////////
 433    //    Allocator propagation testing
 434    ////////////////////////////////////
 435    if(!boost::container::test::test_propagate_allocator<boost_container_set>())
 436       return 1;
 437
 438    if(!boost::container::test::test_propagate_allocator<boost_container_multiset>())
 439       return 1;
 440
 441    if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<set<int> >())
 442       return 1;
 443
 444    if (!boost::container::test::test_set_methods_with_initializer_list_as_argument_for<multiset<int> >())
 445       return 1;
 446
 447    ////////////////////////////////////
 448    //    Test optimize_size option
 449    ////////////////////////////////////
 450    //
 451    // set
 452    //
 453    typedef set< int*, std::less<int*>, std::allocator<int*>
 454               , tree_assoc_options< optimize_size<false>, tree_type<red_black_tree> >::type > rbset_size_optimized_no;
 455    typedef set< int*, std::less<int*>, std::allocator<int*>
 456               , tree_assoc_options< optimize_size<true>, tree_type<red_black_tree>  >::type > rbset_size_optimized_yes;
 457    BOOST_STATIC_ASSERT(sizeof(rbset_size_optimized_yes) < sizeof(rbset_size_optimized_no));
 458
 459    typedef set< int*, std::less<int*>, std::allocator<int*>
 460               , tree_assoc_options< optimize_size<false>, tree_type<avl_tree> >::type > avlset_size_optimized_no;
 461    typedef set< int*, std::less<int*>, std::allocator<int*>
 462               , tree_assoc_options< optimize_size<true>, tree_type<avl_tree>  >::type > avlset_size_optimized_yes;
 463    BOOST_STATIC_ASSERT(sizeof(avlset_size_optimized_yes) < sizeof(avlset_size_optimized_no));
 464    //
 465    // multiset
 466    //
 467    typedef multiset< int*, std::less<int*>, std::allocator<int*>
 468                    , tree_assoc_options< optimize_size<false>, tree_type<red_black_tree> >::type > rbmset_size_optimized_no;
 469    typedef multiset< int*, std::less<int*>, std::allocator<int*>
 470                    , tree_assoc_options< optimize_size<true>, tree_type<red_black_tree>  >::type > rbmset_size_optimized_yes;
 471    BOOST_STATIC_ASSERT(sizeof(rbmset_size_optimized_yes) < sizeof(rbmset_size_optimized_no));
 472
 473    typedef multiset< int*, std::less<int*>, std::allocator<int*>
 474                    , tree_assoc_options< optimize_size<false>, tree_type<avl_tree> >::type > avlmset_size_optimized_no;
 475    typedef multiset< int*, std::less<int*>, std::allocator<int*>
 476                    , tree_assoc_options< optimize_size<true>, tree_type<avl_tree>  >::type > avlmset_size_optimized_yes;
 477    BOOST_STATIC_ASSERT(sizeof(avlmset_size_optimized_yes) < sizeof(avlmset_size_optimized_no));
 478
 479    ////////////////////////////////////
 480    //    Iterator testing
 481    ////////////////////////////////////
 482    {
 483       typedef boost::container::set<int> cont_int;
 484       cont_int a; a.insert(0); a.insert(1); a.insert(2);
 485       boost::intrusive::test::test_iterator_bidirectional< cont_int >(a);
 486       if(boost::report_errors() != 0) {
 487          return 1;
 488       }
 489    }
 490    {
 491       typedef boost::container::multiset<int> cont_int;
 492       cont_int a; a.insert(0); a.insert(1); a.insert(2);
 493       boost::intrusive::test::test_iterator_bidirectional< cont_int >(a);
 494       if(boost::report_errors() != 0) {
 495          return 1;
 496       }
 497    }
 498
 499    ////////////////////////////////////
 500    //    Node extraction/insertion testing functions
 501    ////////////////////////////////////
 502    if(!node_type_test())
 503       return 1;
 504
 505    return 0;
 506 }
 507
 508 #include <boost/container/detail/config_end.hpp>