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