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