/* Copyright 2003-2007 Joaquín M López Muñoz.

 * Distributed under the Boost Software License, Version 1.0.

 * (See accompanying file LICENSE_1_0.txt or copy at

 * http://www.boost.org/LICENSE_1_0.txt)

 *

 * See http://www.boost.org/libs/multi_index for library home page.

 */

#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP

#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP

#if defined(_MSC_VER)&&(_MSC_VER>=1200)

#pragma once

#endif

#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */

#include <algorithm>

#include <boost/call_traits.hpp>

#include <boost/detail/allocator_utilities.hpp>

#include <boost/detail/no_exceptions_support.hpp>

#include <boost/detail/workaround.hpp>

#include <boost/limits.hpp>

#include <boost/mpl/push_front.hpp>

#include <boost/multi_index/detail/access_specifier.hpp>

#include <boost/multi_index/detail/auto_space.hpp>

#include <boost/multi_index/detail/bucket_array.hpp>

#include <boost/multi_index/detail/hash_index_iterator.hpp>

#include <boost/multi_index/detail/modify_key_adaptor.hpp>

#include <boost/multi_index/detail/safe_ctr_proxy.hpp>

#include <boost/multi_index/detail/safe_mode.hpp>

#include <boost/multi_index/detail/scope_guard.hpp>

#include <boost/multi_index/hashed_index_fwd.hpp>

#include <boost/tuple/tuple.hpp>

#include <cstddef>

#include <functional>

#include <utility>

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

#include <boost/serialization/nvp.hpp>

#endif

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)

#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \

  detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \

    detail::make_obj_guard(*this,&hashed_index::check_invariant_);           \

  BOOST_JOIN(check_invariant_,__LINE__).touch();

#else

#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT

#endif

namespace boost{

namespace multi_index{

namespace detail{

/* hashed_index adds a layer of hashed indexing to a given Super */

/* Most of the implementation of unique and non-unique indices is

 * shared. We tell from one another on instantiation time by using

 * these tags.

 */

struct hashed_unique_tag{};

struct hashed_non_unique_tag{};

template<

  typename KeyFromValue,typename Hash,typename Pred,

  typename SuperMeta,typename TagList,typename Category

>

class hashed_index:

  BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

#if BOOST_WORKAROUND(BOOST_MSVC,<1300)

  ,public safe_ctr_proxy_impl<

    hashed_index_iterator<

      hashed_index_node<typename SuperMeta::type::node_type>,

      bucket_array<typename SuperMeta::type::final_allocator_type> >,

    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >

#else

  ,public safe_mode::safe_container<

    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >

#endif

#endif

{ 

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\

    BOOST_WORKAROUND(__MWERKS__,<=0x3003)

/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the

 * lifetime of const references bound to temporaries --precisely what

 * scopeguards are.

 */

#pragma parse_mfunc_templ off

#endif

  typedef typename SuperMeta::type                   super;

protected:

  typedef hashed_index_node<

    typename super::node_type>                       node_type;

  typedef bucket_array<

    typename super::final_allocator_type>            bucket_array_type;

public:

  /* types */

  typedef typename KeyFromValue::result_type         key_type;

  typedef typename node_type::value_type             value_type;

  typedef KeyFromValue                               key_from_value;

  typedef Hash                                       hasher;

  typedef Pred                                       key_equal;

  typedef tuple<std::size_t,

    key_from_value,hasher,key_equal>                 ctor_args;

  typedef typename super::final_allocator_type       allocator_type;

  typedef typename allocator_type::pointer           pointer;

  typedef typename allocator_type::const_pointer     const_pointer;

  typedef typename allocator_type::reference         reference;

  typedef typename allocator_type::const_reference   const_reference;

  typedef std::size_t                                size_type;      

  typedef std::ptrdiff_t                             difference_type;

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

#if BOOST_WORKAROUND(BOOST_MSVC,<1300)

  typedef safe_mode::safe_iterator<

    hashed_index_iterator<

      node_type,bucket_array_type>,

    safe_ctr_proxy<

      hashed_index_iterator<

        node_type,bucket_array_type> > >             iterator;

#else

  typedef safe_mode::safe_iterator<

    hashed_index_iterator<

      node_type,bucket_array_type>,

    hashed_index>                                    iterator;

#endif

#else

  typedef hashed_index_iterator<

    node_type,bucket_array_type>                     iterator;

#endif

  typedef iterator                                   const_iterator;

  typedef iterator                                   local_iterator;

  typedef const_iterator                             const_local_iterator;

  typedef TagList                                    tag_list;

protected:

  typedef typename super::final_node_type     final_node_type;

  typedef tuples::cons<

    ctor_args, 

    typename super::ctor_args_list>           ctor_args_list;

  typedef typename mpl::push_front<

    typename super::index_type_list,

    hashed_index>::type                       index_type_list;

  typedef typename mpl::push_front<

    typename super::iterator_type_list,

    iterator>::type                           iterator_type_list;

  typedef typename mpl::push_front<

    typename super::const_iterator_type_list,

    const_iterator>::type                     const_iterator_type_list;

  typedef typename super::copy_map_type       copy_map_type;

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

  typedef typename super::index_saver_type    index_saver_type;

  typedef typename super::index_loader_type   index_loader_type;

#endif

private:

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

#if BOOST_WORKAROUND(BOOST_MSVC,<1300)

  typedef safe_ctr_proxy_impl<

    hashed_index_iterator<

      node_type,

      bucket_array_type>,

    hashed_index>                             safe_super;

#else

  typedef safe_mode::safe_container<

    hashed_index>                             safe_super;

#endif

#endif

  typedef typename call_traits<value_type>::param_type value_param_type;

  typedef typename call_traits<

    key_type>::param_type                              key_param_type;

public:

  /* construct/destroy/copy

   * Default and copy ctors are in the protected section as indices are

   * not supposed to be created on their own. No range ctor either.

   */

  hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(

    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)

  {

    this->final()=x.final();

    return *this;

  }

  allocator_type get_allocator()const

  {

    return this->final().get_allocator();

  }

  /* size and capacity */

  bool      empty()const{return this->final_empty_();}

  size_type size()const{return this->final_size_();}

  size_type max_size()const{return this->final_max_size_();}

  /* iterators */

  iterator begin()

  {

    return make_iterator(

      node_type::from_impl(buckets.at(first_bucket)->next()));

  }

  const_iterator begin()const

  {

    return make_iterator(

      node_type::from_impl(buckets.at(first_bucket)->next()));

  }

  iterator       end(){return make_iterator(header());}

  const_iterator end()const{return make_iterator(header());}

  /* modifiers */

  std::pair<iterator,bool> insert(value_param_type x)

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    std::pair<final_node_type*,bool> p=this->final_insert_(x);

    return std::pair<iterator,bool>(make_iterator(p.first),p.second);

  }

  iterator insert(iterator position,value_param_type x)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    std::pair<final_node_type*,bool> p=this->final_insert_(

      x,static_cast<final_node_type*>(position.get_node()));

    return make_iterator(p.first);

  }

  template<typename InputIterator>

  void insert(InputIterator first,InputIterator last)

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    iterator hint=end();

    for(;first!=last;++first)hint=insert(hint,*first);

  }

  iterator erase(iterator position)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    this->final_erase_(static_cast<final_node_type*>(position++.get_node()));

    return position;

  }

  size_type erase(key_param_type k)

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    size_type               s=0;

    std::size_t             buc=buckets.position(hash(k));

    hashed_index_node_impl* x=buckets.at(buc);

    hashed_index_node_impl* y=x->next();

    while(y!=x){

      if(eq(k,key(node_type::from_impl(y)->value()))){

        bool b;

        do{

          hashed_index_node_impl* z=y->next();

          b=z!=x&&eq(

            key(node_type::from_impl(y)->value()),

            key(node_type::from_impl(z)->value()));

          this->final_erase_(

            static_cast<final_node_type*>(node_type::from_impl(y)));

          y=z;

          ++s;

        }while(b);

        break;

      }

      y=y->next();

    }

    return s;

  }

  iterator erase(iterator first,iterator last)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);

    BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    while(first!=last){

      first=erase(first);

    }

    return first;

  }

  bool replace(iterator position,value_param_type x)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    return this->final_replace_(

      x,static_cast<final_node_type*>(position.get_node()));

  }

  template<typename Modifier>

  bool modify(iterator position,Modifier mod)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    /* MSVC++ 6.0 optimizer on safe mode code chokes if this

     * this is not added. Left it for all compilers as it does no

     * harm.

     */

    position.detach();

#endif

    return this->final_modify_(

      mod,static_cast<final_node_type*>(position.get_node()));

  }

  template<typename Modifier>

  bool modify_key(iterator position,Modifier mod)

  {

    BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);

    BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    return modify(

      position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));

  }

  void clear()

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    this->final_clear_();

  }

  void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    this->final_swap_(x.final());

  }

  /* observers */

  key_from_value key_extractor()const{return key;}

  hasher         hash_function()const{return hash;}

  key_equal      key_eq()const{return eq;}

  /* lookup */

  /* Internally, these ops rely on const_iterator being the same

   * type as iterator.

   */

  template<typename CompatibleKey>

  iterator find(const CompatibleKey& k)const

  {

    return find(k,hash,eq);

  }

  template<

    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred

  >

  iterator find(

    const CompatibleKey& k,

    const CompatibleHash& hash,const CompatiblePred& eq)const

  {

    std::size_t             buc=buckets.position(hash(k));

    hashed_index_node_impl* x=buckets.at(buc);

    hashed_index_node_impl* y=x->next();

    while(y!=x){

      if(eq(k,key(node_type::from_impl(y)->value()))){

        return make_iterator(node_type::from_impl(y));

      }

      y=y->next();

    }

    return end();

  }

  template<typename CompatibleKey>

  size_type count(const CompatibleKey& k)const

  {

    return count(k,hash,eq);

  }

  template<

    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred

  >

  size_type count(

    const CompatibleKey& k,

    const CompatibleHash& hash,const CompatiblePred& eq)const

  {

    size_type               res=0;

    std::size_t             buc=buckets.position(hash(k));

    hashed_index_node_impl* x=buckets.at(buc);

    hashed_index_node_impl* y=x->next();

    while(y!=x){

      if(eq(k,key(node_type::from_impl(y)->value()))){

        do{

          ++res;

          y=y->next();

        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));

        break;

      }

      y=y->next();

    }

    return res;

  }

  template<typename CompatibleKey>

  std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const

  {

    return equal_range(k,hash,eq);

  }

  template<

    typename CompatibleKey,typename CompatibleHash,typename CompatiblePred

  >

  std::pair<iterator,iterator> equal_range(

    const CompatibleKey& k,

    const CompatibleHash& hash,const CompatiblePred& eq)const

  {

    std::size_t             buc=buckets.position(hash(k));

    hashed_index_node_impl* x=buckets.at(buc);

    hashed_index_node_impl* y=x->next();

    while(y!=x){

      if(eq(k,key(node_type::from_impl(y)->value()))){

        hashed_index_node_impl* y0=y;

        do{

          y=y->next();

        }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));

        if(y==x){

          do{

            ++y;

          }while(y==y->next());

          y=y->next();

        }

        return std::pair<iterator,iterator>(

          make_iterator(node_type::from_impl(y0)),

          make_iterator(node_type::from_impl(y)));

      }

      y=y->next();

    }

    return std::pair<iterator,iterator>(end(),end());

  }

  /* bucket interface */

  size_type bucket_count()const{return buckets.size();}

  size_type max_bucket_count()const{return static_cast<size_type>(-1);}

  size_type bucket_size(size_type n)const

  {

    size_type               res=0;

    hashed_index_node_impl* x=buckets.at(n);

    hashed_index_node_impl* y=x->next();

    while(y!=x){

      ++res;

      y=y->next();

    }

    return res;

  }

  size_type bucket(key_param_type k)const

  {

    return buckets.position(hash(k));

  }

  local_iterator begin(size_type n)

  {

    return const_cast<const hashed_index*>(this)->begin(n);

  }

  const_local_iterator begin(size_type n)const

  {

    hashed_index_node_impl* x=buckets.at(n);

    hashed_index_node_impl* y=x->next();

    if(y==x)return end();

    return make_iterator(node_type::from_impl(y));

  }

  local_iterator end(size_type n)

  {

    return const_cast<const hashed_index*>(this)->end(n);

  }

  const_local_iterator end(size_type n)const

  {

    hashed_index_node_impl* x=buckets.at(n);

    if(x==x->next())return end();

    do{

      ++x;

    }while(x==x->next());

    return make_iterator(node_type::from_impl(x->next()));

  }

  /* hash policy */

  float load_factor()const{return static_cast<float>(size())/bucket_count();}

  float max_load_factor()const{return mlf;}

  void  max_load_factor(float z){mlf=z;calculate_max_load();}

  void rehash(size_type n)

  {

    BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;

    if(size()<max_load&&n<=bucket_count())return;

    size_type bc =(std::numeric_limits<size_type>::max)();

    float     fbc=static_cast<float>(1+size()/mlf);

    if(bc>fbc){

      bc=static_cast<size_type>(fbc);

      if(bc<n)bc=n;

    }

    unchecked_rehash(bc);

  }

BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:

  hashed_index(const ctor_args_list& args_list,const allocator_type& al):

    super(args_list.get_tail(),al),

    key(tuples::get<1>(args_list.get_head())),

    hash(tuples::get<2>(args_list.get_head())),

    eq(tuples::get<3>(args_list.get_head())),

    buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),

    mlf(1.0),

    first_bucket(buckets.size())

  {

    calculate_max_load();

  }

  hashed_index(

    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):

    super(x),

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    safe_super(),

#endif

    key(x.key),

    hash(x.hash),

    eq(x.eq),

    buckets(x.get_allocator(),header()->impl(),x.buckets.size()),

    mlf(x.mlf),

    max_load(x.max_load),

    first_bucket(x.first_bucket)

  {

    /* Copy ctor just takes the internal configuration objects from x. The rest

     * is done in subsequent call to copy_().

     */

  }

  ~hashed_index()

  {

    /* the container is guaranteed to be empty by now */

  }

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

  iterator make_iterator(node_type* node)

  {

    return iterator(node,&buckets,this);

  }

  const_iterator make_iterator(node_type* node)const

  {

    return const_iterator(

      node,

      &const_cast<bucket_array_type&>(buckets),

      const_cast<hashed_index*>(this));

  }

#else

  iterator make_iterator(node_type* node)

  {

    return iterator(node,&buckets);

  }

  const_iterator make_iterator(node_type* node)const

  {

    return const_iterator(node,&const_cast<bucket_array_type&>(buckets));

  }

#endif

  void copy_(

    const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,

    const copy_map_type& map)

  {

    for(hashed_index_node_impl* begin_org=x.buckets.begin(),

                              * begin_cpy=buckets.begin(),

                              * end_org=x.buckets.end();

        begin_org!=end_org;++begin_org,++begin_cpy){

      hashed_index_node_impl* next_org=begin_org->next();

      hashed_index_node_impl* cpy=begin_cpy;

      while(next_org!=begin_org){

        cpy->next()=

          static_cast<node_type*>(

            map.find(

              static_cast<final_node_type*>(

                node_type::from_impl(next_org))))->impl();

        next_org=next_org->next();

        cpy=cpy->next();

      }

      cpy->next()=begin_cpy;

    }

    super::copy_(x,map);

  }

  node_type* insert_(value_param_type v,node_type* x)

  {

    reserve(size()+1);

    std::size_t             buc=find_bucket(v);

    hashed_index_node_impl* pos=buckets.at(buc);

    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,x));

    if(res==x){

      link(x,pos);

      if(first_bucket>buc)first_bucket=buc;

    }

    return res;

  }

  node_type* insert_(value_param_type v,node_type* position,node_type* x)

  {

    reserve(size()+1);

    std::size_t             buc=find_bucket(v);

    hashed_index_node_impl* pos=buckets.at(buc);

    if(!link_point(v,pos,Category()))return node_type::from_impl(pos);

    node_type* res=static_cast<node_type*>(super::insert_(v,position,x));

    if(res==x){

      link(x,pos);

      if(first_bucket>buc)first_bucket=buc;

    }

    return res;

  }

  void erase_(node_type* x)

  {

    unlink(x);

    first_bucket=buckets.first_nonempty(first_bucket);

    super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    detach_iterators(x);

#endif

  }

  void delete_all_nodes_()

  {

    for(hashed_index_node_impl* x=buckets.begin(),*x_end=buckets.end();

        x!=x_end;++x){

      hashed_index_node_impl* y=x->next();

      while(y!=x){

        hashed_index_node_impl* z=y->next();

        this->final_delete_node_(

          static_cast<final_node_type*>(node_type::from_impl(y)));

        y=z;

      }

    }

  }

  void clear_()

  {

    super::clear_();

    buckets.clear();

    first_bucket=buckets.size();

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    safe_super::detach_dereferenceable_iterators();

#endif

  }

  void swap_(

    hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)

  {

    std::swap(key,x.key);

    std::swap(hash,x.hash);

    std::swap(eq,x.eq);

    buckets.swap(x.buckets);

    std::swap(mlf,x.mlf);

    std::swap(max_load,x.max_load);

    std::swap(first_bucket,x.first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

    safe_super::swap(x);

#endif

    super::swap_(x);

  }

  bool replace_(value_param_type v,node_type* x)

  {

    if(eq(key(v),key(x->value()))){

      return super::replace_(v,x);

    }

    hashed_index_node_impl* y=prev(x);

    unlink_next(y);

    BOOST_TRY{

      std::size_t             buc=find_bucket(v);

      hashed_index_node_impl* pos=buckets.at(buc);

      if(link_point(v,pos,Category())&&super::replace_(v,x)){

        link(x,pos);

        if(first_bucket>buc){

          first_bucket=buc;

        }

        else if(first_bucket<buc){

          first_bucket=buckets.first_nonempty(first_bucket);

        }

        return true;

      }

      link(x,y);

      return false;

    }

    BOOST_CATCH(...){

      link(x,y);

      BOOST_RETHROW;

    }

    BOOST_CATCH_END

  }

  bool modify_(node_type* x)

  {

    unlink(x);

    std::size_t             buc;

    hashed_index_node_impl* pos;

    BOOST_TRY

    {

      buc=find_bucket(x->value());

      pos=buckets.at(buc);

      if(!link_point(x->value(),pos,Category())){

        first_bucket=buckets.first_nonempty(first_bucket);

        super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

        detach_iterators(x);

#endif

        return false;

      }

    }

    BOOST_CATCH(...){

      first_bucket=buckets.first_nonempty(first_bucket);

      super::erase_(x);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

      detach_iterators(x);

#endif

      BOOST_RETHROW;

    }

    BOOST_CATCH_END

    BOOST_TRY{

      if(super::modify_(x)){

        link(x,pos);

        if(first_bucket>buc){

          first_bucket=buc;

        }

        else if(first_bucket<buc){

          first_bucket=buckets.first_nonempty(first_bucket);

        }

        return true;

      }

      first_bucket=buckets.first_nonempty(first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

      detach_iterators(x);

#endif

      return false;

    }

    BOOST_CATCH(...){

      first_bucket=buckets.first_nonempty(first_bucket);

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

      detach_iterators(x);

#endif

      BOOST_RETHROW;

    }

    BOOST_CATCH_END

  }

#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)

  /* serialization */

  template<typename Archive>

  void save_(

    Archive& ar,const unsigned int version,const index_saver_type& sm)const

  {

    ar<<serialization::make_nvp("position",buckets);

    super::save_(ar,version,sm);

  }

  template<typename Archive>

  void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)

  {

    ar>>serialization::make_nvp("position",buckets);

    super::load_(ar,version,lm);

  }

#endif

#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)

  /* invariant stuff */

  bool invariant_()const

  {

    if(size()==0||begin()==end()){

      if(size()!=0||begin()!=end())return false;

    }

    else{

      size_type s0=0;

      for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}

      if(s0!=size())return false;

      size_type s1=0;

      for(size_type buc=0;buc<bucket_count();++buc){

        size_type ss1=0;

        for(const_local_iterator it=begin(buc),it_end=end(buc);

            it!=it_end;++it,++ss1){

          if(find_bucket(*it)!=buc)return false;

        }

        if(ss1!=bucket_size(buc))return false;

        s1+=ss1;

      }

      if(s1!=size())return false;

    }

    if(first_bucket!=buckets.first_nonempty(0))return false;

    return super::invariant_();

  }

  /* This forwarding function eases things for the boost::mem_fn construct

   * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,

   * final_check_invariant is already an inherited member function of index.

   */

  void check_invariant_()const{this->final_check_invariant_();}

#endif

private:

  node_type* header()const{return this->final_header();}

  std::size_t find_bucket(value_param_type v)const

  {

    return bucket(key(v));

  }

  bool link_point(

    value_param_type v,hashed_index_node_impl*& pos,hashed_unique_tag)

  {

    hashed_index_node_impl* x=pos->next();

    while(x!=pos){

      if(eq(key(v),key(node_type::from_impl(x)->value()))){

        pos=x;

        return false;

      }

      x=x->next();

    }

    return true;

  }

  bool link_point(

    value_param_type v,hashed_index_node_impl*& pos,hashed_non_unique_tag)

  {

    hashed_index_node_impl* prev=pos;

    hashed_index_node_impl* x=pos->next();

    while(x!=pos){

      if(eq(key(v),key(node_type::from_impl(x)->value()))){

        pos=prev;

        return true;

      }

      prev=x;

      x=x->next();

    }

    return true;

  }

  void link(node_type* x,hashed_index_node_impl* pos)

  {

    hashed_index_node_impl::link(x->impl(),pos);

  };

  void link(hashed_index_node_impl* x,hashed_index_node_impl* pos)

  {

    hashed_index_node_impl::link(x,pos);

  };

  void unlink(node_type* x)

  {

    hashed_index_node_impl::unlink(x->impl());

  };

  static hashed_index_node_impl* prev(node_type* x)

  {

    return hashed_index_node_impl::prev(x->impl());

  }

  static void unlink_next(hashed_index_node_impl* x)

  {

    hashed_index_node_impl::unlink_next(x);

  }

  void calculate_max_load()

  {

    float fml=static_cast<float>(mlf*bucket_count());

    max_load=(std::numeric_limits<size_type>::max)();

    if(max_load>fml)max_load=static_cast<size_type>(fml);

  }

  void reserve(size_type n)

  {

    if(n>max_load){

      size_type bc =(std::numeric_limits<size_type>::max)();

      float     fbc=static_cast<float>(1+n/mlf);

      if(bc>fbc)bc =static_cast<size_type>(fbc);

      unchecked_rehash(bc);

    }

  }

  void unchecked_rehash(size_type n)

  {

    bucket_array_type buckets1(get_allocator(),header()->impl(),n);

    auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());

    std::size_t i=0;

    hashed_index_node_impl* x=buckets.begin();

    hashed_index_node_impl* x_end=buckets.end();

    for(;x!=x_end;++x){

      hashed_index_node_impl* y=x->next();

      while(y!=x){

        hashes.data()[i++]=hash(key(node_type::from_impl(y)->value()));

        y=y->next();

      }

    }

    i=0;

    x=buckets.begin();

    for(;x!=x_end;++x){

      hashed_index_node_impl* y=x->next();

      while(y!=x){

        hashed_index_node_impl* z=y->next();

        std::size_t             buc1=buckets1.position(hashes.data()[i++]);

        hashed_index_node_impl* x1=buckets1.at(buc1);

        link(y,x1);

        y=z;

      }

    }

    buckets.swap(buckets1);

    calculate_max_load();

    first_bucket=buckets.first_nonempty(0);

  }

#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)

  void detach_iterators(node_type* x)

  {

    iterator it=make_iterator(x);

    safe_mode::detach_equivalent_iterators(it);

  }

#endif

  key_from_value               key;

  hasher                       hash;

  key_equal                    eq;

  bucket_array_type            buckets;

  float                        mlf;

  size_type                    max_load;

  std::size_t                  first_bucket;