ceph/src/boost/boost/multi_index/sequenced_index.hpp

   1 /* Copyright 2003-2017 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
  10 #define BOOST_MULTI_INDEX_SEQUENCED_INDEX_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <boost/bind.hpp>
  18 #include <boost/call_traits.hpp>
  19 #include <boost/detail/allocator_utilities.hpp>
  20 #include <boost/detail/no_exceptions_support.hpp>
  21 #include <boost/detail/workaround.hpp>
  22 #include <boost/foreach_fwd.hpp>
  23 #include <boost/iterator/reverse_iterator.hpp>
  24 #include <boost/move/core.hpp>
  25 #include <boost/move/utility.hpp>
  26 #include <boost/mpl/bool.hpp>
  27 #include <boost/mpl/not.hpp>
  28 #include <boost/mpl/push_front.hpp>
  29 #include <boost/multi_index/detail/access_specifier.hpp>
  30 #include <boost/multi_index/detail/bidir_node_iterator.hpp>
  31 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
  32 #include <boost/multi_index/detail/index_node_base.hpp>
  33 #include <boost/multi_index/detail/safe_mode.hpp>
  34 #include <boost/multi_index/detail/scope_guard.hpp>
  35 #include <boost/multi_index/detail/seq_index_node.hpp>
  36 #include <boost/multi_index/detail/seq_index_ops.hpp>
  37 #include <boost/multi_index/detail/vartempl_support.hpp>
  38 #include <boost/multi_index/sequenced_index_fwd.hpp>
  39 #include <boost/tuple/tuple.hpp>
  40 #include <boost/type_traits/is_integral.hpp>
  41 #include <cstddef>
  42 #include <functional>
  43 #include <utility>
  44
  45 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  46 #include<initializer_list>
  47 #endif
  48
  49 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  50 #include <boost/bind.hpp>
  51 #endif
  52
  53 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  54 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x)                    \
  55   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  56     detail::make_obj_guard(x,&sequenced_index::check_invariant_);            \
  57   BOOST_JOIN(check_invariant_,__LINE__).touch();
  58 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT                          \
  59   BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(*this)
  60 #else
  61 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x)
  62 #define BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
  63 #endif
  64
  65 namespace boost{
  66
  67 namespace multi_index{
  68
  69 namespace detail{
  70
  71 /* sequenced_index adds a layer of sequenced indexing to a given Super */
  72
  73 template<typename SuperMeta,typename TagList>
  74 class sequenced_index:
  75   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
  76
  77 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  78   ,public safe_mode::safe_container<
  79     sequenced_index<SuperMeta,TagList> >
  80 #endif
  81
  82 {
  83 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  84     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  85 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
  86  * lifetime of const references bound to temporaries --precisely what
  87  * scopeguards are.
  88  */
  89
  90 #pragma parse_mfunc_templ off
  91 #endif
  92
  93   typedef typename SuperMeta::type                    super;
  94
  95 protected:
  96   typedef sequenced_index_node<
  97     typename super::node_type>                        node_type;
  98
  99 private:
 100   typedef typename node_type::impl_type               node_impl_type;
 101
 102 public:
 103   /* types */
 104
 105   typedef typename node_type::value_type              value_type;
 106   typedef tuples::null_type                           ctor_args;
 107   typedef typename super::final_allocator_type        allocator_type;
 108   typedef typename allocator_type::reference          reference;
 109   typedef typename allocator_type::const_reference    const_reference;
 110
 111 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 112   typedef safe_mode::safe_iterator<
 113     bidir_node_iterator<node_type>,
 114     sequenced_index>                                  iterator;
 115 #else
 116   typedef bidir_node_iterator<node_type>              iterator;
 117 #endif
 118
 119   typedef iterator                                    const_iterator;
 120
 121   typedef std::size_t                                 size_type;
 122   typedef std::ptrdiff_t                              difference_type;
 123   typedef typename allocator_type::pointer            pointer;
 124   typedef typename allocator_type::const_pointer      const_pointer;
 125   typedef typename
 126     boost::reverse_iterator<iterator>                 reverse_iterator;
 127   typedef typename
 128     boost::reverse_iterator<const_iterator>           const_reverse_iterator;
 129   typedef TagList                                     tag_list;
 130
 131 protected:
 132   typedef typename super::final_node_type     final_node_type;
 133   typedef tuples::cons<
 134     ctor_args,
 135     typename super::ctor_args_list>           ctor_args_list;
 136   typedef typename mpl::push_front<
 137     typename super::index_type_list,
 138     sequenced_index>::type                    index_type_list;
 139   typedef typename mpl::push_front<
 140     typename super::iterator_type_list,
 141     iterator>::type                           iterator_type_list;
 142   typedef typename mpl::push_front<
 143     typename super::const_iterator_type_list,
 144     const_iterator>::type                     const_iterator_type_list;
 145   typedef typename super::copy_map_type       copy_map_type;
 146
 147 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 148   typedef typename super::index_saver_type    index_saver_type;
 149   typedef typename super::index_loader_type   index_loader_type;
 150 #endif
 151
 152 private:
 153 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 154   typedef safe_mode::safe_container<
 155     sequenced_index>                          safe_super;
 156 #endif
 157
 158   typedef typename call_traits<value_type>::param_type value_param_type;
 159
 160   /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL
 161    * expansion.
 162    */
 163
 164   typedef std::pair<iterator,bool>                     emplace_return_type;
 165
 166 public:
 167
 168   /* construct/copy/destroy
 169    * Default and copy ctors are in the protected section as indices are
 170    * not supposed to be created on their own. No range ctor either.
 171    */
 172
 173   sequenced_index<SuperMeta,TagList>& operator=(
 174     const sequenced_index<SuperMeta,TagList>& x)
 175   {
 176     this->final()=x.final();
 177     return *this;
 178   }
 179
 180 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 181   sequenced_index<SuperMeta,TagList>& operator=(
 182     std::initializer_list<value_type> list)
 183   {
 184     this->final()=list;
 185     return *this;
 186   }
 187 #endif
 188
 189   template <class InputIterator>
 190   void assign(InputIterator first,InputIterator last)
 191   {
 192     assign_iter(first,last,mpl::not_<is_integral<InputIterator> >());
 193   }
 194
 195 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 196   void assign(std::initializer_list<value_type> list)
 197   {
 198     assign(list.begin(),list.end());
 199   }
 200 #endif
 201
 202   void assign(size_type n,value_param_type value)
 203   {
 204     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 205     clear();
 206     for(size_type i=0;i<n;++i)push_back(value);
 207   }
 208
 209   allocator_type get_allocator()const BOOST_NOEXCEPT
 210   {
 211     return this->final().get_allocator();
 212   }
 213
 214   /* iterators */
 215
 216   iterator  begin()BOOST_NOEXCEPT
 217     {return make_iterator(node_type::from_impl(header()->next()));}
 218   const_iterator begin()const BOOST_NOEXCEPT
 219     {return make_iterator(node_type::from_impl(header()->next()));}
 220   iterator
 221     end()BOOST_NOEXCEPT{return make_iterator(header());}
 222   const_iterator
 223     end()const BOOST_NOEXCEPT{return make_iterator(header());}
 224   reverse_iterator
 225     rbegin()BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 226   const_reverse_iterator
 227     rbegin()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(end());}
 228   reverse_iterator
 229     rend()BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 230   const_reverse_iterator
 231     rend()const BOOST_NOEXCEPT{return boost::make_reverse_iterator(begin());}
 232   const_iterator
 233     cbegin()const BOOST_NOEXCEPT{return begin();}
 234   const_iterator
 235     cend()const BOOST_NOEXCEPT{return end();}
 236   const_reverse_iterator
 237     crbegin()const BOOST_NOEXCEPT{return rbegin();}
 238   const_reverse_iterator
 239     crend()const BOOST_NOEXCEPT{return rend();}
 240
 241   iterator iterator_to(const value_type& x)
 242   {
 243     return make_iterator(node_from_value<node_type>(&x));
 244   }
 245
 246   const_iterator iterator_to(const value_type& x)const
 247   {
 248     return make_iterator(node_from_value<node_type>(&x));
 249   }
 250
 251   /* capacity */
 252
 253   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
 254   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
 255   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
 256
 257   void resize(size_type n)
 258   {
 259     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 260     if(n>size()){
 261       for(size_type m=n-size();m--;)
 262         this->final_emplace_(BOOST_MULTI_INDEX_NULL_PARAM_PACK);
 263     }
 264     else if(n<size()){for(size_type m=size()-n;m--;)pop_back();}
 265   }
 266
 267   void resize(size_type n,value_param_type x)
 268   {
 269     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 270     if(n>size())insert(end(),n-size(),x);
 271     else if(n<size())for(size_type m=size()-n;m--;)pop_back();
 272   }
 273
 274   /* access: no non-const versions provided as sequenced_index
 275    * handles const elements.
 276    */
 277
 278   const_reference front()const{return *begin();}
 279   const_reference back()const{return *--end();}
 280
 281   /* modifiers */
 282
 283   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 284     emplace_return_type,emplace_front,emplace_front_impl)
 285
 286   std::pair<iterator,bool> push_front(const value_type& x)
 287                              {return insert(begin(),x);}
 288   std::pair<iterator,bool> push_front(BOOST_RV_REF(value_type) x)
 289                              {return insert(begin(),boost::move(x));}
 290   void                     pop_front(){erase(begin());}
 291
 292   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 293     emplace_return_type,emplace_back,emplace_back_impl)
 294
 295   std::pair<iterator,bool> push_back(const value_type& x)
 296                              {return insert(end(),x);}
 297   std::pair<iterator,bool> push_back(BOOST_RV_REF(value_type) x)
 298                              {return insert(end(),boost::move(x));}
 299   void                     pop_back(){erase(--end());}
 300
 301   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
 302     emplace_return_type,emplace,emplace_impl,iterator,position)
 303
 304   std::pair<iterator,bool> insert(iterator position,const value_type& x)
 305   {
 306     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 307     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 308     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 309     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 310     if(p.second&&position.get_node()!=header()){
 311       relink(position.get_node(),p.first);
 312     }
 313     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 314   }
 315
 316   std::pair<iterator,bool> insert(iterator position,BOOST_RV_REF(value_type) x)
 317   {
 318     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 319     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 320     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 321     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
 322     if(p.second&&position.get_node()!=header()){
 323       relink(position.get_node(),p.first);
 324     }
 325     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 326   }
 327
 328   void insert(iterator position,size_type n,value_param_type x)
 329   {
 330     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 331     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 332     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 333     for(size_type i=0;i<n;++i)insert(position,x);
 334   }
 335
 336   template<typename InputIterator>
 337   void insert(iterator position,InputIterator first,InputIterator last)
 338   {
 339     insert_iter(position,first,last,mpl::not_<is_integral<InputIterator> >());
 340   }
 341
 342 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 343   void insert(iterator position,std::initializer_list<value_type> list)
 344   {
 345     insert(position,list.begin(),list.end());
 346   }
 347 #endif
 348
 349   iterator erase(iterator position)
 350   {
 351     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 352     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 353     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 354     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 355     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 356     return position;
 357   }
 358
 359   iterator erase(iterator first,iterator last)
 360   {
 361     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 362     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 363     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 364     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 365     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 366     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 367     while(first!=last){
 368       first=erase(first);
 369     }
 370     return first;
 371   }
 372
 373   bool replace(iterator position,const value_type& x)
 374   {
 375     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 376     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 377     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 378     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 379     return this->final_replace_(
 380       x,static_cast<final_node_type*>(position.get_node()));
 381   }
 382
 383   bool replace(iterator position,BOOST_RV_REF(value_type) x)
 384   {
 385     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 386     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 387     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 388     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 389     return this->final_replace_rv_(
 390       x,static_cast<final_node_type*>(position.get_node()));
 391   }
 392
 393   template<typename Modifier>
 394   bool modify(iterator position,Modifier mod)
 395   {
 396     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 397     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 398     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 399     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 400
 401 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 402     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 403      * this is not added. Left it for all compilers as it does no
 404      * harm.
 405      */
 406
 407     position.detach();
 408 #endif
 409
 410     return this->final_modify_(
 411       mod,static_cast<final_node_type*>(position.get_node()));
 412   }
 413
 414   template<typename Modifier,typename Rollback>
 415   bool modify(iterator position,Modifier mod,Rollback back_)
 416   {
 417     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 418     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 419     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 420     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 421
 422 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 423     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 424      * this is not added. Left it for all compilers as it does no
 425      * harm.
 426      */
 427
 428     position.detach();
 429 #endif
 430
 431     return this->final_modify_(
 432       mod,back_,static_cast<final_node_type*>(position.get_node()));
 433   }
 434
 435   void swap(sequenced_index<SuperMeta,TagList>& x)
 436   {
 437     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 438     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF(x);
 439     this->final_swap_(x.final());
 440   }
 441
 442   void clear()BOOST_NOEXCEPT
 443   {
 444     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 445     this->final_clear_();
 446   }
 447
 448   /* list operations */
 449
 450   void splice(iterator position,sequenced_index<SuperMeta,TagList>& x)
 451   {
 452     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 453     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 454     BOOST_MULTI_INDEX_CHECK_DIFFERENT_CONTAINER(*this,x);
 455     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 456     iterator first=x.begin(),last=x.end();
 457     while(first!=last){
 458       if(insert(position,*first).second)first=x.erase(first);
 459       else ++first;
 460     }
 461   }
 462
 463   void splice(iterator position,sequenced_index<SuperMeta,TagList>& x,iterator i)
 464   {
 465     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 466     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 467     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 468     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 469     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
 470     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 471     if(&x==this){
 472       if(position!=i)relink(position.get_node(),i.get_node());
 473     }
 474     else{
 475       if(insert(position,*i).second){
 476
 477 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 478     /* MSVC++ 6.0 optimizer has a hard time with safe mode, and the following
 479      * workaround is needed. Left it for all compilers as it does no
 480      * harm.
 481      */
 482         i.detach();
 483         x.erase(x.make_iterator(i.get_node()));
 484 #else
 485         x.erase(i);
 486 #endif
 487
 488       }
 489     }
 490   }
 491
 492   void splice(
 493     iterator position,sequenced_index<SuperMeta,TagList>& x,
 494     iterator first,iterator last)
 495   {
 496     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 497     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 498     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 499     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 500     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
 501     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
 502     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 503     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 504     if(&x==this){
 505       BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
 506       if(position!=last)relink(
 507         position.get_node(),first.get_node(),last.get_node());
 508     }
 509     else{
 510       while(first!=last){
 511         if(insert(position,*first).second)first=x.erase(first);
 512         else ++first;
 513       }
 514     }
 515   }
 516
 517   void remove(value_param_type value)
 518   {
 519     sequenced_index_remove(
 520       *this,
 521       ::boost::bind(std::equal_to<value_type>(),::boost::arg<1>(),value));
 522   }
 523
 524   template<typename Predicate>
 525   void remove_if(Predicate pred)
 526   {
 527     sequenced_index_remove(*this,pred);
 528   }
 529
 530   void unique()
 531   {
 532     sequenced_index_unique(*this,std::equal_to<value_type>());
 533   }
 534
 535   template <class BinaryPredicate>
 536   void unique(BinaryPredicate binary_pred)
 537   {
 538     sequenced_index_unique(*this,binary_pred);
 539   }
 540
 541   void merge(sequenced_index<SuperMeta,TagList>& x)
 542   {
 543     sequenced_index_merge(*this,x,std::less<value_type>());
 544   }
 545
 546   template <typename Compare>
 547   void merge(sequenced_index<SuperMeta,TagList>& x,Compare comp)
 548   {
 549     sequenced_index_merge(*this,x,comp);
 550   }
 551
 552   void sort()
 553   {
 554     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 555     sequenced_index_sort(header(),std::less<value_type>());
 556   }
 557
 558   template <typename Compare>
 559   void sort(Compare comp)
 560   {
 561     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 562     sequenced_index_sort(header(),comp);
 563   }
 564
 565   void reverse()BOOST_NOEXCEPT
 566   {
 567     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 568     node_impl_type::reverse(header()->impl());
 569   }
 570
 571   /* rearrange operations */
 572
 573   void relocate(iterator position,iterator i)
 574   {
 575     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 576     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 577     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 578     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 579     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,*this);
 580     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 581     if(position!=i)relink(position.get_node(),i.get_node());
 582   }
 583
 584   void relocate(iterator position,iterator first,iterator last)
 585   {
 586     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 587     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 588     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 589     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 590     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 591     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 592     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 593     BOOST_MULTI_INDEX_CHECK_OUTSIDE_RANGE(position,first,last);
 594     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 595     if(position!=last)relink(
 596       position.get_node(),first.get_node(),last.get_node());
 597   }
 598
 599   template<typename InputIterator>
 600   void rearrange(InputIterator first)
 601   {
 602     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 603     node_type* pos=header();
 604     for(size_type s=size();s--;){
 605       const value_type& v=*first++;
 606       relink(pos,node_from_value<node_type>(&v));
 607     }
 608   }
 609
 610 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 611   sequenced_index(const ctor_args_list& args_list,const allocator_type& al):
 612     super(args_list.get_tail(),al)
 613   {
 614     empty_initialize();
 615   }
 616
 617   sequenced_index(const sequenced_index<SuperMeta,TagList>& x):
 618     super(x)
 619
 620 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 621     ,safe_super()
 622 #endif
 623
 624   {
 625     /* the actual copying takes place in subsequent call to copy_() */
 626   }
 627
 628   sequenced_index(
 629     const sequenced_index<SuperMeta,TagList>& x,do_not_copy_elements_tag):
 630     super(x,do_not_copy_elements_tag())
 631
 632 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 633     ,safe_super()
 634 #endif
 635
 636   {
 637     empty_initialize();
 638   }
 639
 640   ~sequenced_index()
 641   {
 642     /* the container is guaranteed to be empty by now */
 643   }
 644
 645 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 646   iterator       make_iterator(node_type* node){return iterator(node,this);}
 647   const_iterator make_iterator(node_type* node)const
 648     {return const_iterator(node,const_cast<sequenced_index*>(this));}
 649 #else
 650   iterator       make_iterator(node_type* node){return iterator(node);}
 651   const_iterator make_iterator(node_type* node)const
 652                    {return const_iterator(node);}
 653 #endif
 654
 655   void copy_(
 656     const sequenced_index<SuperMeta,TagList>& x,const copy_map_type& map)
 657   {
 658     node_type* org=x.header();
 659     node_type* cpy=header();
 660     do{
 661       node_type* next_org=node_type::from_impl(org->next());
 662       node_type* next_cpy=map.find(static_cast<final_node_type*>(next_org));
 663       cpy->next()=next_cpy->impl();
 664       next_cpy->prior()=cpy->impl();
 665       org=next_org;
 666       cpy=next_cpy;
 667     }while(org!=x.header());
 668
 669     super::copy_(x,map);
 670   }
 671
 672   template<typename Variant>
 673   final_node_type* insert_(
 674     value_param_type v,final_node_type*& x,Variant variant)
 675   {
 676     final_node_type* res=super::insert_(v,x,variant);
 677     if(res==x)link(static_cast<node_type*>(x));
 678     return res;
 679   }
 680
 681   template<typename Variant>
 682   final_node_type* insert_(
 683     value_param_type v,node_type* position,final_node_type*& x,Variant variant)
 684   {
 685     final_node_type* res=super::insert_(v,position,x,variant);
 686     if(res==x)link(static_cast<node_type*>(x));
 687     return res;
 688   }
 689
 690   void erase_(node_type* x)
 691   {
 692     unlink(x);
 693     super::erase_(x);
 694
 695 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 696     detach_iterators(x);
 697 #endif
 698   }
 699
 700   void delete_all_nodes_()
 701   {
 702     for(node_type* x=node_type::from_impl(header()->next());x!=header();){
 703       node_type* y=node_type::from_impl(x->next());
 704       this->final_delete_node_(static_cast<final_node_type*>(x));
 705       x=y;
 706     }
 707   }
 708
 709   void clear_()
 710   {
 711     super::clear_();
 712     empty_initialize();
 713
 714 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 715     safe_super::detach_dereferenceable_iterators();
 716 #endif
 717   }
 718
 719   void swap_(sequenced_index<SuperMeta,TagList>& x)
 720   {
 721 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 722     safe_super::swap(x);
 723 #endif
 724
 725     super::swap_(x);
 726   }
 727
 728   void swap_elements_(sequenced_index<SuperMeta,TagList>& x)
 729   {
 730 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 731     safe_super::swap(x);
 732 #endif
 733
 734     super::swap_elements_(x);
 735   }
 736
 737   template<typename Variant>
 738   bool replace_(value_param_type v,node_type* x,Variant variant)
 739   {
 740     return super::replace_(v,x,variant);
 741   }
 742
 743   bool modify_(node_type* x)
 744   {
 745     BOOST_TRY{
 746       if(!super::modify_(x)){
 747         unlink(x);
 748
 749 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 750         detach_iterators(x);
 751 #endif
 752
 753         return false;
 754       }
 755       else return true;
 756     }
 757     BOOST_CATCH(...){
 758       unlink(x);
 759
 760 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 761       detach_iterators(x);
 762 #endif
 763
 764       BOOST_RETHROW;
 765     }
 766     BOOST_CATCH_END
 767   }
 768
 769   bool modify_rollback_(node_type* x)
 770   {
 771     return super::modify_rollback_(x);
 772   }
 773
 774   bool check_rollback_(node_type* x)const
 775   {
 776     return super::check_rollback_(x);
 777   }
 778
 779 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 780   /* serialization */
 781
 782   template<typename Archive>
 783   void save_(
 784     Archive& ar,const unsigned int version,const index_saver_type& sm)const
 785   {
 786     sm.save(begin(),end(),ar,version);
 787     super::save_(ar,version,sm);
 788   }
 789
 790   template<typename Archive>
 791   void load_(
 792     Archive& ar,const unsigned int version,const index_loader_type& lm)
 793   {
 794     lm.load(
 795       ::boost::bind(
 796         &sequenced_index::rearranger,this,::boost::arg<1>(),::boost::arg<2>()),
 797       ar,version);
 798     super::load_(ar,version,lm);
 799   }
 800 #endif
 801
 802 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 803   /* invariant stuff */
 804
 805   bool invariant_()const
 806   {
 807     if(size()==0||begin()==end()){
 808       if(size()!=0||begin()!=end()||
 809          header()->next()!=header()->impl()||
 810          header()->prior()!=header()->impl())return false;
 811     }
 812     else{
 813       size_type s=0;
 814       for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s){
 815         if(it.get_node()->next()->prior()!=it.get_node()->impl())return false;
 816         if(it.get_node()->prior()->next()!=it.get_node()->impl())return false;
 817       }
 818       if(s!=size())return false;
 819     }
 820
 821     return super::invariant_();
 822   }
 823
 824   /* This forwarding function eases things for the boost::mem_fn construct
 825    * in BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT. Actually,
 826    * final_check_invariant is already an inherited member function of index.
 827    */
 828   void check_invariant_()const{this->final_check_invariant_();}
 829 #endif
 830
 831 private:
 832   node_type* header()const{return this->final_header();}
 833
 834   void empty_initialize()
 835   {
 836     header()->prior()=header()->next()=header()->impl();
 837   }
 838
 839   void link(node_type* x)
 840   {
 841     node_impl_type::link(x->impl(),header()->impl());
 842   };
 843
 844   static void unlink(node_type* x)
 845   {
 846     node_impl_type::unlink(x->impl());
 847   }
 848
 849   static void relink(node_type* position,node_type* x)
 850   {
 851     node_impl_type::relink(position->impl(),x->impl());
 852   }
 853
 854   static void relink(node_type* position,node_type* first,node_type* last)
 855   {
 856     node_impl_type::relink(
 857       position->impl(),first->impl(),last->impl());
 858   }
 859
 860 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 861   void rearranger(node_type* position,node_type *x)
 862   {
 863     if(!position)position=header();
 864     node_type::increment(position);
 865     if(position!=x)relink(position,x);
 866   }
 867 #endif
 868
 869 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 870   void detach_iterators(node_type* x)
 871   {
 872     iterator it=make_iterator(x);
 873     safe_mode::detach_equivalent_iterators(it);
 874   }
 875 #endif
 876
 877   template <class InputIterator>
 878   void assign_iter(InputIterator first,InputIterator last,mpl::true_)
 879   {
 880     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 881     clear();
 882     for(;first!=last;++first)this->final_insert_ref_(*first);
 883   }
 884
 885   void assign_iter(size_type n,value_param_type value,mpl::false_)
 886   {
 887     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 888     clear();
 889     for(size_type i=0;i<n;++i)push_back(value);
 890   }
 891
 892   template<typename InputIterator>
 893   void insert_iter(
 894     iterator position,InputIterator first,InputIterator last,mpl::true_)
 895   {
 896     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 897     for(;first!=last;++first){
 898       std::pair<final_node_type*,bool> p=
 899         this->final_insert_ref_(*first);
 900       if(p.second&&position.get_node()!=header()){
 901         relink(position.get_node(),p.first);
 902       }
 903     }
 904   }
 905
 906   void insert_iter(
 907     iterator position,size_type n,value_param_type x,mpl::false_)
 908   {
 909     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 910     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 911     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 912     for(size_type i=0;i<n;++i)insert(position,x);
 913   }
 914
 915   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
 916   std::pair<iterator,bool> emplace_front_impl(
 917     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
 918   {
 919     return emplace_impl(begin(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
 920   }
 921
 922   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
 923   std::pair<iterator,bool> emplace_back_impl(
 924     BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
 925   {
 926     return emplace_impl(end(),BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
 927   }
 928
 929   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
 930   std::pair<iterator,bool> emplace_impl(
 931     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
 932   {
 933     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 934     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 935     BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT;
 936     std::pair<final_node_type*,bool> p=
 937       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
 938     if(p.second&&position.get_node()!=header()){
 939       relink(position.get_node(),p.first);
 940     }
 941     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 942   }
 943
 944 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
 945     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 946 #pragma parse_mfunc_templ reset
 947 #endif
 948 };
 949
 950 /* comparison */
 951
 952 template<
 953   typename SuperMeta1,typename TagList1,
 954   typename SuperMeta2,typename TagList2
 955 >
 956 bool operator==(
 957   const sequenced_index<SuperMeta1,TagList1>& x,
 958   const sequenced_index<SuperMeta2,TagList2>& y)
 959 {
 960   return x.size()==y.size()&&std::equal(x.begin(),x.end(),y.begin());
 961 }
 962
 963 template<
 964   typename SuperMeta1,typename TagList1,
 965   typename SuperMeta2,typename TagList2
 966 >
 967 bool operator<(
 968   const sequenced_index<SuperMeta1,TagList1>& x,
 969   const sequenced_index<SuperMeta2,TagList2>& y)
 970 {
 971   return std::lexicographical_compare(x.begin(),x.end(),y.begin(),y.end());
 972 }
 973
 974 template<
 975   typename SuperMeta1,typename TagList1,
 976   typename SuperMeta2,typename TagList2
 977 >
 978 bool operator!=(
 979   const sequenced_index<SuperMeta1,TagList1>& x,
 980   const sequenced_index<SuperMeta2,TagList2>& y)
 981 {
 982   return !(x==y);
 983 }
 984
 985 template<
 986   typename SuperMeta1,typename TagList1,
 987   typename SuperMeta2,typename TagList2
 988 >
 989 bool operator>(
 990   const sequenced_index<SuperMeta1,TagList1>& x,
 991   const sequenced_index<SuperMeta2,TagList2>& y)
 992 {
 993   return y<x;
 994 }
 995
 996 template<
 997   typename SuperMeta1,typename TagList1,
 998   typename SuperMeta2,typename TagList2
 999 >
1000 bool operator>=(
1001   const sequenced_index<SuperMeta1,TagList1>& x,
1002   const sequenced_index<SuperMeta2,TagList2>& y)
1003 {
1004   return !(x<y);
1005 }
1006
1007 template<
1008   typename SuperMeta1,typename TagList1,
1009   typename SuperMeta2,typename TagList2
1010 >
1011 bool operator<=(
1012   const sequenced_index<SuperMeta1,TagList1>& x,
1013   const sequenced_index<SuperMeta2,TagList2>& y)
1014 {
1015   return !(x>y);
1016 }
1017
1018 /*  specialized algorithms */
1019
1020 template<typename SuperMeta,typename TagList>
1021 void swap(
1022   sequenced_index<SuperMeta,TagList>& x,
1023   sequenced_index<SuperMeta,TagList>& y)
1024 {
1025   x.swap(y);
1026 }
1027
1028 } /* namespace multi_index::detail */
1029
1030 /* sequenced index specifier */
1031
1032 template <typename TagList>
1033 struct sequenced
1034 {
1035   BOOST_STATIC_ASSERT(detail::is_tag<TagList>::value);
1036
1037   template<typename Super>
1038   struct node_class
1039   {
1040     typedef detail::sequenced_index_node<Super> type;
1041   };
1042
1043   template<typename SuperMeta>
1044   struct index_class
1045   {
1046     typedef detail::sequenced_index<SuperMeta,typename TagList::type> type;
1047   };
1048 };
1049
1050 } /* namespace multi_index */
1051
1052 } /* namespace boost */
1053
1054 /* Boost.Foreach compatibility */
1055
1056 template<typename SuperMeta,typename TagList>
1057 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1058   boost::multi_index::detail::sequenced_index<SuperMeta,TagList>*&,
1059   boost_foreach_argument_dependent_lookup_hack)
1060 {
1061   return 0;
1062 }
1063
1064 #undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT
1065 #undef BOOST_MULTI_INDEX_SEQ_INDEX_CHECK_INVARIANT_OF
1066
1067 #endif