]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ///////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2006-2015 | |
4 | // | |
5 | // Distributed under the Boost Software License, Version 1.0. | |
6 | // (See accompanying file LICENSE_1_0.txt or copy at | |
7 | // http://www.boost.org/LICENSE_1_0.txt) | |
8 | // | |
9 | // See http://www.boost.org/libs/intrusive for documentation. | |
10 | // | |
11 | ///////////////////////////////////////////////////////////////////////////// | |
12 | #ifndef BOOST_INTRUSIVE_HASHTABLE_HPP | |
13 | #define BOOST_INTRUSIVE_HASHTABLE_HPP | |
14 | ||
15 | #include <boost/intrusive/detail/config_begin.hpp> | |
16 | #include <boost/intrusive/intrusive_fwd.hpp> | |
17 | ||
18 | //General intrusive utilities | |
19 | #include <boost/intrusive/detail/hashtable_node.hpp> | |
20 | #include <boost/intrusive/detail/transform_iterator.hpp> | |
21 | #include <boost/intrusive/link_mode.hpp> | |
22 | #include <boost/intrusive/detail/ebo_functor_holder.hpp> | |
23 | #include <boost/intrusive/detail/is_stateful_value_traits.hpp> | |
24 | #include <boost/intrusive/detail/node_to_value.hpp> | |
25 | #include <boost/intrusive/detail/exception_disposer.hpp> | |
26 | #include <boost/intrusive/detail/node_cloner_disposer.hpp> | |
27 | #include <boost/intrusive/detail/simple_disposers.hpp> | |
28 | #include <boost/intrusive/detail/size_holder.hpp> | |
29 | #include <boost/intrusive/detail/iterator.hpp> | |
30 | ||
31 | //Implementation utilities | |
32 | #include <boost/intrusive/unordered_set_hook.hpp> | |
33 | #include <boost/intrusive/slist.hpp> | |
34 | #include <boost/intrusive/pointer_traits.hpp> | |
35 | #include <boost/intrusive/detail/mpl.hpp> | |
36 | ||
37 | //boost | |
38 | #include <boost/functional/hash.hpp> | |
39 | #include <boost/intrusive/detail/assert.hpp> | |
40 | #include <boost/static_assert.hpp> | |
41 | #include <boost/move/utility_core.hpp> | |
42 | #include <boost/move/adl_move_swap.hpp> | |
43 | ||
44 | //std C++ | |
45 | #include <boost/intrusive/detail/minimal_less_equal_header.hpp> //std::equal_to | |
46 | #include <boost/intrusive/detail/minimal_pair_header.hpp> //std::pair | |
47 | #include <algorithm> //std::lower_bound, std::upper_bound | |
48 | #include <cstddef> //std::size_t | |
49 | ||
50 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
51 | # pragma once | |
52 | #endif | |
53 | ||
54 | namespace boost { | |
55 | namespace intrusive { | |
56 | ||
57 | /// @cond | |
58 | ||
59 | template<class InputIt, class T> | |
60 | InputIt priv_algo_find(InputIt first, InputIt last, const T& value) | |
61 | { | |
62 | for (; first != last; ++first) { | |
63 | if (*first == value) { | |
64 | return first; | |
65 | } | |
66 | } | |
67 | return last; | |
68 | } | |
69 | ||
70 | template<class InputIt, class T> | |
71 | typename boost::intrusive::iterator_traits<InputIt>::difference_type | |
72 | priv_algo_count(InputIt first, InputIt last, const T& value) | |
73 | { | |
74 | typename boost::intrusive::iterator_traits<InputIt>::difference_type ret = 0; | |
75 | for (; first != last; ++first) { | |
76 | if (*first == value) { | |
77 | ret++; | |
78 | } | |
79 | } | |
80 | return ret; | |
81 | } | |
82 | ||
83 | template <class ForwardIterator1, class ForwardIterator2> | |
84 | bool priv_algo_is_permutation(ForwardIterator1 first1, ForwardIterator1 last1, ForwardIterator2 first2) | |
85 | { | |
86 | typedef typename | |
87 | boost::intrusive::iterator_traits<ForwardIterator2>::difference_type | |
88 | distance_type; | |
89 | //Efficiently compare identical prefixes: O(N) if sequences | |
90 | //have the same elements in the same order. | |
91 | for ( ; first1 != last1; ++first1, ++first2){ | |
92 | if (! (*first1 == *first2)) | |
93 | break; | |
94 | } | |
95 | if (first1 == last1){ | |
96 | return true; | |
97 | } | |
98 | ||
99 | //Establish last2 assuming equal ranges by iterating over the | |
100 | //rest of the list. | |
101 | ForwardIterator2 last2 = first2; | |
102 | boost::intrusive::iterator_advance(last2, boost::intrusive::iterator_distance(first1, last1)); | |
103 | for(ForwardIterator1 scan = first1; scan != last1; ++scan){ | |
104 | if (scan != (priv_algo_find)(first1, scan, *scan)){ | |
105 | continue; //We've seen this one before. | |
106 | } | |
107 | distance_type matches = (priv_algo_count)(first2, last2, *scan); | |
108 | if (0 == matches || (priv_algo_count)(scan, last1, *scan != matches)){ | |
109 | return false; | |
110 | } | |
111 | } | |
112 | return true; | |
113 | } | |
114 | ||
115 | template<int Dummy = 0> | |
116 | struct prime_list_holder | |
117 | { | |
118 | static const std::size_t prime_list[]; | |
119 | static const std::size_t prime_list_size; | |
120 | }; | |
121 | ||
122 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
123 | ||
124 | //We only support LLP64(Win64) or LP64(most Unix) data models | |
125 | #ifdef _WIN64 //In 64 bit windows sizeof(size_t) == sizeof(unsigned long long) | |
126 | #define BOOST_INTRUSIVE_PRIME_C(NUMBER) NUMBER##ULL | |
127 | #define BOOST_INTRUSIVE_64_BIT_SIZE_T 1 | |
128 | #else //In 32 bit windows and 32/64 bit unixes sizeof(size_t) == sizeof(unsigned long) | |
129 | #define BOOST_INTRUSIVE_PRIME_C(NUMBER) NUMBER##UL | |
130 | #define BOOST_INTRUSIVE_64_BIT_SIZE_T (((((ULONG_MAX>>16)>>16)>>16)>>15) != 0) | |
131 | #endif | |
132 | ||
133 | template<int Dummy> | |
134 | const std::size_t prime_list_holder<Dummy>::prime_list[] = { | |
135 | BOOST_INTRUSIVE_PRIME_C(3), BOOST_INTRUSIVE_PRIME_C(7), | |
136 | BOOST_INTRUSIVE_PRIME_C(11), BOOST_INTRUSIVE_PRIME_C(17), | |
137 | BOOST_INTRUSIVE_PRIME_C(29), BOOST_INTRUSIVE_PRIME_C(53), | |
138 | BOOST_INTRUSIVE_PRIME_C(97), BOOST_INTRUSIVE_PRIME_C(193), | |
139 | BOOST_INTRUSIVE_PRIME_C(389), BOOST_INTRUSIVE_PRIME_C(769), | |
140 | BOOST_INTRUSIVE_PRIME_C(1543), BOOST_INTRUSIVE_PRIME_C(3079), | |
141 | BOOST_INTRUSIVE_PRIME_C(6151), BOOST_INTRUSIVE_PRIME_C(12289), | |
142 | BOOST_INTRUSIVE_PRIME_C(24593), BOOST_INTRUSIVE_PRIME_C(49157), | |
143 | BOOST_INTRUSIVE_PRIME_C(98317), BOOST_INTRUSIVE_PRIME_C(196613), | |
144 | BOOST_INTRUSIVE_PRIME_C(393241), BOOST_INTRUSIVE_PRIME_C(786433), | |
145 | BOOST_INTRUSIVE_PRIME_C(1572869), BOOST_INTRUSIVE_PRIME_C(3145739), | |
146 | BOOST_INTRUSIVE_PRIME_C(6291469), BOOST_INTRUSIVE_PRIME_C(12582917), | |
147 | BOOST_INTRUSIVE_PRIME_C(25165843), BOOST_INTRUSIVE_PRIME_C(50331653), | |
148 | BOOST_INTRUSIVE_PRIME_C(100663319), BOOST_INTRUSIVE_PRIME_C(201326611), | |
149 | BOOST_INTRUSIVE_PRIME_C(402653189), BOOST_INTRUSIVE_PRIME_C(805306457), | |
150 | BOOST_INTRUSIVE_PRIME_C(1610612741), BOOST_INTRUSIVE_PRIME_C(3221225473), | |
151 | #if BOOST_INTRUSIVE_64_BIT_SIZE_T | |
152 | //Taken from Boost.MultiIndex code, thanks to Joaquin M Lopez Munoz. | |
153 | BOOST_INTRUSIVE_PRIME_C(6442450939), BOOST_INTRUSIVE_PRIME_C(12884901893), | |
154 | BOOST_INTRUSIVE_PRIME_C(25769803751), BOOST_INTRUSIVE_PRIME_C(51539607551), | |
155 | BOOST_INTRUSIVE_PRIME_C(103079215111), BOOST_INTRUSIVE_PRIME_C(206158430209), | |
156 | BOOST_INTRUSIVE_PRIME_C(412316860441), BOOST_INTRUSIVE_PRIME_C(824633720831), | |
157 | BOOST_INTRUSIVE_PRIME_C(1649267441651), BOOST_INTRUSIVE_PRIME_C(3298534883309), | |
158 | BOOST_INTRUSIVE_PRIME_C(6597069766657), BOOST_INTRUSIVE_PRIME_C(13194139533299), | |
159 | BOOST_INTRUSIVE_PRIME_C(26388279066623), BOOST_INTRUSIVE_PRIME_C(52776558133303), | |
160 | BOOST_INTRUSIVE_PRIME_C(105553116266489), BOOST_INTRUSIVE_PRIME_C(211106232532969), | |
161 | BOOST_INTRUSIVE_PRIME_C(422212465066001), BOOST_INTRUSIVE_PRIME_C(844424930131963), | |
162 | BOOST_INTRUSIVE_PRIME_C(1688849860263953), BOOST_INTRUSIVE_PRIME_C(3377699720527861), | |
163 | BOOST_INTRUSIVE_PRIME_C(6755399441055731), BOOST_INTRUSIVE_PRIME_C(13510798882111483), | |
164 | BOOST_INTRUSIVE_PRIME_C(27021597764222939), BOOST_INTRUSIVE_PRIME_C(54043195528445957), | |
165 | BOOST_INTRUSIVE_PRIME_C(108086391056891903), BOOST_INTRUSIVE_PRIME_C(216172782113783843), | |
166 | BOOST_INTRUSIVE_PRIME_C(432345564227567621), BOOST_INTRUSIVE_PRIME_C(864691128455135207), | |
167 | BOOST_INTRUSIVE_PRIME_C(1729382256910270481), BOOST_INTRUSIVE_PRIME_C(3458764513820540933), | |
168 | BOOST_INTRUSIVE_PRIME_C(6917529027641081903), BOOST_INTRUSIVE_PRIME_C(13835058055282163729), | |
169 | BOOST_INTRUSIVE_PRIME_C(18446744073709551557) | |
170 | #else | |
171 | BOOST_INTRUSIVE_PRIME_C(4294967291) | |
172 | #endif | |
173 | }; | |
174 | ||
175 | #undef BOOST_INTRUSIVE_PRIME_C | |
176 | #undef BOOST_INTRUSIVE_64_BIT_SIZE_T | |
177 | ||
178 | #endif //#if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
179 | ||
180 | template<int Dummy> | |
181 | const std::size_t prime_list_holder<Dummy>::prime_list_size | |
182 | = sizeof(prime_list)/sizeof(std::size_t); | |
183 | ||
184 | struct hash_bool_flags | |
185 | { | |
186 | static const std::size_t unique_keys_pos = 1u; | |
187 | static const std::size_t constant_time_size_pos = 2u; | |
188 | static const std::size_t power_2_buckets_pos = 4u; | |
189 | static const std::size_t cache_begin_pos = 8u; | |
190 | static const std::size_t compare_hash_pos = 16u; | |
191 | static const std::size_t incremental_pos = 32u; | |
192 | }; | |
193 | ||
194 | namespace detail { | |
195 | ||
196 | template<class SupposedValueTraits> | |
197 | struct get_slist_impl_from_supposed_value_traits | |
198 | { | |
199 | typedef SupposedValueTraits value_traits; | |
200 | typedef typename detail::get_node_traits | |
201 | <value_traits>::type node_traits; | |
202 | typedef typename get_slist_impl | |
203 | <typename reduced_slist_node_traits | |
204 | <node_traits>::type | |
205 | >::type type; | |
206 | }; | |
207 | ||
208 | template<class SupposedValueTraits> | |
209 | struct unordered_bucket_impl | |
210 | { | |
211 | typedef typename | |
212 | get_slist_impl_from_supposed_value_traits | |
213 | <SupposedValueTraits>::type slist_impl; | |
214 | typedef detail::bucket_impl<slist_impl> implementation_defined; | |
215 | typedef implementation_defined type; | |
216 | }; | |
217 | ||
218 | template<class SupposedValueTraits> | |
219 | struct unordered_bucket_ptr_impl | |
220 | { | |
221 | typedef typename detail::get_node_traits | |
222 | <SupposedValueTraits>::type::node_ptr node_ptr; | |
223 | typedef typename unordered_bucket_impl | |
224 | <SupposedValueTraits>::type bucket_type; | |
225 | ||
226 | typedef typename pointer_traits | |
227 | <node_ptr>::template rebind_pointer | |
228 | < bucket_type >::type implementation_defined; | |
229 | typedef implementation_defined type; | |
230 | }; | |
231 | ||
232 | template <class T> | |
233 | struct store_hash_is_true | |
234 | { | |
235 | template<bool Add> | |
236 | struct two_or_three {yes_type _[2 + Add];}; | |
237 | template <class U> static yes_type test(...); | |
238 | template <class U> static two_or_three<U::store_hash> test (int); | |
239 | static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2; | |
240 | }; | |
241 | ||
242 | template <class T> | |
243 | struct optimize_multikey_is_true | |
244 | { | |
245 | template<bool Add> | |
246 | struct two_or_three {yes_type _[2 + Add];}; | |
247 | template <class U> static yes_type test(...); | |
248 | template <class U> static two_or_three<U::optimize_multikey> test (int); | |
249 | static const bool value = sizeof(test<T>(0)) > sizeof(yes_type)*2; | |
250 | }; | |
251 | ||
252 | struct insert_commit_data_impl | |
253 | { | |
254 | std::size_t hash; | |
255 | }; | |
256 | ||
257 | template<class Node, class SlistNodePtr> | |
258 | BOOST_INTRUSIVE_FORCEINLINE typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type | |
259 | dcast_bucket_ptr(const SlistNodePtr &p) | |
260 | { | |
261 | typedef typename pointer_traits<SlistNodePtr>::template rebind_pointer<Node>::type node_ptr; | |
262 | return pointer_traits<node_ptr>::pointer_to(static_cast<Node&>(*p)); | |
263 | } | |
264 | ||
265 | template<class NodeTraits> | |
266 | struct group_functions | |
267 | { | |
268 | // A group is reverse-linked | |
269 | // | |
270 | // A is "first in group" | |
271 | // C is "last in group" | |
272 | // __________________ | |
273 | // | _____ _____ | | |
274 | // | | | | | | <- Group links | |
275 | // ^ V ^ V ^ V | |
276 | // _ _ _ _ | |
277 | // A|_| B|_| C|_| D|_| | |
278 | // | |
279 | // ^ | ^ | ^ | ^ V <- Bucket links | |
280 | // _ _____| |_____| |______| |____| | | |
281 | // |B| | | |
282 | // ^________________________________| | |
283 | // | |
284 | ||
285 | typedef NodeTraits node_traits; | |
286 | typedef unordered_group_adapter<node_traits> group_traits; | |
287 | typedef typename node_traits::node_ptr node_ptr; | |
288 | typedef typename node_traits::node node; | |
289 | typedef typename reduced_slist_node_traits | |
290 | <node_traits>::type reduced_node_traits; | |
291 | typedef typename reduced_node_traits::node_ptr slist_node_ptr; | |
292 | typedef typename reduced_node_traits::node slist_node; | |
293 | typedef circular_slist_algorithms<group_traits> group_algorithms; | |
294 | typedef circular_slist_algorithms<node_traits> node_algorithms; | |
295 | ||
296 | static slist_node_ptr get_bucket_before_begin | |
297 | (const slist_node_ptr &bucket_beg, const slist_node_ptr &bucket_end, const node_ptr &p) | |
298 | { | |
299 | //First find the last node of p's group. | |
300 | //This requires checking the first node of the next group or | |
301 | //the bucket node. | |
302 | node_ptr prev_node = p; | |
303 | node_ptr nxt(node_traits::get_next(p)); | |
304 | while(!(bucket_beg <= nxt && nxt <= bucket_end) && | |
305 | (group_traits::get_next(nxt) == prev_node)){ | |
306 | prev_node = nxt; | |
307 | nxt = node_traits::get_next(nxt); | |
308 | } | |
309 | ||
310 | //If we've reached the bucket node just return it. | |
311 | if(bucket_beg <= nxt && nxt <= bucket_end){ | |
312 | return nxt; | |
313 | } | |
314 | ||
315 | //Otherwise, iterate using group links until the bucket node | |
316 | node_ptr first_node_of_group = nxt; | |
317 | node_ptr last_node_group = group_traits::get_next(first_node_of_group); | |
318 | slist_node_ptr possible_end = node_traits::get_next(last_node_group); | |
319 | ||
320 | while(!(bucket_beg <= possible_end && possible_end <= bucket_end)){ | |
321 | first_node_of_group = detail::dcast_bucket_ptr<node>(possible_end); | |
322 | last_node_group = group_traits::get_next(first_node_of_group); | |
323 | possible_end = node_traits::get_next(last_node_group); | |
324 | } | |
325 | return possible_end; | |
326 | } | |
327 | ||
328 | static node_ptr get_prev_to_first_in_group(const slist_node_ptr &bucket_node, const node_ptr &first_in_group) | |
329 | { | |
330 | node_ptr nb = detail::dcast_bucket_ptr<node>(bucket_node); | |
331 | node_ptr n; | |
332 | while((n = node_traits::get_next(nb)) != first_in_group){ | |
333 | nb = group_traits::get_next(n); //go to last in group | |
334 | } | |
335 | return nb; | |
336 | } | |
337 | ||
338 | static void erase_from_group(const slist_node_ptr &end_ptr, const node_ptr &to_erase_ptr, detail::true_) | |
339 | { | |
340 | node_ptr const nxt_ptr(node_traits::get_next(to_erase_ptr)); | |
341 | //Check if the next node is in the group (not end node) and reverse linked to | |
342 | //'to_erase_ptr'. Erase if that's the case. | |
343 | if(nxt_ptr != end_ptr && to_erase_ptr == group_traits::get_next(nxt_ptr)){ | |
344 | group_algorithms::unlink_after(nxt_ptr); | |
345 | } | |
346 | } | |
347 | ||
348 | BOOST_INTRUSIVE_FORCEINLINE static void erase_from_group(const slist_node_ptr&, const node_ptr&, detail::false_) | |
349 | {} | |
350 | ||
351 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(const node_ptr &first_in_group, detail::true_) | |
352 | { return group_traits::get_next(first_in_group); } | |
353 | ||
354 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_last_in_group(node_ptr n, detail::false_) | |
355 | { return n; } | |
356 | ||
357 | static node_ptr get_first_in_group(node_ptr n, detail::true_) | |
358 | { | |
359 | node_ptr ng; | |
360 | while(n == node_traits::get_next((ng = group_traits::get_next(n)))){ | |
361 | n = ng; | |
362 | } | |
363 | return n; | |
364 | } | |
365 | ||
366 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr next_group_if_first_in_group(node_ptr ptr) | |
367 | { | |
368 | return node_traits::get_next(group_traits::get_next(ptr)); | |
369 | } | |
370 | ||
371 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr get_first_in_group(const node_ptr &n, detail::false_) | |
372 | { return n; } | |
373 | ||
374 | BOOST_INTRUSIVE_FORCEINLINE static void insert_in_group(const node_ptr &first_in_group, const node_ptr &n, true_) | |
375 | { group_algorithms::link_after(first_in_group, n); } | |
376 | ||
377 | static void insert_in_group(const node_ptr&, const node_ptr&, false_) | |
378 | {} | |
379 | ||
380 | BOOST_INTRUSIVE_FORCEINLINE static node_ptr split_group(node_ptr const new_first_in_group) | |
381 | { | |
382 | node_ptr const first((get_first_in_group)(new_first_in_group, detail::true_())); | |
383 | if(first != new_first_in_group){ | |
384 | node_ptr const last = group_traits::get_next(first); | |
385 | group_traits::set_next(first, group_traits::get_next(new_first_in_group)); | |
386 | group_traits::set_next(new_first_in_group, last); | |
387 | } | |
388 | return first; | |
389 | } | |
390 | }; | |
391 | ||
392 | template<class BucketType, class SplitTraits> | |
393 | class incremental_rehash_rollback | |
394 | { | |
395 | private: | |
396 | typedef BucketType bucket_type; | |
397 | typedef SplitTraits split_traits; | |
398 | ||
399 | incremental_rehash_rollback(); | |
400 | incremental_rehash_rollback & operator=(const incremental_rehash_rollback &); | |
401 | incremental_rehash_rollback (const incremental_rehash_rollback &); | |
402 | ||
403 | public: | |
404 | incremental_rehash_rollback | |
405 | (bucket_type &source_bucket, bucket_type &destiny_bucket, split_traits &split_traits) | |
406 | : source_bucket_(source_bucket), destiny_bucket_(destiny_bucket) | |
407 | , split_traits_(split_traits), released_(false) | |
408 | {} | |
409 | ||
410 | BOOST_INTRUSIVE_FORCEINLINE void release() | |
411 | { released_ = true; } | |
412 | ||
413 | ~incremental_rehash_rollback() | |
414 | { | |
415 | if(!released_){ | |
416 | //If an exception is thrown, just put all moved nodes back in the old bucket | |
417 | //and move back the split mark. | |
418 | destiny_bucket_.splice_after(destiny_bucket_.before_begin(), source_bucket_); | |
419 | split_traits_.decrement(); | |
420 | } | |
421 | } | |
422 | ||
423 | private: | |
424 | bucket_type &source_bucket_; | |
425 | bucket_type &destiny_bucket_; | |
426 | split_traits &split_traits_; | |
427 | bool released_; | |
428 | }; | |
429 | ||
430 | template<class NodeTraits> | |
431 | struct node_functions | |
432 | { | |
433 | BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr p, std::size_t h, true_) | |
434 | { return NodeTraits::set_hash(p, h); } | |
435 | ||
436 | BOOST_INTRUSIVE_FORCEINLINE static void store_hash(typename NodeTraits::node_ptr, std::size_t, false_) | |
437 | {} | |
438 | }; | |
439 | ||
440 | BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::false_) | |
441 | { return hash_value % bucket_cnt; } | |
442 | ||
443 | BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket(std::size_t hash_value, std::size_t bucket_cnt, detail::true_) | |
444 | { return hash_value & (bucket_cnt - 1); } | |
445 | ||
446 | template<bool Power2Buckets, bool Incremental> | |
447 | BOOST_INTRUSIVE_FORCEINLINE std::size_t hash_to_bucket_split(std::size_t hash_value, std::size_t bucket_cnt, std::size_t split) | |
448 | { | |
449 | std::size_t bucket_number = detail::hash_to_bucket(hash_value, bucket_cnt, detail::bool_<Power2Buckets>()); | |
450 | if(Incremental) | |
451 | bucket_number -= static_cast<std::size_t>(bucket_number >= split)*(bucket_cnt/2); | |
452 | return bucket_number; | |
453 | } | |
454 | ||
455 | } //namespace detail { | |
456 | ||
457 | //!This metafunction will obtain the type of a bucket | |
458 | //!from the value_traits or hook option to be used with | |
459 | //!a hash container. | |
460 | template<class ValueTraitsOrHookOption> | |
461 | struct unordered_bucket | |
462 | : public detail::unordered_bucket_impl | |
463 | <typename ValueTraitsOrHookOption:: | |
464 | template pack<empty>::proto_value_traits | |
465 | > | |
466 | {}; | |
467 | ||
468 | //!This metafunction will obtain the type of a bucket pointer | |
469 | //!from the value_traits or hook option to be used with | |
470 | //!a hash container. | |
471 | template<class ValueTraitsOrHookOption> | |
472 | struct unordered_bucket_ptr | |
473 | : public detail::unordered_bucket_ptr_impl | |
474 | <typename ValueTraitsOrHookOption:: | |
475 | template pack<empty>::proto_value_traits | |
476 | > | |
477 | {}; | |
478 | ||
479 | //!This metafunction will obtain the type of the default bucket traits | |
480 | //!(when the user does not specify the bucket_traits<> option) from the | |
481 | //!value_traits or hook option to be used with | |
482 | //!a hash container. | |
483 | template<class ValueTraitsOrHookOption> | |
484 | struct unordered_default_bucket_traits | |
485 | { | |
486 | typedef typename ValueTraitsOrHookOption:: | |
487 | template pack<empty>::proto_value_traits supposed_value_traits; | |
488 | typedef typename detail:: | |
489 | get_slist_impl_from_supposed_value_traits | |
490 | <supposed_value_traits>::type slist_impl; | |
491 | typedef detail::bucket_traits_impl | |
492 | <slist_impl> implementation_defined; | |
493 | typedef implementation_defined type; | |
494 | }; | |
495 | ||
496 | struct default_bucket_traits; | |
497 | ||
498 | //hashtable default hook traits | |
499 | struct default_hashtable_hook_applier | |
500 | { template <class T> struct apply{ typedef typename T::default_hashtable_hook type; }; }; | |
501 | ||
502 | template<> | |
503 | struct is_default_hook_tag<default_hashtable_hook_applier> | |
504 | { static const bool value = true; }; | |
505 | ||
506 | struct hashtable_defaults | |
507 | { | |
508 | typedef default_hashtable_hook_applier proto_value_traits; | |
509 | typedef std::size_t size_type; | |
510 | typedef void key_of_value; | |
511 | typedef void equal; | |
512 | typedef void hash; | |
513 | typedef default_bucket_traits bucket_traits; | |
514 | static const bool constant_time_size = true; | |
515 | static const bool power_2_buckets = false; | |
516 | static const bool cache_begin = false; | |
517 | static const bool compare_hash = false; | |
518 | static const bool incremental = false; | |
519 | }; | |
520 | ||
521 | template<class ValueTraits, bool IsConst> | |
522 | struct downcast_node_to_value_t | |
523 | : public detail::node_to_value<ValueTraits, IsConst> | |
524 | { | |
525 | typedef detail::node_to_value<ValueTraits, IsConst> base_t; | |
526 | typedef typename base_t::result_type result_type; | |
527 | typedef ValueTraits value_traits; | |
528 | typedef typename detail::get_slist_impl | |
529 | <typename detail::reduced_slist_node_traits | |
530 | <typename value_traits::node_traits>::type | |
531 | >::type slist_impl; | |
532 | typedef typename detail::add_const_if_c | |
533 | <typename slist_impl::node, IsConst>::type & first_argument_type; | |
534 | typedef typename detail::add_const_if_c | |
535 | < typename ValueTraits::node_traits::node | |
536 | , IsConst>::type & intermediate_argument_type; | |
537 | typedef typename pointer_traits | |
538 | <typename ValueTraits::pointer>:: | |
539 | template rebind_pointer | |
540 | <const ValueTraits>::type const_value_traits_ptr; | |
541 | ||
542 | BOOST_INTRUSIVE_FORCEINLINE downcast_node_to_value_t(const const_value_traits_ptr &ptr) | |
543 | : base_t(ptr) | |
544 | {} | |
545 | ||
546 | BOOST_INTRUSIVE_FORCEINLINE result_type operator()(first_argument_type arg) const | |
547 | { return this->base_t::operator()(static_cast<intermediate_argument_type>(arg)); } | |
548 | }; | |
549 | ||
550 | template<class F, class SlistNodePtr, class NodePtr> | |
551 | struct node_cast_adaptor | |
552 | //Use public inheritance to avoid MSVC bugs with closures | |
553 | : public detail::ebo_functor_holder<F> | |
554 | { | |
555 | typedef detail::ebo_functor_holder<F> base_t; | |
556 | ||
557 | typedef typename pointer_traits<SlistNodePtr>::element_type slist_node; | |
558 | typedef typename pointer_traits<NodePtr>::element_type node; | |
559 | ||
560 | template<class ConvertibleToF, class RealValuTraits> | |
561 | BOOST_INTRUSIVE_FORCEINLINE node_cast_adaptor(const ConvertibleToF &c2f, const RealValuTraits *traits) | |
562 | : base_t(base_t(c2f, traits)) | |
563 | {} | |
564 | ||
565 | BOOST_INTRUSIVE_FORCEINLINE typename base_t::node_ptr operator()(const slist_node &to_clone) | |
566 | { return base_t::operator()(static_cast<const node &>(to_clone)); } | |
567 | ||
568 | BOOST_INTRUSIVE_FORCEINLINE void operator()(SlistNodePtr to_clone) | |
569 | { | |
570 | base_t::operator()(pointer_traits<NodePtr>::pointer_to(static_cast<node &>(*to_clone))); | |
571 | } | |
572 | }; | |
573 | ||
574 | //bucket_plus_vtraits stores ValueTraits + BucketTraits | |
575 | //this data is needed by iterators to obtain the | |
576 | //value from the iterator and detect the bucket | |
577 | template<class ValueTraits, class BucketTraits> | |
578 | struct bucket_plus_vtraits | |
579 | { | |
580 | typedef BucketTraits bucket_traits; | |
581 | typedef ValueTraits value_traits; | |
582 | ||
583 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; | |
584 | ||
585 | typedef typename | |
586 | detail::get_slist_impl_from_supposed_value_traits | |
587 | <value_traits>::type slist_impl; | |
588 | typedef typename value_traits::node_traits node_traits; | |
589 | typedef unordered_group_adapter<node_traits> group_traits; | |
590 | typedef typename slist_impl::iterator siterator; | |
591 | typedef typename slist_impl::size_type size_type; | |
592 | typedef detail::bucket_impl<slist_impl> bucket_type; | |
593 | typedef detail::group_functions<node_traits> group_functions_t; | |
594 | typedef typename slist_impl::node_algorithms node_algorithms; | |
595 | typedef typename slist_impl::node_ptr slist_node_ptr; | |
596 | typedef typename node_traits::node_ptr node_ptr; | |
597 | typedef typename node_traits::node node; | |
598 | typedef typename value_traits::value_type value_type; | |
599 | typedef typename value_traits::pointer pointer; | |
600 | typedef typename value_traits::const_pointer const_pointer; | |
601 | typedef typename pointer_traits<pointer>::reference reference; | |
602 | typedef typename pointer_traits | |
603 | <const_pointer>::reference const_reference; | |
604 | typedef circular_slist_algorithms<group_traits> group_algorithms; | |
605 | typedef typename pointer_traits | |
606 | <typename value_traits::pointer>:: | |
607 | template rebind_pointer | |
608 | <const value_traits>::type const_value_traits_ptr; | |
609 | typedef typename pointer_traits | |
610 | <typename value_traits::pointer>:: | |
611 | template rebind_pointer | |
612 | <const bucket_plus_vtraits>::type const_bucket_value_traits_ptr; | |
613 | typedef typename detail::unordered_bucket_ptr_impl | |
614 | <value_traits>::type bucket_ptr; | |
615 | ||
616 | template<class BucketTraitsType> | |
617 | BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits) | |
618 | : data(val_traits, ::boost::forward<BucketTraitsType>(b_traits)) | |
619 | {} | |
620 | ||
621 | BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits & operator =(const bucket_plus_vtraits &x) | |
622 | { data.bucket_traits_ = x.data.bucket_traits_; return *this; } | |
623 | ||
624 | BOOST_INTRUSIVE_FORCEINLINE const_value_traits_ptr priv_value_traits_ptr() const | |
625 | { return pointer_traits<const_value_traits_ptr>::pointer_to(this->priv_value_traits()); } | |
626 | ||
627 | //bucket_value_traits | |
628 | // | |
629 | BOOST_INTRUSIVE_FORCEINLINE const bucket_plus_vtraits &get_bucket_value_traits() const | |
630 | { return *this; } | |
631 | ||
632 | BOOST_INTRUSIVE_FORCEINLINE bucket_plus_vtraits &get_bucket_value_traits() | |
633 | { return *this; } | |
634 | ||
635 | BOOST_INTRUSIVE_FORCEINLINE const_bucket_value_traits_ptr bucket_value_traits_ptr() const | |
636 | { return pointer_traits<const_bucket_value_traits_ptr>::pointer_to(this->get_bucket_value_traits()); } | |
637 | ||
638 | //value traits | |
639 | // | |
640 | BOOST_INTRUSIVE_FORCEINLINE const value_traits &priv_value_traits() const | |
641 | { return this->data; } | |
642 | ||
643 | BOOST_INTRUSIVE_FORCEINLINE value_traits &priv_value_traits() | |
644 | { return this->data; } | |
645 | ||
646 | //bucket_traits | |
647 | // | |
648 | BOOST_INTRUSIVE_FORCEINLINE const bucket_traits &priv_bucket_traits() const | |
649 | { return this->data.bucket_traits_; } | |
650 | ||
651 | BOOST_INTRUSIVE_FORCEINLINE bucket_traits &priv_bucket_traits() | |
652 | { return this->data.bucket_traits_; } | |
653 | ||
654 | //bucket operations | |
655 | BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_bucket_pointer() const | |
656 | { return this->priv_bucket_traits().bucket_begin(); } | |
657 | ||
658 | typename slist_impl::size_type priv_bucket_count() const | |
659 | { return this->priv_bucket_traits().bucket_count(); } | |
660 | ||
661 | BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_invalid_bucket() const | |
662 | { | |
663 | const bucket_traits &rbt = this->priv_bucket_traits(); | |
664 | return rbt.bucket_begin() + rbt.bucket_count(); | |
665 | } | |
666 | ||
667 | BOOST_INTRUSIVE_FORCEINLINE siterator priv_invalid_local_it() const | |
668 | { return this->priv_bucket_traits().bucket_begin()->before_begin(); } | |
669 | ||
670 | template<class NodeDisposer> | |
671 | static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::true_) //optimize multikey | |
672 | { | |
673 | size_type n = 0; | |
674 | siterator const sfirst(++siterator(sbefore_first)); | |
675 | if(sfirst != slast){ | |
676 | node_ptr const nf = detail::dcast_bucket_ptr<node>(sfirst.pointed_node()); | |
677 | node_ptr const nl = detail::dcast_bucket_ptr<node>(slast.pointed_node()); | |
678 | node_ptr const ne = detail::dcast_bucket_ptr<node>(b.end().pointed_node()); | |
679 | ||
680 | if(group_functions_t::next_group_if_first_in_group(nf) != nf) { | |
681 | // The node is at the beginning of a group. | |
682 | if(nl != ne){ | |
683 | group_functions_t::split_group(nl); | |
684 | } | |
685 | } | |
686 | else { | |
687 | node_ptr const group1 = group_functions_t::split_group(nf); | |
688 | if(nl != ne) { | |
689 | node_ptr const group2 = group_functions_t::split_group(ne); | |
690 | if(nf == group2) { //Both first and last in the same group | |
691 | //so join group1 and group2 | |
692 | node_ptr const end1 = group_traits::get_next(group1); | |
693 | node_ptr const end2 = group_traits::get_next(group2); | |
694 | group_traits::set_next(group1, end2); | |
695 | group_traits::set_next(group2, end1); | |
696 | } | |
697 | } | |
698 | } | |
699 | ||
700 | siterator it(++siterator(sbefore_first)); | |
701 | while(it != slast){ | |
702 | node_disposer((it++).pointed_node()); | |
703 | ++n; | |
704 | } | |
705 | b.erase_after(sbefore_first, slast); | |
706 | } | |
707 | return n; | |
708 | } | |
709 | ||
710 | template<class NodeDisposer> | |
711 | static size_type priv_erase_from_single_bucket(bucket_type &b, siterator sbefore_first, siterator slast, NodeDisposer node_disposer, detail::false_) //optimize multikey | |
712 | { | |
713 | size_type n = 0; | |
714 | siterator it(++siterator(sbefore_first)); | |
715 | while(it != slast){ | |
716 | node_disposer((it++).pointed_node()); | |
717 | ++n; | |
718 | } | |
719 | b.erase_after(sbefore_first, slast); | |
720 | return n; | |
721 | } | |
722 | ||
723 | template<class NodeDisposer> | |
724 | static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::true_) //optimize multikey | |
725 | { | |
726 | node_ptr const ne(detail::dcast_bucket_ptr<node>(b.end().pointed_node())); | |
727 | node_ptr n(detail::dcast_bucket_ptr<node>(i.pointed_node())); | |
728 | node_ptr pos = node_traits::get_next(group_traits::get_next(n)); | |
729 | node_ptr bn; | |
730 | node_ptr nn(node_traits::get_next(n)); | |
731 | ||
732 | if(pos != n) { | |
733 | //Node is the first of the group | |
734 | bn = group_functions_t::get_prev_to_first_in_group(ne, n); | |
735 | ||
736 | //Unlink the rest of the group if it's not the last node of its group | |
737 | if(nn != ne && group_traits::get_next(nn) == n){ | |
738 | group_algorithms::unlink_after(nn); | |
739 | } | |
740 | } | |
741 | else if(nn != ne && group_traits::get_next(nn) == n){ | |
742 | //Node is not the end of the group | |
743 | bn = group_traits::get_next(n); | |
744 | group_algorithms::unlink_after(nn); | |
745 | } | |
746 | else{ | |
747 | //Node is the end of the group | |
748 | bn = group_traits::get_next(n); | |
749 | node_ptr const x(group_algorithms::get_previous_node(n)); | |
750 | group_algorithms::unlink_after(x); | |
751 | } | |
752 | b.erase_after_and_dispose(bucket_type::s_iterator_to(*bn), node_disposer); | |
753 | } | |
754 | ||
755 | template<class NodeDisposer> | |
756 | BOOST_INTRUSIVE_FORCEINLINE static void priv_erase_node(bucket_type &b, siterator i, NodeDisposer node_disposer, detail::false_) //optimize multikey | |
757 | { b.erase_after_and_dispose(b.previous(i), node_disposer); } | |
758 | ||
759 | template<class NodeDisposer, bool OptimizeMultikey> | |
760 | size_type priv_erase_node_range( siterator const &before_first_it, size_type const first_bucket | |
761 | , siterator const &last_it, size_type const last_bucket | |
762 | , NodeDisposer node_disposer, detail::bool_<OptimizeMultikey> optimize_multikey_tag) | |
763 | { | |
764 | size_type num_erased(0); | |
765 | siterator last_step_before_it; | |
766 | if(first_bucket != last_bucket){ | |
767 | bucket_type *b = (&this->priv_bucket_pointer()[0]); | |
768 | num_erased += this->priv_erase_from_single_bucket | |
769 | (b[first_bucket], before_first_it, b[first_bucket].end(), node_disposer, optimize_multikey_tag); | |
770 | for(size_type i = 0, n = (last_bucket - first_bucket - 1); i != n; ++i){ | |
771 | num_erased += this->priv_erase_whole_bucket(b[first_bucket+i+1], node_disposer); | |
772 | } | |
773 | last_step_before_it = b[last_bucket].before_begin(); | |
774 | } | |
775 | else{ | |
776 | last_step_before_it = before_first_it; | |
777 | } | |
778 | num_erased += this->priv_erase_from_single_bucket | |
779 | (this->priv_bucket_pointer()[last_bucket], last_step_before_it, last_it, node_disposer, optimize_multikey_tag); | |
780 | return num_erased; | |
781 | } | |
782 | ||
783 | static siterator priv_get_last(bucket_type &b, detail::true_) //optimize multikey | |
784 | { | |
785 | //First find the last node of p's group. | |
786 | //This requires checking the first node of the next group or | |
787 | //the bucket node. | |
788 | slist_node_ptr end_ptr(b.end().pointed_node()); | |
789 | node_ptr possible_end(node_traits::get_next( detail::dcast_bucket_ptr<node>(end_ptr))); | |
790 | node_ptr last_node_group(possible_end); | |
791 | ||
792 | while(end_ptr != possible_end){ | |
793 | last_node_group = group_traits::get_next(detail::dcast_bucket_ptr<node>(possible_end)); | |
794 | possible_end = node_traits::get_next(last_node_group); | |
795 | } | |
796 | return bucket_type::s_iterator_to(*last_node_group); | |
797 | } | |
798 | ||
799 | template<class NodeDisposer> | |
800 | size_type priv_erase_whole_bucket(bucket_type &b, NodeDisposer node_disposer) | |
801 | { | |
802 | size_type num_erased = 0; | |
803 | siterator b_begin(b.before_begin()); | |
804 | siterator nxt(b_begin); | |
805 | ++nxt; | |
806 | siterator const end_sit(b.end()); | |
807 | while(nxt != end_sit){ | |
808 | //No need to init group links as we'll delete all bucket nodes | |
809 | nxt = bucket_type::s_erase_after_and_dispose(b_begin, node_disposer); | |
810 | ++num_erased; | |
811 | } | |
812 | return num_erased; | |
813 | } | |
814 | ||
815 | BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_last(bucket_type &b, detail::false_) //NOT optimize multikey | |
816 | { return b.previous(b.end()); } | |
817 | ||
818 | static siterator priv_get_previous(bucket_type &b, siterator i, detail::true_) //optimize multikey | |
819 | { | |
820 | node_ptr const elem(detail::dcast_bucket_ptr<node>(i.pointed_node())); | |
821 | node_ptr const prev_in_group(group_traits::get_next(elem)); | |
822 | bool const first_in_group = node_traits::get_next(prev_in_group) != elem; | |
823 | typename bucket_type::node &n = first_in_group | |
824 | ? *group_functions_t::get_prev_to_first_in_group(b.end().pointed_node(), elem) | |
825 | : *group_traits::get_next(elem) | |
826 | ; | |
827 | return bucket_type::s_iterator_to(n); | |
828 | } | |
829 | ||
830 | BOOST_INTRUSIVE_FORCEINLINE static siterator priv_get_previous(bucket_type &b, siterator i, detail::false_) //NOT optimize multikey | |
831 | { return b.previous(i); } | |
832 | ||
833 | std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::true_) //optimize multikey | |
834 | { | |
835 | const bucket_ptr f(this->priv_bucket_pointer()), l(f + this->priv_bucket_count() - 1); | |
836 | slist_node_ptr bb = group_functions_t::get_bucket_before_begin | |
837 | ( f->end().pointed_node() | |
838 | , l->end().pointed_node() | |
839 | , detail::dcast_bucket_ptr<node>(it.pointed_node())); | |
840 | //Now get the bucket_impl from the iterator | |
841 | const bucket_type &b = static_cast<const bucket_type&> | |
842 | (bucket_type::slist_type::container_from_end_iterator(bucket_type::s_iterator_to(*bb))); | |
843 | //Now just calculate the index b has in the bucket array | |
844 | return static_cast<size_type>(&b - &*f); | |
845 | } | |
846 | ||
847 | std::size_t priv_get_bucket_num_no_hash_store(siterator it, detail::false_) //NO optimize multikey | |
848 | { | |
849 | bucket_ptr f(this->priv_bucket_pointer()), l(f + this->priv_bucket_count() - 1); | |
850 | slist_node_ptr first_ptr(f->cend().pointed_node()) | |
851 | , last_ptr(l->cend().pointed_node()); | |
852 | ||
853 | //The end node is embedded in the singly linked list: | |
854 | //iterate until we reach it. | |
855 | while(!(first_ptr <= it.pointed_node() && it.pointed_node() <= last_ptr)){ | |
856 | ++it; | |
857 | } | |
858 | //Now get the bucket_impl from the iterator | |
859 | const bucket_type &b = static_cast<const bucket_type&> | |
860 | (bucket_type::container_from_end_iterator(it)); | |
861 | ||
862 | //Now just calculate the index b has in the bucket array | |
863 | return static_cast<std::size_t>(&b - &*f); | |
864 | } | |
865 | ||
866 | BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_) //store_hash | |
867 | { return node_traits::get_hash(detail::dcast_bucket_ptr<node>(n)); } | |
868 | ||
869 | BOOST_INTRUSIVE_FORCEINLINE static std::size_t priv_stored_hash(slist_node_ptr, detail::false_) //NO store_hash | |
870 | { return std::size_t(-1); } | |
871 | ||
872 | BOOST_INTRUSIVE_FORCEINLINE node &priv_value_to_node(reference v) | |
873 | { return *this->priv_value_traits().to_node_ptr(v); } | |
874 | ||
875 | BOOST_INTRUSIVE_FORCEINLINE const node &priv_value_to_node(const_reference v) const | |
876 | { return *this->priv_value_traits().to_node_ptr(v); } | |
877 | ||
878 | BOOST_INTRUSIVE_FORCEINLINE reference priv_value_from_slist_node(slist_node_ptr n) | |
879 | { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); } | |
880 | ||
881 | BOOST_INTRUSIVE_FORCEINLINE const_reference priv_value_from_slist_node(slist_node_ptr n) const | |
882 | { return *this->priv_value_traits().to_value_ptr(detail::dcast_bucket_ptr<node>(n)); } | |
883 | ||
884 | void priv_clear_buckets(const bucket_ptr buckets_ptr, const size_type bucket_cnt) | |
885 | { | |
886 | bucket_ptr buckets_it = buckets_ptr; | |
887 | for(size_type bucket_i = 0; bucket_i != bucket_cnt; ++buckets_it, ++bucket_i){ | |
888 | if(safemode_or_autounlink){ | |
889 | buckets_it->clear_and_dispose(detail::init_disposer<node_algorithms>()); | |
890 | } | |
891 | else{ | |
892 | buckets_it->clear(); | |
893 | } | |
894 | } | |
895 | } | |
896 | ||
897 | BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::true_) const //For store_hash == true | |
898 | { return node_traits::get_hash(this->priv_value_traits().to_node_ptr(v)); } | |
899 | ||
900 | typedef hashtable_iterator<bucket_plus_vtraits, false> iterator; | |
901 | typedef hashtable_iterator<bucket_plus_vtraits, true> const_iterator; | |
902 | ||
903 | BOOST_INTRUSIVE_FORCEINLINE iterator end() | |
904 | { return iterator(this->priv_invalid_local_it(), 0); } | |
905 | ||
906 | BOOST_INTRUSIVE_FORCEINLINE const_iterator end() const | |
907 | { return this->cend(); } | |
908 | ||
909 | BOOST_INTRUSIVE_FORCEINLINE const_iterator cend() const | |
910 | { return const_iterator(this->priv_invalid_local_it(), 0); } | |
911 | ||
912 | static size_type suggested_upper_bucket_count(size_type n) | |
913 | { | |
914 | const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; | |
915 | const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; | |
916 | std::size_t const* bound = std::lower_bound(primes, primes_end, n); | |
917 | bound -= (bound == primes_end); | |
918 | return size_type(*bound); | |
919 | } | |
920 | ||
921 | static size_type suggested_lower_bucket_count(size_type n) | |
922 | { | |
923 | const std::size_t *primes = &prime_list_holder<0>::prime_list[0]; | |
924 | const std::size_t *primes_end = primes + prime_list_holder<0>::prime_list_size; | |
925 | size_type const* bound = std::upper_bound(primes, primes_end, n); | |
926 | bound -= (bound != primes); | |
927 | return size_type(*bound); | |
928 | } | |
929 | ||
930 | //Public functions: | |
931 | struct data_type : public ValueTraits | |
932 | { | |
933 | template<class BucketTraitsType> | |
934 | BOOST_INTRUSIVE_FORCEINLINE data_type(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits) | |
935 | : ValueTraits(val_traits), bucket_traits_(::boost::forward<BucketTraitsType>(b_traits)) | |
936 | {} | |
937 | ||
938 | bucket_traits bucket_traits_; | |
939 | } data; | |
940 | }; | |
941 | ||
942 | template<class Hash, class> | |
943 | struct get_hash | |
944 | { | |
945 | typedef Hash type; | |
946 | }; | |
947 | ||
948 | template<class T> | |
949 | struct get_hash<void, T> | |
950 | { | |
951 | typedef ::boost::hash<T> type; | |
952 | }; | |
953 | ||
954 | template<class EqualTo, class> | |
955 | struct get_equal_to | |
956 | { | |
957 | typedef EqualTo type; | |
958 | }; | |
959 | ||
960 | template<class T> | |
961 | struct get_equal_to<void, T> | |
962 | { | |
963 | typedef std::equal_to<T> type; | |
964 | }; | |
965 | ||
966 | template<class KeyOfValue, class T> | |
967 | struct get_hash_key_of_value | |
968 | { | |
969 | typedef KeyOfValue type; | |
970 | }; | |
971 | ||
972 | template<class T> | |
973 | struct get_hash_key_of_value<void, T> | |
974 | { | |
975 | typedef ::boost::intrusive::detail::identity<T> type; | |
976 | }; | |
977 | ||
978 | template<class T, class VoidOrKeyOfValue> | |
979 | struct hash_key_types_base | |
980 | { | |
981 | typedef typename get_hash_key_of_value | |
982 | < VoidOrKeyOfValue, T>::type key_of_value; | |
983 | typedef typename key_of_value::type key_type; | |
984 | }; | |
985 | ||
986 | template<class T, class VoidOrKeyOfValue, class VoidOrKeyHash> | |
987 | struct hash_key_hash | |
988 | : get_hash | |
989 | < VoidOrKeyHash | |
990 | , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type | |
991 | > | |
992 | {}; | |
993 | ||
994 | template<class T, class VoidOrKeyOfValue, class VoidOrKeyEqual> | |
995 | struct hash_key_equal | |
996 | : get_equal_to | |
997 | < VoidOrKeyEqual | |
998 | , typename hash_key_types_base<T, VoidOrKeyOfValue>::key_type | |
999 | > | |
1000 | ||
1001 | {}; | |
1002 | ||
1003 | //bucket_hash_t | |
1004 | //Stores bucket_plus_vtraits plust the hash function | |
1005 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class BucketTraits> | |
1006 | struct bucket_hash_t | |
1007 | //Use public inheritance to avoid MSVC bugs with closures | |
1008 | : public detail::ebo_functor_holder | |
1009 | <typename hash_key_hash < typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits::value_type | |
1010 | , VoidOrKeyOfValue | |
1011 | , VoidOrKeyHash | |
1012 | >::type | |
1013 | > | |
1014 | , bucket_plus_vtraits<ValueTraits, BucketTraits> //4 | |
1015 | { | |
1016 | typedef typename bucket_plus_vtraits<ValueTraits,BucketTraits>::value_traits value_traits; | |
1017 | typedef typename value_traits::value_type value_type; | |
1018 | typedef typename value_traits::node_traits node_traits; | |
1019 | typedef hash_key_hash | |
1020 | < value_type, VoidOrKeyOfValue, VoidOrKeyHash> hash_key_hash_t; | |
1021 | typedef typename hash_key_hash_t::type hasher; | |
1022 | typedef typename hash_key_types_base<value_type, VoidOrKeyOfValue>::key_of_value key_of_value; | |
1023 | ||
1024 | typedef BucketTraits bucket_traits; | |
1025 | typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t; | |
1026 | typedef detail::ebo_functor_holder<hasher> base_t; | |
1027 | ||
1028 | template<class BucketTraitsType> | |
1029 | BOOST_INTRUSIVE_FORCEINLINE bucket_hash_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h) | |
1030 | : detail::ebo_functor_holder<hasher>(h), bucket_plus_vtraits_t(val_traits, ::boost::forward<BucketTraitsType>(b_traits)) | |
1031 | {} | |
1032 | ||
1033 | BOOST_INTRUSIVE_FORCEINLINE const hasher &priv_hasher() const | |
1034 | { return this->base_t::get(); } | |
1035 | ||
1036 | hasher &priv_hasher() | |
1037 | { return this->base_t::get(); } | |
1038 | ||
1039 | using bucket_plus_vtraits_t::priv_stored_or_compute_hash; //For store_hash == true | |
1040 | ||
1041 | BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_stored_or_compute_hash(const value_type &v, detail::false_) const //For store_hash == false | |
1042 | { return this->priv_hasher()(key_of_value()(v)); } | |
1043 | }; | |
1044 | ||
1045 | template<class ValueTraits, class BucketTraits, class VoidOrKeyOfValue, class VoidOrKeyEqual> | |
1046 | struct hashtable_equal_holder | |
1047 | { | |
1048 | typedef detail::ebo_functor_holder | |
1049 | < typename hash_key_equal < typename bucket_plus_vtraits<ValueTraits, BucketTraits>::value_traits::value_type | |
1050 | , VoidOrKeyOfValue | |
1051 | , VoidOrKeyEqual | |
1052 | >::type | |
1053 | > type; | |
1054 | }; | |
1055 | ||
1056 | ||
1057 | //bucket_hash_equal_t | |
1058 | //Stores bucket_hash_t and the equality function when the first | |
1059 | //non-empty bucket shall not be cached. | |
1060 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, bool> | |
1061 | struct bucket_hash_equal_t | |
1062 | //Use public inheritance to avoid MSVC bugs with closures | |
1063 | : public bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //3 | |
1064 | , public hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type //equal | |
1065 | { | |
1066 | typedef typename hashtable_equal_holder | |
1067 | <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t; | |
1068 | typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type; | |
1069 | typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; | |
1070 | typedef ValueTraits value_traits; | |
1071 | typedef typename equal_holder_t::functor_type key_equal; | |
1072 | typedef typename bucket_hash_type::hasher hasher; | |
1073 | typedef BucketTraits bucket_traits; | |
1074 | typedef typename bucket_plus_vtraits_t::slist_impl slist_impl; | |
1075 | typedef typename slist_impl::size_type size_type; | |
1076 | typedef typename slist_impl::iterator siterator; | |
1077 | typedef detail::bucket_impl<slist_impl> bucket_type; | |
1078 | typedef typename detail::unordered_bucket_ptr_impl<value_traits>::type bucket_ptr; | |
1079 | ||
1080 | template<class BucketTraitsType> | |
1081 | bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e) | |
1082 | : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) | |
1083 | , equal_holder_t(e) | |
1084 | {} | |
1085 | ||
1086 | BOOST_INTRUSIVE_FORCEINLINE bucket_ptr priv_get_cache() | |
1087 | { return this->bucket_hash_type::priv_bucket_pointer(); } | |
1088 | ||
1089 | BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &) | |
1090 | {} | |
1091 | ||
1092 | BOOST_INTRUSIVE_FORCEINLINE size_type priv_get_cache_bucket_num() | |
1093 | { return 0u; } | |
1094 | ||
1095 | BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache() | |
1096 | {} | |
1097 | ||
1098 | BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &) | |
1099 | {} | |
1100 | ||
1101 | siterator priv_begin() const | |
1102 | { | |
1103 | size_type n = 0; | |
1104 | size_type bucket_cnt = this->bucket_hash_type::priv_bucket_count(); | |
1105 | for (n = 0; n < bucket_cnt; ++n){ | |
1106 | bucket_type &b = this->bucket_hash_type::priv_bucket_pointer()[n]; | |
1107 | if(!b.empty()){ | |
1108 | return b.begin(); | |
1109 | } | |
1110 | } | |
1111 | return this->bucket_hash_type::priv_invalid_local_it(); | |
1112 | } | |
1113 | ||
1114 | BOOST_INTRUSIVE_FORCEINLINE void priv_insertion_update_cache(size_type) | |
1115 | {} | |
1116 | ||
1117 | BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache_range(size_type, size_type) | |
1118 | {} | |
1119 | ||
1120 | BOOST_INTRUSIVE_FORCEINLINE void priv_erasure_update_cache() | |
1121 | {} | |
1122 | ||
1123 | BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const | |
1124 | { return this->equal_holder_t::get(); } | |
1125 | ||
1126 | BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal() | |
1127 | { return this->equal_holder_t::get(); } | |
1128 | }; | |
1129 | ||
1130 | //bucket_hash_equal_t | |
1131 | //Stores bucket_hash_t and the equality function when the first | |
1132 | //non-empty bucket shall be cached. | |
1133 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits> //cache_begin == true version | |
1134 | struct bucket_hash_equal_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual, BucketTraits, true> | |
1135 | //Use public inheritance to avoid MSVC bugs with closures | |
1136 | : bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> //2 | |
1137 | , hashtable_equal_holder<ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type | |
1138 | { | |
1139 | typedef typename hashtable_equal_holder | |
1140 | <ValueTraits, BucketTraits, VoidOrKeyOfValue, VoidOrKeyEqual>::type equal_holder_t; | |
1141 | ||
1142 | typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; | |
1143 | typedef ValueTraits value_traits; | |
1144 | typedef typename equal_holder_t::functor_type key_equal; | |
1145 | typedef bucket_hash_t<ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, BucketTraits> bucket_hash_type; | |
1146 | typedef typename bucket_hash_type::hasher hasher; | |
1147 | typedef BucketTraits bucket_traits; | |
1148 | typedef typename bucket_plus_vtraits_t::slist_impl::size_type size_type; | |
1149 | typedef typename bucket_plus_vtraits_t::slist_impl::iterator siterator; | |
1150 | ||
1151 | template<class BucketTraitsType> | |
1152 | bucket_hash_equal_t(const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits, const hasher & h, const key_equal &e) | |
1153 | : bucket_hash_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h) | |
1154 | , equal_holder_t(e) | |
1155 | {} | |
1156 | ||
1157 | typedef typename detail::unordered_bucket_ptr_impl | |
1158 | <typename bucket_hash_type::value_traits>::type bucket_ptr; | |
1159 | ||
1160 | BOOST_INTRUSIVE_FORCEINLINE bucket_ptr &priv_get_cache() | |
1161 | { return cached_begin_; } | |
1162 | ||
1163 | BOOST_INTRUSIVE_FORCEINLINE const bucket_ptr &priv_get_cache() const | |
1164 | { return cached_begin_; } | |
1165 | ||
1166 | BOOST_INTRUSIVE_FORCEINLINE void priv_set_cache(const bucket_ptr &p) | |
1167 | { cached_begin_ = p; } | |
1168 | ||
1169 | BOOST_INTRUSIVE_FORCEINLINE std::size_t priv_get_cache_bucket_num() | |
1170 | { return this->cached_begin_ - this->bucket_hash_type::priv_bucket_pointer(); } | |
1171 | ||
1172 | BOOST_INTRUSIVE_FORCEINLINE void priv_initialize_cache() | |
1173 | { this->cached_begin_ = this->bucket_hash_type::priv_invalid_bucket(); } | |
1174 | ||
1175 | BOOST_INTRUSIVE_FORCEINLINE void priv_swap_cache(bucket_hash_equal_t &other) | |
1176 | { | |
1177 | ::boost::adl_move_swap(this->cached_begin_, other.cached_begin_); | |
1178 | } | |
1179 | ||
1180 | siterator priv_begin() const | |
1181 | { | |
1182 | if(this->cached_begin_ == this->bucket_hash_type::priv_invalid_bucket()){ | |
1183 | return this->bucket_hash_type::priv_invalid_local_it(); | |
1184 | } | |
1185 | else{ | |
1186 | return this->cached_begin_->begin(); | |
1187 | } | |
1188 | } | |
1189 | ||
1190 | void priv_insertion_update_cache(size_type insertion_bucket) | |
1191 | { | |
1192 | bucket_ptr p = this->bucket_hash_type::priv_bucket_pointer() + insertion_bucket; | |
1193 | if(p < this->cached_begin_){ | |
1194 | this->cached_begin_ = p; | |
1195 | } | |
1196 | } | |
1197 | ||
1198 | BOOST_INTRUSIVE_FORCEINLINE const key_equal &priv_equal() const | |
1199 | { return this->equal_holder_t::get(); } | |
1200 | ||
1201 | BOOST_INTRUSIVE_FORCEINLINE key_equal &priv_equal() | |
1202 | { return this->equal_holder_t::get(); } | |
1203 | ||
1204 | void priv_erasure_update_cache_range(size_type first_bucket_num, size_type last_bucket_num) | |
1205 | { | |
1206 | //If the last bucket is the end, the cache must be updated | |
1207 | //to the last position if all | |
1208 | if(this->priv_get_cache_bucket_num() == first_bucket_num && | |
1209 | this->bucket_hash_type::priv_bucket_pointer()[first_bucket_num].empty() ){ | |
1210 | this->priv_set_cache(this->bucket_hash_type::priv_bucket_pointer() + last_bucket_num); | |
1211 | this->priv_erasure_update_cache(); | |
1212 | } | |
1213 | } | |
1214 | ||
1215 | void priv_erasure_update_cache() | |
1216 | { | |
1217 | if(this->cached_begin_ != this->bucket_hash_type::priv_invalid_bucket()){ | |
1218 | size_type current_n = this->priv_get_cache() - this->bucket_hash_type::priv_bucket_pointer(); | |
1219 | for( const size_type num_buckets = this->bucket_hash_type::priv_bucket_count() | |
1220 | ; current_n < num_buckets | |
1221 | ; ++current_n, ++this->priv_get_cache()){ | |
1222 | if(!this->priv_get_cache()->empty()){ | |
1223 | return; | |
1224 | } | |
1225 | } | |
1226 | this->priv_initialize_cache(); | |
1227 | } | |
1228 | } | |
1229 | ||
1230 | bucket_ptr cached_begin_; | |
1231 | }; | |
1232 | ||
1233 | //This wrapper around size_traits is used | |
1234 | //to maintain minimal container size with compilers like MSVC | |
1235 | //that have problems with EBO and multiple empty base classes | |
1236 | template<class DeriveFrom, class SizeType, bool> | |
1237 | struct hashtable_size_traits_wrapper | |
1238 | : public DeriveFrom | |
1239 | { | |
1240 | template<class Base, class Arg0, class Arg1, class Arg2> | |
1241 | hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0 | |
1242 | , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2) | |
1243 | : DeriveFrom(::boost::forward<Base>(base) | |
1244 | , ::boost::forward<Arg0>(arg0) | |
1245 | , ::boost::forward<Arg1>(arg1) | |
1246 | , ::boost::forward<Arg2>(arg2)) | |
1247 | {} | |
1248 | typedef detail::size_holder < true, SizeType> size_traits;//size_traits | |
1249 | ||
1250 | size_traits size_traits_; | |
1251 | ||
1252 | typedef const size_traits & size_traits_const_t; | |
1253 | typedef size_traits & size_traits_t; | |
1254 | ||
1255 | BOOST_INTRUSIVE_FORCEINLINE size_traits_const_t priv_size_traits() const | |
1256 | { return size_traits_; } | |
1257 | ||
1258 | BOOST_INTRUSIVE_FORCEINLINE size_traits_t priv_size_traits() | |
1259 | { return size_traits_; } | |
1260 | }; | |
1261 | ||
1262 | template<class DeriveFrom, class SizeType> | |
1263 | struct hashtable_size_traits_wrapper<DeriveFrom, SizeType, false> | |
1264 | : public DeriveFrom | |
1265 | { | |
1266 | template<class Base, class Arg0, class Arg1, class Arg2> | |
1267 | hashtable_size_traits_wrapper( BOOST_FWD_REF(Base) base, BOOST_FWD_REF(Arg0) arg0 | |
1268 | , BOOST_FWD_REF(Arg1) arg1, BOOST_FWD_REF(Arg2) arg2) | |
1269 | : DeriveFrom(::boost::forward<Base>(base) | |
1270 | , ::boost::forward<Arg0>(arg0) | |
1271 | , ::boost::forward<Arg1>(arg1) | |
1272 | , ::boost::forward<Arg2>(arg2)) | |
1273 | {} | |
1274 | ||
1275 | typedef detail::size_holder< false, SizeType> size_traits; | |
1276 | ||
1277 | typedef size_traits size_traits_const_t; | |
1278 | typedef size_traits size_traits_t; | |
1279 | ||
1280 | BOOST_INTRUSIVE_FORCEINLINE size_traits priv_size_traits() const | |
1281 | { return size_traits(); } | |
1282 | }; | |
1283 | ||
1284 | //hashdata_internal | |
1285 | //Stores bucket_hash_equal_t and split_traits | |
1286 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags> | |
1287 | struct hashdata_internal | |
1288 | : public hashtable_size_traits_wrapper | |
1289 | < bucket_hash_equal_t | |
1290 | < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual | |
1291 | , BucketTraits | |
1292 | , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) | |
1293 | > //2 | |
1294 | , SizeType | |
1295 | , (BoolFlags & hash_bool_flags::incremental_pos) != 0 | |
1296 | > | |
1297 | { | |
1298 | typedef hashtable_size_traits_wrapper | |
1299 | < bucket_hash_equal_t | |
1300 | < ValueTraits, VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual | |
1301 | , BucketTraits | |
1302 | , 0 != (BoolFlags & hash_bool_flags::cache_begin_pos) | |
1303 | > //2 | |
1304 | , SizeType | |
1305 | , (BoolFlags & hash_bool_flags::incremental_pos) != 0 | |
1306 | > internal_type; | |
1307 | typedef typename internal_type::key_equal key_equal; | |
1308 | typedef typename internal_type::hasher hasher; | |
1309 | typedef bucket_plus_vtraits<ValueTraits,BucketTraits> bucket_plus_vtraits_t; | |
1310 | typedef typename bucket_plus_vtraits_t::size_type size_type; | |
1311 | typedef typename internal_type::size_traits split_traits; | |
1312 | typedef typename bucket_plus_vtraits_t::bucket_ptr bucket_ptr; | |
1313 | typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr; | |
1314 | typedef typename bucket_plus_vtraits_t::siterator siterator; | |
1315 | typedef typename bucket_plus_vtraits_t::bucket_traits bucket_traits; | |
1316 | typedef typename bucket_plus_vtraits_t::value_traits value_traits; | |
1317 | typedef typename bucket_plus_vtraits_t::bucket_type bucket_type; | |
1318 | typedef typename value_traits::value_type value_type; | |
1319 | typedef typename value_traits::pointer pointer; | |
1320 | typedef typename value_traits::const_pointer const_pointer; | |
1321 | typedef typename pointer_traits<pointer>::reference reference; | |
1322 | typedef typename pointer_traits | |
1323 | <const_pointer>::reference const_reference; | |
1324 | typedef typename value_traits::node_traits node_traits; | |
1325 | typedef typename node_traits::node node; | |
1326 | typedef typename node_traits::node_ptr node_ptr; | |
1327 | typedef typename node_traits::const_node_ptr const_node_ptr; | |
1328 | typedef detail::node_functions<node_traits> node_functions_t; | |
1329 | typedef typename detail::get_slist_impl | |
1330 | <typename detail::reduced_slist_node_traits | |
1331 | <typename value_traits::node_traits>::type | |
1332 | >::type slist_impl; | |
1333 | typedef typename slist_impl::node_algorithms node_algorithms; | |
1334 | typedef typename slist_impl::node_ptr slist_node_ptr; | |
1335 | ||
1336 | typedef hash_key_types_base | |
1337 | < typename ValueTraits::value_type | |
1338 | , VoidOrKeyOfValue | |
1339 | > hash_types_base; | |
1340 | typedef typename hash_types_base::key_of_value key_of_value; | |
1341 | ||
1342 | static const bool store_hash = detail::store_hash_is_true<node_traits>::value; | |
1343 | static const bool safemode_or_autounlink = is_safe_autounlink<value_traits::link_mode>::value; | |
1344 | static const bool stateful_value_traits = detail::is_stateful_value_traits<value_traits>::value; | |
1345 | ||
1346 | typedef detail::bool_<store_hash> store_hash_t; | |
1347 | ||
1348 | typedef detail::transform_iterator | |
1349 | < typename slist_impl::iterator | |
1350 | , downcast_node_to_value_t | |
1351 | < value_traits | |
1352 | , false> > local_iterator; | |
1353 | ||
1354 | typedef detail::transform_iterator | |
1355 | < typename slist_impl::iterator | |
1356 | , downcast_node_to_value_t | |
1357 | < value_traits | |
1358 | , true> > const_local_iterator; | |
1359 | // | |
1360 | ||
1361 | template<class BucketTraitsType> | |
1362 | hashdata_internal( const ValueTraits &val_traits, BOOST_FWD_REF(BucketTraitsType) b_traits | |
1363 | , const hasher & h, const key_equal &e) | |
1364 | : internal_type(val_traits, ::boost::forward<BucketTraitsType>(b_traits), h, e) | |
1365 | {} | |
1366 | ||
1367 | BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_t priv_split_traits() | |
1368 | { return this->priv_size_traits(); } | |
1369 | ||
1370 | BOOST_INTRUSIVE_FORCEINLINE typename internal_type::size_traits_const_t priv_split_traits() const | |
1371 | { return this->priv_size_traits(); } | |
1372 | ||
1373 | ~hashdata_internal() | |
1374 | { this->priv_clear_buckets(); } | |
1375 | ||
1376 | void priv_clear_buckets() | |
1377 | { | |
1378 | this->internal_type::priv_clear_buckets | |
1379 | ( this->priv_get_cache() | |
1380 | , this->internal_type::priv_bucket_count() | |
1381 | - (this->priv_get_cache() | |
1382 | - this->internal_type::priv_bucket_pointer())); | |
1383 | } | |
1384 | ||
1385 | void priv_clear_buckets_and_cache() | |
1386 | { | |
1387 | this->priv_clear_buckets(); | |
1388 | this->priv_initialize_cache(); | |
1389 | } | |
1390 | ||
1391 | void priv_initialize_buckets_and_cache() | |
1392 | { | |
1393 | this->internal_type::priv_clear_buckets | |
1394 | ( this->internal_type::priv_bucket_pointer() | |
1395 | , this->internal_type::priv_bucket_count()); | |
1396 | this->priv_initialize_cache(); | |
1397 | } | |
1398 | ||
1399 | typedef hashtable_iterator<bucket_plus_vtraits_t, false> iterator; | |
1400 | typedef hashtable_iterator<bucket_plus_vtraits_t, true> const_iterator; | |
1401 | ||
1402 | static std::size_t priv_stored_hash(slist_node_ptr n, detail::true_ true_value) | |
1403 | { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, true_value); } | |
1404 | ||
1405 | static std::size_t priv_stored_hash(slist_node_ptr n, detail::false_ false_value) | |
1406 | { return bucket_plus_vtraits<ValueTraits, BucketTraits>::priv_stored_hash(n, false_value); } | |
1407 | ||
1408 | //public functions | |
1409 | BOOST_INTRUSIVE_FORCEINLINE SizeType split_count() const | |
1410 | { | |
1411 | return this->priv_split_traits().get_size(); | |
1412 | } | |
1413 | ||
1414 | BOOST_INTRUSIVE_FORCEINLINE iterator iterator_to(reference value) | |
1415 | { | |
1416 | return iterator(bucket_type::s_iterator_to | |
1417 | (this->priv_value_to_node(value)), &this->get_bucket_value_traits()); | |
1418 | } | |
1419 | ||
1420 | const_iterator iterator_to(const_reference value) const | |
1421 | { | |
1422 | siterator const sit = bucket_type::s_iterator_to | |
1423 | ( *pointer_traits<node_ptr>::const_cast_from | |
1424 | (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))) | |
1425 | ); | |
1426 | return const_iterator(sit, &this->get_bucket_value_traits()); | |
1427 | } | |
1428 | ||
1429 | static local_iterator s_local_iterator_to(reference value) | |
1430 | { | |
1431 | BOOST_STATIC_ASSERT((!stateful_value_traits)); | |
1432 | siterator sit = bucket_type::s_iterator_to(*value_traits::to_node_ptr(value)); | |
1433 | return local_iterator(sit, const_value_traits_ptr()); | |
1434 | } | |
1435 | ||
1436 | static const_local_iterator s_local_iterator_to(const_reference value) | |
1437 | { | |
1438 | BOOST_STATIC_ASSERT((!stateful_value_traits)); | |
1439 | siterator const sit = bucket_type::s_iterator_to | |
1440 | ( *pointer_traits<node_ptr>::const_cast_from | |
1441 | (value_traits::to_node_ptr(value)) | |
1442 | ); | |
1443 | return const_local_iterator(sit, const_value_traits_ptr()); | |
1444 | } | |
1445 | ||
1446 | local_iterator local_iterator_to(reference value) | |
1447 | { | |
1448 | siterator sit = bucket_type::s_iterator_to(this->priv_value_to_node(value)); | |
1449 | return local_iterator(sit, this->priv_value_traits_ptr()); | |
1450 | } | |
1451 | ||
1452 | const_local_iterator local_iterator_to(const_reference value) const | |
1453 | { | |
1454 | siterator sit = bucket_type::s_iterator_to | |
1455 | ( *pointer_traits<node_ptr>::const_cast_from | |
1456 | (pointer_traits<const_node_ptr>::pointer_to(this->priv_value_to_node(value))) | |
1457 | ); | |
1458 | return const_local_iterator(sit, this->priv_value_traits_ptr()); | |
1459 | } | |
1460 | ||
1461 | BOOST_INTRUSIVE_FORCEINLINE size_type bucket_count() const | |
1462 | { return this->priv_bucket_count(); } | |
1463 | ||
1464 | BOOST_INTRUSIVE_FORCEINLINE size_type bucket_size(size_type n) const | |
1465 | { return this->priv_bucket_pointer()[n].size(); } | |
1466 | ||
1467 | BOOST_INTRUSIVE_FORCEINLINE bucket_ptr bucket_pointer() const | |
1468 | { return this->priv_bucket_pointer(); } | |
1469 | ||
1470 | BOOST_INTRUSIVE_FORCEINLINE local_iterator begin(size_type n) | |
1471 | { return local_iterator(this->priv_bucket_pointer()[n].begin(), this->priv_value_traits_ptr()); } | |
1472 | ||
1473 | BOOST_INTRUSIVE_FORCEINLINE const_local_iterator begin(size_type n) const | |
1474 | { return this->cbegin(n); } | |
1475 | ||
1476 | const_local_iterator cbegin(size_type n) const | |
1477 | { | |
1478 | return const_local_iterator | |
1479 | ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].begin() | |
1480 | , this->priv_value_traits_ptr()); | |
1481 | } | |
1482 | ||
1483 | using internal_type::end; | |
1484 | using internal_type::cend; | |
1485 | local_iterator end(size_type n) | |
1486 | { return local_iterator(this->priv_bucket_pointer()[n].end(), this->priv_value_traits_ptr()); } | |
1487 | ||
1488 | BOOST_INTRUSIVE_FORCEINLINE const_local_iterator end(size_type n) const | |
1489 | { return this->cend(n); } | |
1490 | ||
1491 | const_local_iterator cend(size_type n) const | |
1492 | { | |
1493 | return const_local_iterator | |
1494 | ( pointer_traits<bucket_ptr>::const_cast_from(this->priv_bucket_pointer())[n].end() | |
1495 | , this->priv_value_traits_ptr()); | |
1496 | } | |
1497 | ||
1498 | //Public functions for hashtable_impl | |
1499 | ||
1500 | BOOST_INTRUSIVE_FORCEINLINE iterator begin() | |
1501 | { return iterator(this->priv_begin(), &this->get_bucket_value_traits()); } | |
1502 | ||
1503 | BOOST_INTRUSIVE_FORCEINLINE const_iterator begin() const | |
1504 | { return this->cbegin(); } | |
1505 | ||
1506 | BOOST_INTRUSIVE_FORCEINLINE const_iterator cbegin() const | |
1507 | { return const_iterator(this->priv_begin(), &this->get_bucket_value_traits()); } | |
1508 | ||
1509 | BOOST_INTRUSIVE_FORCEINLINE hasher hash_function() const | |
1510 | { return this->priv_hasher(); } | |
1511 | ||
1512 | BOOST_INTRUSIVE_FORCEINLINE key_equal key_eq() const | |
1513 | { return this->priv_equal(); } | |
1514 | }; | |
1515 | ||
1516 | /// @endcond | |
1517 | ||
1518 | //! The class template hashtable is an intrusive hash table container, that | |
1519 | //! is used to construct intrusive unordered_set and unordered_multiset containers. The | |
1520 | //! no-throw guarantee holds only, if the VoidOrKeyEqual object and Hasher don't throw. | |
1521 | //! | |
1522 | //! hashtable is a semi-intrusive container: each object to be stored in the | |
1523 | //! container must contain a proper hook, but the container also needs | |
1524 | //! additional auxiliary memory to work: hashtable needs a pointer to an array | |
1525 | //! of type `bucket_type` to be passed in the constructor. This bucket array must | |
1526 | //! have at least the same lifetime as the container. This makes the use of | |
1527 | //! hashtable more complicated than purely intrusive containers. | |
1528 | //! `bucket_type` is default-constructible, copyable and assignable | |
1529 | //! | |
1530 | //! The template parameter \c T is the type to be managed by the container. | |
1531 | //! The user can specify additional options and if no options are provided | |
1532 | //! default options are used. | |
1533 | //! | |
1534 | //! The container supports the following options: | |
1535 | //! \c base_hook<>/member_hook<>/value_traits<>, | |
1536 | //! \c constant_time_size<>, \c size_type<>, \c hash<> and \c equal<> | |
1537 | //! \c bucket_traits<>, power_2_buckets<>, cache_begin<> and incremental<>. | |
1538 | //! | |
1539 | //! hashtable only provides forward iterators but it provides 4 iterator types: | |
1540 | //! iterator and const_iterator to navigate through the whole container and | |
1541 | //! local_iterator and const_local_iterator to navigate through the values | |
1542 | //! stored in a single bucket. Local iterators are faster and smaller. | |
1543 | //! | |
1544 | //! It's not recommended to use non constant-time size hashtables because several | |
1545 | //! key functions, like "empty()", become non-constant time functions. Non | |
1546 | //! constant_time size hashtables are mainly provided to support auto-unlink hooks. | |
1547 | //! | |
1548 | //! hashtables, does not make automatic rehashings nor | |
1549 | //! offers functions related to a load factor. Rehashing can be explicitly requested | |
1550 | //! and the user must provide a new bucket array that will be used from that moment. | |
1551 | //! | |
1552 | //! Since no automatic rehashing is done, iterators are never invalidated when | |
1553 | //! inserting or erasing elements. Iterators are only invalidated when rehashing. | |
1554 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
1555 | template<class T, class ...Options> | |
1556 | #else | |
1557 | template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyHash, class VoidOrKeyEqual, class BucketTraits, class SizeType, std::size_t BoolFlags> | |
1558 | #endif | |
1559 | class hashtable_impl | |
1560 | : private hashtable_size_traits_wrapper | |
1561 | < hashdata_internal | |
1562 | < ValueTraits | |
1563 | , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual | |
1564 | , BucketTraits, SizeType | |
1565 | , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1 | |
1566 | > | |
1567 | , SizeType | |
1568 | , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0 | |
1569 | > | |
1570 | { | |
1571 | typedef hashtable_size_traits_wrapper | |
1572 | < hashdata_internal | |
1573 | < ValueTraits | |
1574 | , VoidOrKeyOfValue, VoidOrKeyHash, VoidOrKeyEqual | |
1575 | , BucketTraits, SizeType | |
1576 | , BoolFlags & (hash_bool_flags::incremental_pos | hash_bool_flags::cache_begin_pos) //1 | |
1577 | > | |
1578 | , SizeType | |
1579 | , (BoolFlags & hash_bool_flags::constant_time_size_pos) != 0 | |
1580 | > internal_type; | |
1581 | typedef typename internal_type::size_traits size_traits; | |
1582 | typedef hash_key_types_base | |
1583 | < typename ValueTraits::value_type | |
1584 | , VoidOrKeyOfValue | |
1585 | > hash_types_base; | |
1586 | public: | |
1587 | typedef ValueTraits value_traits; | |
1588 | ||
1589 | /// @cond | |
1590 | typedef BucketTraits bucket_traits; | |
1591 | ||
1592 | typedef typename internal_type::slist_impl slist_impl; | |
1593 | typedef bucket_plus_vtraits<ValueTraits, BucketTraits> bucket_plus_vtraits_t; | |
1594 | typedef typename bucket_plus_vtraits_t::const_value_traits_ptr const_value_traits_ptr; | |
1595 | ||
1596 | using internal_type::begin; | |
1597 | using internal_type::cbegin; | |
1598 | using internal_type::end; | |
1599 | using internal_type::cend; | |
1600 | using internal_type::hash_function; | |
1601 | using internal_type::key_eq; | |
1602 | using internal_type::bucket_size; | |
1603 | using internal_type::bucket_count; | |
1604 | using internal_type::local_iterator_to; | |
1605 | using internal_type::s_local_iterator_to; | |
1606 | using internal_type::iterator_to; | |
1607 | using internal_type::bucket_pointer; | |
1608 | using internal_type::suggested_upper_bucket_count; | |
1609 | using internal_type::suggested_lower_bucket_count; | |
1610 | using internal_type::split_count; | |
1611 | ||
1612 | /// @endcond | |
1613 | ||
1614 | typedef typename value_traits::pointer pointer; | |
1615 | typedef typename value_traits::const_pointer const_pointer; | |
1616 | typedef typename value_traits::value_type value_type; | |
1617 | typedef typename hash_types_base::key_type key_type; | |
1618 | typedef typename hash_types_base::key_of_value key_of_value; | |
1619 | typedef typename pointer_traits<pointer>::reference reference; | |
1620 | typedef typename pointer_traits<const_pointer>::reference const_reference; | |
1621 | typedef typename pointer_traits<pointer>::difference_type difference_type; | |
1622 | typedef SizeType size_type; | |
1623 | typedef typename internal_type::key_equal key_equal; | |
1624 | typedef typename internal_type::hasher hasher; | |
1625 | typedef detail::bucket_impl<slist_impl> bucket_type; | |
1626 | typedef typename internal_type::bucket_ptr bucket_ptr; | |
1627 | typedef typename slist_impl::iterator siterator; | |
1628 | typedef typename slist_impl::const_iterator const_siterator; | |
1629 | typedef typename internal_type::iterator iterator; | |
1630 | typedef typename internal_type::const_iterator const_iterator; | |
1631 | typedef typename internal_type::local_iterator local_iterator; | |
1632 | typedef typename internal_type::const_local_iterator const_local_iterator; | |
1633 | typedef typename value_traits::node_traits node_traits; | |
1634 | typedef typename node_traits::node node; | |
1635 | typedef typename pointer_traits | |
1636 | <pointer>::template rebind_pointer | |
1637 | < node >::type node_ptr; | |
1638 | typedef typename pointer_traits | |
1639 | <pointer>::template rebind_pointer | |
1640 | < const node >::type const_node_ptr; | |
1641 | typedef typename pointer_traits | |
1642 | <node_ptr>::reference node_reference; | |
1643 | typedef typename pointer_traits | |
1644 | <const_node_ptr>::reference const_node_reference; | |
1645 | typedef typename slist_impl::node_algorithms node_algorithms; | |
1646 | ||
1647 | static const bool stateful_value_traits = internal_type::stateful_value_traits; | |
1648 | static const bool store_hash = internal_type::store_hash; | |
1649 | ||
1650 | static const bool unique_keys = 0 != (BoolFlags & hash_bool_flags::unique_keys_pos); | |
1651 | static const bool constant_time_size = 0 != (BoolFlags & hash_bool_flags::constant_time_size_pos); | |
1652 | static const bool cache_begin = 0 != (BoolFlags & hash_bool_flags::cache_begin_pos); | |
1653 | static const bool compare_hash = 0 != (BoolFlags & hash_bool_flags::compare_hash_pos); | |
1654 | static const bool incremental = 0 != (BoolFlags & hash_bool_flags::incremental_pos); | |
1655 | static const bool power_2_buckets = incremental || (0 != (BoolFlags & hash_bool_flags::power_2_buckets_pos)); | |
1656 | ||
1657 | static const bool optimize_multikey | |
1658 | = detail::optimize_multikey_is_true<node_traits>::value && !unique_keys; | |
1659 | ||
1660 | /// @cond | |
1661 | static const bool is_multikey = !unique_keys; | |
1662 | private: | |
1663 | ||
1664 | //Configuration error: compare_hash<> can't be specified without store_hash<> | |
1665 | //See documentation for more explanations | |
1666 | BOOST_STATIC_ASSERT((!compare_hash || store_hash)); | |
1667 | ||
1668 | typedef typename slist_impl::node_ptr slist_node_ptr; | |
1669 | typedef typename pointer_traits | |
1670 | <slist_node_ptr>::template rebind_pointer | |
1671 | < void >::type void_pointer; | |
1672 | //We'll define group traits, but these won't be instantiated if | |
1673 | //optimize_multikey is not true | |
1674 | typedef unordered_group_adapter<node_traits> group_traits; | |
1675 | typedef circular_slist_algorithms<group_traits> group_algorithms; | |
1676 | typedef typename internal_type::store_hash_t store_hash_t; | |
1677 | typedef detail::bool_<optimize_multikey> optimize_multikey_t; | |
1678 | typedef detail::bool_<cache_begin> cache_begin_t; | |
1679 | typedef detail::bool_<power_2_buckets> power_2_buckets_t; | |
1680 | typedef typename internal_type::split_traits split_traits; | |
1681 | typedef detail::group_functions<node_traits> group_functions_t; | |
1682 | typedef detail::node_functions<node_traits> node_functions_t; | |
1683 | ||
1684 | private: | |
1685 | //noncopyable, movable | |
1686 | BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable_impl) | |
1687 | ||
1688 | static const bool safemode_or_autounlink = internal_type::safemode_or_autounlink; | |
1689 | ||
1690 | //Constant-time size is incompatible with auto-unlink hooks! | |
1691 | BOOST_STATIC_ASSERT(!(constant_time_size && ((int)value_traits::link_mode == (int)auto_unlink))); | |
1692 | //Cache begin is incompatible with auto-unlink hooks! | |
1693 | BOOST_STATIC_ASSERT(!(cache_begin && ((int)value_traits::link_mode == (int)auto_unlink))); | |
1694 | ||
1695 | template<class Disposer> | |
1696 | struct typeof_node_disposer | |
1697 | { | |
1698 | typedef node_cast_adaptor | |
1699 | < detail::node_disposer< Disposer, value_traits, CircularSListAlgorithms> | |
1700 | , slist_node_ptr, node_ptr > type; | |
1701 | }; | |
1702 | ||
1703 | template<class Disposer> | |
1704 | typename typeof_node_disposer<Disposer>::type | |
1705 | make_node_disposer(const Disposer &disposer) const | |
1706 | { | |
1707 | typedef typename typeof_node_disposer<Disposer>::type return_t; | |
1708 | return return_t(disposer, &this->priv_value_traits()); | |
1709 | } | |
1710 | ||
1711 | /// @endcond | |
1712 | ||
1713 | public: | |
1714 | typedef detail::insert_commit_data_impl insert_commit_data; | |
1715 | ||
1716 | ||
1717 | public: | |
1718 | ||
1719 | //! <b>Requires</b>: buckets must not be being used by any other resource. | |
1720 | //! | |
1721 | //! <b>Effects</b>: Constructs an empty unordered_set, storing a reference | |
1722 | //! to the bucket array and copies of the key_hasher and equal_func functors. | |
1723 | //! | |
1724 | //! <b>Complexity</b>: Constant. | |
1725 | //! | |
1726 | //! <b>Throws</b>: If value_traits::node_traits::node | |
1727 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) | |
1728 | //! or the copy constructor or invocation of hash_func or equal_func throws. | |
1729 | //! | |
1730 | //! <b>Notes</b>: buckets array must be disposed only after | |
1731 | //! *this is disposed. | |
1732 | explicit hashtable_impl ( const bucket_traits &b_traits | |
1733 | , const hasher & hash_func = hasher() | |
1734 | , const key_equal &equal_func = key_equal() | |
1735 | , const value_traits &v_traits = value_traits()) | |
1736 | : internal_type(v_traits, b_traits, hash_func, equal_func) | |
1737 | { | |
1738 | this->priv_initialize_buckets_and_cache(); | |
1739 | this->priv_size_traits().set_size(size_type(0)); | |
1740 | size_type bucket_sz = this->priv_bucket_count(); | |
1741 | BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); | |
1742 | //Check power of two bucket array if the option is activated | |
1743 | BOOST_INTRUSIVE_INVARIANT_ASSERT | |
1744 | (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1)))); | |
1745 | this->priv_split_traits().set_size(bucket_sz>>1); | |
1746 | } | |
1747 | ||
1748 | //! <b>Requires</b>: buckets must not be being used by any other resource | |
1749 | //! and dereferencing iterator must yield an lvalue of type value_type. | |
1750 | //! | |
1751 | //! <b>Effects</b>: Constructs an empty container and inserts elements from | |
1752 | //! [b, e). | |
1753 | //! | |
1754 | //! <b>Complexity</b>: If N is distance(b, e): Average case is O(N) | |
1755 | //! (with a good hash function and with buckets_len >= N),worst case O(N^2). | |
1756 | //! | |
1757 | //! <b>Throws</b>: If value_traits::node_traits::node | |
1758 | //! constructor throws (this does not happen with predefined Boost.Intrusive hooks) | |
1759 | //! or the copy constructor or invocation of hasher or key_equal throws. | |
1760 | //! | |
1761 | //! <b>Notes</b>: buckets array must be disposed only after | |
1762 | //! *this is disposed. | |
1763 | template<class Iterator> | |
1764 | hashtable_impl ( bool unique, Iterator b, Iterator e | |
1765 | , const bucket_traits &b_traits | |
1766 | , const hasher & hash_func = hasher() | |
1767 | , const key_equal &equal_func = key_equal() | |
1768 | , const value_traits &v_traits = value_traits()) | |
1769 | : internal_type(v_traits, b_traits, hash_func, equal_func) | |
1770 | { | |
1771 | this->priv_initialize_buckets_and_cache(); | |
1772 | this->priv_size_traits().set_size(size_type(0)); | |
1773 | size_type bucket_sz = this->priv_bucket_count(); | |
1774 | BOOST_INTRUSIVE_INVARIANT_ASSERT(bucket_sz != 0); | |
1775 | //Check power of two bucket array if the option is activated | |
1776 | BOOST_INTRUSIVE_INVARIANT_ASSERT | |
1777 | (!power_2_buckets || (0 == (bucket_sz & (bucket_sz-1)))); | |
1778 | this->priv_split_traits().set_size(bucket_sz>>1); | |
1779 | //Now insert | |
1780 | if(unique) | |
1781 | this->insert_unique(b, e); | |
1782 | else | |
1783 | this->insert_equal(b, e); | |
1784 | } | |
1785 | ||
1786 | //! <b>Effects</b>: to-do | |
1787 | //! | |
1788 | hashtable_impl(BOOST_RV_REF(hashtable_impl) x) | |
1789 | : internal_type( ::boost::move(x.priv_value_traits()) | |
1790 | , ::boost::move(x.priv_bucket_traits()) | |
1791 | , ::boost::move(x.priv_hasher()) | |
1792 | , ::boost::move(x.priv_equal()) | |
1793 | ) | |
1794 | { | |
1795 | this->priv_swap_cache(x); | |
1796 | x.priv_initialize_cache(); | |
1797 | this->priv_size_traits().set_size(x.priv_size_traits().get_size()); | |
1798 | x.priv_size_traits().set_size(size_type(0)); | |
1799 | this->priv_split_traits().set_size(x.priv_split_traits().get_size()); | |
1800 | x.priv_split_traits().set_size(size_type(0)); | |
1801 | } | |
1802 | ||
1803 | //! <b>Effects</b>: to-do | |
1804 | //! | |
1805 | hashtable_impl& operator=(BOOST_RV_REF(hashtable_impl) x) | |
1806 | { this->swap(x); return *this; } | |
1807 | ||
1808 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
1809 | //! <b>Effects</b>: Detaches all elements from this. The objects in the unordered_set | |
1810 | //! are not deleted (i.e. no destructors are called). | |
1811 | //! | |
1812 | //! <b>Complexity</b>: Linear to the number of elements in the unordered_set, if | |
1813 | //! it's a safe-mode or auto-unlink value. Otherwise constant. | |
1814 | //! | |
1815 | //! <b>Throws</b>: Nothing. | |
1816 | ~hashtable_impl(); | |
1817 | ||
1818 | //! <b>Effects</b>: Returns an iterator pointing to the beginning of the unordered_set. | |
1819 | //! | |
1820 | //! <b>Complexity</b>: Amortized constant time. | |
1821 | //! Worst case (empty unordered_set): O(this->bucket_count()) | |
1822 | //! | |
1823 | //! <b>Throws</b>: Nothing. | |
1824 | iterator begin(); | |
1825 | ||
1826 | //! <b>Effects</b>: Returns a const_iterator pointing to the beginning | |
1827 | //! of the unordered_set. | |
1828 | //! | |
1829 | //! <b>Complexity</b>: Amortized constant time. | |
1830 | //! Worst case (empty unordered_set): O(this->bucket_count()) | |
1831 | //! | |
1832 | //! <b>Throws</b>: Nothing. | |
1833 | const_iterator begin() const; | |
1834 | ||
1835 | //! <b>Effects</b>: Returns a const_iterator pointing to the beginning | |
1836 | //! of the unordered_set. | |
1837 | //! | |
1838 | //! <b>Complexity</b>: Amortized constant time. | |
1839 | //! Worst case (empty unordered_set): O(this->bucket_count()) | |
1840 | //! | |
1841 | //! <b>Throws</b>: Nothing. | |
1842 | const_iterator cbegin() const; | |
1843 | ||
1844 | //! <b>Effects</b>: Returns an iterator pointing to the end of the unordered_set. | |
1845 | //! | |
1846 | //! <b>Complexity</b>: Constant. | |
1847 | //! | |
1848 | //! <b>Throws</b>: Nothing. | |
1849 | iterator end(); | |
1850 | ||
1851 | //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. | |
1852 | //! | |
1853 | //! <b>Complexity</b>: Constant. | |
1854 | //! | |
1855 | //! <b>Throws</b>: Nothing. | |
1856 | const_iterator end() const; | |
1857 | ||
1858 | //! <b>Effects</b>: Returns a const_iterator pointing to the end of the unordered_set. | |
1859 | //! | |
1860 | //! <b>Complexity</b>: Constant. | |
1861 | //! | |
1862 | //! <b>Throws</b>: Nothing. | |
1863 | const_iterator cend() const; | |
1864 | ||
1865 | //! <b>Effects</b>: Returns the hasher object used by the unordered_set. | |
1866 | //! | |
1867 | //! <b>Complexity</b>: Constant. | |
1868 | //! | |
1869 | //! <b>Throws</b>: If hasher copy-constructor throws. | |
1870 | hasher hash_function() const; | |
1871 | ||
1872 | //! <b>Effects</b>: Returns the key_equal object used by the unordered_set. | |
1873 | //! | |
1874 | //! <b>Complexity</b>: Constant. | |
1875 | //! | |
1876 | //! <b>Throws</b>: If key_equal copy-constructor throws. | |
1877 | key_equal key_eq() const; | |
1878 | ||
1879 | #endif | |
1880 | ||
1881 | //! <b>Effects</b>: Returns true if the container is empty. | |
1882 | //! | |
1883 | //! <b>Complexity</b>: if constant-time size and cache_begin options are disabled, | |
1884 | //! average constant time (worst case, with empty() == true: O(this->bucket_count()). | |
1885 | //! Otherwise constant. | |
1886 | //! | |
1887 | //! <b>Throws</b>: Nothing. | |
1888 | bool empty() const | |
1889 | { | |
1890 | if(constant_time_size){ | |
1891 | return !this->size(); | |
1892 | } | |
1893 | else if(cache_begin){ | |
1894 | return this->begin() == this->end(); | |
1895 | } | |
1896 | else{ | |
1897 | size_type bucket_cnt = this->priv_bucket_count(); | |
1898 | const bucket_type *b = boost::intrusive::detail::to_raw_pointer(this->priv_bucket_pointer()); | |
1899 | for (size_type n = 0; n < bucket_cnt; ++n, ++b){ | |
1900 | if(!b->empty()){ | |
1901 | return false; | |
1902 | } | |
1903 | } | |
1904 | return true; | |
1905 | } | |
1906 | } | |
1907 | ||
1908 | //! <b>Effects</b>: Returns the number of elements stored in the unordered_set. | |
1909 | //! | |
1910 | //! <b>Complexity</b>: Linear to elements contained in *this if | |
1911 | //! constant_time_size is false. Constant-time otherwise. | |
1912 | //! | |
1913 | //! <b>Throws</b>: Nothing. | |
1914 | size_type size() const | |
1915 | { | |
1916 | if(constant_time_size) | |
1917 | return this->priv_size_traits().get_size(); | |
1918 | else{ | |
1919 | size_type len = 0; | |
1920 | size_type bucket_cnt = this->priv_bucket_count(); | |
1921 | const bucket_type *b = boost::intrusive::detail::to_raw_pointer(this->priv_bucket_pointer()); | |
1922 | for (size_type n = 0; n < bucket_cnt; ++n, ++b){ | |
1923 | len += b->size(); | |
1924 | } | |
1925 | return len; | |
1926 | } | |
1927 | } | |
1928 | ||
1929 | //! <b>Requires</b>: the hasher and the equality function unqualified swap | |
1930 | //! call should not throw. | |
1931 | //! | |
1932 | //! <b>Effects</b>: Swaps the contents of two unordered_sets. | |
1933 | //! Swaps also the contained bucket array and equality and hasher functors. | |
1934 | //! | |
1935 | //! <b>Complexity</b>: Constant. | |
1936 | //! | |
1937 | //! <b>Throws</b>: If the swap() call for the comparison or hash functors | |
1938 | //! found using ADL throw. Basic guarantee. | |
1939 | void swap(hashtable_impl& other) | |
1940 | { | |
1941 | //These can throw | |
1942 | ::boost::adl_move_swap(this->priv_equal(), other.priv_equal()); | |
1943 | ::boost::adl_move_swap(this->priv_hasher(), other.priv_hasher()); | |
1944 | //These can't throw | |
1945 | ::boost::adl_move_swap(this->priv_bucket_traits(), other.priv_bucket_traits()); | |
1946 | ::boost::adl_move_swap(this->priv_value_traits(), other.priv_value_traits()); | |
1947 | this->priv_swap_cache(other); | |
1948 | this->priv_size_traits().swap(other.priv_size_traits()); | |
1949 | this->priv_split_traits().swap(other.priv_split_traits()); | |
1950 | } | |
1951 | ||
1952 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw | |
1953 | //! Cloner should yield to nodes that compare equal and produce the same | |
1954 | //! hash than the original node. | |
1955 | //! | |
1956 | //! <b>Effects</b>: Erases all the elements from *this | |
1957 | //! calling Disposer::operator()(pointer), clones all the | |
1958 | //! elements from src calling Cloner::operator()(const_reference ) | |
1959 | //! and inserts them on *this. The hash function and the equality | |
1960 | //! predicate are copied from the source. | |
1961 | //! | |
1962 | //! If store_hash option is true, this method does not use the hash function. | |
1963 | //! | |
1964 | //! If any operation throws, all cloned elements are unlinked and disposed | |
1965 | //! calling Disposer::operator()(pointer). | |
1966 | //! | |
1967 | //! <b>Complexity</b>: Linear to erased plus inserted elements. | |
1968 | //! | |
1969 | //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying | |
1970 | //! throws. Basic guarantee. | |
1971 | template <class Cloner, class Disposer> | |
1972 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable_impl &src, Cloner cloner, Disposer disposer) | |
1973 | { this->priv_clone_from(src, cloner, disposer); } | |
1974 | ||
1975 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw | |
1976 | //! Cloner should yield to nodes that compare equal and produce the same | |
1977 | //! hash than the original node. | |
1978 | //! | |
1979 | //! <b>Effects</b>: Erases all the elements from *this | |
1980 | //! calling Disposer::operator()(pointer), clones all the | |
1981 | //! elements from src calling Cloner::operator()(reference) | |
1982 | //! and inserts them on *this. The hash function and the equality | |
1983 | //! predicate are copied from the source. | |
1984 | //! | |
1985 | //! If store_hash option is true, this method does not use the hash function. | |
1986 | //! | |
1987 | //! If any operation throws, all cloned elements are unlinked and disposed | |
1988 | //! calling Disposer::operator()(pointer). | |
1989 | //! | |
1990 | //! <b>Complexity</b>: Linear to erased plus inserted elements. | |
1991 | //! | |
1992 | //! <b>Throws</b>: If cloner or hasher throw or hash or equality predicate copying | |
1993 | //! throws. Basic guarantee. | |
1994 | template <class Cloner, class Disposer> | |
1995 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable_impl) src, Cloner cloner, Disposer disposer) | |
1996 | { this->priv_clone_from(static_cast<hashtable_impl&>(src), cloner, disposer); } | |
1997 | ||
1998 | //! <b>Requires</b>: value must be an lvalue | |
1999 | //! | |
2000 | //! <b>Effects</b>: Inserts the value into the unordered_set. | |
2001 | //! | |
2002 | //! <b>Returns</b>: An iterator to the inserted value. | |
2003 | //! | |
2004 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2005 | //! | |
2006 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee. | |
2007 | //! | |
2008 | //! <b>Note</b>: Does not affect the validity of iterators and references. | |
2009 | //! No copy-constructors are called. | |
2010 | iterator insert_equal(reference value) | |
2011 | { | |
2012 | size_type bucket_num; | |
2013 | std::size_t hash_value; | |
2014 | siterator prev; | |
2015 | siterator const it = this->priv_find | |
2016 | (key_of_value()(value), this->priv_hasher(), this->priv_equal(), bucket_num, hash_value, prev); | |
2017 | bool const next_is_in_group = optimize_multikey && it != this->priv_invalid_local_it(); | |
2018 | return this->priv_insert_equal_after_find(value, bucket_num, hash_value, prev, next_is_in_group); | |
2019 | } | |
2020 | ||
2021 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue | |
2022 | //! of type value_type. | |
2023 | //! | |
2024 | //! <b>Effects</b>: Equivalent to this->insert_equal(t) for each element in [b, e). | |
2025 | //! | |
2026 | //! <b>Complexity</b>: Average case O(N), where N is distance(b, e). | |
2027 | //! Worst case O(N*this->size()). | |
2028 | //! | |
2029 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. | |
2030 | //! | |
2031 | //! <b>Note</b>: Does not affect the validity of iterators and references. | |
2032 | //! No copy-constructors are called. | |
2033 | template<class Iterator> | |
2034 | void insert_equal(Iterator b, Iterator e) | |
2035 | { | |
2036 | for (; b != e; ++b) | |
2037 | this->insert_equal(*b); | |
2038 | } | |
2039 | ||
2040 | //! <b>Requires</b>: value must be an lvalue | |
2041 | //! | |
2042 | //! <b>Effects</b>: Tries to inserts value into the unordered_set. | |
2043 | //! | |
2044 | //! <b>Returns</b>: If the value | |
2045 | //! is not already present inserts it and returns a pair containing the | |
2046 | //! iterator to the new value and true. If there is an equivalent value | |
2047 | //! returns a pair containing an iterator to the already present value | |
2048 | //! and false. | |
2049 | //! | |
2050 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2051 | //! | |
2052 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. Strong guarantee. | |
2053 | //! | |
2054 | //! <b>Note</b>: Does not affect the validity of iterators and references. | |
2055 | //! No copy-constructors are called. | |
2056 | std::pair<iterator, bool> insert_unique(reference value) | |
2057 | { | |
2058 | insert_commit_data commit_data; | |
2059 | std::pair<iterator, bool> ret = this->insert_unique_check(key_of_value()(value), commit_data); | |
2060 | if(ret.second){ | |
2061 | ret.first = this->insert_unique_commit(value, commit_data); | |
2062 | } | |
2063 | return ret; | |
2064 | } | |
2065 | ||
2066 | //! <b>Requires</b>: Dereferencing iterator must yield an lvalue | |
2067 | //! of type value_type. | |
2068 | //! | |
2069 | //! <b>Effects</b>: Equivalent to this->insert_unique(t) for each element in [b, e). | |
2070 | //! | |
2071 | //! <b>Complexity</b>: Average case O(N), where N is distance(b, e). | |
2072 | //! Worst case O(N*this->size()). | |
2073 | //! | |
2074 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. Basic guarantee. | |
2075 | //! | |
2076 | //! <b>Note</b>: Does not affect the validity of iterators and references. | |
2077 | //! No copy-constructors are called. | |
2078 | template<class Iterator> | |
2079 | void insert_unique(Iterator b, Iterator e) | |
2080 | { | |
2081 | for (; b != e; ++b) | |
2082 | this->insert_unique(*b); | |
2083 | } | |
2084 | ||
2085 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2086 | //! the same hash values as the stored hasher. The difference is that | |
2087 | //! "hash_func" hashes the given key instead of the value_type. | |
2088 | //! | |
2089 | //! "equal_func" must be a equality function that induces | |
2090 | //! the same equality as key_equal. The difference is that | |
2091 | //! "equal_func" compares an arbitrary key with the contained values. | |
2092 | //! | |
2093 | //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using | |
2094 | //! a user provided key instead of the value itself. | |
2095 | //! | |
2096 | //! <b>Returns</b>: If there is an equivalent value | |
2097 | //! returns a pair containing an iterator to the already present value | |
2098 | //! and false. If the value can be inserted returns true in the returned | |
2099 | //! pair boolean and fills "commit_data" that is meant to be used with | |
2100 | //! the "insert_commit" function. | |
2101 | //! | |
2102 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2103 | //! | |
2104 | //! <b>Throws</b>: If hash_func or equal_func throw. Strong guarantee. | |
2105 | //! | |
2106 | //! <b>Notes</b>: This function is used to improve performance when constructing | |
2107 | //! a value_type is expensive: if there is an equivalent value | |
2108 | //! the constructed object must be discarded. Many times, the part of the | |
2109 | //! node that is used to impose the hash or the equality is much cheaper to | |
2110 | //! construct than the value_type and this function offers the possibility to | |
2111 | //! use that the part to check if the insertion will be successful. | |
2112 | //! | |
2113 | //! If the check is successful, the user can construct the value_type and use | |
2114 | //! "insert_commit" to insert the object in constant-time. | |
2115 | //! | |
2116 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more | |
2117 | //! objects are inserted or erased from the unordered_set. | |
2118 | //! | |
2119 | //! After a successful rehashing insert_commit_data remains valid. | |
2120 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2121 | std::pair<iterator, bool> insert_unique_check | |
2122 | ( const KeyType &key | |
2123 | , KeyHasher hash_func | |
2124 | , KeyEqual equal_func | |
2125 | , insert_commit_data &commit_data) | |
2126 | { | |
2127 | size_type bucket_num; | |
2128 | siterator prev; | |
2129 | siterator const pos = this->priv_find(key, hash_func, equal_func, bucket_num, commit_data.hash, prev); | |
2130 | return std::pair<iterator, bool> | |
2131 | ( iterator(pos, &this->get_bucket_value_traits()) | |
2132 | , pos == this->priv_invalid_local_it()); | |
2133 | } | |
2134 | ||
2135 | //! <b>Effects</b>: Checks if a value can be inserted in the unordered_set, using | |
2136 | //! a user provided key instead of the value itself. | |
2137 | //! | |
2138 | //! <b>Returns</b>: If there is an equivalent value | |
2139 | //! returns a pair containing an iterator to the already present value | |
2140 | //! and false. If the value can be inserted returns true in the returned | |
2141 | //! pair boolean and fills "commit_data" that is meant to be used with | |
2142 | //! the "insert_commit" function. | |
2143 | //! | |
2144 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2145 | //! | |
2146 | //! <b>Throws</b>: If hasher or key_compare throw. Strong guarantee. | |
2147 | //! | |
2148 | //! <b>Notes</b>: This function is used to improve performance when constructing | |
2149 | //! a value_type is expensive: if there is an equivalent value | |
2150 | //! the constructed object must be discarded. Many times, the part of the | |
2151 | //! node that is used to impose the hash or the equality is much cheaper to | |
2152 | //! construct than the value_type and this function offers the possibility to | |
2153 | //! use that the part to check if the insertion will be successful. | |
2154 | //! | |
2155 | //! If the check is successful, the user can construct the value_type and use | |
2156 | //! "insert_commit" to insert the object in constant-time. | |
2157 | //! | |
2158 | //! "commit_data" remains valid for a subsequent "insert_commit" only if no more | |
2159 | //! objects are inserted or erased from the unordered_set. | |
2160 | //! | |
2161 | //! After a successful rehashing insert_commit_data remains valid. | |
2162 | BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator, bool> insert_unique_check | |
2163 | ( const key_type &key, insert_commit_data &commit_data) | |
2164 | { return this->insert_unique_check(key, this->priv_hasher(), this->priv_equal(), commit_data); } | |
2165 | ||
2166 | //! <b>Requires</b>: value must be an lvalue of type value_type. commit_data | |
2167 | //! must have been obtained from a previous call to "insert_check". | |
2168 | //! No objects should have been inserted or erased from the unordered_set between | |
2169 | //! the "insert_check" that filled "commit_data" and the call to "insert_commit". | |
2170 | //! | |
2171 | //! <b>Effects</b>: Inserts the value in the unordered_set using the information obtained | |
2172 | //! from the "commit_data" that a previous "insert_check" filled. | |
2173 | //! | |
2174 | //! <b>Returns</b>: An iterator to the newly inserted object. | |
2175 | //! | |
2176 | //! <b>Complexity</b>: Constant time. | |
2177 | //! | |
2178 | //! <b>Throws</b>: Nothing. | |
2179 | //! | |
2180 | //! <b>Notes</b>: This function has only sense if a "insert_check" has been | |
2181 | //! previously executed to fill "commit_data". No value should be inserted or | |
2182 | //! erased between the "insert_check" and "insert_commit" calls. | |
2183 | //! | |
2184 | //! After a successful rehashing insert_commit_data remains valid. | |
2185 | iterator insert_unique_commit(reference value, const insert_commit_data &commit_data) | |
2186 | { | |
2187 | size_type bucket_num = this->priv_hash_to_bucket(commit_data.hash); | |
2188 | bucket_type &b = this->priv_bucket_pointer()[bucket_num]; | |
2189 | this->priv_size_traits().increment(); | |
2190 | node_ptr const n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); | |
2191 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n)); | |
2192 | node_functions_t::store_hash(n, commit_data.hash, store_hash_t()); | |
2193 | this->priv_insertion_update_cache(bucket_num); | |
2194 | group_functions_t::insert_in_group(n, n, optimize_multikey_t()); | |
2195 | return iterator(b.insert_after(b.before_begin(), *n), &this->get_bucket_value_traits()); | |
2196 | } | |
2197 | ||
2198 | //! <b>Effects</b>: Erases the element pointed to by i. | |
2199 | //! | |
2200 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2201 | //! | |
2202 | //! <b>Throws</b>: Nothing. | |
2203 | //! | |
2204 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2205 | //! to the erased element. No destructors are called. | |
2206 | BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator i) | |
2207 | { this->erase_and_dispose(i, detail::null_disposer()); } | |
2208 | ||
2209 | //! <b>Effects</b>: Erases the range pointed to by b end e. | |
2210 | //! | |
2211 | //! <b>Complexity</b>: Average case O(distance(b, e)), | |
2212 | //! worst case O(this->size()). | |
2213 | //! | |
2214 | //! <b>Throws</b>: Nothing. | |
2215 | //! | |
2216 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2217 | //! to the erased elements. No destructors are called. | |
2218 | BOOST_INTRUSIVE_FORCEINLINE void erase(const_iterator b, const_iterator e) | |
2219 | { this->erase_and_dispose(b, e, detail::null_disposer()); } | |
2220 | ||
2221 | //! <b>Effects</b>: Erases all the elements with the given value. | |
2222 | //! | |
2223 | //! <b>Returns</b>: The number of erased elements. | |
2224 | //! | |
2225 | //! <b>Complexity</b>: Average case O(this->count(value)). | |
2226 | //! Worst case O(this->size()). | |
2227 | //! | |
2228 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2229 | //! Basic guarantee. | |
2230 | //! | |
2231 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2232 | //! to the erased elements. No destructors are called. | |
2233 | BOOST_INTRUSIVE_FORCEINLINE size_type erase(const key_type &key) | |
2234 | { return this->erase(key, this->priv_hasher(), this->priv_equal()); } | |
2235 | ||
2236 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2237 | //! the same hash values as the stored hasher. The difference is that | |
2238 | //! "hash_func" hashes the given key instead of the value_type. | |
2239 | //! | |
2240 | //! "equal_func" must be a equality function that induces | |
2241 | //! the same equality as key_equal. The difference is that | |
2242 | //! "equal_func" compares an arbitrary key with the contained values. | |
2243 | //! | |
2244 | //! <b>Effects</b>: Erases all the elements that have the same hash and | |
2245 | //! compare equal with the given key. | |
2246 | //! | |
2247 | //! <b>Returns</b>: The number of erased elements. | |
2248 | //! | |
2249 | //! <b>Complexity</b>: Average case O(this->count(value)). | |
2250 | //! Worst case O(this->size()). | |
2251 | //! | |
2252 | //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee. | |
2253 | //! | |
2254 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2255 | //! to the erased elements. No destructors are called. | |
2256 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2257 | BOOST_INTRUSIVE_FORCEINLINE size_type erase(const KeyType& key, KeyHasher hash_func, KeyEqual equal_func) | |
2258 | { return this->erase_and_dispose(key, hash_func, equal_func, detail::null_disposer()); } | |
2259 | ||
2260 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. | |
2261 | //! | |
2262 | //! <b>Effects</b>: Erases the element pointed to by i. | |
2263 | //! Disposer::operator()(pointer) is called for the removed element. | |
2264 | //! | |
2265 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2266 | //! | |
2267 | //! <b>Throws</b>: Nothing. | |
2268 | //! | |
2269 | //! <b>Note</b>: Invalidates the iterators | |
2270 | //! to the erased elements. | |
2271 | template<class Disposer> | |
2272 | BOOST_INTRUSIVE_DOC1ST(void | |
2273 | , typename detail::disable_if_convertible<Disposer BOOST_INTRUSIVE_I const_iterator>::type) | |
2274 | erase_and_dispose(const_iterator i, Disposer disposer) | |
2275 | { | |
2276 | //Get the bucket number and local iterator for both iterators | |
2277 | siterator const first_local_it(i.slist_it()); | |
2278 | size_type const first_bucket_num = this->priv_get_bucket_num(first_local_it); | |
2279 | this->priv_erase_node(this->priv_bucket_pointer()[first_bucket_num], first_local_it, make_node_disposer(disposer), optimize_multikey_t()); | |
2280 | this->priv_size_traits().decrement(); | |
2281 | this->priv_erasure_update_cache_range(first_bucket_num, first_bucket_num); | |
2282 | } | |
2283 | ||
2284 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. | |
2285 | //! | |
2286 | //! <b>Effects</b>: Erases the range pointed to by b end e. | |
2287 | //! Disposer::operator()(pointer) is called for the removed elements. | |
2288 | //! | |
2289 | //! <b>Complexity</b>: Average case O(distance(b, e)), | |
2290 | //! worst case O(this->size()). | |
2291 | //! | |
2292 | //! <b>Throws</b>: Nothing. | |
2293 | //! | |
2294 | //! <b>Note</b>: Invalidates the iterators | |
2295 | //! to the erased elements. | |
2296 | template<class Disposer> | |
2297 | void erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer) | |
2298 | { | |
2299 | if(b != e){ | |
2300 | //Get the bucket number and local iterator for both iterators | |
2301 | siterator first_local_it(b.slist_it()); | |
2302 | size_type first_bucket_num = this->priv_get_bucket_num(first_local_it); | |
2303 | ||
2304 | const bucket_ptr buck_ptr = this->priv_bucket_pointer(); | |
2305 | siterator before_first_local_it | |
2306 | = this->priv_get_previous(buck_ptr[first_bucket_num], first_local_it); | |
2307 | size_type last_bucket_num; | |
2308 | siterator last_local_it; | |
2309 | ||
2310 | //For the end iterator, we will assign the end iterator | |
2311 | //of the last bucket | |
2312 | if(e == this->end()){ | |
2313 | last_bucket_num = this->bucket_count() - 1; | |
2314 | last_local_it = buck_ptr[last_bucket_num].end(); | |
2315 | } | |
2316 | else{ | |
2317 | last_local_it = e.slist_it(); | |
2318 | last_bucket_num = this->priv_get_bucket_num(last_local_it); | |
2319 | } | |
2320 | size_type const num_erased = this->priv_erase_node_range | |
2321 | ( before_first_local_it, first_bucket_num, last_local_it, last_bucket_num | |
2322 | , make_node_disposer(disposer), optimize_multikey_t()); | |
2323 | this->priv_size_traits().set_size(this->priv_size_traits().get_size()-num_erased); | |
2324 | this->priv_erasure_update_cache_range(first_bucket_num, last_bucket_num); | |
2325 | } | |
2326 | } | |
2327 | ||
2328 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. | |
2329 | //! | |
2330 | //! <b>Effects</b>: Erases all the elements with the given value. | |
2331 | //! Disposer::operator()(pointer) is called for the removed elements. | |
2332 | //! | |
2333 | //! <b>Returns</b>: The number of erased elements. | |
2334 | //! | |
2335 | //! <b>Complexity</b>: Average case O(this->count(value)). | |
2336 | //! Worst case O(this->size()). | |
2337 | //! | |
2338 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2339 | //! Basic guarantee. | |
2340 | //! | |
2341 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2342 | //! to the erased elements. No destructors are called. | |
2343 | template<class Disposer> | |
2344 | BOOST_INTRUSIVE_FORCEINLINE size_type erase_and_dispose(const key_type &key, Disposer disposer) | |
2345 | { return this->erase_and_dispose(key, this->priv_hasher(), this->priv_equal(), disposer); } | |
2346 | ||
2347 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. | |
2348 | //! | |
2349 | //! <b>Effects</b>: Erases all the elements with the given key. | |
2350 | //! according to the comparison functor "equal_func". | |
2351 | //! Disposer::operator()(pointer) is called for the removed elements. | |
2352 | //! | |
2353 | //! <b>Returns</b>: The number of erased elements. | |
2354 | //! | |
2355 | //! <b>Complexity</b>: Average case O(this->count(value)). | |
2356 | //! Worst case O(this->size()). | |
2357 | //! | |
2358 | //! <b>Throws</b>: If hash_func or equal_func throw. Basic guarantee. | |
2359 | //! | |
2360 | //! <b>Note</b>: Invalidates the iterators | |
2361 | //! to the erased elements. | |
2362 | template<class KeyType, class KeyHasher, class KeyEqual, class Disposer> | |
2363 | size_type erase_and_dispose(const KeyType& key, KeyHasher hash_func | |
2364 | ,KeyEqual equal_func, Disposer disposer) | |
2365 | { | |
2366 | size_type bucket_num; | |
2367 | std::size_t h; | |
2368 | siterator prev; | |
2369 | siterator it = this->priv_find(key, hash_func, equal_func, bucket_num, h, prev); | |
2370 | bool const success = it != this->priv_invalid_local_it(); | |
2371 | ||
2372 | size_type cnt(0); | |
2373 | if(success){ | |
2374 | if(optimize_multikey){ | |
2375 | cnt = this->priv_erase_from_single_bucket | |
2376 | (this->priv_bucket_pointer()[bucket_num], prev, ++(priv_last_in_group)(it), make_node_disposer(disposer), optimize_multikey_t()); | |
2377 | } | |
2378 | else{ | |
2379 | bucket_type &b = this->priv_bucket_pointer()[bucket_num]; | |
2380 | siterator const end_sit = b.end(); | |
2381 | do{ | |
2382 | ++cnt; | |
2383 | ++it; | |
2384 | }while(it != end_sit && | |
2385 | this->priv_is_value_equal_to_key | |
2386 | (this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)); | |
2387 | bucket_type::s_erase_after_and_dispose(prev, it, make_node_disposer(disposer)); | |
2388 | } | |
2389 | this->priv_size_traits().set_size(this->priv_size_traits().get_size()-cnt); | |
2390 | this->priv_erasure_update_cache(); | |
2391 | } | |
2392 | ||
2393 | return cnt; | |
2394 | } | |
2395 | ||
2396 | //! <b>Effects</b>: Erases all of the elements. | |
2397 | //! | |
2398 | //! <b>Complexity</b>: Linear to the number of elements on the container. | |
2399 | //! if it's a safe-mode or auto-unlink value_type. Constant time otherwise. | |
2400 | //! | |
2401 | //! <b>Throws</b>: Nothing. | |
2402 | //! | |
2403 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2404 | //! to the erased elements. No destructors are called. | |
2405 | void clear() | |
2406 | { | |
2407 | this->priv_clear_buckets_and_cache(); | |
2408 | this->priv_size_traits().set_size(size_type(0)); | |
2409 | } | |
2410 | ||
2411 | //! <b>Requires</b>: Disposer::operator()(pointer) shouldn't throw. | |
2412 | //! | |
2413 | //! <b>Effects</b>: Erases all of the elements. | |
2414 | //! | |
2415 | //! <b>Complexity</b>: Linear to the number of elements on the container. | |
2416 | //! Disposer::operator()(pointer) is called for the removed elements. | |
2417 | //! | |
2418 | //! <b>Throws</b>: Nothing. | |
2419 | //! | |
2420 | //! <b>Note</b>: Invalidates the iterators (but not the references) | |
2421 | //! to the erased elements. No destructors are called. | |
2422 | template<class Disposer> | |
2423 | void clear_and_dispose(Disposer disposer) | |
2424 | { | |
2425 | if(!constant_time_size || !this->empty()){ | |
2426 | size_type num_buckets = this->bucket_count(); | |
2427 | bucket_ptr b = this->priv_bucket_pointer(); | |
2428 | typename typeof_node_disposer<Disposer>::type d(disposer, &this->priv_value_traits()); | |
2429 | for(; num_buckets--; ++b){ | |
2430 | b->clear_and_dispose(d); | |
2431 | } | |
2432 | this->priv_size_traits().set_size(size_type(0)); | |
2433 | } | |
2434 | this->priv_initialize_cache(); | |
2435 | } | |
2436 | ||
2437 | //! <b>Effects</b>: Returns the number of contained elements with the given value | |
2438 | //! | |
2439 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2440 | //! | |
2441 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2442 | BOOST_INTRUSIVE_FORCEINLINE size_type count(const key_type &key) const | |
2443 | { return this->count(key, this->priv_hasher(), this->priv_equal()); } | |
2444 | ||
2445 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2446 | //! the same hash values as the stored hasher. The difference is that | |
2447 | //! "hash_func" hashes the given key instead of the value_type. | |
2448 | //! | |
2449 | //! "equal_func" must be a equality function that induces | |
2450 | //! the same equality as key_equal. The difference is that | |
2451 | //! "equal_func" compares an arbitrary key with the contained values. | |
2452 | //! | |
2453 | //! <b>Effects</b>: Returns the number of contained elements with the given key | |
2454 | //! | |
2455 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2456 | //! | |
2457 | //! <b>Throws</b>: If hash_func or equal throw. | |
2458 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2459 | size_type count(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const | |
2460 | { | |
2461 | size_type cnt; | |
2462 | size_type n_bucket; | |
2463 | this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt); | |
2464 | return cnt; | |
2465 | } | |
2466 | ||
2467 | //! <b>Effects</b>: Finds an iterator to the first element is equal to | |
2468 | //! "value" or end() if that element does not exist. | |
2469 | //! | |
2470 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2471 | //! | |
2472 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2473 | BOOST_INTRUSIVE_FORCEINLINE iterator find(const key_type &key) | |
2474 | { return this->find(key, this->priv_hasher(), this->priv_equal()); } | |
2475 | ||
2476 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2477 | //! the same hash values as the stored hasher. The difference is that | |
2478 | //! "hash_func" hashes the given key instead of the value_type. | |
2479 | //! | |
2480 | //! "equal_func" must be a equality function that induces | |
2481 | //! the same equality as key_equal. The difference is that | |
2482 | //! "equal_func" compares an arbitrary key with the contained values. | |
2483 | //! | |
2484 | //! <b>Effects</b>: Finds an iterator to the first element whose key is | |
2485 | //! "key" according to the given hash and equality functor or end() if | |
2486 | //! that element does not exist. | |
2487 | //! | |
2488 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2489 | //! | |
2490 | //! <b>Throws</b>: If hash_func or equal_func throw. | |
2491 | //! | |
2492 | //! <b>Note</b>: This function is used when constructing a value_type | |
2493 | //! is expensive and the value_type can be compared with a cheaper | |
2494 | //! key type. Usually this key is part of the value_type. | |
2495 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2496 | iterator find(const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) | |
2497 | { | |
2498 | size_type bucket_n; | |
2499 | std::size_t hash; | |
2500 | siterator prev; | |
2501 | return iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash, prev) | |
2502 | , &this->get_bucket_value_traits()); | |
2503 | } | |
2504 | ||
2505 | //! <b>Effects</b>: Finds a const_iterator to the first element whose key is | |
2506 | //! "key" or end() if that element does not exist. | |
2507 | //! | |
2508 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2509 | //! | |
2510 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2511 | BOOST_INTRUSIVE_FORCEINLINE const_iterator find(const key_type &key) const | |
2512 | { return this->find(key, this->priv_hasher(), this->priv_equal()); } | |
2513 | ||
2514 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2515 | //! the same hash values as the stored hasher. The difference is that | |
2516 | //! "hash_func" hashes the given key instead of the value_type. | |
2517 | //! | |
2518 | //! "equal_func" must be a equality function that induces | |
2519 | //! the same equality as key_equal. The difference is that | |
2520 | //! "equal_func" compares an arbitrary key with the contained values. | |
2521 | //! | |
2522 | //! <b>Effects</b>: Finds an iterator to the first element whose key is | |
2523 | //! "key" according to the given hasher and equality functor or end() if | |
2524 | //! that element does not exist. | |
2525 | //! | |
2526 | //! <b>Complexity</b>: Average case O(1), worst case O(this->size()). | |
2527 | //! | |
2528 | //! <b>Throws</b>: If hash_func or equal_func throw. | |
2529 | //! | |
2530 | //! <b>Note</b>: This function is used when constructing a value_type | |
2531 | //! is expensive and the value_type can be compared with a cheaper | |
2532 | //! key type. Usually this key is part of the value_type. | |
2533 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2534 | const_iterator find | |
2535 | (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const | |
2536 | { | |
2537 | size_type bucket_n; | |
2538 | std::size_t hash_value; | |
2539 | siterator prev; | |
2540 | return const_iterator( this->priv_find(key, hash_func, equal_func, bucket_n, hash_value, prev) | |
2541 | , &this->get_bucket_value_traits()); | |
2542 | } | |
2543 | ||
2544 | //! <b>Effects</b>: Returns a range containing all elements with values equivalent | |
2545 | //! to value. Returns std::make_pair(this->end(), this->end()) if no such | |
2546 | //! elements exist. | |
2547 | //! | |
2548 | //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()). | |
2549 | //! | |
2550 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2551 | BOOST_INTRUSIVE_FORCEINLINE std::pair<iterator,iterator> equal_range(const key_type &key) | |
2552 | { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); } | |
2553 | ||
2554 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2555 | //! the same hash values as the stored hasher. The difference is that | |
2556 | //! "hash_func" hashes the given key instead of the value_type. | |
2557 | //! | |
2558 | //! "equal_func" must be a equality function that induces | |
2559 | //! the same equality as key_equal. The difference is that | |
2560 | //! "equal_func" compares an arbitrary key with the contained values. | |
2561 | //! | |
2562 | //! <b>Effects</b>: Returns a range containing all elements with equivalent | |
2563 | //! keys. Returns std::make_pair(this->end(), this->end()) if no such | |
2564 | //! elements exist. | |
2565 | //! | |
2566 | //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)). | |
2567 | //! Worst case O(this->size()). | |
2568 | //! | |
2569 | //! <b>Throws</b>: If hash_func or the equal_func throw. | |
2570 | //! | |
2571 | //! <b>Note</b>: This function is used when constructing a value_type | |
2572 | //! is expensive and the value_type can be compared with a cheaper | |
2573 | //! key type. Usually this key is part of the value_type. | |
2574 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2575 | std::pair<iterator,iterator> equal_range | |
2576 | (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) | |
2577 | { | |
2578 | std::pair<siterator, siterator> ret = | |
2579 | this->priv_equal_range(key, hash_func, equal_func); | |
2580 | return std::pair<iterator, iterator> | |
2581 | ( iterator(ret.first, &this->get_bucket_value_traits()) | |
2582 | , iterator(ret.second, &this->get_bucket_value_traits())); | |
2583 | } | |
2584 | ||
2585 | //! <b>Effects</b>: Returns a range containing all elements with values equivalent | |
2586 | //! to value. Returns std::make_pair(this->end(), this->end()) if no such | |
2587 | //! elements exist. | |
2588 | //! | |
2589 | //! <b>Complexity</b>: Average case O(this->count(value)). Worst case O(this->size()). | |
2590 | //! | |
2591 | //! <b>Throws</b>: If the internal hasher or the equality functor throws. | |
2592 | BOOST_INTRUSIVE_FORCEINLINE std::pair<const_iterator, const_iterator> | |
2593 | equal_range(const key_type &key) const | |
2594 | { return this->equal_range(key, this->priv_hasher(), this->priv_equal()); } | |
2595 | ||
2596 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2597 | //! the same hash values as the stored hasher. The difference is that | |
2598 | //! "hash_func" hashes the given key instead of the value_type. | |
2599 | //! | |
2600 | //! "equal_func" must be a equality function that induces | |
2601 | //! the same equality as key_equal. The difference is that | |
2602 | //! "equal_func" compares an arbitrary key with the contained values. | |
2603 | //! | |
2604 | //! <b>Effects</b>: Returns a range containing all elements with equivalent | |
2605 | //! keys. Returns std::make_pair(this->end(), this->end()) if no such | |
2606 | //! elements exist. | |
2607 | //! | |
2608 | //! <b>Complexity</b>: Average case O(this->count(key, hash_func, equal_func)). | |
2609 | //! Worst case O(this->size()). | |
2610 | //! | |
2611 | //! <b>Throws</b>: If the hasher or equal_func throw. | |
2612 | //! | |
2613 | //! <b>Note</b>: This function is used when constructing a value_type | |
2614 | //! is expensive and the value_type can be compared with a cheaper | |
2615 | //! key type. Usually this key is part of the value_type. | |
2616 | template<class KeyType, class KeyHasher, class KeyEqual> | |
2617 | std::pair<const_iterator,const_iterator> equal_range | |
2618 | (const KeyType &key, KeyHasher hash_func, KeyEqual equal_func) const | |
2619 | { | |
2620 | std::pair<siterator, siterator> ret = | |
2621 | this->priv_equal_range(key, hash_func, equal_func); | |
2622 | return std::pair<const_iterator, const_iterator> | |
2623 | ( const_iterator(ret.first, &this->get_bucket_value_traits()) | |
2624 | , const_iterator(ret.second, &this->get_bucket_value_traits())); | |
2625 | } | |
2626 | ||
2627 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
2628 | ||
2629 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2630 | //! appropriate type. Otherwise the behavior is undefined. | |
2631 | //! | |
2632 | //! <b>Effects</b>: Returns: a valid iterator belonging to the unordered_set | |
2633 | //! that points to the value | |
2634 | //! | |
2635 | //! <b>Complexity</b>: Constant. | |
2636 | //! | |
2637 | //! <b>Throws</b>: If the internal hash function throws. | |
2638 | iterator iterator_to(reference value); | |
2639 | ||
2640 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2641 | //! appropriate type. Otherwise the behavior is undefined. | |
2642 | //! | |
2643 | //! <b>Effects</b>: Returns: a valid const_iterator belonging to the | |
2644 | //! unordered_set that points to the value | |
2645 | //! | |
2646 | //! <b>Complexity</b>: Constant. | |
2647 | //! | |
2648 | //! <b>Throws</b>: If the internal hash function throws. | |
2649 | const_iterator iterator_to(const_reference value) const; | |
2650 | ||
2651 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2652 | //! appropriate type. Otherwise the behavior is undefined. | |
2653 | //! | |
2654 | //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set | |
2655 | //! that points to the value | |
2656 | //! | |
2657 | //! <b>Complexity</b>: Constant. | |
2658 | //! | |
2659 | //! <b>Throws</b>: Nothing. | |
2660 | //! | |
2661 | //! <b>Note</b>: This static function is available only if the <i>value traits</i> | |
2662 | //! is stateless. | |
2663 | static local_iterator s_local_iterator_to(reference value); | |
2664 | ||
2665 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2666 | //! appropriate type. Otherwise the behavior is undefined. | |
2667 | //! | |
2668 | //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to | |
2669 | //! the unordered_set that points to the value | |
2670 | //! | |
2671 | //! <b>Complexity</b>: Constant. | |
2672 | //! | |
2673 | //! <b>Throws</b>: Nothing. | |
2674 | //! | |
2675 | //! <b>Note</b>: This static function is available only if the <i>value traits</i> | |
2676 | //! is stateless. | |
2677 | static const_local_iterator s_local_iterator_to(const_reference value); | |
2678 | ||
2679 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2680 | //! appropriate type. Otherwise the behavior is undefined. | |
2681 | //! | |
2682 | //! <b>Effects</b>: Returns: a valid local_iterator belonging to the unordered_set | |
2683 | //! that points to the value | |
2684 | //! | |
2685 | //! <b>Complexity</b>: Constant. | |
2686 | //! | |
2687 | //! <b>Throws</b>: Nothing. | |
2688 | local_iterator local_iterator_to(reference value); | |
2689 | ||
2690 | //! <b>Requires</b>: value must be an lvalue and shall be in a unordered_set of | |
2691 | //! appropriate type. Otherwise the behavior is undefined. | |
2692 | //! | |
2693 | //! <b>Effects</b>: Returns: a valid const_local_iterator belonging to | |
2694 | //! the unordered_set that points to the value | |
2695 | //! | |
2696 | //! <b>Complexity</b>: Constant. | |
2697 | //! | |
2698 | //! <b>Throws</b>: Nothing. | |
2699 | const_local_iterator local_iterator_to(const_reference value) const; | |
2700 | ||
2701 | //! <b>Effects</b>: Returns the number of buckets passed in the constructor | |
2702 | //! or the last rehash function. | |
2703 | //! | |
2704 | //! <b>Complexity</b>: Constant. | |
2705 | //! | |
2706 | //! <b>Throws</b>: Nothing. | |
2707 | size_type bucket_count() const; | |
2708 | ||
2709 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2710 | //! | |
2711 | //! <b>Effects</b>: Returns the number of elements in the nth bucket. | |
2712 | //! | |
2713 | //! <b>Complexity</b>: Constant. | |
2714 | //! | |
2715 | //! <b>Throws</b>: Nothing. | |
2716 | size_type bucket_size(size_type n) const; | |
2717 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
2718 | ||
2719 | //! <b>Effects</b>: Returns the index of the bucket in which elements | |
2720 | //! with keys equivalent to k would be found, if any such element existed. | |
2721 | //! | |
2722 | //! <b>Complexity</b>: Constant. | |
2723 | //! | |
2724 | //! <b>Throws</b>: If the hash functor throws. | |
2725 | //! | |
2726 | //! <b>Note</b>: the return value is in the range [0, this->bucket_count()). | |
2727 | BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const key_type& k) const | |
2728 | { return this->bucket(k, this->priv_hasher()); } | |
2729 | ||
2730 | //! <b>Requires</b>: "hash_func" must be a hash function that induces | |
2731 | //! the same hash values as the stored hasher. The difference is that | |
2732 | //! "hash_func" hashes the given key instead of the value_type. | |
2733 | //! | |
2734 | //! <b>Effects</b>: Returns the index of the bucket in which elements | |
2735 | //! with keys equivalent to k would be found, if any such element existed. | |
2736 | //! | |
2737 | //! <b>Complexity</b>: Constant. | |
2738 | //! | |
2739 | //! <b>Throws</b>: If hash_func throws. | |
2740 | //! | |
2741 | //! <b>Note</b>: the return value is in the range [0, this->bucket_count()). | |
2742 | template<class KeyType, class KeyHasher> | |
2743 | BOOST_INTRUSIVE_FORCEINLINE size_type bucket(const KeyType& k, KeyHasher hash_func) const | |
2744 | { return this->priv_hash_to_bucket(hash_func(k)); } | |
2745 | ||
2746 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
2747 | //! <b>Effects</b>: Returns the bucket array pointer passed in the constructor | |
2748 | //! or the last rehash function. | |
2749 | //! | |
2750 | //! <b>Complexity</b>: Constant. | |
2751 | //! | |
2752 | //! <b>Throws</b>: Nothing. | |
2753 | bucket_ptr bucket_pointer() const; | |
2754 | ||
2755 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2756 | //! | |
2757 | //! <b>Effects</b>: Returns a local_iterator pointing to the beginning | |
2758 | //! of the sequence stored in the bucket n. | |
2759 | //! | |
2760 | //! <b>Complexity</b>: Constant. | |
2761 | //! | |
2762 | //! <b>Throws</b>: Nothing. | |
2763 | //! | |
2764 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2765 | //! containing all of the elements in the nth bucket. | |
2766 | local_iterator begin(size_type n); | |
2767 | ||
2768 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2769 | //! | |
2770 | //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning | |
2771 | //! of the sequence stored in the bucket n. | |
2772 | //! | |
2773 | //! <b>Complexity</b>: Constant. | |
2774 | //! | |
2775 | //! <b>Throws</b>: Nothing. | |
2776 | //! | |
2777 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2778 | //! containing all of the elements in the nth bucket. | |
2779 | const_local_iterator begin(size_type n) const; | |
2780 | ||
2781 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2782 | //! | |
2783 | //! <b>Effects</b>: Returns a const_local_iterator pointing to the beginning | |
2784 | //! of the sequence stored in the bucket n. | |
2785 | //! | |
2786 | //! <b>Complexity</b>: Constant. | |
2787 | //! | |
2788 | //! <b>Throws</b>: Nothing. | |
2789 | //! | |
2790 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2791 | //! containing all of the elements in the nth bucket. | |
2792 | const_local_iterator cbegin(size_type n) const; | |
2793 | ||
2794 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2795 | //! | |
2796 | //! <b>Effects</b>: Returns a local_iterator pointing to the end | |
2797 | //! of the sequence stored in the bucket n. | |
2798 | //! | |
2799 | //! <b>Complexity</b>: Constant. | |
2800 | //! | |
2801 | //! <b>Throws</b>: Nothing. | |
2802 | //! | |
2803 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2804 | //! containing all of the elements in the nth bucket. | |
2805 | local_iterator end(size_type n); | |
2806 | ||
2807 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2808 | //! | |
2809 | //! <b>Effects</b>: Returns a const_local_iterator pointing to the end | |
2810 | //! of the sequence stored in the bucket n. | |
2811 | //! | |
2812 | //! <b>Complexity</b>: Constant. | |
2813 | //! | |
2814 | //! <b>Throws</b>: Nothing. | |
2815 | //! | |
2816 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2817 | //! containing all of the elements in the nth bucket. | |
2818 | const_local_iterator end(size_type n) const; | |
2819 | ||
2820 | //! <b>Requires</b>: n is in the range [0, this->bucket_count()). | |
2821 | //! | |
2822 | //! <b>Effects</b>: Returns a const_local_iterator pointing to the end | |
2823 | //! of the sequence stored in the bucket n. | |
2824 | //! | |
2825 | //! <b>Complexity</b>: Constant. | |
2826 | //! | |
2827 | //! <b>Throws</b>: Nothing. | |
2828 | //! | |
2829 | //! <b>Note</b>: [this->begin(n), this->end(n)) is a valid range | |
2830 | //! containing all of the elements in the nth bucket. | |
2831 | const_local_iterator cend(size_type n) const; | |
2832 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
2833 | ||
2834 | //! <b>Requires</b>: new_bucket_traits can hold a pointer to a new bucket array | |
2835 | //! or the same as the old bucket array with a different length. new_size is the length of the | |
2836 | //! the array pointed by new_buckets. If new_bucket_traits.bucket_begin() == this->bucket_pointer() | |
2837 | //! new_bucket_traits.bucket_count() can be bigger or smaller than this->bucket_count(). | |
2838 | //! 'new_bucket_traits' copy constructor should not throw. | |
2839 | //! | |
2840 | //! <b>Effects</b>: | |
2841 | //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is false, | |
2842 | //! unlinks values from the old bucket and inserts then in the new one according | |
2843 | //! to the hash value of values. | |
2844 | //! | |
2845 | //! If `new_bucket_traits.bucket_begin() == this->bucket_pointer()` is true, | |
2846 | //! the implementations avoids moving values as much as possible. | |
2847 | //! | |
2848 | //! Bucket traits hold by *this is assigned from new_bucket_traits. | |
2849 | //! If the container is configured as incremental<>, the split bucket is set | |
2850 | //! to the new bucket_count(). | |
2851 | //! | |
2852 | //! If store_hash option is true, this method does not use the hash function. | |
2853 | //! If false, the implementation tries to minimize calls to the hash function | |
2854 | //! (e.g. once for equivalent values if optimize_multikey<true> is true). | |
2855 | //! | |
2856 | //! If rehash is successful updates the internal bucket_traits with new_bucket_traits. | |
2857 | //! | |
2858 | //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic. | |
2859 | //! | |
2860 | //! <b>Throws</b>: If the hasher functor throws. Basic guarantee. | |
2861 | BOOST_INTRUSIVE_FORCEINLINE void rehash(const bucket_traits &new_bucket_traits) | |
2862 | { this->rehash_impl(new_bucket_traits, false); } | |
2863 | ||
2864 | //! <b>Note</b>: This function is used when keys from inserted elements are changed | |
2865 | //! (e.g. a language change when key is a string) but uniqueness and hash properties are | |
2866 | //! preserved so a fast full rehash recovers invariants for *this without extracting and | |
2867 | //! reinserting all elements again. | |
2868 | //! | |
2869 | //! <b>Requires</b>: Calls produced to the hash function should not alter the value uniqueness | |
2870 | //! properties of already inserted elements. If hasher(key1) == hasher(key2) was true when | |
2871 | //! elements were inserted, it shall be true during calls produced in the execution of this function. | |
2872 | //! | |
2873 | //! key_equal is not called inside this function so it is assumed that key_equal(value1, value2) | |
2874 | //! should produce the same results as before for inserted elements. | |
2875 | //! | |
2876 | //! <b>Effects</b>: Reprocesses all values hold by *this, recalculating their hash values | |
2877 | //! and redistributing them though the buckets. | |
2878 | //! | |
2879 | //! If store_hash option is true, this method uses the hash function and updates the stored hash value. | |
2880 | //! | |
2881 | //! <b>Complexity</b>: Average case linear in this->size(), worst case quadratic. | |
2882 | //! | |
2883 | //! <b>Throws</b>: If the hasher functor throws. Basic guarantee. | |
2884 | BOOST_INTRUSIVE_FORCEINLINE void full_rehash() | |
2885 | { this->rehash_impl(this->priv_bucket_traits(), true); } | |
2886 | ||
2887 | //! <b>Requires</b>: | |
2888 | //! | |
2889 | //! <b>Effects</b>: | |
2890 | //! | |
2891 | //! <b>Complexity</b>: | |
2892 | //! | |
2893 | //! <b>Throws</b>: | |
2894 | //! | |
2895 | //! <b>Note</b>: this method is only available if incremental<true> option is activated. | |
2896 | bool incremental_rehash(bool grow = true) | |
2897 | { | |
2898 | //This function is only available for containers with incremental hashing | |
2899 | BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); | |
2900 | const size_type split_idx = this->priv_split_traits().get_size(); | |
2901 | const size_type bucket_cnt = this->priv_bucket_count(); | |
2902 | const bucket_ptr buck_ptr = this->priv_bucket_pointer(); | |
2903 | bool ret = false; | |
2904 | ||
2905 | if(grow){ | |
2906 | //Test if the split variable can be changed | |
2907 | if((ret = split_idx < bucket_cnt)){ | |
2908 | const size_type bucket_to_rehash = split_idx - bucket_cnt/2; | |
2909 | bucket_type &old_bucket = buck_ptr[bucket_to_rehash]; | |
2910 | this->priv_split_traits().increment(); | |
2911 | ||
2912 | //Anti-exception stuff: if an exception is thrown while | |
2913 | //moving elements from old_bucket to the target bucket, all moved | |
2914 | //elements are moved back to the original one. | |
2915 | detail::incremental_rehash_rollback<bucket_type, split_traits> rollback | |
2916 | ( buck_ptr[split_idx], old_bucket, this->priv_split_traits()); | |
2917 | for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end()) | |
2918 | ; i != end_sit; i = before_i, ++i){ | |
2919 | const value_type &v = this->priv_value_from_slist_node(i.pointed_node()); | |
2920 | const std::size_t hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); | |
2921 | const size_type new_n = this->priv_hash_to_bucket(hash_value); | |
2922 | siterator const last = (priv_last_in_group)(i); | |
2923 | if(new_n == bucket_to_rehash){ | |
2924 | before_i = last; | |
2925 | } | |
2926 | else{ | |
2927 | bucket_type &new_b = buck_ptr[new_n]; | |
2928 | new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); | |
2929 | } | |
2930 | } | |
2931 | rollback.release(); | |
2932 | this->priv_erasure_update_cache(); | |
2933 | } | |
2934 | } | |
2935 | else if((ret = split_idx > bucket_cnt/2)){ //!grow | |
2936 | const size_type target_bucket_num = split_idx - 1 - bucket_cnt/2; | |
2937 | bucket_type &target_bucket = buck_ptr[target_bucket_num]; | |
2938 | bucket_type &source_bucket = buck_ptr[split_idx-1]; | |
2939 | target_bucket.splice_after(target_bucket.cbefore_begin(), source_bucket); | |
2940 | this->priv_split_traits().decrement(); | |
2941 | this->priv_insertion_update_cache(target_bucket_num); | |
2942 | } | |
2943 | return ret; | |
2944 | } | |
2945 | ||
2946 | //! <b>Effects</b>: If new_bucket_traits.bucket_count() is not | |
2947 | //! this->bucket_count()/2 or this->bucket_count()*2, or | |
2948 | //! this->split_bucket() != new_bucket_traits.bucket_count() returns false | |
2949 | //! and does nothing. | |
2950 | //! | |
2951 | //! Otherwise, copy assigns new_bucket_traits to the internal bucket_traits | |
2952 | //! and transfers all the objects from old buckets to the new ones. | |
2953 | //! | |
2954 | //! <b>Complexity</b>: Linear to size(). | |
2955 | //! | |
2956 | //! <b>Throws</b>: Nothing | |
2957 | //! | |
2958 | //! <b>Note</b>: this method is only available if incremental<true> option is activated. | |
2959 | bool incremental_rehash(const bucket_traits &new_bucket_traits) | |
2960 | { | |
2961 | //This function is only available for containers with incremental hashing | |
2962 | BOOST_STATIC_ASSERT(( incremental && power_2_buckets )); | |
2963 | size_type const new_bucket_traits_size = new_bucket_traits.bucket_count(); | |
2964 | size_type const cur_bucket_traits = this->priv_bucket_count(); | |
2965 | const size_type split_idx = this->split_count(); | |
2966 | ||
2967 | //Test new bucket size is consistent with internal bucket size and split count | |
2968 | if(new_bucket_traits_size/2 == cur_bucket_traits){ | |
2969 | if(!(split_idx >= cur_bucket_traits)) | |
2970 | return false; | |
2971 | } | |
2972 | else if(new_bucket_traits_size == cur_bucket_traits/2){ | |
2973 | if(!(split_idx <= new_bucket_traits_size)) | |
2974 | return false; | |
2975 | } | |
2976 | else{ | |
2977 | return false; | |
2978 | } | |
2979 | ||
2980 | const size_type ini_n = this->priv_get_cache_bucket_num(); | |
2981 | const bucket_ptr old_buckets = this->priv_bucket_pointer(); | |
2982 | this->priv_bucket_traits() = new_bucket_traits; | |
2983 | if(new_bucket_traits.bucket_begin() != old_buckets){ | |
2984 | for(size_type n = ini_n; n < split_idx; ++n){ | |
2985 | bucket_type &new_bucket = new_bucket_traits.bucket_begin()[n]; | |
2986 | bucket_type &old_bucket = old_buckets[n]; | |
2987 | new_bucket.splice_after(new_bucket.cbefore_begin(), old_bucket); | |
2988 | } | |
2989 | //Put cache to safe position | |
2990 | this->priv_initialize_cache(); | |
2991 | this->priv_insertion_update_cache(ini_n); | |
2992 | } | |
2993 | return true; | |
2994 | } | |
2995 | ||
2996 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
2997 | ||
2998 | //! <b>Requires</b>: incremental<> option must be set | |
2999 | //! | |
3000 | //! <b>Effects</b>: returns the current split count | |
3001 | //! | |
3002 | //! <b>Complexity</b>: Constant | |
3003 | //! | |
3004 | //! <b>Throws</b>: Nothing | |
3005 | size_type split_count() const; | |
3006 | ||
3007 | //! <b>Effects</b>: Returns the nearest new bucket count optimized for | |
3008 | //! the container that is bigger or equal than n. This suggestion can be | |
3009 | //! used to create bucket arrays with a size that will usually improve | |
3010 | //! container's performance. If such value does not exist, the | |
3011 | //! higher possible value is returned. | |
3012 | //! | |
3013 | //! <b>Complexity</b>: Amortized constant time. | |
3014 | //! | |
3015 | //! <b>Throws</b>: Nothing. | |
3016 | static size_type suggested_upper_bucket_count(size_type n); | |
3017 | ||
3018 | //! <b>Effects</b>: Returns the nearest new bucket count optimized for | |
3019 | //! the container that is smaller or equal than n. This suggestion can be | |
3020 | //! used to create bucket arrays with a size that will usually improve | |
3021 | //! container's performance. If such value does not exist, the | |
3022 | //! lowest possible value is returned. | |
3023 | //! | |
3024 | //! <b>Complexity</b>: Amortized constant time. | |
3025 | //! | |
3026 | //! <b>Throws</b>: Nothing. | |
3027 | static size_type suggested_lower_bucket_count(size_type n); | |
3028 | #endif //#if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
3029 | ||
3030 | ||
3031 | friend bool operator==(const hashtable_impl &x, const hashtable_impl &y) | |
3032 | { | |
3033 | //Taken from N3068 | |
3034 | if(constant_time_size && x.size() != y.size()){ | |
3035 | return false; | |
3036 | } | |
3037 | for (const_iterator ix = x.cbegin(), ex = x.cend(); ix != ex; ++ix){ | |
3038 | std::pair<const_iterator, const_iterator> eqx(x.equal_range(key_of_value()(*ix))), | |
3039 | eqy(y.equal_range(key_of_value()(*ix))); | |
3040 | if (boost::intrusive::iterator_distance(eqx.first, eqx.second) != | |
3041 | boost::intrusive::iterator_distance(eqy.first, eqy.second) || | |
3042 | !(priv_algo_is_permutation)(eqx.first, eqx.second, eqy.first) ){ | |
3043 | return false; | |
3044 | } | |
3045 | ix = eqx.second; | |
3046 | } | |
3047 | return true; | |
3048 | } | |
3049 | ||
3050 | friend bool operator!=(const hashtable_impl &x, const hashtable_impl &y) | |
3051 | { return !(x == y); } | |
3052 | ||
3053 | friend bool operator<(const hashtable_impl &x, const hashtable_impl &y) | |
3054 | { return ::boost::intrusive::algo_lexicographical_compare(x.begin(), x.end(), y.begin(), y.end()); } | |
3055 | ||
3056 | friend bool operator>(const hashtable_impl &x, const hashtable_impl &y) | |
3057 | { return y < x; } | |
3058 | ||
3059 | friend bool operator<=(const hashtable_impl &x, const hashtable_impl &y) | |
3060 | { return !(y < x); } | |
3061 | ||
3062 | friend bool operator>=(const hashtable_impl &x, const hashtable_impl &y) | |
3063 | { return !(x < y); } | |
3064 | ||
3065 | /// @cond | |
3066 | BOOST_INTRUSIVE_FORCEINLINE void check() const {} | |
3067 | private: | |
3068 | ||
3069 | void rehash_impl(const bucket_traits &new_bucket_traits, bool do_full_rehash) | |
3070 | { | |
3071 | const bucket_ptr new_buckets = new_bucket_traits.bucket_begin(); | |
3072 | size_type new_bucket_count = new_bucket_traits.bucket_count(); | |
3073 | const bucket_ptr old_buckets = this->priv_bucket_pointer(); | |
3074 | size_type old_bucket_count = this->priv_bucket_count(); | |
3075 | ||
3076 | //Check power of two bucket array if the option is activated | |
3077 | BOOST_INTRUSIVE_INVARIANT_ASSERT | |
3078 | (!power_2_buckets || (0 == (new_bucket_count & (new_bucket_count-1u)))); | |
3079 | ||
3080 | size_type n = this->priv_get_cache_bucket_num(); | |
3081 | const bool same_buffer = old_buckets == new_buckets; | |
3082 | //If the new bucket length is a common factor | |
3083 | //of the old one we can avoid hash calculations. | |
3084 | const bool fast_shrink = (!do_full_rehash) && (!incremental) && (old_bucket_count >= new_bucket_count) && | |
3085 | (power_2_buckets || (old_bucket_count % new_bucket_count) == 0); | |
3086 | //If we are shrinking the same bucket array and it's | |
3087 | //is a fast shrink, just rehash the last nodes | |
3088 | size_type new_first_bucket_num = new_bucket_count; | |
3089 | if(same_buffer && fast_shrink && (n < new_bucket_count)){ | |
3090 | new_first_bucket_num = n; | |
3091 | n = new_bucket_count; | |
3092 | } | |
3093 | ||
3094 | //Anti-exception stuff: they destroy the elements if something goes wrong. | |
3095 | //If the source and destination buckets are the same, the second rollback function | |
3096 | //is harmless, because all elements have been already unlinked and destroyed | |
3097 | typedef detail::init_disposer<node_algorithms> NodeDisposer; | |
3098 | typedef detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> ArrayDisposer; | |
3099 | NodeDisposer node_disp; | |
3100 | ArrayDisposer rollback1(new_buckets[0], node_disp, new_bucket_count); | |
3101 | ArrayDisposer rollback2(old_buckets[0], node_disp, old_bucket_count); | |
3102 | ||
3103 | //Put size in a safe value for rollback exception | |
3104 | size_type const size_backup = this->priv_size_traits().get_size(); | |
3105 | this->priv_size_traits().set_size(0); | |
3106 | //Put cache to safe position | |
3107 | this->priv_initialize_cache(); | |
3108 | this->priv_insertion_update_cache(size_type(0u)); | |
3109 | ||
3110 | //Iterate through nodes | |
3111 | for(; n < old_bucket_count; ++n){ | |
3112 | bucket_type &old_bucket = old_buckets[n]; | |
3113 | if(!fast_shrink){ | |
3114 | for( siterator before_i(old_bucket.before_begin()), i(old_bucket.begin()), end_sit(old_bucket.end()) | |
3115 | ; i != end_sit | |
3116 | ; i = before_i, ++i){ | |
3117 | ||
3118 | //First obtain hash value (and store it if do_full_rehash) | |
3119 | std::size_t hash_value; | |
3120 | if(do_full_rehash){ | |
3121 | value_type &v = this->priv_value_from_slist_node(i.pointed_node()); | |
3122 | hash_value = this->priv_hasher()(key_of_value()(v)); | |
3123 | node_functions_t::store_hash(pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(v)), hash_value, store_hash_t()); | |
3124 | } | |
3125 | else{ | |
3126 | const value_type &v = this->priv_value_from_slist_node(i.pointed_node()); | |
3127 | hash_value = this->priv_stored_or_compute_hash(v, store_hash_t()); | |
3128 | } | |
3129 | ||
3130 | //Now calculate the new bucket position | |
3131 | const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental> | |
3132 | (hash_value, new_bucket_count, new_bucket_count); | |
3133 | ||
3134 | //Update first used bucket cache | |
3135 | if(cache_begin && new_n < new_first_bucket_num) | |
3136 | new_first_bucket_num = new_n; | |
3137 | ||
3138 | //If the target bucket is new, transfer the whole group | |
3139 | siterator const last = (priv_last_in_group)(i); | |
3140 | ||
3141 | if(same_buffer && new_n == n){ | |
3142 | before_i = last; | |
3143 | } | |
3144 | else{ | |
3145 | bucket_type &new_b = new_buckets[new_n]; | |
3146 | new_b.splice_after(new_b.before_begin(), old_bucket, before_i, last); | |
3147 | } | |
3148 | } | |
3149 | } | |
3150 | else{ | |
3151 | const size_type new_n = detail::hash_to_bucket_split<power_2_buckets, incremental>(n, new_bucket_count, new_bucket_count); | |
3152 | if(cache_begin && new_n < new_first_bucket_num) | |
3153 | new_first_bucket_num = new_n; | |
3154 | bucket_type &new_b = new_buckets[new_n]; | |
3155 | new_b.splice_after( new_b.before_begin() | |
3156 | , old_bucket | |
3157 | , old_bucket.before_begin() | |
3158 | , bucket_plus_vtraits_t::priv_get_last(old_bucket, optimize_multikey_t())); | |
3159 | } | |
3160 | } | |
3161 | ||
3162 | this->priv_size_traits().set_size(size_backup); | |
3163 | this->priv_split_traits().set_size(new_bucket_count); | |
3164 | if(&new_bucket_traits != &this->priv_bucket_traits()){ | |
3165 | this->priv_bucket_traits() = new_bucket_traits; | |
3166 | } | |
3167 | this->priv_initialize_cache(); | |
3168 | this->priv_insertion_update_cache(new_first_bucket_num); | |
3169 | rollback1.release(); | |
3170 | rollback2.release(); | |
3171 | } | |
3172 | ||
3173 | template <class MaybeConstHashtableImpl, class Cloner, class Disposer> | |
3174 | void priv_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer) | |
3175 | { | |
3176 | this->clear_and_dispose(disposer); | |
3177 | if(!constant_time_size || !src.empty()){ | |
3178 | const size_type src_bucket_count = src.bucket_count(); | |
3179 | const size_type dst_bucket_count = this->bucket_count(); | |
3180 | //Check power of two bucket array if the option is activated | |
3181 | BOOST_INTRUSIVE_INVARIANT_ASSERT | |
3182 | (!power_2_buckets || (0 == (src_bucket_count & (src_bucket_count-1)))); | |
3183 | BOOST_INTRUSIVE_INVARIANT_ASSERT | |
3184 | (!power_2_buckets || (0 == (dst_bucket_count & (dst_bucket_count-1)))); | |
3185 | //If src bucket count is bigger or equal, structural copy is possible | |
3186 | const bool structural_copy = (!incremental) && (src_bucket_count >= dst_bucket_count) && | |
3187 | (power_2_buckets || (src_bucket_count % dst_bucket_count) == 0); | |
3188 | if(structural_copy){ | |
3189 | this->priv_structural_clone_from(src, cloner, disposer); | |
3190 | } | |
3191 | else{ | |
3192 | //Unlike previous cloning algorithm, this can throw | |
3193 | //if cloner, hasher or comparison functor throw | |
3194 | typedef typename detail::if_c< detail::is_const<MaybeConstHashtableImpl>::value | |
3195 | , typename MaybeConstHashtableImpl::const_iterator | |
3196 | , typename MaybeConstHashtableImpl::iterator | |
3197 | >::type clone_iterator; | |
3198 | clone_iterator b(src.begin()), e(src.end()); | |
3199 | detail::exception_disposer<hashtable_impl, Disposer> rollback(*this, disposer); | |
3200 | for(; b != e; ++b){ | |
3201 | //No need to check for duplicates and insert it in the first position | |
3202 | //as this is an unordered container. So use minimal insertion code | |
3203 | std::size_t const hash_to_store = this->priv_stored_or_compute_hash(*b, store_hash_t());; | |
3204 | size_type const bucket_number = this->priv_hash_to_bucket(hash_to_store); | |
3205 | typedef typename detail::if_c | |
3206 | <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type; | |
3207 | reference_type r = *b; | |
3208 | this->priv_clone_front_in_bucket<reference_type>(bucket_number, r, hash_to_store, cloner); | |
3209 | } | |
3210 | rollback.release(); | |
3211 | } | |
3212 | } | |
3213 | } | |
3214 | ||
3215 | template<class ValueReference, class Cloner> | |
3216 | void priv_clone_front_in_bucket( size_type const bucket_number | |
3217 | , typename detail::identity<ValueReference>::type src_ref | |
3218 | , std::size_t const hash_to_store, Cloner cloner) | |
3219 | { | |
3220 | //No need to check for duplicates and insert it in the first position | |
3221 | //as this is an unordered container. So use minimal insertion code | |
3222 | //std::size_t const hash_value = this->priv_stored_or_compute_hash(src_ref, store_hash_t());; | |
3223 | //size_type const bucket_number = this->priv_hash_to_bucket(hash_value); | |
3224 | bucket_type &cur_bucket = this->priv_bucket_pointer()[bucket_number]; | |
3225 | siterator const prev(cur_bucket.before_begin()); | |
3226 | //Just check if the cloned node is equal to the first inserted value in the new bucket | |
3227 | //as equal src values were contiguous and they should be already inserted in the | |
3228 | //destination bucket. | |
3229 | bool const next_is_in_group = optimize_multikey && !cur_bucket.empty() && | |
3230 | this->priv_equal()( key_of_value()(src_ref) | |
3231 | , key_of_value()(this->priv_value_from_slist_node((++siterator(prev)).pointed_node()))); | |
3232 | this->priv_insert_equal_after_find(*cloner(src_ref), bucket_number, hash_to_store, prev, next_is_in_group); | |
3233 | } | |
3234 | ||
3235 | template <class MaybeConstHashtableImpl, class Cloner, class Disposer> | |
3236 | void priv_structural_clone_from(MaybeConstHashtableImpl &src, Cloner cloner, Disposer disposer) | |
3237 | { | |
3238 | //First clone the first ones | |
3239 | const size_type src_bucket_count = src.bucket_count(); | |
3240 | const size_type dst_bucket_count = this->bucket_count(); | |
3241 | const bucket_ptr src_buckets = src.priv_bucket_pointer(); | |
3242 | const bucket_ptr dst_buckets = this->priv_bucket_pointer(); | |
3243 | size_type constructed = 0; | |
3244 | typedef node_cast_adaptor< detail::node_disposer<Disposer, value_traits, CircularSListAlgorithms> | |
3245 | , slist_node_ptr, node_ptr > NodeDisposer; | |
3246 | NodeDisposer node_disp(disposer, &this->priv_value_traits()); | |
3247 | ||
3248 | detail::exception_array_disposer<bucket_type, NodeDisposer, size_type> | |
3249 | rollback(dst_buckets[0], node_disp, constructed); | |
3250 | //Now insert the remaining ones using the modulo trick | |
3251 | for( //"constructed" already initialized | |
3252 | ; constructed < src_bucket_count | |
3253 | ; ++constructed){ | |
3254 | //Since incremental hashing can't be structurally copied, avoid hash_to_bucket_split | |
3255 | const std::size_t new_n = detail::hash_to_bucket(constructed, dst_bucket_count, detail::bool_<power_2_buckets>()); | |
3256 | bucket_type &src_b = src_buckets[constructed]; | |
3257 | for( siterator b(src_b.begin()), e(src_b.end()); b != e; ++b){ | |
3258 | slist_node_ptr const n(b.pointed_node()); | |
3259 | typedef typename detail::if_c | |
3260 | <detail::is_const<MaybeConstHashtableImpl>::value, const_reference, reference>::type reference_type; | |
3261 | reference_type r = this->priv_value_from_slist_node(n); | |
3262 | this->priv_clone_front_in_bucket<reference_type> | |
3263 | (new_n, r, this->priv_stored_hash(n, store_hash_t()), cloner); | |
3264 | } | |
3265 | } | |
3266 | this->priv_hasher() = src.priv_hasher(); | |
3267 | this->priv_equal() = src.priv_equal(); | |
3268 | rollback.release(); | |
3269 | this->priv_size_traits().set_size(src.priv_size_traits().get_size()); | |
3270 | this->priv_split_traits().set_size(dst_bucket_count); | |
3271 | this->priv_insertion_update_cache(0u); | |
3272 | this->priv_erasure_update_cache(); | |
3273 | } | |
3274 | ||
3275 | std::size_t priv_hash_to_bucket(std::size_t hash_value) const | |
3276 | { | |
3277 | return detail::hash_to_bucket_split<power_2_buckets, incremental> | |
3278 | (hash_value, this->priv_bucket_traits().bucket_count(), this->priv_split_traits().get_size()); | |
3279 | } | |
3280 | ||
3281 | iterator priv_insert_equal_after_find(reference value, size_type bucket_num, std::size_t hash_value, siterator prev, bool const next_is_in_group) | |
3282 | { | |
3283 | //Now store hash if needed | |
3284 | node_ptr n = pointer_traits<node_ptr>::pointer_to(this->priv_value_to_node(value)); | |
3285 | node_functions_t::store_hash(n, hash_value, store_hash_t()); | |
3286 | //Checks for some modes | |
3287 | BOOST_INTRUSIVE_SAFE_HOOK_DEFAULT_ASSERT(!safemode_or_autounlink || node_algorithms::unique(n)); | |
3288 | //Shortcut to optimize_multikey cases | |
3289 | group_functions_t::insert_in_group | |
3290 | ( next_is_in_group ? detail::dcast_bucket_ptr<node>((++siterator(prev)).pointed_node()) : n | |
3291 | , n, optimize_multikey_t()); | |
3292 | //Update cache and increment size if needed | |
3293 | this->priv_insertion_update_cache(bucket_num); | |
3294 | this->priv_size_traits().increment(); | |
3295 | //Insert the element in the bucket after it | |
3296 | return iterator(bucket_type::s_insert_after(prev, *n), &this->get_bucket_value_traits()); | |
3297 | } | |
3298 | ||
3299 | template<class KeyType, class KeyHasher, class KeyEqual> | |
3300 | siterator priv_find //In case it is not found previt is bucket.before_begin() | |
3301 | ( const KeyType &key, KeyHasher hash_func | |
3302 | , KeyEqual equal_func, size_type &bucket_number, std::size_t &h, siterator &previt) const | |
3303 | { | |
3304 | h = hash_func(key); | |
3305 | return this->priv_find_with_hash(key, equal_func, bucket_number, h, previt); | |
3306 | } | |
3307 | ||
3308 | template<class KeyType, class KeyEqual> | |
3309 | bool priv_is_value_equal_to_key(const value_type &v, const std::size_t h, const KeyType &key, KeyEqual equal_func) const | |
3310 | { | |
3311 | (void)h; | |
3312 | return (!compare_hash || this->priv_stored_or_compute_hash(v, store_hash_t()) == h) && equal_func(key, key_of_value()(v)); | |
3313 | } | |
3314 | ||
3315 | //return previous iterator to the next equal range group in case | |
3316 | static siterator priv_last_in_group(const siterator &it_first_in_group) | |
3317 | { | |
3318 | return bucket_type::s_iterator_to | |
3319 | (*group_functions_t::get_last_in_group | |
3320 | (detail::dcast_bucket_ptr<node>(it_first_in_group.pointed_node()), optimize_multikey_t())); | |
3321 | } | |
3322 | ||
3323 | template<class KeyType, class KeyEqual> | |
3324 | siterator priv_find_with_hash //In case it is not found previt is bucket.before_begin() | |
3325 | ( const KeyType &key, KeyEqual equal_func, size_type &bucket_number, const std::size_t h, siterator &previt) const | |
3326 | { | |
3327 | bucket_number = this->priv_hash_to_bucket(h); | |
3328 | bucket_type &b = this->priv_bucket_pointer()[bucket_number]; | |
3329 | previt = b.before_begin(); | |
3330 | siterator it = previt; | |
3331 | siterator const endit = b.end(); | |
3332 | ||
3333 | while(++it != endit){ | |
3334 | if(this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){ | |
3335 | return it; | |
3336 | } | |
3337 | previt = it = (priv_last_in_group)(it); | |
3338 | } | |
3339 | previt = b.before_begin(); | |
3340 | return this->priv_invalid_local_it(); | |
3341 | } | |
3342 | ||
3343 | template<class KeyType, class KeyHasher, class KeyEqual> | |
3344 | std::pair<siterator, siterator> priv_local_equal_range | |
3345 | ( const KeyType &key | |
3346 | , KeyHasher hash_func | |
3347 | , KeyEqual equal_func | |
3348 | , size_type &found_bucket | |
3349 | , size_type &cnt) const | |
3350 | { | |
3351 | cnt = 0; | |
3352 | //Let's see if the element is present | |
3353 | ||
3354 | siterator prev; | |
3355 | size_type n_bucket; | |
3356 | std::size_t h; | |
3357 | std::pair<siterator, siterator> to_return | |
3358 | ( this->priv_find(key, hash_func, equal_func, n_bucket, h, prev) | |
3359 | , this->priv_invalid_local_it()); | |
3360 | ||
3361 | if(to_return.first != to_return.second){ | |
3362 | found_bucket = n_bucket; | |
3363 | //If it's present, find the first that it's not equal in | |
3364 | //the same bucket | |
3365 | bucket_type &b = this->priv_bucket_pointer()[n_bucket]; | |
3366 | siterator it = to_return.first; | |
3367 | ++cnt; //At least one is found | |
3368 | if(optimize_multikey){ | |
3369 | to_return.second = ++(priv_last_in_group)(it); | |
3370 | cnt += boost::intrusive::iterator_distance(++it, to_return.second); | |
3371 | } | |
3372 | else{ | |
3373 | siterator const bend = b.end(); | |
3374 | while(++it != bend && | |
3375 | this->priv_is_value_equal_to_key(this->priv_value_from_slist_node(it.pointed_node()), h, key, equal_func)){ | |
3376 | ++cnt; | |
3377 | } | |
3378 | to_return.second = it; | |
3379 | } | |
3380 | } | |
3381 | return to_return; | |
3382 | } | |
3383 | ||
3384 | template<class KeyType, class KeyHasher, class KeyEqual> | |
3385 | std::pair<siterator, siterator> priv_equal_range | |
3386 | ( const KeyType &key | |
3387 | , KeyHasher hash_func | |
3388 | , KeyEqual equal_func) const | |
3389 | { | |
3390 | size_type n_bucket; | |
3391 | size_type cnt; | |
3392 | ||
3393 | //Let's see if the element is present | |
3394 | std::pair<siterator, siterator> to_return | |
3395 | (this->priv_local_equal_range(key, hash_func, equal_func, n_bucket, cnt)); | |
3396 | //If not, find the next element as ".second" if ".second" local iterator | |
3397 | //is not pointing to an element. | |
3398 | bucket_ptr const bp = this->priv_bucket_pointer(); | |
3399 | if(to_return.first != to_return.second && | |
3400 | to_return.second == bp[n_bucket].end()){ | |
3401 | to_return.second = this->priv_invalid_local_it(); | |
3402 | ++n_bucket; | |
3403 | for( const size_type max_bucket = this->priv_bucket_count() | |
3404 | ; n_bucket != max_bucket | |
3405 | ; ++n_bucket){ | |
3406 | bucket_type &b = bp[n_bucket]; | |
3407 | if(!b.empty()){ | |
3408 | to_return.second = b.begin(); | |
3409 | break; | |
3410 | } | |
3411 | } | |
3412 | } | |
3413 | return to_return; | |
3414 | } | |
3415 | ||
3416 | std::size_t priv_get_bucket_num(siterator it) | |
3417 | { return this->priv_get_bucket_num_hash_dispatch(it, store_hash_t()); } | |
3418 | ||
3419 | std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::true_) //store_hash | |
3420 | { | |
3421 | return this->priv_hash_to_bucket | |
3422 | (this->priv_stored_hash(it.pointed_node(), store_hash_t())); | |
3423 | } | |
3424 | ||
3425 | std::size_t priv_get_bucket_num_hash_dispatch(siterator it, detail::false_) //NO store_hash | |
3426 | { return this->priv_get_bucket_num_no_hash_store(it, optimize_multikey_t()); } | |
3427 | ||
3428 | static siterator priv_get_previous(bucket_type &b, siterator i) | |
3429 | { return bucket_plus_vtraits_t::priv_get_previous(b, i, optimize_multikey_t()); } | |
3430 | ||
3431 | /// @endcond | |
3432 | }; | |
3433 | ||
3434 | /// @cond | |
3435 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3436 | template < class T | |
3437 | , bool UniqueKeys | |
3438 | , class PackedOptions | |
3439 | > | |
3440 | #else | |
3441 | template <class T, bool UniqueKeys, class ...Options> | |
3442 | #endif | |
3443 | struct make_bucket_traits | |
3444 | { | |
3445 | //Real value traits must be calculated from options | |
3446 | typedef typename detail::get_value_traits | |
3447 | <T, typename PackedOptions::proto_value_traits>::type value_traits; | |
3448 | ||
3449 | typedef typename PackedOptions::bucket_traits specified_bucket_traits; | |
3450 | ||
3451 | //Real bucket traits must be calculated from options and calculated value_traits | |
3452 | typedef typename detail::get_slist_impl | |
3453 | <typename detail::reduced_slist_node_traits | |
3454 | <typename value_traits::node_traits>::type | |
3455 | >::type slist_impl; | |
3456 | ||
3457 | typedef typename | |
3458 | detail::if_c< detail::is_same | |
3459 | < specified_bucket_traits | |
3460 | , default_bucket_traits | |
3461 | >::value | |
3462 | , detail::bucket_traits_impl<slist_impl> | |
3463 | , specified_bucket_traits | |
3464 | >::type type; | |
3465 | }; | |
3466 | /// @endcond | |
3467 | ||
3468 | //! Helper metafunction to define a \c hashtable that yields to the same type when the | |
3469 | //! same options (either explicitly or implicitly) are used. | |
3470 | #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3471 | template<class T, class ...Options> | |
3472 | #else | |
3473 | template<class T, class O1 = void, class O2 = void | |
3474 | , class O3 = void, class O4 = void | |
3475 | , class O5 = void, class O6 = void | |
3476 | , class O7 = void, class O8 = void | |
3477 | , class O9 = void, class O10= void | |
3478 | > | |
3479 | #endif | |
3480 | struct make_hashtable | |
3481 | { | |
3482 | /// @cond | |
3483 | typedef typename pack_options | |
3484 | < hashtable_defaults, | |
3485 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3486 | O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 | |
3487 | #else | |
3488 | Options... | |
3489 | #endif | |
3490 | >::type packed_options; | |
3491 | ||
3492 | typedef typename detail::get_value_traits | |
3493 | <T, typename packed_options::proto_value_traits>::type value_traits; | |
3494 | ||
3495 | typedef typename make_bucket_traits | |
3496 | <T, false, packed_options>::type bucket_traits; | |
3497 | ||
3498 | typedef hashtable_impl | |
3499 | < value_traits | |
3500 | , typename packed_options::key_of_value | |
3501 | , typename packed_options::hash | |
3502 | , typename packed_options::equal | |
3503 | , bucket_traits | |
3504 | , typename packed_options::size_type | |
3505 | , (std::size_t(false)*hash_bool_flags::unique_keys_pos) | |
3506 | |(std::size_t(packed_options::constant_time_size)*hash_bool_flags::constant_time_size_pos) | |
3507 | |(std::size_t(packed_options::power_2_buckets)*hash_bool_flags::power_2_buckets_pos) | |
3508 | |(std::size_t(packed_options::cache_begin)*hash_bool_flags::cache_begin_pos) | |
3509 | |(std::size_t(packed_options::compare_hash)*hash_bool_flags::compare_hash_pos) | |
3510 | |(std::size_t(packed_options::incremental)*hash_bool_flags::incremental_pos) | |
3511 | > implementation_defined; | |
3512 | ||
3513 | /// @endcond | |
3514 | typedef implementation_defined type; | |
3515 | }; | |
3516 | ||
3517 | #if !defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) | |
3518 | ||
3519 | #if defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3520 | template<class T, class ...Options> | |
3521 | #else | |
3522 | template<class T, class O1, class O2, class O3, class O4, class O5, class O6, class O7, class O8, class O9, class O10> | |
3523 | #endif | |
3524 | class hashtable | |
3525 | : public make_hashtable<T, | |
3526 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3527 | O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 | |
3528 | #else | |
3529 | Options... | |
3530 | #endif | |
3531 | >::type | |
3532 | { | |
3533 | typedef typename make_hashtable<T, | |
3534 | #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES) | |
3535 | O1, O2, O3, O4, O5, O6, O7, O8, O9, O10 | |
3536 | #else | |
3537 | Options... | |
3538 | #endif | |
3539 | >::type Base; | |
3540 | BOOST_MOVABLE_BUT_NOT_COPYABLE(hashtable) | |
3541 | ||
3542 | public: | |
3543 | typedef typename Base::value_traits value_traits; | |
3544 | typedef typename Base::iterator iterator; | |
3545 | typedef typename Base::const_iterator const_iterator; | |
3546 | typedef typename Base::bucket_ptr bucket_ptr; | |
3547 | typedef typename Base::size_type size_type; | |
3548 | typedef typename Base::hasher hasher; | |
3549 | typedef typename Base::bucket_traits bucket_traits; | |
3550 | typedef typename Base::key_equal key_equal; | |
3551 | ||
3552 | //Assert if passed value traits are compatible with the type | |
3553 | BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value)); | |
3554 | ||
3555 | BOOST_INTRUSIVE_FORCEINLINE explicit hashtable ( const bucket_traits &b_traits | |
3556 | , const hasher & hash_func = hasher() | |
3557 | , const key_equal &equal_func = key_equal() | |
3558 | , const value_traits &v_traits = value_traits()) | |
3559 | : Base(b_traits, hash_func, equal_func, v_traits) | |
3560 | {} | |
3561 | ||
3562 | BOOST_INTRUSIVE_FORCEINLINE hashtable(BOOST_RV_REF(hashtable) x) | |
3563 | : Base(BOOST_MOVE_BASE(Base, x)) | |
3564 | {} | |
3565 | ||
3566 | BOOST_INTRUSIVE_FORCEINLINE hashtable& operator=(BOOST_RV_REF(hashtable) x) | |
3567 | { return static_cast<hashtable&>(this->Base::operator=(BOOST_MOVE_BASE(Base, x))); } | |
3568 | ||
3569 | template <class Cloner, class Disposer> | |
3570 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(const hashtable &src, Cloner cloner, Disposer disposer) | |
3571 | { Base::clone_from(src, cloner, disposer); } | |
3572 | ||
3573 | template <class Cloner, class Disposer> | |
3574 | BOOST_INTRUSIVE_FORCEINLINE void clone_from(BOOST_RV_REF(hashtable) src, Cloner cloner, Disposer disposer) | |
3575 | { Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer); } | |
3576 | }; | |
3577 | ||
3578 | #endif | |
3579 | ||
3580 | } //namespace intrusive | |
3581 | } //namespace boost | |
3582 | ||
3583 | #include <boost/intrusive/detail/config_end.hpp> | |
3584 | ||
3585 | #endif //BOOST_INTRUSIVE_HASHTABLE_HPP |