diff options
Diffstat (limited to 'boost/multi_index/hashed_index.hpp')
| -rw-r--r-- | boost/multi_index/hashed_index.hpp | 1127 |
1 files changed, 761 insertions, 366 deletions
diff --git a/boost/multi_index/hashed_index.hpp b/boost/multi_index/hashed_index.hpp index 0ee4aebc17..ebf55c9ef0 100644 --- a/boost/multi_index/hashed_index.hpp +++ b/boost/multi_index/hashed_index.hpp @@ -1,4 +1,4 @@ -/* Copyright 2003-2011 Joaquin M Lopez Munoz. +/* Copyright 2003-2014 Joaquin M Lopez Munoz. * 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) @@ -9,7 +9,7 @@ #ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP #define BOOST_MULTI_INDEX_HASHED_INDEX_HPP -#if defined(_MSC_VER)&&(_MSC_VER>=1200) +#if defined(_MSC_VER) #pragma once #endif @@ -21,33 +21,46 @@ #include <boost/detail/workaround.hpp> #include <boost/foreach_fwd.hpp> #include <boost/limits.hpp> +#include <boost/move/core.hpp> #include <boost/mpl/bool.hpp> +#include <boost/mpl/if.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/do_not_copy_elements_tag.hpp> #include <boost/multi_index/detail/hash_index_iterator.hpp> #include <boost/multi_index/detail/index_node_base.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/detail/vartempl_support.hpp> #include <boost/multi_index/hashed_index_fwd.hpp> #include <boost/tuple/tuple.hpp> +#include <boost/type_traits/is_same.hpp> +#include <cmath> #include <cstddef> #include <functional> +#include <iterator> #include <utility> +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) +#include <initializer_list> +#endif + #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 \ +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \ detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \ - detail::make_obj_guard(*this,&hashed_index::check_invariant_); \ + detail::make_obj_guard(x,&hashed_index::check_invariant_); \ BOOST_JOIN(check_invariant_,__LINE__).touch(); +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \ + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this) #else +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) #define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT #endif @@ -61,12 +74,9 @@ namespace detail{ /* Most of the implementation of unique and non-unique indices is * shared. We tell from one another on instantiation time by using - * these tags. + * Category tags defined in hash_index_node.hpp. */ -struct hashed_unique_tag{}; -struct hashed_non_unique_tag{}; - template< typename KeyFromValue,typename Hash,typename Pred, typename SuperMeta,typename TagList,typename Category @@ -75,17 +85,9 @@ 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)&&\ @@ -102,11 +104,13 @@ class hashed_index: protected: typedef hashed_index_node< - typename super::node_type> node_type; + typename super::node_type,Category> node_type; private: + typedef typename node_type::node_alg node_alg; typedef typename node_type::impl_type node_impl_type; typedef typename node_impl_type::pointer node_impl_pointer; + typedef typename node_impl_type::base_pointer node_impl_base_pointer; typedef bucket_array< typename super::final_allocator_type> bucket_array_type; @@ -129,28 +133,24 @@ public: 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>, + node_type,bucket_array_type, + hashed_index_global_iterator_tag>, hashed_index> iterator; -#endif #else typedef hashed_index_iterator< - node_type,bucket_array_type> iterator; + node_type,bucket_array_type, + hashed_index_global_iterator_tag> iterator; #endif typedef iterator const_iterator; - typedef iterator local_iterator; - typedef const_iterator const_local_iterator; + typedef hashed_index_iterator< + node_type,bucket_array_type, + hashed_index_local_iterator_tag> local_iterator; + typedef local_iterator const_local_iterator; + typedef TagList tag_list; protected: @@ -176,21 +176,20 @@ protected: 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; + /* Needed to avoid commas in BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL + * expansion. + */ + + typedef std::pair<iterator,bool> emplace_return_type; + public: /* construct/destroy/copy @@ -205,36 +204,36 @@ public: return *this; } - allocator_type get_allocator()const +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=( + std::initializer_list<value_type> list) + { + this->final()=list; + return *this; + } +#endif + + allocator_type get_allocator()const BOOST_NOEXCEPT { 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_();} + bool empty()const BOOST_NOEXCEPT{return this->final_empty_();} + size_type size()const BOOST_NOEXCEPT{return this->final_size_();} + size_type max_size()const BOOST_NOEXCEPT{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());} - - const_iterator cbegin()const{return begin();} - const_iterator cend()const{return end();} + iterator begin()BOOST_NOEXCEPT + {return make_iterator(node_type::from_impl(header()->next()->prior()));} + const_iterator begin()const BOOST_NOEXCEPT + {return make_iterator(node_type::from_impl(header()->next()->prior()));} + iterator end()BOOST_NOEXCEPT{return make_iterator(header());} + const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());} + const_iterator cbegin()const BOOST_NOEXCEPT{return begin();} + const_iterator cend()const BOOST_NOEXCEPT{return end();} iterator iterator_to(const value_type& x) { @@ -248,14 +247,27 @@ public: /* modifiers */ - std::pair<iterator,bool> insert(value_param_type x) + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL( + emplace_return_type,emplace,emplace_impl) + + BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG( + iterator,emplace_hint,emplace_hint_impl,iterator,position) + + std::pair<iterator,bool> insert(const value_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) + std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool> p=this->final_insert_rv_(x); + return std::pair<iterator,bool>(make_iterator(p.first),p.second); + } + + iterator insert(iterator position,const value_type& x) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this); @@ -265,14 +277,30 @@ public: return make_iterator(p.first); } + iterator insert(iterator position,BOOST_RV_REF(value_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_rv_( + 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); + for(;first!=last;++first)this->final_insert_ref_(*first); } +#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST) + void insert(std::initializer_list<value_type> list) + { + insert(list.begin(),list.end()); + } +#endif + iterator erase(iterator position) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); @@ -287,28 +315,23 @@ public: { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; - size_type s=0; - std::size_t buc=buckets.position(hash(k)); - node_impl_pointer x=buckets.at(buc); - node_impl_pointer y=x->next(); - while(y!=x){ - if(eq(k,key(node_type::from_impl(y)->value()))){ - bool b; + std::size_t buc=buckets.position(hash_(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq_(k,key(node_type::from_impl(x)->value()))){ + node_impl_pointer y=end_of_range(x); + size_type s=0; do{ - node_impl_pointer z=y->next(); - b=z!=x&&eq( - key(node_type::from_impl(y)->value()), - key(node_type::from_impl(z)->value())); + node_impl_pointer z=node_alg::after(x); this->final_erase_( - static_cast<final_node_type*>(node_type::from_impl(y))); - y=z; + static_cast<final_node_type*>(node_type::from_impl(x))); + x=z; ++s; - }while(b); - break; + }while(x!=y); + return s; } - y=y->next(); } - return s; + return 0; } iterator erase(iterator first,iterator last) @@ -325,7 +348,7 @@ public: return first; } - bool replace(iterator position,value_param_type x) + bool replace(iterator position,const value_type& x) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); @@ -335,6 +358,16 @@ public: x,static_cast<final_node_type*>(position.get_node())); } + bool replace(iterator position,BOOST_RV_REF(value_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_rv_( + x,static_cast<final_node_type*>(position.get_node())); + } + template<typename Modifier> bool modify(iterator position,Modifier mod) { @@ -357,7 +390,7 @@ public: } template<typename Modifier,typename Rollback> - bool modify(iterator position,Modifier mod,Rollback back) + bool modify(iterator position,Modifier mod,Rollback back_) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); @@ -374,7 +407,7 @@ public: #endif return this->final_modify_( - mod,back,static_cast<final_node_type*>(position.get_node())); + mod,back_,static_cast<final_node_type*>(position.get_node())); } template<typename Modifier> @@ -389,7 +422,7 @@ public: } template<typename Modifier,typename Rollback> - bool modify_key(iterator position,Modifier mod,Rollback back) + bool modify_key(iterator position,Modifier mod,Rollback back_) { BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position); BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position); @@ -398,10 +431,10 @@ public: return modify( position, modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key), - modify_key_adaptor<Rollback,value_type,KeyFromValue>(back,key)); + modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key)); } - void clear() + void clear()BOOST_NOEXCEPT { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; this->final_clear_(); @@ -410,14 +443,15 @@ public: void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x) { BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x); 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;} + hasher hash_function()const{return hash_;} + key_equal key_eq()const{return eq_;} /* lookup */ @@ -428,7 +462,7 @@ public: template<typename CompatibleKey> iterator find(const CompatibleKey& k)const { - return find(k,hash,eq); + return find(k,hash_,eq_); } template< @@ -438,14 +472,12 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - std::size_t buc=buckets.position(hash(k)); - node_impl_pointer x=buckets.at(buc); - node_impl_pointer y=x->next(); - while(y!=x){ - if(eq(k,key(node_type::from_impl(y)->value()))){ - return make_iterator(node_type::from_impl(y)); + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ + return make_iterator(node_type::from_impl(x)); } - y=y->next(); } return end(); } @@ -453,7 +485,7 @@ public: template<typename CompatibleKey> size_type count(const CompatibleKey& k)const { - return count(k,hash,eq); + return count(k,hash_,eq_); } template< @@ -463,27 +495,26 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - size_type res=0; - std::size_t buc=buckets.position(hash(k)); - node_impl_pointer x=buckets.at(buc); - node_impl_pointer y=x->next(); - while(y!=x){ - if(eq(k,key(node_type::from_impl(y)->value()))){ + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ + size_type res=0; + node_impl_pointer y=end_of_range(x); do{ ++res; - y=y->next(); - }while(y!=x&&eq(k,key(node_type::from_impl(y)->value()))); - break; + x=node_alg::after(x); + }while(x!=y); + return res; } - y=y->next(); } - return res; + return 0; } template<typename CompatibleKey> std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const { - return equal_range(k,hash,eq); + return equal_range(k,hash_,eq_); } template< @@ -493,50 +524,36 @@ public: const CompatibleKey& k, const CompatibleHash& hash,const CompatiblePred& eq)const { - std::size_t buc=buckets.position(hash(k)); - node_impl_pointer x=buckets.at(buc); - node_impl_pointer y=x->next(); - while(y!=x){ - if(eq(k,key(node_type::from_impl(y)->value()))){ - node_impl_pointer 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(); - } + std::size_t buc=buckets.position(hash(k)); + for(node_impl_pointer x=buckets.at(buc)->prior(); + x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){ + if(eq(k,key(node_type::from_impl(x)->value()))){ return std::pair<iterator,iterator>( - make_iterator(node_type::from_impl(y0)), - make_iterator(node_type::from_impl(y))); + make_iterator(node_type::from_impl(x)), + make_iterator(node_type::from_impl(end_of_range(x)))); } - 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_count()const BOOST_NOEXCEPT{return buckets.size();} + size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);} size_type bucket_size(size_type n)const { - size_type res=0; - node_impl_pointer x=buckets.at(n); - node_impl_pointer y=x->next(); - while(y!=x){ + size_type res=0; + for(node_impl_pointer x=buckets.at(n)->prior(); + x!=node_impl_pointer(0);x=node_alg::after_local(x)){ ++res; - y=y->next(); } return res; } size_type bucket(key_param_type k)const { - return buckets.position(hash(k)); + return buckets.position(hash_(k)); } local_iterator begin(size_type n) @@ -546,10 +563,9 @@ public: const_local_iterator begin(size_type n)const { - node_impl_pointer x=buckets.at(n); - node_impl_pointer y=x->next(); - if(y==x)return end(); - return make_iterator(node_type::from_impl(y)); + node_impl_pointer x=buckets.at(n)->prior(); + if(x==node_impl_pointer(0))return end(n); + return make_local_iterator(node_type::from_impl(x)); } local_iterator end(size_type n) @@ -557,14 +573,9 @@ public: return const_cast<const hashed_index*>(this)->end(n); } - const_local_iterator end(size_type n)const + const_local_iterator end(size_type)const { - node_impl_pointer 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())); + return make_local_iterator(0); } const_local_iterator cbegin(size_type n)const{return begin(n);} @@ -572,24 +583,25 @@ public: local_iterator local_iterator_to(const value_type& x) { - return make_iterator(node_from_value<node_type>(&x)); + return make_local_iterator(node_from_value<node_type>(&x)); } const_local_iterator local_iterator_to(const value_type& x)const { - return make_iterator(node_from_value<node_type>(&x)); + return make_local_iterator(node_from_value<node_type>(&x)); } /* hash policy */ - float load_factor()const{return static_cast<float>(size())/bucket_count();} - float max_load_factor()const{return mlf;} + float load_factor()const BOOST_NOEXCEPT + {return static_cast<float>(size())/bucket_count();} + float max_load_factor()const BOOST_NOEXCEPT{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; + 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); @@ -600,15 +612,19 @@ public: unchecked_rehash(bc); } + void reserve(size_type n) + { + rehash(static_cast<size_type>(std::ceil(static_cast<double>(n)/mlf))); + } + 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())), + 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.0f), - first_bucket(buckets.size()) + mlf(1.0f) { calculate_max_load(); } @@ -622,18 +638,35 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #endif key(x.key), - hash(x.hash), - eq(x.eq), + 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) + max_load(x.max_load) { /* Copy ctor just takes the internal configuration objects from x. The rest * is done in subsequent call to copy_(). */ } + hashed_index( + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + do_not_copy_elements_tag): + super(x,do_not_copy_elements_tag()), + +#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(),0), + mlf(1.0f) + { + calculate_max_load(); + } + ~hashed_index() { /* the container is guaranteed to be empty by now */ @@ -642,90 +675,163 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) iterator make_iterator(node_type* node) { - return iterator(node,&buckets,this); + return iterator(node,this); } const_iterator make_iterator(node_type* node)const { - return const_iterator( - node, - &const_cast<bucket_array_type&>(buckets), - const_cast<hashed_index*>(this)); + return const_iterator(node,const_cast<hashed_index*>(this)); } #else iterator make_iterator(node_type* node) { - return iterator(node,&buckets); + return iterator(node); } const_iterator make_iterator(node_type* node)const { - return const_iterator(node,&const_cast<bucket_array_type&>(buckets)); + return const_iterator(node); } #endif + local_iterator make_local_iterator(node_type* node) + { + return local_iterator(node); + } + + const_local_iterator make_local_iterator(node_type* node)const + { + return const_local_iterator(node); + } + void copy_( const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, const copy_map_type& map) { - for(node_impl_pointer begin_org=x.buckets.begin(), - begin_cpy=buckets.begin(), - end_org=x.buckets.end(); - begin_org!=end_org;++begin_org,++begin_cpy){ - - node_impl_pointer next_org=begin_org->next(); - node_impl_pointer 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; + copy_(x,map,Category()); + } + + void copy_( + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + const copy_map_type& map,hashed_unique_tag) + { + if(x.size()!=0){ + node_impl_pointer end_org=x.header()->impl(), + org=end_org, + cpy=header()->impl(); + do{ + node_impl_pointer prev_org=org->prior(), + prev_cpy= + static_cast<node_type*>(map.find(static_cast<final_node_type*>( + node_type::from_impl(prev_org))))->impl(); + cpy->prior()=prev_cpy; + if(node_alg::is_first_of_bucket(org)){ + node_impl_base_pointer buc_org=prev_org->next(), + buc_cpy= + buckets.begin()+(buc_org-x.buckets.begin()); + prev_cpy->next()=buc_cpy; + buc_cpy->prior()=cpy; + } + else{ + prev_cpy->next()=node_impl_type::base_pointer_from(cpy); + } + org=prev_org; + cpy=prev_cpy; + }while(org!=end_org); } super::copy_(x,map); } + + void copy_( + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + const copy_map_type& map,hashed_non_unique_tag) + { + if(x.size()!=0){ + node_impl_pointer end_org=x.header()->impl(), + org=end_org, + cpy=header()->impl(); + do{ + node_impl_pointer next_org=node_alg::after(org), + next_cpy= + static_cast<node_type*>(map.find(static_cast<final_node_type*>( + node_type::from_impl(next_org))))->impl(); + if(node_alg::is_first_of_bucket(next_org)){ + node_impl_base_pointer buc_org=org->next(), + buc_cpy= + buckets.begin()+(buc_org-x.buckets.begin()); + cpy->next()=buc_cpy; + buc_cpy->prior()=next_cpy; + next_cpy->prior()=cpy; + } + else{ + if(org->next()==node_impl_type::base_pointer_from(next_org)){ + cpy->next()=node_impl_type::base_pointer_from(next_cpy); + } + else{ + cpy->next()= + node_impl_type::base_pointer_from( + static_cast<node_type*>(map.find(static_cast<final_node_type*>( + node_type::from_impl( + node_impl_type::pointer_from(org->next())))))->impl()); + } + + if(next_org->prior()!=org){ + next_cpy->prior()= + static_cast<node_type*>(map.find(static_cast<final_node_type*>( + node_type::from_impl(next_org->prior()))))->impl(); + } + else{ + next_cpy->prior()=cpy; + } + } + org=next_org; + cpy=next_cpy; + }while(org!=end_org); + } - node_type* insert_(value_param_type v,node_type* x) - { - reserve(size()+1); + super::copy_(x,map); + } - std::size_t buc=find_bucket(v); - node_impl_pointer pos=buckets.at(buc); - if(!link_point(v,pos,Category()))return node_type::from_impl(pos); + template<typename Variant> + final_node_type* insert_( + value_param_type v,final_node_type*& x,Variant variant) + { + reserve_for_insert(size()+1); - node_type* res=static_cast<node_type*>(super::insert_(v,x)); - if(res==x){ - link(x,pos); - if(first_bucket>buc)first_bucket=buc; + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(!link_point(v,pos)){ + return static_cast<final_node_type*>( + node_type::from_impl(node_impl_type::pointer_from(pos))); } + + final_node_type* res=super::insert_(v,x,variant); + if(res==x)link(static_cast<node_type*>(x),pos); return res; } - node_type* insert_(value_param_type v,node_type* position,node_type* x) + template<typename Variant> + final_node_type* insert_( + value_param_type v,node_type* position,final_node_type*& x,Variant variant) { - reserve(size()+1); - - std::size_t buc=find_bucket(v); - node_impl_pointer pos=buckets.at(buc); - if(!link_point(v,pos,Category()))return node_type::from_impl(pos); + reserve_for_insert(size()+1); - 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; + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(!link_point(v,pos)){ + return static_cast<final_node_type*>( + node_type::from_impl(node_impl_type::pointer_from(pos))); } + + final_node_type* res=super::insert_(v,position,x,variant); + if(res==x)link(static_cast<node_type*>(x),pos); 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) @@ -735,23 +841,42 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: void delete_all_nodes_() { - for(node_impl_pointer x=buckets.begin(),x_end=buckets.end(); - x!=x_end;++x){ - node_impl_pointer y=x->next(); - while(y!=x){ - node_impl_pointer z=y->next(); - this->final_delete_node_( - static_cast<final_node_type*>(node_type::from_impl(y))); - y=z; + delete_all_nodes_(Category()); + } + + void delete_all_nodes_(hashed_unique_tag) + { + for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){ + node_impl_pointer y=x->prior(); + this->final_delete_node_( + static_cast<final_node_type*>(node_type::from_impl(x))); + x=y; + } + } + + void delete_all_nodes_(hashed_non_unique_tag) + { + for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){ + node_impl_pointer y=x->prior(); + if(y->next()!=node_impl_type::base_pointer_from(x)&& + y->next()->prior()!=x){ /* n-1 of group */ + /* Make the second node prior() pointer back-linked so that it won't + * refer to a deleted node when the time for its own destruction comes. + */ + + node_impl_pointer first=node_impl_type::pointer_from(y->next()); + first->next()->prior()=first; } + this->final_delete_node_( + static_cast<final_node_type*>(node_type::from_impl(x))); + x=y; } } void clear_() { super::clear_(); - buckets.clear(); - first_bucket=buckets.size(); + buckets.clear(header()->impl()); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) safe_super::detach_dereferenceable_iterators(); @@ -762,12 +887,11 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x) { std::swap(key,x.key); - std::swap(hash,x.hash); - std::swap(eq,x.eq); + 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); @@ -776,33 +900,42 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: super::swap_(x); } - bool replace_(value_param_type v,node_type* x) + void swap_elements_( + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x) { - if(eq(key(v),key(x->value()))){ - return super::replace_(v,x); - } + buckets.swap(x.buckets); + std::swap(mlf,x.mlf); + std::swap(max_load,x.max_load); + +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) + safe_super::swap(x); +#endif - node_impl_pointer y=prev(x); - unlink_next(y); + super::swap_elements_(x); + } + + template<typename Variant> + bool replace_(value_param_type v,node_type* x,Variant variant) + { + if(eq_(key(v),key(x->value()))){ + return super::replace_(v,x,variant); + } + + unlink_undo undo; + unlink(x,undo); BOOST_TRY{ - std::size_t buc=find_bucket(v); - node_impl_pointer pos=buckets.at(buc); - if(link_point(v,pos,Category())&&super::replace_(v,x)){ + std::size_t buc=find_bucket(v); + link_info pos(buckets.at(buc)); + if(link_point(v,pos)&&super::replace_(v,x,variant)){ 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); + undo(); return false; } BOOST_CATCH(...){ - link(x,y); + undo(); BOOST_RETHROW; } BOOST_CATCH_END @@ -814,7 +947,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: bool b; BOOST_TRY{ buc=find_bucket(x->value()); - b=in_place(x->impl(),key(x->value()),buc,Category()); + b=in_place(x->impl(),key(x->value()),buc); } BOOST_CATCH(...){ erase_(x); @@ -824,9 +957,8 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: if(!b){ unlink(x); BOOST_TRY{ - node_impl_pointer pos=buckets.at(buc); - if(!link_point(x->value(),pos,Category())){ - first_bucket=buckets.first_nonempty(first_bucket); + link_info pos(buckets.at(buc)); + if(!link_point(x->value(),pos)){ super::erase_(x); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) @@ -835,15 +967,8 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: return false; } link(x,pos); - if(first_bucket>buc){ - first_bucket=buc; - } - else if(first_bucket<buc){ - first_bucket=buckets.first_nonempty(first_bucket); - } } BOOST_CATCH(...){ - first_bucket=buckets.first_nonempty(first_bucket); super::erase_(x); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) @@ -858,7 +983,7 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: BOOST_TRY{ if(!super::modify_(x)){ unlink(x); - first_bucket=buckets.first_nonempty(first_bucket); + #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); #endif @@ -868,7 +993,6 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: } BOOST_CATCH(...){ unlink(x); - first_bucket=buckets.first_nonempty(first_bucket); #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) detach_iterators(x); @@ -882,35 +1006,83 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: bool modify_rollback_(node_type* x) { std::size_t buc=find_bucket(x->value()); - if(in_place(x->impl(),key(x->value()),buc,Category())){ + if(in_place(x->impl(),key(x->value()),buc)){ return super::modify_rollback_(x); } - node_impl_pointer y=prev(x); - unlink_next(y); + unlink_undo undo; + unlink(x,undo); BOOST_TRY{ - node_impl_pointer pos=buckets.at(buc); - if(link_point(x->value(),pos,Category())&&super::modify_rollback_(x)){ + link_info pos(buckets.at(buc)); + if(link_point(x->value(),pos)&&super::modify_rollback_(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); + undo(); return false; } BOOST_CATCH(...){ - link(x,y); + undo(); BOOST_RETHROW; } BOOST_CATCH_END } + /* comparison */ + +#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + /* defect macro refers to class, not function, templates, but anyway */ + + template<typename K,typename H,typename P,typename S,typename T,typename C> + friend bool operator==( + const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y); +#endif + + bool equals(const hashed_index& x)const{return equals(x,Category());} + + bool equals(const hashed_index& x,hashed_unique_tag)const + { + if(size()!=x.size())return false; + for(const_iterator it=begin(),it_end=end(),it2_end=x.end(); + it!=it_end;++it){ + const_iterator it2=x.find(key(*it)); + if(it2==it2_end||!(*it==*it2))return false; + } + return true; + } + + bool equals(const hashed_index& x,hashed_non_unique_tag)const + { + if(size()!=x.size())return false; + for(const_iterator it=begin(),it_end=end();it!=it_end;){ + const_iterator it2,it2_last; + boost::tie(it2,it2_last)=x.equal_range(key(*it)); + if(it2==it2_last)return false; + + const_iterator it_last=make_iterator( + node_type::from_impl(end_of_range(it.get_node()->impl()))); + if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false; + + /* From is_permutation code in + * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf + */ + + for(;it!=it_last;++it,++it2){ + if(!(*it==*it2))break; + } + if(it!=it_last){ + for(const_iterator scan=it;scan!=it_last;++scan){ + if(std::find(it,scan,*scan)!=scan)continue; + std::ptrdiff_t matches=std::count(it2,it2_last,*scan); + if(matches==0||matches!=std::count(scan,it_last,*scan))return false; + } + it=it_last; + } + } + return true; + } + #if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION) /* serialization */ @@ -956,8 +1128,6 @@ BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS: if(s1!=size())return false; } - if(first_bucket!=buckets.first_nonempty(0))return false; - return super::invariant_(); } @@ -976,64 +1146,147 @@ private: return bucket(key(v)); } + struct link_info_non_unique + { + link_info_non_unique(node_impl_base_pointer pos): + first(pos),last(node_impl_base_pointer(0)){} + + operator const node_impl_base_pointer&()const{return this->first;} + + node_impl_base_pointer first,last; + }; + + typedef typename mpl::if_< + is_same<Category,hashed_unique_tag>, + node_impl_base_pointer, + link_info_non_unique + >::type link_info; + + bool link_point(value_param_type v,link_info& pos) + { + return link_point(v,pos,Category()); + } + bool link_point( - value_param_type v,node_impl_pointer& pos,hashed_unique_tag) + value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag) { - node_impl_pointer x=pos->next(); - while(x!=pos){ - if(eq(key(v),key(node_type::from_impl(x)->value()))){ - pos=x; + for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0); + x=node_alg::after_local(x)){ + if(eq_(key(v),key(node_type::from_impl(x)->value()))){ + pos=node_impl_type::base_pointer_from(x); return false; } - x=x->next(); } return true; } bool link_point( - value_param_type v,node_impl_pointer& pos,hashed_non_unique_tag) + value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag) { - node_impl_pointer prev=pos; - node_impl_pointer x=pos->next(); - while(x!=pos){ - if(eq(key(v),key(node_type::from_impl(x)->value()))){ - pos=prev; + for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0); + x=node_alg::next_to_inspect(x)){ + if(eq_(key(v),key(node_type::from_impl(x)->value()))){ + pos.first=node_impl_type::base_pointer_from(x); + pos.last=node_impl_type::base_pointer_from(last_of_range(x)); return true; } - prev=x; - x=x->next(); } return true; } - - static void link(node_type* x,node_impl_pointer pos) + + node_impl_pointer last_of_range(node_impl_pointer x)const { - node_impl_type::link(x->impl(),pos); - }; + return last_of_range(x,Category()); + } - static void link(node_impl_pointer x,node_impl_pointer pos) + node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const { - node_impl_type::link(x,pos); - }; + return x; + } - static void unlink(node_type* x) + node_impl_pointer last_of_range( + node_impl_pointer x,hashed_non_unique_tag)const { - node_impl_type::unlink(x->impl()); - }; + node_impl_base_pointer y=x->next(); + node_impl_pointer z=y->prior(); + if(z==x){ /* range of size 1 or 2 */ + node_impl_pointer yy=node_impl_type::pointer_from(y); + return + eq_( + key(node_type::from_impl(x)->value()), + key(node_type::from_impl(yy)->value()))?yy:x; + } + else if(z->prior()==x) /* last of bucket */ + return x; + else /* group of size>2 */ + return z; + } + + node_impl_pointer end_of_range(node_impl_pointer x)const + { + return end_of_range(x,Category()); + } - static node_impl_pointer prev(node_type* x) + node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const { - return node_impl_type::prev(x->impl()); + return node_alg::after(last_of_range(x)); + } + + node_impl_pointer end_of_range( + node_impl_pointer x,hashed_non_unique_tag)const + { + node_impl_base_pointer y=x->next(); + node_impl_pointer z=y->prior(); + if(z==x){ /* range of size 1 or 2 */ + node_impl_pointer yy=node_impl_type::pointer_from(y); + if(!eq_( + key(node_type::from_impl(x)->value()), + key(node_type::from_impl(yy)->value())))yy=x; + return yy->next()->prior()==yy? + node_impl_type::pointer_from(yy->next()): + yy->next()->prior(); + } + else if(z->prior()==x) /* last of bucket */ + return z; + else /* group of size>2 */ + return z->next()->prior()==z? + node_impl_type::pointer_from(z->next()): + z->next()->prior(); } - static node_impl_pointer prev_from(node_type* x,node_impl_pointer y) + void link(node_type* x,const link_info& pos) { - return node_impl_type::prev_from(x->impl(),y); + link(x,pos,Category()); } - static void unlink_next(node_impl_pointer x) + void link(node_type* x,node_impl_base_pointer pos,hashed_unique_tag) { - node_impl_type::unlink_next(x); + node_alg::link(x->impl(),pos,header()->impl()); + } + + void link(node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag) + { + if(pos.last==node_impl_base_pointer(0)){ + node_alg::link(x->impl(),pos.first,header()->impl()); + } + else{ + node_alg::link( + x->impl(), + node_impl_type::pointer_from(pos.first), + node_impl_type::pointer_from(pos.last)); + } + } + + void unlink(node_type* x) + { + node_alg::unlink(x->impl()); + } + + typedef typename node_alg::unlink_undo unlink_undo; + + void unlink(node_type* x,unlink_undo& undo) + { + node_alg::unlink(x->impl(),undo); } void calculate_max_load() @@ -1043,112 +1296,206 @@ private: if(max_load>fml)max_load=static_cast<size_type>(fml); } - void reserve(size_type n) + void reserve_for_insert(size_type n) { if(n>max_load){ size_type bc =(std::numeric_limits<size_type>::max)(); - float fbc=static_cast<float>(1+n/mlf); + float fbc=static_cast<float>(1+static_cast<double>(n)/mlf); if(bc>fbc)bc =static_cast<size_type>(fbc); unchecked_rehash(bc); } } - void unchecked_rehash(size_type n) + void unchecked_rehash(size_type n){unchecked_rehash(n,Category());} + + void unchecked_rehash(size_type n,hashed_unique_tag) { - bucket_array_type buckets1(get_allocator(),header()->impl(),n); - auto_space<std::size_t,allocator_type> hashes(get_allocator(),size()); + node_impl_type cpy_end_node; + node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node), + end_=header()->impl(); + bucket_array_type buckets_cpy(get_allocator(),cpy_end,n); - std::size_t i=0; - node_impl_pointer x=buckets.begin(); - node_impl_pointer x_end=buckets.end(); - for(;x!=x_end;++x){ - node_impl_pointer y=x->next(); - while(y!=x){ - hashes.data()[i++]=hash(key(node_type::from_impl(y)->value())); - y=y->next(); + if(size()!=0){ + auto_space< + std::size_t,allocator_type> hashes(get_allocator(),size()); + auto_space< + node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size()); + std::size_t i=0,size_=size(); + bool within_bucket=false; + BOOST_TRY{ + for(;i!=size_;++i){ + node_impl_pointer x=end_->prior(); + + /* only this can possibly throw */ + std::size_t h=hash_(key(node_type::from_impl(x)->value())); + + hashes.data()[i]=h; + node_ptrs.data()[i]=x; + within_bucket=!node_alg::unlink_last(end_); + node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end); + } } + BOOST_CATCH(...){ + if(i!=0){ + std::size_t prev_buc=buckets.position(hashes.data()[i-1]); + if(!within_bucket)prev_buc=~prev_buc; + + for(std::size_t j=i;j--;){ + std::size_t buc=buckets.position(hashes.data()[j]); + node_impl_pointer x=node_ptrs.data()[j]; + if(buc==prev_buc)node_alg::append(x,end_); + else node_alg::link(x,buckets.at(buc),end_); + prev_buc=buc; + } + } + BOOST_RETHROW; + } + BOOST_CATCH_END } - i=0; - x=buckets.begin(); - for(;x!=x_end;++x){ - node_impl_pointer y=x->next(); - while(y!=x){ - node_impl_pointer z=y->next(); - std::size_t buc1=buckets1.position(hashes.data()[i++]); - node_impl_pointer x1=buckets1.at(buc1); - link(y,x1); - y=z; + end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_; + end_->next()=cpy_end->next(); + end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_; + buckets.swap(buckets_cpy); + calculate_max_load(); + } + + void unchecked_rehash(size_type n,hashed_non_unique_tag) + { + node_impl_type cpy_end_node; + node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node), + end_=header()->impl(); + bucket_array_type buckets_cpy(get_allocator(),cpy_end,n); + + if(size()!=0){ + auto_space< + std::size_t,allocator_type> hashes(get_allocator(),size()); + auto_space< + node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size()); + std::size_t i=0; + bool within_bucket=false; + BOOST_TRY{ + for(;;++i){ + node_impl_pointer x=end_->prior(); + if(x==end_)break; + + /* only this can possibly throw */ + std::size_t h=hash_(key(node_type::from_impl(x)->value())); + + hashes.data()[i]=h; + node_ptrs.data()[i]=x; + std::pair<node_impl_pointer,bool> p= + node_alg::unlink_last_group(end_); + node_alg::link_range( + p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end); + within_bucket=!(p.second); + } } + BOOST_CATCH(...){ + if(i!=0){ + std::size_t prev_buc=buckets.position(hashes.data()[i-1]); + if(!within_bucket)prev_buc=~prev_buc; + + for(std::size_t j=i;j--;){ + std::size_t buc=buckets.position(hashes.data()[j]); + node_impl_pointer x=node_ptrs.data()[j], + y= + x->prior()->next()!=node_impl_type::base_pointer_from(x)&& + x->prior()->next()->prior()!=x? + node_impl_type::pointer_from(x->prior()->next()):x; + node_alg::unlink_range(y,x); + if(buc==prev_buc)node_alg::append_range(y,x,end_); + else node_alg::link_range(y,x,buckets.at(buc),end_); + prev_buc=buc; + } + } + BOOST_RETHROW; + } + BOOST_CATCH_END } - buckets.swap(buckets1); + end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_; + end_->next()=cpy_end->next(); + end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_; + buckets.swap(buckets_cpy); calculate_max_load(); - first_bucket=buckets.first_nonempty(0); + } + + bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const + { + return in_place(x,k,buc,Category()); } bool in_place( node_impl_pointer x,key_param_type k,std::size_t buc, hashed_unique_tag)const { - std::less_equal<node_impl_pointer> leq; - node_impl_pointer bbegin=buckets.begin(); - node_impl_pointer bend=buckets.end(); - node_impl_pointer pbuc=x->next(); - - while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next(); - if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false; - - node_impl_pointer y=x; - while(y->next()!=x){ - y=y->next(); - if(y==pbuc)continue; - if(eq(k,key(node_type::from_impl(y)->value())))return false; + bool found=false; + for(node_impl_pointer y=buckets.at(buc)->prior(); + y!=node_impl_pointer(0);y=node_alg::after_local(y)){ + if(y==x)found=true; + else if(eq_(k,key(node_type::from_impl(y)->value())))return false; } - return true; + return found; } bool in_place( node_impl_pointer x,key_param_type k,std::size_t buc, hashed_non_unique_tag)const { - std::less_equal<node_impl_pointer> leq; - node_impl_pointer bbegin=buckets.begin(); - node_impl_pointer bend=buckets.end(); - node_impl_pointer pbuc=x->next(); - - while(!leq(bbegin,pbuc)||!leq(pbuc,bend))pbuc=pbuc->next(); - if(buc!=static_cast<std::size_t>(pbuc-bbegin))return false; - - node_impl_pointer y=x->next(); - if(y!=pbuc){ - if(eq(k,key(node_type::from_impl(y)->value()))){ - /* adjacent to equivalent element -> in place */ - return true; - } - else{ - y=y->next(); - while(y!=pbuc){ - if(eq(k,key(node_type::from_impl(y)->value())))return false; - y=y->next(); + bool found=false; + int range_size=0; + for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){ + if(node_alg::is_first_of_group(y)){ /* group of 3 or more */ + if(y==x){ + /* in place <-> equal to some other member of the group */ + return eq_( + k, + key(node_type::from_impl( + node_impl_type::pointer_from(y->next()))->value())); + } + else{ + node_impl_pointer z= + node_alg::after_local(y->next()->prior()); /* end of range */ + if(eq_(k,key(node_type::from_impl(y)->value()))){ + if(found)return false; /* x lies outside */ + do{ + if(y==x)return true; + y=node_alg::after_local(y); + }while(y!=z); + return false; /* x not found */ + } + else{ + if(range_size==1&&!found)return false; + if(range_size==2)return found; + range_size=0; + y=z; /* skip range (and potentially x, too, which is fine) */ + } } } - } - while(y->next()!=x){ - y=y->next(); - if(eq(k,key(node_type::from_impl(y)->value()))){ - while(y->next()!=x){ - y=y->next(); - if(!eq(k,key(node_type::from_impl(y)->value())))return false; + else{ /* group of 1 or 2 */ + if(y==x){ + if(range_size==1)return true; + range_size=1; + found=true; } - /* after a group of equivalent elements --> in place */ - return true; + else if(eq_(k,key(node_type::from_impl(y)->value()))){ + if(range_size==0&&found)return false; + if(range_size==1&&!found)return false; + if(range_size==2)return false; + ++range_size; + } + else{ + if(range_size==1&&!found)return false; + if(range_size==2)return found; + range_size=0; + } + y=node_alg::after_local(y); } } - return true; + return found; } - #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE) void detach_iterators(node_type* x) { @@ -1157,13 +1504,35 @@ private: } #endif + template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> + std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT; + std::pair<final_node_type*,bool>p= + this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + return std::pair<iterator,bool>(make_iterator(p.first),p.second); + } + + template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK> + iterator emplace_hint_impl( + iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK) + { + 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_emplace_hint_( + static_cast<final_node_type*>(position.get_node()), + BOOST_MULTI_INDEX_FORWARD_PARAM_PACK); + return make_iterator(p.first); + } + key_from_value key; - hasher hash; - key_equal eq; + hasher hash_; + key_equal eq_; bucket_array_type buckets; float mlf; size_type max_load; - std::size_t first_bucket; #if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\ BOOST_WORKAROUND(__MWERKS__,<=0x3003) @@ -1171,6 +1540,30 @@ private: #endif }; +/* comparison */ + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator==( + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y) +{ + return x.equals(y); +} + +template< + typename KeyFromValue,typename Hash,typename Pred, + typename SuperMeta,typename TagList,typename Category +> +bool operator!=( + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x, + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y) +{ + return !(x==y); +} + /* specialized algorithms */ template< @@ -1201,7 +1594,7 @@ struct hashed_unique template<typename Super> struct node_class { - typedef detail::hashed_index_node<Super> type; + typedef detail::hashed_index_node<Super,detail::hashed_unique_tag> type; }; template<typename SuperMeta> @@ -1226,7 +1619,8 @@ struct hashed_non_unique template<typename Super> struct node_class { - typedef detail::hashed_index_node<Super> type; + typedef detail::hashed_index_node< + Super,detail::hashed_non_unique_tag> type; }; template<typename SuperMeta> @@ -1257,5 +1651,6 @@ inline boost::mpl::true_* boost_foreach_is_noncopyable( } #undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT +#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF #endif |