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