-/* 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)
#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
#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
/* 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
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)&&\
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;
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:
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
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)
{
/* 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);
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);
{
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)
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);
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)
{
}
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);
#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>
}
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);
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_();
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 */
template<typename CompatibleKey>
iterator find(const CompatibleKey& k)const
{
- return find(k,hash,eq);
+ return find(k,hash_,eq_);
}
template<
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();
}
template<typename CompatibleKey>
size_type count(const CompatibleKey& k)const
{
- return count(k,hash,eq);
+ return count(k,hash_,eq_);
}
template<
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<
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)
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)
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);}
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);
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();
}
#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 */
#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)
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();
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);
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
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);
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)
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)
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
}
BOOST_CATCH(...){
unlink(x);
- first_bucket=buckets.first_nonempty(first_bucket);
#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
detach_iterators(x);
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 */
if(s1!=size())return false;
}
- if(first_bucket!=buckets.first_nonempty(0))return false;
-
return super::invariant_();
}
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()
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)
{
}
#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)
#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<
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>
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>
}
#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
+#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF
#endif
projects / platform / upstream / boost.git / blobdiff