ceph/src/boost/libs/container/test/flat_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
  11 #include <boost/container/detail/config_begin.hpp>
  12 #include <boost/container/flat_map.hpp>
  13 #include <boost/container/allocator.hpp>
  14 #include <boost/container/detail/flat_tree.hpp>
  15 #include <boost/container/stable_vector.hpp>
  16 #include <boost/container/small_vector.hpp>
  17 #include <boost/container/deque.hpp>
  18 #include <boost/container/static_vector.hpp>
  19 #include <boost/container/detail/container_or_allocator_rebind.hpp>
  20
  21 #include "print_container.hpp"
  22 #include "dummy_test_allocator.hpp"
  23 #include "movable_int.hpp"
  24 #include "map_test.hpp"
  25 #include "propagate_allocator_test.hpp"
  26 #include "container_common_tests.hpp"
  27 #include "emplace_test.hpp"
  28 #include "../../intrusive/test/iterator_test.hpp"
  29
  30 #include <map>
  31
  32
  33 using namespace boost::container;
  34
  35 namespace boost {
  36 namespace container {
  37
  38 //Explicit instantiation to detect compilation errors
  39
  40 //flat_map
  41 typedef std::pair<test::movable_and_copyable_int, test::movable_and_copyable_int> test_pair_t;
  42
  43 template class flat_map
  44    < test::movable_and_copyable_int
  45    , test::movable_and_copyable_int
  46    , std::less<test::movable_and_copyable_int>
  47    , test::simple_allocator< test_pair_t >
  48    >;
  49
  50 template class flat_map
  51    < test::movable_and_copyable_int
  52    , test::movable_and_copyable_int
  53    , std::less<test::movable_and_copyable_int>
  54    , small_vector< test_pair_t, 10, std::allocator< test_pair_t > >
  55    >;
  56
  57 //flat_multimap
  58 template class flat_multimap
  59    < test::movable_and_copyable_int
  60    , test::movable_and_copyable_int
  61    , std::less<test::movable_and_copyable_int>
  62    , stable_vector< test_pair_t, allocator< test_pair_t > >
  63    >;
  64
  65 template class flat_multimap
  66    < test::movable_and_copyable_int
  67    , test::movable_and_copyable_int
  68    , std::less<test::movable_and_copyable_int>
  69    , deque<test_pair_t, test::simple_allocator< test_pair_t > >
  70    >;
  71
  72 template class flat_multimap
  73    < test::movable_and_copyable_int
  74    , test::movable_and_copyable_int
  75    , std::less<test::movable_and_copyable_int>
  76    , static_vector<test_pair_t, 10 >
  77    >;
  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 #if (__cplusplus > 201103L)
  85 #include <vector>
  86
  87 namespace boost{
  88 namespace container{
  89
  90 template class flat_map
  91    < test::movable_and_copyable_int
  92    , test::movable_and_copyable_int
  93    , std::less<test::movable_and_copyable_int>
  94    , std::vector<test_pair_t>
  95 >;
  96
  97 }} //boost::container
  98
  99 #endif
 100
 101 class recursive_flat_map
 102 {
 103    public:
 104    recursive_flat_map(const recursive_flat_map &c)
 105       : id_(c.id_), map_(c.map_)
 106    {}
 107
 108    recursive_flat_map & operator =(const recursive_flat_map &c)
 109    {
 110       id_ = c.id_;
 111       map_= c.map_;
 112       return *this;
 113    }
 114
 115    int id_;
 116    flat_map<recursive_flat_map, recursive_flat_map> map_;
 117    flat_map<recursive_flat_map, recursive_flat_map>::iterator it_;
 118    flat_map<recursive_flat_map, recursive_flat_map>::const_iterator cit_;
 119    flat_map<recursive_flat_map, recursive_flat_map>::reverse_iterator rit_;
 120    flat_map<recursive_flat_map, recursive_flat_map>::const_reverse_iterator crit_;
 121
 122    friend bool operator< (const recursive_flat_map &a, const recursive_flat_map &b)
 123    {  return a.id_ < b.id_;   }
 124 };
 125
 126
 127 class recursive_flat_multimap
 128 {
 129 public:
 130    recursive_flat_multimap(const recursive_flat_multimap &c)
 131       : id_(c.id_), map_(c.map_)
 132    {}
 133
 134    recursive_flat_multimap & operator =(const recursive_flat_multimap &c)
 135    {
 136       id_ = c.id_;
 137       map_= c.map_;
 138       return *this;
 139    }
 140    int id_;
 141    flat_multimap<recursive_flat_multimap, recursive_flat_multimap> map_;
 142    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::iterator it_;
 143    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::const_iterator cit_;
 144    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::reverse_iterator rit_;
 145    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::const_reverse_iterator crit_;
 146
 147    friend bool operator< (const recursive_flat_multimap &a, const recursive_flat_multimap &b)
 148    {  return a.id_ < b.id_;   }
 149 };
 150
 151 template<class C>
 152 void test_move()
 153 {
 154    //Now test move semantics
 155    C original;
 156    C move_ctor(boost::move(original));
 157    C move_assign;
 158    move_assign = boost::move(move_ctor);
 159    move_assign.swap(original);
 160 }
 161
 162
 163 namespace boost{
 164 namespace container {
 165 namespace test{
 166
 167 bool flat_tree_ordered_insertion_test()
 168 {
 169    using namespace boost::container;
 170    const std::size_t NumElements = 100;
 171
 172    //Ordered insertion multimap
 173    {
 174       std::multimap<int, int> int_mmap;
 175       for(std::size_t i = 0; i != NumElements; ++i){
 176          int_mmap.insert(std::multimap<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 177       }
 178       //Construction insertion
 179       flat_multimap<int, int> fmmap(ordered_range, int_mmap.begin(), int_mmap.end());
 180       if(!CheckEqualContainers(int_mmap, fmmap))
 181          return false;
 182       //Insertion when empty
 183       fmmap.clear();
 184       fmmap.insert(ordered_range, int_mmap.begin(), int_mmap.end());
 185       if(!CheckEqualContainers(int_mmap, fmmap))
 186          return false;
 187       //Re-insertion
 188       fmmap.insert(ordered_range, int_mmap.begin(), int_mmap.end());
 189       std::multimap<int, int> int_mmap2(int_mmap);
 190       int_mmap2.insert(int_mmap.begin(), int_mmap.end());
 191       if(!CheckEqualContainers(int_mmap2, fmmap))
 192          return false;
 193       //Re-re-insertion
 194       fmmap.insert(ordered_range, int_mmap2.begin(), int_mmap2.end());
 195       std::multimap<int, int> int_mmap4(int_mmap2);
 196       int_mmap4.insert(int_mmap2.begin(), int_mmap2.end());
 197       if(!CheckEqualContainers(int_mmap4, fmmap))
 198          return false;
 199       //Re-re-insertion of even
 200       std::multimap<int, int> int_even_mmap;
 201       for(std::size_t i = 0; i < NumElements; i+=2){
 202          int_mmap.insert(std::multimap<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 203       }
 204       fmmap.insert(ordered_range, int_even_mmap.begin(), int_even_mmap.end());
 205       int_mmap4.insert(int_even_mmap.begin(), int_even_mmap.end());
 206       if(!CheckEqualContainers(int_mmap4, fmmap))
 207          return false;
 208    }
 209
 210    //Ordered insertion map
 211    {
 212       std::map<int, int> int_map;
 213       for(std::size_t i = 0; i != NumElements; ++i){
 214          int_map.insert(std::map<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 215       }
 216       //Construction insertion
 217       flat_map<int, int> fmap(ordered_unique_range, int_map.begin(), int_map.end());
 218       if(!CheckEqualContainers(int_map, fmap))
 219          return false;
 220       //Insertion when empty
 221       fmap.clear();
 222       fmap.insert(ordered_unique_range, int_map.begin(), int_map.end());
 223       if(!CheckEqualContainers(int_map, fmap))
 224          return false;
 225       //Re-insertion
 226       fmap.insert(ordered_unique_range, int_map.begin(), int_map.end());
 227       std::map<int, int> int_map2(int_map);
 228       int_map2.insert(int_map.begin(), int_map.end());
 229       if(!CheckEqualContainers(int_map2, fmap))
 230          return false;
 231       //Re-re-insertion
 232       fmap.insert(ordered_unique_range, int_map2.begin(), int_map2.end());
 233       std::map<int, int> int_map4(int_map2);
 234       int_map4.insert(int_map2.begin(), int_map2.end());
 235       if(!CheckEqualContainers(int_map4, fmap))
 236          return false;
 237       //Re-re-insertion of even
 238       std::map<int, int> int_even_map;
 239       for(std::size_t i = 0; i < NumElements; i+=2){
 240          int_map.insert(std::map<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 241       }
 242       fmap.insert(ordered_unique_range, int_even_map.begin(), int_even_map.end());
 243       int_map4.insert(int_even_map.begin(), int_even_map.end());
 244       if(!CheckEqualContainers(int_map4, fmap))
 245          return false;
 246    }
 247
 248    return true;
 249 }
 250
 251 template< class RandomIt >
 252 void random_shuffle( RandomIt first, RandomIt last )
 253 {
 254    typedef typename boost::container::iterator_traits<RandomIt>::difference_type difference_type;
 255    difference_type n = last - first;
 256    for (difference_type i = n-1; i > 0; --i) {
 257       difference_type j = std::rand() % (i+1);
 258       if(j != i) {
 259          boost::adl_move_swap(first[i], first[j]);
 260       }
 261    }
 262 }
 263
 264 bool flat_tree_extract_adopt_test()
 265 {
 266    using namespace boost::container;
 267    const std::size_t NumElements = 100;
 268
 269    //extract/adopt map
 270    {
 271       //Construction insertion
 272       flat_map<int, int> fmap;
 273
 274       for(std::size_t i = 0; i != NumElements; ++i){
 275          fmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 276       }
 277
 278       flat_map<int, int> fmap_copy(fmap);
 279       flat_map<int, int>::sequence_type seq(fmap.extract_sequence());
 280       if(!fmap.empty())
 281          return false;
 282       if(!CheckEqualContainers(seq, fmap_copy))
 283          return false;
 284
 285       seq.insert(seq.end(), fmap_copy.begin(), fmap_copy.end());
 286       boost::container::test::random_shuffle(seq.begin(), seq.end());
 287       fmap.adopt_sequence(boost::move(seq));
 288       if(!CheckEqualContainers(fmap, fmap_copy))
 289          return false;
 290    }
 291
 292    //extract/adopt map, ordered_unique_range
 293    {
 294       //Construction insertion
 295       flat_map<int, int> fmap;
 296
 297       for(std::size_t i = 0; i != NumElements; ++i){
 298          fmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 299       }
 300
 301       flat_map<int, int> fmap_copy(fmap);
 302       flat_map<int, int>::sequence_type seq(fmap.extract_sequence());
 303       if(!fmap.empty())
 304          return false;
 305       if(!CheckEqualContainers(seq, fmap_copy))
 306          return false;
 307
 308       fmap.adopt_sequence(ordered_unique_range, boost::move(seq));
 309       if(!CheckEqualContainers(fmap, fmap_copy))
 310          return false;
 311    }
 312
 313    //extract/adopt multimap
 314    {
 315       //Construction insertion
 316       flat_multimap<int, int> fmmap;
 317
 318       for(std::size_t i = 0; i != NumElements; ++i){
 319          fmmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 320          fmmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 321       }
 322
 323       flat_multimap<int, int> fmmap_copy(fmmap);
 324       flat_multimap<int, int>::sequence_type seq(fmmap.extract_sequence());
 325       if(!fmmap.empty())
 326          return false;
 327       if(!CheckEqualContainers(seq, fmmap_copy))
 328          return false;
 329
 330       boost::container::test::random_shuffle(seq.begin(), seq.end());
 331       fmmap.adopt_sequence(boost::move(seq));
 332       if(!CheckEqualContainers(fmmap, fmmap_copy))
 333          return false;
 334    }
 335
 336    //extract/adopt multimap, ordered_range
 337    {
 338       //Construction insertion
 339       flat_multimap<int, int> fmmap;
 340
 341       for(std::size_t i = 0; i != NumElements; ++i){
 342          fmmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 343          fmmap.emplace(static_cast<int>(i), -static_cast<int>(i));
 344       }
 345
 346       flat_multimap<int, int> fmmap_copy(fmmap);
 347       flat_multimap<int, int>::sequence_type seq(fmmap.extract_sequence());
 348       if(!fmmap.empty())
 349          return false;
 350       if(!CheckEqualContainers(seq, fmmap_copy))
 351          return false;
 352
 353       fmmap.adopt_sequence(ordered_range, boost::move(seq));
 354       if(!CheckEqualContainers(fmmap, fmmap_copy))
 355          return false;
 356    }
 357
 358    return true;
 359 }
 360
 361 }}}
 362
 363 template<class VoidAllocatorOrContainer>
 364 struct GetMapContainer
 365 {
 366    template<class ValueType>
 367    struct apply
 368    {
 369       typedef std::pair<ValueType, ValueType> type_t;
 370       typedef flat_map< ValueType
 371                  , ValueType
 372                  , std::less<ValueType>
 373                  , typename boost::container::container_detail::container_or_allocator_rebind<VoidAllocatorOrContainer, type_t>::type
 374                  > map_type;
 375
 376       typedef flat_multimap< ValueType
 377                  , ValueType
 378                  , std::less<ValueType>
 379                  , typename boost::container::container_detail::container_or_allocator_rebind<VoidAllocatorOrContainer, type_t>::type
 380                  > multimap_type;
 381    };
 382 };
 383
 384 struct boost_container_flat_map;
 385 struct boost_container_flat_multimap;
 386
 387 namespace boost { namespace container {   namespace test {
 388
 389 template<>
 390 struct alloc_propagate_base<boost_container_flat_map>
 391 {
 392    template <class T, class Allocator>
 393    struct apply
 394    {
 395       typedef typename boost::container::allocator_traits<Allocator>::
 396          template portable_rebind_alloc<std::pair<T, T> >::type TypeAllocator;
 397       typedef boost::container::flat_map<T, T, std::less<T>, TypeAllocator> type;
 398    };
 399 };
 400
 401 template<>
 402 struct alloc_propagate_base<boost_container_flat_multimap>
 403 {
 404    template <class T, class Allocator>
 405    struct apply
 406    {
 407       typedef typename boost::container::allocator_traits<Allocator>::
 408          template portable_rebind_alloc<std::pair<T, T> >::type TypeAllocator;
 409       typedef boost::container::flat_multimap<T, T, std::less<T>, TypeAllocator> type;
 410    };
 411 };
 412
 413 template <class Key, class T, class Compare, class Allocator>
 414 struct get_real_stored_allocator<flat_map<Key, T, Compare, Allocator> >
 415 {
 416    typedef typename flat_map<Key, T, Compare, Allocator>::impl_stored_allocator_type type;
 417 };
 418
 419 template <class Key, class T, class Compare, class Allocator>
 420 struct get_real_stored_allocator<flat_multimap<Key, T, Compare, Allocator> >
 421 {
 422    typedef typename flat_multimap<Key, T, Compare, Allocator>::impl_stored_allocator_type type;
 423 };
 424
 425 }}}   //namespace boost::container::test
 426
 427 template<class VoidAllocatorOrContainer>
 428 int test_map_variants()
 429 {
 430    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<int>::map_type MyMap;
 431    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::movable_int>::map_type MyMoveMap;
 432    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::movable_and_copyable_int>::map_type MyCopyMoveMap;
 433    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::copyable_int>::map_type MyCopyMap;
 434
 435    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<int>::multimap_type MyMultiMap;
 436    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::movable_int>::multimap_type MyMoveMultiMap;
 437    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::movable_and_copyable_int>::multimap_type MyCopyMoveMultiMap;
 438    typedef typename GetMapContainer<VoidAllocatorOrContainer>::template apply<test::copyable_int>::multimap_type MyCopyMultiMap;
 439
 440    typedef std::map<int, int>                                     MyStdMap;
 441    typedef std::multimap<int, int>                                MyStdMultiMap;
 442
 443    if (0 != test::map_test<
 444                   MyMap
 445                   ,MyStdMap
 446                   ,MyMultiMap
 447                   ,MyStdMultiMap>()){
 448       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 449       return 1;
 450    }
 451
 452    if (0 != test::map_test<
 453                   MyMoveMap
 454                   ,MyStdMap
 455                   ,MyMoveMultiMap
 456                   ,MyStdMultiMap>()){
 457       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 458       return 1;
 459    }
 460
 461    if (0 != test::map_test<
 462                   MyCopyMoveMap
 463                   ,MyStdMap
 464                   ,MyCopyMoveMultiMap
 465                   ,MyStdMultiMap>()){
 466       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 467       return 1;
 468    }
 469
 470    if (0 != test::map_test<
 471                   MyCopyMap
 472                   ,MyStdMap
 473                   ,MyCopyMultiMap
 474                   ,MyStdMultiMap>()){
 475       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 476       return 1;
 477    }
 478
 479    return 0;
 480 }
 481
 482 int main()
 483 {
 484    using namespace boost::container::test;
 485
 486    //Allocator argument container
 487    {
 488       flat_map<int, int> map_((flat_map<int, int>::allocator_type()));
 489       flat_multimap<int, int> multimap_((flat_multimap<int, int>::allocator_type()));
 490    }
 491    //Now test move semantics
 492    {
 493       test_move<flat_map<recursive_flat_map, recursive_flat_map> >();
 494       test_move<flat_multimap<recursive_flat_multimap, recursive_flat_multimap> >();
 495    }
 496    //Now test nth/index_of
 497    {
 498       flat_map<int, int> map;
 499       flat_multimap<int, int> mmap;
 500
 501       map.insert(std::pair<int, int>(0, 0));
 502       map.insert(std::pair<int, int>(1, 0));
 503       map.insert(std::pair<int, int>(2, 0));
 504       mmap.insert(std::pair<int, int>(0, 0));
 505       mmap.insert(std::pair<int, int>(1, 0));
 506       mmap.insert(std::pair<int, int>(2, 0));
 507       if(!boost::container::test::test_nth_index_of(map))
 508          return 1;
 509       if(!boost::container::test::test_nth_index_of(mmap))
 510          return 1;
 511    }
 512
 513    ////////////////////////////////////
 514    //    Ordered insertion test
 515    ////////////////////////////////////
 516    if(!flat_tree_ordered_insertion_test()){
 517       return 1;
 518    }
 519
 520    ////////////////////////////////////
 521    //    Extract/Adopt test
 522    ////////////////////////////////////
 523    if(!flat_tree_extract_adopt_test()){
 524       return 1;
 525    }
 526
 527    if (!boost::container::test::instantiate_constructors<flat_map<int, int>, flat_multimap<int, int> >())
 528       return 1;
 529
 530    ////////////////////////////////////
 531    //    Testing allocator implementations
 532    ////////////////////////////////////
 533    //       std::allocator
 534    if(test_map_variants< std::allocator<void> >()){
 535       std::cerr << "test_map_variants< std::allocator<void> > failed" << std::endl;
 536       return 1;
 537    }
 538    //       boost::container::allocator
 539    if(test_map_variants< allocator<void> >()){
 540       std::cerr << "test_map_variants< allocator<void> > failed" << std::endl;
 541       return 1;
 542    }
 543
 544    if(!boost::container::test::test_map_support_for_initialization_list_for<flat_map<int, int> >())
 545       return 1;
 546
 547    if (!boost::container::test::test_map_support_for_initialization_list_for<flat_multimap<int, int> >())
 548       return 1;
 549
 550    ////////////////////////////////////
 551    //    Emplace testing
 552    ////////////////////////////////////
 553    const test::EmplaceOptions MapOptions = (test::EmplaceOptions)(test::EMPLACE_HINT_PAIR | test::EMPLACE_ASSOC_PAIR);
 554
 555    if(!boost::container::test::test_emplace<flat_map<test::EmplaceInt, test::EmplaceInt>, MapOptions>())
 556       return 1;
 557    if(!boost::container::test::test_emplace<flat_multimap<test::EmplaceInt, test::EmplaceInt>, MapOptions>())
 558       return 1;
 559
 560    ////////////////////////////////////
 561    //    Allocator propagation testing
 562    ////////////////////////////////////
 563    if(!boost::container::test::test_propagate_allocator<boost_container_flat_map>())
 564       return 1;
 565
 566    if(!boost::container::test::test_propagate_allocator<boost_container_flat_multimap>())
 567       return 1;
 568
 569    ////////////////////////////////////
 570    //    Iterator testing
 571    ////////////////////////////////////
 572    {
 573       typedef boost::container::flat_map<int, int> cont_int;
 574       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));
 575       boost::intrusive::test::test_iterator_random< cont_int >(a);
 576       if(boost::report_errors() != 0) {
 577          return 1;
 578       }
 579    }
 580    {
 581       typedef boost::container::flat_multimap<int, int> cont_int;
 582       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));
 583       boost::intrusive::test::test_iterator_random< cont_int >(a);
 584       if(boost::report_errors() != 0) {
 585          return 1;
 586       }
 587    }
 588
 589    return 0;
 590 }
 591
 592 #include <boost/container/detail/config_end.hpp>
 593