1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/multi_index/hashed_index.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,1075 @@
1.4 +/* Copyright 2003-2007 Joaquín M López Muñoz.
1.5 + * Distributed under the Boost Software License, Version 1.0.
1.6 + * (See accompanying file LICENSE_1_0.txt or copy at
1.7 + * http://www.boost.org/LICENSE_1_0.txt)
1.8 + *
1.9 + * See http://www.boost.org/libs/multi_index for library home page.
1.10 + */
1.11 +
1.12 +#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
1.13 +#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP
1.14 +
1.15 +#if defined(_MSC_VER)&&(_MSC_VER>=1200)
1.16 +#pragma once
1.17 +#endif
1.18 +
1.19 +#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
1.20 +#include <algorithm>
1.21 +#include <boost/call_traits.hpp>
1.22 +#include <boost/detail/allocator_utilities.hpp>
1.23 +#include <boost/detail/no_exceptions_support.hpp>
1.24 +#include <boost/detail/workaround.hpp>
1.25 +#include <boost/limits.hpp>
1.26 +#include <boost/mpl/push_front.hpp>
1.27 +#include <boost/multi_index/detail/access_specifier.hpp>
1.28 +#include <boost/multi_index/detail/auto_space.hpp>
1.29 +#include <boost/multi_index/detail/bucket_array.hpp>
1.30 +#include <boost/multi_index/detail/hash_index_iterator.hpp>
1.31 +#include <boost/multi_index/detail/modify_key_adaptor.hpp>
1.32 +#include <boost/multi_index/detail/safe_ctr_proxy.hpp>
1.33 +#include <boost/multi_index/detail/safe_mode.hpp>
1.34 +#include <boost/multi_index/detail/scope_guard.hpp>
1.35 +#include <boost/multi_index/hashed_index_fwd.hpp>
1.36 +#include <boost/tuple/tuple.hpp>
1.37 +#include <cstddef>
1.38 +#include <functional>
1.39 +#include <utility>
1.40 +
1.41 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.42 +#include <boost/serialization/nvp.hpp>
1.43 +#endif
1.44 +
1.45 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.46 +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \
1.47 + detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
1.48 + detail::make_obj_guard(*this,&hashed_index::check_invariant_); \
1.49 + BOOST_JOIN(check_invariant_,__LINE__).touch();
1.50 +#else
1.51 +#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1.52 +#endif
1.53 +
1.54 +namespace boost{
1.55 +
1.56 +namespace multi_index{
1.57 +
1.58 +namespace detail{
1.59 +
1.60 +/* hashed_index adds a layer of hashed indexing to a given Super */
1.61 +
1.62 +/* Most of the implementation of unique and non-unique indices is
1.63 + * shared. We tell from one another on instantiation time by using
1.64 + * these tags.
1.65 + */
1.66 +
1.67 +struct hashed_unique_tag{};
1.68 +struct hashed_non_unique_tag{};
1.69 +
1.70 +template<
1.71 + typename KeyFromValue,typename Hash,typename Pred,
1.72 + typename SuperMeta,typename TagList,typename Category
1.73 +>
1.74 +class hashed_index:
1.75 + BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
1.76 +
1.77 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.78 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.79 + ,public safe_ctr_proxy_impl<
1.80 + hashed_index_iterator<
1.81 + hashed_index_node<typename SuperMeta::type::node_type>,
1.82 + bucket_array<typename SuperMeta::type::final_allocator_type> >,
1.83 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
1.84 +#else
1.85 + ,public safe_mode::safe_container<
1.86 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category> >
1.87 +#endif
1.88 +#endif
1.89 +
1.90 +{
1.91 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.92 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.93 +/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
1.94 + * lifetime of const references bound to temporaries --precisely what
1.95 + * scopeguards are.
1.96 + */
1.97 +
1.98 +#pragma parse_mfunc_templ off
1.99 +#endif
1.100 +
1.101 + typedef typename SuperMeta::type super;
1.102 +
1.103 +protected:
1.104 + typedef hashed_index_node<
1.105 + typename super::node_type> node_type;
1.106 + typedef bucket_array<
1.107 + typename super::final_allocator_type> bucket_array_type;
1.108 +
1.109 +public:
1.110 + /* types */
1.111 +
1.112 + typedef typename KeyFromValue::result_type key_type;
1.113 + typedef typename node_type::value_type value_type;
1.114 + typedef KeyFromValue key_from_value;
1.115 + typedef Hash hasher;
1.116 + typedef Pred key_equal;
1.117 + typedef tuple<std::size_t,
1.118 + key_from_value,hasher,key_equal> ctor_args;
1.119 + typedef typename super::final_allocator_type allocator_type;
1.120 + typedef typename allocator_type::pointer pointer;
1.121 + typedef typename allocator_type::const_pointer const_pointer;
1.122 + typedef typename allocator_type::reference reference;
1.123 + typedef typename allocator_type::const_reference const_reference;
1.124 + typedef std::size_t size_type;
1.125 + typedef std::ptrdiff_t difference_type;
1.126 +
1.127 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.128 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.129 + typedef safe_mode::safe_iterator<
1.130 + hashed_index_iterator<
1.131 + node_type,bucket_array_type>,
1.132 + safe_ctr_proxy<
1.133 + hashed_index_iterator<
1.134 + node_type,bucket_array_type> > > iterator;
1.135 +#else
1.136 + typedef safe_mode::safe_iterator<
1.137 + hashed_index_iterator<
1.138 + node_type,bucket_array_type>,
1.139 + hashed_index> iterator;
1.140 +#endif
1.141 +#else
1.142 + typedef hashed_index_iterator<
1.143 + node_type,bucket_array_type> iterator;
1.144 +#endif
1.145 +
1.146 + typedef iterator const_iterator;
1.147 +
1.148 + typedef iterator local_iterator;
1.149 + typedef const_iterator const_local_iterator;
1.150 + typedef TagList tag_list;
1.151 +
1.152 +protected:
1.153 + typedef typename super::final_node_type final_node_type;
1.154 + typedef tuples::cons<
1.155 + ctor_args,
1.156 + typename super::ctor_args_list> ctor_args_list;
1.157 + typedef typename mpl::push_front<
1.158 + typename super::index_type_list,
1.159 + hashed_index>::type index_type_list;
1.160 + typedef typename mpl::push_front<
1.161 + typename super::iterator_type_list,
1.162 + iterator>::type iterator_type_list;
1.163 + typedef typename mpl::push_front<
1.164 + typename super::const_iterator_type_list,
1.165 + const_iterator>::type const_iterator_type_list;
1.166 + typedef typename super::copy_map_type copy_map_type;
1.167 +
1.168 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.169 + typedef typename super::index_saver_type index_saver_type;
1.170 + typedef typename super::index_loader_type index_loader_type;
1.171 +#endif
1.172 +
1.173 +private:
1.174 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.175 +#if BOOST_WORKAROUND(BOOST_MSVC,<1300)
1.176 + typedef safe_ctr_proxy_impl<
1.177 + hashed_index_iterator<
1.178 + node_type,
1.179 + bucket_array_type>,
1.180 + hashed_index> safe_super;
1.181 +#else
1.182 + typedef safe_mode::safe_container<
1.183 + hashed_index> safe_super;
1.184 +#endif
1.185 +#endif
1.186 +
1.187 + typedef typename call_traits<value_type>::param_type value_param_type;
1.188 + typedef typename call_traits<
1.189 + key_type>::param_type key_param_type;
1.190 +
1.191 +public:
1.192 +
1.193 + /* construct/destroy/copy
1.194 + * Default and copy ctors are in the protected section as indices are
1.195 + * not supposed to be created on their own. No range ctor either.
1.196 + */
1.197 +
1.198 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
1.199 + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
1.200 + {
1.201 + this->final()=x.final();
1.202 + return *this;
1.203 + }
1.204 +
1.205 + allocator_type get_allocator()const
1.206 + {
1.207 + return this->final().get_allocator();
1.208 + }
1.209 +
1.210 + /* size and capacity */
1.211 +
1.212 + bool empty()const{return this->final_empty_();}
1.213 + size_type size()const{return this->final_size_();}
1.214 + size_type max_size()const{return this->final_max_size_();}
1.215 +
1.216 + /* iterators */
1.217 +
1.218 + iterator begin()
1.219 + {
1.220 + return make_iterator(
1.221 + node_type::from_impl(buckets.at(first_bucket)->next()));
1.222 + }
1.223 +
1.224 + const_iterator begin()const
1.225 + {
1.226 + return make_iterator(
1.227 + node_type::from_impl(buckets.at(first_bucket)->next()));
1.228 + }
1.229 +
1.230 + iterator end(){return make_iterator(header());}
1.231 + const_iterator end()const{return make_iterator(header());}
1.232 +
1.233 + /* modifiers */
1.234 +
1.235 + std::pair<iterator,bool> insert(value_param_type x)
1.236 + {
1.237 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.238 + std::pair<final_node_type*,bool> p=this->final_insert_(x);
1.239 + return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1.240 + }
1.241 +
1.242 + iterator insert(iterator position,value_param_type x)
1.243 + {
1.244 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.245 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.246 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.247 + std::pair<final_node_type*,bool> p=this->final_insert_(
1.248 + x,static_cast<final_node_type*>(position.get_node()));
1.249 + return make_iterator(p.first);
1.250 + }
1.251 +
1.252 + template<typename InputIterator>
1.253 + void insert(InputIterator first,InputIterator last)
1.254 + {
1.255 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.256 + iterator hint=end();
1.257 + for(;first!=last;++first)hint=insert(hint,*first);
1.258 + }
1.259 +
1.260 + iterator erase(iterator position)
1.261 + {
1.262 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.263 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.264 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.265 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.266 + this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
1.267 + return position;
1.268 + }
1.269 +
1.270 + size_type erase(key_param_type k)
1.271 + {
1.272 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.273 +
1.274 + size_type s=0;
1.275 + std::size_t buc=buckets.position(hash(k));
1.276 + hashed_index_node_impl* x=buckets.at(buc);
1.277 + hashed_index_node_impl* y=x->next();
1.278 + while(y!=x){
1.279 + if(eq(k,key(node_type::from_impl(y)->value()))){
1.280 + bool b;
1.281 + do{
1.282 + hashed_index_node_impl* z=y->next();
1.283 + b=z!=x&&eq(
1.284 + key(node_type::from_impl(y)->value()),
1.285 + key(node_type::from_impl(z)->value()));
1.286 + this->final_erase_(
1.287 + static_cast<final_node_type*>(node_type::from_impl(y)));
1.288 + y=z;
1.289 + ++s;
1.290 + }while(b);
1.291 + break;
1.292 + }
1.293 + y=y->next();
1.294 + }
1.295 + return s;
1.296 + }
1.297 +
1.298 + iterator erase(iterator first,iterator last)
1.299 + {
1.300 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
1.301 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
1.302 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
1.303 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
1.304 + BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
1.305 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.306 + while(first!=last){
1.307 + first=erase(first);
1.308 + }
1.309 + return first;
1.310 + }
1.311 +
1.312 + bool replace(iterator position,value_param_type x)
1.313 + {
1.314 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.315 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.316 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.317 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.318 + return this->final_replace_(
1.319 + x,static_cast<final_node_type*>(position.get_node()));
1.320 + }
1.321 +
1.322 + template<typename Modifier>
1.323 + bool modify(iterator position,Modifier mod)
1.324 + {
1.325 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.326 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.327 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.328 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.329 +
1.330 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.331 + /* MSVC++ 6.0 optimizer on safe mode code chokes if this
1.332 + * this is not added. Left it for all compilers as it does no
1.333 + * harm.
1.334 + */
1.335 +
1.336 + position.detach();
1.337 +#endif
1.338 +
1.339 + return this->final_modify_(
1.340 + mod,static_cast<final_node_type*>(position.get_node()));
1.341 + }
1.342 +
1.343 + template<typename Modifier>
1.344 + bool modify_key(iterator position,Modifier mod)
1.345 + {
1.346 + BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1.347 + BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
1.348 + BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1.349 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.350 + return modify(
1.351 + position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
1.352 + }
1.353 +
1.354 + void clear()
1.355 + {
1.356 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.357 + this->final_clear_();
1.358 + }
1.359 +
1.360 + void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
1.361 + {
1.362 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.363 + this->final_swap_(x.final());
1.364 + }
1.365 +
1.366 + /* observers */
1.367 +
1.368 + key_from_value key_extractor()const{return key;}
1.369 + hasher hash_function()const{return hash;}
1.370 + key_equal key_eq()const{return eq;}
1.371 +
1.372 + /* lookup */
1.373 +
1.374 + /* Internally, these ops rely on const_iterator being the same
1.375 + * type as iterator.
1.376 + */
1.377 +
1.378 + template<typename CompatibleKey>
1.379 + iterator find(const CompatibleKey& k)const
1.380 + {
1.381 + return find(k,hash,eq);
1.382 + }
1.383 +
1.384 + template<
1.385 + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1.386 + >
1.387 + iterator find(
1.388 + const CompatibleKey& k,
1.389 + const CompatibleHash& hash,const CompatiblePred& eq)const
1.390 + {
1.391 + std::size_t buc=buckets.position(hash(k));
1.392 + hashed_index_node_impl* x=buckets.at(buc);
1.393 + hashed_index_node_impl* y=x->next();
1.394 + while(y!=x){
1.395 + if(eq(k,key(node_type::from_impl(y)->value()))){
1.396 + return make_iterator(node_type::from_impl(y));
1.397 + }
1.398 + y=y->next();
1.399 + }
1.400 + return end();
1.401 + }
1.402 +
1.403 + template<typename CompatibleKey>
1.404 + size_type count(const CompatibleKey& k)const
1.405 + {
1.406 + return count(k,hash,eq);
1.407 + }
1.408 +
1.409 + template<
1.410 + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1.411 + >
1.412 + size_type count(
1.413 + const CompatibleKey& k,
1.414 + const CompatibleHash& hash,const CompatiblePred& eq)const
1.415 + {
1.416 + size_type res=0;
1.417 + std::size_t buc=buckets.position(hash(k));
1.418 + hashed_index_node_impl* x=buckets.at(buc);
1.419 + hashed_index_node_impl* y=x->next();
1.420 + while(y!=x){
1.421 + if(eq(k,key(node_type::from_impl(y)->value()))){
1.422 + do{
1.423 + ++res;
1.424 + y=y->next();
1.425 + }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
1.426 + break;
1.427 + }
1.428 + y=y->next();
1.429 + }
1.430 + return res;
1.431 + }
1.432 +
1.433 + template<typename CompatibleKey>
1.434 + std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
1.435 + {
1.436 + return equal_range(k,hash,eq);
1.437 + }
1.438 +
1.439 + template<
1.440 + typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1.441 + >
1.442 + std::pair<iterator,iterator> equal_range(
1.443 + const CompatibleKey& k,
1.444 + const CompatibleHash& hash,const CompatiblePred& eq)const
1.445 + {
1.446 + std::size_t buc=buckets.position(hash(k));
1.447 + hashed_index_node_impl* x=buckets.at(buc);
1.448 + hashed_index_node_impl* y=x->next();
1.449 + while(y!=x){
1.450 + if(eq(k,key(node_type::from_impl(y)->value()))){
1.451 + hashed_index_node_impl* y0=y;
1.452 + do{
1.453 + y=y->next();
1.454 + }while(y!=x&&eq(k,key(node_type::from_impl(y)->value())));
1.455 + if(y==x){
1.456 + do{
1.457 + ++y;
1.458 + }while(y==y->next());
1.459 + y=y->next();
1.460 + }
1.461 + return std::pair<iterator,iterator>(
1.462 + make_iterator(node_type::from_impl(y0)),
1.463 + make_iterator(node_type::from_impl(y)));
1.464 + }
1.465 + y=y->next();
1.466 + }
1.467 + return std::pair<iterator,iterator>(end(),end());
1.468 + }
1.469 +
1.470 + /* bucket interface */
1.471 +
1.472 + size_type bucket_count()const{return buckets.size();}
1.473 + size_type max_bucket_count()const{return static_cast<size_type>(-1);}
1.474 +
1.475 + size_type bucket_size(size_type n)const
1.476 + {
1.477 + size_type res=0;
1.478 + hashed_index_node_impl* x=buckets.at(n);
1.479 + hashed_index_node_impl* y=x->next();
1.480 + while(y!=x){
1.481 + ++res;
1.482 + y=y->next();
1.483 + }
1.484 + return res;
1.485 + }
1.486 +
1.487 + size_type bucket(key_param_type k)const
1.488 + {
1.489 + return buckets.position(hash(k));
1.490 + }
1.491 +
1.492 + local_iterator begin(size_type n)
1.493 + {
1.494 + return const_cast<const hashed_index*>(this)->begin(n);
1.495 + }
1.496 +
1.497 + const_local_iterator begin(size_type n)const
1.498 + {
1.499 + hashed_index_node_impl* x=buckets.at(n);
1.500 + hashed_index_node_impl* y=x->next();
1.501 + if(y==x)return end();
1.502 + return make_iterator(node_type::from_impl(y));
1.503 + }
1.504 +
1.505 + local_iterator end(size_type n)
1.506 + {
1.507 + return const_cast<const hashed_index*>(this)->end(n);
1.508 + }
1.509 +
1.510 + const_local_iterator end(size_type n)const
1.511 + {
1.512 + hashed_index_node_impl* x=buckets.at(n);
1.513 + if(x==x->next())return end();
1.514 + do{
1.515 + ++x;
1.516 + }while(x==x->next());
1.517 + return make_iterator(node_type::from_impl(x->next()));
1.518 + }
1.519 +
1.520 + /* hash policy */
1.521 +
1.522 + float load_factor()const{return static_cast<float>(size())/bucket_count();}
1.523 + float max_load_factor()const{return mlf;}
1.524 + void max_load_factor(float z){mlf=z;calculate_max_load();}
1.525 +
1.526 + void rehash(size_type n)
1.527 + {
1.528 + BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1.529 + if(size()<max_load&&n<=bucket_count())return;
1.530 +
1.531 + size_type bc =(std::numeric_limits<size_type>::max)();
1.532 + float fbc=static_cast<float>(1+size()/mlf);
1.533 + if(bc>fbc){
1.534 + bc=static_cast<size_type>(fbc);
1.535 + if(bc<n)bc=n;
1.536 + }
1.537 + unchecked_rehash(bc);
1.538 + }
1.539 +
1.540 +BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
1.541 + hashed_index(const ctor_args_list& args_list,const allocator_type& al):
1.542 + super(args_list.get_tail(),al),
1.543 + key(tuples::get<1>(args_list.get_head())),
1.544 + hash(tuples::get<2>(args_list.get_head())),
1.545 + eq(tuples::get<3>(args_list.get_head())),
1.546 + buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
1.547 + mlf(1.0),
1.548 + first_bucket(buckets.size())
1.549 + {
1.550 + calculate_max_load();
1.551 + }
1.552 +
1.553 + hashed_index(
1.554 + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
1.555 + super(x),
1.556 +
1.557 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.558 + safe_super(),
1.559 +#endif
1.560 +
1.561 + key(x.key),
1.562 + hash(x.hash),
1.563 + eq(x.eq),
1.564 + buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
1.565 + mlf(x.mlf),
1.566 + max_load(x.max_load),
1.567 + first_bucket(x.first_bucket)
1.568 + {
1.569 + /* Copy ctor just takes the internal configuration objects from x. The rest
1.570 + * is done in subsequent call to copy_().
1.571 + */
1.572 + }
1.573 +
1.574 + ~hashed_index()
1.575 + {
1.576 + /* the container is guaranteed to be empty by now */
1.577 + }
1.578 +
1.579 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.580 + iterator make_iterator(node_type* node)
1.581 + {
1.582 + return iterator(node,&buckets,this);
1.583 + }
1.584 +
1.585 + const_iterator make_iterator(node_type* node)const
1.586 + {
1.587 + return const_iterator(
1.588 + node,
1.589 + &const_cast<bucket_array_type&>(buckets),
1.590 + const_cast<hashed_index*>(this));
1.591 + }
1.592 +#else
1.593 + iterator make_iterator(node_type* node)
1.594 + {
1.595 + return iterator(node,&buckets);
1.596 + }
1.597 +
1.598 + const_iterator make_iterator(node_type* node)const
1.599 + {
1.600 + return const_iterator(node,&const_cast<bucket_array_type&>(buckets));
1.601 + }
1.602 +#endif
1.603 +
1.604 + void copy_(
1.605 + const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1.606 + const copy_map_type& map)
1.607 + {
1.608 + for(hashed_index_node_impl* begin_org=x.buckets.begin(),
1.609 + * begin_cpy=buckets.begin(),
1.610 + * end_org=x.buckets.end();
1.611 + begin_org!=end_org;++begin_org,++begin_cpy){
1.612 +
1.613 + hashed_index_node_impl* next_org=begin_org->next();
1.614 + hashed_index_node_impl* cpy=begin_cpy;
1.615 + while(next_org!=begin_org){
1.616 + cpy->next()=
1.617 + static_cast<node_type*>(
1.618 + map.find(
1.619 + static_cast<final_node_type*>(
1.620 + node_type::from_impl(next_org))))->impl();
1.621 + next_org=next_org->next();
1.622 + cpy=cpy->next();
1.623 + }
1.624 + cpy->next()=begin_cpy;
1.625 + }
1.626 +
1.627 + super::copy_(x,map);
1.628 + }
1.629 +
1.630 + node_type* insert_(value_param_type v,node_type* x)
1.631 + {
1.632 + reserve(size()+1);
1.633 +
1.634 + std::size_t buc=find_bucket(v);
1.635 + hashed_index_node_impl* pos=buckets.at(buc);
1.636 + if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
1.637 +
1.638 + node_type* res=static_cast<node_type*>(super::insert_(v,x));
1.639 + if(res==x){
1.640 + link(x,pos);
1.641 + if(first_bucket>buc)first_bucket=buc;
1.642 + }
1.643 + return res;
1.644 + }
1.645 +
1.646 + node_type* insert_(value_param_type v,node_type* position,node_type* x)
1.647 + {
1.648 + reserve(size()+1);
1.649 +
1.650 + std::size_t buc=find_bucket(v);
1.651 + hashed_index_node_impl* pos=buckets.at(buc);
1.652 + if(!link_point(v,pos,Category()))return node_type::from_impl(pos);
1.653 +
1.654 + node_type* res=static_cast<node_type*>(super::insert_(v,position,x));
1.655 + if(res==x){
1.656 + link(x,pos);
1.657 + if(first_bucket>buc)first_bucket=buc;
1.658 + }
1.659 + return res;
1.660 + }
1.661 +
1.662 + void erase_(node_type* x)
1.663 + {
1.664 + unlink(x);
1.665 + first_bucket=buckets.first_nonempty(first_bucket);
1.666 + super::erase_(x);
1.667 +
1.668 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.669 + detach_iterators(x);
1.670 +#endif
1.671 + }
1.672 +
1.673 + void delete_all_nodes_()
1.674 + {
1.675 + for(hashed_index_node_impl* x=buckets.begin(),*x_end=buckets.end();
1.676 + x!=x_end;++x){
1.677 + hashed_index_node_impl* y=x->next();
1.678 + while(y!=x){
1.679 + hashed_index_node_impl* z=y->next();
1.680 + this->final_delete_node_(
1.681 + static_cast<final_node_type*>(node_type::from_impl(y)));
1.682 + y=z;
1.683 + }
1.684 + }
1.685 + }
1.686 +
1.687 + void clear_()
1.688 + {
1.689 + super::clear_();
1.690 + buckets.clear();
1.691 + first_bucket=buckets.size();
1.692 +
1.693 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.694 + safe_super::detach_dereferenceable_iterators();
1.695 +#endif
1.696 + }
1.697 +
1.698 + void swap_(
1.699 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
1.700 + {
1.701 + std::swap(key,x.key);
1.702 + std::swap(hash,x.hash);
1.703 + std::swap(eq,x.eq);
1.704 + buckets.swap(x.buckets);
1.705 + std::swap(mlf,x.mlf);
1.706 + std::swap(max_load,x.max_load);
1.707 + std::swap(first_bucket,x.first_bucket);
1.708 +
1.709 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.710 + safe_super::swap(x);
1.711 +#endif
1.712 +
1.713 + super::swap_(x);
1.714 + }
1.715 +
1.716 + bool replace_(value_param_type v,node_type* x)
1.717 + {
1.718 + if(eq(key(v),key(x->value()))){
1.719 + return super::replace_(v,x);
1.720 + }
1.721 +
1.722 + hashed_index_node_impl* y=prev(x);
1.723 + unlink_next(y);
1.724 +
1.725 + BOOST_TRY{
1.726 + std::size_t buc=find_bucket(v);
1.727 + hashed_index_node_impl* pos=buckets.at(buc);
1.728 + if(link_point(v,pos,Category())&&super::replace_(v,x)){
1.729 + link(x,pos);
1.730 + if(first_bucket>buc){
1.731 + first_bucket=buc;
1.732 + }
1.733 + else if(first_bucket<buc){
1.734 + first_bucket=buckets.first_nonempty(first_bucket);
1.735 + }
1.736 + return true;
1.737 + }
1.738 + link(x,y);
1.739 + return false;
1.740 + }
1.741 + BOOST_CATCH(...){
1.742 + link(x,y);
1.743 + BOOST_RETHROW;
1.744 + }
1.745 + BOOST_CATCH_END
1.746 + }
1.747 +
1.748 + bool modify_(node_type* x)
1.749 + {
1.750 + unlink(x);
1.751 +
1.752 + std::size_t buc;
1.753 + hashed_index_node_impl* pos;
1.754 + BOOST_TRY
1.755 + {
1.756 + buc=find_bucket(x->value());
1.757 + pos=buckets.at(buc);
1.758 + if(!link_point(x->value(),pos,Category())){
1.759 + first_bucket=buckets.first_nonempty(first_bucket);
1.760 + super::erase_(x);
1.761 +
1.762 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.763 + detach_iterators(x);
1.764 +#endif
1.765 + return false;
1.766 + }
1.767 +
1.768 + }
1.769 + BOOST_CATCH(...){
1.770 + first_bucket=buckets.first_nonempty(first_bucket);
1.771 + super::erase_(x);
1.772 +
1.773 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.774 + detach_iterators(x);
1.775 +#endif
1.776 +
1.777 + BOOST_RETHROW;
1.778 + }
1.779 + BOOST_CATCH_END
1.780 +
1.781 + BOOST_TRY{
1.782 + if(super::modify_(x)){
1.783 + link(x,pos);
1.784 + if(first_bucket>buc){
1.785 + first_bucket=buc;
1.786 + }
1.787 + else if(first_bucket<buc){
1.788 + first_bucket=buckets.first_nonempty(first_bucket);
1.789 + }
1.790 + return true;
1.791 + }
1.792 +
1.793 + first_bucket=buckets.first_nonempty(first_bucket);
1.794 +
1.795 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.796 + detach_iterators(x);
1.797 +#endif
1.798 + return false;
1.799 + }
1.800 + BOOST_CATCH(...){
1.801 + first_bucket=buckets.first_nonempty(first_bucket);
1.802 +
1.803 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.804 + detach_iterators(x);
1.805 +#endif
1.806 +
1.807 + BOOST_RETHROW;
1.808 + }
1.809 + BOOST_CATCH_END
1.810 + }
1.811 +
1.812 +#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1.813 + /* serialization */
1.814 +
1.815 + template<typename Archive>
1.816 + void save_(
1.817 + Archive& ar,const unsigned int version,const index_saver_type& sm)const
1.818 + {
1.819 + ar<<serialization::make_nvp("position",buckets);
1.820 + super::save_(ar,version,sm);
1.821 + }
1.822 +
1.823 + template<typename Archive>
1.824 + void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1.825 + {
1.826 + ar>>serialization::make_nvp("position",buckets);
1.827 + super::load_(ar,version,lm);
1.828 + }
1.829 +#endif
1.830 +
1.831 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1.832 + /* invariant stuff */
1.833 +
1.834 + bool invariant_()const
1.835 + {
1.836 + if(size()==0||begin()==end()){
1.837 + if(size()!=0||begin()!=end())return false;
1.838 + }
1.839 + else{
1.840 + size_type s0=0;
1.841 + for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1.842 + if(s0!=size())return false;
1.843 +
1.844 + size_type s1=0;
1.845 + for(size_type buc=0;buc<bucket_count();++buc){
1.846 + size_type ss1=0;
1.847 + for(const_local_iterator it=begin(buc),it_end=end(buc);
1.848 + it!=it_end;++it,++ss1){
1.849 + if(find_bucket(*it)!=buc)return false;
1.850 + }
1.851 + if(ss1!=bucket_size(buc))return false;
1.852 + s1+=ss1;
1.853 + }
1.854 + if(s1!=size())return false;
1.855 + }
1.856 +
1.857 + if(first_bucket!=buckets.first_nonempty(0))return false;
1.858 +
1.859 + return super::invariant_();
1.860 + }
1.861 +
1.862 + /* This forwarding function eases things for the boost::mem_fn construct
1.863 + * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1.864 + * final_check_invariant is already an inherited member function of index.
1.865 + */
1.866 + void check_invariant_()const{this->final_check_invariant_();}
1.867 +#endif
1.868 +
1.869 +private:
1.870 + node_type* header()const{return this->final_header();}
1.871 +
1.872 + std::size_t find_bucket(value_param_type v)const
1.873 + {
1.874 + return bucket(key(v));
1.875 + }
1.876 +
1.877 + bool link_point(
1.878 + value_param_type v,hashed_index_node_impl*& pos,hashed_unique_tag)
1.879 + {
1.880 + hashed_index_node_impl* x=pos->next();
1.881 + while(x!=pos){
1.882 + if(eq(key(v),key(node_type::from_impl(x)->value()))){
1.883 + pos=x;
1.884 + return false;
1.885 + }
1.886 + x=x->next();
1.887 + }
1.888 + return true;
1.889 + }
1.890 +
1.891 + bool link_point(
1.892 + value_param_type v,hashed_index_node_impl*& pos,hashed_non_unique_tag)
1.893 + {
1.894 + hashed_index_node_impl* prev=pos;
1.895 + hashed_index_node_impl* x=pos->next();
1.896 + while(x!=pos){
1.897 + if(eq(key(v),key(node_type::from_impl(x)->value()))){
1.898 + pos=prev;
1.899 + return true;
1.900 + }
1.901 + prev=x;
1.902 + x=x->next();
1.903 + }
1.904 + return true;
1.905 + }
1.906 +
1.907 + void link(node_type* x,hashed_index_node_impl* pos)
1.908 + {
1.909 + hashed_index_node_impl::link(x->impl(),pos);
1.910 + };
1.911 +
1.912 + void link(hashed_index_node_impl* x,hashed_index_node_impl* pos)
1.913 + {
1.914 + hashed_index_node_impl::link(x,pos);
1.915 + };
1.916 +
1.917 + void unlink(node_type* x)
1.918 + {
1.919 + hashed_index_node_impl::unlink(x->impl());
1.920 + };
1.921 +
1.922 + static hashed_index_node_impl* prev(node_type* x)
1.923 + {
1.924 + return hashed_index_node_impl::prev(x->impl());
1.925 + }
1.926 +
1.927 + static void unlink_next(hashed_index_node_impl* x)
1.928 + {
1.929 + hashed_index_node_impl::unlink_next(x);
1.930 + }
1.931 +
1.932 + void calculate_max_load()
1.933 + {
1.934 + float fml=static_cast<float>(mlf*bucket_count());
1.935 + max_load=(std::numeric_limits<size_type>::max)();
1.936 + if(max_load>fml)max_load=static_cast<size_type>(fml);
1.937 + }
1.938 +
1.939 + void reserve(size_type n)
1.940 + {
1.941 + if(n>max_load){
1.942 + size_type bc =(std::numeric_limits<size_type>::max)();
1.943 + float fbc=static_cast<float>(1+n/mlf);
1.944 + if(bc>fbc)bc =static_cast<size_type>(fbc);
1.945 + unchecked_rehash(bc);
1.946 + }
1.947 + }
1.948 +
1.949 + void unchecked_rehash(size_type n)
1.950 + {
1.951 + bucket_array_type buckets1(get_allocator(),header()->impl(),n);
1.952 + auto_space<std::size_t,allocator_type> hashes(get_allocator(),size());
1.953 +
1.954 + std::size_t i=0;
1.955 + hashed_index_node_impl* x=buckets.begin();
1.956 + hashed_index_node_impl* x_end=buckets.end();
1.957 + for(;x!=x_end;++x){
1.958 + hashed_index_node_impl* y=x->next();
1.959 + while(y!=x){
1.960 + hashes.data()[i++]=hash(key(node_type::from_impl(y)->value()));
1.961 + y=y->next();
1.962 + }
1.963 + }
1.964 +
1.965 + i=0;
1.966 + x=buckets.begin();
1.967 + for(;x!=x_end;++x){
1.968 + hashed_index_node_impl* y=x->next();
1.969 + while(y!=x){
1.970 + hashed_index_node_impl* z=y->next();
1.971 + std::size_t buc1=buckets1.position(hashes.data()[i++]);
1.972 + hashed_index_node_impl* x1=buckets1.at(buc1);
1.973 + link(y,x1);
1.974 + y=z;
1.975 + }
1.976 + }
1.977 +
1.978 + buckets.swap(buckets1);
1.979 + calculate_max_load();
1.980 + first_bucket=buckets.first_nonempty(0);
1.981 + }
1.982 +
1.983 +#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1.984 + void detach_iterators(node_type* x)
1.985 + {
1.986 + iterator it=make_iterator(x);
1.987 + safe_mode::detach_equivalent_iterators(it);
1.988 + }
1.989 +#endif
1.990 +
1.991 + key_from_value key;
1.992 + hasher hash;
1.993 + key_equal eq;
1.994 + bucket_array_type buckets;
1.995 + float mlf;
1.996 + size_type max_load;
1.997 + std::size_t first_bucket;
1.998 +
1.999 +#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1.1000 + BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1.1001 +#pragma parse_mfunc_templ reset
1.1002 +#endif
1.1003 +};
1.1004 +
1.1005 +/* specialized algorithms */
1.1006 +
1.1007 +template<
1.1008 + typename KeyFromValue,typename Hash,typename Pred,
1.1009 + typename SuperMeta,typename TagList,typename Category
1.1010 +>
1.1011 +void swap(
1.1012 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1.1013 + hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1.1014 +{
1.1015 + x.swap(y);
1.1016 +}
1.1017 +
1.1018 +} /* namespace multi_index::detail */
1.1019 +
1.1020 +/* sequenced index specifiers */
1.1021 +
1.1022 +template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1.1023 +struct hashed_unique
1.1024 +{
1.1025 + typedef typename detail::hashed_index_args<
1.1026 + Arg1,Arg2,Arg3,Arg4> index_args;
1.1027 + typedef typename index_args::tag_list_type::type tag_list_type;
1.1028 + typedef typename index_args::key_from_value_type key_from_value_type;
1.1029 + typedef typename index_args::hash_type hash_type;
1.1030 + typedef typename index_args::pred_type pred_type;
1.1031 +
1.1032 + template<typename Super>
1.1033 + struct node_class
1.1034 + {
1.1035 + typedef detail::hashed_index_node<Super> type;
1.1036 + };
1.1037 +
1.1038 + template<typename SuperMeta>
1.1039 + struct index_class
1.1040 + {
1.1041 + typedef detail::hashed_index<
1.1042 + key_from_value_type,hash_type,pred_type,
1.1043 + SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1.1044 + };
1.1045 +};
1.1046 +
1.1047 +template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1.1048 +struct hashed_non_unique
1.1049 +{
1.1050 + typedef typename detail::hashed_index_args<
1.1051 + Arg1,Arg2,Arg3,Arg4> index_args;
1.1052 + typedef typename index_args::tag_list_type::type tag_list_type;
1.1053 + typedef typename index_args::key_from_value_type key_from_value_type;
1.1054 + typedef typename index_args::hash_type hash_type;
1.1055 + typedef typename index_args::pred_type pred_type;
1.1056 +
1.1057 + template<typename Super>
1.1058 + struct node_class
1.1059 + {
1.1060 + typedef detail::hashed_index_node<Super> type;
1.1061 + };
1.1062 +
1.1063 + template<typename SuperMeta>
1.1064 + struct index_class
1.1065 + {
1.1066 + typedef detail::hashed_index<
1.1067 + key_from_value_type,hash_type,pred_type,
1.1068 + SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1.1069 + };
1.1070 +};
1.1071 +
1.1072 +} /* namespace multi_index */
1.1073 +
1.1074 +} /* namespace boost */
1.1075 +
1.1076 +#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1.1077 +
1.1078 +#endif