ceph/src/boost/libs/multi_index/test/test_modifiers.cpp

   1 /* Boost.MultiIndex test for modifier memfuns.
   2  *
   3  * Copyright 2003-2017 Joaquin M Lopez Munoz.
   4  * Distributed under the Boost Software License, Version 1.0.
   5  * (See accompanying file LICENSE_1_0.txt or copy at
   6  * http://www.boost.org/LICENSE_1_0.txt)
   7  *
   8  * See http://www.boost.org/libs/multi_index for library home page.
   9  */
  10
  11 #include "test_modifiers.hpp"
  12
  13 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  14 #include <boost/detail/lightweight_test.hpp>
  15 #include <boost/enable_shared_from_this.hpp>
  16 #include <boost/iterator/iterator_facade.hpp>
  17 #include <boost/move/core.hpp>
  18 #include <boost/next_prior.hpp>
  19 #include <boost/shared_ptr.hpp>
  20 #include <iterator>
  21 #include <vector>
  22 #include "pre_multi_index.hpp"
  23 #include "employee.hpp"
  24
  25 using namespace boost::multi_index;
  26
  27 struct non_copyable_int
  28 {
  29   explicit non_copyable_int(int n_):n(n_){}
  30   non_copyable_int(BOOST_RV_REF(non_copyable_int) x):n(x.n){x.n=0;}
  31   non_copyable_int& operator=(BOOST_RV_REF(non_copyable_int) x)
  32   {
  33     n=x.n;
  34     x.n=0;
  35     return *this;
  36   }
  37
  38   int n;
  39 private:
  40   BOOST_MOVABLE_BUT_NOT_COPYABLE(non_copyable_int)
  41 };
  42
  43 class always_one
  44 {
  45 public:
  46   always_one():n(1){}
  47   ~always_one(){n=0;}
  48
  49   int get()const{return n;}
  50
  51 private:
  52   int n;
  53 };
  54
  55 inline bool operator==(const always_one& x,const always_one& y)
  56 {
  57   return x.get()==y.get();
  58 }
  59
  60 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
  61 namespace boost{
  62 #endif
  63
  64 inline std::size_t hash_value(const always_one& x)
  65 {
  66   return static_cast<std::size_t>(x.get());
  67 }
  68
  69 #if defined(BOOST_NO_ARGUMENT_DEPENDENT_LOOKUP)
  70 } /* namespace boost */
  71 #endif
  72
  73 class linked_object
  74 {
  75   struct impl:boost::enable_shared_from_this<impl>
  76   {
  77     typedef boost::shared_ptr<const impl> ptr;
  78
  79     impl(int n_,ptr next_=ptr()):n(n_),next(next_){}
  80
  81     int n;
  82     ptr next;
  83   };
  84
  85   typedef multi_index_container<
  86     impl,
  87     indexed_by<
  88
  89 #if BOOST_WORKAROUND(__IBMCPP__,BOOST_TESTED_AT(1010))
  90       ordered_unique<member<impl,int,&linked_object::impl::n> >,
  91       hashed_non_unique<member<impl,int,&linked_object::impl::n> >,
  92 #else
  93       ordered_unique<member<impl,int,&impl::n> >,
  94       hashed_non_unique<member<impl,int,&impl::n> >,
  95 #endif
  96
  97       sequenced<>,
  98       random_access<>
  99     >
 100   > impl_repository_t;
 101
 102   static impl_repository_t impl_repository;
 103
 104 public:
 105   linked_object(int n):pimpl(init(impl(n))){}
 106   linked_object(int n,const linked_object& x):pimpl(init(impl(n,x.pimpl))){}
 107
 108 private:
 109   impl::ptr init(const impl& x)
 110   {
 111     std::pair<impl_repository_t::iterator,bool> p=impl_repository.insert(x);
 112     if(p.second)return impl::ptr(&*p.first,&erase_impl);
 113     else        return p.first->shared_from_this();
 114   }
 115
 116   static void erase_impl(const impl* p)
 117   {
 118     impl_repository.erase(p->n);
 119   }
 120
 121   impl::ptr pimpl;
 122 };
 123
 124 linked_object::impl_repository_t linked_object::impl_repository;
 125
 126 struct tempvalue_iterator:
 127   boost::iterator_facade<
 128     tempvalue_iterator,int,boost::forward_traversal_tag,int>
 129 {
 130   tempvalue_iterator(int n_):n(n_){}
 131
 132   void increment(){++n;}
 133   bool equal(const tempvalue_iterator& x)const{return n==x.n;}
 134   int dereference()const{return n;}
 135
 136   int n;
 137 };
 138
 139 struct change_int
 140 {
 141   change_int(int n):n(n){}
 142
 143   void operator()(int& x)const{x=n;}
 144
 145   int n;
 146 };
 147
 148 #if !(defined BOOST_NO_EXCEPTIONS)
 149 struct change_int_and_throw
 150 {
 151   change_int_and_throw(int n):n(n){}
 152
 153   void operator()(int& x)const{x=n;throw 0;}
 154
 155   int n;
 156 };
 157 #endif
 158
 159 void test_modifiers()
 160 {
 161   employee_set              es;
 162   employee_set_by_name&     i1=get<name>(es);
 163   employee_set_by_age&      i2=get<age>(es);
 164   employee_set_as_inserted& i3=get<as_inserted>(es);
 165   employee_set_by_ssn&      i4=get<ssn>(es);
 166   employee_set_randomly&    i5=get<randomly>(es);
 167
 168   es.insert(employee(0,"Joe",31,1123));
 169   BOOST_TEST(es.emplace(0,"Joe",31,1123).second==false);
 170   BOOST_TEST(i1.insert(employee(0,"Joe Jr.",5,2563)).second==false);
 171   BOOST_TEST(i2.emplace_hint(i2.end(),1,"Victor",5,1123)->name!="Victor");
 172   BOOST_TEST(i3.insert(i3.begin(),employee(1,"Victor",5,1123)).second
 173                 ==false);
 174   BOOST_TEST(i3.push_front(employee(0,"Joe Jr.",5,2563)).second==false);
 175   BOOST_TEST(i3.push_back(employee(0,"Joe Jr.",5,2563)).second==false);
 176   BOOST_TEST(i5.emplace_front(1,"Victor",5,1123).second==false);
 177   BOOST_TEST(i5.emplace_back(1,"Victor",5,1123).second==false);
 178
 179   employee_set_by_name::iterator it1=i1.find("Joe");
 180   i1.insert(it1,employee(1,"Joe Jr.",5,2563));
 181   BOOST_TEST(es.size()==2);
 182
 183   employee_set_by_age::iterator it2=i2.find(31);
 184   i2.insert(it2,employee(2,"Grandda Joe",64,7881));
 185   BOOST_TEST(es.size()==3);
 186
 187   employee_set_as_inserted::iterator it3=i3.begin();
 188   i3.insert(it3,100,employee(3,"Judy",39,6201));
 189   BOOST_TEST((--it3)->ssn==6201);
 190   BOOST_TEST(es.size()==4);
 191
 192   employee_set_randomly::iterator it5=i5.begin();
 193   i5.insert(it5,100,employee(4,"Jill",52,3379));
 194   BOOST_TEST(i5.begin()->age==52);
 195   BOOST_TEST(es.size()==5);
 196
 197   es.erase(employee(1,"Joe Jr.",5,2563));
 198   BOOST_TEST(i3.size()==4&&i5.size()==4);
 199
 200   BOOST_TEST(i1.erase("Judy")==1);
 201   BOOST_TEST(es.size()==3&&i2.size()==3);
 202
 203   BOOST_TEST(i2.erase(it2)->age==52);
 204   BOOST_TEST(i3.size()==2&&i4.size()==2);
 205
 206   i3.pop_front();
 207   BOOST_TEST(i1.size()==1&&i2.size()==1);
 208
 209   i5.erase(i5.begin(),i5.end());
 210   BOOST_TEST(es.size()==0&&i3.size()==0);
 211
 212   i5.emplace(i5.end(),0,"Joe",31,1123);
 213   BOOST_TEST(i1.erase(i1.begin())==i1.end());
 214   BOOST_TEST(i1.size()==0);
 215
 216   i1.emplace(0,"Joe",31,1123);
 217   i3.emplace(i3.begin(),1,"Jack",31,5032);
 218   i4.emplace_hint(i4.end(),2,"James",31,3847);
 219   BOOST_TEST(i2.erase(31)==3);
 220   BOOST_TEST(i2.size()==0);
 221
 222   i3.emplace_front(1,"Jack",31,5032);
 223   i3.emplace_back(0,"Joe",31,1123);
 224   BOOST_TEST(i3.front()==employee(1,"Jack",31,5032));
 225   BOOST_TEST(i3.back()==employee(0,"Joe",31,1123));
 226
 227   i3.pop_back();
 228   BOOST_TEST(i3.back()==employee(1,"Jack",31,5032));
 229   BOOST_TEST(es.size()==1);
 230
 231   i3.pop_front();
 232   BOOST_TEST(es.size()==0);
 233
 234   i5.push_back(employee(1,"Jack",31,5032));
 235   i5.push_front(employee(0,"Joe",31,1123));
 236   i5.insert(i5.end()-1,employee(2,"Grandda Joe",64,7881));
 237   BOOST_TEST(i5.back()==employee(1,"Jack",31,5032));
 238   BOOST_TEST(i5.front()==employee(0,"Joe",31,1123));
 239   BOOST_TEST(i5[0]==i5.front()&&i5.at(0)==i5.front());
 240   BOOST_TEST(i5[i5.size()-1]==i5.back()&&i5.at(i5.size()-1)==i5.back());
 241
 242   i5.pop_front();
 243   BOOST_TEST(i5.back()==employee(1,"Jack",31,5032));
 244   BOOST_TEST(i5.front()==employee(2,"Grandda Joe",64,7881));
 245   BOOST_TEST(es.size()==2);
 246
 247   i5.pop_back();
 248   BOOST_TEST(i5.back()==employee(2,"Grandda Joe",64,7881));
 249   BOOST_TEST(i5.front()==i5.front());
 250   BOOST_TEST(es.size()==1);
 251
 252   i5.erase(i5.begin());
 253   BOOST_TEST(es.size()==0);
 254
 255   std::vector<employee> ve;
 256   ve.push_back(employee(3,"Anna",31,5388));
 257   ve.push_back(employee(1,"Rachel",27,9012));
 258   ve.push_back(employee(2,"Agatha",40,1520));
 259
 260   i1.insert(ve.begin(),ve.end());
 261   BOOST_TEST(i2.size()==3);
 262
 263 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 264   i1.insert({{4,"Vanessa",20,9236},{5,"Penelope",55,2358}});
 265   BOOST_TEST(i2.size()==5);
 266 #endif
 267
 268   BOOST_TEST(i2.erase(i2.begin(),i2.end())==i2.end());
 269   BOOST_TEST(es.size()==0);
 270
 271   i2.insert(ve.begin(),ve.end());
 272   BOOST_TEST(i3.size()==3);
 273
 274 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 275   i2.insert({{4,"Vanessa",20,9236},{5,"Penelope",55,2358}});
 276   BOOST_TEST(i3.size()==5);
 277 #endif
 278
 279   BOOST_TEST(*(i3.erase(i3.begin()))==employee(1,"Rachel",27,9012));
 280   BOOST_TEST(i3.erase(i3.begin(),i3.end())==i3.end());
 281   BOOST_TEST(es.size()==0);
 282
 283   i3.insert(i3.end(),ve.begin(),ve.end());
 284   BOOST_TEST(es.size()==3);
 285
 286 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 287   i3.insert(i3.begin(),{{4,"Vanessa",20,9236},{5,"Penelope",55,2358}});
 288   BOOST_TEST(i3.front().name=="Vanessa");
 289   BOOST_TEST(i4.size()==5);
 290 #endif
 291
 292   BOOST_TEST(i4.erase(9012)==1);
 293   i4.erase(i4.begin());
 294   BOOST_TEST(i4.erase(i4.begin(),i4.end())==i4.end());
 295
 296   i4.insert(ve.begin(),ve.end());
 297   BOOST_TEST(i5.size()==3);
 298
 299   BOOST_TEST(i5.erase(i5.begin(),i5.end())==i5.end());
 300   BOOST_TEST(es.size()==0);
 301
 302   i5.insert(i5.begin(),ve.begin(),ve.end());
 303   BOOST_TEST(i1.size()==3);
 304
 305 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 306   i5.insert(i5.end(),{{4,"Vanessa",20,9236},{5,"Penelope",55,2358}});
 307   BOOST_TEST(i5.back().name=="Penelope");
 308   BOOST_TEST(i1.size()==5);
 309 #endif
 310
 311   BOOST_TEST(es.erase(es.begin(),es.end())==es.end());
 312   BOOST_TEST(i2.size()==0);
 313
 314   es.insert(employee(0,"Joe",31,1123));
 315   es.insert(employee(1,"Robert",27,5601));
 316   es.insert(employee(2,"John",40,7889));
 317   es.insert(employee(3,"Albert",20,9012));
 318   es.insert(employee(4,"John",57,1002));
 319
 320   employee_set es_backup(es);
 321
 322   employee_set es2;
 323   es2.insert(employee(3,"Anna",31,5388));
 324   es2.insert(employee(1,"Rachel",27,9012));
 325   es2.insert(employee(2,"Agatha",40,1520));
 326
 327   employee_set es2_backup(es2);
 328
 329   i1.swap(get<1>(es2));
 330   BOOST_TEST(es==es2_backup&&es2==es_backup);
 331
 332   i2.swap(get<2>(es2));
 333   BOOST_TEST(es==es_backup&&es2==es2_backup);
 334
 335   i3.swap(get<3>(es2));
 336   BOOST_TEST(es==es2_backup&&es2==es_backup);
 337
 338   i4.swap(get<4>(es2));
 339   BOOST_TEST(es==es_backup&&es2==es2_backup);
 340
 341   i5.swap(get<5>(es2));
 342   BOOST_TEST(es==es2_backup&&es2==es_backup);
 343
 344 #if defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
 345   ::boost::multi_index::detail::swap(i1,get<1>(es2));
 346 #else
 347   using std::swap;
 348   swap(i1,get<1>(es2));
 349 #endif
 350
 351   BOOST_TEST(es==es_backup&&es2==es2_backup);
 352
 353 #if defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
 354   ::boost::multi_index::detail::swap(i2,get<2>(es2));
 355 #else
 356   using std::swap;
 357   swap(i2,get<2>(es2));
 358 #endif
 359
 360   BOOST_TEST(es==es2_backup&&es2==es_backup);
 361
 362 #if defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
 363   ::boost::multi_index::detail::swap(i3,get<3>(es2));
 364 #else
 365   using std::swap;
 366   swap(i3,get<3>(es2));
 367 #endif
 368
 369   BOOST_TEST(es==es_backup&&es2==es2_backup);
 370
 371 #if defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
 372   ::boost::multi_index::detail::swap(i4,get<4>(es2));
 373 #else
 374   using std::swap;
 375   swap(i4,get<4>(es2));
 376 #endif
 377
 378   BOOST_TEST(es==es2_backup&&es2==es_backup);
 379
 380 #if defined(BOOST_FUNCTION_SCOPE_USING_DECLARATION_BREAKS_ADL)
 381   ::boost::multi_index::detail::swap(i5,get<5>(es2));
 382 #else
 383   using std::swap;
 384   swap(i5,get<5>(es2));
 385 #endif
 386
 387   BOOST_TEST(es==es_backup&&es2==es2_backup);
 388
 389   i3.clear();
 390   BOOST_TEST(i3.size()==0);
 391
 392   es=es2;
 393   i4.clear();
 394   BOOST_TEST(i4.size()==0);
 395
 396   es=es2;
 397   i5.clear();
 398   BOOST_TEST(i5.size()==0);
 399
 400   es2.clear();
 401   BOOST_TEST(es2.size()==0);
 402
 403   /* non-copyable elements */
 404
 405   multi_index_container<
 406     non_copyable_int,
 407     indexed_by<
 408       ordered_non_unique<member<non_copyable_int,int,&non_copyable_int::n> >,
 409       hashed_non_unique<member<non_copyable_int,int,&non_copyable_int::n> >,
 410       sequenced<>,
 411       random_access<>
 412     >
 413   > ncic,ncic2;
 414
 415   ncic.emplace(1);
 416   get<1>(ncic).emplace(1);
 417   get<2>(ncic).emplace_back(1);
 418   get<3>(ncic).emplace_back(1);
 419
 420   non_copyable_int nci(1);
 421   ncic.insert(boost::move(nci));
 422   BOOST_TEST(nci.n==0);
 423
 424   nci.n=1;
 425   get<1>(ncic).insert(boost::move(nci));
 426   BOOST_TEST(nci.n==0);
 427
 428   nci.n=1;
 429   get<2>(ncic).push_back(boost::move(nci));
 430   BOOST_TEST(nci.n==0);
 431
 432   nci.n=1;
 433   get<3>(ncic).push_back(boost::move(nci));
 434   BOOST_TEST(nci.n==0);
 435
 436   std::vector<int> vi(4,1);
 437   const std::vector<int>& cvi=vi;
 438   ncic.insert(vi.begin(),vi.end());
 439   ncic.insert(cvi.begin(),cvi.end());
 440   get<2>(ncic).insert(get<2>(ncic).begin(),vi.begin(),vi.end());
 441   get<2>(ncic).insert(get<2>(ncic).begin(),cvi.begin(),cvi.end());
 442
 443   BOOST_TEST(ncic.count(1)==24);
 444
 445   ncic.swap(ncic2);
 446   BOOST_TEST(ncic.empty());
 447   BOOST_TEST(ncic2.count(1)==24);
 448
 449   /* testcase for problem reported at
 450    * http://lists.boost.org/boost-users/2006/12/24215.php
 451    */
 452
 453   multi_index_container<
 454     always_one,
 455     indexed_by<
 456       hashed_non_unique<identity<always_one> >
 457     >
 458   > aoc;
 459
 460   aoc.insert(always_one());
 461   aoc.insert(always_one());
 462   aoc.erase(*(aoc.begin()));
 463   BOOST_TEST(aoc.empty());
 464
 465   /* Testcases for compliance with "as close to hint as possible"
 466    * proposed behavior for associative containers:
 467    *   http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html#233
 468    *   http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2005/n1780.html
 469    */
 470
 471   typedef multi_index_container<
 472     int,
 473     indexed_by<
 474       ordered_non_unique<identity<int> >
 475     >
 476   > int_non_unique_container;
 477
 478   int_non_unique_container c;
 479   c.insert(0);c.insert(0);
 480   c.insert(1);c.insert(1);
 481   c.insert(2);c.insert(2);
 482
 483   BOOST_TEST(std::distance(c.begin(),c.insert(c.begin(),1))==2);
 484   BOOST_TEST(std::distance(c.begin(),c.insert(boost::next(c.begin()),1))==2);
 485   BOOST_TEST(std::distance(c.begin(),c.insert(c.lower_bound(1),1))==2);
 486   BOOST_TEST(
 487     std::distance(c.begin(),c.insert(boost::next(c.lower_bound(1)),1))==3);
 488   BOOST_TEST(std::distance(c.begin(),c.insert(c.upper_bound(1),1))==8);
 489   BOOST_TEST(std::distance(c.begin(),c.insert(boost::prior(c.end()),1))==9);
 490   BOOST_TEST(std::distance(c.begin(),c.insert(c.end(),1))==10);
 491
 492   /* testcase for erase() reentrancy */
 493   {
 494     linked_object o1(1);
 495     linked_object o2(2,o1);
 496     o1=o2;
 497   }
 498
 499   /* testcases for bug reported at
 500    * https://svn.boost.org/trac/boost/ticket/9665
 501    */
 502
 503   {
 504     multi_index_container<
 505       int,
 506       indexed_by<hashed_unique<identity<int> > >
 507     > hc;
 508     hc.insert(tempvalue_iterator(0),tempvalue_iterator(10));
 509     BOOST_TEST(hc.size()==10);
 510
 511     multi_index_container<
 512       int,
 513       indexed_by<ordered_unique<identity<int> > >
 514     > oc;
 515     oc.insert(tempvalue_iterator(0),tempvalue_iterator(10));
 516     BOOST_TEST(oc.size()==10);
 517   }
 518
 519   /* testcases for https://svn.boost.org/trac10/ticket/12542 */
 520
 521   {
 522     multi_index_container<
 523       int,
 524       indexed_by<
 525         ordered_unique<identity<int> >,
 526         hashed_unique<identity<int> >
 527      >
 528     > ohc;
 529
 530 #if !(defined BOOST_NO_EXCEPTIONS)
 531     ohc.insert(0);
 532     ohc.insert(1);
 533
 534     try{
 535       ohc.modify_key(ohc.begin(),change_int_and_throw(1));
 536     }
 537     catch(int){}
 538     BOOST_TEST(ohc.size()==1);
 539     ohc.clear();
 540
 541     ohc.insert(0);
 542     ohc.insert(1);
 543
 544     try{
 545       ohc.modify_key(ohc.begin(),change_int_and_throw(1),change_int(0));
 546     }
 547     catch(int){}
 548     BOOST_TEST(ohc.size()==1);
 549     ohc.clear();
 550
 551     ohc.insert(0);
 552     ohc.insert(1);
 553
 554     try{
 555       ohc.modify_key(
 556         ohc.begin(),change_int_and_throw(1),change_int_and_throw(0));
 557     }
 558     catch(int){}
 559     BOOST_TEST(ohc.size()==1);
 560     ohc.clear();
 561
 562     ohc.insert(0);
 563     ohc.insert(1);
 564
 565     try{
 566       ohc.modify_key(ohc.begin(),change_int(1),change_int_and_throw(0));
 567     }
 568     catch(int){}
 569     BOOST_TEST(ohc.size()==1);
 570     ohc.clear();
 571 #endif
 572
 573     ohc.insert(0);
 574     ohc.insert(1);
 575
 576     ohc.modify_key(ohc.begin(),change_int(1),change_int(1));
 577     BOOST_TEST(ohc.size()==1);
 578     ohc.clear();
 579   }
 580 }