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