ceph/src/boost/boost/multi_index/hashed_index.hpp

   1 /* Copyright 2003-2021 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_HASHED_INDEX_HPP
  10 #define BOOST_MULTI_INDEX_HASHED_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 <algorithm>
  18 #include <boost/call_traits.hpp>
  19 #include <boost/core/addressof.hpp>
  20 #include <boost/core/no_exceptions_support.hpp>
  21 #include <boost/detail/workaround.hpp>
  22 #include <boost/foreach_fwd.hpp>
  23 #include <boost/limits.hpp>
  24 #include <boost/move/core.hpp>
  25 #include <boost/move/utility_core.hpp>
  26 #include <boost/mpl/bool.hpp>
  27 #include <boost/mpl/if.hpp>
  28 #include <boost/mpl/push_front.hpp>
  29 #include <boost/multi_index/detail/access_specifier.hpp>
  30 #include <boost/multi_index/detail/adl_swap.hpp>
  31 #include <boost/multi_index/detail/allocator_traits.hpp>
  32 #include <boost/multi_index/detail/auto_space.hpp>
  33 #include <boost/multi_index/detail/bucket_array.hpp>
  34 #include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
  35 #include <boost/multi_index/detail/hash_index_iterator.hpp>
  36 #include <boost/multi_index/detail/index_node_base.hpp>
  37 #include <boost/multi_index/detail/invalidate_iterators.hpp>
  38 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
  39 #include <boost/multi_index/detail/node_handle.hpp>
  40 #include <boost/multi_index/detail/promotes_arg.hpp>
  41 #include <boost/multi_index/detail/safe_mode.hpp>
  42 #include <boost/multi_index/detail/scope_guard.hpp>
  43 #include <boost/multi_index/detail/vartempl_support.hpp>
  44 #include <boost/multi_index/hashed_index_fwd.hpp>
  45 #include <boost/tuple/tuple.hpp>
  46 #include <boost/type_traits/is_same.hpp>
  47 #include <cmath>
  48 #include <cstddef>
  49 #include <functional>
  50 #include <iterator>
  51 #include <utility>
  52
  53 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
  54 #include <initializer_list>
  55 #endif
  56
  57 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  58 #include <boost/serialization/nvp.hpp>
  59 #endif
  60
  61 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  62 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)                 \
  63   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  64     detail::make_obj_guard(x,&hashed_index::check_invariant_);               \
  65   BOOST_JOIN(check_invariant_,__LINE__).touch();
  66 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \
  67   BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this)
  68 #else
  69 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)
  70 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
  71 #endif
  72
  73 namespace boost{
  74
  75 namespace multi_index{
  76
  77 namespace detail{
  78
  79 /* hashed_index adds a layer of hashed indexing to a given Super */
  80
  81 /* Most of the implementation of unique and non-unique indices is
  82  * shared. We tell from one another on instantiation time by using
  83  * Category tags defined in hash_index_node.hpp.
  84  */
  85
  86 #if defined(BOOST_MSVC)
  87 #pragma warning(push)
  88 #pragma warning(disable:4355) /* this used in base member initializer list */
  89 #endif
  90
  91 template<
  92   typename KeyFromValue,typename Hash,typename Pred,
  93   typename SuperMeta,typename TagList,typename Category
  94 >
  95 class hashed_index:
  96   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
  97 {
  98 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  99     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
 100 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
 101  * lifetime of const references bound to temporaries --precisely what
 102  * scopeguards are.
 103  */
 104
 105 #pragma parse_mfunc_templ off
 106 #endif
 107
 108 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
 109   /* cross-index access */
 110
 111   template <typename,typename,typename> friend class index_base;
 112 #endif
 113
 114   typedef typename SuperMeta::type               super;
 115
 116 protected:
 117   typedef hashed_index_node<
 118     typename super::index_node_type>             index_node_type;
 119
 120 private:
 121   typedef typename index_node_type::
 122     template node_alg<Category>::type            node_alg;
 123   typedef typename index_node_type::impl_type    node_impl_type;
 124   typedef typename node_impl_type::pointer       node_impl_pointer;
 125   typedef typename node_impl_type::base_pointer  node_impl_base_pointer;
 126   typedef bucket_array<
 127     typename super::final_allocator_type>        bucket_array_type;
 128
 129 public:
 130   /* types */
 131
 132   typedef typename KeyFromValue::result_type     key_type;
 133   typedef typename index_node_type::value_type   value_type;
 134   typedef KeyFromValue                           key_from_value;
 135   typedef Hash                                   hasher;
 136   typedef Pred                                   key_equal;
 137   typedef typename super::final_allocator_type   allocator_type;
 138
 139 private:
 140   typedef allocator_traits<allocator_type>       alloc_traits;
 141
 142 public:
 143   typedef typename alloc_traits::pointer         pointer;
 144   typedef typename alloc_traits::const_pointer   const_pointer;
 145   typedef value_type&                            reference;
 146   typedef const value_type&                      const_reference;
 147   typedef typename alloc_traits::size_type       size_type;
 148   typedef typename alloc_traits::difference_type difference_type;
 149   typedef tuple<size_type,
 150     key_from_value,hasher,key_equal>             ctor_args;
 151
 152 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 153   typedef safe_mode::safe_iterator<
 154     hashed_index_iterator<
 155       index_node_type,bucket_array_type,
 156       Category,
 157       hashed_index_global_iterator_tag> >        iterator;
 158 #else
 159   typedef hashed_index_iterator<
 160     index_node_type,bucket_array_type,
 161     Category,hashed_index_global_iterator_tag>   iterator;
 162 #endif
 163
 164   typedef iterator                               const_iterator;
 165
 166   typedef hashed_index_iterator<
 167     index_node_type,bucket_array_type,
 168     Category,hashed_index_local_iterator_tag>    local_iterator;
 169   typedef local_iterator                         const_local_iterator;
 170
 171   typedef typename super::final_node_handle_type node_type;
 172   typedef detail::insert_return_type<
 173     iterator,node_type>                          insert_return_type;
 174   typedef TagList                                tag_list;
 175
 176 protected:
 177   typedef typename super::final_node_type     final_node_type;
 178   typedef tuples::cons<
 179     ctor_args,
 180     typename super::ctor_args_list>           ctor_args_list;
 181   typedef typename mpl::push_front<
 182     typename super::index_type_list,
 183     hashed_index>::type                       index_type_list;
 184   typedef typename mpl::push_front<
 185     typename super::iterator_type_list,
 186     iterator>::type                           iterator_type_list;
 187   typedef typename mpl::push_front<
 188     typename super::const_iterator_type_list,
 189     const_iterator>::type                     const_iterator_type_list;
 190   typedef typename super::copy_map_type       copy_map_type;
 191
 192 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 193   typedef typename super::index_saver_type    index_saver_type;
 194   typedef typename super::index_loader_type   index_loader_type;
 195 #endif
 196
 197 private:
 198 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 199   typedef safe_mode::safe_container<iterator> safe_container;
 200 #endif
 201
 202   typedef typename call_traits<value_type>::param_type value_param_type;
 203   typedef typename call_traits<
 204     key_type>::param_type                              key_param_type;
 205
 206   /* needed to avoid commas in some macros */
 207
 208   typedef std::pair<iterator,bool>                     pair_return_type;
 209
 210 public:
 211
 212   /* construct/destroy/copy
 213    * Default and copy ctors are in the protected section as indices are
 214    * not supposed to be created on their own. No range ctor either.
 215    */
 216
 217   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
 218     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
 219   {
 220     this->final()=x.final();
 221     return *this;
 222   }
 223
 224 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 225   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
 226     std::initializer_list<value_type> list)
 227   {
 228     this->final()=list;
 229     return *this;
 230   }
 231 #endif
 232
 233   allocator_type get_allocator()const BOOST_NOEXCEPT
 234   {
 235     return this->final().get_allocator();
 236   }
 237
 238   /* size and capacity */
 239
 240   bool      empty()const BOOST_NOEXCEPT{return this->final_empty_();}
 241   size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
 242   size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
 243
 244   /* iterators */
 245
 246   iterator begin()BOOST_NOEXCEPT
 247   {
 248     return make_iterator(
 249       index_node_type::from_impl(header()->next()->prior()));
 250
 251   }
 252   const_iterator begin()const BOOST_NOEXCEPT
 253   {
 254     return make_iterator(
 255       index_node_type::from_impl(header()->next()->prior()));
 256   }
 257
 258   iterator       end()BOOST_NOEXCEPT{return make_iterator(header());}
 259   const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
 260   const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
 261   const_iterator cend()const BOOST_NOEXCEPT{return end();}
 262
 263   iterator iterator_to(const value_type& x)
 264   {
 265     return make_iterator(
 266       node_from_value<index_node_type>(boost::addressof(x)));
 267   }
 268
 269   const_iterator iterator_to(const value_type& x)const
 270   {
 271     return make_iterator(
 272       node_from_value<index_node_type>(boost::addressof(x)));
 273   }
 274
 275   /* modifiers */
 276
 277   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
 278     pair_return_type,emplace,emplace_impl)
 279
 280   BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
 281     iterator,emplace_hint,emplace_hint_impl,iterator,position)
 282
 283   std::pair<iterator,bool> insert(const value_type& x)
 284   {
 285     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 286     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 287     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 288   }
 289
 290   std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
 291   {
 292     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 293     std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
 294     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 295   }
 296
 297   iterator insert(iterator position,const value_type& x)
 298   {
 299     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 300     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 301     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 302     std::pair<final_node_type*,bool> p=this->final_insert_(
 303       x,static_cast<final_node_type*>(position.get_node()));
 304     return make_iterator(p.first);
 305   }
 306
 307   iterator insert(iterator position,BOOST_RV_REF(value_type) x)
 308   {
 309     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 310     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 311     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 312     std::pair<final_node_type*,bool> p=this->final_insert_rv_(
 313       x,static_cast<final_node_type*>(position.get_node()));
 314     return make_iterator(p.first);
 315   }
 316
 317   template<typename InputIterator>
 318   void insert(InputIterator first,InputIterator last)
 319   {
 320     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 321     for(;first!=last;++first)this->final_insert_ref_(*first);
 322   }
 323
 324 #if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
 325   void insert(std::initializer_list<value_type> list)
 326   {
 327     insert(list.begin(),list.end());
 328   }
 329 #endif
 330
 331   insert_return_type insert(BOOST_RV_REF(node_type) nh)
 332   {
 333     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
 334     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 335     std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh);
 336     return insert_return_type(make_iterator(p.first),p.second,boost::move(nh));
 337   }
 338
 339   iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh)
 340   {
 341     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 342     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 343     if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
 344     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 345     std::pair<final_node_type*,bool> p=this->final_insert_nh_(
 346       nh,static_cast<final_node_type*>(position.get_node()));
 347     return make_iterator(p.first);
 348   }
 349
 350   node_type extract(const_iterator position)
 351   {
 352     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 353     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 354     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 355     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 356     return this->final_extract_(
 357       static_cast<final_node_type*>(position.get_node()));
 358   }
 359
 360   node_type extract(key_param_type x)
 361   {
 362     iterator position=find(x);
 363     if(position==end())return node_type();
 364     else return extract(position);
 365   }
 366
 367   iterator erase(iterator position)
 368   {
 369     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 370     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 371     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 372     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 373     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 374     return position;
 375   }
 376
 377   size_type erase(key_param_type k)
 378   {
 379     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 380
 381     std::size_t buc=buckets.position(hash_(k));
 382     for(node_impl_pointer x=buckets.at(buc)->prior();
 383         x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
 384       if(eq_(k,key(index_node_type::from_impl(x)->value()))){
 385         node_impl_pointer y=end_of_range(x);
 386         size_type         s=0;
 387         do{
 388           node_impl_pointer z=node_alg::after(x);
 389           this->final_erase_(
 390             static_cast<final_node_type*>(index_node_type::from_impl(x)));
 391           x=z;
 392           ++s;
 393         }while(x!=y);
 394         return s;
 395       }
 396     }
 397     return 0;
 398   }
 399
 400   iterator erase(iterator first,iterator last)
 401   {
 402     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 403     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 404     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 405     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 406     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 407     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 408     while(first!=last){
 409       first=erase(first);
 410     }
 411     return first;
 412   }
 413
 414   bool replace(iterator position,const value_type& x)
 415   {
 416     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 417     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 418     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 419     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 420     return this->final_replace_(
 421       x,static_cast<final_node_type*>(position.get_node()));
 422   }
 423
 424   bool replace(iterator position,BOOST_RV_REF(value_type) x)
 425   {
 426     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 427     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 428     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 429     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 430     return this->final_replace_rv_(
 431       x,static_cast<final_node_type*>(position.get_node()));
 432   }
 433
 434   template<typename Modifier>
 435   bool modify(iterator position,Modifier mod)
 436   {
 437     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 438     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 439     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 440     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 441
 442 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 443     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 444      * this is not added. Left it for all compilers as it does no
 445      * harm.
 446      */
 447
 448     position.detach();
 449 #endif
 450
 451     return this->final_modify_(
 452       mod,static_cast<final_node_type*>(position.get_node()));
 453   }
 454
 455   template<typename Modifier,typename Rollback>
 456   bool modify(iterator position,Modifier mod,Rollback back_)
 457   {
 458     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 459     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 460     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 461     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 462
 463 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 464     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 465      * this is not added. Left it for all compilers as it does no
 466      * harm.
 467      */
 468
 469     position.detach();
 470 #endif
 471
 472     return this->final_modify_(
 473       mod,back_,static_cast<final_node_type*>(position.get_node()));
 474   }
 475
 476   template<typename Modifier>
 477   bool modify_key(iterator position,Modifier mod)
 478   {
 479     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 480     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 481     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 482     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 483     return modify(
 484       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
 485   }
 486
 487   template<typename Modifier,typename Rollback>
 488   bool modify_key(iterator position,Modifier mod,Rollback back_)
 489   {
 490     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 491     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 492     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 493     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 494     return modify(
 495       position,
 496       modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
 497       modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
 498   }
 499
 500   void clear()BOOST_NOEXCEPT
 501   {
 502     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 503     this->final_clear_();
 504   }
 505
 506   void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
 507   {
 508     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 509     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x);
 510     this->final_swap_(x.final());
 511   }
 512
 513   template<typename Index>
 514   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
 515   merge(Index& x)
 516   {
 517     merge(x,x.begin(),x.end());
 518   }
 519
 520   template<typename Index>
 521   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
 522   merge(BOOST_RV_REF(Index) x){merge(static_cast<Index&>(x));}
 523
 524   template<typename Index>
 525   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type)
 526   merge(Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i)
 527   {
 528     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
 529     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
 530     BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
 531     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
 532     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 533     if(x.end().get_node()==this->header()){ /* same container */
 534       return std::pair<iterator,bool>(
 535         make_iterator(static_cast<final_node_type*>(i.get_node())),true);
 536     }
 537     else{
 538       std::pair<final_node_type*,bool> p=this->final_transfer_(
 539         x,static_cast<final_node_type*>(i.get_node()));
 540       return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 541     }
 542   }
 543
 544   template<typename Index>
 545   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type)
 546   merge(BOOST_RV_REF(Index) x,BOOST_DEDUCED_TYPENAME Index::iterator i)
 547   {
 548     return merge(static_cast<Index&>(x),i);
 549   }
 550
 551   template<typename Index>
 552   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
 553   merge(
 554     Index& x,
 555     BOOST_DEDUCED_TYPENAME Index::iterator first,
 556     BOOST_DEDUCED_TYPENAME Index::iterator last)
 557   {
 558     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 559     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 560     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
 561     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
 562     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 563     BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
 564     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 565     if(x.end().get_node()!=this->header()){ /* different containers */
 566       this->final_transfer_range_(x,first,last);
 567     }
 568   }
 569
 570   template<typename Index>
 571   BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
 572   merge(
 573     BOOST_RV_REF(Index) x,
 574     BOOST_DEDUCED_TYPENAME Index::iterator first,
 575     BOOST_DEDUCED_TYPENAME Index::iterator last)
 576   {
 577     merge(static_cast<Index&>(x),first,last);
 578   }
 579
 580   /* observers */
 581
 582   key_from_value key_extractor()const{return key;}
 583   hasher         hash_function()const{return hash_;}
 584   key_equal      key_eq()const{return eq_;}
 585
 586   /* lookup */
 587
 588   /* Internally, these ops rely on const_iterator being the same
 589    * type as iterator.
 590    */
 591
 592   /* Implementation note: When CompatibleKey is consistently promoted to
 593    * KeyFromValue::result_type for equality comparison, the promotion is made
 594    * once in advance to increase efficiency.
 595    */
 596
 597   template<typename CompatibleKey>
 598   iterator find(const CompatibleKey& k)const
 599   {
 600     return find(k,hash_,eq_);
 601   }
 602
 603   template<
 604     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 605   >
 606   iterator find(
 607     const CompatibleKey& k,
 608     const CompatibleHash& hash,const CompatiblePred& eq)const
 609   {
 610     return find(
 611       k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
 612   }
 613
 614   template<typename CompatibleKey>
 615   size_type count(const CompatibleKey& k)const
 616   {
 617     return count(k,hash_,eq_);
 618   }
 619
 620   template<
 621     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 622   >
 623   size_type count(
 624     const CompatibleKey& k,
 625     const CompatibleHash& hash,const CompatiblePred& eq)const
 626   {
 627     return count(
 628       k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
 629   }
 630
 631   template<typename CompatibleKey>
 632   bool contains(const CompatibleKey& k)const
 633   {
 634     return contains(k,hash_,eq_);
 635   }
 636
 637   template<
 638     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 639   >
 640   bool contains(
 641     const CompatibleKey& k,
 642     const CompatibleHash& hash,const CompatiblePred& eq)const
 643   {
 644     return find(k,hash,eq)!=end();
 645   }
 646
 647   template<typename CompatibleKey>
 648   std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
 649   {
 650     return equal_range(k,hash_,eq_);
 651   }
 652
 653   template<
 654     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 655   >
 656   std::pair<iterator,iterator> equal_range(
 657     const CompatibleKey& k,
 658     const CompatibleHash& hash,const CompatiblePred& eq)const
 659   {
 660     return equal_range(
 661       k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
 662   }
 663
 664   /* bucket interface */
 665
 666   size_type bucket_count()const BOOST_NOEXCEPT
 667   {
 668     return static_cast<size_type>(buckets.size());
 669   }
 670
 671   size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
 672
 673   size_type bucket_size(size_type n)const
 674   {
 675     size_type res=0;
 676     for(node_impl_pointer x=buckets.at(n)->prior();
 677         x!=node_impl_pointer(0);x=node_alg::after_local(x)){
 678       ++res;
 679     }
 680     return res;
 681   }
 682
 683   size_type bucket(key_param_type k)const
 684   {
 685     return static_cast<size_type>(buckets.position(hash_(k)));
 686   }
 687
 688   local_iterator begin(size_type n)
 689   {
 690     return const_cast<const hashed_index*>(this)->begin(n);
 691   }
 692
 693   const_local_iterator begin(size_type n)const
 694   {
 695     node_impl_pointer x=buckets.at(n)->prior();
 696     if(x==node_impl_pointer(0))return end(n);
 697     return make_local_iterator(index_node_type::from_impl(x));
 698   }
 699
 700   local_iterator end(size_type n)
 701   {
 702     return const_cast<const hashed_index*>(this)->end(n);
 703   }
 704
 705   const_local_iterator end(size_type)const
 706   {
 707     return make_local_iterator(0);
 708   }
 709
 710   const_local_iterator cbegin(size_type n)const{return begin(n);}
 711   const_local_iterator cend(size_type n)const{return end(n);}
 712
 713   local_iterator local_iterator_to(const value_type& x)
 714   {
 715     return make_local_iterator(
 716       node_from_value<index_node_type>(boost::addressof(x)));
 717   }
 718
 719   const_local_iterator local_iterator_to(const value_type& x)const
 720   {
 721     return make_local_iterator(
 722       node_from_value<index_node_type>(boost::addressof(x)));
 723   }
 724
 725   /* hash policy */
 726
 727   float load_factor()const BOOST_NOEXCEPT
 728     {return static_cast<float>(size())/bucket_count();}
 729   float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
 730   void  max_load_factor(float z){mlf=z;calculate_max_load();}
 731
 732   void rehash(size_type n)
 733   {
 734     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 735     if(size()<=max_load&&n<=bucket_count())return;
 736
 737     size_type bc =(std::numeric_limits<size_type>::max)();
 738     float     fbc=1.0f+static_cast<float>(size())/mlf;
 739     if(bc>fbc){
 740       bc=static_cast<size_type>(fbc);
 741       if(bc<n)bc=n;
 742     }
 743     unchecked_rehash(bc);
 744   }
 745
 746   void reserve(size_type n)
 747   {
 748     rehash(static_cast<size_type>(std::ceil(static_cast<float>(n)/mlf)));
 749   }
 750
 751 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 752   hashed_index(const ctor_args_list& args_list,const allocator_type& al):
 753     super(args_list.get_tail(),al),
 754     key(tuples::get<1>(args_list.get_head())),
 755     hash_(tuples::get<2>(args_list.get_head())),
 756     eq_(tuples::get<3>(args_list.get_head())),
 757     buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
 758     mlf(1.0f)
 759
 760 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 761     ,safe(*this)
 762 #endif
 763
 764   {
 765     calculate_max_load();
 766   }
 767
 768   hashed_index(
 769     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
 770     super(x),
 771     key(x.key),
 772     hash_(x.hash_),
 773     eq_(x.eq_),
 774     buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
 775     mlf(x.mlf),
 776     max_load(x.max_load)
 777
 778 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 779     ,safe(*this)
 780 #endif
 781
 782   {
 783     /* Copy ctor just takes the internal configuration objects from x. The rest
 784      * is done in subsequent call to copy_().
 785      */
 786   }
 787
 788   hashed_index(
 789     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
 790     do_not_copy_elements_tag):
 791     super(x,do_not_copy_elements_tag()),
 792     key(x.key),
 793     hash_(x.hash_),
 794     eq_(x.eq_),
 795     buckets(x.get_allocator(),header()->impl(),0),
 796     mlf(1.0f)
 797
 798 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 799     ,safe(*this)
 800 #endif
 801
 802   {
 803      calculate_max_load();
 804   }
 805
 806   ~hashed_index()
 807   {
 808     /* the container is guaranteed to be empty by now */
 809   }
 810
 811 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 812   iterator make_iterator(index_node_type* node)
 813   {
 814     return iterator(node,&safe);
 815   }
 816
 817   const_iterator make_iterator(index_node_type* node)const
 818   {
 819     return const_iterator(node,const_cast<safe_container*>(&safe));
 820   }
 821 #else
 822   iterator make_iterator(index_node_type* node)
 823   {
 824     return iterator(node);
 825   }
 826
 827   const_iterator make_iterator(index_node_type* node)const
 828   {
 829     return const_iterator(node);
 830   }
 831 #endif
 832
 833   local_iterator make_local_iterator(index_node_type* node)
 834   {
 835     return local_iterator(node);
 836   }
 837
 838   const_local_iterator make_local_iterator(index_node_type* node)const
 839   {
 840     return const_local_iterator(node);
 841   }
 842
 843   void copy_(
 844     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
 845     const copy_map_type& map)
 846   {
 847     copy_(x,map,Category());
 848   }
 849
 850   void copy_(
 851     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
 852     const copy_map_type& map,hashed_unique_tag)
 853   {
 854     if(x.size()!=0){
 855       node_impl_pointer end_org=x.header()->impl(),
 856                         org=end_org,
 857                         cpy=header()->impl();
 858       do{
 859         node_impl_pointer prev_org=org->prior(),
 860                           prev_cpy=
 861           static_cast<index_node_type*>(map.find(static_cast<final_node_type*>(
 862             index_node_type::from_impl(prev_org))))->impl();
 863         cpy->prior()=prev_cpy;
 864         if(node_alg::is_first_of_bucket(org)){
 865           node_impl_base_pointer buc_org=prev_org->next(),
 866                                  buc_cpy=
 867             buckets.begin()+(buc_org-x.buckets.begin());
 868           prev_cpy->next()=buc_cpy;
 869           buc_cpy->prior()=cpy;
 870         }
 871         else{
 872           prev_cpy->next()=node_impl_type::base_pointer_from(cpy);
 873         }
 874         org=prev_org;
 875         cpy=prev_cpy;
 876       }while(org!=end_org);
 877     }
 878
 879     super::copy_(x,map);
 880   }
 881
 882   void copy_(
 883     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
 884     const copy_map_type& map,hashed_non_unique_tag)
 885   {
 886     if(x.size()!=0){
 887       node_impl_pointer end_org=x.header()->impl(),
 888                         org=end_org,
 889                         cpy=header()->impl();
 890       do{
 891         node_impl_pointer next_org=node_alg::after(org),
 892                           next_cpy=
 893           static_cast<index_node_type*>(map.find(static_cast<final_node_type*>(
 894             index_node_type::from_impl(next_org))))->impl();
 895         if(node_alg::is_first_of_bucket(next_org)){
 896           node_impl_base_pointer buc_org=org->next(),
 897                                  buc_cpy=
 898             buckets.begin()+(buc_org-x.buckets.begin());
 899           cpy->next()=buc_cpy;
 900           buc_cpy->prior()=next_cpy;
 901           next_cpy->prior()=cpy;
 902         }
 903         else{
 904           if(org->next()==node_impl_type::base_pointer_from(next_org)){
 905             cpy->next()=node_impl_type::base_pointer_from(next_cpy);
 906           }
 907           else{
 908             cpy->next()=
 909               node_impl_type::base_pointer_from(
 910                 static_cast<index_node_type*>(
 911                   map.find(static_cast<final_node_type*>(
 912                     index_node_type::from_impl(
 913                       node_impl_type::pointer_from(org->next())))))->impl());
 914           }
 915
 916           if(next_org->prior()!=org){
 917             next_cpy->prior()=
 918               static_cast<index_node_type*>(
 919                 map.find(static_cast<final_node_type*>(
 920                   index_node_type::from_impl(next_org->prior()))))->impl();
 921           }
 922           else{
 923             next_cpy->prior()=cpy;
 924           }
 925         }
 926         org=next_org;
 927         cpy=next_cpy;
 928       }while(org!=end_org);
 929     }
 930
 931     super::copy_(x,map);
 932   }
 933
 934   template<typename Variant>
 935   final_node_type* insert_(
 936     value_param_type v,final_node_type*& x,Variant variant)
 937   {
 938     reserve_for_insert(size()+1);
 939
 940     std::size_t buc=find_bucket(v);
 941     link_info   pos(buckets.at(buc));
 942     if(!link_point(v,pos)){
 943       return static_cast<final_node_type*>(
 944         index_node_type::from_impl(node_impl_type::pointer_from(pos)));
 945     }
 946
 947     final_node_type* res=super::insert_(v,x,variant);
 948     if(res==x)link(static_cast<index_node_type*>(x),pos);
 949     return res;
 950   }
 951
 952   template<typename Variant>
 953   final_node_type* insert_(
 954     value_param_type v,index_node_type* position,
 955     final_node_type*& x,Variant variant)
 956   {
 957     reserve_for_insert(size()+1);
 958
 959     std::size_t buc=find_bucket(v);
 960     link_info   pos(buckets.at(buc));
 961     if(!link_point(v,pos)){
 962       return static_cast<final_node_type*>(
 963         index_node_type::from_impl(node_impl_type::pointer_from(pos)));
 964     }
 965
 966     final_node_type* res=super::insert_(v,position,x,variant);
 967     if(res==x)link(static_cast<index_node_type*>(x),pos);
 968     return res;
 969   }
 970
 971   template<typename Dst>
 972   void extract_(index_node_type* x,Dst dst)
 973   {
 974     unlink(x);
 975     super::extract_(x,dst.next());
 976
 977 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 978     transfer_iterators(dst.get(),x);
 979 #endif
 980   }
 981
 982   void delete_all_nodes_()
 983   {
 984     delete_all_nodes_(Category());
 985   }
 986
 987   void delete_all_nodes_(hashed_unique_tag)
 988   {
 989     for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
 990       node_impl_pointer y=x->prior();
 991       this->final_delete_node_(
 992         static_cast<final_node_type*>(index_node_type::from_impl(x)));
 993       x=y;
 994     }
 995   }
 996
 997   void delete_all_nodes_(hashed_non_unique_tag)
 998   {
 999     for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
1000       node_impl_pointer y=x->prior();
1001       if(y->next()!=node_impl_type::base_pointer_from(x)&&
1002          y->next()->prior()!=x){ /* n-1 of group */
1003         /* Make the second node prior() pointer back-linked so that it won't
1004          * refer to a deleted node when the time for its own destruction comes.
1005          */
1006
1007         node_impl_pointer first=node_impl_type::pointer_from(y->next());
1008         first->next()->prior()=first;
1009       }
1010       this->final_delete_node_(
1011         static_cast<final_node_type*>(index_node_type::from_impl(x)));
1012       x=y;
1013     }
1014   }
1015
1016   void clear_()
1017   {
1018     super::clear_();
1019     buckets.clear(header()->impl());
1020
1021 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1022     safe.detach_dereferenceable_iterators();
1023 #endif
1024   }
1025
1026   template<typename BoolConstant>
1027   void swap_(
1028     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1029     BoolConstant swap_allocators)
1030   {
1031     adl_swap(key,x.key);
1032     adl_swap(hash_,x.hash_);
1033     adl_swap(eq_,x.eq_);
1034     buckets.swap(x.buckets,swap_allocators);
1035     std::swap(mlf,x.mlf);
1036     std::swap(max_load,x.max_load);
1037
1038 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1039     safe.swap(x.safe);
1040 #endif
1041
1042     super::swap_(x,swap_allocators);
1043   }
1044
1045   void swap_elements_(
1046     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
1047   {
1048     buckets.swap(x.buckets);
1049     std::swap(mlf,x.mlf);
1050     std::swap(max_load,x.max_load);
1051
1052 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1053     safe.swap(x.safe);
1054 #endif
1055
1056     super::swap_elements_(x);
1057   }
1058
1059   template<typename Variant>
1060   bool replace_(value_param_type v,index_node_type* x,Variant variant)
1061   {
1062     if(eq_(key(v),key(x->value()))){
1063       return super::replace_(v,x,variant);
1064     }
1065
1066     unlink_undo undo;
1067     unlink(x,undo);
1068
1069     BOOST_TRY{
1070       std::size_t  buc=find_bucket(v);
1071       link_info    pos(buckets.at(buc));
1072       if(link_point(v,pos)&&super::replace_(v,x,variant)){
1073         link(x,pos);
1074         return true;
1075       }
1076       undo();
1077       return false;
1078     }
1079     BOOST_CATCH(...){
1080       undo();
1081       BOOST_RETHROW;
1082     }
1083     BOOST_CATCH_END
1084   }
1085
1086   bool modify_(index_node_type* x)
1087   {
1088     std::size_t buc;
1089     bool        b;
1090     BOOST_TRY{
1091       buc=find_bucket(x->value());
1092       b=in_place(x->impl(),key(x->value()),buc);
1093     }
1094     BOOST_CATCH(...){
1095       extract_(x,invalidate_iterators());
1096       BOOST_RETHROW;
1097     }
1098     BOOST_CATCH_END
1099     if(!b){
1100       unlink(x);
1101       BOOST_TRY{
1102         link_info pos(buckets.at(buc));
1103         if(!link_point(x->value(),pos)){
1104           super::extract_(x,invalidate_iterators());
1105
1106 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1107           detach_iterators(x);
1108 #endif
1109           return false;
1110         }
1111         link(x,pos);
1112       }
1113       BOOST_CATCH(...){
1114         super::extract_(x,invalidate_iterators());
1115
1116 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1117       detach_iterators(x);
1118 #endif
1119
1120         BOOST_RETHROW;
1121       }
1122       BOOST_CATCH_END
1123     }
1124
1125     BOOST_TRY{
1126       if(!super::modify_(x)){
1127         unlink(x);
1128
1129 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1130         detach_iterators(x);
1131 #endif
1132         return false;
1133       }
1134       else return true;
1135     }
1136     BOOST_CATCH(...){
1137       unlink(x);
1138
1139 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1140       detach_iterators(x);
1141 #endif
1142
1143       BOOST_RETHROW;
1144     }
1145     BOOST_CATCH_END
1146   }
1147
1148   bool modify_rollback_(index_node_type* x)
1149   {
1150     std::size_t buc=find_bucket(x->value());
1151     if(in_place(x->impl(),key(x->value()),buc)){
1152       return super::modify_rollback_(x);
1153     }
1154
1155     unlink_undo undo;
1156     unlink(x,undo);
1157
1158     BOOST_TRY{
1159       link_info pos(buckets.at(buc));
1160       if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
1161         link(x,pos);
1162         return true;
1163       }
1164       undo();
1165       return false;
1166     }
1167     BOOST_CATCH(...){
1168       undo();
1169       BOOST_RETHROW;
1170     }
1171     BOOST_CATCH_END
1172   }
1173
1174   bool check_rollback_(index_node_type* x)const
1175   {
1176     std::size_t buc=find_bucket(x->value());
1177     return in_place(x->impl(),key(x->value()),buc)&&super::check_rollback_(x);
1178   }
1179
1180   /* comparison */
1181
1182 #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
1183   /* defect macro refers to class, not function, templates, but anyway */
1184
1185   template<typename K,typename H,typename P,typename S,typename T,typename C>
1186   friend bool operator==(
1187     const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y);
1188 #endif
1189
1190   bool equals(const hashed_index& x)const{return equals(x,Category());}
1191
1192   bool equals(const hashed_index& x,hashed_unique_tag)const
1193   {
1194     if(size()!=x.size())return false;
1195     for(const_iterator it=begin(),it_end=end(),it2_end=x.end();
1196         it!=it_end;++it){
1197       const_iterator it2=x.find(key(*it));
1198       if(it2==it2_end||!(*it==*it2))return false;
1199     }
1200     return true;
1201   }
1202
1203   bool equals(const hashed_index& x,hashed_non_unique_tag)const
1204   {
1205     if(size()!=x.size())return false;
1206     for(const_iterator it=begin(),it_end=end();it!=it_end;){
1207       const_iterator it2,it2_last;
1208       boost::tie(it2,it2_last)=x.equal_range(key(*it));
1209       if(it2==it2_last)return false;
1210
1211       const_iterator it_last=make_iterator(
1212         index_node_type::from_impl(end_of_range(it.get_node()->impl())));
1213       if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false;
1214
1215       /* From is_permutation code in
1216        * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
1217        */
1218
1219       for(;it!=it_last;++it,++it2){
1220         if(!(*it==*it2))break;
1221       }
1222       if(it!=it_last){
1223         for(const_iterator scan=it;scan!=it_last;++scan){
1224           if(std::find(it,scan,*scan)!=scan)continue;
1225           difference_type matches=std::count(it2,it2_last,*scan);
1226           if(matches==0||matches!=std::count(scan,it_last,*scan))return false;
1227         }
1228         it=it_last;
1229       }
1230     }
1231     return true;
1232   }
1233
1234 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1235   /* serialization */
1236
1237   template<typename Archive>
1238   void save_(
1239     Archive& ar,const unsigned int version,const index_saver_type& sm)const
1240   {
1241     ar<<serialization::make_nvp("position",buckets);
1242     super::save_(ar,version,sm);
1243   }
1244
1245   template<typename Archive>
1246   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1247   {
1248     ar>>serialization::make_nvp("position",buckets);
1249     super::load_(ar,version,lm);
1250   }
1251 #endif
1252
1253 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1254   /* invariant stuff */
1255
1256   bool invariant_()const
1257   {
1258     if(size()==0||begin()==end()){
1259       if(size()!=0||begin()!=end())return false;
1260     }
1261     else{
1262       size_type s0=0;
1263       for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1264       if(s0!=size())return false;
1265
1266       size_type s1=0;
1267       for(size_type buc=0;buc<bucket_count();++buc){
1268         size_type ss1=0;
1269         for(const_local_iterator it=begin(buc),it_end=end(buc);
1270             it!=it_end;++it,++ss1){
1271           if(find_bucket(*it)!=buc)return false;
1272         }
1273         if(ss1!=bucket_size(buc))return false;
1274         s1+=ss1;
1275       }
1276       if(s1!=size())return false;
1277     }
1278
1279     return super::invariant_();
1280   }
1281
1282   /* This forwarding function eases things for the boost::mem_fn construct
1283    * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1284    * final_check_invariant is already an inherited member function of index.
1285    */
1286   void check_invariant_()const{this->final_check_invariant_();}
1287 #endif
1288
1289 private:
1290   index_node_type* header()const{return this->final_header();}
1291
1292   std::size_t find_bucket(value_param_type v)const
1293   {
1294     return bucket(key(v));
1295   }
1296
1297   struct link_info_non_unique
1298   {
1299     link_info_non_unique(node_impl_base_pointer pos):
1300       first(pos),last(node_impl_base_pointer(0)){}
1301
1302     operator const node_impl_base_pointer&()const{return this->first;}
1303
1304     node_impl_base_pointer first,last;
1305   };
1306
1307   typedef typename mpl::if_<
1308     is_same<Category,hashed_unique_tag>,
1309     node_impl_base_pointer,
1310     link_info_non_unique
1311   >::type                                link_info;
1312
1313   bool link_point(value_param_type v,link_info& pos)
1314   {
1315     return link_point(v,pos,Category());
1316   }
1317
1318   bool link_point(
1319     value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1320   {
1321     for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1322         x=node_alg::after_local(x)){
1323       if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){
1324         pos=node_impl_type::base_pointer_from(x);
1325         return false;
1326       }
1327     }
1328     return true;
1329   }
1330
1331   bool link_point(
1332     value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
1333   {
1334     for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0);
1335         x=node_alg::next_to_inspect(x)){
1336       if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){
1337         pos.first=node_impl_type::base_pointer_from(x);
1338         pos.last=node_impl_type::base_pointer_from(last_of_range(x));
1339         return true;
1340       }
1341     }
1342     return true;
1343   }
1344
1345   node_impl_pointer last_of_range(node_impl_pointer x)const
1346   {
1347     return last_of_range(x,Category());
1348   }
1349
1350   node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1351   {
1352     return x;
1353   }
1354
1355   node_impl_pointer last_of_range(
1356     node_impl_pointer x,hashed_non_unique_tag)const
1357   {
1358     node_impl_base_pointer y=x->next();
1359     node_impl_pointer      z=y->prior();
1360     if(z==x){                      /* range of size 1 or 2 */
1361       node_impl_pointer yy=node_impl_type::pointer_from(y);
1362       return
1363         eq_(
1364           key(index_node_type::from_impl(x)->value()),
1365           key(index_node_type::from_impl(yy)->value()))?yy:x;
1366     }
1367     else if(z->prior()==x)               /* last of bucket */
1368       return x;
1369     else                                /* group of size>2 */
1370       return z;
1371   }
1372
1373   node_impl_pointer end_of_range(node_impl_pointer x)const
1374   {
1375     return end_of_range(x,Category());
1376   }
1377
1378   node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1379   {
1380     return node_alg::after(last_of_range(x));
1381   }
1382
1383   node_impl_pointer end_of_range(
1384     node_impl_pointer x,hashed_non_unique_tag)const
1385   {
1386     node_impl_base_pointer y=x->next();
1387     node_impl_pointer      z=y->prior();
1388     if(z==x){                      /* range of size 1 or 2 */
1389       node_impl_pointer yy=node_impl_type::pointer_from(y);
1390       if(!eq_(
1391            key(index_node_type::from_impl(x)->value()),
1392            key(index_node_type::from_impl(yy)->value())))yy=x;
1393       return yy->next()->prior()==yy?
1394                node_impl_type::pointer_from(yy->next()):
1395                yy->next()->prior();
1396     }
1397     else if(z->prior()==x)               /* last of bucket */
1398       return z;
1399     else                                /* group of size>2 */
1400       return z->next()->prior()==z?
1401                node_impl_type::pointer_from(z->next()):
1402                z->next()->prior();
1403   }
1404
1405   void link(index_node_type* x,const link_info& pos)
1406   {
1407     link(x,pos,Category());
1408   }
1409
1410   void link(index_node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1411   {
1412     node_alg::link(x->impl(),pos,header()->impl());
1413   }
1414
1415   void link(
1416     index_node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
1417   {
1418     if(pos.last==node_impl_base_pointer(0)){
1419       node_alg::link(x->impl(),pos.first,header()->impl());
1420     }
1421     else{
1422       node_alg::link(
1423         x->impl(),
1424         node_impl_type::pointer_from(pos.first),
1425         node_impl_type::pointer_from(pos.last));
1426     }
1427   }
1428
1429   void unlink(index_node_type* x)
1430   {
1431     node_alg::unlink(x->impl());
1432   }
1433
1434   typedef typename node_alg::unlink_undo unlink_undo;
1435
1436   void unlink(index_node_type* x,unlink_undo& undo)
1437   {
1438     node_alg::unlink(x->impl(),undo);
1439   }
1440
1441   void calculate_max_load()
1442   {
1443     float fml=mlf*static_cast<float>(bucket_count());
1444     max_load=(std::numeric_limits<size_type>::max)();
1445     if(max_load>fml)max_load=static_cast<size_type>(fml);
1446   }
1447
1448   void reserve_for_insert(size_type n)
1449   {
1450     if(n>max_load){
1451       size_type bc =(std::numeric_limits<size_type>::max)();
1452       float     fbc=1.0f+static_cast<float>(n)/mlf;
1453       if(bc>fbc)bc =static_cast<size_type>(fbc);
1454       unchecked_rehash(bc);
1455     }
1456   }
1457
1458   void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1459
1460   void unchecked_rehash(size_type n,hashed_unique_tag)
1461   {
1462     node_impl_type    cpy_end_node;
1463     node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1464                       end_=header()->impl();
1465     bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1466
1467     if(size()!=0){
1468       auto_space<
1469         std::size_t,allocator_type>       hashes(get_allocator(),size());
1470       auto_space<
1471         node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1472       std::size_t                         i=0,size_=size();
1473       bool                                within_bucket=false;
1474       BOOST_TRY{
1475         for(;i!=size_;++i){
1476           node_impl_pointer x=end_->prior();
1477
1478           /* only this can possibly throw */
1479           std::size_t h=hash_(key(index_node_type::from_impl(x)->value()));
1480
1481           hashes.data()[i]=h;
1482           node_ptrs.data()[i]=x;
1483           within_bucket=!node_alg::unlink_last(end_);
1484           node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1485         }
1486       }
1487       BOOST_CATCH(...){
1488         if(i!=0){
1489           std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1490           if(!within_bucket)prev_buc=~prev_buc;
1491
1492           for(std::size_t j=i;j--;){
1493             std::size_t       buc=buckets.position(hashes.data()[j]);
1494             node_impl_pointer x=node_ptrs.data()[j];
1495             if(buc==prev_buc)node_alg::append(x,end_);
1496             else node_alg::link(x,buckets.at(buc),end_);
1497             prev_buc=buc;
1498           }
1499         }
1500         BOOST_RETHROW;
1501       }
1502       BOOST_CATCH_END
1503     }
1504
1505     end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1506     end_->next()=cpy_end->next();
1507     end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1508     buckets.swap(buckets_cpy);
1509     calculate_max_load();
1510   }
1511
1512   void unchecked_rehash(size_type n,hashed_non_unique_tag)
1513   {
1514     node_impl_type    cpy_end_node;
1515     node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1516                       end_=header()->impl();
1517     bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1518
1519     if(size()!=0){
1520       auto_space<
1521         std::size_t,allocator_type>       hashes(get_allocator(),size());
1522       auto_space<
1523         node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1524       std::size_t                         i=0;
1525       bool                                within_bucket=false;
1526       BOOST_TRY{
1527         for(;;++i){
1528           node_impl_pointer x=end_->prior();
1529           if(x==end_)break;
1530
1531           /* only this can possibly throw */
1532           std::size_t h=hash_(key(index_node_type::from_impl(x)->value()));
1533
1534           hashes.data()[i]=h;
1535           node_ptrs.data()[i]=x;
1536           std::pair<node_impl_pointer,bool> p=
1537             node_alg::unlink_last_group(end_);
1538           node_alg::link_range(
1539             p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1540           within_bucket=!(p.second);
1541         }
1542       }
1543       BOOST_CATCH(...){
1544         if(i!=0){
1545           std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1546           if(!within_bucket)prev_buc=~prev_buc;
1547
1548           for(std::size_t j=i;j--;){
1549             std::size_t       buc=buckets.position(hashes.data()[j]);
1550             node_impl_pointer x=node_ptrs.data()[j],
1551                               y=
1552               x->prior()->next()!=node_impl_type::base_pointer_from(x)&&
1553               x->prior()->next()->prior()!=x?
1554                 node_impl_type::pointer_from(x->prior()->next()):x;
1555             node_alg::unlink_range(y,x);
1556             if(buc==prev_buc)node_alg::append_range(y,x,end_);
1557             else node_alg::link_range(y,x,buckets.at(buc),end_);
1558             prev_buc=buc;
1559           }
1560         }
1561         BOOST_RETHROW;
1562       }
1563       BOOST_CATCH_END
1564     }
1565
1566     end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1567     end_->next()=cpy_end->next();
1568     end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1569     buckets.swap(buckets_cpy);
1570     calculate_max_load();
1571   }
1572
1573   bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1574   {
1575     return in_place(x,k,buc,Category());
1576   }
1577
1578   bool in_place(
1579     node_impl_pointer x,key_param_type k,std::size_t buc,
1580     hashed_unique_tag)const
1581   {
1582     bool found=false;
1583     for(node_impl_pointer y=buckets.at(buc)->prior();
1584         y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1585       if(y==x)found=true;
1586       else if(eq_(k,key(index_node_type::from_impl(y)->value())))return false;
1587     }
1588     return found;
1589   }
1590
1591   bool in_place(
1592     node_impl_pointer x,key_param_type k,std::size_t buc,
1593     hashed_non_unique_tag)const
1594   {
1595     bool found=false;
1596     int  range_size=0;
1597     for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){
1598       if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
1599         if(y==x){
1600           /* in place <-> equal to some other member of the group */
1601           return eq_(
1602             k,
1603             key(index_node_type::from_impl(
1604               node_impl_type::pointer_from(y->next()))->value()));
1605         }
1606         else{
1607           node_impl_pointer z=
1608             node_alg::after_local(y->next()->prior()); /* end of range */
1609           if(eq_(k,key(index_node_type::from_impl(y)->value()))){
1610             if(found)return false; /* x lies outside */
1611             do{
1612               if(y==x)return true;
1613               y=node_alg::after_local(y);
1614             }while(y!=z);
1615             return false; /* x not found */
1616           }
1617           else{
1618             if(range_size==1&&!found)return false;
1619             if(range_size==2)return found;
1620             range_size=0;
1621             y=z; /* skip range (and potentially x, too, which is fine) */
1622           }
1623         }
1624       }
1625       else{ /* group of 1 or 2 */
1626         if(y==x){
1627           if(range_size==1)return true;
1628           range_size=1;
1629           found=true;
1630         }
1631         else if(eq_(k,key(index_node_type::from_impl(y)->value()))){
1632           if(range_size==0&&found)return false;
1633           if(range_size==1&&!found)return false;
1634           if(range_size==2)return false;
1635           ++range_size;
1636         }
1637         else{
1638           if(range_size==1&&!found)return false;
1639           if(range_size==2)return found;
1640           range_size=0;
1641         }
1642         y=node_alg::after_local(y);
1643       }
1644     }
1645     return found;
1646   }
1647
1648 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1649   void detach_iterators(index_node_type* x)
1650   {
1651     iterator it=make_iterator(x);
1652     safe_mode::detach_equivalent_iterators(it);
1653   }
1654
1655   template<typename Dst>
1656   void transfer_iterators(Dst& dst,index_node_type* x)
1657   {
1658     iterator it=make_iterator(x);
1659     safe_mode::transfer_equivalent_iterators(dst,it);
1660   }
1661 #endif
1662
1663   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1664   std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1665   {
1666     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1667     std::pair<final_node_type*,bool>p=
1668       this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1669     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1670   }
1671
1672   template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1673   iterator emplace_hint_impl(
1674     iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1675   {
1676     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1677     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1678     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1679     std::pair<final_node_type*,bool>p=
1680       this->final_emplace_hint_(
1681         static_cast<final_node_type*>(position.get_node()),
1682         BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1683     return make_iterator(p.first);
1684   }
1685
1686   template<
1687     typename CompatibleHash,typename CompatiblePred
1688   >
1689   iterator find(
1690     const key_type& k,
1691     const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1692   {
1693     return find(k,hash,eq,mpl::false_());
1694   }
1695
1696   template<
1697     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1698   >
1699   iterator find(
1700     const CompatibleKey& k,
1701     const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1702   {
1703     std::size_t buc=buckets.position(hash(k));
1704     for(node_impl_pointer x=buckets.at(buc)->prior();
1705         x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1706       if(eq(k,key(index_node_type::from_impl(x)->value()))){
1707         return make_iterator(index_node_type::from_impl(x));
1708       }
1709     }
1710     return end();
1711   }
1712
1713   template<
1714     typename CompatibleHash,typename CompatiblePred
1715   >
1716   size_type count(
1717     const key_type& k,
1718     const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1719   {
1720     return count(k,hash,eq,mpl::false_());
1721   }
1722
1723   template<
1724     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1725   >
1726   size_type count(
1727     const CompatibleKey& k,
1728     const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1729   {
1730     std::size_t buc=buckets.position(hash(k));
1731     for(node_impl_pointer x=buckets.at(buc)->prior();
1732         x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1733       if(eq(k,key(index_node_type::from_impl(x)->value()))){
1734         size_type         res=0;
1735         node_impl_pointer y=end_of_range(x);
1736         do{
1737           ++res;
1738           x=node_alg::after(x);
1739         }while(x!=y);
1740         return res;
1741       }
1742     }
1743     return 0;
1744   }
1745
1746   template<
1747     typename CompatibleHash,typename CompatiblePred
1748   >
1749   std::pair<iterator,iterator> equal_range(
1750     const key_type& k,
1751     const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1752   {
1753     return equal_range(k,hash,eq,mpl::false_());
1754   }
1755
1756   template<
1757     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1758   >
1759   std::pair<iterator,iterator> equal_range(
1760     const CompatibleKey& k,
1761     const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1762   {
1763     std::size_t buc=buckets.position(hash(k));
1764     for(node_impl_pointer x=buckets.at(buc)->prior();
1765         x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1766       if(eq(k,key(index_node_type::from_impl(x)->value()))){
1767         return std::pair<iterator,iterator>(
1768           make_iterator(index_node_type::from_impl(x)),
1769           make_iterator(index_node_type::from_impl(end_of_range(x))));
1770       }
1771     }
1772     return std::pair<iterator,iterator>(end(),end());
1773   }
1774
1775   key_from_value               key;
1776   hasher                       hash_;
1777   key_equal                    eq_;
1778   bucket_array_type            buckets;
1779   float                        mlf;
1780   size_type                    max_load;
1781
1782 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1783   safe_container               safe;
1784 #endif
1785
1786 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1787     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1788 #pragma parse_mfunc_templ reset
1789 #endif
1790 };
1791
1792 #if defined(BOOST_MSVC)
1793 #pragma warning(pop) /* C4355 */
1794 #endif
1795
1796 /* comparison */
1797
1798 template<
1799   typename KeyFromValue,typename Hash,typename Pred,
1800   typename SuperMeta,typename TagList,typename Category
1801 >
1802 bool operator==(
1803   const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1804   const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1805 {
1806   return x.equals(y);
1807 }
1808
1809 template<
1810   typename KeyFromValue,typename Hash,typename Pred,
1811   typename SuperMeta,typename TagList,typename Category
1812 >
1813 bool operator!=(
1814   const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1815   const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1816 {
1817   return !(x==y);
1818 }
1819
1820 /*  specialized algorithms */
1821
1822 template<
1823   typename KeyFromValue,typename Hash,typename Pred,
1824   typename SuperMeta,typename TagList,typename Category
1825 >
1826 void swap(
1827   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1828   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1829 {
1830   x.swap(y);
1831 }
1832
1833 } /* namespace multi_index::detail */
1834
1835 /* hashed index specifiers */
1836
1837 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1838 struct hashed_unique
1839 {
1840   typedef typename detail::hashed_index_args<
1841     Arg1,Arg2,Arg3,Arg4>                           index_args;
1842   typedef typename index_args::tag_list_type::type tag_list_type;
1843   typedef typename index_args::key_from_value_type key_from_value_type;
1844   typedef typename index_args::hash_type           hash_type;
1845   typedef typename index_args::pred_type           pred_type;
1846
1847   template<typename Super>
1848   struct node_class
1849   {
1850     typedef detail::hashed_index_node<Super> type;
1851   };
1852
1853   template<typename SuperMeta>
1854   struct index_class
1855   {
1856     typedef detail::hashed_index<
1857       key_from_value_type,hash_type,pred_type,
1858       SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1859   };
1860 };
1861
1862 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1863 struct hashed_non_unique
1864 {
1865   typedef typename detail::hashed_index_args<
1866     Arg1,Arg2,Arg3,Arg4>                           index_args;
1867   typedef typename index_args::tag_list_type::type tag_list_type;
1868   typedef typename index_args::key_from_value_type key_from_value_type;
1869   typedef typename index_args::hash_type           hash_type;
1870   typedef typename index_args::pred_type           pred_type;
1871
1872   template<typename Super>
1873   struct node_class
1874   {
1875     typedef detail::hashed_index_node<Super> type;
1876   };
1877
1878   template<typename SuperMeta>
1879   struct index_class
1880   {
1881     typedef detail::hashed_index<
1882       key_from_value_type,hash_type,pred_type,
1883       SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1884   };
1885 };
1886
1887 } /* namespace multi_index */
1888
1889 } /* namespace boost */
1890
1891 /* Boost.Foreach compatibility */
1892
1893 template<
1894   typename KeyFromValue,typename Hash,typename Pred,
1895   typename SuperMeta,typename TagList,typename Category
1896 >
1897 inline boost::mpl::true_* boost_foreach_is_noncopyable(
1898   boost::multi_index::detail::hashed_index<
1899     KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>*&,
1900   boost_foreach_argument_dependent_lookup_hack)
1901 {
1902   return 0;
1903 }
1904
1905 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1906 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF
1907
1908 #endif