boost/multi_index/hashed_index.hpp

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