boost/multi_index/hashed_index.hpp

   1 /* Copyright 2003-2007 Joaquín M López Muñoz.
   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)&&(_MSC_VER>=1200)
  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/limits.hpp>
  23 #include <boost/mpl/push_front.hpp>
  24 #include <boost/multi_index/detail/access_specifier.hpp>
  25 #include <boost/multi_index/detail/auto_space.hpp>
  26 #include <boost/multi_index/detail/bucket_array.hpp>
  27 #include <boost/multi_index/detail/hash_index_iterator.hpp>
  28 #include <boost/multi_index/detail/index_node_base.hpp>
  29 #include <boost/multi_index/detail/modify_key_adaptor.hpp>
  30 #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
  31 #include <boost/multi_index/detail/safe_mode.hpp>
  32 #include <boost/multi_index/detail/scope_guard.hpp>
  33 #include <boost/multi_index/hashed_index_fwd.hpp>
  34 #include <boost/tuple/tuple.hpp>
  35 #include <cstddef>
  36 #include <functional>
  37 #include <utility>
  38
  39 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
  40 #include <boost/serialization/nvp.hpp>
  41 #endif
  42
  43 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
  44 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \
  45   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
  46     detail::make_obj_guard(*this,&hashed_index::check_invariant_);           \
  47   BOOST_JOIN(check_invariant_,__LINE__).touch();
  48 #else
  49 #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
  50 #endif
  51
  52 namespace boost{
  53
  54 namespace multi_index{
  55
  56 namespace detail{
  57
  58 /* hashed_index adds a layer of hashed indexing to a given Super */
  59
  60 /* Most of the implementation of unique and non-unique indices is
  61  * shared. We tell from one another on instantiation time by using
  62  * these tags.
  63  */
  64
  65 struct hashed_unique_tag{};
  66 struct hashed_non_unique_tag{};
  67
  68 template<
  69   typename KeyFromValue,typename Hash,typename Pred,
  70   typename SuperMeta,typename TagList,typename Category
  71 >
  72 class hashed_index:
  73   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
  74
  75 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
  76 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
  77   ,public safe_ctr_proxy_impl<
  78     hashed_index_iterator<
  79       hashed_index_node<typename SuperMeta::type::node_type>,
  80       bucket_array<typename SuperMeta::type::final_allocator_type> >,
  81     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
  82 #else
  83   ,public safe_mode::safe_container<
  84     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
  85 #endif
  86 #endif
  87
  88 {
  89 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
  90     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
  91 /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
  92  * lifetime of const references bound to temporaries --precisely what
  93  * scopeguards are.
  94  */
  95
  96 #pragma parse_mfunc_templ off
  97 #endif
  98
  99   typedef typename SuperMeta::type                   super;
 100
 101 protected:
 102   typedef hashed_index_node<
 103     typename super::node_type>                       node_type;
 104
 105 private:
 106   typedef typename node_type::impl_type              node_impl_type;
 107   typedef typename node_impl_type::pointer           node_impl_pointer;
 108   typedef bucket_array<
 109     typename super::final_allocator_type>            bucket_array_type;
 110
 111 public:
 112   /* types */
 113
 114   typedef typename KeyFromValue::result_type         key_type;
 115   typedef typename node_type::value_type             value_type;
 116   typedef KeyFromValue                               key_from_value;
 117   typedef Hash                                       hasher;
 118   typedef Pred                                       key_equal;
 119   typedef tuple<std::size_t,
 120     key_from_value,hasher,key_equal>                 ctor_args;
 121   typedef typename super::final_allocator_type       allocator_type;
 122   typedef typename allocator_type::pointer           pointer;
 123   typedef typename allocator_type::const_pointer     const_pointer;
 124   typedef typename allocator_type::reference         reference;
 125   typedef typename allocator_type::const_reference   const_reference;
 126   typedef std::size_t                                size_type;
 127   typedef std::ptrdiff_t                             difference_type;
 128
 129 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 130 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 131   typedef safe_mode::safe_iterator<
 132     hashed_index_iterator<
 133       node_type,bucket_array_type>,
 134     safe_ctr_proxy<
 135       hashed_index_iterator<
 136         node_type,bucket_array_type> > >             iterator;
 137 #else
 138   typedef safe_mode::safe_iterator<
 139     hashed_index_iterator<
 140       node_type,bucket_array_type>,
 141     hashed_index>                                    iterator;
 142 #endif
 143 #else
 144   typedef hashed_index_iterator<
 145     node_type,bucket_array_type>                     iterator;
 146 #endif
 147
 148   typedef iterator                                   const_iterator;
 149
 150   typedef iterator                                   local_iterator;
 151   typedef const_iterator                             const_local_iterator;
 152   typedef TagList                                    tag_list;
 153
 154 protected:
 155   typedef typename super::final_node_type     final_node_type;
 156   typedef tuples::cons<
 157     ctor_args,
 158     typename super::ctor_args_list>           ctor_args_list;
 159   typedef typename mpl::push_front<
 160     typename super::index_type_list,
 161     hashed_index>::type                       index_type_list;
 162   typedef typename mpl::push_front<
 163     typename super::iterator_type_list,
 164     iterator>::type                           iterator_type_list;
 165   typedef typename mpl::push_front<
 166     typename super::const_iterator_type_list,
 167     const_iterator>::type                     const_iterator_type_list;
 168   typedef typename super::copy_map_type       copy_map_type;
 169
 170 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 171   typedef typename super::index_saver_type    index_saver_type;
 172   typedef typename super::index_loader_type   index_loader_type;
 173 #endif
 174
 175 private:
 176 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 177 #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
 178   typedef safe_ctr_proxy_impl<
 179     hashed_index_iterator<
 180       node_type,bucket_array_type>,
 181     hashed_index>                             safe_super;
 182 #else
 183   typedef safe_mode::safe_container<
 184     hashed_index>                             safe_super;
 185 #endif
 186 #endif
 187
 188   typedef typename call_traits<value_type>::param_type value_param_type;
 189   typedef typename call_traits<
 190     key_type>::param_type                              key_param_type;
 191
 192 public:
 193
 194   /* construct/destroy/copy
 195    * Default and copy ctors are in the protected section as indices are
 196    * not supposed to be created on their own. No range ctor either.
 197    */
 198
 199   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
 200     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
 201   {
 202     this->final()=x.final();
 203     return *this;
 204   }
 205
 206   allocator_type get_allocator()const
 207   {
 208     return this->final().get_allocator();
 209   }
 210
 211   /* size and capacity */
 212
 213   bool      empty()const{return this->final_empty_();}
 214   size_type size()const{return this->final_size_();}
 215   size_type max_size()const{return this->final_max_size_();}
 216
 217   /* iterators */
 218
 219   iterator begin()
 220   {
 221     return make_iterator(
 222       node_type::from_impl(buckets.at(first_bucket)->next()));
 223   }
 224
 225   const_iterator begin()const
 226   {
 227     return make_iterator(
 228       node_type::from_impl(buckets.at(first_bucket)->next()));
 229   }
 230
 231   iterator       end(){return make_iterator(header());}
 232   const_iterator end()const{return make_iterator(header());}
 233
 234   const_iterator cbegin()const{return begin();}
 235   const_iterator cend()const{return end();}
 236
 237   iterator iterator_to(const value_type& x)
 238   {
 239     return make_iterator(node_from_value<node_type>(&x));
 240   }
 241
 242   const_iterator iterator_to(const value_type& x)const
 243   {
 244     return make_iterator(node_from_value<node_type>(&x));
 245   }
 246
 247   /* modifiers */
 248
 249   std::pair<iterator,bool> insert(value_param_type x)
 250   {
 251     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 252     std::pair<final_node_type*,bool> p=this->final_insert_(x);
 253     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
 254   }
 255
 256   iterator insert(iterator position,value_param_type x)
 257   {
 258     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 259     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 260     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 261     std::pair<final_node_type*,bool> p=this->final_insert_(
 262       x,static_cast<final_node_type*>(position.get_node()));
 263     return make_iterator(p.first);
 264   }
 265
 266   template<typename InputIterator>
 267   void insert(InputIterator first,InputIterator last)
 268   {
 269     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 270     iterator hint=end();
 271     for(;first!=last;++first)hint=insert(hint,*first);
 272   }
 273
 274   iterator erase(iterator position)
 275   {
 276     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 277     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 278     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 279     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 280     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
 281     return position;
 282   }
 283
 284   size_type erase(key_param_type k)
 285   {
 286     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 287
 288     size_type         s=0;
 289     std::size_t       buc=buckets.position(hash(k));
 290     node_impl_pointer x=buckets.at(buc);
 291     node_impl_pointer y=x->next();
 292     while(y!=x){
 293       if(eq(k,key(node_type::from_impl(y)->value()))){
 294         bool b;
 295         do{
 296           node_impl_pointer z=y->next();
 297           b=z!=x&&eq(
 298             key(node_type::from_impl(y)->value()),
 299             key(node_type::from_impl(z)->value()));
 300           this->final_erase_(
 301             static_cast<final_node_type*>(node_type::from_impl(y)));
 302           y=z;
 303           ++s;
 304         }while(b);
 305         break;
 306       }
 307       y=y->next();
 308     }
 309     return s;
 310   }
 311
 312   iterator erase(iterator first,iterator last)
 313   {
 314     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
 315     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
 316     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
 317     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
 318     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
 319     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 320     while(first!=last){
 321       first=erase(first);
 322     }
 323     return first;
 324   }
 325
 326   bool replace(iterator position,value_param_type x)
 327   {
 328     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 329     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 330     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 331     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 332     return this->final_replace_(
 333       x,static_cast<final_node_type*>(position.get_node()));
 334   }
 335
 336   template<typename Modifier>
 337   bool modify(iterator position,Modifier mod)
 338   {
 339     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 340     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 341     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 342     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 343
 344 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 345     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 346      * this is not added. Left it for all compilers as it does no
 347      * harm.
 348      */
 349
 350     position.detach();
 351 #endif
 352
 353     return this->final_modify_(
 354       mod,static_cast<final_node_type*>(position.get_node()));
 355   }
 356
 357   template<typename Modifier,typename Rollback>
 358   bool modify(iterator position,Modifier mod,Rollback back)
 359   {
 360     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 361     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 362     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 363     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 364
 365 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 366     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
 367      * this is not added. Left it for all compilers as it does no
 368      * harm.
 369      */
 370
 371     position.detach();
 372 #endif
 373
 374     return this->final_modify_(
 375       mod,back,static_cast<final_node_type*>(position.get_node()));
 376   }
 377
 378   template<typename Modifier>
 379   bool modify_key(iterator position,Modifier mod)
 380   {
 381     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 382     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 383     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 384     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 385     return modify(
 386       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
 387   }
 388
 389   template<typename Modifier,typename Rollback>
 390   bool modify_key(iterator position,Modifier mod,Rollback back)
 391   {
 392     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
 393     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
 394     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
 395     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 396     return modify(
 397       position,
 398       modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
 399       modify_key_adaptor<Modifier,value_type,KeyFromValue>(back,key));
 400   }
 401
 402   void clear()
 403   {
 404     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 405     this->final_clear_();
 406   }
 407
 408   void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
 409   {
 410     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 411     this->final_swap_(x.final());
 412   }
 413
 414   /* observers */
 415
 416   key_from_value key_extractor()const{return key;}
 417   hasher         hash_function()const{return hash;}
 418   key_equal      key_eq()const{return eq;}
 419
 420   /* lookup */
 421
 422   /* Internally, these ops rely on const_iterator being the same
 423    * type as iterator.
 424    */
 425
 426   template<typename CompatibleKey>
 427   iterator find(const CompatibleKey& k)const
 428   {
 429     return find(k,hash,eq);
 430   }
 431
 432   template<
 433     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 434   >
 435   iterator find(
 436     const CompatibleKey& k,
 437     const CompatibleHash& hash,const CompatiblePred& eq)const
 438   {
 439     std::size_t       buc=buckets.position(hash(k));
 440     node_impl_pointer x=buckets.at(buc);
 441     node_impl_pointer y=x->next();
 442     while(y!=x){
 443       if(eq(k,key(node_type::from_impl(y)->value()))){
 444         return make_iterator(node_type::from_impl(y));
 445       }
 446       y=y->next();
 447     }
 448     return end();
 449   }
 450
 451   template<typename CompatibleKey>
 452   size_type count(const CompatibleKey& k)const
 453   {
 454     return count(k,hash,eq);
 455   }
 456
 457   template<
 458     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 459   >
 460   size_type count(
 461     const CompatibleKey& k,
 462     const CompatibleHash& hash,const CompatiblePred& eq)const
 463   {
 464     size_type         res=0;
 465     std::size_t       buc=buckets.position(hash(k));
 466     node_impl_pointer x=buckets.at(buc);
 467     node_impl_pointer y=x->next();
 468     while(y!=x){
 469       if(eq(k,key(node_type::from_impl(y)->value()))){
 470         do{
 471           ++res;
 472           y=y->next();
 473         }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
 474         break;
 475       }
 476       y=y->next();
 477     }
 478     return res;
 479   }
 480
 481   template<typename CompatibleKey>
 482   std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
 483   {
 484     return equal_range(k,hash,eq);
 485   }
 486
 487   template<
 488     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
 489   >
 490   std::pair<iterator,iterator> equal_range(
 491     const CompatibleKey& k,
 492     const CompatibleHash& hash,const CompatiblePred& eq)const
 493   {
 494     std::size_t       buc=buckets.position(hash(k));
 495     node_impl_pointer x=buckets.at(buc);
 496     node_impl_pointer y=x->next();
 497     while(y!=x){
 498       if(eq(k,key(node_type::from_impl(y)->value()))){
 499         node_impl_pointer y0=y;
 500         do{
 501           y=y->next();
 502         }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
 503         if(y==x){
 504           do{
 505             ++y;
 506           }while(y==y->next());
 507           y=y->next();
 508         }
 509         return std::pair<iterator,iterator>(
 510           make_iterator(node_type::from_impl(y0)),
 511           make_iterator(node_type::from_impl(y)));
 512       }
 513       y=y->next();
 514     }
 515     return std::pair<iterator,iterator>(end(),end());
 516   }
 517
 518   /* bucket interface */
 519
 520   size_type bucket_count()const{return buckets.size();}
 521   size_type max_bucket_count()const{return static_cast<size_type>(-1);}
 522
 523   size_type bucket_size(size_type n)const
 524   {
 525     size_type         res=0;
 526     node_impl_pointer x=buckets.at(n);
 527     node_impl_pointer y=x->next();
 528     while(y!=x){
 529       ++res;
 530       y=y->next();
 531     }
 532     return res;
 533   }
 534
 535   size_type bucket(key_param_type k)const
 536   {
 537     return buckets.position(hash(k));
 538   }
 539
 540   local_iterator begin(size_type n)
 541   {
 542     return const_cast<const hashed_index*>(this)->begin(n);
 543   }
 544
 545   const_local_iterator begin(size_type n)const
 546   {
 547     node_impl_pointer x=buckets.at(n);
 548     node_impl_pointer y=x->next();
 549     if(y==x)return end();
 550     return make_iterator(node_type::from_impl(y));
 551   }
 552
 553   local_iterator end(size_type n)
 554   {
 555     return const_cast<const hashed_index*>(this)->end(n);
 556   }
 557
 558   const_local_iterator end(size_type n)const
 559   {
 560     node_impl_pointer x=buckets.at(n);
 561     if(x==x->next())return end();
 562     do{
 563       ++x;
 564     }while(x==x->next());
 565     return make_iterator(node_type::from_impl(x->next()));
 566   }
 567
 568   const_local_iterator cbegin(size_type n)const{return begin(n);}
 569   const_local_iterator cend(size_type n)const{return end(n);}
 570
 571   local_iterator local_iterator_to(const value_type& x)
 572   {
 573     return make_iterator(node_from_value<node_type>(&x));
 574   }
 575
 576   const_local_iterator local_iterator_to(const value_type& x)const
 577   {
 578     return make_iterator(node_from_value<node_type>(&x));
 579   }
 580
 581   /* hash policy */
 582
 583   float load_factor()const{return static_cast<float>(size())/bucket_count();}
 584   float max_load_factor()const{return mlf;}
 585   void  max_load_factor(float z){mlf=z;calculate_max_load();}
 586
 587   void rehash(size_type n)
 588   {
 589     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
 590     if(size()<max_load&&n<=bucket_count())return;
 591
 592     size_type bc =(std::numeric_limits<size_type>::max)();
 593     float     fbc=static_cast<float>(1+size()/mlf);
 594     if(bc>fbc){
 595       bc=static_cast<size_type>(fbc);
 596       if(bc<n)bc=n;
 597     }
 598     unchecked_rehash(bc);
 599   }
 600
 601 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
 602   hashed_index(const ctor_args_list& args_list,const allocator_type& al):
 603     super(args_list.get_tail(),al),
 604     key(tuples::get<1>(args_list.get_head())),
 605     hash(tuples::get<2>(args_list.get_head())),
 606     eq(tuples::get<3>(args_list.get_head())),
 607     buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
 608     mlf(1.0),
 609     first_bucket(buckets.size())
 610   {
 611     calculate_max_load();
 612   }
 613
 614   hashed_index(
 615     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
 616     super(x),
 617
 618 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 619     safe_super(),
 620 #endif
 621
 622     key(x.key),
 623     hash(x.hash),
 624     eq(x.eq),
 625     buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
 626     mlf(x.mlf),
 627     max_load(x.max_load),
 628     first_bucket(x.first_bucket)
 629   {
 630     /* Copy ctor just takes the internal configuration objects from x. The rest
 631      * is done in subsequent call to copy_().
 632      */
 633   }
 634
 635   ~hashed_index()
 636   {
 637     /* the container is guaranteed to be empty by now */
 638   }
 639
 640 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 641   iterator make_iterator(node_type* node)
 642   {
 643     return iterator(node,&buckets,this);
 644   }
 645
 646   const_iterator make_iterator(node_type* node)const
 647   {
 648     return const_iterator(
 649       node,
 650       &const_cast<bucket_array_type&>(buckets),
 651       const_cast<hashed_index*>(this));
 652   }
 653 #else
 654   iterator make_iterator(node_type* node)
 655   {
 656     return iterator(node,&buckets);
 657   }
 658
 659   const_iterator make_iterator(node_type* node)const
 660   {
 661     return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
 662   }
 663 #endif
 664
 665   void copy_(
 666     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
 667     const copy_map_type& map)
 668   {
 669     for(node_impl_pointer begin_org=x.buckets.begin(),
 670                           begin_cpy=buckets.begin(),
 671                           end_org=x.buckets.end();
 672         begin_org!=end_org;++begin_org,++begin_cpy){
 673
 674       node_impl_pointer next_org=begin_org->next();
 675       node_impl_pointer cpy=begin_cpy;
 676       while(next_org!=begin_org){
 677         cpy->next()=
 678           static_cast<node_type*>(
 679             map.find(
 680               static_cast<final_node_type*>(
 681                 node_type::from_impl(next_org))))->impl();
 682         next_org=next_org->next();
 683         cpy=cpy->next();
 684       }
 685       cpy->next()=begin_cpy;
 686     }
 687
 688     super::copy_(x,map);
 689   }
 690
 691   node_type* insert_(value_param_type v,node_type* x)
 692   {
 693     reserve(size()+1);
 694
 695     std::size_t       buc=find_bucket(v);
 696     node_impl_pointer pos=buckets.at(buc);
 697     if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
 698
 699     node_type* res=static_cast<node_type*>(super::insert_(v,x));
 700     if(res==x){
 701       link(x,pos);
 702       if(first_bucket>buc)first_bucket=buc;
 703     }
 704     return res;
 705   }
 706
 707   node_type* insert_(value_param_type v,node_type* position,node_type* x)
 708   {
 709     reserve(size()+1);
 710
 711     std::size_t       buc=find_bucket(v);
 712     node_impl_pointer pos=buckets.at(buc);
 713     if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
 714
 715     node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
 716     if(res==x){
 717       link(x,pos);
 718       if(first_bucket>buc)first_bucket=buc;
 719     }
 720     return res;
 721   }
 722
 723   void erase_(node_type* x)
 724   {
 725     unlink(x);
 726     first_bucket=buckets.first_nonempty(first_bucket);
 727     super::erase_(x);
 728
 729 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 730     detach_iterators(x);
 731 #endif
 732   }
 733
 734   void delete_all_nodes_()
 735   {
 736     for(node_impl_pointer x=buckets.begin(),x_end=buckets.end();
 737         x!=x_end;++x){
 738       node_impl_pointer y=x->next();
 739       while(y!=x){
 740         node_impl_pointer z=y->next();
 741         this->final_delete_node_(
 742           static_cast<final_node_type*>(node_type::from_impl(y)));
 743         y=z;
 744       }
 745     }
 746   }
 747
 748   void clear_()
 749   {
 750     super::clear_();
 751     buckets.clear();
 752     first_bucket=buckets.size();
 753
 754 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 755     safe_super::detach_dereferenceable_iterators();
 756 #endif
 757   }
 758
 759   void swap_(
 760     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
 761   {
 762     std::swap(key,x.key);
 763     std::swap(hash,x.hash);
 764     std::swap(eq,x.eq);
 765     buckets.swap(x.buckets);
 766     std::swap(mlf,x.mlf);
 767     std::swap(max_load,x.max_load);
 768     std::swap(first_bucket,x.first_bucket);
 769
 770 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 771     safe_super::swap(x);
 772 #endif
 773
 774     super::swap_(x);
 775   }
 776
 777   bool replace_(value_param_type v,node_type* x)
 778   {
 779     if(eq(key(v),key(x->value()))){
 780       return super::replace_(v,x);
 781     }
 782
 783     node_impl_pointer y=prev(x);
 784     unlink_next(y);
 785
 786     BOOST_TRY{
 787       std::size_t       buc=find_bucket(v);
 788       node_impl_pointer pos=buckets.at(buc);
 789       if(link_point(v,pos,Category())&&super::replace_(v,x)){
 790         link(x,pos);
 791         if(first_bucket>buc){
 792           first_bucket=buc;
 793         }
 794         else if(first_bucket<buc){
 795           first_bucket=buckets.first_nonempty(first_bucket);
 796         }
 797         return true;
 798       }
 799       link(x,y);
 800       return false;
 801     }
 802     BOOST_CATCH(...){
 803       link(x,y);
 804       BOOST_RETHROW;
 805     }
 806     BOOST_CATCH_END
 807   }
 808
 809   bool modify_(node_type* x)
 810   {
 811     unlink(x);
 812
 813     std::size_t       buc;
 814     node_impl_pointer pos;
 815     BOOST_TRY
 816     {
 817       buc=find_bucket(x->value());
 818       pos=buckets.at(buc);
 819       if(!link_point(x->value(),pos,Category())){
 820         first_bucket=buckets.first_nonempty(first_bucket);
 821         super::erase_(x);
 822
 823 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 824         detach_iterators(x);
 825 #endif
 826         return false;
 827       }
 828
 829     }
 830     BOOST_CATCH(...){
 831       first_bucket=buckets.first_nonempty(first_bucket);
 832       super::erase_(x);
 833
 834 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 835       detach_iterators(x);
 836 #endif
 837
 838       BOOST_RETHROW;
 839     }
 840     BOOST_CATCH_END
 841
 842     BOOST_TRY{
 843       if(super::modify_(x)){
 844         link(x,pos);
 845         if(first_bucket>buc){
 846           first_bucket=buc;
 847         }
 848         else if(first_bucket<buc){
 849           first_bucket=buckets.first_nonempty(first_bucket);
 850         }
 851         return true;
 852       }
 853
 854       first_bucket=buckets.first_nonempty(first_bucket);
 855
 856 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 857       detach_iterators(x);
 858 #endif
 859       return false;
 860     }
 861     BOOST_CATCH(...){
 862       first_bucket=buckets.first_nonempty(first_bucket);
 863
 864 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
 865       detach_iterators(x);
 866 #endif
 867
 868       BOOST_RETHROW;
 869     }
 870     BOOST_CATCH_END
 871   }
 872
 873   bool modify_rollback_(node_type* x)
 874   {
 875     node_impl_pointer y=prev(x);
 876     unlink_next(y);
 877
 878     BOOST_TRY{
 879       std::size_t             buc=find_bucket(x->value());
 880       node_impl_pointer pos=buckets.at(buc);
 881       if(link_point(x->value(),pos,Category())&&super::modify_rollback_(x)){
 882         link(x,pos);
 883         if(first_bucket>buc){
 884           first_bucket=buc;
 885         }
 886         else if(first_bucket<buc){
 887           first_bucket=buckets.first_nonempty(first_bucket);
 888         }
 889         return true;
 890       }
 891       link(x,y);
 892       return false;
 893     }
 894     BOOST_CATCH(...){
 895       link(x,y);
 896       BOOST_RETHROW;
 897     }
 898     BOOST_CATCH_END
 899   }
 900
 901 #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
 902   /* serialization */
 903
 904   template<typename Archive>
 905   void save_(
 906     Archive& ar,const unsigned int version,const index_saver_type& sm)const
 907   {
 908     ar<<serialization::make_nvp("position",buckets);
 909     super::save_(ar,version,sm);
 910   }
 911
 912   template<typename Archive>
 913   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
 914   {
 915     ar>>serialization::make_nvp("position",buckets);
 916     super::load_(ar,version,lm);
 917   }
 918 #endif
 919
 920 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
 921   /* invariant stuff */
 922
 923   bool invariant_()const
 924   {
 925     if(size()==0||begin()==end()){
 926       if(size()!=0||begin()!=end())return false;
 927     }
 928     else{
 929       size_type s0=0;
 930       for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
 931       if(s0!=size())return false;
 932
 933       size_type s1=0;
 934       for(size_type buc=0;buc<bucket_count();++buc){
 935         size_type ss1=0;
 936         for(const_local_iterator it=begin(buc),it_end=end(buc);
 937             it!=it_end;++it,++ss1){
 938           if(find_bucket(*it)!=buc)return false;
 939         }
 940         if(ss1!=bucket_size(buc))return false;
 941         s1+=ss1;
 942       }
 943       if(s1!=size())return false;
 944     }
 945
 946     if(first_bucket!=buckets.first_nonempty(0))return false;
 947
 948     return super::invariant_();
 949   }
 950
 951   /* This forwarding function eases things for the boost::mem_fn construct
 952    * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
 953    * final_check_invariant is already an inherited member function of index.
 954    */
 955   void check_invariant_()const{this->final_check_invariant_();}
 956 #endif
 957
 958 private:
 959   node_type* header()const{return this->final_header();}
 960
 961   std::size_t find_bucket(value_param_type v)const
 962   {
 963     return bucket(key(v));
 964   }
 965
 966   bool link_point(
 967     value_param_type v,node_impl_pointer& pos,hashed_unique_tag)
 968   {
 969     node_impl_pointer x=pos->next();
 970     while(x!=pos){
 971       if(eq(key(v),key(node_type::from_impl(x)->value()))){
 972         pos=x;
 973         return false;
 974       }
 975       x=x->next();
 976     }
 977     return true;
 978   }
 979
 980   bool link_point(
 981     value_param_type v,node_impl_pointer& pos,hashed_non_unique_tag)
 982   {
 983     node_impl_pointer prev=pos;
 984     node_impl_pointer x=pos->next();
 985     while(x!=pos){
 986       if(eq(key(v),key(node_type::from_impl(x)->value()))){
 987         pos=prev;
 988         return true;
 989       }
 990       prev=x;
 991       x=x->next();
 992     }
 993     return true;
 994   }
 995
 996   void link(node_type* x,node_impl_pointer pos)
 997   {
 998     node_impl_type::link(x->impl(),pos);
 999   };
1000
1001   void link(node_impl_pointer x,node_impl_pointer pos)
1002   {
1003     node_impl_type::link(x,pos);
1004   };
1005
1006   void unlink(node_type* x)
1007   {
1008     node_impl_type::unlink(x->impl());
1009   };
1010
1011   static node_impl_pointer prev(node_type* x)
1012   {
1013     return node_impl_type::prev(x->impl());
1014   }
1015
1016   static void unlink_next(node_impl_pointer x)
1017   {
1018     node_impl_type::unlink_next(x);
1019   }
1020
1021   void calculate_max_load()
1022   {
1023     float fml=static_cast<float>(mlf*bucket_count());
1024     max_load=(std::numeric_limits<size_type>::max)();
1025     if(max_load>fml)max_load=static_cast<size_type>(fml);
1026   }
1027
1028   void reserve(size_type n)
1029   {
1030     if(n>max_load){
1031       size_type bc =(std::numeric_limits<size_type>::max)();
1032       float     fbc=static_cast<float>(1+n/mlf);
1033       if(bc>fbc)bc =static_cast<size_type>(fbc);
1034       unchecked_rehash(bc);
1035     }
1036   }
1037
1038   void unchecked_rehash(size_type n)
1039   {
1040     bucket_array_type buckets1(get_allocator(),header()->impl(),n);
1041     auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
1042
1043     std::size_t i=0;
1044     node_impl_pointer x=buckets.begin();
1045     node_impl_pointer x_end=buckets.end();
1046     for(;x!=x_end;++x){
1047       node_impl_pointer y=x->next();
1048       while(y!=x){
1049         hashes.data()[i++]=hash(key(node_type::from_impl(y)->value()));
1050         y=y->next();
1051       }
1052     }
1053
1054     i=0;
1055     x=buckets.begin();
1056     for(;x!=x_end;++x){
1057       node_impl_pointer y=x->next();
1058       while(y!=x){
1059         node_impl_pointer z=y->next();
1060         std::size_t       buc1=buckets1.position(hashes.data()[i++]);
1061         node_impl_pointer x1=buckets1.at(buc1);
1062         link(y,x1);
1063         y=z;
1064       }
1065     }
1066
1067     buckets.swap(buckets1);
1068     calculate_max_load();
1069     first_bucket=buckets.first_nonempty(0);
1070   }
1071
1072 #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1073   void detach_iterators(node_type* x)
1074   {
1075     iterator it=make_iterator(x);
1076     safe_mode::detach_equivalent_iterators(it);
1077   }
1078 #endif
1079
1080   key_from_value               key;
1081   hasher                       hash;
1082   key_equal                    eq;
1083   bucket_array_type            buckets;
1084   float                        mlf;
1085   size_type                    max_load;
1086   std::size_t                  first_bucket;
1087
1088 #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1089     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1090 #pragma parse_mfunc_templ reset
1091 #endif
1092 };
1093
1094 /*  specialized algorithms */
1095
1096 template<
1097   typename KeyFromValue,typename Hash,typename Pred,
1098   typename SuperMeta,typename TagList,typename Category
1099 >
1100 void swap(
1101   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1102   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1103 {
1104   x.swap(y);
1105 }
1106
1107 } /* namespace multi_index::detail */
1108
1109 /* hashed index specifiers */
1110
1111 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1112 struct hashed_unique
1113 {
1114   typedef typename detail::hashed_index_args<
1115     Arg1,Arg2,Arg3,Arg4>                           index_args;
1116   typedef typename index_args::tag_list_type::type tag_list_type;
1117   typedef typename index_args::key_from_value_type key_from_value_type;
1118   typedef typename index_args::hash_type           hash_type;
1119   typedef typename index_args::pred_type           pred_type;
1120
1121   template<typename Super>
1122   struct node_class
1123   {
1124     typedef detail::hashed_index_node<Super> type;
1125   };
1126
1127   template<typename SuperMeta>
1128   struct index_class
1129   {
1130     typedef detail::hashed_index<
1131       key_from_value_type,hash_type,pred_type,
1132       SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1133   };
1134 };
1135
1136 template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1137 struct hashed_non_unique
1138 {
1139   typedef typename detail::hashed_index_args<
1140     Arg1,Arg2,Arg3,Arg4>                           index_args;
1141   typedef typename index_args::tag_list_type::type tag_list_type;
1142   typedef typename index_args::key_from_value_type key_from_value_type;
1143   typedef typename index_args::hash_type           hash_type;
1144   typedef typename index_args::pred_type           pred_type;
1145
1146   template<typename Super>
1147   struct node_class
1148   {
1149     typedef detail::hashed_index_node<Super> type;
1150   };
1151
1152   template<typename SuperMeta>
1153   struct index_class
1154   {
1155     typedef detail::hashed_index<
1156       key_from_value_type,hash_type,pred_type,
1157       SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1158   };
1159 };
1160
1161 } /* namespace multi_index */
1162
1163 } /* namespace boost */
1164
1165 #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1166
1167 #endif