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