Line data Source code
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 :
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 : #if defined(BOOST_MSVC)
86 : #pragma warning(push)
87 : #pragma warning(disable:4355) /* this used in base member initializer list */
88 : #endif
89 :
90 : template<
91 : typename KeyFromValue,typename Hash,typename Pred,
92 : typename SuperMeta,typename TagList,typename Category
93 : >
94 : class 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 :
115 : protected:
116 : typedef hashed_index_node<
117 : typename super::index_node_type> index_node_type;
118 :
119 : private:
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 :
128 : public:
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 :
138 : private:
139 : typedef allocator_traits<allocator_type> alloc_traits;
140 :
141 : public:
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 :
175 : protected:
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 :
196 : private:
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 :
209 : public:
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 45 : allocator_type get_allocator()const BOOST_NOEXCEPT
233 : {
234 45 : return this->final().get_allocator();
235 : }
236 :
237 : /* size and capacity */
238 :
239 48989 : bool empty()const BOOST_NOEXCEPT{return this->final_empty_();}
240 15152541 : 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 49 : iterator begin()BOOST_NOEXCEPT
246 : {
247 49 : return make_iterator(
248 49 : index_node_type::from_impl(header()->next()->prior()));
249 :
250 : }
251 24273 : const_iterator begin()const BOOST_NOEXCEPT
252 : {
253 24273 : return make_iterator(
254 24273 : index_node_type::from_impl(header()->next()->prior()));
255 : }
256 :
257 128344 : iterator end()BOOST_NOEXCEPT{return make_iterator(header());}
258 1437042 : 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 2203 : iterator iterator_to(const value_type& x)
263 : {
264 2203 : return make_iterator(
265 2203 : node_from_value<index_node_type>(boost::addressof(x)));
266 : }
267 :
268 3075816 : const_iterator iterator_to(const value_type& x)const
269 : {
270 3075816 : return make_iterator(
271 3075816 : node_from_value<index_node_type>(boost::addressof(x)));
272 : }
273 :
274 : /* modifiers */
275 :
276 26904 : 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 387 : std::pair<iterator,bool> insert(const value_type& x)
283 : {
284 : BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
285 387 : std::pair<final_node_type*,bool> p=this->final_insert_(x);
286 387 : 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 24701 : 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 24701 : this->final_erase_(static_cast<final_node_type*>(position++.get_node()));
373 24701 : 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 1036159 : 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 1036159 : return this->final_modify_(
451 1036159 : 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 23808 : void clear()BOOST_NOEXCEPT
500 : {
501 : BOOST_MULTI_INDEX_HASHED_INDEX_CHECK_INVARIANT;
502 23808 : this->final_clear_();
503 23808 : }
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 808603 : iterator find(const CompatibleKey& k)const
598 : {
599 808603 : return find(k,hash_,eq_);
600 : }
601 :
602 : template<
603 : typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
604 : >
605 808603 : iterator find(
606 : const CompatibleKey& k,
607 : const CompatibleHash& hash,const CompatiblePred& eq)const
608 : {
609 808603 : return find(
610 808603 : k,hash,eq,promotes_1st_arg<CompatiblePred,CompatibleKey,key_type>());
611 : }
612 :
613 : template<typename CompatibleKey>
614 241 : size_type count(const CompatibleKey& k)const
615 : {
616 241 : return count(k,hash_,eq_);
617 : }
618 :
619 : template<
620 : typename CompatibleKey,typename CompatibleHash,typename CompatiblePred
621 : >
622 241 : size_type count(
623 : const CompatibleKey& k,
624 : const CompatibleHash& hash,const CompatiblePred& eq)const
625 : {
626 241 : return count(
627 241 : 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 48105 : size_type bucket_count()const BOOST_NOEXCEPT
666 : {
667 48105 : 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 1063450 : size_type bucket(key_param_type k)const
683 : {
684 1063450 : 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(static_cast<size_type>(std::ceil(static_cast<float>(n)/mlf)));
748 : }
749 :
750 : BOOST_MULTI_INDEX_PROTECTED_IF_MEMBER_TEMPLATE_FRIENDS:
751 48090 : hashed_index(const ctor_args_list& args_list,const allocator_type& al):
752 48090 : super(args_list.get_tail(),al),
753 48090 : key(tuples::get<1>(args_list.get_head())),
754 48090 : hash_(tuples::get<2>(args_list.get_head())),
755 48090 : eq_(tuples::get<3>(args_list.get_head())),
756 48090 : buckets(al,header()->impl(),tuples::get<0>(args_list.get_head())),
757 48090 : mlf(1.0f)
758 :
759 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
760 : ,safe(*this)
761 : #endif
762 :
763 : {
764 48090 : calculate_max_load();
765 48090 : }
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 48090 : ~hashed_index()
806 : {
807 : /* the container is guaranteed to be empty by now */
808 48090 : }
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 157893 : iterator make_iterator(index_node_type* node)
822 : {
823 157893 : return iterator(node);
824 : }
825 :
826 4618558 : const_iterator make_iterator(index_node_type* node)const
827 : {
828 4618558 : 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 27291 : final_node_type* insert_(
935 : value_param_type v,final_node_type*& x,Variant variant)
936 : {
937 27291 : reserve_for_insert(size()+1);
938 :
939 27291 : std::size_t buc=find_bucket(v);
940 27291 : link_info pos(buckets.at(buc));
941 27291 : if(!link_point(v,pos)){
942 0 : return static_cast<final_node_type*>(
943 0 : index_node_type::from_impl(node_impl_type::pointer_from(pos)));
944 : }
945 :
946 27291 : final_node_type* res=super::insert_(v,x,variant);
947 27291 : if(res==x)link(static_cast<index_node_type*>(x),pos);
948 27291 : return res;
949 27291 : }
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(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 24701 : void extract_(index_node_type* x,Dst dst)
972 : {
973 24701 : unlink(x);
974 24701 : super::extract_(x,dst.next());
975 :
976 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
977 : transfer_iterators(dst.get(),x);
978 : #endif
979 24701 : }
980 :
981 71898 : void delete_all_nodes_()
982 : {
983 71898 : delete_all_nodes_(Category());
984 71898 : }
985 :
986 71898 : void delete_all_nodes_(hashed_unique_tag)
987 : {
988 74488 : for(node_impl_pointer x_end=header()->impl(),x=x_end->prior();x!=x_end;){
989 2590 : node_impl_pointer y=x->prior();
990 2590 : this->final_delete_node_(
991 2590 : static_cast<final_node_type*>(index_node_type::from_impl(x)));
992 2590 : x=y;
993 : }
994 71898 : }
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 23808 : void clear_()
1016 : {
1017 23808 : super::clear_();
1018 23808 : buckets.clear(header()->impl());
1019 :
1020 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1021 : safe.detach_dereferenceable_iterators();
1022 : #endif
1023 23808 : }
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 1036159 : bool modify_(index_node_type* x)
1086 : {
1087 : std::size_t buc;
1088 : bool b;
1089 : BOOST_TRY{
1090 1036159 : buc=find_bucket(x->value());
1091 1036159 : b=in_place(x->impl(),key(x->value()),buc);
1092 1036159 : }
1093 : BOOST_CATCH(...){
1094 0 : extract_(x,invalidate_iterators());
1095 0 : BOOST_RETHROW;
1096 0 : }
1097 : BOOST_CATCH_END
1098 1036159 : if(!b){
1099 0 : unlink(x);
1100 : BOOST_TRY{
1101 0 : link_info pos(buckets.at(buc));
1102 0 : if(!link_point(x->value(),pos)){
1103 0 : super::extract_(x,invalidate_iterators());
1104 :
1105 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1106 : detach_iterators(x);
1107 : #endif
1108 0 : return false;
1109 : }
1110 0 : link(x,pos);
1111 0 : }
1112 : BOOST_CATCH(...){
1113 0 : super::extract_(x,invalidate_iterators());
1114 :
1115 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1116 : detach_iterators(x);
1117 : #endif
1118 :
1119 0 : BOOST_RETHROW;
1120 0 : }
1121 : BOOST_CATCH_END
1122 0 : }
1123 :
1124 : BOOST_TRY{
1125 1036159 : if(!super::modify_(x)){
1126 0 : unlink(x);
1127 :
1128 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1129 : detach_iterators(x);
1130 : #endif
1131 0 : return false;
1132 : }
1133 1036159 : else return true;
1134 0 : }
1135 : BOOST_CATCH(...){
1136 0 : unlink(x);
1137 :
1138 : #if defined(BOOST_MULTI_INDEX_ENABLE_SAFE_MODE)
1139 : detach_iterators(x);
1140 : #endif
1141 :
1142 0 : BOOST_RETHROW;
1143 0 : }
1144 : BOOST_CATCH_END
1145 1036159 : }
1146 :
1147 : bool modify_rollback_(index_node_type* x)
1148 : {
1149 : std::size_t buc=find_bucket(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(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 :
1288 : private:
1289 1760810 : index_node_type* header()const{return this->final_header();}
1290 :
1291 1063450 : std::size_t find_bucket(value_param_type v)const
1292 : {
1293 1063450 : return bucket(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 27291 : bool link_point(value_param_type v,link_info& pos)
1313 : {
1314 27291 : return link_point(v,pos,Category());
1315 : }
1316 :
1317 27291 : bool link_point(
1318 : value_param_type v,node_impl_base_pointer& pos,hashed_unique_tag)
1319 : {
1320 33020 : for(node_impl_pointer x=pos->prior();x!=node_impl_pointer(0);
1321 5729 : x=node_alg::after_local(x)){
1322 5729 : if(eq_(key(v),key(index_node_type::from_impl(x)->value()))){
1323 0 : pos=node_impl_type::base_pointer_from(x);
1324 0 : return false;
1325 : }
1326 5729 : }
1327 27291 : return true;
1328 27291 : }
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 103 : node_impl_pointer last_of_range(node_impl_pointer x)const
1345 : {
1346 103 : return last_of_range(x,Category());
1347 : }
1348 :
1349 103 : node_impl_pointer last_of_range(node_impl_pointer x,hashed_unique_tag)const
1350 : {
1351 103 : 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 103 : node_impl_pointer end_of_range(node_impl_pointer x)const
1373 : {
1374 103 : return end_of_range(x,Category());
1375 : }
1376 :
1377 103 : node_impl_pointer end_of_range(node_impl_pointer x,hashed_unique_tag)const
1378 : {
1379 103 : 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 27291 : void link(index_node_type* x,const link_info& pos)
1405 : {
1406 27291 : link(x,pos,Category());
1407 27291 : }
1408 :
1409 27291 : void link(index_node_type* x,node_impl_base_pointer pos,hashed_unique_tag)
1410 : {
1411 27291 : node_alg::link(x->impl(),pos,header()->impl());
1412 27291 : }
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 24701 : void unlink(index_node_type* x)
1429 : {
1430 24701 : node_alg::unlink(x->impl());
1431 24701 : }
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 48105 : void calculate_max_load()
1441 : {
1442 48105 : float fml=mlf*static_cast<float>(bucket_count());
1443 48105 : max_load=(std::numeric_limits<size_type>::max)();
1444 48105 : if(max_load>fml)max_load=static_cast<size_type>(fml);
1445 48105 : }
1446 :
1447 27291 : void reserve_for_insert(size_type n)
1448 : {
1449 27291 : if(n>max_load){
1450 15 : size_type bc =(std::numeric_limits<size_type>::max)();
1451 15 : float fbc=1.0f+static_cast<float>(n)/mlf;
1452 15 : if(bc>fbc)bc =static_cast<size_type>(fbc);
1453 15 : unchecked_rehash(bc);
1454 15 : }
1455 27291 : }
1456 :
1457 15 : void unchecked_rehash(size_type n){unchecked_rehash(n,Category());}
1458 :
1459 15 : void unchecked_rehash(size_type n,hashed_unique_tag)
1460 : {
1461 : node_impl_type cpy_end_node;
1462 15 : node_impl_pointer cpy_end=node_impl_pointer(&cpy_end_node),
1463 15 : end_=header()->impl();
1464 15 : bucket_array_type buckets_cpy(get_allocator(),cpy_end,n);
1465 :
1466 15 : if(size()!=0){
1467 : auto_space<
1468 15 : std::size_t,allocator_type> hashes(get_allocator(),size());
1469 : auto_space<
1470 15 : node_impl_pointer,allocator_type> node_ptrs(get_allocator(),size());
1471 15 : std::size_t i=0,size_=size();
1472 15 : bool within_bucket=false;
1473 : BOOST_TRY{
1474 2698 : for(;i!=size_;++i){
1475 2683 : node_impl_pointer x=end_->prior();
1476 :
1477 : /* only this can possibly throw */
1478 2683 : std::size_t h=hash_(key(index_node_type::from_impl(x)->value()));
1479 :
1480 2683 : hashes.data()[i]=h;
1481 2683 : node_ptrs.data()[i]=x;
1482 2683 : within_bucket=!node_alg::unlink_last(end_);
1483 2683 : node_alg::link(x,buckets_cpy.at(buckets_cpy.position(h)),cpy_end);
1484 2683 : }
1485 15 : }
1486 : BOOST_CATCH(...){
1487 0 : if(i!=0){
1488 0 : std::size_t prev_buc=buckets.position(hashes.data()[i-1]);
1489 0 : if(!within_bucket)prev_buc=~prev_buc;
1490 :
1491 0 : for(std::size_t j=i;j--;){
1492 0 : std::size_t buc=buckets.position(hashes.data()[j]);
1493 0 : node_impl_pointer x=node_ptrs.data()[j];
1494 0 : if(buc==prev_buc)node_alg::append(x,end_);
1495 0 : else node_alg::link(x,buckets.at(buc),end_);
1496 0 : prev_buc=buc;
1497 : }
1498 0 : }
1499 0 : BOOST_RETHROW;
1500 0 : }
1501 : BOOST_CATCH_END
1502 15 : }
1503 :
1504 15 : end_->prior()=cpy_end->prior()!=cpy_end?cpy_end->prior():end_;
1505 15 : end_->next()=cpy_end->next();
1506 15 : end_->prior()->next()->prior()=end_->next()->prior()->prior()=end_;
1507 15 : buckets.swap(buckets_cpy);
1508 15 : calculate_max_load();
1509 15 : }
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 1036159 : bool in_place(node_impl_pointer x,key_param_type k,std::size_t buc)const
1573 : {
1574 1036159 : return in_place(x,k,buc,Category());
1575 : }
1576 :
1577 1036159 : bool in_place(
1578 : node_impl_pointer x,key_param_type k,std::size_t buc,
1579 : hashed_unique_tag)const
1580 : {
1581 1036159 : bool found=false;
1582 2678836 : for(node_impl_pointer y=buckets.at(buc)->prior();
1583 2678836 : y!=node_impl_pointer(0);y=node_alg::after_local(y)){
1584 1642677 : if(y==x)found=true;
1585 606518 : else if(eq_(k,key(index_node_type::from_impl(y)->value())))return false;
1586 1642677 : }
1587 1036159 : return found;
1588 1036159 : }
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 26904 : 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 26904 : this->final_emplace_(BOOST_MULTI_INDEX_FORWARD_PARAM_PACK);
1668 26904 : 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 808603 : iterator find(
1699 : const CompatibleKey& k,
1700 : const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1701 : {
1702 808603 : std::size_t buc=buckets.position(hash(k));
1703 824331 : for(node_impl_pointer x=buckets.at(buc)->prior();
1704 824331 : x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1705 94811 : if(eq(k,key(index_node_type::from_impl(x)->value()))){
1706 79083 : return make_iterator(index_node_type::from_impl(x));
1707 : }
1708 15728 : }
1709 729520 : return end();
1710 808603 : }
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 241 : size_type count(
1726 : const CompatibleKey& k,
1727 : const CompatibleHash& hash,const CompatiblePred& eq,mpl::false_)const
1728 : {
1729 241 : std::size_t buc=buckets.position(hash(k));
1730 252 : for(node_impl_pointer x=buckets.at(buc)->prior();
1731 252 : x!=node_impl_pointer(0);x=node_alg::next_to_inspect(x)){
1732 114 : if(eq(k,key(index_node_type::from_impl(x)->value()))){
1733 103 : size_type res=0;
1734 103 : node_impl_pointer y=end_of_range(x);
1735 103 : do{
1736 103 : ++res;
1737 103 : x=node_alg::after(x);
1738 103 : }while(x!=y);
1739 103 : return res;
1740 : }
1741 11 : }
1742 138 : return 0;
1743 241 : }
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 :
1797 : template<
1798 : typename KeyFromValue,typename Hash,typename Pred,
1799 : typename SuperMeta,typename TagList,typename Category
1800 : >
1801 : bool 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 :
1808 : template<
1809 : typename KeyFromValue,typename Hash,typename Pred,
1810 : typename SuperMeta,typename TagList,typename Category
1811 : >
1812 : bool 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 :
1821 : template<
1822 : typename KeyFromValue,typename Hash,typename Pred,
1823 : typename SuperMeta,typename TagList,typename Category
1824 : >
1825 : void 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 :
1836 : template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1837 : struct 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 :
1861 : template<typename Arg1,typename Arg2,typename Arg3,typename Arg4>
1862 : struct 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 :
1892 : namespace boost{
1893 : namespace foreach{
1894 :
1895 : template<typename>
1896 : struct is_noncopyable;
1897 :
1898 : template<
1899 : typename KeyFromValue,typename Hash,typename Pred,
1900 : typename SuperMeta,typename TagList,typename Category
1901 : >
1902 : struct 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
|
