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

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