Line data Source code
1 : // Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
2 : // Copyright (C) 2005-2016 Daniel James
3 : //
4 : // Distributed under the Boost Software License, Version 1.0. (See accompanying
5 : // file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
6 :
7 : #ifndef BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
8 : #define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
9 :
10 : #include <boost/config.hpp>
11 : #if defined(BOOST_HAS_PRAGMA_ONCE)
12 : #pragma once
13 : #endif
14 :
15 : #include <boost/assert.hpp>
16 : #include <boost/core/no_exceptions_support.hpp>
17 : #include <boost/core/pointer_traits.hpp>
18 : #include <boost/detail/select_type.hpp>
19 : #include <boost/limits.hpp>
20 : #include <boost/move/move.hpp>
21 : #include <boost/preprocessor/arithmetic/inc.hpp>
22 : #include <boost/preprocessor/cat.hpp>
23 : #include <boost/preprocessor/repetition/enum.hpp>
24 : #include <boost/preprocessor/repetition/enum_binary_params.hpp>
25 : #include <boost/preprocessor/repetition/enum_params.hpp>
26 : #include <boost/preprocessor/repetition/repeat_from_to.hpp>
27 : #include <boost/preprocessor/seq/enum.hpp>
28 : #include <boost/preprocessor/seq/size.hpp>
29 : #include <boost/swap.hpp>
30 : #include <boost/throw_exception.hpp>
31 : #include <boost/tuple/tuple.hpp>
32 : #include <boost/type_traits/add_lvalue_reference.hpp>
33 : #include <boost/type_traits/aligned_storage.hpp>
34 : #include <boost/type_traits/alignment_of.hpp>
35 : #include <boost/type_traits/integral_constant.hpp>
36 : #include <boost/type_traits/is_base_of.hpp>
37 : #include <boost/type_traits/is_class.hpp>
38 : #include <boost/type_traits/is_empty.hpp>
39 : #include <boost/type_traits/is_nothrow_move_assignable.hpp>
40 : #include <boost/type_traits/is_nothrow_move_constructible.hpp>
41 : #include <boost/type_traits/is_nothrow_swappable.hpp>
42 : #include <boost/type_traits/is_same.hpp>
43 : #include <boost/type_traits/remove_const.hpp>
44 : #include <boost/unordered/detail/fwd.hpp>
45 : #include <boost/utility/addressof.hpp>
46 : #include <boost/utility/enable_if.hpp>
47 : #include <cmath>
48 : #include <iterator>
49 : #include <stdexcept>
50 : #include <utility>
51 :
52 : #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
53 : #include <type_traits>
54 : #endif
55 :
56 : ////////////////////////////////////////////////////////////////////////////////
57 : // Configuration
58 : //
59 : // Unless documented elsewhere these configuration macros should be considered
60 : // an implementation detail, I'll try not to break them, but you never know.
61 :
62 : // Use Sun C++ workarounds
63 : // I'm not sure which versions of the compiler require these workarounds, so
64 : // I'm just using them of everything older than the current test compilers
65 : // (as of May 2017).
66 :
67 : #if !defined(BOOST_UNORDERED_SUN_WORKAROUNDS1)
68 : #if BOOST_COMP_SUNPRO && BOOST_COMP_SUNPRO < BOOST_VERSION_NUMBER(5, 20, 0)
69 : #define BOOST_UNORDERED_SUN_WORKAROUNDS1 1
70 : #else
71 : #define BOOST_UNORDERED_SUN_WORKAROUNDS1 0
72 : #endif
73 : #endif
74 :
75 : // BOOST_UNORDERED_EMPLACE_LIMIT = The maximum number of parameters in
76 : // emplace (not including things like hints). Don't set it to a lower value, as
77 : // that might break something.
78 :
79 : #if !defined BOOST_UNORDERED_EMPLACE_LIMIT
80 : #define BOOST_UNORDERED_EMPLACE_LIMIT 10
81 : #endif
82 :
83 : // BOOST_UNORDERED_USE_ALLOCATOR_TRAITS - Pick which version of
84 : // allocator_traits to use.
85 : //
86 : // 0 = Own partial implementation
87 : // 1 = std::allocator_traits
88 : // 2 = boost::container::allocator_traits
89 :
90 : #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
91 : #if !defined(BOOST_NO_CXX11_ALLOCATOR)
92 : #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 1
93 : #elif defined(BOOST_MSVC)
94 : #if BOOST_MSVC < 1400
95 : // Use container's allocator_traits for older versions of Visual
96 : // C++ as I don't test with them.
97 : #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 2
98 : #endif
99 : #endif
100 : #endif
101 :
102 : #if !defined(BOOST_UNORDERED_USE_ALLOCATOR_TRAITS)
103 : #define BOOST_UNORDERED_USE_ALLOCATOR_TRAITS 0
104 : #endif
105 :
106 : // BOOST_UNORDERED_TUPLE_ARGS
107 : //
108 : // Maximum number of std::tuple members to support, or 0 if std::tuple
109 : // isn't avaiable. More are supported when full C++11 is used.
110 :
111 : // Already defined, so do nothing
112 : #if defined(BOOST_UNORDERED_TUPLE_ARGS)
113 :
114 : // Assume if we have C++11 tuple it's properly variadic,
115 : // and just use a max number of 10 arguments.
116 : #elif !defined(BOOST_NO_CXX11_HDR_TUPLE)
117 : #define BOOST_UNORDERED_TUPLE_ARGS 10
118 :
119 : // Visual C++ has a decent enough tuple for piecewise construction,
120 : // so use that if available, using _VARIADIC_MAX for the maximum
121 : // number of parameters. Note that this comes after the check
122 : // for a full C++11 tuple.
123 : #elif defined(BOOST_MSVC)
124 : #if !BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT
125 : #define BOOST_UNORDERED_TUPLE_ARGS 0
126 : #elif defined(_VARIADIC_MAX)
127 : #define BOOST_UNORDERED_TUPLE_ARGS _VARIADIC_MAX
128 : #else
129 : #define BOOST_UNORDERED_TUPLE_ARGS 5
130 : #endif
131 :
132 : // Assume that we don't have std::tuple
133 : #else
134 : #define BOOST_UNORDERED_TUPLE_ARGS 0
135 : #endif
136 :
137 : #if BOOST_UNORDERED_TUPLE_ARGS
138 : #include <tuple>
139 : #endif
140 :
141 : // BOOST_UNORDERED_CXX11_CONSTRUCTION
142 : //
143 : // Use C++11 construction, requires variadic arguments, good construct support
144 : // in allocator_traits and piecewise construction of std::pair
145 : // Otherwise allocators aren't used for construction/destruction
146 :
147 : #if BOOST_UNORDERED_HAVE_PIECEWISE_CONSTRUCT && \
148 : !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) && BOOST_UNORDERED_TUPLE_ARGS
149 : #if BOOST_COMP_SUNPRO && BOOST_LIB_STD_GNU
150 : // Sun C++ std::pair piecewise construction doesn't seem to be exception safe.
151 : // (At least for Sun C++ 12.5 using libstdc++).
152 : #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
153 : #elif BOOST_COMP_GNUC && BOOST_COMP_GNUC < BOOST_VERSION_NUMBER(4, 7, 0)
154 : // Piecewise construction in GCC 4.6 doesn't work for uncopyable types.
155 : #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
156 : #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0 && \
157 : !defined(BOOST_NO_SFINAE_EXPR)
158 : #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1
159 : #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
160 : #define BOOST_UNORDERED_CXX11_CONSTRUCTION 1
161 : #endif
162 : #endif
163 :
164 : #if !defined(BOOST_UNORDERED_CXX11_CONSTRUCTION)
165 : #define BOOST_UNORDERED_CXX11_CONSTRUCTION 0
166 : #endif
167 :
168 : // BOOST_UNORDERED_SUPPRESS_DEPRECATED
169 : //
170 : // Define to stop deprecation attributes
171 :
172 : #if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED)
173 : #define BOOST_UNORDERED_DEPRECATED(msg)
174 : #endif
175 :
176 : // BOOST_UNORDERED_DEPRECATED
177 : //
178 : // Wrapper around various depreaction attributes.
179 :
180 : #if defined(__has_cpp_attribute) && \
181 : (!defined(__cplusplus) || __cplusplus >= 201402)
182 : #if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED)
183 : #define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]]
184 : #endif
185 : #endif
186 :
187 : #if !defined(BOOST_UNORDERED_DEPRECATED)
188 : #if defined(__GNUC__) && __GNUC__ >= 4
189 : #define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated))
190 : #elif defined(_MSC_VER) && _MSC_VER >= 1400
191 : #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg))
192 : #elif defined(_MSC_VER) && _MSC_VER >= 1310
193 : #define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated)
194 : #else
195 : #define BOOST_UNORDERED_DEPRECATED(msg)
196 : #endif
197 : #endif
198 :
199 : // BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES
200 :
201 : #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES)
202 : #if BOOST_COMP_CLANG && __cplusplus >= 201703
203 : #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 1
204 : #endif
205 : #endif
206 :
207 : #if !defined(BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES)
208 : #define BOOST_UNORDERED_TEMPLATE_DEDUCTION_GUIDES 0
209 : #endif
210 :
211 : namespace boost {
212 : namespace unordered {
213 : namespace iterator_detail {
214 : template <typename Node> struct iterator;
215 : template <typename Node> struct c_iterator;
216 : template <typename Node> struct l_iterator;
217 : template <typename Node> struct cl_iterator;
218 : }
219 : }
220 : }
221 :
222 : namespace boost {
223 : namespace unordered {
224 : namespace detail {
225 :
226 : template <typename Types> struct table;
227 : template <typename NodePointer> struct bucket;
228 : struct ptr_bucket;
229 :
230 : template <typename A, typename T> struct node;
231 : template <typename T> struct ptr_node;
232 :
233 : static const float minimum_max_load_factor = 1e-3f;
234 : static const std::size_t default_bucket_count = 11;
235 :
236 : struct move_tag
237 : {
238 : };
239 :
240 : struct empty_emplace
241 : {
242 : };
243 :
244 : struct no_key
245 : {
246 : no_key() {}
247 : template <class T> no_key(T const&) {}
248 : };
249 :
250 : namespace func {
251 : template <class T> inline void ignore_unused_variable_warning(T const&)
252 : {
253 : }
254 : }
255 :
256 : //////////////////////////////////////////////////////////////////////////
257 : // iterator SFINAE
258 :
259 : template <typename I>
260 : struct is_forward : boost::is_base_of<std::forward_iterator_tag,
261 : typename std::iterator_traits<I>::iterator_category>
262 : {
263 : };
264 :
265 : template <typename I, typename ReturnType>
266 : struct enable_if_forward
267 : : boost::enable_if_c<boost::unordered::detail::is_forward<I>::value,
268 : ReturnType>
269 : {
270 : };
271 :
272 : template <typename I, typename ReturnType>
273 : struct disable_if_forward
274 : : boost::disable_if_c<boost::unordered::detail::is_forward<I>::value,
275 : ReturnType>
276 : {
277 : };
278 : }
279 : }
280 : }
281 :
282 : ////////////////////////////////////////////////////////////////////////////////
283 : // primes
284 :
285 : // clang-format off
286 : #define BOOST_UNORDERED_PRIMES \
287 : (17ul)(29ul)(37ul)(53ul)(67ul)(79ul) \
288 : (97ul)(131ul)(193ul)(257ul)(389ul)(521ul)(769ul) \
289 : (1031ul)(1543ul)(2053ul)(3079ul)(6151ul)(12289ul)(24593ul) \
290 : (49157ul)(98317ul)(196613ul)(393241ul)(786433ul) \
291 : (1572869ul)(3145739ul)(6291469ul)(12582917ul)(25165843ul) \
292 : (50331653ul)(100663319ul)(201326611ul)(402653189ul)(805306457ul) \
293 : (1610612741ul)(3221225473ul)(4294967291ul)
294 : // clang-format on
295 :
296 : namespace boost {
297 : namespace unordered {
298 : namespace detail {
299 : template <class T> struct prime_list_template
300 : {
301 : static std::size_t const value[];
302 :
303 : #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
304 : static std::ptrdiff_t const length;
305 : #else
306 : static std::ptrdiff_t const length =
307 : BOOST_PP_SEQ_SIZE(BOOST_UNORDERED_PRIMES);
308 : #endif
309 : };
310 :
311 : template <class T>
312 : std::size_t const prime_list_template<T>::value[] = {
313 : BOOST_PP_SEQ_ENUM(BOOST_UNORDERED_PRIMES)};
314 :
315 : #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
316 : template <class T>
317 : std::ptrdiff_t const prime_list_template<T>::length = BOOST_PP_SEQ_SIZE(
318 : BOOST_UNORDERED_PRIMES);
319 : #endif
320 :
321 : #undef BOOST_UNORDERED_PRIMES
322 :
323 : typedef prime_list_template<std::size_t> prime_list;
324 :
325 : // no throw
326 0 : inline std::size_t next_prime(std::size_t num)
327 : {
328 0 : std::size_t const* const prime_list_begin = prime_list::value;
329 0 : std::size_t const* const prime_list_end =
330 : prime_list_begin + prime_list::length;
331 0 : std::size_t const* bound =
332 0 : std::lower_bound(prime_list_begin, prime_list_end, num);
333 0 : if (bound == prime_list_end)
334 0 : bound--;
335 0 : return *bound;
336 : }
337 :
338 : // no throw
339 : inline std::size_t prev_prime(std::size_t num)
340 : {
341 : std::size_t const* const prime_list_begin = prime_list::value;
342 : std::size_t const* const prime_list_end =
343 : prime_list_begin + prime_list::length;
344 : std::size_t const* bound =
345 : std::upper_bound(prime_list_begin, prime_list_end, num);
346 : if (bound != prime_list_begin)
347 : bound--;
348 : return *bound;
349 : }
350 :
351 : //////////////////////////////////////////////////////////////////////////
352 : // insert_size/initial_size
353 :
354 : template <class I>
355 0 : inline std::size_t insert_size(I i, I j,
356 : typename boost::unordered::detail::enable_if_forward<I, void*>::type =
357 : 0)
358 : {
359 0 : return static_cast<std::size_t>(std::distance(i, j));
360 : }
361 :
362 : template <class I>
363 : inline std::size_t insert_size(I, I,
364 : typename boost::unordered::detail::disable_if_forward<I, void*>::type =
365 : 0)
366 : {
367 : return 1;
368 : }
369 :
370 : template <class I>
371 : inline std::size_t initial_size(I i, I j,
372 : std::size_t num_buckets =
373 : boost::unordered::detail::default_bucket_count)
374 : {
375 : return (std::max)(
376 : boost::unordered::detail::insert_size(i, j), num_buckets);
377 : }
378 :
379 : //////////////////////////////////////////////////////////////////////////
380 : // compressed
381 :
382 55170 : template <typename T, int Index> struct compressed_base : private T
383 : {
384 304103 : compressed_base(T const& x) : T(x) {}
385 0 : compressed_base(T& x, move_tag) : T(boost::move(x)) {}
386 :
387 5257417 : T& get() { return *this; }
388 671 : T const& get() const { return *this; }
389 : };
390 :
391 : template <typename T, int Index> struct uncompressed_base
392 : {
393 304102 : uncompressed_base(T const& x) : value_(x) {}
394 : uncompressed_base(T& x, move_tag) : value_(boost::move(x)) {}
395 :
396 : T& get() { return value_; }
397 61990022 : T const& get() const { return value_; }
398 :
399 : private:
400 : T value_;
401 : };
402 :
403 : template <typename T, int Index>
404 : struct generate_base
405 : : boost::detail::if_true<
406 : boost::is_empty<T>::value>::BOOST_NESTED_TEMPLATE
407 : then<boost::unordered::detail::compressed_base<T, Index>,
408 : boost::unordered::detail::uncompressed_base<T, Index> >
409 : {
410 : };
411 :
412 : template <typename T1, typename T2>
413 55170 : struct compressed
414 : : private boost::unordered::detail::generate_base<T1, 1>::type,
415 : private boost::unordered::detail::generate_base<T2, 2>::type
416 : {
417 : typedef typename generate_base<T1, 1>::type base1;
418 : typedef typename generate_base<T2, 2>::type base2;
419 :
420 : typedef T1 first_type;
421 : typedef T2 second_type;
422 :
423 102604 : first_type& first() { return static_cast<base1*>(this)->get(); }
424 :
425 40859693 : first_type const& first() const
426 : {
427 16211551 : return static_cast<base1 const*>(this)->get();
428 : }
429 :
430 5154820 : second_type& second() { return static_cast<base2*>(this)->get(); }
431 :
432 56394981 : second_type const& second() const
433 : {
434 13064809 : return static_cast<base2 const*>(this)->get();
435 : }
436 :
437 : template <typename First, typename Second>
438 304103 : compressed(First const& x1, Second const& x2) : base1(x1), base2(x2)
439 : {
440 : }
441 :
442 0 : compressed(compressed const& x) : base1(x.first()), base2(x.second()) {}
443 :
444 0 : compressed(compressed& x, move_tag m)
445 0 : : base1(x.first(), m), base2(x.second(), m)
446 : {
447 : }
448 :
449 : void assign(compressed const& x)
450 : {
451 : first() = x.first();
452 : second() = x.second();
453 : }
454 :
455 : void move_assign(compressed& x)
456 : {
457 : first() = boost::move(x.first());
458 : second() = boost::move(x.second());
459 : }
460 :
461 : void swap(compressed& x)
462 : {
463 : boost::swap(first(), x.first());
464 : boost::swap(second(), x.second());
465 : }
466 :
467 : private:
468 : // Prevent assignment just to make use of assign or
469 : // move_assign explicit.
470 : compressed& operator=(compressed const&);
471 : };
472 :
473 : //////////////////////////////////////////////////////////////////////////
474 : // pair_traits
475 : //
476 : // Used to get the types from a pair without instantiating it.
477 :
478 : template <typename Pair> struct pair_traits
479 : {
480 : typedef typename Pair::first_type first_type;
481 : typedef typename Pair::second_type second_type;
482 : };
483 :
484 : template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> >
485 : {
486 : typedef T1 first_type;
487 : typedef T2 second_type;
488 : };
489 :
490 : #if defined(BOOST_MSVC)
491 : #pragma warning(push)
492 : #pragma warning(disable : 4512) // assignment operator could not be generated.
493 : #pragma warning(disable : 4345) // behavior change: an object of POD type
494 : // constructed with an initializer of the form ()
495 : // will be default-initialized.
496 : #endif
497 :
498 : //////////////////////////////////////////////////////////////////////////
499 : // Bits and pieces for implementing traits
500 :
501 : template <typename T>
502 : typename boost::add_lvalue_reference<T>::type make();
503 : struct choice9
504 : {
505 : typedef char (&type)[9];
506 : };
507 : struct choice8 : choice9
508 : {
509 : typedef char (&type)[8];
510 : };
511 : struct choice7 : choice8
512 : {
513 : typedef char (&type)[7];
514 : };
515 : struct choice6 : choice7
516 : {
517 : typedef char (&type)[6];
518 : };
519 : struct choice5 : choice6
520 : {
521 : typedef char (&type)[5];
522 : };
523 : struct choice4 : choice5
524 : {
525 : typedef char (&type)[4];
526 : };
527 : struct choice3 : choice4
528 : {
529 : typedef char (&type)[3];
530 : };
531 : struct choice2 : choice3
532 : {
533 : typedef char (&type)[2];
534 : };
535 : struct choice1 : choice2
536 : {
537 : typedef char (&type)[1];
538 : };
539 : choice1 choose();
540 :
541 : typedef choice1::type yes_type;
542 : typedef choice2::type no_type;
543 :
544 : struct private_type
545 : {
546 : private_type const& operator,(int) const;
547 : };
548 :
549 : template <typename T> no_type is_private_type(T const&);
550 : yes_type is_private_type(private_type const&);
551 :
552 : struct convert_from_anything
553 : {
554 : template <typename T> convert_from_anything(T const&);
555 : };
556 : }
557 : }
558 : }
559 :
560 : ////////////////////////////////////////////////////////////////////////////
561 : // emplace_args
562 : //
563 : // Either forwarding variadic arguments, or storing the arguments in
564 : // emplace_args##n
565 :
566 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
567 :
568 : #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
569 : #define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
570 : #define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)...
571 :
572 : #else
573 :
574 : #define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
575 : #define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
576 : #define BOOST_UNORDERED_EMPLACE_FORWARD args
577 :
578 : #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
579 :
580 : #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
581 : typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
582 : BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
583 :
584 : #else
585 :
586 : #define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
587 : typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \
588 : BOOST_PP_CAT(Arg, n); \
589 : BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
590 :
591 : #endif
592 :
593 : #define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
594 : BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
595 :
596 : #define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
597 : boost::forward<BOOST_PP_CAT(A, i)>(BOOST_PP_CAT(a, i))
598 :
599 : #define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
600 : BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
601 :
602 : #define BOOST_UNORDERED_EARGS(z, n, _) \
603 : template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
604 : struct BOOST_PP_CAT(emplace_args, n) \
605 : { \
606 : BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) BOOST_PP_CAT( \
607 : emplace_args, n)(BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)) \
608 : : BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
609 : { \
610 : } \
611 : }; \
612 : \
613 : template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
614 : inline BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> \
615 : create_emplace_args(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)) \
616 : { \
617 : BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> e( \
618 : BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
619 : return e; \
620 : }
621 :
622 : namespace boost {
623 : namespace unordered {
624 : namespace detail {
625 : template <typename A0> struct emplace_args1
626 : {
627 : BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
628 :
629 : explicit emplace_args1(Arg0 b0) : a0(b0) {}
630 : };
631 :
632 : template <typename A0>
633 : inline emplace_args1<A0> create_emplace_args(BOOST_FWD_REF(A0) b0)
634 : {
635 : emplace_args1<A0> e(b0);
636 : return e;
637 : }
638 :
639 : template <typename A0, typename A1> struct emplace_args2
640 : {
641 : BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
642 : BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
643 :
644 : emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {}
645 : };
646 :
647 : template <typename A0, typename A1>
648 : inline emplace_args2<A0, A1> create_emplace_args(
649 : BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1)
650 : {
651 : emplace_args2<A0, A1> e(b0, b1);
652 : return e;
653 : }
654 :
655 : template <typename A0, typename A1, typename A2> struct emplace_args3
656 : {
657 : BOOST_UNORDERED_EARGS_MEMBER(1, 0, _)
658 : BOOST_UNORDERED_EARGS_MEMBER(1, 1, _)
659 : BOOST_UNORDERED_EARGS_MEMBER(1, 2, _)
660 :
661 : emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {}
662 : };
663 :
664 : template <typename A0, typename A1, typename A2>
665 : inline emplace_args3<A0, A1, A2> create_emplace_args(
666 : BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1, BOOST_FWD_REF(A2) b2)
667 : {
668 : emplace_args3<A0, A1, A2> e(b0, b1, b2);
669 : return e;
670 : }
671 :
672 : BOOST_UNORDERED_EARGS(1, 4, _)
673 : BOOST_UNORDERED_EARGS(1, 5, _)
674 : BOOST_UNORDERED_EARGS(1, 6, _)
675 : BOOST_UNORDERED_EARGS(1, 7, _)
676 : BOOST_UNORDERED_EARGS(1, 8, _)
677 : BOOST_UNORDERED_EARGS(1, 9, _)
678 : BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
679 : BOOST_UNORDERED_EARGS, _)
680 : }
681 : }
682 : }
683 :
684 : #undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
685 : #undef BOOST_UNORDERED_EARGS_MEMBER
686 : #undef BOOST_UNORDERED_EARGS_INIT
687 :
688 : #endif
689 :
690 : ////////////////////////////////////////////////////////////////////////////////
691 : //
692 : // Some utilities for implementing allocator_traits, but useful elsewhere so
693 : // they're always defined.
694 :
695 : namespace boost {
696 : namespace unordered {
697 : namespace detail {
698 :
699 : ////////////////////////////////////////////////////////////////////////////
700 : // Integral_constrant, true_type, false_type
701 : //
702 : // Uses the standard versions if available.
703 :
704 : #if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
705 :
706 : using std::integral_constant;
707 : using std::true_type;
708 : using std::false_type;
709 :
710 : #else
711 :
712 : template <typename T, T Value> struct integral_constant
713 : {
714 : enum
715 : {
716 : value = Value
717 : };
718 : };
719 :
720 : typedef boost::unordered::detail::integral_constant<bool, true> true_type;
721 : typedef boost::unordered::detail::integral_constant<bool, false>
722 : false_type;
723 :
724 : #endif
725 :
726 : ////////////////////////////////////////////////////////////////////////////
727 : // Explicitly call a destructor
728 :
729 : #if defined(BOOST_MSVC)
730 : #pragma warning(push)
731 : #pragma warning(disable : 4100) // unreferenced formal parameter
732 : #endif
733 :
734 : namespace func {
735 183546 : template <class T> inline void destroy(T* x) { x->~T(); }
736 : }
737 :
738 : #if defined(BOOST_MSVC)
739 : #pragma warning(pop)
740 : #endif
741 :
742 : //////////////////////////////////////////////////////////////////////////
743 : // value_base
744 : //
745 : // Space used to store values.
746 :
747 : template <typename ValueType> struct value_base
748 : {
749 : typedef ValueType value_type;
750 :
751 : typename boost::aligned_storage<sizeof(value_type),
752 : boost::alignment_of<value_type>::value>::type data_;
753 :
754 : value_base() : data_() {}
755 :
756 : void* address() { return this; }
757 :
758 70494441 : value_type& value() { return *(ValueType*)this; }
759 :
760 : value_type const& value() const { return *(ValueType const*)this; }
761 :
762 73826092 : value_type* value_ptr() { return (ValueType*)this; }
763 :
764 : value_type const* value_ptr() const { return (ValueType const*)this; }
765 :
766 : private:
767 : value_base& operator=(value_base const&);
768 : };
769 :
770 : //////////////////////////////////////////////////////////////////////////
771 : // optional
772 : // TODO: Use std::optional when available.
773 :
774 : template <typename T> class optional
775 : {
776 : BOOST_MOVABLE_BUT_NOT_COPYABLE(optional)
777 :
778 : boost::unordered::detail::value_base<T> value_;
779 : bool has_value_;
780 :
781 : void destroy()
782 : {
783 : if (has_value_) {
784 : boost::unordered::detail::func::destroy(value_.value_ptr());
785 : has_value_ = false;
786 : }
787 : }
788 :
789 : void move(optional<T>& x)
790 : {
791 : BOOST_ASSERT(!has_value_ && x.has_value_);
792 : new (value_.value_ptr()) T(boost::move(x.value_.value()));
793 : boost::unordered::detail::func::destroy(x.value_.value_ptr());
794 : has_value_ = true;
795 : x.has_value_ = false;
796 : }
797 :
798 : public:
799 : optional() BOOST_NOEXCEPT : has_value_(false) {}
800 :
801 : optional(BOOST_RV_REF(optional<T>) x) : has_value_(false)
802 : {
803 : if (x.has_value_) {
804 : move(x);
805 : }
806 : }
807 :
808 : explicit optional(T const& x) : has_value_(true)
809 : {
810 : new (value_.value_ptr()) T(x);
811 : }
812 :
813 : optional& operator=(BOOST_RV_REF(optional<T>) x)
814 : {
815 : destroy();
816 : if (x.has_value_) {
817 : move(x);
818 : }
819 : return *this;
820 : }
821 :
822 : ~optional() { destroy(); }
823 :
824 : bool has_value() const { return has_value_; }
825 : T& operator*() { return value_.value(); }
826 : T const& operator*() const { return value_.value(); }
827 : T* operator->() { return value_.value_ptr(); }
828 : T const* operator->() const { return value_.value_ptr(); }
829 :
830 : bool operator==(optional<T> const& x)
831 : {
832 : return has_value_ ? x.has_value_ && value_.value() == x.value_.value()
833 : : !x.has_value_;
834 : }
835 :
836 : bool operator!=(optional<T> const& x) { return !((*this) == x); }
837 :
838 : void swap(optional<T>& x)
839 : {
840 : if (has_value_ != x.has_value_) {
841 : if (has_value_) {
842 : x.move(*this);
843 : } else {
844 : move(x);
845 : }
846 : } else if (has_value_) {
847 : boost::swap(value_.value(), x.value_.value());
848 : }
849 : }
850 :
851 : friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); }
852 : };
853 : }
854 : }
855 : }
856 :
857 : ////////////////////////////////////////////////////////////////////////////
858 : // Expression test mechanism
859 : //
860 : // When SFINAE expressions are available, define
861 : // BOOST_UNORDERED_HAS_FUNCTION which can check if a function call is
862 : // supported by a class, otherwise define BOOST_UNORDERED_HAS_MEMBER which
863 : // can detect if a class has the specified member, but not that it has the
864 : // correct type, this is good enough for a passable impression of
865 : // allocator_traits.
866 :
867 : #if !defined(BOOST_NO_SFINAE_EXPR)
868 :
869 : namespace boost {
870 : namespace unordered {
871 : namespace detail {
872 : template <typename T, long unsigned int> struct expr_test;
873 : template <typename T> struct expr_test<T, sizeof(char)> : T
874 : {
875 : };
876 : }
877 : }
878 : }
879 :
880 : #define BOOST_UNORDERED_CHECK_EXPRESSION(count, result, expression) \
881 : template <typename U> \
882 : static \
883 : typename boost::unordered::detail::expr_test<BOOST_PP_CAT(choice, result), \
884 : sizeof(for_expr_test(((expression), 0)))>::type \
885 : test(BOOST_PP_CAT(choice, count))
886 :
887 : #define BOOST_UNORDERED_DEFAULT_EXPRESSION(count, result) \
888 : template <typename U> \
889 : static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count))
890 :
891 : #define BOOST_UNORDERED_HAS_FUNCTION(name, thing, args, _) \
892 : struct BOOST_PP_CAT(has_, name) \
893 : { \
894 : template <typename U> static char for_expr_test(U const&); \
895 : BOOST_UNORDERED_CHECK_EXPRESSION( \
896 : 1, 1, boost::unordered::detail::make<thing>().name args); \
897 : BOOST_UNORDERED_DEFAULT_EXPRESSION(2, 2); \
898 : \
899 : enum \
900 : { \
901 : value = sizeof(test<T>(choose())) == sizeof(choice1::type) \
902 : }; \
903 : }
904 :
905 : #else
906 :
907 : namespace boost {
908 : namespace unordered {
909 : namespace detail {
910 : template <typename T> struct identity
911 : {
912 : typedef T type;
913 : };
914 : }
915 : }
916 : }
917 :
918 : #define BOOST_UNORDERED_CHECK_MEMBER(count, result, name, member) \
919 : \
920 : typedef \
921 : typename boost::unordered::detail::identity<member>::type BOOST_PP_CAT( \
922 : check, count); \
923 : \
924 : template <BOOST_PP_CAT(check, count) e> struct BOOST_PP_CAT(test, count) \
925 : { \
926 : typedef BOOST_PP_CAT(choice, result) type; \
927 : }; \
928 : \
929 : template <class U> \
930 : static typename BOOST_PP_CAT(test, count)<&U::name>::type test( \
931 : BOOST_PP_CAT(choice, count))
932 :
933 : #define BOOST_UNORDERED_DEFAULT_MEMBER(count, result) \
934 : template <class U> \
935 : static BOOST_PP_CAT(choice, result)::type test(BOOST_PP_CAT(choice, count))
936 :
937 : #define BOOST_UNORDERED_HAS_MEMBER(name) \
938 : struct BOOST_PP_CAT(has_, name) \
939 : { \
940 : struct impl \
941 : { \
942 : struct base_mixin \
943 : { \
944 : int name; \
945 : }; \
946 : struct base : public T, public base_mixin \
947 : { \
948 : }; \
949 : \
950 : BOOST_UNORDERED_CHECK_MEMBER(1, 1, name, int base_mixin::*); \
951 : BOOST_UNORDERED_DEFAULT_MEMBER(2, 2); \
952 : \
953 : enum \
954 : { \
955 : value = sizeof(choice2::type) == sizeof(test<base>(choose())) \
956 : }; \
957 : }; \
958 : \
959 : enum \
960 : { \
961 : value = impl::value \
962 : }; \
963 : }
964 :
965 : #endif
966 :
967 : ////////////////////////////////////////////////////////////////////////////
968 : // TRAITS TYPE DETECTION MECHANISM
969 : //
970 : // Used to implement traits that use a type if present, or a
971 : // default otherwise.
972 :
973 : #if defined(BOOST_MSVC) && BOOST_MSVC <= 1400
974 :
975 : #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
976 : template <typename Tp, typename Default> struct default_type_##tname \
977 : { \
978 : \
979 : template <typename X> \
980 : static choice1::type test(choice1, typename X::tname* = 0); \
981 : \
982 : template <typename X> static choice2::type test(choice2, void* = 0); \
983 : \
984 : struct DefaultWrap \
985 : { \
986 : typedef Default tname; \
987 : }; \
988 : \
989 : enum \
990 : { \
991 : value = (1 == sizeof(test<Tp>(choose()))) \
992 : }; \
993 : \
994 : typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \
995 : then<Tp, DefaultWrap>::type::tname type; \
996 : }
997 :
998 : #else
999 :
1000 : namespace boost {
1001 : namespace unordered {
1002 : namespace detail {
1003 : template <typename T, typename T2> struct sfinae : T2
1004 : {
1005 : };
1006 : }
1007 : }
1008 : }
1009 :
1010 : #define BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(tname) \
1011 : template <typename Tp, typename Default> struct default_type_##tname \
1012 : { \
1013 : \
1014 : template <typename X> \
1015 : static typename boost::unordered::detail::sfinae<typename X::tname, \
1016 : choice1>::type test(choice1); \
1017 : \
1018 : template <typename X> static choice2::type test(choice2); \
1019 : \
1020 : struct DefaultWrap \
1021 : { \
1022 : typedef Default tname; \
1023 : }; \
1024 : \
1025 : enum \
1026 : { \
1027 : value = (1 == sizeof(test<Tp>(choose()))) \
1028 : }; \
1029 : \
1030 : typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE \
1031 : then<Tp, DefaultWrap>::type::tname type; \
1032 : }
1033 :
1034 : #endif
1035 :
1036 : #define BOOST_UNORDERED_DEFAULT_TYPE(T, tname, arg) \
1037 : typename default_type_##tname<T, arg>::type
1038 :
1039 : ////////////////////////////////////////////////////////////////////////////////
1040 : //
1041 : // Allocator traits
1042 : //
1043 : // First our implementation, then later light wrappers around the alternatives
1044 :
1045 : #if BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 0
1046 :
1047 : #include <boost/limits.hpp>
1048 : #include <boost/pointer_to_other.hpp>
1049 : #include <boost/utility/enable_if.hpp>
1050 :
1051 : namespace boost {
1052 : namespace unordered {
1053 : namespace detail {
1054 :
1055 : template <typename Alloc, typename T> struct rebind_alloc;
1056 :
1057 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1058 :
1059 : template <template <typename, typename...> class Alloc, typename U,
1060 : typename T, typename... Args>
1061 : struct rebind_alloc<Alloc<U, Args...>, T>
1062 : {
1063 : typedef Alloc<T, Args...> type;
1064 : };
1065 :
1066 : #else
1067 :
1068 : template <template <typename> class Alloc, typename U, typename T>
1069 : struct rebind_alloc<Alloc<U>, T>
1070 : {
1071 : typedef Alloc<T> type;
1072 : };
1073 :
1074 : template <template <typename, typename> class Alloc, typename U,
1075 : typename T, typename A0>
1076 : struct rebind_alloc<Alloc<U, A0>, T>
1077 : {
1078 : typedef Alloc<T, A0> type;
1079 : };
1080 :
1081 : template <template <typename, typename, typename> class Alloc, typename U,
1082 : typename T, typename A0, typename A1>
1083 : struct rebind_alloc<Alloc<U, A0, A1>, T>
1084 : {
1085 : typedef Alloc<T, A0, A1> type;
1086 : };
1087 :
1088 : #endif
1089 :
1090 : template <typename Alloc, typename T> struct rebind_wrap
1091 : {
1092 : template <typename X>
1093 : static choice1::type test(
1094 : choice1, typename X::BOOST_NESTED_TEMPLATE rebind<T>::other* = 0);
1095 : template <typename X> static choice2::type test(choice2, void* = 0);
1096 :
1097 : enum
1098 : {
1099 : value = (1 == sizeof(test<Alloc>(choose())))
1100 : };
1101 :
1102 : struct fallback
1103 : {
1104 : template <typename U> struct rebind
1105 : {
1106 : typedef typename rebind_alloc<Alloc, T>::type other;
1107 : };
1108 : };
1109 :
1110 : typedef
1111 : typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE then<
1112 : Alloc, fallback>::type::BOOST_NESTED_TEMPLATE rebind<T>::other type;
1113 : };
1114 : }
1115 : }
1116 : }
1117 :
1118 : namespace boost {
1119 : namespace unordered {
1120 : namespace detail {
1121 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(pointer);
1122 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_pointer);
1123 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(void_pointer);
1124 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(const_void_pointer);
1125 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(difference_type);
1126 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(size_type);
1127 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(
1128 : propagate_on_container_copy_assignment);
1129 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(
1130 : propagate_on_container_move_assignment);
1131 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(propagate_on_container_swap);
1132 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal);
1133 :
1134 : #if !defined(BOOST_NO_SFINAE_EXPR)
1135 :
1136 : template <typename T>
1137 : BOOST_UNORDERED_HAS_FUNCTION(
1138 : select_on_container_copy_construction, U const, (), 0);
1139 :
1140 : template <typename T>
1141 : BOOST_UNORDERED_HAS_FUNCTION(max_size, U const, (), 0);
1142 :
1143 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1144 :
1145 : template <typename T, typename ValueType, typename... Args>
1146 : BOOST_UNORDERED_HAS_FUNCTION(construct, U,
1147 : (boost::unordered::detail::make<ValueType*>(),
1148 : boost::unordered::detail::make<Args const>()...),
1149 : 2);
1150 :
1151 : #else
1152 :
1153 : template <typename T, typename ValueType>
1154 : BOOST_UNORDERED_HAS_FUNCTION(construct, U,
1155 : (boost::unordered::detail::make<ValueType*>(),
1156 : boost::unordered::detail::make<ValueType const>()),
1157 : 2);
1158 :
1159 : #endif
1160 :
1161 : template <typename T, typename ValueType>
1162 : BOOST_UNORDERED_HAS_FUNCTION(
1163 : destroy, U, (boost::unordered::detail::make<ValueType*>()), 1);
1164 :
1165 : #else
1166 :
1167 : template <typename T>
1168 : BOOST_UNORDERED_HAS_MEMBER(select_on_container_copy_construction);
1169 :
1170 : template <typename T> BOOST_UNORDERED_HAS_MEMBER(max_size);
1171 :
1172 : template <typename T, typename ValueType>
1173 : BOOST_UNORDERED_HAS_MEMBER(construct);
1174 :
1175 : template <typename T, typename ValueType>
1176 : BOOST_UNORDERED_HAS_MEMBER(destroy);
1177 :
1178 : #endif
1179 : }
1180 : }
1181 : }
1182 :
1183 : namespace boost {
1184 : namespace unordered {
1185 : namespace detail {
1186 : namespace func {
1187 :
1188 : template <typename Alloc>
1189 : inline Alloc call_select_on_container_copy_construction(
1190 : const Alloc& rhs,
1191 : typename boost::enable_if_c<
1192 : boost::unordered::detail::has_select_on_container_copy_construction<
1193 : Alloc>::value,
1194 : void*>::type = 0)
1195 : {
1196 : return rhs.select_on_container_copy_construction();
1197 : }
1198 :
1199 : template <typename Alloc>
1200 : inline Alloc call_select_on_container_copy_construction(
1201 : const Alloc& rhs,
1202 : typename boost::disable_if_c<
1203 : boost::unordered::detail::has_select_on_container_copy_construction<
1204 : Alloc>::value,
1205 : void*>::type = 0)
1206 : {
1207 : return rhs;
1208 : }
1209 :
1210 : template <typename SizeType, typename Alloc>
1211 : inline SizeType call_max_size(const Alloc& a,
1212 : typename boost::enable_if_c<
1213 : boost::unordered::detail::has_max_size<Alloc>::value, void*>::type =
1214 : 0)
1215 : {
1216 : return a.max_size();
1217 : }
1218 :
1219 : template <typename SizeType, typename Alloc>
1220 : inline SizeType call_max_size(const Alloc&,
1221 : typename boost::disable_if_c<
1222 : boost::unordered::detail::has_max_size<Alloc>::value, void*>::type =
1223 : 0)
1224 : {
1225 : return (std::numeric_limits<SizeType>::max)();
1226 : }
1227 : } // namespace func.
1228 : }
1229 : }
1230 : }
1231 :
1232 : namespace boost {
1233 : namespace unordered {
1234 : namespace detail {
1235 : template <typename Alloc> struct allocator_traits
1236 : {
1237 : typedef Alloc allocator_type;
1238 : typedef typename Alloc::value_type value_type;
1239 :
1240 : typedef BOOST_UNORDERED_DEFAULT_TYPE(
1241 : Alloc, pointer, value_type*) pointer;
1242 :
1243 : template <typename T>
1244 : struct pointer_to_other : boost::pointer_to_other<pointer, T>
1245 : {
1246 : };
1247 :
1248 : typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_pointer,
1249 : typename pointer_to_other<const value_type>::type) const_pointer;
1250 :
1251 : // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, void_pointer,
1252 : // typename pointer_to_other<void>::type)
1253 : // void_pointer;
1254 : //
1255 : // typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, const_void_pointer,
1256 : // typename pointer_to_other<const void>::type)
1257 : // const_void_pointer;
1258 :
1259 : typedef BOOST_UNORDERED_DEFAULT_TYPE(
1260 : Alloc, difference_type, std::ptrdiff_t) difference_type;
1261 :
1262 : typedef BOOST_UNORDERED_DEFAULT_TYPE(
1263 : Alloc, size_type, std::size_t) size_type;
1264 :
1265 : #if !defined(BOOST_NO_CXX11_TEMPLATE_ALIASES)
1266 : template <typename T>
1267 : using rebind_alloc = typename rebind_wrap<Alloc, T>::type;
1268 :
1269 : template <typename T>
1270 : using rebind_traits =
1271 : boost::unordered::detail::allocator_traits<rebind_alloc<T> >;
1272 : #endif
1273 :
1274 : static pointer allocate(Alloc& a, size_type n) { return a.allocate(n); }
1275 :
1276 : // I never use this, so I'll just comment it out for now.
1277 : //
1278 : // static pointer allocate(Alloc& a, size_type n,
1279 : // const_void_pointer hint)
1280 : // { return DEFAULT_FUNC(allocate, pointer)(a, n, hint); }
1281 :
1282 : static void deallocate(Alloc& a, pointer p, size_type n)
1283 : {
1284 : a.deallocate(p, n);
1285 : }
1286 :
1287 : public:
1288 : #if BOOST_UNORDERED_CXX11_CONSTRUCTION
1289 :
1290 : template <typename T, typename... Args>
1291 : static
1292 : typename boost::enable_if_c<boost::unordered::detail::has_construct<
1293 : Alloc, T, Args...>::value>::type
1294 : construct(Alloc& a, T* p, BOOST_FWD_REF(Args)... x)
1295 : {
1296 : a.construct(p, boost::forward<Args>(x)...);
1297 : }
1298 :
1299 : template <typename T, typename... Args>
1300 : static
1301 : typename boost::disable_if_c<boost::unordered::detail::has_construct<
1302 : Alloc, T, Args...>::value>::type
1303 : construct(Alloc&, T* p, BOOST_FWD_REF(Args)... x)
1304 : {
1305 : new (static_cast<void*>(p)) T(boost::forward<Args>(x)...);
1306 : }
1307 :
1308 : template <typename T>
1309 : static typename boost::enable_if_c<
1310 : boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1311 : destroy(Alloc& a, T* p)
1312 : {
1313 : a.destroy(p);
1314 : }
1315 :
1316 : template <typename T>
1317 : static typename boost::disable_if_c<
1318 : boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1319 : destroy(Alloc&, T* p)
1320 : {
1321 : boost::unordered::detail::func::destroy(p);
1322 : }
1323 :
1324 : #elif !defined(BOOST_NO_SFINAE_EXPR)
1325 :
1326 : template <typename T>
1327 : static typename boost::enable_if_c<
1328 : boost::unordered::detail::has_construct<Alloc, T>::value>::type
1329 : construct(Alloc& a, T* p, T const& x)
1330 : {
1331 : a.construct(p, x);
1332 : }
1333 :
1334 : template <typename T>
1335 : static typename boost::disable_if_c<
1336 : boost::unordered::detail::has_construct<Alloc, T>::value>::type
1337 : construct(Alloc&, T* p, T const& x)
1338 : {
1339 : new (static_cast<void*>(p)) T(x);
1340 : }
1341 :
1342 : template <typename T>
1343 : static typename boost::enable_if_c<
1344 : boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1345 : destroy(Alloc& a, T* p)
1346 : {
1347 : a.destroy(p);
1348 : }
1349 :
1350 : template <typename T>
1351 : static typename boost::disable_if_c<
1352 : boost::unordered::detail::has_destroy<Alloc, T>::value>::type
1353 : destroy(Alloc&, T* p)
1354 : {
1355 : boost::unordered::detail::func::destroy(p);
1356 : }
1357 :
1358 : #else
1359 :
1360 : // If we don't have SFINAE expressions, only call construct for the
1361 : // copy constructor for the allocator's value_type - as that's
1362 : // the only construct method that old fashioned allocators support.
1363 :
1364 : template <typename T>
1365 : static void construct(Alloc& a, T* p, T const& x,
1366 : typename boost::enable_if_c<
1367 : boost::unordered::detail::has_construct<Alloc, T>::value &&
1368 : boost::is_same<T, value_type>::value,
1369 : void*>::type = 0)
1370 : {
1371 : a.construct(p, x);
1372 : }
1373 :
1374 : template <typename T>
1375 : static void construct(Alloc&, T* p, T const& x,
1376 : typename boost::disable_if_c<
1377 : boost::unordered::detail::has_construct<Alloc, T>::value &&
1378 : boost::is_same<T, value_type>::value,
1379 : void*>::type = 0)
1380 : {
1381 : new (static_cast<void*>(p)) T(x);
1382 : }
1383 :
1384 : template <typename T>
1385 : static void destroy(Alloc& a, T* p,
1386 : typename boost::enable_if_c<
1387 : boost::unordered::detail::has_destroy<Alloc, T>::value &&
1388 : boost::is_same<T, value_type>::value,
1389 : void*>::type = 0)
1390 : {
1391 : a.destroy(p);
1392 : }
1393 :
1394 : template <typename T>
1395 : static void destroy(Alloc&, T* p,
1396 : typename boost::disable_if_c<
1397 : boost::unordered::detail::has_destroy<Alloc, T>::value &&
1398 : boost::is_same<T, value_type>::value,
1399 : void*>::type = 0)
1400 : {
1401 : boost::unordered::detail::func::destroy(p);
1402 : }
1403 :
1404 : #endif
1405 :
1406 : static size_type max_size(const Alloc& a)
1407 : {
1408 : return boost::unordered::detail::func::call_max_size<size_type>(a);
1409 : }
1410 :
1411 : // Allocator propagation on construction
1412 :
1413 : static Alloc select_on_container_copy_construction(Alloc const& rhs)
1414 : {
1415 : return boost::unordered::detail::func::
1416 : call_select_on_container_copy_construction(rhs);
1417 : }
1418 :
1419 : // Allocator propagation on assignment and swap.
1420 : // Return true if lhs is modified.
1421 : typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc,
1422 : propagate_on_container_copy_assignment,
1423 : false_type) propagate_on_container_copy_assignment;
1424 : typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc,
1425 : propagate_on_container_move_assignment,
1426 : false_type) propagate_on_container_move_assignment;
1427 : typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, propagate_on_container_swap,
1428 : false_type) propagate_on_container_swap;
1429 :
1430 : typedef BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal,
1431 : typename boost::is_empty<Alloc>::type) is_always_equal;
1432 : };
1433 : }
1434 : }
1435 : }
1436 :
1437 : #undef BOOST_UNORDERED_DEFAULT_TYPE_TMPLT
1438 : #undef BOOST_UNORDERED_DEFAULT_TYPE
1439 :
1440 : ////////////////////////////////////////////////////////////////////////////////
1441 : //
1442 : // std::allocator_traits
1443 :
1444 : #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 1
1445 :
1446 : #include <memory>
1447 :
1448 : namespace boost {
1449 : namespace unordered {
1450 : namespace detail {
1451 :
1452 : BOOST_UNORDERED_DEFAULT_TYPE_TMPLT(is_always_equal);
1453 :
1454 : template <typename Alloc>
1455 : struct allocator_traits : std::allocator_traits<Alloc>
1456 : {
1457 : // As is_always_equal was introduced in C++17, std::allocator_traits
1458 : // doesn't always have it. So use it when available, implement it
1459 : // ourselves when not. Would be simpler not to bother with
1460 : // std::allocator_traits, but I feel like I should try to use
1461 : // it where possible.
1462 : typedef BOOST_UNORDERED_DEFAULT_TYPE(std::allocator_traits<Alloc>,
1463 : is_always_equal,
1464 : BOOST_UNORDERED_DEFAULT_TYPE(Alloc, is_always_equal,
1465 : typename boost::is_empty<Alloc>::type)) is_always_equal;
1466 : };
1467 :
1468 : template <typename Alloc, typename T> struct rebind_wrap
1469 : {
1470 : typedef typename std::allocator_traits<Alloc>::template rebind_alloc<T>
1471 : type;
1472 : };
1473 : }
1474 : }
1475 : }
1476 :
1477 : ////////////////////////////////////////////////////////////////////////////////
1478 : //
1479 : // boost::container::allocator_traits
1480 :
1481 : #elif BOOST_UNORDERED_USE_ALLOCATOR_TRAITS == 2
1482 :
1483 : #include <boost/container/allocator_traits.hpp>
1484 :
1485 : namespace boost {
1486 : namespace unordered {
1487 : namespace detail {
1488 :
1489 : template <typename Alloc>
1490 : struct allocator_traits : boost::container::allocator_traits<Alloc>
1491 : {
1492 : };
1493 :
1494 : template <typename Alloc, typename T>
1495 : struct rebind_wrap : boost::container::allocator_traits<
1496 : Alloc>::template portable_rebind_alloc<T>
1497 : {
1498 : };
1499 : }
1500 : }
1501 : }
1502 :
1503 : #else
1504 :
1505 : #error "Invalid BOOST_UNORDERED_USE_ALLOCATOR_TRAITS value."
1506 :
1507 : #endif
1508 :
1509 : ////////////////////////////////////////////////////////////////////////////
1510 : // Functions used to construct nodes. Emulates variadic construction,
1511 : // piecewise construction etc.
1512 :
1513 : ////////////////////////////////////////////////////////////////////////////
1514 : // construct_value
1515 : //
1516 : // Only use allocator_traits::construct, allocator_traits::destroy when full
1517 : // C++11 support is available.
1518 :
1519 : #if BOOST_UNORDERED_CXX11_CONSTRUCTION
1520 :
1521 : #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1522 : Traits::construct(alloc, address, a0)
1523 : #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) Traits::destroy(alloc, x)
1524 :
1525 : #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1526 :
1527 : namespace boost {
1528 : namespace unordered {
1529 : namespace detail {
1530 : namespace func {
1531 : template <typename T, typename... Args>
1532 : inline void construct_value(T* address, BOOST_FWD_REF(Args)... args)
1533 : {
1534 : new ((void*)address) T(boost::forward<Args>(args)...);
1535 : }
1536 : }
1537 : }
1538 : }
1539 : }
1540 :
1541 : #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1542 : boost::unordered::detail::func::construct_value(address, a0)
1543 : #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \
1544 : boost::unordered::detail::func::destroy(x)
1545 :
1546 : #else
1547 :
1548 : namespace boost {
1549 : namespace unordered {
1550 : namespace detail {
1551 : namespace func {
1552 : template <typename T> inline void construct_value(T* address)
1553 : {
1554 : new ((void*)address) T();
1555 : }
1556 :
1557 : template <typename T, typename A0>
1558 : inline void construct_value(T* address, BOOST_FWD_REF(A0) a0)
1559 : {
1560 : new ((void*)address) T(boost::forward<A0>(a0));
1561 : }
1562 : }
1563 : }
1564 : }
1565 : }
1566 :
1567 : #define BOOST_UNORDERED_CALL_CONSTRUCT1(Traits, alloc, address, a0) \
1568 : boost::unordered::detail::func::construct_value(address, a0)
1569 : #define BOOST_UNORDERED_CALL_DESTROY(Traits, alloc, x) \
1570 : boost::unordered::detail::func::destroy(x)
1571 :
1572 : #endif
1573 :
1574 : ////////////////////////////////////////////////////////////////////////////
1575 : // Construct from tuple
1576 : //
1577 : // Used to emulate piecewise construction.
1578 :
1579 : #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
1580 : template <typename Alloc, typename T, \
1581 : BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1582 : void construct_from_tuple(Alloc&, T* ptr, \
1583 : namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
1584 : { \
1585 : new ((void*)ptr) \
1586 : T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
1587 : }
1588 :
1589 : #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
1590 :
1591 : // construct_from_tuple for boost::tuple
1592 : // The workaround for old Sun compilers comes later in the file.
1593 :
1594 : #if !BOOST_UNORDERED_SUN_WORKAROUNDS1
1595 :
1596 : namespace boost {
1597 : namespace unordered {
1598 : namespace detail {
1599 : namespace func {
1600 : template <typename Alloc, typename T>
1601 : void construct_from_tuple(Alloc&, T* ptr, boost::tuple<>)
1602 : {
1603 : new ((void*)ptr) T();
1604 : }
1605 :
1606 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost)
1607 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost)
1608 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost)
1609 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost)
1610 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost)
1611 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost)
1612 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost)
1613 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost)
1614 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost)
1615 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost)
1616 : }
1617 : }
1618 : }
1619 : }
1620 :
1621 : #endif
1622 :
1623 : // construct_from_tuple for std::tuple
1624 :
1625 : #if !BOOST_UNORDERED_CXX11_CONSTRUCTION && BOOST_UNORDERED_TUPLE_ARGS
1626 :
1627 : namespace boost {
1628 : namespace unordered {
1629 : namespace detail {
1630 : namespace func {
1631 : template <typename Alloc, typename T>
1632 : void construct_from_tuple(Alloc&, T* ptr, std::tuple<>)
1633 : {
1634 : new ((void*)ptr) T();
1635 : }
1636 :
1637 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, std)
1638 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, std)
1639 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, std)
1640 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, std)
1641 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, std)
1642 :
1643 : #if BOOST_UNORDERED_TUPLE_ARGS >= 6
1644 : BOOST_PP_REPEAT_FROM_TO(6, BOOST_PP_INC(BOOST_UNORDERED_TUPLE_ARGS),
1645 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE, std)
1646 : #endif
1647 : }
1648 : }
1649 : }
1650 : }
1651 :
1652 : #endif
1653 :
1654 : #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
1655 : #undef BOOST_UNORDERED_GET_TUPLE_ARG
1656 :
1657 : // construct_from_tuple for boost::tuple on old versions of sunpro.
1658 : //
1659 : // Old versions of Sun C++ had problems with template overloads of
1660 : // boost::tuple, so to fix it I added a distinct type for each length to
1661 : // the overloads. That means there's no possible ambiguity between the
1662 : // different overloads, so that the compiler doesn't get confused
1663 :
1664 : #if BOOST_UNORDERED_SUN_WORKAROUNDS1
1665 :
1666 : #define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
1667 : template <typename Alloc, typename T, \
1668 : BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
1669 : void construct_from_tuple_impl(boost::unordered::detail::func::length<n>, \
1670 : Alloc&, T* ptr, \
1671 : namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
1672 : { \
1673 : new ((void*)ptr) \
1674 : T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
1675 : }
1676 :
1677 : #define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
1678 :
1679 : namespace boost {
1680 : namespace unordered {
1681 : namespace detail {
1682 : namespace func {
1683 : template <int N> struct length
1684 : {
1685 : };
1686 :
1687 : template <typename Alloc, typename T>
1688 : void construct_from_tuple_impl(
1689 : boost::unordered::detail::func::length<0>, Alloc&, T* ptr,
1690 : boost::tuple<>)
1691 : {
1692 : new ((void*)ptr) T();
1693 : }
1694 :
1695 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 1, boost)
1696 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 2, boost)
1697 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 3, boost)
1698 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 4, boost)
1699 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 5, boost)
1700 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 6, boost)
1701 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 7, boost)
1702 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 8, boost)
1703 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 9, boost)
1704 : BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(1, 10, boost)
1705 :
1706 : template <typename Alloc, typename T, typename Tuple>
1707 : void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
1708 : {
1709 : construct_from_tuple_impl(boost::unordered::detail::func::length<
1710 : boost::tuples::length<Tuple>::value>(),
1711 : alloc, ptr, x);
1712 : }
1713 : }
1714 : }
1715 : }
1716 : }
1717 :
1718 : #undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
1719 : #undef BOOST_UNORDERED_GET_TUPLE_ARG
1720 :
1721 : #endif
1722 :
1723 : namespace boost {
1724 : namespace unordered {
1725 : namespace detail {
1726 : namespace func {
1727 : ////////////////////////////////////////////////////////////////////////
1728 : // Trait to check for piecewise construction.
1729 :
1730 : template <typename A0> struct use_piecewise
1731 : {
1732 : static choice1::type test(
1733 : choice1, boost::unordered::piecewise_construct_t);
1734 :
1735 : static choice2::type test(choice2, ...);
1736 :
1737 : enum
1738 : {
1739 : value = sizeof(choice1::type) ==
1740 : sizeof(test(choose(), boost::unordered::detail::make<A0>()))
1741 : };
1742 : };
1743 :
1744 : #if BOOST_UNORDERED_CXX11_CONSTRUCTION
1745 :
1746 : ////////////////////////////////////////////////////////////////////////
1747 : // Construct from variadic parameters
1748 :
1749 : template <typename Alloc, typename T, typename... Args>
1750 2448950 : inline void construct_from_args(
1751 : Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args)
1752 : {
1753 4897900 : boost::unordered::detail::allocator_traits<Alloc>::construct(
1754 : alloc, address, boost::forward<Args>(args)...);
1755 : }
1756 :
1757 : // For backwards compatibility, implement a special case for
1758 : // piecewise_construct with boost::tuple
1759 :
1760 : template <typename A0> struct detect_boost_tuple
1761 : {
1762 : template <typename T0, typename T1, typename T2, typename T3,
1763 : typename T4, typename T5, typename T6, typename T7, typename T8,
1764 : typename T9>
1765 : static choice1::type test(choice1,
1766 : boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> const&);
1767 :
1768 : static choice2::type test(choice2, ...);
1769 :
1770 : enum
1771 : {
1772 : value = sizeof(choice1::type) ==
1773 : sizeof(test(choose(), boost::unordered::detail::make<A0>()))
1774 : };
1775 : };
1776 :
1777 : // Special case for piecewise_construct
1778 :
1779 : template <typename Alloc, typename A, typename B, typename A0,
1780 : typename A1, typename A2>
1781 : inline typename boost::enable_if_c<use_piecewise<A0>::value &&
1782 : detect_boost_tuple<A1>::value &&
1783 : detect_boost_tuple<A2>::value,
1784 : void>::type
1785 : construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1786 : BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1787 : {
1788 : boost::unordered::detail::func::construct_from_tuple(
1789 : alloc, boost::addressof(address->first), boost::forward<A1>(a1));
1790 : BOOST_TRY
1791 : {
1792 : boost::unordered::detail::func::construct_from_tuple(
1793 : alloc, boost::addressof(address->second), boost::forward<A2>(a2));
1794 : }
1795 : BOOST_CATCH(...)
1796 : {
1797 : boost::unordered::detail::func::destroy(
1798 : boost::addressof(address->first));
1799 : BOOST_RETHROW
1800 : }
1801 : BOOST_CATCH_END
1802 : }
1803 :
1804 : #elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
1805 :
1806 : ////////////////////////////////////////////////////////////////////////
1807 : // Construct from variadic parameters
1808 :
1809 : template <typename Alloc, typename T, typename... Args>
1810 : inline void construct_from_args(
1811 : Alloc&, T* address, BOOST_FWD_REF(Args)... args)
1812 : {
1813 : new ((void*)address) T(boost::forward<Args>(args)...);
1814 : }
1815 :
1816 : // Special case for piecewise_construct
1817 :
1818 : template <typename Alloc, typename A, typename B, typename A0,
1819 : typename A1, typename A2>
1820 : inline typename enable_if<use_piecewise<A0>, void>::type
1821 : construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1822 : BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
1823 : {
1824 : boost::unordered::detail::func::construct_from_tuple(
1825 : alloc, boost::addressof(address->first), boost::forward<A1>(a1));
1826 : BOOST_TRY
1827 : {
1828 : boost::unordered::detail::func::construct_from_tuple(
1829 : alloc, boost::addressof(address->second), boost::forward<A2>(a2));
1830 : }
1831 : BOOST_CATCH(...)
1832 : {
1833 : boost::unordered::detail::func::destroy(
1834 : boost::addressof(address->first));
1835 : BOOST_RETHROW
1836 : }
1837 : BOOST_CATCH_END
1838 : }
1839 :
1840 : #else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1841 :
1842 : ////////////////////////////////////////////////////////////////////////
1843 : // Construct from emplace_args
1844 :
1845 : // Explicitly write out first three overloads for the sake of sane
1846 : // error messages.
1847 :
1848 : template <typename Alloc, typename T, typename A0>
1849 : inline void construct_from_args(
1850 : Alloc&, T* address, emplace_args1<A0> const& args)
1851 : {
1852 : new ((void*)address) T(boost::forward<A0>(args.a0));
1853 : }
1854 :
1855 : template <typename Alloc, typename T, typename A0, typename A1>
1856 : inline void construct_from_args(
1857 : Alloc&, T* address, emplace_args2<A0, A1> const& args)
1858 : {
1859 : new ((void*)address)
1860 : T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1));
1861 : }
1862 :
1863 : template <typename Alloc, typename T, typename A0, typename A1,
1864 : typename A2>
1865 : inline void construct_from_args(
1866 : Alloc&, T* address, emplace_args3<A0, A1, A2> const& args)
1867 : {
1868 : new ((void*)address) T(boost::forward<A0>(args.a0),
1869 : boost::forward<A1>(args.a1), boost::forward<A2>(args.a2));
1870 : }
1871 :
1872 : // Use a macro for the rest.
1873 :
1874 : #define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
1875 : template <typename Alloc, typename T, \
1876 : BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)> \
1877 : inline void construct_from_args(Alloc&, T* address, \
1878 : boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \
1879 : BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) > const& args) \
1880 : { \
1881 : new ((void*)address) \
1882 : T(BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, args.a)); \
1883 : }
1884 :
1885 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 4, _)
1886 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 5, _)
1887 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 6, _)
1888 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 7, _)
1889 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 8, _)
1890 : BOOST_UNORDERED_CONSTRUCT_IMPL(1, 9, _)
1891 : BOOST_PP_REPEAT_FROM_TO(10, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
1892 : BOOST_UNORDERED_CONSTRUCT_IMPL, _)
1893 :
1894 : #undef BOOST_UNORDERED_CONSTRUCT_IMPL
1895 :
1896 : // Construct with piecewise_construct
1897 :
1898 : template <typename Alloc, typename A, typename B, typename A0,
1899 : typename A1, typename A2>
1900 : inline void construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1901 : boost::unordered::detail::emplace_args3<A0, A1, A2> const& args,
1902 : typename enable_if<use_piecewise<A0>, void*>::type = 0)
1903 : {
1904 : boost::unordered::detail::func::construct_from_tuple(
1905 : alloc, boost::addressof(address->first), args.a1);
1906 : BOOST_TRY
1907 : {
1908 : boost::unordered::detail::func::construct_from_tuple(
1909 : alloc, boost::addressof(address->second), args.a2);
1910 : }
1911 : BOOST_CATCH(...)
1912 : {
1913 : boost::unordered::detail::func::destroy(
1914 : boost::addressof(address->first));
1915 : BOOST_RETHROW
1916 : }
1917 : BOOST_CATCH_END
1918 : }
1919 :
1920 : #endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1921 : }
1922 : }
1923 : }
1924 : }
1925 :
1926 : namespace boost {
1927 : namespace unordered {
1928 : namespace detail {
1929 :
1930 : ///////////////////////////////////////////////////////////////////
1931 : //
1932 : // Node construction
1933 :
1934 : template <typename NodeAlloc> struct node_constructor
1935 : {
1936 : typedef NodeAlloc node_allocator;
1937 : typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1938 : node_allocator_traits;
1939 : typedef typename node_allocator_traits::value_type node;
1940 : typedef typename node_allocator_traits::pointer node_pointer;
1941 : typedef typename node::value_type value_type;
1942 :
1943 : node_allocator& alloc_;
1944 : node_pointer node_;
1945 :
1946 2449030 : node_constructor(node_allocator& n) : alloc_(n), node_() {}
1947 :
1948 : ~node_constructor();
1949 :
1950 : void create_node();
1951 :
1952 : // no throw
1953 2449030 : node_pointer release()
1954 : {
1955 0 : BOOST_ASSERT(node_);
1956 2449030 : node_pointer p = node_;
1957 0 : node_ = node_pointer();
1958 : return p;
1959 : }
1960 :
1961 0 : void reclaim(node_pointer p)
1962 : {
1963 0 : BOOST_ASSERT(!node_);
1964 0 : node_ = p;
1965 0 : BOOST_UNORDERED_CALL_DESTROY(
1966 : node_allocator_traits, alloc_, node_->value_ptr());
1967 0 : }
1968 :
1969 : private:
1970 : node_constructor(node_constructor const&);
1971 : node_constructor& operator=(node_constructor const&);
1972 : };
1973 :
1974 2449030 : template <typename Alloc> node_constructor<Alloc>::~node_constructor()
1975 : {
1976 0 : if (node_) {
1977 0 : boost::unordered::detail::func::destroy(boost::to_address(node_));
1978 0 : node_allocator_traits::deallocate(alloc_, node_, 1);
1979 : }
1980 : }
1981 :
1982 : template <typename Alloc> void node_constructor<Alloc>::create_node()
1983 : {
1984 : BOOST_ASSERT(!node_);
1985 : node_ = node_allocator_traits::allocate(alloc_, 1);
1986 : new ((void*)boost::to_address(node_)) node();
1987 : }
1988 :
1989 : template <typename NodeAlloc> struct node_tmp
1990 : {
1991 : typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1992 : node_allocator_traits;
1993 : typedef typename node_allocator_traits::pointer node_pointer;
1994 : typedef typename node_allocator_traits::value_type node;
1995 :
1996 : NodeAlloc& alloc_;
1997 : node_pointer node_;
1998 :
1999 2449030 : explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {}
2000 :
2001 : ~node_tmp();
2002 :
2003 : // no throw
2004 2449030 : node_pointer release()
2005 : {
2006 2448950 : node_pointer p = node_;
2007 2449030 : node_ = node_pointer();
2008 : return p;
2009 : }
2010 : };
2011 :
2012 2449030 : template <typename Alloc> node_tmp<Alloc>::~node_tmp()
2013 : {
2014 2448950 : if (node_) {
2015 0 : BOOST_UNORDERED_CALL_DESTROY(
2016 : node_allocator_traits, alloc_, node_->value_ptr());
2017 0 : boost::unordered::detail::func::destroy(boost::to_address(node_));
2018 0 : node_allocator_traits::deallocate(alloc_, node_, 1);
2019 : }
2020 2448950 : }
2021 : }
2022 : }
2023 : }
2024 :
2025 : namespace boost {
2026 : namespace unordered {
2027 : namespace detail {
2028 : namespace func {
2029 :
2030 : // Some nicer construct_node functions, might try to
2031 : // improve implementation later.
2032 :
2033 : template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE>
2034 : inline
2035 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2036 2448950 : construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
2037 : {
2038 4897900 : node_constructor<Alloc> a(alloc);
2039 2448950 : a.create_node();
2040 4897900 : construct_from_args(
2041 2448950 : alloc, a.node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
2042 2448950 : return a.release();
2043 : }
2044 :
2045 : template <typename Alloc, typename U>
2046 : inline
2047 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2048 0 : construct_node(Alloc& alloc, BOOST_FWD_REF(U) x)
2049 : {
2050 0 : node_constructor<Alloc> a(alloc);
2051 0 : a.create_node();
2052 0 : BOOST_UNORDERED_CALL_CONSTRUCT1(
2053 : boost::unordered::detail::allocator_traits<Alloc>, alloc,
2054 : a.node_->value_ptr(), boost::forward<U>(x));
2055 0 : return a.release();
2056 : }
2057 :
2058 : #if BOOST_UNORDERED_CXX11_CONSTRUCTION
2059 :
2060 : template <typename Alloc, typename Key>
2061 : inline
2062 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2063 80 : construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
2064 : {
2065 160 : node_constructor<Alloc> a(alloc);
2066 80 : a.create_node();
2067 80 : boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2068 80 : a.node_->value_ptr(), std::piecewise_construct,
2069 : std::forward_as_tuple(boost::forward<Key>(k)),
2070 : std::forward_as_tuple());
2071 80 : return a.release();
2072 : }
2073 :
2074 : template <typename Alloc, typename Key, typename Mapped>
2075 : inline
2076 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2077 : construct_node_pair(
2078 : Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
2079 : {
2080 : node_constructor<Alloc> a(alloc);
2081 : a.create_node();
2082 : boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2083 : a.node_->value_ptr(), std::piecewise_construct,
2084 : std::forward_as_tuple(boost::forward<Key>(k)),
2085 : std::forward_as_tuple(boost::forward<Mapped>(m)));
2086 : return a.release();
2087 : }
2088 :
2089 : template <typename Alloc, typename Key, typename... Args>
2090 : inline
2091 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2092 : construct_node_pair_from_args(
2093 : Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Args)... args)
2094 : {
2095 : node_constructor<Alloc> a(alloc);
2096 : a.create_node();
2097 : #if !(BOOST_COMP_CLANG && BOOST_COMP_CLANG < BOOST_VERSION_NUMBER(3, 8, 0) && \
2098 : defined(BOOST_LIBSTDCXX11))
2099 : boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2100 : a.node_->value_ptr(), std::piecewise_construct,
2101 : std::forward_as_tuple(boost::forward<Key>(k)),
2102 : std::forward_as_tuple(boost::forward<Args>(args)...));
2103 : #else
2104 : // It doesn't seem to be possible to construct a tuple with 3 variadic
2105 : // rvalue reference members when using older versions of clang with
2106 : // libstdc++, so just use std::make_tuple instead of
2107 : // std::forward_as_tuple.
2108 : boost::unordered::detail::allocator_traits<Alloc>::construct(alloc,
2109 : a.node_->value_ptr(), std::piecewise_construct,
2110 : std::forward_as_tuple(boost::forward<Key>(k)),
2111 : std::make_tuple(boost::forward<Args>(args)...));
2112 : #endif
2113 : return a.release();
2114 : }
2115 :
2116 : #else
2117 :
2118 : template <typename Alloc, typename Key>
2119 : inline
2120 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2121 : construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
2122 : {
2123 : node_constructor<Alloc> a(alloc);
2124 : a.create_node();
2125 : boost::unordered::detail::func::construct_value(
2126 : boost::addressof(a.node_->value_ptr()->first),
2127 : boost::forward<Key>(k));
2128 : BOOST_TRY
2129 : {
2130 : boost::unordered::detail::func::construct_value(
2131 : boost::addressof(a.node_->value_ptr()->second));
2132 : }
2133 : BOOST_CATCH(...)
2134 : {
2135 : boost::unordered::detail::func::destroy(
2136 : boost::addressof(a.node_->value_ptr()->first));
2137 : BOOST_RETHROW
2138 : }
2139 : BOOST_CATCH_END
2140 : return a.release();
2141 : }
2142 :
2143 : template <typename Alloc, typename Key, typename Mapped>
2144 : inline
2145 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2146 : construct_node_pair(
2147 : Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
2148 : {
2149 : node_constructor<Alloc> a(alloc);
2150 : a.create_node();
2151 : boost::unordered::detail::func::construct_value(
2152 : boost::addressof(a.node_->value_ptr()->first),
2153 : boost::forward<Key>(k));
2154 : BOOST_TRY
2155 : {
2156 : boost::unordered::detail::func::construct_value(
2157 : boost::addressof(a.node_->value_ptr()->second),
2158 : boost::forward<Mapped>(m));
2159 : }
2160 : BOOST_CATCH(...)
2161 : {
2162 : boost::unordered::detail::func::destroy(
2163 : boost::addressof(a.node_->value_ptr()->first));
2164 : BOOST_RETHROW
2165 : }
2166 : BOOST_CATCH_END
2167 : return a.release();
2168 : }
2169 :
2170 : template <typename Alloc, typename Key,
2171 : BOOST_UNORDERED_EMPLACE_TEMPLATE>
2172 : inline
2173 : typename boost::unordered::detail::allocator_traits<Alloc>::pointer
2174 : construct_node_pair_from_args(
2175 : Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
2176 : {
2177 : node_constructor<Alloc> a(alloc);
2178 : a.create_node();
2179 : boost::unordered::detail::func::construct_value(
2180 : boost::addressof(a.node_->value_ptr()->first),
2181 : boost::forward<Key>(k));
2182 : BOOST_TRY
2183 : {
2184 : boost::unordered::detail::func::construct_from_args(alloc,
2185 : boost::addressof(a.node_->value_ptr()->second),
2186 : BOOST_UNORDERED_EMPLACE_FORWARD);
2187 : }
2188 : BOOST_CATCH(...)
2189 : {
2190 : boost::unordered::detail::func::destroy(
2191 : boost::addressof(a.node_->value_ptr()->first));
2192 : BOOST_RETHROW
2193 : }
2194 : BOOST_CATCH_END
2195 : return a.release();
2196 : }
2197 :
2198 : #endif
2199 : }
2200 : }
2201 : }
2202 : }
2203 :
2204 : #if defined(BOOST_MSVC)
2205 : #pragma warning(pop)
2206 : #endif
2207 :
2208 : // The 'iterator_detail' namespace was a misguided attempt at avoiding ADL
2209 : // in the detail namespace. It didn't work because the template parameters
2210 : // were in detail. I'm not changing it at the moment to be safe. I might
2211 : // do in the future if I change the iterator types.
2212 : namespace boost {
2213 : namespace unordered {
2214 : namespace iterator_detail {
2215 :
2216 : //////////////////////////////////////////////////////////////////////////
2217 : // Iterators
2218 : //
2219 : // all no throw
2220 :
2221 : template <typename Node> struct l_iterator
2222 : {
2223 : #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2224 : template <typename Node2>
2225 : friend struct boost::unordered::iterator_detail::cl_iterator;
2226 :
2227 : private:
2228 : #endif
2229 : typedef typename Node::node_pointer node_pointer;
2230 : node_pointer ptr_;
2231 : std::size_t bucket_;
2232 : std::size_t bucket_count_;
2233 :
2234 : public:
2235 : typedef typename Node::value_type element_type;
2236 : typedef typename Node::value_type value_type;
2237 : typedef value_type* pointer;
2238 : typedef value_type& reference;
2239 : typedef std::ptrdiff_t difference_type;
2240 : typedef std::forward_iterator_tag iterator_category;
2241 :
2242 : l_iterator() BOOST_NOEXCEPT : ptr_() {}
2243 :
2244 : l_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT
2245 : : ptr_(n),
2246 : bucket_(b),
2247 : bucket_count_(c)
2248 : {
2249 : }
2250 :
2251 : value_type& operator*() const { return ptr_->value(); }
2252 :
2253 : value_type* operator->() const { return ptr_->value_ptr(); }
2254 :
2255 : l_iterator& operator++()
2256 : {
2257 : ptr_ = static_cast<node_pointer>(ptr_->next_);
2258 : if (ptr_ && ptr_->get_bucket() != bucket_)
2259 : ptr_ = node_pointer();
2260 : return *this;
2261 : }
2262 :
2263 : l_iterator operator++(int)
2264 : {
2265 : l_iterator tmp(*this);
2266 : ++(*this);
2267 : return tmp;
2268 : }
2269 :
2270 : bool operator==(l_iterator x) const BOOST_NOEXCEPT
2271 : {
2272 : return ptr_ == x.ptr_;
2273 : }
2274 :
2275 : bool operator!=(l_iterator x) const BOOST_NOEXCEPT
2276 : {
2277 : return ptr_ != x.ptr_;
2278 : }
2279 : };
2280 :
2281 : template <typename Node> struct cl_iterator
2282 : {
2283 : friend struct boost::unordered::iterator_detail::l_iterator<Node>;
2284 :
2285 : private:
2286 : typedef typename Node::node_pointer node_pointer;
2287 : node_pointer ptr_;
2288 : std::size_t bucket_;
2289 : std::size_t bucket_count_;
2290 :
2291 : public:
2292 : typedef typename Node::value_type const element_type;
2293 : typedef typename Node::value_type value_type;
2294 : typedef value_type const* pointer;
2295 : typedef value_type const& reference;
2296 : typedef std::ptrdiff_t difference_type;
2297 : typedef std::forward_iterator_tag iterator_category;
2298 :
2299 : cl_iterator() BOOST_NOEXCEPT : ptr_() {}
2300 :
2301 : cl_iterator(node_pointer n, std::size_t b, std::size_t c) BOOST_NOEXCEPT
2302 : : ptr_(n),
2303 : bucket_(b),
2304 : bucket_count_(c)
2305 : {
2306 : }
2307 :
2308 : cl_iterator(
2309 : boost::unordered::iterator_detail::l_iterator<Node> const& x)
2310 : BOOST_NOEXCEPT : ptr_(x.ptr_),
2311 : bucket_(x.bucket_),
2312 : bucket_count_(x.bucket_count_)
2313 : {
2314 : }
2315 :
2316 : value_type const& operator*() const { return ptr_->value(); }
2317 :
2318 : value_type const* operator->() const { return ptr_->value_ptr(); }
2319 :
2320 : cl_iterator& operator++()
2321 : {
2322 : ptr_ = static_cast<node_pointer>(ptr_->next_);
2323 : if (ptr_ && ptr_->get_bucket() != bucket_)
2324 : ptr_ = node_pointer();
2325 : return *this;
2326 : }
2327 :
2328 : cl_iterator operator++(int)
2329 : {
2330 : cl_iterator tmp(*this);
2331 : ++(*this);
2332 : return tmp;
2333 : }
2334 :
2335 : friend bool operator==(
2336 : cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT
2337 : {
2338 : return x.ptr_ == y.ptr_;
2339 : }
2340 :
2341 : friend bool operator!=(
2342 : cl_iterator const& x, cl_iterator const& y) BOOST_NOEXCEPT
2343 : {
2344 : return x.ptr_ != y.ptr_;
2345 : }
2346 : };
2347 :
2348 : template <typename Node> struct iterator
2349 : {
2350 : #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2351 : template <typename>
2352 : friend struct boost::unordered::iterator_detail::c_iterator;
2353 : template <typename> friend struct boost::unordered::detail::table;
2354 :
2355 : private:
2356 : #endif
2357 : typedef typename Node::node_pointer node_pointer;
2358 : node_pointer node_;
2359 :
2360 : public:
2361 : typedef typename Node::value_type element_type;
2362 : typedef typename Node::value_type value_type;
2363 : typedef value_type* pointer;
2364 : typedef value_type& reference;
2365 : typedef std::ptrdiff_t difference_type;
2366 : typedef std::forward_iterator_tag iterator_category;
2367 :
2368 15755469 : iterator() BOOST_NOEXCEPT : node_() {}
2369 :
2370 35837859 : explicit iterator(typename Node::link_pointer x) BOOST_NOEXCEPT
2371 5264006 : : node_(static_cast<node_pointer>(x))
2372 : {
2373 : }
2374 :
2375 24834407 : value_type& operator*() const { return node_->value(); }
2376 :
2377 58925272 : value_type* operator->() const { return node_->value_ptr(); }
2378 :
2379 3385763 : iterator& operator++()
2380 : {
2381 3249592 : node_ = static_cast<node_pointer>(node_->next_);
2382 3342922 : return *this;
2383 : }
2384 :
2385 5264006 : iterator operator++(int)
2386 : {
2387 5264006 : iterator tmp(node_);
2388 2010296 : node_ = static_cast<node_pointer>(node_->next_);
2389 4199306 : return tmp;
2390 : }
2391 :
2392 83348 : bool operator==(iterator const& x) const BOOST_NOEXCEPT
2393 : {
2394 : return node_ == x.node_;
2395 : }
2396 :
2397 47898932 : bool operator!=(iterator const& x) const BOOST_NOEXCEPT
2398 : {
2399 61103 : return node_ != x.node_;
2400 : }
2401 : };
2402 :
2403 : template <typename Node> struct c_iterator
2404 : {
2405 : friend struct boost::unordered::iterator_detail::iterator<Node>;
2406 :
2407 : #if !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)
2408 : template <typename> friend struct boost::unordered::detail::table;
2409 :
2410 : private:
2411 : #endif
2412 : typedef typename Node::node_pointer node_pointer;
2413 : typedef boost::unordered::iterator_detail::iterator<Node> n_iterator;
2414 : node_pointer node_;
2415 :
2416 : public:
2417 : typedef typename Node::value_type const element_type;
2418 : typedef typename Node::value_type value_type;
2419 : typedef value_type const* pointer;
2420 : typedef value_type const& reference;
2421 : typedef std::ptrdiff_t difference_type;
2422 : typedef std::forward_iterator_tag iterator_category;
2423 :
2424 0 : c_iterator() BOOST_NOEXCEPT : node_() {}
2425 :
2426 0 : explicit c_iterator(typename Node::link_pointer x) BOOST_NOEXCEPT
2427 0 : : node_(static_cast<node_pointer>(x))
2428 : {
2429 : }
2430 :
2431 108030 : c_iterator(n_iterator const& x) BOOST_NOEXCEPT : node_(x.node_) {}
2432 :
2433 0 : value_type const& operator*() const { return node_->value(); }
2434 :
2435 12323390 : value_type const* operator->() const { return node_->value_ptr(); }
2436 :
2437 10183350 : c_iterator& operator++()
2438 : {
2439 10183350 : node_ = static_cast<node_pointer>(node_->next_);
2440 10183350 : return *this;
2441 : }
2442 :
2443 0 : c_iterator operator++(int)
2444 : {
2445 0 : c_iterator tmp(node_);
2446 0 : node_ = static_cast<node_pointer>(node_->next_);
2447 0 : return tmp;
2448 : }
2449 :
2450 0 : friend bool operator==(
2451 : c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT
2452 : {
2453 : return x.node_ == y.node_;
2454 : }
2455 :
2456 10264880 : friend bool operator!=(
2457 : c_iterator const& x, c_iterator const& y) BOOST_NOEXCEPT
2458 : {
2459 0 : return x.node_ != y.node_;
2460 : }
2461 : };
2462 : }
2463 : }
2464 : }
2465 :
2466 : namespace boost {
2467 : namespace unordered {
2468 : namespace detail {
2469 :
2470 : ///////////////////////////////////////////////////////////////////
2471 : //
2472 : // Node Holder
2473 : //
2474 : // Temporary store for nodes. Deletes any that aren't used.
2475 :
2476 : template <typename NodeAlloc> struct node_holder
2477 : {
2478 : private:
2479 : typedef NodeAlloc node_allocator;
2480 : typedef boost::unordered::detail::allocator_traits<NodeAlloc>
2481 : node_allocator_traits;
2482 : typedef typename node_allocator_traits::value_type node;
2483 : typedef typename node_allocator_traits::pointer node_pointer;
2484 : typedef typename node::value_type value_type;
2485 : typedef typename node::link_pointer link_pointer;
2486 : typedef boost::unordered::iterator_detail::iterator<node> iterator;
2487 :
2488 : node_constructor<NodeAlloc> constructor_;
2489 : node_pointer nodes_;
2490 :
2491 : public:
2492 : template <typename Table>
2493 0 : explicit node_holder(Table& b) : constructor_(b.node_alloc()), nodes_()
2494 : {
2495 0 : if (b.size_) {
2496 0 : typename Table::link_pointer prev = b.get_previous_start();
2497 0 : nodes_ = static_cast<node_pointer>(prev->next_);
2498 0 : prev->next_ = link_pointer();
2499 0 : b.size_ = 0;
2500 : }
2501 0 : }
2502 :
2503 : ~node_holder();
2504 :
2505 0 : node_pointer pop_node()
2506 : {
2507 0 : node_pointer n = nodes_;
2508 0 : nodes_ = static_cast<node_pointer>(nodes_->next_);
2509 0 : n->next_ = link_pointer();
2510 : return n;
2511 : }
2512 :
2513 0 : template <typename T> inline node_pointer copy_of(T const& v)
2514 : {
2515 0 : if (nodes_) {
2516 0 : constructor_.reclaim(pop_node());
2517 : } else {
2518 0 : constructor_.create_node();
2519 : }
2520 0 : BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits,
2521 : constructor_.alloc_, constructor_.node_->value_ptr(), v);
2522 0 : return constructor_.release();
2523 : }
2524 :
2525 : template <typename T> inline node_pointer move_copy_of(T& v)
2526 : {
2527 : if (nodes_) {
2528 : constructor_.reclaim(pop_node());
2529 : } else {
2530 : constructor_.create_node();
2531 : }
2532 : BOOST_UNORDERED_CALL_CONSTRUCT1(node_allocator_traits,
2533 : constructor_.alloc_, constructor_.node_->value_ptr(),
2534 : boost::move(v));
2535 : return constructor_.release();
2536 : }
2537 :
2538 : iterator begin() const { return iterator(nodes_); }
2539 : };
2540 :
2541 0 : template <typename Alloc> node_holder<Alloc>::~node_holder()
2542 : {
2543 0 : while (nodes_) {
2544 0 : node_pointer p = nodes_;
2545 0 : nodes_ = static_cast<node_pointer>(p->next_);
2546 :
2547 0 : BOOST_UNORDERED_CALL_DESTROY(
2548 : node_allocator_traits, constructor_.alloc_, p->value_ptr());
2549 0 : boost::unordered::detail::func::destroy(boost::to_address(p));
2550 0 : node_allocator_traits::deallocate(constructor_.alloc_, p, 1);
2551 : }
2552 0 : }
2553 :
2554 : ///////////////////////////////////////////////////////////////////
2555 : //
2556 : // Bucket
2557 :
2558 : template <typename NodePointer> struct bucket
2559 : {
2560 : typedef NodePointer link_pointer;
2561 : link_pointer next_;
2562 :
2563 : bucket() : next_() {}
2564 : bucket(link_pointer n) : next_(n) {}
2565 :
2566 : link_pointer first_from_start() { return next_; }
2567 :
2568 : enum
2569 : {
2570 : extra_node = true
2571 : };
2572 : };
2573 :
2574 : struct ptr_bucket
2575 : {
2576 : typedef ptr_bucket* link_pointer;
2577 : link_pointer next_;
2578 :
2579 16514040 : ptr_bucket() : next_(0) {}
2580 82687 : ptr_bucket(link_pointer n) : next_(n) {}
2581 :
2582 1578425 : link_pointer first_from_start() { return this; }
2583 :
2584 : enum
2585 : {
2586 : extra_node = false
2587 : };
2588 : };
2589 :
2590 : ///////////////////////////////////////////////////////////////////
2591 : //
2592 : // Hash Policy
2593 :
2594 : template <typename SizeT> struct prime_policy
2595 : {
2596 : template <typename Hash, typename T>
2597 0 : static inline SizeT apply_hash(Hash const& hf, T const& x)
2598 : {
2599 0 : return hf(x);
2600 : }
2601 :
2602 0 : static inline SizeT to_bucket(SizeT bucket_count, SizeT hash)
2603 : {
2604 0 : return hash % bucket_count;
2605 : }
2606 :
2607 0 : static inline SizeT new_bucket_count(SizeT min)
2608 : {
2609 0 : return boost::unordered::detail::next_prime(min);
2610 : }
2611 :
2612 : static inline SizeT prev_bucket_count(SizeT max)
2613 : {
2614 : return boost::unordered::detail::prev_prime(max);
2615 : }
2616 : };
2617 :
2618 : template <typename SizeT> struct mix64_policy
2619 : {
2620 : template <typename Hash, typename T>
2621 40859022 : static inline SizeT apply_hash(Hash const& hf, T const& x)
2622 : {
2623 40859022 : SizeT key = hf(x);
2624 40859022 : key = (~key) + (key << 21); // key = (key << 21) - key - 1;
2625 40859022 : key = key ^ (key >> 24);
2626 40859022 : key = (key + (key << 3)) + (key << 8); // key * 265
2627 40859022 : key = key ^ (key >> 14);
2628 40859022 : key = (key + (key << 2)) + (key << 4); // key * 21
2629 40859022 : key = key ^ (key >> 28);
2630 40859022 : key = key + (key << 31);
2631 40859022 : return key;
2632 : }
2633 :
2634 43308114 : static inline SizeT to_bucket(SizeT bucket_count, SizeT hash)
2635 : {
2636 43308114 : return hash & (bucket_count - 1);
2637 : }
2638 :
2639 386790 : static inline SizeT new_bucket_count(SizeT min)
2640 : {
2641 304106 : if (min <= 4)
2642 : return 4;
2643 311631 : --min;
2644 311631 : min |= min >> 1;
2645 311631 : min |= min >> 2;
2646 311631 : min |= min >> 4;
2647 311631 : min |= min >> 8;
2648 311631 : min |= min >> 16;
2649 311631 : min |= min >> 32;
2650 304105 : return min + 1;
2651 : }
2652 :
2653 : static inline SizeT prev_bucket_count(SizeT max)
2654 : {
2655 : max |= max >> 1;
2656 : max |= max >> 2;
2657 : max |= max >> 4;
2658 : max |= max >> 8;
2659 : max |= max >> 16;
2660 : max |= max >> 32;
2661 : return (max >> 1) + 1;
2662 : }
2663 : };
2664 :
2665 : template <int digits, int radix> struct pick_policy_impl
2666 : {
2667 : typedef prime_policy<std::size_t> type;
2668 : };
2669 :
2670 : template <> struct pick_policy_impl<64, 2>
2671 : {
2672 : typedef mix64_policy<std::size_t> type;
2673 : };
2674 :
2675 : template <typename T>
2676 : struct pick_policy2
2677 : : pick_policy_impl<std::numeric_limits<std::size_t>::digits,
2678 : std::numeric_limits<std::size_t>::radix>
2679 : {
2680 : };
2681 :
2682 : // While the mix policy is generally faster, the prime policy is a lot
2683 : // faster when a large number consecutive integers are used, because
2684 : // there are no collisions. Since that is probably quite common, use
2685 : // prime policy for integeral types. But not the smaller ones, as they
2686 : // don't have enough unique values for this to be an issue.
2687 :
2688 : template <> struct pick_policy2<int>
2689 : {
2690 : typedef prime_policy<std::size_t> type;
2691 : };
2692 :
2693 : template <> struct pick_policy2<unsigned int>
2694 : {
2695 : typedef prime_policy<std::size_t> type;
2696 : };
2697 :
2698 : template <> struct pick_policy2<long>
2699 : {
2700 : typedef prime_policy<std::size_t> type;
2701 : };
2702 :
2703 : template <> struct pick_policy2<unsigned long>
2704 : {
2705 : typedef prime_policy<std::size_t> type;
2706 : };
2707 :
2708 : #if !defined(BOOST_NO_LONG_LONG)
2709 : template <> struct pick_policy2<boost::long_long_type>
2710 : {
2711 : typedef prime_policy<std::size_t> type;
2712 : };
2713 :
2714 : template <> struct pick_policy2<boost::ulong_long_type>
2715 : {
2716 : typedef prime_policy<std::size_t> type;
2717 : };
2718 : #endif
2719 :
2720 : template <typename T>
2721 : struct pick_policy : pick_policy2<typename boost::remove_cv<T>::type>
2722 : {
2723 : };
2724 :
2725 : //////////////////////////////////////////////////////////////////////////
2726 : // Functions
2727 : //
2728 : // This double buffers the storage for the hash function and key equality
2729 : // predicate in order to have exception safe copy/swap. To do so,
2730 : // use 'construct_spare' to construct in the spare space, and then when
2731 : // ready to use 'switch_functions' to switch to the new functions.
2732 : // If an exception is thrown between these two calls, use
2733 : // 'cleanup_spare_functions' to destroy the unused constructed functions.
2734 :
2735 : template <class H, class P> class functions
2736 : {
2737 : public:
2738 : static const bool nothrow_move_assignable =
2739 : boost::is_nothrow_move_assignable<H>::value &&
2740 : boost::is_nothrow_move_assignable<P>::value;
2741 : static const bool nothrow_move_constructible =
2742 : boost::is_nothrow_move_constructible<H>::value &&
2743 : boost::is_nothrow_move_constructible<P>::value;
2744 : static const bool nothrow_swappable =
2745 : boost::is_nothrow_swappable<H>::value &&
2746 : boost::is_nothrow_swappable<P>::value;
2747 :
2748 : private:
2749 : functions& operator=(functions const&);
2750 :
2751 : typedef compressed<H, P> function_pair;
2752 :
2753 : typedef typename boost::aligned_storage<sizeof(function_pair),
2754 : boost::alignment_of<function_pair>::value>::type aligned_function;
2755 :
2756 : unsigned char current_; // 0/1 - Currently active functions
2757 : // +2 - Both constructed
2758 : aligned_function funcs_[2];
2759 :
2760 : public:
2761 304103 : functions(H const& hf, P const& eq) : current_(0)
2762 : {
2763 304103 : construct_functions(current_, hf, eq);
2764 : }
2765 :
2766 0 : functions(functions const& bf) : current_(0)
2767 : {
2768 0 : construct_functions(current_, bf.current_functions());
2769 : }
2770 :
2771 0 : functions(functions& bf, boost::unordered::detail::move_tag)
2772 0 : : current_(0)
2773 : {
2774 0 : construct_functions(current_, bf.current_functions(),
2775 : boost::unordered::detail::integral_constant<bool,
2776 : nothrow_move_constructible>());
2777 : }
2778 :
2779 55170 : ~functions()
2780 : {
2781 55170 : BOOST_ASSERT(!(current_ & 2));
2782 55170 : destroy_functions(current_);
2783 : }
2784 :
2785 40859693 : H const& hash_function() const { return current_functions().first(); }
2786 :
2787 56394981 : P const& key_eq() const { return current_functions().second(); }
2788 :
2789 61990693 : function_pair const& current_functions() const
2790 : {
2791 : return *static_cast<function_pair const*>(
2792 29298093 : static_cast<void const*>(funcs_[current_ & 1].address()));
2793 : }
2794 :
2795 0 : function_pair& current_functions()
2796 : {
2797 : return *static_cast<function_pair*>(
2798 0 : static_cast<void*>(funcs_[current_ & 1].address()));
2799 : }
2800 :
2801 : void construct_spare_functions(function_pair const& f)
2802 : {
2803 : BOOST_ASSERT(!(current_ & 2));
2804 : construct_functions(current_ ^ 1, f);
2805 : current_ |= 2;
2806 : }
2807 :
2808 0 : void cleanup_spare_functions()
2809 : {
2810 0 : if (current_ & 2) {
2811 0 : current_ = static_cast<unsigned char>(current_ & 1);
2812 0 : destroy_functions(current_ ^ 1);
2813 : }
2814 : }
2815 :
2816 : void switch_functions()
2817 : {
2818 : BOOST_ASSERT(current_ & 2);
2819 : destroy_functions(static_cast<unsigned char>(current_ & 1));
2820 : current_ ^= 3;
2821 : }
2822 :
2823 : private:
2824 304103 : void construct_functions(unsigned char which, H const& hf, P const& eq)
2825 : {
2826 1 : BOOST_ASSERT(!(which & 2));
2827 304103 : new ((void*)&funcs_[which]) function_pair(hf, eq);
2828 : }
2829 :
2830 0 : void construct_functions(unsigned char which, function_pair const& f,
2831 : boost::unordered::detail::false_type =
2832 : boost::unordered::detail::false_type())
2833 : {
2834 0 : BOOST_ASSERT(!(which & 2));
2835 0 : new ((void*)&funcs_[which]) function_pair(f);
2836 : }
2837 :
2838 0 : void construct_functions(unsigned char which, function_pair& f,
2839 : boost::unordered::detail::true_type)
2840 : {
2841 0 : BOOST_ASSERT(!(which & 2));
2842 0 : new ((void*)&funcs_[which])
2843 : function_pair(f, boost::unordered::detail::move_tag());
2844 : }
2845 :
2846 55170 : void destroy_functions(unsigned char which)
2847 : {
2848 55170 : BOOST_ASSERT(!(which & 2));
2849 55170 : boost::unordered::detail::func::destroy(
2850 55170 : (function_pair*)(&funcs_[which]));
2851 : }
2852 : };
2853 :
2854 : ////////////////////////////////////////////////////////////////////////////
2855 : // rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
2856 : // e.g. for int
2857 :
2858 : #if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
2859 : #define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
2860 : #else
2861 : struct please_ignore_this_overload
2862 : {
2863 : typedef please_ignore_this_overload type;
2864 : };
2865 :
2866 : template <typename T> struct rv_ref_impl
2867 : {
2868 : typedef BOOST_RV_REF(T) type;
2869 : };
2870 :
2871 : template <typename T>
2872 : struct rv_ref
2873 : : boost::detail::if_true<boost::is_class<T>::value>::
2874 : BOOST_NESTED_TEMPLATE then<boost::unordered::detail::rv_ref_impl<T>,
2875 : please_ignore_this_overload>::type
2876 : {
2877 : };
2878 :
2879 : #define BOOST_UNORDERED_RV_REF(T) \
2880 : typename boost::unordered::detail::rv_ref<T>::type
2881 : #endif
2882 :
2883 : #if defined(BOOST_MSVC)
2884 : #pragma warning(push)
2885 : #pragma warning(disable : 4127) // conditional expression is constant
2886 : #endif
2887 :
2888 : //////////////////////////////////////////////////////////////////////////
2889 : // convert double to std::size_t
2890 :
2891 165374 : inline std::size_t double_to_size(double f)
2892 : {
2893 165374 : return f >= static_cast<double>(
2894 : (std::numeric_limits<std::size_t>::max)())
2895 82687 : ? (std::numeric_limits<std::size_t>::max)()
2896 : : static_cast<std::size_t>(f);
2897 : }
2898 :
2899 : template <typename Types>
2900 : struct table : boost::unordered::detail::functions<typename Types::hasher,
2901 : typename Types::key_equal>
2902 : {
2903 : private:
2904 : table(table const&);
2905 : table& operator=(table const&);
2906 :
2907 : public:
2908 : typedef typename Types::node node;
2909 : typedef typename Types::bucket bucket;
2910 : typedef typename Types::hasher hasher;
2911 : typedef typename Types::key_equal key_equal;
2912 : typedef typename Types::const_key_type const_key_type;
2913 : typedef typename Types::extractor extractor;
2914 : typedef typename Types::value_type value_type;
2915 : typedef typename Types::table table_impl;
2916 : typedef typename Types::link_pointer link_pointer;
2917 : typedef typename Types::policy policy;
2918 : typedef typename Types::iterator iterator;
2919 : typedef typename Types::c_iterator c_iterator;
2920 : typedef typename Types::l_iterator l_iterator;
2921 : typedef typename Types::cl_iterator cl_iterator;
2922 :
2923 : typedef boost::unordered::detail::functions<typename Types::hasher,
2924 : typename Types::key_equal>
2925 : functions;
2926 :
2927 : typedef typename Types::value_allocator value_allocator;
2928 : typedef typename boost::unordered::detail::rebind_wrap<value_allocator,
2929 : node>::type node_allocator;
2930 : typedef typename boost::unordered::detail::rebind_wrap<value_allocator,
2931 : bucket>::type bucket_allocator;
2932 : typedef boost::unordered::detail::allocator_traits<node_allocator>
2933 : node_allocator_traits;
2934 : typedef boost::unordered::detail::allocator_traits<bucket_allocator>
2935 : bucket_allocator_traits;
2936 : typedef typename node_allocator_traits::pointer node_pointer;
2937 : typedef
2938 : typename node_allocator_traits::const_pointer const_node_pointer;
2939 : typedef typename bucket_allocator_traits::pointer bucket_pointer;
2940 : typedef boost::unordered::detail::node_constructor<node_allocator>
2941 : node_constructor;
2942 : typedef boost::unordered::detail::node_tmp<node_allocator> node_tmp;
2943 :
2944 : typedef std::pair<iterator, bool> emplace_return;
2945 :
2946 : ////////////////////////////////////////////////////////////////////////
2947 : // Members
2948 :
2949 : boost::unordered::detail::compressed<bucket_allocator, node_allocator>
2950 : allocators_;
2951 : std::size_t bucket_count_;
2952 : std::size_t size_;
2953 : float mlf_;
2954 : std::size_t max_load_;
2955 : bucket_pointer buckets_;
2956 :
2957 : ////////////////////////////////////////////////////////////////////////
2958 : // Data access
2959 :
2960 26493 : static node_pointer get_node(c_iterator it) { return it.node_; }
2961 :
2962 20225343 : static node_pointer next_node(link_pointer n)
2963 : {
2964 : return static_cast<node_pointer>(n->next_);
2965 : }
2966 :
2967 : static node_pointer next_for_find(link_pointer n)
2968 : {
2969 : node_pointer n2 = static_cast<node_pointer>(n);
2970 : do {
2971 11559460 : n2 = next_node(n2);
2972 11559460 : } while (n2 && !n2->is_first_in_group());
2973 : return n2;
2974 : }
2975 :
2976 0 : node_pointer next_group(node_pointer n) const
2977 : {
2978 : node_pointer n1 = n;
2979 : do {
2980 8226120 : n1 = next_node(n1);
2981 8226120 : } while (n1 && !n1->is_first_in_group());
2982 : return n1;
2983 : }
2984 :
2985 : std::size_t group_count(node_pointer n) const
2986 : {
2987 : std::size_t x = 0;
2988 : node_pointer it = n;
2989 : do {
2990 41352 : ++x;
2991 41352 : it = next_node(it);
2992 41352 : } while (it && !it->is_first_in_group());
2993 :
2994 : return x;
2995 : }
2996 :
2997 18544881 : std::size_t node_bucket(node_pointer n) const
2998 : {
2999 18544881 : return n->get_bucket();
3000 : }
3001 :
3002 : bucket_allocator const& bucket_alloc() const
3003 : {
3004 : return allocators_.first();
3005 : }
3006 :
3007 0 : node_allocator const& node_alloc() const
3008 : {
3009 0 : return allocators_.second();
3010 : }
3011 :
3012 102604 : bucket_allocator& bucket_alloc() { return allocators_.first(); }
3013 :
3014 2449110 : node_allocator& node_alloc() { return allocators_.second(); }
3015 :
3016 : std::size_t max_bucket_count() const
3017 : {
3018 : // -1 to account for the start bucket.
3019 : return policy::prev_bucket_count(
3020 : bucket_allocator_traits::max_size(bucket_alloc()) - 1);
3021 : }
3022 :
3023 45848380 : bucket_pointer get_bucket_pointer(std::size_t bucket_index) const
3024 : {
3025 0 : BOOST_ASSERT(buckets_);
3026 45848380 : return buckets_ + static_cast<std::ptrdiff_t>(bucket_index);
3027 : }
3028 :
3029 1566055 : link_pointer get_previous_start() const
3030 : {
3031 246871 : return get_bucket_pointer(bucket_count_)->first_from_start();
3032 : }
3033 :
3034 37410079 : link_pointer get_previous_start(std::size_t bucket_index) const
3035 : {
3036 37383579 : return get_bucket_pointer(bucket_index)->next_;
3037 : }
3038 :
3039 695285 : node_pointer begin() const
3040 : {
3041 942108 : return size_ ? next_node(get_previous_start()) : node_pointer();
3042 : }
3043 :
3044 37712881 : node_pointer begin(std::size_t bucket_index) const
3045 : {
3046 37712881 : if (!size_)
3047 : return node_pointer();
3048 37383579 : link_pointer prev = get_previous_start(bucket_index);
3049 37383579 : return prev ? next_node(prev) : node_pointer();
3050 : }
3051 :
3052 43308114 : std::size_t hash_to_bucket(std::size_t hash_value) const
3053 : {
3054 43308114 : return policy::to_bucket(bucket_count_, hash_value);
3055 : }
3056 :
3057 0 : std::size_t bucket_size(std::size_t index) const
3058 : {
3059 0 : node_pointer n = begin(index);
3060 0 : if (!n)
3061 : return 0;
3062 :
3063 : std::size_t count = 0;
3064 0 : while (n && node_bucket(n) == index) {
3065 0 : ++count;
3066 0 : n = next_node(n);
3067 : }
3068 :
3069 : return count;
3070 : }
3071 :
3072 : ////////////////////////////////////////////////////////////////////////
3073 : // Load methods
3074 :
3075 82687 : void recalculate_max_load()
3076 : {
3077 : using namespace std;
3078 :
3079 : // From 6.3.1/13:
3080 : // Only resize when size >= mlf_ * count
3081 82687 : max_load_ = buckets_ ? boost::unordered::detail::double_to_size(
3082 82687 : ceil(static_cast<double>(mlf_) *
3083 82687 : static_cast<double>(bucket_count_)))
3084 : : 0;
3085 82687 : }
3086 :
3087 : void max_load_factor(float z)
3088 : {
3089 : BOOST_ASSERT(z > 0);
3090 : mlf_ = (std::max)(z, minimum_max_load_factor);
3091 : recalculate_max_load();
3092 : }
3093 :
3094 82687 : std::size_t min_buckets_for_size(std::size_t size) const
3095 : {
3096 82687 : BOOST_ASSERT(mlf_ >= minimum_max_load_factor);
3097 :
3098 : using namespace std;
3099 :
3100 : // From insert/emplace requirements:
3101 : //
3102 : // size <= mlf_ * count
3103 : // => count >= size / mlf_
3104 : //
3105 : // Or from rehash post-condition:
3106 : //
3107 : // count >= size / mlf_
3108 :
3109 82687 : return policy::new_bucket_count(
3110 : boost::unordered::detail::double_to_size(
3111 82687 : floor(static_cast<double>(size) / static_cast<double>(mlf_)) +
3112 82687 : 1));
3113 : }
3114 :
3115 : ////////////////////////////////////////////////////////////////////////
3116 : // Constructors
3117 :
3118 304103 : table(std::size_t num_buckets, hasher const& hf, key_equal const& eq,
3119 : node_allocator const& a)
3120 : : functions(hf, eq), allocators_(a, a),
3121 1 : bucket_count_(policy::new_bucket_count(num_buckets)), size_(0),
3122 304103 : mlf_(1.0f), max_load_(0), buckets_()
3123 : {
3124 304102 : }
3125 :
3126 0 : table(table const& x, node_allocator const& a)
3127 : : functions(x), allocators_(a, a),
3128 0 : bucket_count_(x.min_buckets_for_size(x.size_)), size_(0),
3129 0 : mlf_(x.mlf_), max_load_(0), buckets_()
3130 : {
3131 : }
3132 :
3133 0 : table(table& x, boost::unordered::detail::move_tag m)
3134 0 : : functions(x, m), allocators_(x.allocators_, m),
3135 0 : bucket_count_(x.bucket_count_), size_(x.size_), mlf_(x.mlf_),
3136 0 : max_load_(x.max_load_), buckets_(x.buckets_)
3137 : {
3138 0 : x.buckets_ = bucket_pointer();
3139 0 : x.size_ = 0;
3140 0 : x.max_load_ = 0;
3141 : }
3142 :
3143 : table(table& x, node_allocator const& a,
3144 : boost::unordered::detail::move_tag m)
3145 : : functions(x, m), allocators_(a, a),
3146 : bucket_count_(x.bucket_count_), size_(0), mlf_(x.mlf_),
3147 : max_load_(0), buckets_()
3148 : {
3149 : }
3150 :
3151 : ////////////////////////////////////////////////////////////////////////
3152 : // Clear buckets and Create buckets
3153 : //
3154 : // IMPORTANT: If the container already contains any elements, the
3155 : // buckets will not contain any links to them. This will
3156 : // need to be dealt with, for example by:
3157 : // - deleting them
3158 : // - putting them in a 'node_holder' for future use
3159 : // (as in assignment)
3160 : // - placing them in buckets (see rehash_impl)
3161 :
3162 : // Clear the bucket pointers.
3163 0 : void clear_buckets()
3164 : {
3165 0 : bucket_pointer end = get_bucket_pointer(bucket_count_);
3166 0 : for (bucket_pointer it = buckets_; it != end; ++it) {
3167 0 : it->next_ = node_pointer();
3168 : }
3169 0 : }
3170 :
3171 : // Create container buckets. If the container already contains any
3172 : // buckets
3173 : // the linked list will be transferred to the new buckets, but none
3174 : // of the bucket pointers will be set. See above note.
3175 : //
3176 : // Strong exception safety.
3177 82687 : void create_buckets(std::size_t new_count)
3178 : {
3179 : link_pointer dummy_node;
3180 :
3181 : // Construct the new buckets and dummy node, and destroy the old
3182 : // buckets
3183 82687 : if (buckets_) {
3184 7529 : dummy_node =
3185 7529 : (buckets_ + static_cast<std::ptrdiff_t>(bucket_count_))->next_;
3186 : bucket_pointer new_buckets =
3187 7529 : bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3188 7529 : destroy_buckets();
3189 7529 : buckets_ = new_buckets;
3190 : } else if (bucket::extra_node) {
3191 : node_constructor a(node_alloc());
3192 : a.create_node();
3193 : buckets_ =
3194 : bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3195 : dummy_node = a.release();
3196 : } else {
3197 75158 : dummy_node = link_pointer();
3198 75158 : buckets_ =
3199 150316 : bucket_allocator_traits::allocate(bucket_alloc(), new_count + 1);
3200 : }
3201 :
3202 : // nothrow from here...
3203 82687 : bucket_count_ = new_count;
3204 82687 : recalculate_max_load();
3205 :
3206 82687 : bucket_pointer end =
3207 82687 : buckets_ + static_cast<std::ptrdiff_t>(new_count);
3208 16596744 : for (bucket_pointer i = buckets_; i != end; ++i) {
3209 16514040 : new ((void*)boost::to_address(i)) bucket();
3210 : }
3211 82687 : new ((void*)boost::to_address(end)) bucket(dummy_node);
3212 82687 : }
3213 :
3214 : ////////////////////////////////////////////////////////////////////////
3215 : // Swap and Move
3216 :
3217 : void swap_allocators(table& other, false_type)
3218 : {
3219 : boost::unordered::detail::func::ignore_unused_variable_warning(other);
3220 :
3221 : // According to 23.2.1.8, if propagate_on_container_swap is
3222 : // false the behaviour is undefined unless the allocators
3223 : // are equal.
3224 : BOOST_ASSERT(node_alloc() == other.node_alloc());
3225 : }
3226 :
3227 : void swap_allocators(table& other, true_type)
3228 : {
3229 : allocators_.swap(other.allocators_);
3230 : }
3231 :
3232 : // Not nothrow swappable
3233 : void swap(table& x, false_type)
3234 : {
3235 : if (this == &x) {
3236 : return;
3237 : }
3238 :
3239 : this->construct_spare_functions(x.current_functions());
3240 : BOOST_TRY { x.construct_spare_functions(this->current_functions()); }
3241 : BOOST_CATCH(...)
3242 : {
3243 : this->cleanup_spare_functions();
3244 : BOOST_RETHROW
3245 : }
3246 : BOOST_CATCH_END
3247 : this->switch_functions();
3248 : x.switch_functions();
3249 :
3250 : swap_allocators(
3251 : x, boost::unordered::detail::integral_constant<bool,
3252 : allocator_traits<
3253 : node_allocator>::propagate_on_container_swap::value>());
3254 :
3255 : boost::swap(buckets_, x.buckets_);
3256 : boost::swap(bucket_count_, x.bucket_count_);
3257 : boost::swap(size_, x.size_);
3258 : std::swap(mlf_, x.mlf_);
3259 : std::swap(max_load_, x.max_load_);
3260 : }
3261 :
3262 : // Nothrow swappable
3263 : void swap(table& x, true_type)
3264 : {
3265 : swap_allocators(
3266 : x, boost::unordered::detail::integral_constant<bool,
3267 : allocator_traits<
3268 : node_allocator>::propagate_on_container_swap::value>());
3269 :
3270 : boost::swap(buckets_, x.buckets_);
3271 : boost::swap(bucket_count_, x.bucket_count_);
3272 : boost::swap(size_, x.size_);
3273 : std::swap(mlf_, x.mlf_);
3274 : std::swap(max_load_, x.max_load_);
3275 : this->current_functions().swap(x.current_functions());
3276 : }
3277 :
3278 : // Only swaps the allocators if propagate_on_container_swap.
3279 : // If not propagate_on_container_swap and allocators aren't
3280 : // equal, behaviour is undefined.
3281 : void swap(table& x)
3282 : {
3283 : BOOST_ASSERT(allocator_traits<
3284 : node_allocator>::propagate_on_container_swap::value ||
3285 : node_alloc() == x.node_alloc());
3286 : swap(x, boost::unordered::detail::integral_constant<bool,
3287 : functions::nothrow_swappable>());
3288 : }
3289 :
3290 : // Only call with nodes allocated with the currect allocator, or
3291 : // one that is equal to it. (Can't assert because other's
3292 : // allocators might have already been moved).
3293 : void move_buckets_from(table& other)
3294 : {
3295 : BOOST_ASSERT(!buckets_);
3296 : buckets_ = other.buckets_;
3297 : bucket_count_ = other.bucket_count_;
3298 : size_ = other.size_;
3299 : max_load_ = other.max_load_;
3300 : other.buckets_ = bucket_pointer();
3301 : other.size_ = 0;
3302 : other.max_load_ = 0;
3303 : }
3304 :
3305 : // For use in the constructor when allocators might be different.
3306 : void move_construct_buckets(table& src)
3307 : {
3308 : if (this->node_alloc() == src.node_alloc()) {
3309 : move_buckets_from(src);
3310 : } else {
3311 : this->create_buckets(this->bucket_count_);
3312 : link_pointer prev = this->get_previous_start();
3313 : std::size_t last_bucket = this->bucket_count_;
3314 : for (node_pointer n = src.begin(); n; n = next_node(n)) {
3315 : std::size_t n_bucket = n->get_bucket();
3316 : if (n_bucket != last_bucket) {
3317 : this->get_bucket_pointer(n_bucket)->next_ = prev;
3318 : }
3319 : node_pointer n2 = boost::unordered::detail::func::construct_node(
3320 : this->node_alloc(), boost::move(n->value()));
3321 : n2->bucket_info_ = n->bucket_info_;
3322 : prev->next_ = n2;
3323 : ++size_;
3324 : prev = n2;
3325 : last_bucket = n_bucket;
3326 : }
3327 : }
3328 : }
3329 :
3330 : ////////////////////////////////////////////////////////////////////////
3331 : // Delete/destruct
3332 :
3333 55170 : ~table() { delete_buckets(); }
3334 :
3335 128376 : void destroy_node(node_pointer n)
3336 : {
3337 128376 : BOOST_UNORDERED_CALL_DESTROY(
3338 : node_allocator_traits, node_alloc(), n->value_ptr());
3339 128376 : boost::unordered::detail::func::destroy(boost::to_address(n));
3340 128376 : node_allocator_traits::deallocate(node_alloc(), n, 1);
3341 : }
3342 :
3343 55170 : void delete_buckets()
3344 : {
3345 55170 : if (buckets_) {
3346 12388 : node_pointer n = static_cast<node_pointer>(
3347 12388 : get_bucket_pointer(bucket_count_)->next_);
3348 :
3349 : if (bucket::extra_node) {
3350 : node_pointer next = next_node(n);
3351 : boost::unordered::detail::func::destroy(boost::to_address(n));
3352 : node_allocator_traits::deallocate(node_alloc(), n, 1);
3353 : n = next;
3354 : }
3355 :
3356 12388 : while (n) {
3357 0 : node_pointer next = next_node(n);
3358 0 : destroy_node(n);
3359 0 : n = next;
3360 : }
3361 :
3362 12388 : destroy_buckets();
3363 12388 : buckets_ = bucket_pointer();
3364 12388 : max_load_ = 0;
3365 12388 : size_ = 0;
3366 : }
3367 55170 : }
3368 :
3369 19917 : void destroy_buckets()
3370 : {
3371 19917 : bucket_pointer end = get_bucket_pointer(bucket_count_ + 1);
3372 19917 : for (bucket_pointer it = buckets_; it != end; ++it) {
3373 : boost::unordered::detail::func::destroy(boost::to_address(it));
3374 : }
3375 :
3376 19917 : bucket_allocator_traits::deallocate(
3377 : bucket_alloc(), buckets_, bucket_count_ + 1);
3378 19917 : }
3379 :
3380 : ////////////////////////////////////////////////////////////////////////
3381 : // Fix buckets after delete/extract
3382 : //
3383 : // (prev,next) should mark an open range of nodes in a single bucket
3384 : // which
3385 : // have either been unlinked, or are about to be.
3386 :
3387 26493 : std::size_t fix_bucket(
3388 : std::size_t bucket_index, link_pointer prev, node_pointer next)
3389 : {
3390 26493 : std::size_t bucket_index2 = bucket_index;
3391 :
3392 26493 : if (next) {
3393 26356 : bucket_index2 = node_bucket(next);
3394 :
3395 : // If next is in the same bucket, then there's nothing to do.
3396 26356 : if (bucket_index == bucket_index2) {
3397 : return bucket_index2;
3398 : }
3399 :
3400 : // Update the bucket containing next.
3401 16906 : get_bucket_pointer(bucket_index2)->next_ = prev;
3402 : }
3403 :
3404 : // Check if this bucket is now empty.
3405 17043 : bucket_pointer this_bucket = get_bucket_pointer(bucket_index);
3406 17043 : if (this_bucket->next_ == prev) {
3407 10603 : this_bucket->next_ = link_pointer();
3408 : }
3409 :
3410 : return bucket_index2;
3411 : }
3412 :
3413 : ////////////////////////////////////////////////////////////////////////
3414 : // Clear
3415 :
3416 : void clear_impl();
3417 :
3418 : ////////////////////////////////////////////////////////////////////////
3419 : // Assignment
3420 :
3421 : template <typename UniqueType>
3422 0 : void assign(table const& x, UniqueType is_unique)
3423 : {
3424 0 : if (this != &x) {
3425 0 : assign(x, is_unique,
3426 : boost::unordered::detail::integral_constant<bool,
3427 : allocator_traits<node_allocator>::
3428 : propagate_on_container_copy_assignment::value>());
3429 : }
3430 : }
3431 :
3432 : template <typename UniqueType>
3433 0 : void assign(table const& x, UniqueType is_unique, false_type)
3434 : {
3435 : // Strong exception safety.
3436 0 : this->construct_spare_functions(x.current_functions());
3437 : BOOST_TRY
3438 : {
3439 0 : mlf_ = x.mlf_;
3440 0 : recalculate_max_load();
3441 :
3442 0 : if (x.size_ > max_load_) {
3443 0 : create_buckets(min_buckets_for_size(x.size_));
3444 0 : } else if (size_) {
3445 0 : clear_buckets();
3446 : }
3447 : }
3448 0 : BOOST_CATCH(...)
3449 : {
3450 0 : this->cleanup_spare_functions();
3451 0 : BOOST_RETHROW
3452 : }
3453 : BOOST_CATCH_END
3454 0 : this->switch_functions();
3455 0 : assign_buckets(x, is_unique);
3456 0 : }
3457 :
3458 : template <typename UniqueType>
3459 : void assign(table const& x, UniqueType is_unique, true_type)
3460 : {
3461 : if (node_alloc() == x.node_alloc()) {
3462 : allocators_.assign(x.allocators_);
3463 : assign(x, is_unique, false_type());
3464 : } else {
3465 : this->construct_spare_functions(x.current_functions());
3466 : this->switch_functions();
3467 :
3468 : // Delete everything with current allocators before assigning
3469 : // the new ones.
3470 : delete_buckets();
3471 : allocators_.assign(x.allocators_);
3472 :
3473 : // Copy over other data, all no throw.
3474 : mlf_ = x.mlf_;
3475 : bucket_count_ = min_buckets_for_size(x.size_);
3476 :
3477 : // Finally copy the elements.
3478 : if (x.size_) {
3479 : copy_buckets(x, is_unique);
3480 : }
3481 : }
3482 : }
3483 :
3484 : template <typename UniqueType>
3485 : void move_assign(table& x, UniqueType is_unique)
3486 : {
3487 : if (this != &x) {
3488 : move_assign(x, is_unique,
3489 : boost::unordered::detail::integral_constant<bool,
3490 : allocator_traits<node_allocator>::
3491 : propagate_on_container_move_assignment::value>());
3492 : }
3493 : }
3494 :
3495 : // Propagate allocator
3496 : template <typename UniqueType>
3497 : void move_assign(table& x, UniqueType, true_type)
3498 : {
3499 : if (!functions::nothrow_move_assignable) {
3500 : this->construct_spare_functions(x.current_functions());
3501 : this->switch_functions();
3502 : } else {
3503 : this->current_functions().move_assign(x.current_functions());
3504 : }
3505 : delete_buckets();
3506 : allocators_.move_assign(x.allocators_);
3507 : mlf_ = x.mlf_;
3508 : move_buckets_from(x);
3509 : }
3510 :
3511 : // Don't propagate allocator
3512 : template <typename UniqueType>
3513 : void move_assign(table& x, UniqueType is_unique, false_type)
3514 : {
3515 : if (node_alloc() == x.node_alloc()) {
3516 : move_assign_equal_alloc(x);
3517 : } else {
3518 : move_assign_realloc(x, is_unique);
3519 : }
3520 : }
3521 :
3522 : void move_assign_equal_alloc(table& x)
3523 : {
3524 : if (!functions::nothrow_move_assignable) {
3525 : this->construct_spare_functions(x.current_functions());
3526 : this->switch_functions();
3527 : } else {
3528 : this->current_functions().move_assign(x.current_functions());
3529 : }
3530 : delete_buckets();
3531 : mlf_ = x.mlf_;
3532 : move_buckets_from(x);
3533 : }
3534 :
3535 : template <typename UniqueType>
3536 : void move_assign_realloc(table& x, UniqueType is_unique)
3537 : {
3538 : this->construct_spare_functions(x.current_functions());
3539 : BOOST_TRY
3540 : {
3541 : mlf_ = x.mlf_;
3542 : recalculate_max_load();
3543 :
3544 : if (x.size_ > max_load_) {
3545 : create_buckets(min_buckets_for_size(x.size_));
3546 : } else if (size_) {
3547 : clear_buckets();
3548 : }
3549 : }
3550 : BOOST_CATCH(...)
3551 : {
3552 : this->cleanup_spare_functions();
3553 : BOOST_RETHROW
3554 : }
3555 : BOOST_CATCH_END
3556 : this->switch_functions();
3557 : move_assign_buckets(x, is_unique);
3558 : }
3559 :
3560 : // Accessors
3561 :
3562 45660034 : const_key_type& get_key(node_pointer n) const
3563 : {
3564 45660034 : return extractor::extract(n->value());
3565 : }
3566 :
3567 40859693 : std::size_t hash(const_key_type& k) const
3568 : {
3569 35263901 : return policy::apply_hash(this->hash_function(), k);
3570 : }
3571 :
3572 : // Find Node
3573 :
3574 2449030 : node_pointer find_node(std::size_t key_hash, const_key_type& k) const
3575 : {
3576 2449030 : return this->find_node_impl(key_hash, k, this->key_eq());
3577 : }
3578 :
3579 35263901 : node_pointer find_node(const_key_type& k) const
3580 : {
3581 35263901 : return this->find_node_impl(hash(k), k, this->key_eq());
3582 : }
3583 :
3584 : template <class Key, class Pred>
3585 37712322 : node_pointer find_node_impl(
3586 : std::size_t key_hash, Key const& k, Pred const& eq) const
3587 : {
3588 37712322 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
3589 37712322 : node_pointer n = this->begin(bucket_index);
3590 :
3591 : for (;;) {
3592 48850722 : if (!n)
3593 : return n;
3594 :
3595 40064422 : if (eq(k, this->get_key(n))) {
3596 22870522 : return n;
3597 17193840 : } else if (this->node_bucket(n) != bucket_index) {
3598 : return node_pointer();
3599 : }
3600 :
3601 48850722 : n = next_for_find(n);
3602 : }
3603 : }
3604 :
3605 : // Find the node before the key, so that it can be erased.
3606 0 : link_pointer find_previous_node(
3607 : const_key_type& k, std::size_t bucket_index)
3608 : {
3609 0 : link_pointer prev = this->get_previous_start(bucket_index);
3610 0 : if (!prev) {
3611 : return prev;
3612 : }
3613 :
3614 : for (;;) {
3615 0 : node_pointer n = next_node(prev);
3616 0 : if (!n) {
3617 : return link_pointer();
3618 0 : } else if (n->is_first_in_group()) {
3619 0 : if (node_bucket(n) != bucket_index) {
3620 : return link_pointer();
3621 0 : } else if (this->key_eq()(k, this->get_key(n))) {
3622 0 : return prev;
3623 : }
3624 : }
3625 : prev = n;
3626 : }
3627 : }
3628 :
3629 : // Extract and erase
3630 :
3631 : inline node_pointer extract_by_key(const_key_type& k)
3632 : {
3633 : if (!this->size_) {
3634 : return node_pointer();
3635 : }
3636 : std::size_t key_hash = this->hash(k);
3637 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
3638 : link_pointer prev = this->find_previous_node(k, bucket_index);
3639 : if (!prev) {
3640 : return node_pointer();
3641 : }
3642 : node_pointer n = next_node(prev);
3643 : node_pointer n2 = next_node(n);
3644 : if (n2) {
3645 : n2->set_first_in_group();
3646 : }
3647 : prev->next_ = n2;
3648 : --this->size_;
3649 : this->fix_bucket(bucket_index, prev, n2);
3650 : n->next_ = link_pointer();
3651 :
3652 : return n;
3653 : }
3654 :
3655 : // Reserve and rehash
3656 :
3657 : void reserve_for_insert(std::size_t);
3658 : void rehash(std::size_t);
3659 : void reserve(std::size_t);
3660 : void rehash_impl(std::size_t);
3661 :
3662 : ////////////////////////////////////////////////////////////////////////
3663 : // Unique keys
3664 :
3665 : // equals
3666 :
3667 : bool equals_unique(table const& other) const
3668 : {
3669 : if (this->size_ != other.size_)
3670 : return false;
3671 :
3672 : for (node_pointer n1 = this->begin(); n1; n1 = next_node(n1)) {
3673 : node_pointer n2 = other.find_node(other.get_key(n1));
3674 :
3675 : if (!n2 || n1->value() != n2->value())
3676 : return false;
3677 : }
3678 :
3679 : return true;
3680 : }
3681 :
3682 : // Emplace/Insert
3683 :
3684 80 : inline node_pointer add_node_unique(
3685 : node_pointer n, std::size_t key_hash)
3686 : {
3687 80 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
3688 80 : bucket_pointer b = this->get_bucket_pointer(bucket_index);
3689 :
3690 : n->bucket_info_ = bucket_index;
3691 80 : n->set_first_in_group();
3692 :
3693 80 : if (!b->next_) {
3694 42 : link_pointer start_node = this->get_previous_start();
3695 :
3696 42 : if (start_node->next_) {
3697 41 : this->get_bucket_pointer(node_bucket(next_node(start_node)))
3698 : ->next_ = n;
3699 : }
3700 :
3701 42 : b->next_ = start_node;
3702 42 : n->next_ = start_node->next_;
3703 42 : start_node->next_ = n;
3704 : } else {
3705 38 : n->next_ = b->next_->next_;
3706 38 : b->next_->next_ = n;
3707 : }
3708 :
3709 80 : ++this->size_;
3710 80 : return n;
3711 : }
3712 :
3713 80 : inline node_pointer resize_and_add_node_unique(
3714 : node_pointer n, std::size_t key_hash)
3715 : {
3716 160 : node_tmp b(n, this->node_alloc());
3717 80 : this->reserve_for_insert(this->size_ + 1);
3718 80 : return this->add_node_unique(b.release(), key_hash);
3719 : }
3720 :
3721 : template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3722 : iterator emplace_hint_unique(
3723 : c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
3724 : {
3725 : if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3726 : return iterator(hint.node_);
3727 : } else {
3728 : return emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
3729 : }
3730 : }
3731 :
3732 : template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3733 0 : emplace_return emplace_unique(
3734 : const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
3735 : {
3736 0 : std::size_t key_hash = this->hash(k);
3737 0 : node_pointer pos = this->find_node(key_hash, k);
3738 0 : if (pos) {
3739 0 : return emplace_return(iterator(pos), false);
3740 : } else {
3741 : return emplace_return(
3742 0 : iterator(this->resize_and_add_node_unique(
3743 0 : boost::unordered::detail::func::construct_node_from_args(
3744 : this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3745 : key_hash)),
3746 0 : true);
3747 : }
3748 : }
3749 :
3750 : template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3751 : iterator emplace_hint_unique(
3752 : c_iterator hint, no_key, BOOST_UNORDERED_EMPLACE_ARGS)
3753 : {
3754 : node_tmp b(boost::unordered::detail::func::construct_node_from_args(
3755 : this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3756 : this->node_alloc());
3757 : const_key_type& k = this->get_key(b.node_);
3758 : if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3759 : return iterator(hint.node_);
3760 : }
3761 : std::size_t key_hash = this->hash(k);
3762 : node_pointer pos = this->find_node(key_hash, k);
3763 : if (pos) {
3764 : return iterator(pos);
3765 : } else {
3766 : return iterator(
3767 : this->resize_and_add_node_unique(b.release(), key_hash));
3768 : }
3769 : }
3770 :
3771 : template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
3772 : emplace_return emplace_unique(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
3773 : {
3774 : node_tmp b(boost::unordered::detail::func::construct_node_from_args(
3775 : this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
3776 : this->node_alloc());
3777 : const_key_type& k = this->get_key(b.node_);
3778 : std::size_t key_hash = this->hash(k);
3779 : node_pointer pos = this->find_node(key_hash, k);
3780 : if (pos) {
3781 : return emplace_return(iterator(pos), false);
3782 : } else {
3783 : return emplace_return(
3784 : iterator(this->resize_and_add_node_unique(b.release(), key_hash)),
3785 : true);
3786 : }
3787 : }
3788 :
3789 : template <typename Key>
3790 80 : emplace_return try_emplace_unique(BOOST_FWD_REF(Key) k)
3791 : {
3792 80 : std::size_t key_hash = this->hash(k);
3793 80 : node_pointer pos = this->find_node(key_hash, k);
3794 80 : if (pos) {
3795 0 : return emplace_return(iterator(pos), false);
3796 : } else {
3797 : return emplace_return(
3798 80 : iterator(this->resize_and_add_node_unique(
3799 80 : boost::unordered::detail::func::construct_node_pair(
3800 : this->node_alloc(), boost::forward<Key>(k)),
3801 : key_hash)),
3802 160 : true);
3803 : }
3804 : }
3805 :
3806 : template <typename Key>
3807 : iterator try_emplace_hint_unique(c_iterator hint, BOOST_FWD_REF(Key) k)
3808 : {
3809 : if (hint.node_ && this->key_eq()(hint->first, k)) {
3810 : return iterator(hint.node_);
3811 : } else {
3812 : return try_emplace_unique(k).first;
3813 : }
3814 : }
3815 :
3816 : template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
3817 : emplace_return try_emplace_unique(
3818 : BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
3819 : {
3820 : std::size_t key_hash = this->hash(k);
3821 : node_pointer pos = this->find_node(key_hash, k);
3822 : if (pos) {
3823 : return emplace_return(iterator(pos), false);
3824 : } else {
3825 : return emplace_return(
3826 : iterator(this->resize_and_add_node_unique(
3827 : boost::unordered::detail::func::construct_node_pair_from_args(
3828 : this->node_alloc(), boost::forward<Key>(k),
3829 : BOOST_UNORDERED_EMPLACE_FORWARD),
3830 : key_hash)),
3831 : true);
3832 : }
3833 : }
3834 :
3835 : template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
3836 : iterator try_emplace_hint_unique(
3837 : c_iterator hint, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
3838 : {
3839 : if (hint.node_ && this->key_eq()(hint->first, k)) {
3840 : return iterator(hint.node_);
3841 : } else {
3842 : return try_emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
3843 : }
3844 : }
3845 :
3846 : template <typename Key, typename M>
3847 : emplace_return insert_or_assign_unique(
3848 : BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj)
3849 : {
3850 : std::size_t key_hash = this->hash(k);
3851 : node_pointer pos = this->find_node(key_hash, k);
3852 :
3853 : if (pos) {
3854 : pos->value().second = boost::forward<M>(obj);
3855 : return emplace_return(iterator(pos), false);
3856 : } else {
3857 : return emplace_return(
3858 : iterator(this->resize_and_add_node_unique(
3859 : boost::unordered::detail::func::construct_node_pair(
3860 : this->node_alloc(), boost::forward<Key>(k),
3861 : boost::forward<M>(obj)),
3862 : key_hash)),
3863 : true);
3864 : }
3865 : }
3866 :
3867 : template <typename NodeType, typename InsertReturnType>
3868 : void move_insert_node_type_unique(
3869 : NodeType& np, InsertReturnType& result)
3870 : {
3871 : if (np) {
3872 : const_key_type& k = this->get_key(np.ptr_);
3873 : std::size_t key_hash = this->hash(k);
3874 : node_pointer pos = this->find_node(key_hash, k);
3875 :
3876 : if (pos) {
3877 : result.node = boost::move(np);
3878 : result.position = iterator(pos);
3879 : } else {
3880 : this->reserve_for_insert(this->size_ + 1);
3881 : result.position =
3882 : iterator(this->add_node_unique(np.ptr_, key_hash));
3883 : result.inserted = true;
3884 : np.ptr_ = node_pointer();
3885 : }
3886 : }
3887 : }
3888 :
3889 : template <typename NodeType>
3890 : iterator move_insert_node_type_with_hint_unique(
3891 : c_iterator hint, NodeType& np)
3892 : {
3893 : if (!np) {
3894 : return iterator();
3895 : }
3896 : const_key_type& k = this->get_key(np.ptr_);
3897 : if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
3898 : return iterator(hint.node_);
3899 : }
3900 : std::size_t key_hash = this->hash(k);
3901 : node_pointer pos = this->find_node(key_hash, k);
3902 : if (!pos) {
3903 : this->reserve_for_insert(this->size_ + 1);
3904 : pos = this->add_node_unique(np.ptr_, key_hash);
3905 : np.ptr_ = node_pointer();
3906 : }
3907 : return iterator(pos);
3908 : }
3909 :
3910 : template <typename Types2>
3911 : void merge_unique(boost::unordered::detail::table<Types2>& other)
3912 : {
3913 : typedef boost::unordered::detail::table<Types2> other_table;
3914 : BOOST_STATIC_ASSERT(
3915 : (boost::is_same<node, typename other_table::node>::value));
3916 : BOOST_ASSERT(this->node_alloc() == other.node_alloc());
3917 :
3918 : if (other.size_) {
3919 : link_pointer prev = other.get_previous_start();
3920 :
3921 : while (prev->next_) {
3922 : node_pointer n = other_table::next_node(prev);
3923 : const_key_type& k = this->get_key(n);
3924 : std::size_t key_hash = this->hash(k);
3925 : node_pointer pos = this->find_node(key_hash, k);
3926 :
3927 : if (pos) {
3928 : prev = n;
3929 : } else {
3930 : this->reserve_for_insert(this->size_ + 1);
3931 : node_pointer n2 = next_node(n);
3932 : prev->next_ = n2;
3933 : if (n2 && n->is_first_in_group()) {
3934 : n2->set_first_in_group();
3935 : }
3936 : --other.size_;
3937 : other.fix_bucket(other.node_bucket(n), prev, n2);
3938 : this->add_node_unique(n, key_hash);
3939 : }
3940 : }
3941 : }
3942 : }
3943 :
3944 : ////////////////////////////////////////////////////////////////////////
3945 : // Insert range methods
3946 : //
3947 : // if hash function throws, or inserting > 1 element, basic exception
3948 : // safety strong otherwise
3949 :
3950 : template <class InputIt>
3951 0 : void insert_range_unique(const_key_type& k, InputIt i, InputIt j)
3952 : {
3953 0 : insert_range_unique2(k, i, j);
3954 :
3955 0 : while (++i != j) {
3956 : // Note: can't use get_key as '*i' might not be value_type - it
3957 : // could be a pair with first_types as key_type without const or
3958 : // a different second_type.
3959 0 : insert_range_unique2(extractor::extract(*i), i, j);
3960 : }
3961 0 : }
3962 :
3963 : template <class InputIt>
3964 0 : void insert_range_unique2(const_key_type& k, InputIt i, InputIt j)
3965 : {
3966 : // No side effects in this initial code
3967 0 : std::size_t key_hash = this->hash(k);
3968 0 : node_pointer pos = this->find_node(key_hash, k);
3969 :
3970 0 : if (!pos) {
3971 0 : node_tmp b(boost::unordered::detail::func::construct_node(
3972 0 : this->node_alloc(), *i),
3973 : this->node_alloc());
3974 0 : if (this->size_ + 1 > this->max_load_)
3975 0 : this->reserve_for_insert(
3976 0 : this->size_ + boost::unordered::detail::insert_size(i, j));
3977 0 : this->add_node_unique(b.release(), key_hash);
3978 : }
3979 0 : }
3980 :
3981 : template <class InputIt>
3982 : void insert_range_unique(no_key, InputIt i, InputIt j)
3983 : {
3984 : node_constructor a(this->node_alloc());
3985 :
3986 : do {
3987 : if (!a.node_) {
3988 : a.create_node();
3989 : }
3990 : BOOST_UNORDERED_CALL_CONSTRUCT1(
3991 : node_allocator_traits, a.alloc_, a.node_->value_ptr(), *i);
3992 : node_tmp b(a.release(), a.alloc_);
3993 :
3994 : const_key_type& k = this->get_key(b.node_);
3995 : std::size_t key_hash = this->hash(k);
3996 : node_pointer pos = this->find_node(key_hash, k);
3997 :
3998 : if (pos) {
3999 : a.reclaim(b.release());
4000 : } else {
4001 : // reserve has basic exception safety if the hash function
4002 : // throws, strong otherwise.
4003 : this->reserve_for_insert(this->size_ + 1);
4004 : this->add_node_unique(b.release(), key_hash);
4005 : }
4006 : } while (++i != j);
4007 : }
4008 :
4009 : ////////////////////////////////////////////////////////////////////////
4010 : // Extract
4011 :
4012 : inline node_pointer extract_by_iterator_unique(c_iterator i)
4013 : {
4014 : node_pointer n = i.node_;
4015 : BOOST_ASSERT(n);
4016 : std::size_t bucket_index = this->node_bucket(n);
4017 : link_pointer prev = this->get_previous_start(bucket_index);
4018 : while (prev->next_ != n) {
4019 : prev = prev->next_;
4020 : }
4021 : node_pointer n2 = next_node(n);
4022 : prev->next_ = n2;
4023 : --this->size_;
4024 : this->fix_bucket(bucket_index, prev, n2);
4025 : n->next_ = link_pointer();
4026 : return n;
4027 : }
4028 :
4029 : ////////////////////////////////////////////////////////////////////////
4030 : // Erase
4031 : //
4032 : // no throw
4033 :
4034 0 : std::size_t erase_key_unique(const_key_type& k)
4035 : {
4036 0 : if (!this->size_)
4037 : return 0;
4038 0 : std::size_t key_hash = this->hash(k);
4039 0 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
4040 0 : link_pointer prev = this->find_previous_node(k, bucket_index);
4041 0 : if (!prev)
4042 : return 0;
4043 0 : node_pointer n = next_node(prev);
4044 0 : node_pointer n2 = next_node(n);
4045 0 : prev->next_ = n2;
4046 0 : --size_;
4047 0 : this->fix_bucket(bucket_index, prev, n2);
4048 0 : this->destroy_node(n);
4049 0 : return 1;
4050 : }
4051 :
4052 : void erase_nodes_unique(node_pointer i, node_pointer j)
4053 : {
4054 : std::size_t bucket_index = this->node_bucket(i);
4055 :
4056 : // Find the node before i.
4057 : link_pointer prev = this->get_previous_start(bucket_index);
4058 : while (prev->next_ != i)
4059 : prev = prev->next_;
4060 :
4061 : // Delete the nodes.
4062 : prev->next_ = j;
4063 : do {
4064 : node_pointer next = next_node(i);
4065 : destroy_node(i);
4066 : --size_;
4067 : bucket_index = this->fix_bucket(bucket_index, prev, next);
4068 : i = next;
4069 : } while (i != j);
4070 : }
4071 :
4072 : ////////////////////////////////////////////////////////////////////////
4073 : // fill_buckets_unique
4074 :
4075 : void copy_buckets(table const& src, true_type)
4076 : {
4077 : this->create_buckets(this->bucket_count_);
4078 :
4079 : for (node_pointer n = src.begin(); n; n = next_node(n)) {
4080 : std::size_t key_hash = this->hash(this->get_key(n));
4081 : this->add_node_unique(
4082 : boost::unordered::detail::func::construct_node(
4083 : this->node_alloc(), n->value()),
4084 : key_hash);
4085 : }
4086 : }
4087 :
4088 : void assign_buckets(table const& src, true_type)
4089 : {
4090 : node_holder<node_allocator> holder(*this);
4091 : for (node_pointer n = src.begin(); n; n = next_node(n)) {
4092 : std::size_t key_hash = this->hash(this->get_key(n));
4093 : this->add_node_unique(holder.copy_of(n->value()), key_hash);
4094 : }
4095 : }
4096 :
4097 : void move_assign_buckets(table& src, true_type)
4098 : {
4099 : node_holder<node_allocator> holder(*this);
4100 : for (node_pointer n = src.begin(); n; n = next_node(n)) {
4101 : std::size_t key_hash = this->hash(this->get_key(n));
4102 : this->add_node_unique(holder.move_copy_of(n->value()), key_hash);
4103 : }
4104 : }
4105 :
4106 : ////////////////////////////////////////////////////////////////////////
4107 : // Equivalent keys
4108 :
4109 : // Equality
4110 :
4111 : bool equals_equiv(table const& other) const
4112 : {
4113 : if (this->size_ != other.size_)
4114 : return false;
4115 :
4116 : for (node_pointer n1 = this->begin(); n1;) {
4117 : node_pointer n2 = other.find_node(other.get_key(n1));
4118 : if (!n2)
4119 : return false;
4120 : node_pointer end1 = next_group(n1);
4121 : node_pointer end2 = next_group(n2);
4122 : if (!group_equals_equiv(n1, end1, n2, end2))
4123 : return false;
4124 : n1 = end1;
4125 : }
4126 :
4127 : return true;
4128 : }
4129 :
4130 : static bool group_equals_equiv(node_pointer n1, node_pointer end1,
4131 : node_pointer n2, node_pointer end2)
4132 : {
4133 : for (;;) {
4134 : if (n1->value() != n2->value())
4135 : break;
4136 :
4137 : n1 = next_node(n1);
4138 : n2 = next_node(n2);
4139 :
4140 : if (n1 == end1)
4141 : return n2 == end2;
4142 : if (n2 == end2)
4143 : return false;
4144 : }
4145 :
4146 : for (node_pointer n1a = n1, n2a = n2;;) {
4147 : n1a = next_node(n1a);
4148 : n2a = next_node(n2a);
4149 :
4150 : if (n1a == end1) {
4151 : if (n2a == end2)
4152 : break;
4153 : else
4154 : return false;
4155 : }
4156 :
4157 : if (n2a == end2)
4158 : return false;
4159 : }
4160 :
4161 : node_pointer start = n1;
4162 : for (; n1 != end1; n1 = next_node(n1)) {
4163 : value_type const& v = n1->value();
4164 : if (!find_equiv(start, n1, v)) {
4165 : std::size_t matches = count_equal_equiv(n2, end2, v);
4166 : if (!matches)
4167 : return false;
4168 : if (matches != 1 + count_equal_equiv(next_node(n1), end1, v))
4169 : return false;
4170 : }
4171 : }
4172 :
4173 : return true;
4174 : }
4175 :
4176 : static bool find_equiv(
4177 : node_pointer n, node_pointer end, value_type const& v)
4178 : {
4179 : for (; n != end; n = next_node(n))
4180 : if (n->value() == v)
4181 : return true;
4182 : return false;
4183 : }
4184 :
4185 : static std::size_t count_equal_equiv(
4186 : node_pointer n, node_pointer end, value_type const& v)
4187 : {
4188 : std::size_t count = 0;
4189 : for (; n != end; n = next_node(n))
4190 : if (n->value() == v)
4191 : ++count;
4192 : return count;
4193 : }
4194 :
4195 : // Emplace/Insert
4196 :
4197 2448950 : inline node_pointer add_node_equiv(
4198 : node_pointer n, std::size_t key_hash, node_pointer pos)
4199 : {
4200 2448950 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
4201 : n->bucket_info_ = bucket_index;
4202 :
4203 2448950 : if (pos) {
4204 63675 : n->reset_first_in_group();
4205 63675 : n->next_ = pos->next_;
4206 63675 : pos->next_ = n;
4207 63675 : if (n->next_) {
4208 61602 : std::size_t next_bucket = this->node_bucket(next_node(n));
4209 61602 : if (next_bucket != bucket_index) {
4210 24982 : this->get_bucket_pointer(next_bucket)->next_ = n;
4211 : }
4212 : }
4213 : } else {
4214 2385280 : n->set_first_in_group();
4215 4770550 : bucket_pointer b = this->get_bucket_pointer(bucket_index);
4216 :
4217 2385280 : if (!b->next_) {
4218 1311660 : link_pointer start_node = this->get_previous_start();
4219 :
4220 1311660 : if (start_node->next_) {
4221 1236500 : this
4222 : ->get_bucket_pointer(this->node_bucket(next_node(start_node)))
4223 : ->next_ = n;
4224 : }
4225 :
4226 1311660 : b->next_ = start_node;
4227 1311660 : n->next_ = start_node->next_;
4228 1311660 : start_node->next_ = n;
4229 : } else {
4230 1073620 : n->next_ = b->next_->next_;
4231 1073620 : b->next_->next_ = n;
4232 : }
4233 : }
4234 2448950 : ++this->size_;
4235 2448950 : return n;
4236 : }
4237 :
4238 : inline node_pointer add_using_hint_equiv(
4239 : node_pointer n, node_pointer hint)
4240 : {
4241 : n->bucket_info_ = hint->bucket_info_;
4242 : n->reset_first_in_group();
4243 : n->next_ = hint->next_;
4244 : hint->next_ = n;
4245 : if (n->next_) {
4246 : std::size_t next_bucket = this->node_bucket(next_node(n));
4247 : if (next_bucket != this->node_bucket(n)) {
4248 : this->get_bucket_pointer(next_bucket)->next_ = n;
4249 : }
4250 : }
4251 : ++this->size_;
4252 : return n;
4253 : }
4254 :
4255 2448950 : iterator emplace_equiv(node_pointer n)
4256 : {
4257 0 : node_tmp a(n, this->node_alloc());
4258 2448950 : const_key_type& k = this->get_key(a.node_);
4259 2448950 : std::size_t key_hash = this->hash(k);
4260 2448950 : node_pointer position = this->find_node(key_hash, k);
4261 2448950 : this->reserve_for_insert(this->size_ + 1);
4262 2448950 : return iterator(
4263 2448950 : this->add_node_equiv(a.release(), key_hash, position));
4264 : }
4265 :
4266 : iterator emplace_hint_equiv(c_iterator hint, node_pointer n)
4267 : {
4268 : node_tmp a(n, this->node_alloc());
4269 : const_key_type& k = this->get_key(a.node_);
4270 : if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
4271 : this->reserve_for_insert(this->size_ + 1);
4272 : return iterator(
4273 : this->add_using_hint_equiv(a.release(), hint.node_));
4274 : } else {
4275 : std::size_t key_hash = this->hash(k);
4276 : node_pointer position = this->find_node(key_hash, k);
4277 : this->reserve_for_insert(this->size_ + 1);
4278 : return iterator(
4279 : this->add_node_equiv(a.release(), key_hash, position));
4280 : }
4281 : }
4282 :
4283 : void emplace_no_rehash_equiv(node_pointer n)
4284 : {
4285 : node_tmp a(n, this->node_alloc());
4286 : const_key_type& k = this->get_key(a.node_);
4287 : std::size_t key_hash = this->hash(k);
4288 : node_pointer position = this->find_node(key_hash, k);
4289 : this->add_node_equiv(a.release(), key_hash, position);
4290 : }
4291 :
4292 : template <typename NodeType>
4293 : iterator move_insert_node_type_equiv(NodeType& np)
4294 : {
4295 : iterator result;
4296 :
4297 : if (np) {
4298 : const_key_type& k = this->get_key(np.ptr_);
4299 : std::size_t key_hash = this->hash(k);
4300 : node_pointer pos = this->find_node(key_hash, k);
4301 : this->reserve_for_insert(this->size_ + 1);
4302 : result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos));
4303 : np.ptr_ = node_pointer();
4304 : }
4305 :
4306 : return result;
4307 : }
4308 :
4309 : template <typename NodeType>
4310 : iterator move_insert_node_type_with_hint_equiv(
4311 : c_iterator hint, NodeType& np)
4312 : {
4313 : iterator result;
4314 :
4315 : if (np) {
4316 : const_key_type& k = this->get_key(np.ptr_);
4317 :
4318 : if (hint.node_ && this->key_eq()(k, this->get_key(hint.node_))) {
4319 : this->reserve_for_insert(this->size_ + 1);
4320 : result =
4321 : iterator(this->add_using_hint_equiv(np.ptr_, hint.node_));
4322 : } else {
4323 : std::size_t key_hash = this->hash(k);
4324 : node_pointer pos = this->find_node(key_hash, k);
4325 : this->reserve_for_insert(this->size_ + 1);
4326 : result = iterator(this->add_node_equiv(np.ptr_, key_hash, pos));
4327 : }
4328 : np.ptr_ = node_pointer();
4329 : }
4330 :
4331 : return result;
4332 : }
4333 :
4334 : ////////////////////////////////////////////////////////////////////////
4335 : // Insert range methods
4336 :
4337 : // if hash function throws, or inserting > 1 element, basic exception
4338 : // safety. Strong otherwise
4339 : template <class I>
4340 : void insert_range_equiv(I i, I j,
4341 : typename boost::unordered::detail::enable_if_forward<I, void*>::type =
4342 : 0)
4343 : {
4344 : if (i == j)
4345 : return;
4346 :
4347 : std::size_t distance = static_cast<std::size_t>(std::distance(i, j));
4348 : if (distance == 1) {
4349 : emplace_equiv(boost::unordered::detail::func::construct_node(
4350 : this->node_alloc(), *i));
4351 : } else {
4352 : // Only require basic exception safety here
4353 : this->reserve_for_insert(this->size_ + distance);
4354 :
4355 : for (; i != j; ++i) {
4356 : emplace_no_rehash_equiv(
4357 : boost::unordered::detail::func::construct_node(
4358 : this->node_alloc(), *i));
4359 : }
4360 : }
4361 : }
4362 :
4363 : template <class I>
4364 : void insert_range_equiv(I i, I j,
4365 : typename boost::unordered::detail::disable_if_forward<I,
4366 : void*>::type = 0)
4367 : {
4368 : for (; i != j; ++i) {
4369 : emplace_equiv(boost::unordered::detail::func::construct_node(
4370 : this->node_alloc(), *i));
4371 : }
4372 : }
4373 :
4374 : ////////////////////////////////////////////////////////////////////////
4375 : // Extract
4376 :
4377 : inline node_pointer extract_by_iterator_equiv(c_iterator n)
4378 : {
4379 : node_pointer i = n.node_;
4380 : BOOST_ASSERT(i);
4381 : node_pointer j(next_node(i));
4382 : std::size_t bucket_index = this->node_bucket(i);
4383 :
4384 : link_pointer prev = this->get_previous_start(bucket_index);
4385 : while (prev->next_ != i) {
4386 : prev = next_node(prev);
4387 : }
4388 :
4389 : prev->next_ = j;
4390 : if (j && i->is_first_in_group()) {
4391 : j->set_first_in_group();
4392 : }
4393 : --this->size_;
4394 : this->fix_bucket(bucket_index, prev, j);
4395 : i->next_ = link_pointer();
4396 :
4397 : return i;
4398 : }
4399 :
4400 : ////////////////////////////////////////////////////////////////////////
4401 : // Erase
4402 : //
4403 : // no throw
4404 :
4405 0 : std::size_t erase_key_equiv(const_key_type& k)
4406 : {
4407 0 : if (!this->size_)
4408 : return 0;
4409 :
4410 0 : std::size_t key_hash = this->hash(k);
4411 0 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
4412 0 : link_pointer prev = this->find_previous_node(k, bucket_index);
4413 0 : if (!prev)
4414 : return 0;
4415 :
4416 0 : std::size_t deleted_count = 0;
4417 0 : node_pointer n = next_node(prev);
4418 : do {
4419 0 : node_pointer n2 = next_node(n);
4420 0 : destroy_node(n);
4421 0 : ++deleted_count;
4422 0 : n = n2;
4423 0 : } while (n && !n->is_first_in_group());
4424 0 : size_ -= deleted_count;
4425 0 : prev->next_ = n;
4426 0 : this->fix_bucket(bucket_index, prev, n);
4427 0 : return deleted_count;
4428 : }
4429 :
4430 26493 : link_pointer erase_nodes_equiv(node_pointer i, node_pointer j)
4431 : {
4432 26493 : std::size_t bucket_index = this->node_bucket(i);
4433 :
4434 26493 : link_pointer prev = this->get_previous_start(bucket_index);
4435 67625 : while (prev->next_ != i) {
4436 : prev = next_node(prev);
4437 : }
4438 :
4439 : // Delete the nodes.
4440 : // Is it inefficient to call fix_bucket for every node?
4441 26493 : bool includes_first = false;
4442 26493 : prev->next_ = j;
4443 : do {
4444 26493 : includes_first = includes_first || i->is_first_in_group();
4445 26493 : node_pointer next = next_node(i);
4446 52986 : destroy_node(i);
4447 26493 : --size_;
4448 26493 : bucket_index = this->fix_bucket(bucket_index, prev, next);
4449 26493 : i = next;
4450 26493 : } while (i != j);
4451 26493 : if (j && includes_first) {
4452 22641 : j->set_first_in_group();
4453 : }
4454 :
4455 26493 : return prev;
4456 : }
4457 :
4458 : ////////////////////////////////////////////////////////////////////////
4459 : // fill_buckets
4460 :
4461 0 : void copy_buckets(table const& src, false_type)
4462 : {
4463 0 : this->create_buckets(this->bucket_count_);
4464 :
4465 0 : for (node_pointer n = src.begin(); n;) {
4466 0 : std::size_t key_hash = this->hash(this->get_key(n));
4467 0 : node_pointer group_end(next_group(n));
4468 0 : node_pointer pos = this->add_node_equiv(
4469 0 : boost::unordered::detail::func::construct_node(
4470 : this->node_alloc(), n->value()),
4471 : key_hash, node_pointer());
4472 0 : for (n = next_node(n); n != group_end; n = next_node(n)) {
4473 0 : this->add_node_equiv(
4474 0 : boost::unordered::detail::func::construct_node(
4475 : this->node_alloc(), n->value()),
4476 : key_hash, pos);
4477 : }
4478 : }
4479 0 : }
4480 :
4481 0 : void assign_buckets(table const& src, false_type)
4482 : {
4483 0 : node_holder<node_allocator> holder(*this);
4484 0 : for (node_pointer n = src.begin(); n;) {
4485 0 : std::size_t key_hash = this->hash(this->get_key(n));
4486 0 : node_pointer group_end(next_group(n));
4487 0 : node_pointer pos = this->add_node_equiv(
4488 : holder.copy_of(n->value()), key_hash, node_pointer());
4489 0 : for (n = next_node(n); n != group_end; n = next_node(n)) {
4490 0 : this->add_node_equiv(holder.copy_of(n->value()), key_hash, pos);
4491 : }
4492 : }
4493 0 : }
4494 :
4495 : void move_assign_buckets(table& src, false_type)
4496 : {
4497 : node_holder<node_allocator> holder(*this);
4498 : for (node_pointer n = src.begin(); n;) {
4499 : std::size_t key_hash = this->hash(this->get_key(n));
4500 : node_pointer group_end(next_group(n));
4501 : node_pointer pos = this->add_node_equiv(
4502 : holder.move_copy_of(n->value()), key_hash, node_pointer());
4503 : for (n = next_node(n); n != group_end; n = next_node(n)) {
4504 : this->add_node_equiv(
4505 : holder.move_copy_of(n->value()), key_hash, pos);
4506 : }
4507 : }
4508 : }
4509 : };
4510 :
4511 : //////////////////////////////////////////////////////////////////////////
4512 : // Clear
4513 :
4514 54459 : template <typename Types> inline void table<Types>::clear_impl()
4515 : {
4516 54459 : if (size_) {
4517 12373 : bucket_pointer end = get_bucket_pointer(bucket_count_);
4518 1201360 : for (bucket_pointer it = buckets_; it != end; ++it) {
4519 1188990 : it->next_ = node_pointer();
4520 : }
4521 :
4522 12373 : link_pointer prev = end->first_from_start();
4523 12373 : node_pointer n = next_node(prev);
4524 12373 : prev->next_ = node_pointer();
4525 12373 : size_ = 0;
4526 :
4527 114256 : while (n) {
4528 101883 : node_pointer next = next_node(n);
4529 203766 : destroy_node(n);
4530 101883 : n = next;
4531 : }
4532 : }
4533 54459 : }
4534 :
4535 : //////////////////////////////////////////////////////////////////////////
4536 : // Reserve & Rehash
4537 :
4538 : // basic exception safety
4539 : template <typename Types>
4540 2449030 : inline void table<Types>::reserve_for_insert(std::size_t size)
4541 : {
4542 2449030 : if (!buckets_) {
4543 75158 : create_buckets((std::max)(bucket_count_, min_buckets_for_size(size)));
4544 2373879 : } else if (size > max_load_) {
4545 15058 : std::size_t num_buckets =
4546 15058 : min_buckets_for_size((std::max)(size, size_ + (size_ >> 1)));
4547 :
4548 7529 : if (num_buckets != bucket_count_)
4549 7529 : this->rehash_impl(num_buckets);
4550 : }
4551 2449030 : }
4552 :
4553 : // if hash function throws, basic exception safety
4554 : // strong otherwise.
4555 :
4556 : template <typename Types>
4557 0 : inline void table<Types>::rehash(std::size_t min_buckets)
4558 : {
4559 : using namespace std;
4560 :
4561 0 : if (!size_) {
4562 0 : delete_buckets();
4563 0 : bucket_count_ = policy::new_bucket_count(min_buckets);
4564 : } else {
4565 0 : min_buckets = policy::new_bucket_count((std::max)(min_buckets,
4566 0 : boost::unordered::detail::double_to_size(
4567 0 : floor(static_cast<double>(size_) / static_cast<double>(mlf_))) +
4568 0 : 1));
4569 :
4570 0 : if (min_buckets != bucket_count_)
4571 0 : this->rehash_impl(min_buckets);
4572 : }
4573 0 : }
4574 :
4575 : template <typename Types>
4576 7529 : inline void table<Types>::rehash_impl(std::size_t num_buckets)
4577 : {
4578 7529 : BOOST_ASSERT(this->buckets_);
4579 :
4580 7529 : this->create_buckets(num_buckets);
4581 7529 : link_pointer prev = this->get_previous_start();
4582 : BOOST_TRY
4583 : {
4584 3154265 : while (prev->next_) {
4585 3146732 : node_pointer n = next_node(prev);
4586 6293362 : std::size_t key_hash = this->hash(this->get_key(n));
4587 3146732 : std::size_t bucket_index = this->hash_to_bucket(key_hash);
4588 :
4589 : n->bucket_info_ = bucket_index;
4590 3146732 : n->set_first_in_group();
4591 :
4592 : // Iterator through the rest of the group of equal nodes,
4593 : // setting the bucket.
4594 : for (;;) {
4595 3187692 : node_pointer next = next_node(n);
4596 3187692 : if (!next || next->is_first_in_group()) {
4597 : break;
4598 : }
4599 40961 : n = next;
4600 : n->bucket_info_ = bucket_index;
4601 40961 : n->reset_first_in_group();
4602 : }
4603 :
4604 : // n is now the last node in the group
4605 3146732 : bucket_pointer b = this->get_bucket_pointer(bucket_index);
4606 3146732 : if (!b->next_) {
4607 2472800 : b->next_ = prev;
4608 2472800 : prev = n;
4609 : } else {
4610 673931 : link_pointer next = n->next_;
4611 673931 : n->next_ = b->next_->next_;
4612 673931 : b->next_->next_ = prev->next_;
4613 673931 : prev->next_ = next;
4614 : }
4615 : }
4616 : }
4617 0 : BOOST_CATCH(...)
4618 : {
4619 0 : node_pointer n = next_node(prev);
4620 0 : prev->next_ = node_pointer();
4621 0 : while (n) {
4622 0 : node_pointer next = next_node(n);
4623 0 : destroy_node(n);
4624 0 : --size_;
4625 0 : n = next;
4626 : }
4627 0 : BOOST_RETHROW
4628 : }
4629 : BOOST_CATCH_END
4630 7529 : }
4631 :
4632 : #if defined(BOOST_MSVC)
4633 : #pragma warning(pop)
4634 : #endif
4635 :
4636 : ////////////////////////////////////////////////////////////////////////
4637 : // key extractors
4638 : //
4639 : // no throw
4640 : //
4641 : // 'extract_key' is called with the emplace parameters to return a
4642 : // key if available or 'no_key' is one isn't and will need to be
4643 : // constructed. This could be done by overloading the emplace
4644 : // implementation
4645 : // for the different cases, but that's a bit tricky on compilers without
4646 : // variadic templates.
4647 :
4648 : template <typename Key, typename T> struct is_key
4649 : {
4650 : template <typename T2> static choice1::type test(T2 const&);
4651 : static choice2::type test(Key const&);
4652 :
4653 : enum
4654 : {
4655 : value = sizeof(test(boost::unordered::detail::make<T>())) ==
4656 : sizeof(choice2::type)
4657 : };
4658 :
4659 : typedef typename boost::detail::if_true<value>::BOOST_NESTED_TEMPLATE
4660 : then<Key const&, no_key>::type type;
4661 : };
4662 :
4663 : template <class ValueType> struct set_extractor
4664 : {
4665 : typedef ValueType value_type;
4666 : typedef ValueType key_type;
4667 :
4668 0 : static key_type const& extract(value_type const& v) { return v; }
4669 :
4670 0 : static key_type const& extract(BOOST_UNORDERED_RV_REF(value_type) v)
4671 : {
4672 : return v;
4673 : }
4674 :
4675 : static no_key extract() { return no_key(); }
4676 :
4677 : template <class Arg> static no_key extract(Arg const&)
4678 : {
4679 : return no_key();
4680 : }
4681 :
4682 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4683 : template <class Arg1, class Arg2, class... Args>
4684 : static no_key extract(Arg1 const&, Arg2 const&, Args const&...)
4685 : {
4686 : return no_key();
4687 : }
4688 : #else
4689 : template <class Arg1, class Arg2>
4690 : static no_key extract(Arg1 const&, Arg2 const&)
4691 : {
4692 : return no_key();
4693 : }
4694 : #endif
4695 : };
4696 :
4697 : template <class ValueType> struct map_extractor
4698 : {
4699 : typedef ValueType value_type;
4700 : typedef typename boost::remove_const<typename boost::unordered::detail::
4701 : pair_traits<ValueType>::first_type>::type key_type;
4702 :
4703 45660034 : static key_type const& extract(value_type const& v) { return v.first; }
4704 :
4705 : template <class Second>
4706 : static key_type const& extract(std::pair<key_type, Second> const& v)
4707 : {
4708 : return v.first;
4709 : }
4710 :
4711 : template <class Second>
4712 : static key_type const& extract(
4713 : std::pair<key_type const, Second> const& v)
4714 : {
4715 : return v.first;
4716 : }
4717 :
4718 : #if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
4719 : template <class Second>
4720 : static key_type const& extract(
4721 : boost::rv<std::pair<key_type, Second> > const& v)
4722 : {
4723 : return v.first;
4724 : }
4725 :
4726 : template <class Second>
4727 : static key_type const& extract(
4728 : boost::rv<std::pair<key_type const, Second> > const& v)
4729 : {
4730 : return v.first;
4731 : }
4732 : #endif
4733 :
4734 : template <class Arg1>
4735 : static key_type const& extract(key_type const& k, Arg1 const&)
4736 : {
4737 : return k;
4738 : }
4739 :
4740 : static no_key extract() { return no_key(); }
4741 :
4742 : template <class Arg> static no_key extract(Arg const&)
4743 : {
4744 : return no_key();
4745 : }
4746 :
4747 : template <class Arg1, class Arg2>
4748 : static no_key extract(Arg1 const&, Arg2 const&)
4749 : {
4750 : return no_key();
4751 : }
4752 :
4753 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4754 : template <class Arg1, class Arg2, class Arg3, class... Args>
4755 : static no_key extract(
4756 : Arg1 const&, Arg2 const&, Arg3 const&, Args const&...)
4757 : {
4758 : return no_key();
4759 : }
4760 : #endif
4761 :
4762 : #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
4763 :
4764 : #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
4765 : template <typename T2> \
4766 : static no_key extract(boost::unordered::piecewise_construct_t, \
4767 : namespace_ tuple<> const&, T2 const&) \
4768 : { \
4769 : return no_key(); \
4770 : } \
4771 : \
4772 : template <typename T, typename T2> \
4773 : static typename is_key<key_type, T>::type extract( \
4774 : boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k, \
4775 : T2 const&) \
4776 : { \
4777 : return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
4778 : }
4779 :
4780 : #else
4781 :
4782 : #define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
4783 : static no_key extract( \
4784 : boost::unordered::piecewise_construct_t, namespace_ tuple<> const&) \
4785 : { \
4786 : return no_key(); \
4787 : } \
4788 : \
4789 : template <typename T> \
4790 : static typename is_key<key_type, T>::type extract( \
4791 : boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k) \
4792 : { \
4793 : return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
4794 : }
4795 :
4796 : #endif
4797 :
4798 : BOOST_UNORDERED_KEY_FROM_TUPLE(boost::)
4799 :
4800 : #if BOOST_UNORDERED_TUPLE_ARGS
4801 : BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
4802 : #endif
4803 :
4804 : #undef BOOST_UNORDERED_KEY_FROM_TUPLE
4805 : };
4806 :
4807 : ////////////////////////////////////////////////////////////////////////
4808 : // Unique nodes
4809 :
4810 : template <typename A, typename T>
4811 : struct node : boost::unordered::detail::value_base<T>
4812 : {
4813 : typedef
4814 : typename ::boost::unordered::detail::rebind_wrap<A, node<A, T> >::type
4815 : allocator;
4816 : typedef typename ::boost::unordered::detail::allocator_traits<
4817 : allocator>::pointer node_pointer;
4818 : typedef node_pointer link_pointer;
4819 : typedef typename ::boost::unordered::detail::rebind_wrap<A,
4820 : bucket<node_pointer> >::type bucket_allocator;
4821 : typedef typename ::boost::unordered::detail::allocator_traits<
4822 : bucket_allocator>::pointer bucket_pointer;
4823 :
4824 : link_pointer next_;
4825 : std::size_t bucket_info_;
4826 :
4827 : node() : next_(), bucket_info_(0) {}
4828 :
4829 : std::size_t get_bucket() const
4830 : {
4831 : return bucket_info_ & ((std::size_t)-1 >> 1);
4832 : }
4833 :
4834 : std::size_t is_first_in_group() const
4835 : {
4836 : return !(bucket_info_ & ~((std::size_t)-1 >> 1));
4837 : }
4838 :
4839 : void set_first_in_group()
4840 : {
4841 : bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1);
4842 : }
4843 :
4844 : void reset_first_in_group()
4845 : {
4846 : bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1);
4847 : }
4848 :
4849 : private:
4850 : node& operator=(node const&);
4851 : };
4852 :
4853 : template <typename T>
4854 : struct ptr_node : boost::unordered::detail::ptr_bucket
4855 : {
4856 : typedef T value_type;
4857 : typedef boost::unordered::detail::ptr_bucket bucket_base;
4858 : typedef ptr_node<T>* node_pointer;
4859 : typedef ptr_bucket* link_pointer;
4860 : typedef ptr_bucket* bucket_pointer;
4861 :
4862 : std::size_t bucket_info_;
4863 : boost::unordered::detail::value_base<T> value_base_;
4864 :
4865 : ptr_node() : bucket_base(), bucket_info_(0) {}
4866 :
4867 : void* address() { return value_base_.address(); }
4868 69494651 : value_type& value() { return value_base_.value(); }
4869 57774138 : value_type* value_ptr() { return value_base_.value_ptr(); }
4870 :
4871 18544881 : std::size_t get_bucket() const
4872 : {
4873 18544881 : return bucket_info_ & ((std::size_t)-1 >> 1);
4874 : }
4875 :
4876 22855309 : std::size_t is_first_in_group() const
4877 : {
4878 22855309 : return !(bucket_info_ & ~((std::size_t)-1 >> 1));
4879 : }
4880 :
4881 5554732 : void set_first_in_group()
4882 : {
4883 2385360 : bucket_info_ = bucket_info_ & ((std::size_t)-1 >> 1);
4884 3169372 : }
4885 :
4886 104636 : void reset_first_in_group()
4887 : {
4888 63675 : bucket_info_ = bucket_info_ | ~((std::size_t)-1 >> 1);
4889 40961 : }
4890 :
4891 : private:
4892 : ptr_node& operator=(ptr_node const&);
4893 : };
4894 :
4895 : // If the allocator uses raw pointers use ptr_node
4896 : // Otherwise use node.
4897 :
4898 : template <typename A, typename T, typename NodePtr, typename BucketPtr>
4899 : struct pick_node2
4900 : {
4901 : typedef boost::unordered::detail::node<A, T> node;
4902 :
4903 : typedef typename boost::unordered::detail::allocator_traits<
4904 : typename boost::unordered::detail::rebind_wrap<A,
4905 : node>::type>::pointer node_pointer;
4906 :
4907 : typedef boost::unordered::detail::bucket<node_pointer> bucket;
4908 : typedef node_pointer link_pointer;
4909 : };
4910 :
4911 : template <typename A, typename T>
4912 : struct pick_node2<A, T, boost::unordered::detail::ptr_node<T>*,
4913 : boost::unordered::detail::ptr_bucket*>
4914 : {
4915 : typedef boost::unordered::detail::ptr_node<T> node;
4916 : typedef boost::unordered::detail::ptr_bucket bucket;
4917 : typedef bucket* link_pointer;
4918 : };
4919 :
4920 : template <typename A, typename T> struct pick_node
4921 : {
4922 : typedef typename boost::remove_const<T>::type nonconst;
4923 :
4924 : typedef boost::unordered::detail::allocator_traits<
4925 : typename boost::unordered::detail::rebind_wrap<A,
4926 : boost::unordered::detail::ptr_node<nonconst> >::type>
4927 : tentative_node_traits;
4928 :
4929 : typedef boost::unordered::detail::allocator_traits<
4930 : typename boost::unordered::detail::rebind_wrap<A,
4931 : boost::unordered::detail::ptr_bucket>::type>
4932 : tentative_bucket_traits;
4933 :
4934 : typedef pick_node2<A, nonconst, typename tentative_node_traits::pointer,
4935 : typename tentative_bucket_traits::pointer>
4936 : pick;
4937 :
4938 : typedef typename pick::node node;
4939 : typedef typename pick::bucket bucket;
4940 : typedef typename pick::link_pointer link_pointer;
4941 : };
4942 : }
4943 : }
4944 : }
4945 :
4946 : #undef BOOST_UNORDERED_EMPLACE_TEMPLATE
4947 : #undef BOOST_UNORDERED_EMPLACE_ARGS
4948 : #undef BOOST_UNORDERED_EMPLACE_FORWARD
4949 : #undef BOOST_UNORDERED_CALL_CONSTRUCT1
4950 : #undef BOOST_UNORDERED_CALL_DESTROY
4951 :
4952 : #endif
|
