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
  16 #include "print_container.hpp"
  17 #include "dummy_test_allocator.hpp"
  18 #include "movable_int.hpp"
  19 #include "map_test.hpp"
  20 #include "propagate_allocator_test.hpp"
  21 #include "container_common_tests.hpp"
  22 #include "emplace_test.hpp"
  23 #include "../../intrusive/test/iterator_test.hpp"
  24
  25 #include <vector>
  26 #include <map>
  27
  28
  29 using namespace boost::container;
  30
  31 namespace boost {
  32 namespace container {
  33
  34 //Explicit instantiation to detect compilation errors
  35
  36 //flat_map
  37
  38 template class flat_map
  39    < test::movable_and_copyable_int
  40    , test::movable_and_copyable_int
  41    , std::less<test::movable_and_copyable_int>
  42    , test::simple_allocator
  43       < std::pair<test::movable_and_copyable_int, test::movable_and_copyable_int> >
  44    >;
  45
  46 template class flat_map
  47    < test::movable_and_copyable_int
  48    , test::movable_and_copyable_int
  49    , std::less<test::movable_and_copyable_int>
  50    , std::allocator
  51       < std::pair<test::movable_and_copyable_int, test::movable_and_copyable_int> >
  52    >;
  53
  54 template class flat_map
  55    < test::movable_and_copyable_int
  56    , test::movable_and_copyable_int
  57    , std::less<test::movable_and_copyable_int>
  58    , allocator
  59       < std::pair<test::movable_and_copyable_int, test::movable_and_copyable_int> >
  60    >;
  61
  62 //flat_multimap
  63 template class flat_multimap
  64    < test::movable_and_copyable_int
  65    , test::movable_and_copyable_int
  66    , std::less<test::movable_and_copyable_int>
  67    , test::simple_allocator
  68       < std::pair<test::movable_and_copyable_int, test::movable_and_copyable_int> >
  69    >;
  70
  71 //As flat container iterators are typedefs for vector::[const_]iterator,
  72 //no need to explicit instantiate them
  73
  74 }} //boost::container
  75
  76
  77 class recursive_flat_map
  78 {
  79    public:
  80    recursive_flat_map(const recursive_flat_map &c)
  81       : id_(c.id_), map_(c.map_)
  82    {}
  83
  84    recursive_flat_map & operator =(const recursive_flat_map &c)
  85    {
  86       id_ = c.id_;
  87       map_= c.map_;
  88       return *this;
  89    }
  90
  91    int id_;
  92    flat_map<recursive_flat_map, recursive_flat_map> map_;
  93    flat_map<recursive_flat_map, recursive_flat_map>::iterator it_;
  94    flat_map<recursive_flat_map, recursive_flat_map>::const_iterator cit_;
  95    flat_map<recursive_flat_map, recursive_flat_map>::reverse_iterator rit_;
  96    flat_map<recursive_flat_map, recursive_flat_map>::const_reverse_iterator crit_;
  97
  98    friend bool operator< (const recursive_flat_map &a, const recursive_flat_map &b)
  99    {  return a.id_ < b.id_;   }
 100 };
 101
 102
 103 class recursive_flat_multimap
 104 {
 105 public:
 106    recursive_flat_multimap(const recursive_flat_multimap &c)
 107       : id_(c.id_), map_(c.map_)
 108    {}
 109
 110    recursive_flat_multimap & operator =(const recursive_flat_multimap &c)
 111    {
 112       id_ = c.id_;
 113       map_= c.map_;
 114       return *this;
 115    }
 116    int id_;
 117    flat_multimap<recursive_flat_multimap, recursive_flat_multimap> map_;
 118    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::iterator it_;
 119    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::const_iterator cit_;
 120    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::reverse_iterator rit_;
 121    flat_multimap<recursive_flat_multimap, recursive_flat_multimap>::const_reverse_iterator crit_;
 122
 123    friend bool operator< (const recursive_flat_multimap &a, const recursive_flat_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    C move_ctor(boost::move(original));
 133    C move_assign;
 134    move_assign = boost::move(move_ctor);
 135    move_assign.swap(original);
 136 }
 137
 138
 139 namespace boost{
 140 namespace container {
 141 namespace test{
 142
 143 bool flat_tree_ordered_insertion_test()
 144 {
 145    using namespace boost::container;
 146    const std::size_t NumElements = 100;
 147
 148    //Ordered insertion multimap
 149    {
 150       std::multimap<int, int> int_mmap;
 151       for(std::size_t i = 0; i != NumElements; ++i){
 152          int_mmap.insert(std::multimap<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 153       }
 154       //Construction insertion
 155       flat_multimap<int, int> fmmap(ordered_range, int_mmap.begin(), int_mmap.end());
 156       if(!CheckEqualContainers(int_mmap, fmmap))
 157          return false;
 158       //Insertion when empty
 159       fmmap.clear();
 160       fmmap.insert(ordered_range, int_mmap.begin(), int_mmap.end());
 161       if(!CheckEqualContainers(int_mmap, fmmap))
 162          return false;
 163       //Re-insertion
 164       fmmap.insert(ordered_range, int_mmap.begin(), int_mmap.end());
 165       std::multimap<int, int> int_mmap2(int_mmap);
 166       int_mmap2.insert(int_mmap.begin(), int_mmap.end());
 167       if(!CheckEqualContainers(int_mmap2, fmmap))
 168          return false;
 169       //Re-re-insertion
 170       fmmap.insert(ordered_range, int_mmap2.begin(), int_mmap2.end());
 171       std::multimap<int, int> int_mmap4(int_mmap2);
 172       int_mmap4.insert(int_mmap2.begin(), int_mmap2.end());
 173       if(!CheckEqualContainers(int_mmap4, fmmap))
 174          return false;
 175       //Re-re-insertion of even
 176       std::multimap<int, int> int_even_mmap;
 177       for(std::size_t i = 0; i < NumElements; i+=2){
 178          int_mmap.insert(std::multimap<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 179       }
 180       fmmap.insert(ordered_range, int_even_mmap.begin(), int_even_mmap.end());
 181       int_mmap4.insert(int_even_mmap.begin(), int_even_mmap.end());
 182       if(!CheckEqualContainers(int_mmap4, fmmap))
 183          return false;
 184    }
 185
 186    //Ordered insertion map
 187    {
 188       std::map<int, int> int_map;
 189       for(std::size_t i = 0; i != NumElements; ++i){
 190          int_map.insert(std::map<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 191       }
 192       //Construction insertion
 193       flat_map<int, int> fmap(ordered_unique_range, int_map.begin(), int_map.end());
 194       if(!CheckEqualContainers(int_map, fmap))
 195          return false;
 196       //Insertion when empty
 197       fmap.clear();
 198       fmap.insert(ordered_unique_range, int_map.begin(), int_map.end());
 199       if(!CheckEqualContainers(int_map, fmap))
 200          return false;
 201       //Re-insertion
 202       fmap.insert(ordered_unique_range, int_map.begin(), int_map.end());
 203       std::map<int, int> int_map2(int_map);
 204       int_map2.insert(int_map.begin(), int_map.end());
 205       if(!CheckEqualContainers(int_map2, fmap))
 206          return false;
 207       //Re-re-insertion
 208       fmap.insert(ordered_unique_range, int_map2.begin(), int_map2.end());
 209       std::map<int, int> int_map4(int_map2);
 210       int_map4.insert(int_map2.begin(), int_map2.end());
 211       if(!CheckEqualContainers(int_map4, fmap))
 212          return false;
 213       //Re-re-insertion of even
 214       std::map<int, int> int_even_map;
 215       for(std::size_t i = 0; i < NumElements; i+=2){
 216          int_map.insert(std::map<int, int>::value_type(static_cast<int>(i), static_cast<int>(i)));
 217       }
 218       fmap.insert(ordered_unique_range, int_even_map.begin(), int_even_map.end());
 219       int_map4.insert(int_even_map.begin(), int_even_map.end());
 220       if(!CheckEqualContainers(int_map4, fmap))
 221          return false;
 222    }
 223
 224    return true;
 225 }
 226
 227 }}}
 228
 229
 230 template<class VoidAllocator>
 231 struct GetAllocatorMap
 232 {
 233    template<class ValueType>
 234    struct apply
 235    {
 236       typedef flat_map< ValueType
 237                  , ValueType
 238                  , std::less<ValueType>
 239                  , typename allocator_traits<VoidAllocator>
 240                     ::template portable_rebind_alloc< std::pair<ValueType, ValueType> >::type
 241                  > map_type;
 242
 243       typedef flat_multimap< ValueType
 244                  , ValueType
 245                  , std::less<ValueType>
 246                  , typename allocator_traits<VoidAllocator>
 247                     ::template portable_rebind_alloc< std::pair<ValueType, ValueType> >::type
 248                  > multimap_type;
 249    };
 250 };
 251
 252 struct boost_container_flat_map;
 253 struct boost_container_flat_multimap;
 254
 255 namespace boost { namespace container {   namespace test {
 256
 257 template<>
 258 struct alloc_propagate_base<boost_container_flat_map>
 259 {
 260    template <class T, class Allocator>
 261    struct apply
 262    {
 263       typedef typename boost::container::allocator_traits<Allocator>::
 264          template portable_rebind_alloc<std::pair<T, T> >::type TypeAllocator;
 265       typedef boost::container::flat_map<T, T, std::less<T>, TypeAllocator> type;
 266    };
 267 };
 268
 269 template<>
 270 struct alloc_propagate_base<boost_container_flat_multimap>
 271 {
 272    template <class T, class Allocator>
 273    struct apply
 274    {
 275       typedef typename boost::container::allocator_traits<Allocator>::
 276          template portable_rebind_alloc<std::pair<T, T> >::type TypeAllocator;
 277       typedef boost::container::flat_multimap<T, T, std::less<T>, TypeAllocator> type;
 278    };
 279 };
 280
 281 template <class Key, class T, class Compare, class Allocator>
 282 struct get_real_stored_allocator<flat_map<Key, T, Compare, Allocator> >
 283 {
 284    typedef typename flat_map<Key, T, Compare, Allocator>::impl_stored_allocator_type type;
 285 };
 286
 287 template <class Key, class T, class Compare, class Allocator>
 288 struct get_real_stored_allocator<flat_multimap<Key, T, Compare, Allocator> >
 289 {
 290    typedef typename flat_multimap<Key, T, Compare, Allocator>::impl_stored_allocator_type type;
 291 };
 292
 293 }}}   //namespace boost::container::test
 294
 295 template<class VoidAllocator>
 296 int test_map_variants()
 297 {
 298    typedef typename GetAllocatorMap<VoidAllocator>::template apply<int>::map_type MyMap;
 299    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::movable_int>::map_type MyMoveMap;
 300    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::movable_and_copyable_int>::map_type MyCopyMoveMap;
 301    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::copyable_int>::map_type MyCopyMap;
 302
 303    typedef typename GetAllocatorMap<VoidAllocator>::template apply<int>::multimap_type MyMultiMap;
 304    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::movable_int>::multimap_type MyMoveMultiMap;
 305    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::movable_and_copyable_int>::multimap_type MyCopyMoveMultiMap;
 306    typedef typename GetAllocatorMap<VoidAllocator>::template apply<test::copyable_int>::multimap_type MyCopyMultiMap;
 307
 308    typedef std::map<int, int>                                     MyStdMap;
 309    typedef std::multimap<int, int>                                MyStdMultiMap;
 310
 311    if (0 != test::map_test<
 312                   MyMap
 313                   ,MyStdMap
 314                   ,MyMultiMap
 315                   ,MyStdMultiMap>()){
 316       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 317       return 1;
 318    }
 319
 320    if (0 != test::map_test<
 321                   MyMoveMap
 322                   ,MyStdMap
 323                   ,MyMoveMultiMap
 324                   ,MyStdMultiMap>()){
 325       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 326       return 1;
 327    }
 328
 329    if (0 != test::map_test<
 330                   MyCopyMoveMap
 331                   ,MyStdMap
 332                   ,MyCopyMoveMultiMap
 333                   ,MyStdMultiMap>()){
 334       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 335       return 1;
 336    }
 337
 338    if (0 != test::map_test<
 339                   MyCopyMap
 340                   ,MyStdMap
 341                   ,MyCopyMultiMap
 342                   ,MyStdMultiMap>()){
 343       std::cout << "Error in map_test<MyBoostMap>" << std::endl;
 344       return 1;
 345    }
 346
 347    return 0;
 348 }
 349
 350 int main()
 351 {
 352    using namespace boost::container::test;
 353
 354    //Allocator argument container
 355    {
 356       flat_map<int, int> map_((flat_map<int, int>::allocator_type()));
 357       flat_multimap<int, int> multimap_((flat_multimap<int, int>::allocator_type()));
 358    }
 359    //Now test move semantics
 360    {
 361       test_move<flat_map<recursive_flat_map, recursive_flat_map> >();
 362       test_move<flat_multimap<recursive_flat_multimap, recursive_flat_multimap> >();
 363    }
 364    //Now test nth/index_of
 365    {
 366       flat_map<int, int> map;
 367       flat_multimap<int, int> mmap;
 368
 369       map.insert(std::pair<int, int>(0, 0));
 370       map.insert(std::pair<int, int>(1, 0));
 371       map.insert(std::pair<int, int>(2, 0));
 372       mmap.insert(std::pair<int, int>(0, 0));
 373       mmap.insert(std::pair<int, int>(1, 0));
 374       mmap.insert(std::pair<int, int>(2, 0));
 375       if(!boost::container::test::test_nth_index_of(map))
 376          return 1;
 377       if(!boost::container::test::test_nth_index_of(mmap))
 378          return 1;
 379    }
 380
 381    ////////////////////////////////////
 382    //    Ordered insertion test
 383    ////////////////////////////////////
 384    if(!flat_tree_ordered_insertion_test()){
 385       return 1;
 386    }
 387
 388    ////////////////////////////////////
 389    //    Testing allocator implementations
 390    ////////////////////////////////////
 391    //       std::allocator
 392    if(test_map_variants< std::allocator<void> >()){
 393       std::cerr << "test_map_variants< std::allocator<void> > failed" << std::endl;
 394       return 1;
 395    }
 396    //       boost::container::allocator
 397    if(test_map_variants< allocator<void> >()){
 398       std::cerr << "test_map_variants< allocator<void> > failed" << std::endl;
 399       return 1;
 400    }
 401
 402    if(!boost::container::test::test_map_support_for_initialization_list_for<flat_map<int, int> >())
 403       return 1;
 404
 405    if (!boost::container::test::test_map_support_for_initialization_list_for<flat_multimap<int, int> >())
 406       return 1;
 407
 408    ////////////////////////////////////
 409    //    Emplace testing
 410    ////////////////////////////////////
 411    const test::EmplaceOptions MapOptions = (test::EmplaceOptions)(test::EMPLACE_HINT_PAIR | test::EMPLACE_ASSOC_PAIR);
 412
 413    if(!boost::container::test::test_emplace<flat_map<test::EmplaceInt, test::EmplaceInt>, MapOptions>())
 414       return 1;
 415    if(!boost::container::test::test_emplace<flat_multimap<test::EmplaceInt, test::EmplaceInt>, MapOptions>())
 416       return 1;
 417
 418    ////////////////////////////////////
 419    //    Allocator propagation testing
 420    ////////////////////////////////////
 421    if(!boost::container::test::test_propagate_allocator<boost_container_flat_map>())
 422       return 1;
 423
 424    if(!boost::container::test::test_propagate_allocator<boost_container_flat_multimap>())
 425       return 1;
 426
 427    ////////////////////////////////////
 428    //    Iterator testing
 429    ////////////////////////////////////
 430    {
 431       typedef boost::container::flat_map<int, int> cont_int;
 432       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));
 433       boost::intrusive::test::test_iterator_random< cont_int >(a);
 434       if(boost::report_errors() != 0) {
 435          return 1;
 436       }
 437    }
 438    {
 439       typedef boost::container::flat_multimap<int, int> cont_int;
 440       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));
 441       boost::intrusive::test::test_iterator_random< cont_int >(a);
 442       if(boost::report_errors() != 0) {
 443          return 1;
 444       }
 445    }
 446
 447    return 0;
 448 }
 449
 450 #include <boost/container/detail/config_end.hpp>
 451