1/* Copyright 2003-2023 Joaquin M Lopez Munoz.
2 * Distributed under the Boost Software License, Version 1.0.
3 * (See accompanying file LICENSE_1_0.txt or copy at
4 * http://www.boost.org/LICENSE_1_0.txt)
5 *
6 * See http://www.boost.org/libs/multi_index for library home page.
7 */
8
9#ifndef BOOST_MULTI_INDEX_HASHED_INDEX_HPP
10#define BOOST_MULTI_INDEX_HASHED_INDEX_HPP
11
12#if defined(_MSC_VER)
13#pragma once
14#endif
15
16#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
17#include <algorithm>
18#include <boost/call_traits.hpp>
19#include <boost/core/addressof.hpp>
20#include <boost/core/no_exceptions_support.hpp>
21#include <boost/detail/workaround.hpp>
22#include <boost/limits.hpp>
23#include <boost/move/core.hpp>
24#include <boost/move/utility_core.hpp>
25#include <boost/mpl/bool.hpp>
26#include <boost/mpl/if.hpp>
27#include <boost/mpl/push_front.hpp>
28#include <boost/multi_index/detail/access_specifier.hpp>
29#include <boost/multi_index/detail/adl_swap.hpp>
30#include <boost/multi_index/detail/allocator_traits.hpp>
31#include <boost/multi_index/detail/auto_space.hpp>
32#include <boost/multi_index/detail/bucket_array.hpp>
33#include <boost/multi_index/detail/do_not_copy_elements_tag.hpp>
34#include <boost/multi_index/detail/hash_index_iterator.hpp>
35#include <boost/multi_index/detail/index_node_base.hpp>
36#include <boost/multi_index/detail/invalidate_iterators.hpp>
37#include <boost/multi_index/detail/modify_key_adaptor.hpp>
38#include <boost/multi_index/detail/node_handle.hpp>
39#include <boost/multi_index/detail/promotes_arg.hpp>
40#include <boost/multi_index/detail/safe_mode.hpp>
41#include <boost/multi_index/detail/scope_guard.hpp>
42#include <boost/multi_index/detail/vartempl_support.hpp>
43#include <boost/multi_index/hashed_index_fwd.hpp>
44#include <boost/tuple/tuple.hpp>
45#include <boost/type_traits/is_same.hpp>
46#include <cmath>
47#include <cstddef>
48#include <functional>
49#include <iterator>
50#include <utility>
51
52#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
53#include <initializer_list>
54#endif
55
56#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
57#include <boost/core/serialization.hpp>
58#endif
59
60#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
61#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x) \
62 detail::scope_guard BOOST_JOIN(check_invariant_,__LINE__)= \
63 detail::make_obj_guard(x,&hashed_index::check_invariant_); \
64 BOOST_JOIN(check_invariant_,__LINE__).touch();
65#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT \
66 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(*this)
67#else
68#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x)
69#define BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
70#endif
71
72namespace boost{
73
74namespace multi_index{
75
76namespace detail{
77
78/* hashed_index adds a layer of hashed indexing to a given Super */
79
80/* Most of the implementation of unique and non-unique indices is
81 * shared. We tell from one another on instantiation time by using
82 * Category tags defined in hash_index_node.hpp.
83 */
84
85#if defined(BOOST_MSVC)
86#pragma warning(push)
87#pragma warning(disable:4355) /* this used in base member initializer list */
88#endif
89
90template<
91 typename KeyFromValue,typename Hash,typename Pred,
92 typename SuperMeta,typename TagList,typename Category
93>
94class hashed_index:
95 BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS SuperMeta::type
96{
97#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
98 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
99/* The "ISO C++ Template Parser" option in CW8.3 has a problem with the
100 * lifetime of const references bound to temporaries --precisely what
101 * scopeguards are.
102 */
103
104#pragma parse_mfunc_templ off
105#endif
106
107#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
108 /* cross-index access */
109
110 template <typename,typename,typename> friend class index_base;
111#endif
112
113 typedef typename SuperMeta::type super;
114
115protected:
116 typedef hashed_index_node<
117 typename super::index_node_type> index_node_type;
118
119private:
120 typedef typename index_node_type::
121 template node_alg<Category>::type node_alg;
122 typedef typename index_node_type::impl_type node_impl_type;
123 typedef typename node_impl_type::pointer node_impl_pointer;
124 typedef typename node_impl_type::base_pointer node_impl_base_pointer;
125 typedef bucket_array<
126 typename super::final_allocator_type> bucket_array_type;
127
128public:
129 /* types */
130
131 typedef typename KeyFromValue::result_type key_type;
132 typedef typename index_node_type::value_type value_type;
133 typedef KeyFromValue key_from_value;
134 typedef Hash hasher;
135 typedef Pred key_equal;
136 typedef typename super::final_allocator_type allocator_type;
137
138private:
139 typedef allocator_traits<allocator_type> alloc_traits;
140
141public:
142 typedef typename alloc_traits::pointer pointer;
143 typedef typename alloc_traits::const_pointer const_pointer;
144 typedef value_type& reference;
145 typedef const value_type& const_reference;
146 typedef typename alloc_traits::size_type size_type;
147 typedef typename alloc_traits::difference_type difference_type;
148 typedef tuple<size_type,
149 key_from_value,hasher,key_equal> ctor_args;
150
151#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
152 typedef safe_mode::safe_iterator<
153 hashed_index_iterator<
154 index_node_type,bucket_array_type,
155 Category,
156 hashed_index_global_iterator_tag> > iterator;
157#else
158 typedef hashed_index_iterator<
159 index_node_type,bucket_array_type,
160 Category,hashed_index_global_iterator_tag> iterator;
161#endif
162
163 typedef iterator const_iterator;
164
165 typedef hashed_index_iterator<
166 index_node_type,bucket_array_type,
167 Category,hashed_index_local_iterator_tag> local_iterator;
168 typedef local_iterator const_local_iterator;
169
170 typedef typename super::final_node_handle_type node_type;
171 typedef detail::insert_return_type<
172 iterator,node_type> insert_return_type;
173 typedef TagList tag_list;
174
175protected:
176 typedef typename super::final_node_type final_node_type;
177 typedef tuples::cons<
178 ctor_args,
179 typename super::ctor_args_list> ctor_args_list;
180 typedef typename mpl::push_front<
181 typename super::index_type_list,
182 hashed_index>::type index_type_list;
183 typedef typename mpl::push_front<
184 typename super::iterator_type_list,
185 iterator>::type iterator_type_list;
186 typedef typename mpl::push_front<
187 typename super::const_iterator_type_list,
188 const_iterator>::type const_iterator_type_list;
189 typedef typename super::copy_map_type copy_map_type;
190
191#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
192 typedef typename super::index_saver_type index_saver_type;
193 typedef typename super::index_loader_type index_loader_type;
194#endif
195
196private:
197#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
198 typedef safe_mode::safe_container<iterator> safe_container;
199#endif
200
201 typedef typename call_traits<value_type>::param_type value_param_type;
202 typedef typename call_traits<
203 key_type>::param_type key_param_type;
204
205 /* needed to avoid commas in some macros */
206
207 typedef std::pair<iterator,bool> pair_return_type;
208
209public:
210
211 /* construct/destroy/copy
212 * Default and copy ctors are in the protected section as indices are
213 * not supposed to be created on their own. No range ctor either.
214 */
215
216 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
217 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
218 {
219 this->final()=x.final();
220 return *this;
221 }
222
223#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
224 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& operator=(
225 std::initializer_list<value_type> list)
226 {
227 this->final()=list;
228 return *this;
229 }
230#endif
231
232 allocator_type get_allocator()const BOOST_NOEXCEPT
233 {
234 return this->final().get_allocator();
235 }
236
237 /* size and capacity */
238
239 bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
240 size_type size()const BOOST_NOEXCEPT{return this->final_size_();}
241 size_type max_size()const BOOST_NOEXCEPT{return this->final_max_size_();}
242
243 /* iterators */
244
245 iterator begin()BOOST_NOEXCEPT
246 {
247 return make_iterator(
248 index_node_type::from_impl(header()->next()->prior()));
249
250 }
251 const_iterator begin()const BOOST_NOEXCEPT
252 {
253 return make_iterator(
254 index_node_type::from_impl(header()->next()->prior()));
255 }
256
257 iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
258 const_iterator end()const BOOST_NOEXCEPT{return make_iterator(header());}
259 const_iterator cbegin()const BOOST_NOEXCEPT{return begin();}
260 const_iterator cend()const BOOST_NOEXCEPT{return end();}
261
262 iterator iterator_to(const value_type& x)
263 {
264 return make_iterator(
265 node_from_value<index_node_type>(boost::addressof(x)));
266 }
267
268 const_iterator iterator_to(const value_type& x)const
269 {
270 return make_iterator(
271 node_from_value<index_node_type>(boost::addressof(x)));
272 }
273
274 /* modifiers */
275
276 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL(
277 pair_return_type,emplace,emplace_impl)
278
279 BOOST_MULTI_INDEX_OVERLOADS_TO_VARTEMPL_EXTRA_ARG(
280 iterator,emplace_hint,emplace_hint_impl,iterator,position)
281
282 std::pair<iterator,bool> insert(const value_type& x)
283 {
284 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
285 std::pair<final_node_type*,bool> p=this->final_insert_(x);
286 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
287 }
288
289 std::pair<iterator,bool> insert(BOOST_RV_REF(value_type) x)
290 {
291 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
292 std::pair<final_node_type*,bool> p=this->final_insert_rv_(x);
293 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
294 }
295
296 iterator insert(iterator position,const value_type& x)
297 {
298 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
299 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
300 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
301 std::pair<final_node_type*,bool> p=this->final_insert_(
302 x,static_cast<final_node_type*>(position.get_node()));
303 return make_iterator(p.first);
304 }
305
306 iterator insert(iterator position,BOOST_RV_REF(value_type) x)
307 {
308 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
309 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
310 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
311 std::pair<final_node_type*,bool> p=this->final_insert_rv_(
312 x,static_cast<final_node_type*>(position.get_node()));
313 return make_iterator(p.first);
314 }
315
316 template<typename InputIterator>
317 void insert(InputIterator first,InputIterator last)
318 {
319 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
320 for(;first!=last;++first)this->final_insert_ref_(*first);
321 }
322
323#if !defined(BOOST_NO_CXX11_HDR_INITIALIZER_LIST)
324 void insert(std::initializer_list<value_type> list)
325 {
326 insert(list.begin(),list.end());
327 }
328#endif
329
330 insert_return_type insert(BOOST_RV_REF(node_type) nh)
331 {
332 if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
333 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
334 std::pair<final_node_type*,bool> p=this->final_insert_nh_(nh);
335 return insert_return_type(make_iterator(p.first),p.second,boost::move(nh));
336 }
337
338 iterator insert(const_iterator position,BOOST_RV_REF(node_type) nh)
339 {
340 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
341 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
342 if(nh)BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,nh);
343 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
344 std::pair<final_node_type*,bool> p=this->final_insert_nh_(
345 nh,static_cast<final_node_type*>(position.get_node()));
346 return make_iterator(p.first);
347 }
348
349 node_type extract(const_iterator position)
350 {
351 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
352 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
353 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
354 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
355 return this->final_extract_(
356 static_cast<final_node_type*>(position.get_node()));
357 }
358
359 node_type extract(key_param_type x)
360 {
361 iterator position=find(x);
362 if(position==end())return node_type();
363 else return extract(position);
364 }
365
366 iterator erase(iterator position)
367 {
368 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
369 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
370 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
371 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
372 this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
373 return position;
374 }
375
376 size_type erase(key_param_type k)
377 {
378 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
379
380 std::size_t buc=buckets.position(hash_(k));
381 for(node_impl_pointer x=buckets.at(buc)->prior();
382 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
383 if(eq_(k,key(index_node_type::from_impl(x)->value()))){
384 node_impl_pointer y=end_of_range(x);
385 size_type s=0;
386 do{
387 node_impl_pointer z=node_alg::after(x);
388 this->final_erase_(
389 static_cast<final_node_type*>(index_node_type::from_impl(x)));
390 x=z;
391 ++s;
392 }while(x!=y);
393 return s;
394 }
395 }
396 return 0;
397 }
398
399 iterator erase(iterator first,iterator last)
400 {
401 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
402 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
403 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,*this);
404 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,*this);
405 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
406 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
407 while(first!=last){
408 first=erase(first);
409 }
410 return first;
411 }
412
413 bool replace(iterator position,const value_type& x)
414 {
415 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
416 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
417 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
418 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
419 return this->final_replace_(
420 x,static_cast<final_node_type*>(position.get_node()));
421 }
422
423 bool replace(iterator position,BOOST_RV_REF(value_type) x)
424 {
425 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
426 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
427 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
428 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
429 return this->final_replace_rv_(
430 x,static_cast<final_node_type*>(position.get_node()));
431 }
432
433 template<typename Modifier>
434 bool modify(iterator position,Modifier mod)
435 {
436 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
437 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
438 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
439 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
440
441#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
442 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
443 * this is not added. Left it for all compilers as it does no
444 * harm.
445 */
446
447 position.detach();
448#endif
449
450 return this->final_modify_(
451 mod,static_cast<final_node_type*>(position.get_node()));
452 }
453
454 template<typename Modifier,typename Rollback>
455 bool modify(iterator position,Modifier mod,Rollback back_)
456 {
457 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
458 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
459 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
460 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
461
462#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
463 /* MSVC++ 6.0 optimizer on safe mode code chokes if this
464 * this is not added. Left it for all compilers as it does no
465 * harm.
466 */
467
468 position.detach();
469#endif
470
471 return this->final_modify_(
472 mod,back_,static_cast<final_node_type*>(position.get_node()));
473 }
474
475 template<typename Modifier>
476 bool modify_key(iterator position,Modifier mod)
477 {
478 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
479 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
480 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
481 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
482 return modify(
483 position,modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key));
484 }
485
486 template<typename Modifier,typename Rollback>
487 bool modify_key(iterator position,Modifier mod,Rollback back_)
488 {
489 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
490 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(position);
491 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
492 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
493 return modify(
494 position,
495 modify_key_adaptor<Modifier,value_type,KeyFromValue>(mod,key),
496 modify_key_adaptor<Rollback,value_type,KeyFromValue>(back_,key));
497 }
498
499 void clear()BOOST_NOEXCEPT
500 {
501 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
502 this->final_clear_();
503 }
504
505 void swap(hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
506 {
507 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
508 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF(x);
509 this->final_swap_(x.final());
510 }
511
512 template<typename Index>
513 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
514 merge(Index& x)
515 {
516 merge(x,x.begin(),x.end());
517 }
518
519 template<typename Index>
520 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
521 merge(BOOST_RV_REF(Index) x){merge(static_cast<Index&>(x));}
522
523 template<typename Index>
524 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type)
525 merge(Index& x,BOOST_DEDUCED_TYPENAME Index::iterator i)
526 {
527 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(i);
528 BOOST_MULTI_INDEX_CHECK_DEREFERENCEABLE_ITERATOR(i);
529 BOOST_MULTI_INDEX_CHECK_IS_OWNER(i,x);
530 BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
531 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
532 if(x.end().get_node()==this->header()){ /* same container */
533 return std::pair<iterator,bool>(
534 make_iterator(static_cast<final_node_type*>(i.get_node())),true);
535 }
536 else{
537 std::pair<final_node_type*,bool> p=this->final_transfer_(
538 x,static_cast<final_node_type*>(i.get_node()));
539 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
540 }
541 }
542
543 template<typename Index>
544 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,pair_return_type)
545 merge(BOOST_RV_REF(Index) x,BOOST_DEDUCED_TYPENAME Index::iterator i)
546 {
547 return merge(static_cast<Index&>(x),i);
548 }
549
550 template<typename Index>
551 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
552 merge(
553 Index& x,
554 BOOST_DEDUCED_TYPENAME Index::iterator first,
555 BOOST_DEDUCED_TYPENAME Index::iterator last)
556 {
557 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(first);
558 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(last);
559 BOOST_MULTI_INDEX_CHECK_IS_OWNER(first,x);
560 BOOST_MULTI_INDEX_CHECK_IS_OWNER(last,x);
561 BOOST_MULTI_INDEX_CHECK_VALID_RANGE(first,last);
562 BOOST_MULTI_INDEX_CHECK_EQUAL_ALLOCATORS(*this,x);
563 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
564 if(x.end().get_node()!=this->header()){ /* different containers */
565 this->final_transfer_range_(x,first,last);
566 }
567 }
568
569 template<typename Index>
570 BOOST_MULTI_INDEX_ENABLE_IF_MERGEABLE(hashed_index,Index,void)
571 merge(
572 BOOST_RV_REF(Index) x,
573 BOOST_DEDUCED_TYPENAME Index::iterator first,
574 BOOST_DEDUCED_TYPENAME Index::iterator last)
575 {
576 merge(static_cast<Index&>(x),first,last);
577 }
578
579 /* observers */
580
581 key_from_value key_extractor()const{return key;}
582 hasher hash_function()const{return hash_;}
583 key_equal key_eq()const{return eq_;}
584
585 /* lookup */
586
587 /* Internally, these ops rely on const_iterator being the same
588 * type as iterator.
589 */
590
591 /* Implementation note: When CompatibleKey is consistently promoted to
592 * KeyFromValue::result_type for equality comparison, the promotion is made
593 * once in advance to increase efficiency.
594 */
595
596 template<typename CompatibleKey>
597 iterator find(const CompatibleKey& k)const
598 {
599 return find(k,hash_,eq_);
600 }
601
602 template<
603 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
604 >
605 iterator find(
606 const CompatibleKey& k,
607 const CompatibleHash& hash,const CompatiblePred& eq)const
608 {
609 return find(
610 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
611 }
612
613 template<typename CompatibleKey>
614 size_type count(const CompatibleKey& k)const
615 {
616 return count(k,hash_,eq_);
617 }
618
619 template<
620 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
621 >
622 size_type count(
623 const CompatibleKey& k,
624 const CompatibleHash& hash,const CompatiblePred& eq)const
625 {
626 return count(
627 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
628 }
629
630 template<typename CompatibleKey>
631 bool contains(const CompatibleKey& k)const
632 {
633 return contains(k,hash_,eq_);
634 }
635
636 template<
637 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
638 >
639 bool contains(
640 const CompatibleKey& k,
641 const CompatibleHash& hash,const CompatiblePred& eq)const
642 {
643 return find(k,hash,eq)!=end();
644 }
645
646 template<typename CompatibleKey>
647 std::pair<iterator,iterator> equal_range(const CompatibleKey& k)const
648 {
649 return equal_range(k,hash_,eq_);
650 }
651
652 template<
653 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
654 >
655 std::pair<iterator,iterator> equal_range(
656 const CompatibleKey& k,
657 const CompatibleHash& hash,const CompatiblePred& eq)const
658 {
659 return equal_range(
660 k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
661 }
662
663 /* bucket interface */
664
665 size_type bucket_count()const BOOST_NOEXCEPT
666 {
667 return static_cast<size_type>(buckets.size());
668 }
669
670 size_type max_bucket_count()const BOOST_NOEXCEPT{return static_cast<size_type>(-1);}
671
672 size_type bucket_size(size_type n)const
673 {
674 size_type res=0;
675 for(node_impl_pointer x=buckets.at(n)->prior();
676 x!=node_impl_pointer(0);x=node_alg::after_local(x)){
677 ++res;
678 }
679 return res;
680 }
681
682 size_type bucket(key_param_type k)const
683 {
684 return static_cast<size_type>(buckets.position(hash_(k)));
685 }
686
687 local_iterator begin(size_type n)
688 {
689 return const_cast<const hashed_index*>(this)->begin(n);
690 }
691
692 const_local_iterator begin(size_type n)const
693 {
694 node_impl_pointer x=buckets.at(n)->prior();
695 if(x==node_impl_pointer(0))return end(n);
696 return make_local_iterator(index_node_type::from_impl(x));
697 }
698
699 local_iterator end(size_type n)
700 {
701 return const_cast<const hashed_index*>(this)->end(n);
702 }
703
704 const_local_iterator end(size_type)const
705 {
706 return make_local_iterator(0);
707 }
708
709 const_local_iterator cbegin(size_type n)const{return begin(n);}
710 const_local_iterator cend(size_type n)const{return end(n);}
711
712 local_iterator local_iterator_to(const value_type& x)
713 {
714 return make_local_iterator(
715 node_from_value<index_node_type>(boost::addressof(x)));
716 }
717
718 const_local_iterator local_iterator_to(const value_type& x)const
719 {
720 return make_local_iterator(
721 node_from_value<index_node_type>(boost::addressof(x)));
722 }
723
724 /* hash policy */
725
726 float load_factor()const BOOST_NOEXCEPT
727 {return static_cast<float>(size())/bucket_count();}
728 float max_load_factor()const BOOST_NOEXCEPT{return mlf;}
729 void max_load_factor(float z){mlf=z;calculate_max_load();}
730
731 void rehash(size_type n)
732 {
733 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
734 if(size()<=max_load&&n<=bucket_count())return;
735
736 size_type bc =(std::numeric_limits<size_type>::max)();
737 float fbc=1.0f+static_cast<float>(size())/mlf;
738 if(bc>fbc){
739 bc=static_cast<size_type>(fbc);
740 if(bc<n)bc=n;
741 }
742 unchecked_rehash(bc);
743 }
744
745 void reserve(size_type n)
746 {
747 rehash(n: static_cast<size_type>(std::ceil(x: static_cast<float>(n)/mlf)));
748 }
749
750BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
751 hashed_index(const ctor_args_list& args_list,const allocator_type& al):
752 super(args_list.get_tail(),al),
753 key(tuples::get<1>(args_list.get_head())),
754 hash_(tuples::get<2>(args_list.get_head())),
755 eq_(tuples::get<3>(args_list.get_head())),
756 buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
757 mlf(1.0f)
758
759#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
760 ,safe(*this)
761#endif
762
763 {
764 calculate_max_load();
765 }
766
767 hashed_index(
768 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x):
769 super(x),
770 key(x.key),
771 hash_(x.hash_),
772 eq_(x.eq_),
773 buckets(x.get_allocator(),header()->impl(),x.buckets.size()),
774 mlf(x.mlf),
775 max_load(x.max_load)
776
777#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
778 ,safe(*this)
779#endif
780
781 {
782 /* Copy ctor just takes the internal configuration objects from x. The rest
783 * is done in subsequent call to copy_().
784 */
785 }
786
787 hashed_index(
788 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
789 do_not_copy_elements_tag):
790 super(x,do_not_copy_elements_tag()),
791 key(x.key),
792 hash_(x.hash_),
793 eq_(x.eq_),
794 buckets(x.get_allocator(),header()->impl(),0),
795 mlf(1.0f)
796
797#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
798 ,safe(*this)
799#endif
800
801 {
802 calculate_max_load();
803 }
804
805 ~hashed_index()
806 {
807 /* the container is guaranteed to be empty by now */
808 }
809
810#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
811 iterator make_iterator(index_node_type* node)
812 {
813 return iterator(node,&safe);
814 }
815
816 const_iterator make_iterator(index_node_type* node)const
817 {
818 return const_iterator(node,const_cast<safe_container*>(&safe));
819 }
820#else
821 iterator make_iterator(index_node_type* node)
822 {
823 return iterator(node);
824 }
825
826 const_iterator make_iterator(index_node_type* node)const
827 {
828 return const_iterator(node);
829 }
830#endif
831
832 local_iterator make_local_iterator(index_node_type* node)
833 {
834 return local_iterator(node);
835 }
836
837 const_local_iterator make_local_iterator(index_node_type* node)const
838 {
839 return const_local_iterator(node);
840 }
841
842 void copy_(
843 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
844 const copy_map_type& map)
845 {
846 copy_(x,map,Category());
847 }
848
849 void copy_(
850 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
851 const copy_map_type& map,hashed_unique_tag)
852 {
853 if(x.size()!=0){
854 node_impl_pointer end_org=x.header()->impl(),
855 org=end_org,
856 cpy=header()->impl();
857 do{
858 node_impl_pointer prev_org=org->prior(),
859 prev_cpy=
860 static_cast<index_node_type*>(map.find(static_cast<final_node_type*>(
861 index_node_type::from_impl(prev_org))))->impl();
862 cpy->prior()=prev_cpy;
863 if(node_alg::is_first_of_bucket(org)){
864 node_impl_base_pointer buc_org=prev_org->next(),
865 buc_cpy=
866 buckets.begin()+(buc_org-x.buckets.begin());
867 prev_cpy->next()=buc_cpy;
868 buc_cpy->prior()=cpy;
869 }
870 else{
871 prev_cpy->next()=node_impl_type::base_pointer_from(cpy);
872 }
873 org=prev_org;
874 cpy=prev_cpy;
875 }while(org!=end_org);
876 }
877
878 super::copy_(x,map);
879 }
880
881 void copy_(
882 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
883 const copy_map_type& map,hashed_non_unique_tag)
884 {
885 if(x.size()!=0){
886 node_impl_pointer end_org=x.header()->impl(),
887 org=end_org,
888 cpy=header()->impl();
889 do{
890 node_impl_pointer next_org=node_alg::after(org),
891 next_cpy=
892 static_cast<index_node_type*>(map.find(static_cast<final_node_type*>(
893 index_node_type::from_impl(next_org))))->impl();
894 if(node_alg::is_first_of_bucket(next_org)){
895 node_impl_base_pointer buc_org=org->next(),
896 buc_cpy=
897 buckets.begin()+(buc_org-x.buckets.begin());
898 cpy->next()=buc_cpy;
899 buc_cpy->prior()=next_cpy;
900 next_cpy->prior()=cpy;
901 }
902 else{
903 if(org->next()==node_impl_type::base_pointer_from(next_org)){
904 cpy->next()=node_impl_type::base_pointer_from(next_cpy);
905 }
906 else{
907 cpy->next()=
908 node_impl_type::base_pointer_from(
909 static_cast<index_node_type*>(
910 map.find(static_cast<final_node_type*>(
911 index_node_type::from_impl(
912 node_impl_type::pointer_from(org->next())))))->impl());
913 }
914
915 if(next_org->prior()!=org){
916 next_cpy->prior()=
917 static_cast<index_node_type*>(
918 map.find(static_cast<final_node_type*>(
919 index_node_type::from_impl(next_org->prior()))))->impl();
920 }
921 else{
922 next_cpy->prior()=cpy;
923 }
924 }
925 org=next_org;
926 cpy=next_cpy;
927 }while(org!=end_org);
928 }
929
930 super::copy_(x,map);
931 }
932
933 template<typename Variant>
934 final_node_type* insert_(
935 value_param_type v,final_node_type*& x,Variant variant)
936 {
937 reserve_for_insert(n: size()+1);
938
939 std::size_t buc=find_bucket(v);
940 link_info pos(buckets.at(buc));
941 if(!link_point(v,pos)){
942 return static_cast<final_node_type*>(
943 index_node_type::from_impl(node_impl_type::pointer_from(pos)));
944 }
945
946 final_node_type* res=super::insert_(v,x,variant);
947 if(res==x)link(static_cast<index_node_type*>(x),pos);
948 return res;
949 }
950
951 template<typename Variant>
952 final_node_type* insert_(
953 value_param_type v,index_node_type* position,
954 final_node_type*& x,Variant variant)
955 {
956 reserve_for_insert(n: size()+1);
957
958 std::size_t buc=find_bucket(v);
959 link_info pos(buckets.at(buc));
960 if(!link_point(v,pos)){
961 return static_cast<final_node_type*>(
962 index_node_type::from_impl(node_impl_type::pointer_from(pos)));
963 }
964
965 final_node_type* res=super::insert_(v,position,x,variant);
966 if(res==x)link(static_cast<index_node_type*>(x),pos);
967 return res;
968 }
969
970 template<typename Dst>
971 void extract_(index_node_type* x,Dst dst)
972 {
973 unlink(x);
974 super::extract_(x,dst.next());
975
976#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
977 transfer_iterators(dst.get(),x);
978#endif
979 }
980
981 void delete_all_nodes_()
982 {
983 delete_all_nodes_(Category());
984 }
985
986 void delete_all_nodes_(hashed_unique_tag)
987 {
988 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
989 node_impl_pointer y=x->prior();
990 this->final_delete_node_(
991 static_cast<final_node_type*>(index_node_type::from_impl(x)));
992 x=y;
993 }
994 }
995
996 void delete_all_nodes_(hashed_non_unique_tag)
997 {
998 for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
999 node_impl_pointer y=x->prior();
1000 if(y->next()!=node_impl_type::base_pointer_from(x)&&
1001 y->next()->prior()!=x){ /* n-1 of group */
1002 /* Make the second node prior() pointer back-linked so that it won't
1003 * refer to a deleted node when the time for its own destruction comes.
1004 */
1005
1006 node_impl_pointer first=node_impl_type::pointer_from(y->next());
1007 first->next()->prior()=first;
1008 }
1009 this->final_delete_node_(
1010 static_cast<final_node_type*>(index_node_type::from_impl(x)));
1011 x=y;
1012 }
1013 }
1014
1015 void clear_()
1016 {
1017 super::clear_();
1018 buckets.clear(header()->impl());
1019
1020#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1021 safe.detach_dereferenceable_iterators();
1022#endif
1023 }
1024
1025 template<typename BoolConstant>
1026 void swap_(
1027 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1028 BoolConstant swap_allocators)
1029 {
1030 adl_swap(key,x.key);
1031 adl_swap(hash_,x.hash_);
1032 adl_swap(eq_,x.eq_);
1033 buckets.swap(x.buckets,swap_allocators);
1034 std::swap(mlf,x.mlf);
1035 std::swap(max_load,x.max_load);
1036
1037#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1038 safe.swap(x.safe);
1039#endif
1040
1041 super::swap_(x,swap_allocators);
1042 }
1043
1044 void swap_elements_(
1045 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x)
1046 {
1047 buckets.swap(x.buckets);
1048 std::swap(mlf,x.mlf);
1049 std::swap(max_load,x.max_load);
1050
1051#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1052 safe.swap(x.safe);
1053#endif
1054
1055 super::swap_elements_(x);
1056 }
1057
1058 template<typename Variant>
1059 bool replace_(value_param_type v,index_node_type* x,Variant variant)
1060 {
1061 if(eq_(key(v),key(x->value()))){
1062 return super::replace_(v,x,variant);
1063 }
1064
1065 unlink_undo undo;
1066 unlink(x,undo);
1067
1068 BOOST_TRY{
1069 std::size_t buc=find_bucket(v);
1070 link_info pos(buckets.at(buc));
1071 if(link_point(v,pos)&&super::replace_(v,x,variant)){
1072 link(x,pos);
1073 return true;
1074 }
1075 undo();
1076 return false;
1077 }
1078 BOOST_CATCH(...){
1079 undo();
1080 BOOST_RETHROW;
1081 }
1082 BOOST_CATCH_END
1083 }
1084
1085 bool modify_(index_node_type* x)
1086 {
1087 std::size_t buc;
1088 bool b;
1089 BOOST_TRY{
1090 buc=find_bucket(v: x->value());
1091 b=in_place(x->impl(),key(x->value()),buc);
1092 }
1093 BOOST_CATCH(...){
1094 extract_(x,invalidate_iterators());
1095 BOOST_RETHROW;
1096 }
1097 BOOST_CATCH_END
1098 if(!b){
1099 unlink(x);
1100 BOOST_TRY{
1101 link_info pos(buckets.at(buc));
1102 if(!link_point(x->value(),pos)){
1103 super::extract_(x,invalidate_iterators());
1104
1105#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1106 detach_iterators(x);
1107#endif
1108 return false;
1109 }
1110 link(x,pos);
1111 }
1112 BOOST_CATCH(...){
1113 super::extract_(x,invalidate_iterators());
1114
1115#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1116 detach_iterators(x);
1117#endif
1118
1119 BOOST_RETHROW;
1120 }
1121 BOOST_CATCH_END
1122 }
1123
1124 BOOST_TRY{
1125 if(!super::modify_(x)){
1126 unlink(x);
1127
1128#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1129 detach_iterators(x);
1130#endif
1131 return false;
1132 }
1133 else return true;
1134 }
1135 BOOST_CATCH(...){
1136 unlink(x);
1137
1138#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1139 detach_iterators(x);
1140#endif
1141
1142 BOOST_RETHROW;
1143 }
1144 BOOST_CATCH_END
1145 }
1146
1147 bool modify_rollback_(index_node_type* x)
1148 {
1149 std::size_t buc=find_bucket(v: x->value());
1150 if(in_place(x->impl(),key(x->value()),buc)){
1151 return super::modify_rollback_(x);
1152 }
1153
1154 unlink_undo undo;
1155 unlink(x,undo);
1156
1157 BOOST_TRY{
1158 link_info pos(buckets.at(buc));
1159 if(link_point(x->value(),pos)&&super::modify_rollback_(x)){
1160 link(x,pos);
1161 return true;
1162 }
1163 undo();
1164 return false;
1165 }
1166 BOOST_CATCH(...){
1167 undo();
1168 BOOST_RETHROW;
1169 }
1170 BOOST_CATCH_END
1171 }
1172
1173 bool check_rollback_(index_node_type* x)const
1174 {
1175 std::size_t buc=find_bucket(v: x->value());
1176 return in_place(x->impl(),key(x->value()),buc)&&super::check_rollback_(x);
1177 }
1178
1179 /* comparison */
1180
1181#if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
1182 /* defect macro refers to class, not function, templates, but anyway */
1183
1184 template<typename K,typename H,typename P,typename S,typename T,typename C>
1185 friend bool operator==(
1186 const hashed_index<K,H,P,S,T,C>&,const hashed_index<K,H,P,S,T,C>& y);
1187#endif
1188
1189 bool equals(const hashed_index& x)const{return equals(x,Category());}
1190
1191 bool equals(const hashed_index& x,hashed_unique_tag)const
1192 {
1193 if(size()!=x.size())return false;
1194 for(const_iterator it=begin(),it_end=end(),it2_end=x.end();
1195 it!=it_end;++it){
1196 const_iterator it2=x.find(key(*it));
1197 if(it2==it2_end||!(*it==*it2))return false;
1198 }
1199 return true;
1200 }
1201
1202 bool equals(const hashed_index& x,hashed_non_unique_tag)const
1203 {
1204 if(size()!=x.size())return false;
1205 for(const_iterator it=begin(),it_end=end();it!=it_end;){
1206 const_iterator it2,it2_last;
1207 boost::tie(it2,it2_last)=x.equal_range(key(*it));
1208 if(it2==it2_last)return false;
1209
1210 const_iterator it_last=make_iterator(
1211 index_node_type::from_impl(end_of_range(it.get_node()->impl())));
1212 if(std::distance(it,it_last)!=std::distance(it2,it2_last))return false;
1213
1214 /* From is_permutation code in
1215 * http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2010/n3068.pdf
1216 */
1217
1218 for(;it!=it_last;++it,++it2){
1219 if(!(*it==*it2))break;
1220 }
1221 if(it!=it_last){
1222 for(const_iterator scan=it;scan!=it_last;++scan){
1223 if(std::find(it,scan,*scan)!=scan)continue;
1224 difference_type matches=std::count(it2,it2_last,*scan);
1225 if(matches==0||matches!=std::count(scan,it_last,*scan))return false;
1226 }
1227 it=it_last;
1228 }
1229 }
1230 return true;
1231 }
1232
1233#if !defined(BOOST_MULTI_INDEX_DISABLE_SERIALIZATION)
1234 /* serialization */
1235
1236 template<typename Archive>
1237 void save_(
1238 Archive& ar,const unsigned int version,const index_saver_type& sm)const
1239 {
1240 ar<<core::make_nvp("position",buckets);
1241 super::save_(ar,version,sm);
1242 }
1243
1244 template<typename Archive>
1245 void load_(Archive& ar,const unsigned int version,const index_loader_type& lm)
1246 {
1247 ar>>core::make_nvp("position",buckets);
1248 super::load_(ar,version,lm);
1249 }
1250#endif
1251
1252#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)
1253 /* invariant stuff */
1254
1255 bool invariant_()const
1256 {
1257 if(size()==0||begin()==end()){
1258 if(size()!=0||begin()!=end())return false;
1259 }
1260 else{
1261 size_type s0=0;
1262 for(const_iterator it=begin(),it_end=end();it!=it_end;++it,++s0){}
1263 if(s0!=size())return false;
1264
1265 size_type s1=0;
1266 for(size_type buc=0;buc<bucket_count();++buc){
1267 size_type ss1=0;
1268 for(const_local_iterator it=begin(buc),it_end=end(buc);
1269 it!=it_end;++it,++ss1){
1270 if(find_bucket(*it)!=buc)return false;
1271 }
1272 if(ss1!=bucket_size(buc))return false;
1273 s1+=ss1;
1274 }
1275 if(s1!=size())return false;
1276 }
1277
1278 return super::invariant_();
1279 }
1280
1281 /* This forwarding function eases things for the boost::mem_fn construct
1282 * in BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT. Actually,
1283 * final_check_invariant is already an inherited member function of index.
1284 */
1285 void check_invariant_()const{this->final_check_invariant_();}
1286#endif
1287
1288private:
1289 index_node_type* header()const{return this->final_header();}
1290
1291 std::size_t find_bucket(value_param_type v)const
1292 {
1293 return bucket(k: key(v));
1294 }
1295
1296 struct link_info_non_unique
1297 {
1298 link_info_non_unique(node_impl_base_pointer pos):
1299 first(pos),last(node_impl_base_pointer(0)){}
1300
1301 operator const node_impl_base_pointer&()const{return this->first;}
1302
1303 node_impl_base_pointer first,last;
1304 };
1305
1306 typedef typename mpl::if_<
1307 is_same<Category,hashed_unique_tag>,
1308 node_impl_base_pointer,
1309 link_info_non_unique
1310 >::type link_info;
1311
1312 bool link_point(value_param_type v,link_info& pos)
1313 {
1314 return link_point(v,pos,Category());
1315 }
1316
1317 bool link_point(
1318 value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1319 {
1320 for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1321 x=node_alg::after_local(x)){
1322 if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){
1323 pos=node_impl_type::base_pointer_from(x);
1324 return false;
1325 }
1326 }
1327 return true;
1328 }
1329
1330 bool link_point(
1331 value_param_type v,link_info_non_unique& pos,hashed_non_unique_tag)
1332 {
1333 for(node_impl_pointer x=pos.first->prior();x!=node_impl_pointer(0);
1334 x=node_alg::next_to_inspect(x)){
1335 if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){
1336 pos.first=node_impl_type::base_pointer_from(x);
1337 pos.last=node_impl_type::base_pointer_from(last_of_range(x));
1338 return true;
1339 }
1340 }
1341 return true;
1342 }
1343
1344 node_impl_pointer last_of_range(node_impl_pointer x)const
1345 {
1346 return last_of_range(x,Category());
1347 }
1348
1349 node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1350 {
1351 return x;
1352 }
1353
1354 node_impl_pointer last_of_range(
1355 node_impl_pointer x,hashed_non_unique_tag)const
1356 {
1357 node_impl_base_pointer y=x->next();
1358 node_impl_pointer z=y->prior();
1359 if(z==x){ /* range of size 1 or 2 */
1360 node_impl_pointer yy=node_impl_type::pointer_from(y);
1361 return
1362 eq_(
1363 key(index_node_type::from_impl(x)->value()),
1364 key(index_node_type::from_impl(yy)->value()))?yy:x;
1365 }
1366 else if(z->prior()==x) /* last of bucket */
1367 return x;
1368 else /* group of size>2 */
1369 return z;
1370 }
1371
1372 node_impl_pointer end_of_range(node_impl_pointer x)const
1373 {
1374 return end_of_range(x,Category());
1375 }
1376
1377 node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1378 {
1379 return node_alg::after(last_of_range(x));
1380 }
1381
1382 node_impl_pointer end_of_range(
1383 node_impl_pointer x,hashed_non_unique_tag)const
1384 {
1385 node_impl_base_pointer y=x->next();
1386 node_impl_pointer z=y->prior();
1387 if(z==x){ /* range of size 1 or 2 */
1388 node_impl_pointer yy=node_impl_type::pointer_from(y);
1389 if(!eq_(
1390 key(index_node_type::from_impl(x)->value()),
1391 key(index_node_type::from_impl(yy)->value())))yy=x;
1392 return yy->next()->prior()==yy?
1393 node_impl_type::pointer_from(yy->next()):
1394 yy->next()->prior();
1395 }
1396 else if(z->prior()==x) /* last of bucket */
1397 return z;
1398 else /* group of size>2 */
1399 return z->next()->prior()==z?
1400 node_impl_type::pointer_from(z->next()):
1401 z->next()->prior();
1402 }
1403
1404 void link(index_node_type* x,const link_info& pos)
1405 {
1406 link(x,pos,Category());
1407 }
1408
1409 void link(index_node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1410 {
1411 node_alg::link(x->impl(),pos,header()->impl());
1412 }
1413
1414 void link(
1415 index_node_type* x,const link_info_non_unique& pos,hashed_non_unique_tag)
1416 {
1417 if(pos.last==node_impl_base_pointer(0)){
1418 node_alg::link(x->impl(),pos.first,header()->impl());
1419 }
1420 else{
1421 node_alg::link(
1422 x->impl(),
1423 node_impl_type::pointer_from(pos.first),
1424 node_impl_type::pointer_from(pos.last));
1425 }
1426 }
1427
1428 void unlink(index_node_type* x)
1429 {
1430 node_alg::unlink(x->impl());
1431 }
1432
1433 typedef typename node_alg::unlink_undo unlink_undo;
1434
1435 void unlink(index_node_type* x,unlink_undo& undo)
1436 {
1437 node_alg::unlink(x->impl(),undo);
1438 }
1439
1440 void calculate_max_load()
1441 {
1442 float fml=mlf*static_cast<float>(bucket_count());
1443 max_load=(std::numeric_limits<size_type>::max)();
1444 if(max_load>fml)max_load=static_cast<size_type>(fml);
1445 }
1446
1447 void reserve_for_insert(size_type n)
1448 {
1449 if(n>max_load){
1450 size_type bc =(std::numeric_limits<size_type>::max)();
1451 float fbc=1.0f+static_cast<float>(n)/mlf;
1452 if(bc>fbc)bc =static_cast<size_type>(fbc);
1453 unchecked_rehash(bc);
1454 }
1455 }
1456
1457 void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1458
1459 void unchecked_rehash(size_type n,hashed_unique_tag)
1460 {
1461 node_impl_type cpy_end_node;
1462 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1463 end_=header()->impl();
1464 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1465
1466 if(size()!=0){
1467 auto_space<
1468 std::size_t,allocator_type> hashes(get_allocator(),size());
1469 auto_space<
1470 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1471 std::size_t i=0,size_=size();
1472 bool within_bucket=false;
1473 BOOST_TRY{
1474 for(;i!=size_;++i){
1475 node_impl_pointer x=end_->prior();
1476
1477 /* only this can possibly throw */
1478 std::size_t h=hash_(key(index_node_type::from_impl(x)->value()));
1479
1480 hashes.data()[i]=h;
1481 node_ptrs.data()[i]=x;
1482 within_bucket=!node_alg::unlink_last(end_);
1483 node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1484 }
1485 }
1486 BOOST_CATCH(...){
1487 if(i!=0){
1488 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1489 if(!within_bucket)prev_buc=~prev_buc;
1490
1491 for(std::size_t j=i;j--;){
1492 std::size_t buc=buckets.position(hashes.data()[j]);
1493 node_impl_pointer x=node_ptrs.data()[j];
1494 if(buc==prev_buc)node_alg::append(x,end_);
1495 else node_alg::link(x,buckets.at(buc),end_);
1496 prev_buc=buc;
1497 }
1498 }
1499 BOOST_RETHROW;
1500 }
1501 BOOST_CATCH_END
1502 }
1503
1504 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1505 end_->next()=cpy_end->next();
1506 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1507 buckets.swap(buckets_cpy);
1508 calculate_max_load();
1509 }
1510
1511 void unchecked_rehash(size_type n,hashed_non_unique_tag)
1512 {
1513 node_impl_type cpy_end_node;
1514 node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1515 end_=header()->impl();
1516 bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1517
1518 if(size()!=0){
1519 auto_space<
1520 std::size_t,allocator_type> hashes(get_allocator(),size());
1521 auto_space<
1522 node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1523 std::size_t i=0;
1524 bool within_bucket=false;
1525 BOOST_TRY{
1526 for(;;++i){
1527 node_impl_pointer x=end_->prior();
1528 if(x==end_)break;
1529
1530 /* only this can possibly throw */
1531 std::size_t h=hash_(key(index_node_type::from_impl(x)->value()));
1532
1533 hashes.data()[i]=h;
1534 node_ptrs.data()[i]=x;
1535 std::pair<node_impl_pointer,bool> p=
1536 node_alg::unlink_last_group(end_);
1537 node_alg::link_range(
1538 p.first,x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1539 within_bucket=!(p.second);
1540 }
1541 }
1542 BOOST_CATCH(...){
1543 if(i!=0){
1544 std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1545 if(!within_bucket)prev_buc=~prev_buc;
1546
1547 for(std::size_t j=i;j--;){
1548 std::size_t buc=buckets.position(hashes.data()[j]);
1549 node_impl_pointer x=node_ptrs.data()[j],
1550 y=
1551 x->prior()->next()!=node_impl_type::base_pointer_from(x)&&
1552 x->prior()->next()->prior()!=x?
1553 node_impl_type::pointer_from(x->prior()->next()):x;
1554 node_alg::unlink_range(y,x);
1555 if(buc==prev_buc)node_alg::append_range(y,x,end_);
1556 else node_alg::link_range(y,x,buckets.at(buc),end_);
1557 prev_buc=buc;
1558 }
1559 }
1560 BOOST_RETHROW;
1561 }
1562 BOOST_CATCH_END
1563 }
1564
1565 end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1566 end_->next()=cpy_end->next();
1567 end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1568 buckets.swap(buckets_cpy);
1569 calculate_max_load();
1570 }
1571
1572 bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1573 {
1574 return in_place(x,k,buc,Category());
1575 }
1576
1577 bool in_place(
1578 node_impl_pointer x,key_param_type k,std::size_t buc,
1579 hashed_unique_tag)const
1580 {
1581 bool found=false;
1582 for(node_impl_pointer y=buckets.at(buc)->prior();
1583 y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1584 if(y==x)found=true;
1585 else if(eq_(k,key(index_node_type::from_impl(y)->value())))return false;
1586 }
1587 return found;
1588 }
1589
1590 bool in_place(
1591 node_impl_pointer x,key_param_type k,std::size_t buc,
1592 hashed_non_unique_tag)const
1593 {
1594 bool found=false;
1595 int range_size=0;
1596 for(node_impl_pointer y=buckets.at(buc)->prior();y!=node_impl_pointer(0);){
1597 if(node_alg::is_first_of_group(y)){ /* group of 3 or more */
1598 if(y==x){
1599 /* in place <-> equal to some other member of the group */
1600 return eq_(
1601 k,
1602 key(index_node_type::from_impl(
1603 node_impl_type::pointer_from(y->next()))->value()));
1604 }
1605 else{
1606 node_impl_pointer z=
1607 node_alg::after_local(y->next()->prior()); /* end of range */
1608 if(eq_(k,key(index_node_type::from_impl(y)->value()))){
1609 if(found)return false; /* x lies outside */
1610 do{
1611 if(y==x)return true;
1612 y=node_alg::after_local(y);
1613 }while(y!=z);
1614 return false; /* x not found */
1615 }
1616 else{
1617 if(range_size==1&&!found)return false;
1618 if(range_size==2)return found;
1619 range_size=0;
1620 y=z; /* skip range (and potentially x, too, which is fine) */
1621 }
1622 }
1623 }
1624 else{ /* group of 1 or 2 */
1625 if(y==x){
1626 if(range_size==1)return true;
1627 range_size=1;
1628 found=true;
1629 }
1630 else if(eq_(k,key(index_node_type::from_impl(y)->value()))){
1631 if(range_size==0&&found)return false;
1632 if(range_size==1&&!found)return false;
1633 if(range_size==2)return false;
1634 ++range_size;
1635 }
1636 else{
1637 if(range_size==1&&!found)return false;
1638 if(range_size==2)return found;
1639 range_size=0;
1640 }
1641 y=node_alg::after_local(y);
1642 }
1643 }
1644 return found;
1645 }
1646
1647#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1648 void detach_iterators(index_node_type* x)
1649 {
1650 iterator it=make_iterator(x);
1651 safe_mode::detach_equivalent_iterators(it);
1652 }
1653
1654 template<typename Dst>
1655 void transfer_iterators(Dst& dst,index_node_type* x)
1656 {
1657 iterator it=make_iterator(x);
1658 safe_mode::transfer_equivalent_iterators(dst,it);
1659 }
1660#endif
1661
1662 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1663 std::pair<iterator,bool> emplace_impl(BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1664 {
1665 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1666 std::pair<final_node_type*,bool>p=
1667 this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1668 return std::pair<iterator,bool>(make_iterator(p.first),p.second);
1669 }
1670
1671 template<BOOST_MULTI_INDEX_TEMPLATE_PARAM_PACK>
1672 iterator emplace_hint_impl(
1673 iterator position,BOOST_MULTI_INDEX_FUNCTION_PARAM_PACK)
1674 {
1675 BOOST_MULTI_INDEX_CHECK_VALID_ITERATOR(position);
1676 BOOST_MULTI_INDEX_CHECK_IS_OWNER(position,*this);
1677 BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
1678 std::pair<final_node_type*,bool>p=
1679 this->final_emplace_hint_(
1680 static_cast<final_node_type*>(position.get_node()),
1681 BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1682 return make_iterator(p.first);
1683 }
1684
1685 template<
1686 typename CompatibleHash,typename CompatiblePred
1687 >
1688 iterator find(
1689 const key_type& k,
1690 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1691 {
1692 return find(k,hash,eq,mpl::false_());
1693 }
1694
1695 template<
1696 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1697 >
1698 iterator find(
1699 const CompatibleKey& k,
1700 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1701 {
1702 std::size_t buc=buckets.position(hash(k));
1703 for(node_impl_pointer x=buckets.at(buc)->prior();
1704 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1705 if(eq(k,key(index_node_type::from_impl(x)->value()))){
1706 return make_iterator(index_node_type::from_impl(x));
1707 }
1708 }
1709 return end();
1710 }
1711
1712 template<
1713 typename CompatibleHash,typename CompatiblePred
1714 >
1715 size_type count(
1716 const key_type& k,
1717 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1718 {
1719 return count(k,hash,eq,mpl::false_());
1720 }
1721
1722 template<
1723 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1724 >
1725 size_type count(
1726 const CompatibleKey& k,
1727 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1728 {
1729 std::size_t buc=buckets.position(hash(k));
1730 for(node_impl_pointer x=buckets.at(buc)->prior();
1731 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1732 if(eq(k,key(index_node_type::from_impl(x)->value()))){
1733 size_type res=0;
1734 node_impl_pointer y=end_of_range(x);
1735 do{
1736 ++res;
1737 x=node_alg::after(x);
1738 }while(x!=y);
1739 return res;
1740 }
1741 }
1742 return 0;
1743 }
1744
1745 template<
1746 typename CompatibleHash,typename CompatiblePred
1747 >
1748 std::pair<iterator,iterator> equal_range(
1749 const key_type& k,
1750 const CompatibleHash& hash,const CompatiblePred& eq,mpl::true_)const
1751 {
1752 return equal_range(k,hash,eq,mpl::false_());
1753 }
1754
1755 template<
1756 typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
1757 >
1758 std::pair<iterator,iterator> equal_range(
1759 const CompatibleKey& k,
1760 const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1761 {
1762 std::size_t buc=buckets.position(hash(k));
1763 for(node_impl_pointer x=buckets.at(buc)->prior();
1764 x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1765 if(eq(k,key(index_node_type::from_impl(x)->value()))){
1766 return std::pair<iterator,iterator>(
1767 make_iterator(index_node_type::from_impl(x)),
1768 make_iterator(index_node_type::from_impl(end_of_range(x))));
1769 }
1770 }
1771 return std::pair<iterator,iterator>(end(),end());
1772 }
1773
1774 key_from_value key;
1775 hasher hash_;
1776 key_equal eq_;
1777 bucket_array_type buckets;
1778 float mlf;
1779 size_type max_load;
1780
1781#if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1782 safe_container safe;
1783#endif
1784
1785#if defined(BOOST_MULTI_INDEX_ENABLE_INVARIANT_CHECKING)&&\
1786 BOOST_WORKAROUND(__MWERKS__,<=0x3003)
1787#pragma parse_mfunc_templ reset
1788#endif
1789};
1790
1791#if defined(BOOST_MSVC)
1792#pragma warning(pop) /* C4355 */
1793#endif
1794
1795/* comparison */
1796
1797template<
1798 typename KeyFromValue,typename Hash,typename Pred,
1799 typename SuperMeta,typename TagList,typename Category
1800>
1801bool operator==(
1802 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1803 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1804{
1805 return x.equals(y);
1806}
1807
1808template<
1809 typename KeyFromValue,typename Hash,typename Pred,
1810 typename SuperMeta,typename TagList,typename Category
1811>
1812bool operator!=(
1813 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1814 const hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1815{
1816 return !(x==y);
1817}
1818
1819/* specialized algorithms */
1820
1821template<
1822 typename KeyFromValue,typename Hash,typename Pred,
1823 typename SuperMeta,typename TagList,typename Category
1824>
1825void swap(
1826 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& x,
1827 hashed_index<KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>& y)
1828{
1829 x.swap(y);
1830}
1831
1832} /* namespace multi_index::detail */
1833
1834/* hashed index specifiers */
1835
1836template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1837struct hashed_unique
1838{
1839 typedef typename detail::hashed_index_args<
1840 Arg1,Arg2,Arg3,Arg4> index_args;
1841 typedef typename index_args::tag_list_type::type tag_list_type;
1842 typedef typename index_args::key_from_value_type key_from_value_type;
1843 typedef typename index_args::hash_type hash_type;
1844 typedef typename index_args::pred_type pred_type;
1845
1846 template<typename Super>
1847 struct node_class
1848 {
1849 typedef detail::hashed_index_node<Super> type;
1850 };
1851
1852 template<typename SuperMeta>
1853 struct index_class
1854 {
1855 typedef detail::hashed_index<
1856 key_from_value_type,hash_type,pred_type,
1857 SuperMeta,tag_list_type,detail::hashed_unique_tag> type;
1858 };
1859};
1860
1861template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1862struct hashed_non_unique
1863{
1864 typedef typename detail::hashed_index_args<
1865 Arg1,Arg2,Arg3,Arg4> index_args;
1866 typedef typename index_args::tag_list_type::type tag_list_type;
1867 typedef typename index_args::key_from_value_type key_from_value_type;
1868 typedef typename index_args::hash_type hash_type;
1869 typedef typename index_args::pred_type pred_type;
1870
1871 template<typename Super>
1872 struct node_class
1873 {
1874 typedef detail::hashed_index_node<Super> type;
1875 };
1876
1877 template<typename SuperMeta>
1878 struct index_class
1879 {
1880 typedef detail::hashed_index<
1881 key_from_value_type,hash_type,pred_type,
1882 SuperMeta,tag_list_type,detail::hashed_non_unique_tag> type;
1883 };
1884};
1885
1886} /* namespace multi_index */
1887
1888} /* namespace boost */
1889
1890/* Boost.Foreach compatibility */
1891
1892namespace boost{
1893namespace foreach{
1894
1895template<typename>
1896struct is_noncopyable;
1897
1898template<
1899 typename KeyFromValue,typename Hash,typename Pred,
1900 typename SuperMeta,typename TagList,typename Category
1901>
1902struct is_noncopyable<boost::multi_index::detail::hashed_index<
1903 KeyFromValue,Hash,Pred,SuperMeta,TagList,Category>
1904>:boost::mpl::true_{};
1905
1906}
1907}
1908
1909#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT
1910#undef BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT_OF
1911
1912#endif
1913