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