ceph/src/boost/libs/container/test/deque_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 <memory>
  11 #include <deque>
  12 #include <iostream>
  13 #include <list>
  14
  15 #include <boost/container/deque.hpp>
  16 #include <boost/container/allocator.hpp>
  17
  18 #include "print_container.hpp"
  19 #include "check_equal_containers.hpp"
  20 #include "dummy_test_allocator.hpp"
  21 #include "movable_int.hpp"
  22 #include <boost/move/utility_core.hpp>
  23 #include <boost/move/iterator.hpp>
  24 #include <boost/container/detail/mpl.hpp>
  25 #include <boost/container/detail/type_traits.hpp>
  26 #include <string>
  27 #include "emplace_test.hpp"
  28 #include "propagate_allocator_test.hpp"
  29 #include "vector_test.hpp"
  30 #include "default_init_test.hpp"
  31 #include <boost/core/no_exceptions_support.hpp>
  32 #include "../../intrusive/test/iterator_test.hpp"
  33
  34 using namespace boost::container;
  35
  36 //Function to check if both sets are equal
  37 template<class V1, class V2>
  38 bool deque_copyable_only(V1 &, V2 &, dtl::false_type)
  39 {
  40    return true;
  41 }
  42
  43 //Function to check if both sets are equal
  44 template<class V1, class V2>
  45 bool deque_copyable_only(V1 &cntdeque, V2 &stddeque, dtl::true_type)
  46 {
  47    typedef typename V1::value_type IntType;
  48    std::size_t size = cntdeque.size();
  49    stddeque.insert(stddeque.end(), 50u, 1);
  50    cntdeque.insert(cntdeque.end(), 50u, IntType(1));
  51    if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  52    {
  53       IntType move_me(1);
  54       stddeque.insert(stddeque.begin()+std::ptrdiff_t(size)/2, 50u, 1);
  55       cntdeque.insert(cntdeque.begin()+std::ptrdiff_t(size/2), 50u, boost::move(move_me));
  56       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  57    }
  58    {
  59       IntType move_me(2);
  60       cntdeque.assign(cntdeque.size()/2, boost::move(move_me));
  61       stddeque.assign(stddeque.size()/2, 2);
  62       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  63    }
  64    {
  65       IntType move_me(1);
  66       stddeque.clear();
  67       cntdeque.clear();
  68       stddeque.insert(stddeque.begin(), 50u, 1);
  69       cntdeque.insert(cntdeque.begin(), 50u, boost::move(move_me));
  70       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  71       stddeque.insert(stddeque.begin()+20, 50u, 1);
  72       cntdeque.insert(cntdeque.begin()+20, 50u, boost::move(move_me));
  73       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  74       stddeque.insert(stddeque.begin()+20, 20u, 1);
  75       cntdeque.insert(cntdeque.begin()+20, 20u, boost::move(move_me));
  76       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  77    }
  78    {
  79       IntType move_me(1);
  80       stddeque.clear();
  81       cntdeque.clear();
  82       stddeque.insert(stddeque.end(), 50u, 1);
  83       cntdeque.insert(cntdeque.end(), 50u, boost::move(move_me));
  84       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  85       stddeque.insert(stddeque.end()-20, 50u, 1);
  86       cntdeque.insert(cntdeque.end()-20, 50u, boost::move(move_me));
  87       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  88       stddeque.insert(stddeque.end()-20, 20u, 1);
  89       cntdeque.insert(cntdeque.end()-20, 20u, boost::move(move_me));
  90       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
  91    }
  92
  93    return true;
  94 }
  95
  96 //Test recursive structures
  97 class recursive_deque
  98 {
  99 public:
 100
 101    recursive_deque (const recursive_deque &x)
 102       : deque_(x.deque_)
 103    {}
 104
 105    recursive_deque & operator=(const recursive_deque &x)
 106    {  this->deque_ = x.deque_;   return *this; }
 107
 108    int id_;
 109    deque<recursive_deque> deque_;
 110    deque<recursive_deque>::iterator it_;
 111    deque<recursive_deque>::const_iterator cit_;
 112    deque<recursive_deque>::reverse_iterator rit_;
 113    deque<recursive_deque>::const_reverse_iterator crit_;
 114 };
 115
 116 template<class IntType>
 117 bool do_test()
 118 {
 119    //Test for recursive types
 120    {
 121       deque<recursive_deque> recursive_deque_deque;
 122    }
 123
 124    {
 125       //Now test move semantics
 126       deque<recursive_deque> original;
 127       deque<recursive_deque> move_ctor(boost::move(original));
 128       deque<recursive_deque> move_assign;
 129       move_assign = boost::move(move_ctor);
 130       move_assign.swap(original);
 131    }
 132
 133    //Alias deque types
 134    typedef deque<IntType>  MyCntDeque;
 135    typedef std::deque<int> MyStdDeque;
 136    const int max = 100;
 137    {
 138       ::boost::movelib::unique_ptr<MyCntDeque> const pcntdeque = ::boost::movelib::make_unique<MyCntDeque>();
 139       ::boost::movelib::unique_ptr<MyStdDeque> const pstddeque = ::boost::movelib::make_unique<MyStdDeque>();
 140       MyCntDeque &cntdeque = *pcntdeque;
 141       MyStdDeque &stddeque = *pstddeque;
 142       for(int i = 0; i < max*100; ++i){
 143          IntType move_me(i);
 144          cntdeque.insert(cntdeque.end(), boost::move(move_me));
 145          stddeque.insert(stddeque.end(), i);
 146       }
 147       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 148
 149       cntdeque.clear();
 150       stddeque.clear();
 151
 152       for(int i = 0; i < max*100; ++i){
 153          IntType move_me(i);
 154          cntdeque.push_back(boost::move(move_me));
 155          stddeque.push_back(i);
 156       }
 157       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 158
 159       cntdeque.clear();
 160       stddeque.clear();
 161
 162       for(int i = 0; i < max*100; ++i){
 163          IntType move_me(i);
 164          cntdeque.push_front(boost::move(move_me));
 165          stddeque.push_front(i);
 166       }
 167       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 168
 169       typename MyCntDeque::iterator it;
 170       typename MyCntDeque::const_iterator cit = it;
 171       (void)cit;
 172
 173       cntdeque.erase(cntdeque.begin()++);
 174       stddeque.erase(stddeque.begin()++);
 175       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 176
 177       cntdeque.erase(cntdeque.begin());
 178       stddeque.erase(stddeque.begin());
 179       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 180
 181       {
 182          //Initialize values
 183          IntType aux_vect[50];
 184          for(int i = 0; i < 50; ++i){
 185             IntType move_me (-1);
 186             aux_vect[i] = boost::move(move_me);
 187          }
 188          int aux_vect2[50];
 189          for(int i = 0; i < 50; ++i){
 190             aux_vect2[i] = -1;
 191          }
 192
 193          cntdeque.insert(cntdeque.end()
 194                            ,boost::make_move_iterator(&aux_vect[0])
 195                            ,boost::make_move_iterator(aux_vect + 50));
 196          stddeque.insert(stddeque.end(), aux_vect2, aux_vect2 + 50);
 197          if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 198
 199          for(int i = 0; i < 50; ++i){
 200             IntType move_me (i);
 201             aux_vect[i] = boost::move(move_me);
 202          }
 203          for(int i = 0; i < 50; ++i){
 204             aux_vect2[i] = i;
 205          }
 206
 207          cntdeque.insert(cntdeque.begin()+std::ptrdiff_t(cntdeque.size())
 208                            ,boost::make_move_iterator(&aux_vect[0])
 209                            ,boost::make_move_iterator(aux_vect + 50));
 210          stddeque.insert(stddeque.begin()+std::ptrdiff_t(stddeque.size()), aux_vect2, aux_vect2 + 50);
 211          if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 212
 213          for(int i = 0, j = static_cast<int>(cntdeque.size()); i < j; ++i){
 214             cntdeque.erase(cntdeque.begin());
 215             stddeque.erase(stddeque.begin());
 216          }
 217          if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 218       }
 219       {
 220          IntType aux_vect[50];
 221          for(int i = 0; i < 50; ++i){
 222             IntType move_me(-1);
 223             aux_vect[i] = boost::move(move_me);
 224          }
 225          int aux_vect2[50];
 226          for(int i = 0; i < 50; ++i){
 227             aux_vect2[i] = -1;
 228          }
 229          cntdeque.insert(cntdeque.begin()
 230                            ,boost::make_move_iterator(&aux_vect[0])
 231                            ,boost::make_move_iterator(aux_vect + 50));
 232          stddeque.insert(stddeque.begin(), aux_vect2, aux_vect2 + 50);
 233          if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 234       }
 235
 236       if(!deque_copyable_only(cntdeque, stddeque
 237                      ,dtl::bool_<boost::container::test::is_copyable<IntType>::value>())){
 238          return false;
 239       }
 240
 241       cntdeque.erase(cntdeque.begin());
 242       stddeque.erase(stddeque.begin());
 243
 244       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 245
 246       for(int i = 0; i < max; ++i){
 247          IntType move_me(i);
 248          cntdeque.insert(cntdeque.begin(), boost::move(move_me));
 249          stddeque.insert(stddeque.begin(), i);
 250       }
 251       if(!test::CheckEqualContainers(cntdeque, stddeque)) return false;
 252
 253       //Test insertion from list
 254       {
 255          std::list<int> l(50, int(1));
 256          cntdeque.insert(cntdeque.begin(), l.begin(), l.end());
 257          stddeque.insert(stddeque.begin(), l.begin(), l.end());
 258          if(!test::CheckEqualContainers(cntdeque, stddeque)) return 1;
 259          cntdeque.assign(l.begin(), l.end());
 260          stddeque.assign(l.begin(), l.end());
 261          if(!test::CheckEqualContainers(cntdeque, stddeque)) return 1;
 262       }
 263
 264       cntdeque.resize(100);
 265       stddeque.resize(100);
 266       if(!test::CheckEqualContainers(cntdeque, stddeque)) return 1;
 267
 268       cntdeque.resize(200);
 269       stddeque.resize(200);
 270       if(!test::CheckEqualContainers(cntdeque, stddeque)) return 1;
 271    }
 272
 273 #ifndef BOOST_CONTAINER_NO_CXX17_CTAD
 274    //Check Constructor Template Auto Deduction
 275    {
 276       auto gold = MyStdDeque{ 1, 2, 3 };
 277       auto test = deque(gold.begin(), gold.end());
 278       if(!test::CheckEqualContainers(gold, test)) return false;
 279    }
 280    {
 281       auto gold = MyStdDeque{ 1, 2, 3 };
 282       auto test = deque(gold.begin(), gold.end(), new_allocator<int>());
 283       if(!test::CheckEqualContainers(gold, test)) return false;
 284    }
 285 #endif
 286
 287    std::cout << std::endl << "Test OK!" << std::endl;
 288    return true;
 289 }
 290
 291 template<class VoidAllocator>
 292 struct GetAllocatorCont
 293 {
 294    template<class ValueType>
 295    struct apply
 296    {
 297       typedef deque< ValueType
 298                     , typename allocator_traits<VoidAllocator>
 299                         ::template portable_rebind_alloc<ValueType>::type
 300                     > type;
 301    };
 302 };
 303
 304 template<class VoidAllocator>
 305 int test_cont_variants()
 306 {
 307    typedef typename GetAllocatorCont<VoidAllocator>::template apply<int>::type MyCont;
 308    typedef typename GetAllocatorCont<VoidAllocator>::template apply<test::movable_int>::type MyMoveCont;
 309    typedef typename GetAllocatorCont<VoidAllocator>::template apply<test::movable_and_copyable_int>::type MyCopyMoveCont;
 310    typedef typename GetAllocatorCont<VoidAllocator>::template apply<test::copyable_int>::type MyCopyCont;
 311
 312    if(test::vector_test<MyCont>())
 313       return 1;
 314    if(test::vector_test<MyMoveCont>())
 315       return 1;
 316    if(test::vector_test<MyCopyMoveCont>())
 317       return 1;
 318    if(test::vector_test<MyCopyCont>())
 319       return 1;
 320    return 0;
 321 }
 322
 323 struct boost_container_deque;
 324
 325 namespace boost { namespace container {   namespace test {
 326
 327 template<>
 328 struct alloc_propagate_base<boost_container_deque>
 329 {
 330    template <class T, class Allocator>
 331    struct apply
 332    {
 333       typedef boost::container::deque<T, Allocator> type;
 334    };
 335 };
 336
 337 }}}   //namespace boost::container::test
 338
 339 int main ()
 340 {
 341    if(!do_test<int>())
 342       return 1;
 343
 344    if(!do_test<test::movable_int>())
 345       return 1;
 346
 347    if(!do_test<test::movable_and_copyable_int>())
 348       return 1;
 349
 350    if(!do_test<test::copyable_int>())
 351       return 1;
 352
 353    //Test non-copy-move operations
 354    {
 355       deque<test::non_copymovable_int> d;
 356       d.emplace_back();
 357       d.emplace_front(1);
 358       d.resize(10);
 359       d.resize(1);
 360    }
 361
 362    ////////////////////////////////////
 363    //    Allocator implementations
 364    ////////////////////////////////////
 365    //       std:allocator
 366    if(test_cont_variants< std::allocator<void> >()){
 367       std::cerr << "test_cont_variants< std::allocator<void> > failed" << std::endl;
 368       return 1;
 369    }
 370    //       boost::container::allocator
 371    if(test_cont_variants< allocator<void> >()){
 372       std::cerr << "test_cont_variants< allocator<void> > failed" << std::endl;
 373       return 1;
 374    }
 375    ////////////////////////////////////
 376    //    Default init test
 377    ////////////////////////////////////
 378    if(!test::default_init_test< deque<int, test::default_init_allocator<int> > >()){
 379       std::cerr << "Default init test failed" << std::endl;
 380       return 1;
 381    }
 382
 383    ////////////////////////////////////
 384    //    Emplace testing
 385    ////////////////////////////////////
 386    const test::EmplaceOptions Options = (test::EmplaceOptions)(test::EMPLACE_BACK | test::EMPLACE_FRONT | test::EMPLACE_BEFORE);
 387
 388    if(!boost::container::test::test_emplace
 389       < deque<test::EmplaceInt>, Options>())
 390       return 1;
 391    ////////////////////////////////////
 392    //    Allocator propagation testing
 393    ////////////////////////////////////
 394    if(!boost::container::test::test_propagate_allocator<boost_container_deque>())
 395       return 1;
 396
 397    ////////////////////////////////////
 398    //    Initializer lists testing
 399    ////////////////////////////////////
 400    if(!boost::container::test::test_vector_methods_with_initializer_list_as_argument_for
 401       < boost::container::deque<int> >()) {
 402       return 1;
 403    }
 404
 405    ////////////////////////////////////
 406    //    Iterator testing
 407    ////////////////////////////////////
 408    {
 409       typedef boost::container::deque<int> cont_int;
 410       cont_int a; a.push_back(0); a.push_back(1); a.push_back(2);
 411       boost::intrusive::test::test_iterator_random< cont_int >(a);
 412       if(boost::report_errors() != 0) {
 413          return 1;
 414       }
 415    }
 416
 417    ////////////////////////////////////
 418    //    has_trivial_destructor_after_move testing
 419    ////////////////////////////////////
 420    // default allocator
 421    {
 422       typedef boost::container::deque<int> cont;
 423       typedef cont::allocator_type allocator_type;
 424       typedef boost::container::allocator_traits<allocator_type>::pointer pointer;
 425       BOOST_STATIC_ASSERT_MSG(!(boost::has_trivial_destructor_after_move<cont>::value !=
 426                                 boost::has_trivial_destructor_after_move<allocator_type>::value &&
 427                                 boost::has_trivial_destructor_after_move<pointer>::value)
 428                              , "has_trivial_destructor_after_move(std::allocator) test failed");
 429    }
 430    // std::allocator
 431    {
 432       typedef boost::container::deque<int, std::allocator<int> > cont;
 433       typedef cont::allocator_type allocator_type;
 434       typedef boost::container::allocator_traits<allocator_type>::pointer pointer;
 435       BOOST_STATIC_ASSERT_MSG(!(boost::has_trivial_destructor_after_move<cont>::value !=
 436                                boost::has_trivial_destructor_after_move<allocator_type>::value &&
 437                                boost::has_trivial_destructor_after_move<pointer>::value)
 438                              , "has_trivial_destructor_after_move(std::allocator) test failed");
 439    }
 440
 441    return 0;
 442 }