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