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

source code of boost/boost/intrusive/hashtable.hpp