williamr@2: /* Copyright 2003-2007 Joaquín M López Muñoz.
williamr@2:  * Distributed under the Boost Software License, Version 1.0.
williamr@2:  * (See accompanying file LICENSE_1_0.txt or copy at
williamr@2:  * http://www.boost.org/LICENSE_1_0.txt)
williamr@2:  *
williamr@2:  * See http://www.boost.org/libs/multi_index for library home page.
williamr@2:  */
williamr@2: 
williamr@2: #ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
williamr@2: #define BOOST_MULTI_INDEX_HASHED_INDEX_HPP
williamr@2: 
williamr@2: #if defined(_MSC_VER)&&(_MSC_VER>=1200)
williamr@2: #pragma once
williamr@2: #endif
williamr@2: 
williamr@2: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
williamr@2: #include <algorithm>
williamr@2: #include <boost/call_traits.hpp>
williamr@2: #include <boost/detail/allocator_utilities.hpp>
williamr@2: #include <boost/detail/no_exceptions_support.hpp>
williamr@2: #include <boost/detail/workaround.hpp>
williamr@2: #include <boost/limits.hpp>
williamr@2: #include <boost/mpl/push_front.hpp>
williamr@2: #include <boost/multi_index/detail/access_specifier.hpp>
williamr@2: #include <boost/multi_index/detail/auto_space.hpp>
williamr@2: #include <boost/multi_index/detail/bucket_array.hpp>
williamr@2: #include <boost/multi_index/detail/hash_index_iterator.hpp>
williamr@2: #include <boost/multi_index/detail/modify_key_adaptor.hpp>
williamr@2: #include <boost/multi_index/detail/safe_ctr_proxy.hpp>
williamr@2: #include <boost/multi_index/detail/safe_mode.hpp>
williamr@2: #include <boost/multi_index/detail/scope_guard.hpp>
williamr@2: #include <boost/multi_index/hashed_index_fwd.hpp>
williamr@2: #include <boost/tuple/tuple.hpp>
williamr@2: #include <cstddef>
williamr@2: #include <functional>
williamr@2: #include <utility>
williamr@2: 
williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2: #include <boost/serialization/nvp.hpp>
williamr@2: #endif
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
williamr@2: #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT                       \
williamr@2:   detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)=                 \
williamr@2:     detail::make_obj_guard(*this,&hashed_index::check_invariant_);           \
williamr@2:   BOOST_JOIN(check_invariant_,__LINE__).touch();
williamr@2: #else
williamr@2: #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
williamr@2: #endif
williamr@2: 
williamr@2: namespace boost{
williamr@2: 
williamr@2: namespace multi_index{
williamr@2: 
williamr@2: namespace detail{
williamr@2: 
williamr@2: /* hashed_index adds a layer of hashed indexing to a given Super */
williamr@2: 
williamr@2: /* Most of the implementation of unique and non-unique indices is
williamr@2:  * shared. We tell from one another on instantiation time by using
williamr@2:  * these tags.
williamr@2:  */
williamr@2: 
williamr@2: struct hashed_unique_tag{};
williamr@2: struct hashed_non_unique_tag{};
williamr@2: 
williamr@2: template<
williamr@2:   typename KeyFromValue,typename Hash,typename Pred,
williamr@2:   typename SuperMeta,typename TagList,typename Category
williamr@2: >
williamr@2: class hashed_index:
williamr@2:   BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2: #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
williamr@2:   ,public safe_ctr_proxy_impl<
williamr@2:     hashed_index_iterator<
williamr@2:       hashed_index_node<typename SuperMeta::type::node_type>,
williamr@2:       bucket_array<typename SuperMeta::type::final_allocator_type> >,
williamr@2:     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
williamr@2: #else
williamr@2:   ,public safe_mode::safe_container<
williamr@2:     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
williamr@2: #endif
williamr@2: #endif
williamr@2: 
williamr@2: { 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
williamr@2:     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
williamr@2: /* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
williamr@2:  * lifetime of const references bound to temporaries --precisely what
williamr@2:  * scopeguards are.
williamr@2:  */
williamr@2: 
williamr@2: #pragma parse_mfunc_templ off
williamr@2: #endif
williamr@2: 
williamr@2:   typedef typename SuperMeta::type                   super;
williamr@2: 
williamr@2: protected:
williamr@2:   typedef hashed_index_node<
williamr@2:     typename super::node_type>                       node_type;
williamr@2:   typedef bucket_array<
williamr@2:     typename super::final_allocator_type>            bucket_array_type;
williamr@2: 
williamr@2: public:
williamr@2:   /* types */
williamr@2: 
williamr@2:   typedef typename KeyFromValue::result_type         key_type;
williamr@2:   typedef typename node_type::value_type             value_type;
williamr@2:   typedef KeyFromValue                               key_from_value;
williamr@2:   typedef Hash                                       hasher;
williamr@2:   typedef Pred                                       key_equal;
williamr@2:   typedef tuple<std::size_t,
williamr@2:     key_from_value,hasher,key_equal>                 ctor_args;
williamr@2:   typedef typename super::final_allocator_type       allocator_type;
williamr@2:   typedef typename allocator_type::pointer           pointer;
williamr@2:   typedef typename allocator_type::const_pointer     const_pointer;
williamr@2:   typedef typename allocator_type::reference         reference;
williamr@2:   typedef typename allocator_type::const_reference   const_reference;
williamr@2:   typedef std::size_t                                size_type;      
williamr@2:   typedef std::ptrdiff_t                             difference_type;
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2: #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
williamr@2:   typedef safe_mode::safe_iterator<
williamr@2:     hashed_index_iterator<
williamr@2:       node_type,bucket_array_type>,
williamr@2:     safe_ctr_proxy<
williamr@2:       hashed_index_iterator<
williamr@2:         node_type,bucket_array_type> > >             iterator;
williamr@2: #else
williamr@2:   typedef safe_mode::safe_iterator<
williamr@2:     hashed_index_iterator<
williamr@2:       node_type,bucket_array_type>,
williamr@2:     hashed_index>                                    iterator;
williamr@2: #endif
williamr@2: #else
williamr@2:   typedef hashed_index_iterator<
williamr@2:     node_type,bucket_array_type>                     iterator;
williamr@2: #endif
williamr@2: 
williamr@2:   typedef iterator                                   const_iterator;
williamr@2: 
williamr@2:   typedef iterator                                   local_iterator;
williamr@2:   typedef const_iterator                             const_local_iterator;
williamr@2:   typedef TagList                                    tag_list;
williamr@2: 
williamr@2: protected:
williamr@2:   typedef typename super::final_node_type     final_node_type;
williamr@2:   typedef tuples::cons<
williamr@2:     ctor_args, 
williamr@2:     typename super::ctor_args_list>           ctor_args_list;
williamr@2:   typedef typename mpl::push_front<
williamr@2:     typename super::index_type_list,
williamr@2:     hashed_index>::type                       index_type_list;
williamr@2:   typedef typename mpl::push_front<
williamr@2:     typename super::iterator_type_list,
williamr@2:     iterator>::type                           iterator_type_list;
williamr@2:   typedef typename mpl::push_front<
williamr@2:     typename super::const_iterator_type_list,
williamr@2:     const_iterator>::type                     const_iterator_type_list;
williamr@2:   typedef typename super::copy_map_type       copy_map_type;
williamr@2: 
williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2:   typedef typename super::index_saver_type    index_saver_type;
williamr@2:   typedef typename super::index_loader_type   index_loader_type;
williamr@2: #endif
williamr@2: 
williamr@2: private:
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2: #if BOOST_WORKAROUND(BOOST_MSVC,<1300)
williamr@2:   typedef safe_ctr_proxy_impl<
williamr@2:     hashed_index_iterator<
williamr@2:       node_type,
williamr@2:       bucket_array_type>,
williamr@2:     hashed_index>                             safe_super;
williamr@2: #else
williamr@2:   typedef safe_mode::safe_container<
williamr@2:     hashed_index>                             safe_super;
williamr@2: #endif
williamr@2: #endif
williamr@2: 
williamr@2:   typedef typename call_traits<value_type>::param_type value_param_type;
williamr@2:   typedef typename call_traits<
williamr@2:     key_type>::param_type                              key_param_type;
williamr@2: 
williamr@2: public:
williamr@2: 
williamr@2:   /* construct/destroy/copy
williamr@2:    * Default and copy ctors are in the protected section as indices are
williamr@2:    * not supposed to be created on their own. No range ctor either.
williamr@2:    */
williamr@2: 
williamr@2:   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
williamr@2:     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
williamr@2:   {
williamr@2:     this->final()=x.final();
williamr@2:     return *this;
williamr@2:   }
williamr@2: 
williamr@2:   allocator_type get_allocator()const
williamr@2:   {
williamr@2:     return this->final().get_allocator();
williamr@2:   }
williamr@2: 
williamr@2:   /* size and capacity */
williamr@2: 
williamr@2:   bool      empty()const{return this->final_empty_();}
williamr@2:   size_type size()const{return this->final_size_();}
williamr@2:   size_type max_size()const{return this->final_max_size_();}
williamr@2: 
williamr@2:   /* iterators */
williamr@2: 
williamr@2:   iterator begin()
williamr@2:   {
williamr@2:     return make_iterator(
williamr@2:       node_type::from_impl(buckets.at(first_bucket)->next()));
williamr@2:   }
williamr@2: 
williamr@2:   const_iterator begin()const
williamr@2:   {
williamr@2:     return make_iterator(
williamr@2:       node_type::from_impl(buckets.at(first_bucket)->next()));
williamr@2:   }
williamr@2: 
williamr@2:   iterator       end(){return make_iterator(header());}
williamr@2:   const_iterator end()const{return make_iterator(header());}
williamr@2: 
williamr@2:   /* modifiers */
williamr@2: 
williamr@2:   std::pair<iterator,bool> insert(value_param_type x)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     std::pair<final_node_type*,bool> p=this->final_insert_(x);
williamr@2:     return std::pair<iterator,bool>(make_iterator(p.first),p.second);
williamr@2:   }
williamr@2: 
williamr@2:   iterator insert(iterator position,value_param_type x)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     std::pair<final_node_type*,bool> p=this->final_insert_(
williamr@2:       x,static_cast<final_node_type*>(position.get_node()));
williamr@2:     return make_iterator(p.first);
williamr@2:   }
williamr@2:     
williamr@2:   template<typename InputIterator>
williamr@2:   void insert(InputIterator first,InputIterator last)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     iterator hint=end();
williamr@2:     for(;first!=last;++first)hint=insert(hint,*first);
williamr@2:   }
williamr@2: 
williamr@2:   iterator erase(iterator position)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
williamr@2:     return position;
williamr@2:   }
williamr@2: 
williamr@2:   size_type erase(key_param_type k)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2: 
williamr@2:     size_type               s=0;
williamr@2:     std::size_t             buc=buckets.position(hash(k));
williamr@2:     hashed_index_node_impl* x=buckets.at(buc);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     while(y!=x){
williamr@2:       if(eq(k,key(node_type::from_impl(y)->value()))){
williamr@2:         bool b;
williamr@2:         do{
williamr@2:           hashed_index_node_impl* z=y->next();
williamr@2:           b=z!=x&&eq(
williamr@2:             key(node_type::from_impl(y)->value()),
williamr@2:             key(node_type::from_impl(z)->value()));
williamr@2:           this->final_erase_(
williamr@2:             static_cast<final_node_type*>(node_type::from_impl(y)));
williamr@2:           y=z;
williamr@2:           ++s;
williamr@2:         }while(b);
williamr@2:         break;
williamr@2:       }
williamr@2:       y=y->next();
williamr@2:     }
williamr@2:     return s;
williamr@2:   }
williamr@2: 
williamr@2:   iterator erase(iterator first,iterator last)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     while(first!=last){
williamr@2:       first=erase(first);
williamr@2:     }
williamr@2:     return first;
williamr@2:   }
williamr@2: 
williamr@2:   bool replace(iterator position,value_param_type x)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     return this->final_replace_(
williamr@2:       x,static_cast<final_node_type*>(position.get_node()));
williamr@2:   }
williamr@2: 
williamr@2:   template<typename Modifier>
williamr@2:   bool modify(iterator position,Modifier mod)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:     /* MSVC++ 6.0 optimizer on safe mode code chokes if this
williamr@2:      * this is not added. Left it for all compilers as it does no
williamr@2:      * harm.
williamr@2:      */
williamr@2: 
williamr@2:     position.detach();
williamr@2: #endif
williamr@2: 
williamr@2:     return this->final_modify_(
williamr@2:       mod,static_cast<final_node_type*>(position.get_node()));
williamr@2:   }
williamr@2: 
williamr@2:   template<typename Modifier>
williamr@2:   bool modify_key(iterator position,Modifier mod)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
williamr@2:     BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     return modify(
williamr@2:       position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
williamr@2:   }
williamr@2: 
williamr@2:   void clear()
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     this->final_clear_();
williamr@2:   }
williamr@2: 
williamr@2:   void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     this->final_swap_(x.final());
williamr@2:   }
williamr@2: 
williamr@2:   /* observers */
williamr@2: 
williamr@2:   key_from_value key_extractor()const{return key;}
williamr@2:   hasher         hash_function()const{return hash;}
williamr@2:   key_equal      key_eq()const{return eq;}
williamr@2:   
williamr@2:   /* lookup */
williamr@2: 
williamr@2:   /* Internally, these ops rely on const_iterator being the same
williamr@2:    * type as iterator.
williamr@2:    */
williamr@2: 
williamr@2:   template<typename CompatibleKey>
williamr@2:   iterator find(const CompatibleKey& k)const
williamr@2:   {
williamr@2:     return find(k,hash,eq);
williamr@2:   }
williamr@2: 
williamr@2:   template<
williamr@2:     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
williamr@2:   >
williamr@2:   iterator find(
williamr@2:     const CompatibleKey& k,
williamr@2:     const CompatibleHash& hash,const CompatiblePred& eq)const
williamr@2:   {
williamr@2:     std::size_t             buc=buckets.position(hash(k));
williamr@2:     hashed_index_node_impl* x=buckets.at(buc);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     while(y!=x){
williamr@2:       if(eq(k,key(node_type::from_impl(y)->value()))){
williamr@2:         return make_iterator(node_type::from_impl(y));
williamr@2:       }
williamr@2:       y=y->next();
williamr@2:     }
williamr@2:     return end();
williamr@2:   }
williamr@2: 
williamr@2:   template<typename CompatibleKey>
williamr@2:   size_type count(const CompatibleKey& k)const
williamr@2:   {
williamr@2:     return count(k,hash,eq);
williamr@2:   }
williamr@2: 
williamr@2:   template<
williamr@2:     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
williamr@2:   >
williamr@2:   size_type count(
williamr@2:     const CompatibleKey& k,
williamr@2:     const CompatibleHash& hash,const CompatiblePred& eq)const
williamr@2:   {
williamr@2:     size_type               res=0;
williamr@2:     std::size_t             buc=buckets.position(hash(k));
williamr@2:     hashed_index_node_impl* x=buckets.at(buc);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     while(y!=x){
williamr@2:       if(eq(k,key(node_type::from_impl(y)->value()))){
williamr@2:         do{
williamr@2:           ++res;
williamr@2:           y=y->next();
williamr@2:         }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
williamr@2:         break;
williamr@2:       }
williamr@2:       y=y->next();
williamr@2:     }
williamr@2:     return res;
williamr@2:   }
williamr@2: 
williamr@2:   template<typename CompatibleKey>
williamr@2:   std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
williamr@2:   {
williamr@2:     return equal_range(k,hash,eq);
williamr@2:   }
williamr@2: 
williamr@2:   template<
williamr@2:     typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
williamr@2:   >
williamr@2:   std::pair<iterator,iterator> equal_range(
williamr@2:     const CompatibleKey& k,
williamr@2:     const CompatibleHash& hash,const CompatiblePred& eq)const
williamr@2:   {
williamr@2:     std::size_t             buc=buckets.position(hash(k));
williamr@2:     hashed_index_node_impl* x=buckets.at(buc);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     while(y!=x){
williamr@2:       if(eq(k,key(node_type::from_impl(y)->value()))){
williamr@2:         hashed_index_node_impl* y0=y;
williamr@2:         do{
williamr@2:           y=y->next();
williamr@2:         }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
williamr@2:         if(y==x){
williamr@2:           do{
williamr@2:             ++y;
williamr@2:           }while(y==y->next());
williamr@2:           y=y->next();
williamr@2:         }
williamr@2:         return std::pair<iterator,iterator>(
williamr@2:           make_iterator(node_type::from_impl(y0)),
williamr@2:           make_iterator(node_type::from_impl(y)));
williamr@2:       }
williamr@2:       y=y->next();
williamr@2:     }
williamr@2:     return std::pair<iterator,iterator>(end(),end());
williamr@2:   }
williamr@2: 
williamr@2:   /* bucket interface */
williamr@2: 
williamr@2:   size_type bucket_count()const{return buckets.size();}
williamr@2:   size_type max_bucket_count()const{return static_cast<size_type>(-1);}
williamr@2: 
williamr@2:   size_type bucket_size(size_type n)const
williamr@2:   {
williamr@2:     size_type               res=0;
williamr@2:     hashed_index_node_impl* x=buckets.at(n);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     while(y!=x){
williamr@2:       ++res;
williamr@2:       y=y->next();
williamr@2:     }
williamr@2:     return res;
williamr@2:   }
williamr@2: 
williamr@2:   size_type bucket(key_param_type k)const
williamr@2:   {
williamr@2:     return buckets.position(hash(k));
williamr@2:   }
williamr@2: 
williamr@2:   local_iterator begin(size_type n)
williamr@2:   {
williamr@2:     return const_cast<const hashed_index*>(this)->begin(n);
williamr@2:   }
williamr@2: 
williamr@2:   const_local_iterator begin(size_type n)const
williamr@2:   {
williamr@2:     hashed_index_node_impl* x=buckets.at(n);
williamr@2:     hashed_index_node_impl* y=x->next();
williamr@2:     if(y==x)return end();
williamr@2:     return make_iterator(node_type::from_impl(y));
williamr@2:   }
williamr@2: 
williamr@2:   local_iterator end(size_type n)
williamr@2:   {
williamr@2:     return const_cast<const hashed_index*>(this)->end(n);
williamr@2:   }
williamr@2: 
williamr@2:   const_local_iterator end(size_type n)const
williamr@2:   {
williamr@2:     hashed_index_node_impl* x=buckets.at(n);
williamr@2:     if(x==x->next())return end();
williamr@2:     do{
williamr@2:       ++x;
williamr@2:     }while(x==x->next());
williamr@2:     return make_iterator(node_type::from_impl(x->next()));
williamr@2:   }
williamr@2: 
williamr@2:   /* hash policy */
williamr@2: 
williamr@2:   float load_factor()const{return static_cast<float>(size())/bucket_count();}
williamr@2:   float max_load_factor()const{return mlf;}
williamr@2:   void  max_load_factor(float z){mlf=z;calculate_max_load();}
williamr@2: 
williamr@2:   void rehash(size_type n)
williamr@2:   {
williamr@2:     BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
williamr@2:     if(size()<max_load&&n<=bucket_count())return;
williamr@2: 
williamr@2:     size_type bc =(std::numeric_limits<size_type>::max)();
williamr@2:     float     fbc=static_cast<float>(1+size()/mlf);
williamr@2:     if(bc>fbc){
williamr@2:       bc=static_cast<size_type>(fbc);
williamr@2:       if(bc<n)bc=n;
williamr@2:     }
williamr@2:     unchecked_rehash(bc);
williamr@2:   }
williamr@2: 
williamr@2: BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
williamr@2:   hashed_index(const ctor_args_list& args_list,const allocator_type& al):
williamr@2:     super(args_list.get_tail(),al),
williamr@2:     key(tuples::get<1>(args_list.get_head())),
williamr@2:     hash(tuples::get<2>(args_list.get_head())),
williamr@2:     eq(tuples::get<3>(args_list.get_head())),
williamr@2:     buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
williamr@2:     mlf(1.0),
williamr@2:     first_bucket(buckets.size())
williamr@2:   {
williamr@2:     calculate_max_load();
williamr@2:   }
williamr@2: 
williamr@2:   hashed_index(
williamr@2:     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
williamr@2:     super(x),
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:     safe_super(),
williamr@2: #endif
williamr@2: 
williamr@2:     key(x.key),
williamr@2:     hash(x.hash),
williamr@2:     eq(x.eq),
williamr@2:     buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
williamr@2:     mlf(x.mlf),
williamr@2:     max_load(x.max_load),
williamr@2:     first_bucket(x.first_bucket)
williamr@2:   {
williamr@2:     /* Copy ctor just takes the internal configuration objects from x. The rest
williamr@2:      * is done in subsequent call to copy_().
williamr@2:      */
williamr@2:   }
williamr@2: 
williamr@2:   ~hashed_index()
williamr@2:   {
williamr@2:     /* the container is guaranteed to be empty by now */
williamr@2:   }
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:   iterator make_iterator(node_type* node)
williamr@2:   {
williamr@2:     return iterator(node,&buckets,this);
williamr@2:   }
williamr@2: 
williamr@2:   const_iterator make_iterator(node_type* node)const
williamr@2:   {
williamr@2:     return const_iterator(
williamr@2:       node,
williamr@2:       &const_cast<bucket_array_type&>(buckets),
williamr@2:       const_cast<hashed_index*>(this));
williamr@2:   }
williamr@2: #else
williamr@2:   iterator make_iterator(node_type* node)
williamr@2:   {
williamr@2:     return iterator(node,&buckets);
williamr@2:   }
williamr@2: 
williamr@2:   const_iterator make_iterator(node_type* node)const
williamr@2:   {
williamr@2:     return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
williamr@2:   }
williamr@2: #endif
williamr@2: 
williamr@2:   void copy_(
williamr@2:     const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
williamr@2:     const copy_map_type& map)
williamr@2:   {
williamr@2:     for(hashed_index_node_impl* begin_org=x.buckets.begin(),
williamr@2:                               * begin_cpy=buckets.begin(),
williamr@2:                               * end_org=x.buckets.end();
williamr@2:         begin_org!=end_org;++begin_org,++begin_cpy){
williamr@2: 
williamr@2:       hashed_index_node_impl* next_org=begin_org->next();
williamr@2:       hashed_index_node_impl* cpy=begin_cpy;
williamr@2:       while(next_org!=begin_org){
williamr@2:         cpy->next()=
williamr@2:           static_cast<node_type*>(
williamr@2:             map.find(
williamr@2:               static_cast<final_node_type*>(
williamr@2:                 node_type::from_impl(next_org))))->impl();
williamr@2:         next_org=next_org->next();
williamr@2:         cpy=cpy->next();
williamr@2:       }
williamr@2:       cpy->next()=begin_cpy;
williamr@2:     }
williamr@2: 
williamr@2:     super::copy_(x,map);
williamr@2:   }
williamr@2: 
williamr@2:   node_type* insert_(value_param_type v,node_type* x)
williamr@2:   {
williamr@2:     reserve(size()+1);
williamr@2: 
williamr@2:     std::size_t             buc=find_bucket(v);
williamr@2:     hashed_index_node_impl* pos=buckets.at(buc);
williamr@2:     if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
williamr@2: 
williamr@2:     node_type* res=static_cast<node_type*>(super::insert_(v,x));
williamr@2:     if(res==x){
williamr@2:       link(x,pos);
williamr@2:       if(first_bucket>buc)first_bucket=buc;
williamr@2:     }
williamr@2:     return res;
williamr@2:   }
williamr@2: 
williamr@2:   node_type* insert_(value_param_type v,node_type* position,node_type* x)
williamr@2:   {
williamr@2:     reserve(size()+1);
williamr@2: 
williamr@2:     std::size_t             buc=find_bucket(v);
williamr@2:     hashed_index_node_impl* pos=buckets.at(buc);
williamr@2:     if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
williamr@2: 
williamr@2:     node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
williamr@2:     if(res==x){
williamr@2:       link(x,pos);
williamr@2:       if(first_bucket>buc)first_bucket=buc;
williamr@2:     }
williamr@2:     return res;
williamr@2:   }
williamr@2: 
williamr@2:   void erase_(node_type* x)
williamr@2:   {
williamr@2:     unlink(x);
williamr@2:     first_bucket=buckets.first_nonempty(first_bucket);
williamr@2:     super::erase_(x);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:     detach_iterators(x);
williamr@2: #endif
williamr@2:   }
williamr@2: 
williamr@2:   void delete_all_nodes_()
williamr@2:   {
williamr@2:     for(hashed_index_node_impl* x=buckets.begin(),*x_end=buckets.end();
williamr@2:         x!=x_end;++x){
williamr@2:       hashed_index_node_impl* y=x->next();
williamr@2:       while(y!=x){
williamr@2:         hashed_index_node_impl* z=y->next();
williamr@2:         this->final_delete_node_(
williamr@2:           static_cast<final_node_type*>(node_type::from_impl(y)));
williamr@2:         y=z;
williamr@2:       }
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   void clear_()
williamr@2:   {
williamr@2:     super::clear_();
williamr@2:     buckets.clear();
williamr@2:     first_bucket=buckets.size();
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:     safe_super::detach_dereferenceable_iterators();
williamr@2: #endif
williamr@2:   }
williamr@2: 
williamr@2:   void swap_(
williamr@2:     hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
williamr@2:   {
williamr@2:     std::swap(key,x.key);
williamr@2:     std::swap(hash,x.hash);
williamr@2:     std::swap(eq,x.eq);
williamr@2:     buckets.swap(x.buckets);
williamr@2:     std::swap(mlf,x.mlf);
williamr@2:     std::swap(max_load,x.max_load);
williamr@2:     std::swap(first_bucket,x.first_bucket);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:     safe_super::swap(x);
williamr@2: #endif
williamr@2: 
williamr@2:     super::swap_(x);
williamr@2:   }
williamr@2: 
williamr@2:   bool replace_(value_param_type v,node_type* x)
williamr@2:   {
williamr@2:     if(eq(key(v),key(x->value()))){
williamr@2:       return super::replace_(v,x);
williamr@2:     }
williamr@2: 
williamr@2:     hashed_index_node_impl* y=prev(x);
williamr@2:     unlink_next(y);
williamr@2: 
williamr@2:     BOOST_TRY{
williamr@2:       std::size_t             buc=find_bucket(v);
williamr@2:       hashed_index_node_impl* pos=buckets.at(buc);
williamr@2:       if(link_point(v,pos,Category())&&super::replace_(v,x)){
williamr@2:         link(x,pos);
williamr@2:         if(first_bucket>buc){
williamr@2:           first_bucket=buc;
williamr@2:         }
williamr@2:         else if(first_bucket<buc){
williamr@2:           first_bucket=buckets.first_nonempty(first_bucket);
williamr@2:         }
williamr@2:         return true;
williamr@2:       }
williamr@2:       link(x,y);
williamr@2:       return false;
williamr@2:     }
williamr@2:     BOOST_CATCH(...){
williamr@2:       link(x,y);
williamr@2:       BOOST_RETHROW;
williamr@2:     }
williamr@2:     BOOST_CATCH_END
williamr@2:   }
williamr@2: 
williamr@2:   bool modify_(node_type* x)
williamr@2:   {
williamr@2:     unlink(x);
williamr@2: 
williamr@2:     std::size_t             buc;
williamr@2:     hashed_index_node_impl* pos;
williamr@2:     BOOST_TRY
williamr@2:     {
williamr@2:       buc=find_bucket(x->value());
williamr@2:       pos=buckets.at(buc);
williamr@2:       if(!link_point(x->value(),pos,Category())){
williamr@2:         first_bucket=buckets.first_nonempty(first_bucket);
williamr@2:         super::erase_(x);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:         detach_iterators(x);
williamr@2: #endif
williamr@2:         return false;
williamr@2:       }
williamr@2: 
williamr@2:     }
williamr@2:     BOOST_CATCH(...){
williamr@2:       first_bucket=buckets.first_nonempty(first_bucket);
williamr@2:       super::erase_(x);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:       detach_iterators(x);
williamr@2: #endif
williamr@2: 
williamr@2:       BOOST_RETHROW;
williamr@2:     }
williamr@2:     BOOST_CATCH_END
williamr@2: 
williamr@2:     BOOST_TRY{
williamr@2:       if(super::modify_(x)){
williamr@2:         link(x,pos);
williamr@2:         if(first_bucket>buc){
williamr@2:           first_bucket=buc;
williamr@2:         }
williamr@2:         else if(first_bucket<buc){
williamr@2:           first_bucket=buckets.first_nonempty(first_bucket);
williamr@2:         }
williamr@2:         return true;
williamr@2:       }
williamr@2: 
williamr@2:       first_bucket=buckets.first_nonempty(first_bucket);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:       detach_iterators(x);
williamr@2: #endif
williamr@2:       return false;
williamr@2:     }
williamr@2:     BOOST_CATCH(...){
williamr@2:       first_bucket=buckets.first_nonempty(first_bucket);
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:       detach_iterators(x);
williamr@2: #endif
williamr@2: 
williamr@2:       BOOST_RETHROW;
williamr@2:     }
williamr@2:     BOOST_CATCH_END
williamr@2:   }
williamr@2: 
williamr@2: #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
williamr@2:   /* serialization */
williamr@2: 
williamr@2:   template<typename Archive>
williamr@2:   void save_(
williamr@2:     Archive& ar,const unsigned int version,const index_saver_type& sm)const
williamr@2:   {
williamr@2:     ar<<serialization::make_nvp("position",buckets);
williamr@2:     super::save_(ar,version,sm);
williamr@2:   }
williamr@2: 
williamr@2:   template<typename Archive>
williamr@2:   void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
williamr@2:   {
williamr@2:     ar>>serialization::make_nvp("position",buckets);
williamr@2:     super::load_(ar,version,lm);
williamr@2:   }
williamr@2: #endif
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
williamr@2:   /* invariant stuff */
williamr@2: 
williamr@2:   bool invariant_()const
williamr@2:   {
williamr@2:     if(size()==0||begin()==end()){
williamr@2:       if(size()!=0||begin()!=end())return false;
williamr@2:     }
williamr@2:     else{
williamr@2:       size_type s0=0;
williamr@2:       for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
williamr@2:       if(s0!=size())return false;
williamr@2: 
williamr@2:       size_type s1=0;
williamr@2:       for(size_type buc=0;buc<bucket_count();++buc){
williamr@2:         size_type ss1=0;
williamr@2:         for(const_local_iterator it=begin(buc),it_end=end(buc);
williamr@2:             it!=it_end;++it,++ss1){
williamr@2:           if(find_bucket(*it)!=buc)return false;
williamr@2:         }
williamr@2:         if(ss1!=bucket_size(buc))return false;
williamr@2:         s1+=ss1;
williamr@2:       }
williamr@2:       if(s1!=size())return false;
williamr@2:     }
williamr@2: 
williamr@2:     if(first_bucket!=buckets.first_nonempty(0))return false;
williamr@2: 
williamr@2:     return super::invariant_();
williamr@2:   }
williamr@2: 
williamr@2:   /* This forwarding function eases things for the boost::mem_fn construct
williamr@2:    * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
williamr@2:    * final_check_invariant is already an inherited member function of index.
williamr@2:    */
williamr@2:   void check_invariant_()const{this->final_check_invariant_();}
williamr@2: #endif
williamr@2: 
williamr@2: private:
williamr@2:   node_type* header()const{return this->final_header();}
williamr@2: 
williamr@2:   std::size_t find_bucket(value_param_type v)const
williamr@2:   {
williamr@2:     return bucket(key(v));
williamr@2:   }
williamr@2: 
williamr@2:   bool link_point(
williamr@2:     value_param_type v,hashed_index_node_impl*& pos,hashed_unique_tag)
williamr@2:   {
williamr@2:     hashed_index_node_impl* x=pos->next();
williamr@2:     while(x!=pos){
williamr@2:       if(eq(key(v),key(node_type::from_impl(x)->value()))){
williamr@2:         pos=x;
williamr@2:         return false;
williamr@2:       }
williamr@2:       x=x->next();
williamr@2:     }
williamr@2:     return true;
williamr@2:   }
williamr@2: 
williamr@2:   bool link_point(
williamr@2:     value_param_type v,hashed_index_node_impl*& pos,hashed_non_unique_tag)
williamr@2:   {
williamr@2:     hashed_index_node_impl* prev=pos;
williamr@2:     hashed_index_node_impl* x=pos->next();
williamr@2:     while(x!=pos){
williamr@2:       if(eq(key(v),key(node_type::from_impl(x)->value()))){
williamr@2:         pos=prev;
williamr@2:         return true;
williamr@2:       }
williamr@2:       prev=x;
williamr@2:       x=x->next();
williamr@2:     }
williamr@2:     return true;
williamr@2:   }
williamr@2:   
williamr@2:   void link(node_type* x,hashed_index_node_impl* pos)
williamr@2:   {
williamr@2:     hashed_index_node_impl::link(x->impl(),pos);
williamr@2:   };
williamr@2: 
williamr@2:   void link(hashed_index_node_impl* x,hashed_index_node_impl* pos)
williamr@2:   {
williamr@2:     hashed_index_node_impl::link(x,pos);
williamr@2:   };
williamr@2: 
williamr@2:   void unlink(node_type* x)
williamr@2:   {
williamr@2:     hashed_index_node_impl::unlink(x->impl());
williamr@2:   };
williamr@2: 
williamr@2:   static hashed_index_node_impl* prev(node_type* x)
williamr@2:   {
williamr@2:     return hashed_index_node_impl::prev(x->impl());
williamr@2:   }
williamr@2: 
williamr@2:   static void unlink_next(hashed_index_node_impl* x)
williamr@2:   {
williamr@2:     hashed_index_node_impl::unlink_next(x);
williamr@2:   }
williamr@2: 
williamr@2:   void calculate_max_load()
williamr@2:   {
williamr@2:     float fml=static_cast<float>(mlf*bucket_count());
williamr@2:     max_load=(std::numeric_limits<size_type>::max)();
williamr@2:     if(max_load>fml)max_load=static_cast<size_type>(fml);
williamr@2:   }
williamr@2: 
williamr@2:   void reserve(size_type n)
williamr@2:   {
williamr@2:     if(n>max_load){
williamr@2:       size_type bc =(std::numeric_limits<size_type>::max)();
williamr@2:       float     fbc=static_cast<float>(1+n/mlf);
williamr@2:       if(bc>fbc)bc =static_cast<size_type>(fbc);
williamr@2:       unchecked_rehash(bc);
williamr@2:     }
williamr@2:   }
williamr@2: 
williamr@2:   void unchecked_rehash(size_type n)
williamr@2:   {
williamr@2:     bucket_array_type buckets1(get_allocator(),header()->impl(),n);
williamr@2:     auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
williamr@2: 
williamr@2:     std::size_t i=0;
williamr@2:     hashed_index_node_impl* x=buckets.begin();
williamr@2:     hashed_index_node_impl* x_end=buckets.end();
williamr@2:     for(;x!=x_end;++x){
williamr@2:       hashed_index_node_impl* y=x->next();
williamr@2:       while(y!=x){
williamr@2:         hashes.data()[i++]=hash(key(node_type::from_impl(y)->value()));
williamr@2:         y=y->next();
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     i=0;
williamr@2:     x=buckets.begin();
williamr@2:     for(;x!=x_end;++x){
williamr@2:       hashed_index_node_impl* y=x->next();
williamr@2:       while(y!=x){
williamr@2:         hashed_index_node_impl* z=y->next();
williamr@2:         std::size_t             buc1=buckets1.position(hashes.data()[i++]);
williamr@2:         hashed_index_node_impl* x1=buckets1.at(buc1);
williamr@2:         link(y,x1);
williamr@2:         y=z;
williamr@2:       }
williamr@2:     }
williamr@2: 
williamr@2:     buckets.swap(buckets1);
williamr@2:     calculate_max_load();
williamr@2:     first_bucket=buckets.first_nonempty(0);
williamr@2:   }
williamr@2: 
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
williamr@2:   void detach_iterators(node_type* x)
williamr@2:   {
williamr@2:     iterator it=make_iterator(x);
williamr@2:     safe_mode::detach_equivalent_iterators(it);
williamr@2:   }
williamr@2: #endif
williamr@2: 
williamr@2:   key_from_value               key;
williamr@2:   hasher                       hash;
williamr@2:   key_equal                    eq;
williamr@2:   bucket_array_type            buckets;
williamr@2:   float                        mlf;
williamr@2:   size_type                    max_load;
williamr@2:   std::size_t                  first_bucket;
williamr@2:       
williamr@2: #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
williamr@2:     BOOST_WORKAROUND(__MWERKS__,<=0x3003)
williamr@2: #pragma parse_mfunc_templ reset
williamr@2: #endif
williamr@2: };
williamr@2: 
williamr@2: /*  specialized algorithms */
williamr@2: 
williamr@2: template<
williamr@2:   typename KeyFromValue,typename Hash,typename Pred,
williamr@2:   typename SuperMeta,typename TagList,typename Category
williamr@2: >
williamr@2: void swap(
williamr@2:   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
williamr@2:   hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
williamr@2: {
williamr@2:   x.swap(y);
williamr@2: }
williamr@2: 
williamr@2: } /* namespace multi_index::detail */
williamr@2: 
williamr@2: /* sequenced index specifiers */
williamr@2: 
williamr@2: template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
williamr@2: struct hashed_unique
williamr@2: {
williamr@2:   typedef typename detail::hashed_index_args<
williamr@2:     Arg1,Arg2,Arg3,Arg4>                           index_args;
williamr@2:   typedef typename index_args::tag_list_type::type tag_list_type;
williamr@2:   typedef typename index_args::key_from_value_type key_from_value_type;
williamr@2:   typedef typename index_args::hash_type           hash_type;
williamr@2:   typedef typename index_args::pred_type           pred_type;
williamr@2: 
williamr@2:   template<typename Super>
williamr@2:   struct node_class
williamr@2:   {
williamr@2:     typedef detail::hashed_index_node<Super> type;
williamr@2:   };
williamr@2: 
williamr@2:   template<typename SuperMeta>
williamr@2:   struct index_class
williamr@2:   {
williamr@2:     typedef detail::hashed_index<
williamr@2:       key_from_value_type,hash_type,pred_type,
williamr@2:       SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
williamr@2:   };
williamr@2: };
williamr@2: 
williamr@2: template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
williamr@2: struct hashed_non_unique
williamr@2: {
williamr@2:   typedef typename detail::hashed_index_args<
williamr@2:     Arg1,Arg2,Arg3,Arg4>                           index_args;
williamr@2:   typedef typename index_args::tag_list_type::type tag_list_type;
williamr@2:   typedef typename index_args::key_from_value_type key_from_value_type;
williamr@2:   typedef typename index_args::hash_type           hash_type;
williamr@2:   typedef typename index_args::pred_type           pred_type;
williamr@2: 
williamr@2:   template<typename Super>
williamr@2:   struct node_class
williamr@2:   {
williamr@2:     typedef detail::hashed_index_node<Super> type;
williamr@2:   };
williamr@2: 
williamr@2:   template<typename SuperMeta>
williamr@2:   struct index_class
williamr@2:   {
williamr@2:     typedef detail::hashed_index<
williamr@2:       key_from_value_type,hash_type,pred_type,
williamr@2:       SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
williamr@2:   };
williamr@2: };
williamr@2: 
williamr@2: } /* namespace multi_index */
williamr@2: 
williamr@2: } /* namespace boost */
williamr@2: 
williamr@2: #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
williamr@2: 
williamr@2: #endif