implementation.hpp source code [include/boost/unordered/detail/implementation.hpp]

1	// Copyright (C) 2003-2004 Jeremy B. Maitin-Shepard.
2	// Copyright (C) 2005-2016 Daniel James
3	// Copyright (C) 2022 Joaquin M Lopez Munoz.
4	// Copyright (C) 2022 Christian Mazakas
5	//
6	// Distributed under the Boost Software License, Version 1.0. (See accompanying
7	// file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
8
9	#ifndef BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
10	#define BOOST_UNORDERED_DETAIL_IMPLEMENTATION_HPP
11
12	#include <boost/config.hpp>
13	#if defined(BOOST_HAS_PRAGMA_ONCE)
14	#pragma once
15	#endif
16
17	#include <boost/assert.hpp>
18	#include <boost/core/allocator_traits.hpp>
19	#include <boost/core/bit.hpp>
20	#include <boost/core/no_exceptions_support.hpp>
21	#include <boost/core/pointer_traits.hpp>
22	#include <boost/limits.hpp>
23	#include <boost/move/move.hpp>
24	#include <boost/preprocessor/arithmetic/inc.hpp>
25	#include <boost/preprocessor/cat.hpp>
26	#include <boost/preprocessor/repetition/enum.hpp>
27	#include <boost/preprocessor/repetition/enum_binary_params.hpp>
28	#include <boost/preprocessor/repetition/enum_params.hpp>
29	#include <boost/preprocessor/repetition/repeat_from_to.hpp>
30	#include <boost/preprocessor/seq/enum.hpp>
31	#include <boost/preprocessor/seq/size.hpp>
32	#include <boost/swap.hpp>
33	#include <boost/throw_exception.hpp>
34	#include <boost/tuple/tuple.hpp>
35	#include <boost/type_traits/add_lvalue_reference.hpp>
36	#include <boost/type_traits/aligned_storage.hpp>
37	#include <boost/type_traits/alignment_of.hpp>
38	#include <boost/type_traits/integral_constant.hpp>
39	#include <boost/type_traits/is_base_of.hpp>
40	#include <boost/type_traits/is_class.hpp>
41	#include <boost/type_traits/is_convertible.hpp>
42	#include <boost/type_traits/is_empty.hpp>
43	#include <boost/type_traits/is_nothrow_move_assignable.hpp>
44	#include <boost/type_traits/is_nothrow_move_constructible.hpp>
45	#include <boost/type_traits/is_nothrow_swappable.hpp>
46	#include <boost/type_traits/is_same.hpp>
47	#include <boost/type_traits/make_void.hpp>
48	#include <boost/type_traits/remove_const.hpp>
49	#include <boost/unordered/detail/fca.hpp>
50	#include <boost/unordered/detail/type_traits.hpp>
51	#include <boost/unordered/detail/fwd.hpp>
52	#include <boost/utility/addressof.hpp>
53	#include <boost/utility/enable_if.hpp>
54	#include <cmath>
55	#include <iterator>
56	#include <stdexcept>
57	#include <utility>
58
59	#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
60	#include <type_traits>
61	#endif
62
63	#if BOOST_UNORDERED_CXX11_CONSTRUCTION
64	#include <boost/mp11/list.hpp>
65	#include <boost/mp11/algorithm.hpp>
66	#endif
67
68	// BOOST_UNORDERED_SUPPRESS_DEPRECATED
69	//
70	// Define to stop deprecation attributes
71
72	#if defined(BOOST_UNORDERED_SUPPRESS_DEPRECATED)
73	#define BOOST_UNORDERED_DEPRECATED(msg)
74	#endif
75
76	// BOOST_UNORDERED_DEPRECATED
77	//
78	// Wrapper around various depreaction attributes.
79
80	#if defined(__has_cpp_attribute) && \
81	(!defined(__cplusplus) \|\| __cplusplus >= 201402)
82	#if __has_cpp_attribute(deprecated) && !defined(BOOST_UNORDERED_DEPRECATED)
83	#define BOOST_UNORDERED_DEPRECATED(msg) [[deprecated(msg)]]
84	#endif
85	#endif
86
87	#if !defined(BOOST_UNORDERED_DEPRECATED)
88	#if defined(__GNUC__) && __GNUC__ >= 4
89	#define BOOST_UNORDERED_DEPRECATED(msg) __attribute__((deprecated))
90	#elif defined(_MSC_VER) && _MSC_VER >= 1400
91	#define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated(msg))
92	#elif defined(_MSC_VER) && _MSC_VER >= 1310
93	#define BOOST_UNORDERED_DEPRECATED(msg) __declspec(deprecated)
94	#else
95	#define BOOST_UNORDERED_DEPRECATED(msg)
96	#endif
97	#endif
98
99	namespace boost {
100	namespace unordered {
101	namespace detail {
102
103	template <typename Types> struct table;
104
105	static const float minimum_max_load_factor = `1e-3f`;
106	static const std::size_t default_bucket_count = `0`;
107
108	struct move_tag
109	{
110	};
111
112	struct empty_emplace
113	{
114	};
115
116	struct no_key
117	{
118	no_key() {}
119	template <class T> no_key(T const&) {}
120	};
121
122	namespace func {
123	template <class T> inline void ignore_unused_variable_warning(T const&)
124	{
125	}
126	}
127
128	//////////////////////////////////////////////////////////////////////////
129	// iterator SFINAE
130
131	template <typename I>
132	struct is_forward : boost::is_base_of<std::forward_iterator_tag,
133	typename std::iterator_traits<I>::iterator_category>
134	{
135	};
136
137	template <typename I, typename ReturnType>
138	struct enable_if_forward
139	: boost::enable_if_c<boost::unordered::detail::is_forward<I>::value,
140	ReturnType>
141	{
142	};
143
144	template <typename I, typename ReturnType>
145	struct disable_if_forward
146	: boost::disable_if_c<boost::unordered::detail::is_forward<I>::value,
147	ReturnType>
148	{
149	};
150	}
151	}
152	}
153
154	namespace boost {
155	namespace unordered {
156	namespace detail {
157	//////////////////////////////////////////////////////////////////////////
158	// insert_size/initial_size
159
160	template <class I>
161	inline typename boost::unordered::detail::enable_if_forward<I,
162	std::size_t>::type
163	insert_size(I i, I j)
164	{
165	return static_cast<std::size_t>(std::distance(i, j));
166	}
167
168	template <class I>
169	inline typename boost::unordered::detail::disable_if_forward<I,
170	std::size_t>::type insert_size(I, I)
171	{
172	return `1`;
173	}
174
175	template <class I>
176	inline std::size_t initial_size(I i, I j,
177	std::size_t num_buckets =
178	boost::unordered::detail::default_bucket_count)
179	{
180	return (std::max)(
181	boost::unordered::detail::insert_size(i, j), num_buckets);
182	}
183
184	//////////////////////////////////////////////////////////////////////////
185	// compressed
186
187	template <typename T, int Index>
188	struct compressed_base : boost::empty_value<T>
189	{
190	compressed_base(T const& x) : empty_value<T>(boost::empty_init_t (), x)
191	{
192	}
193	compressed_base(T& x, move_tag)
194	: empty_value<T>(boost::empty_init_t (), boost::move(x))
195	{
196	}
197
198	T& get() { return empty_value<T>::get(); }
199	T const& get() const { return empty_value<T>::get(); }
200	};
201
202	template <typename T, int Index>
203	struct generate_base : boost::unordered::detail::compressed_base<T, Index>
204	{
205	typedef compressed_base<T, Index> type;
206
207	generate_base() : type() {}
208	};
209
210	template <typename T1, typename T2>
211	struct compressed
212	: private boost::unordered::detail::generate_base<T1, `1`>::type,
213	private boost::unordered::detail::generate_base<T2, `2`>::type
214	{
215	typedef typename generate_base<T1, `1`>::type base1;
216	typedef typename generate_base<T2, `2`>::type base2;
217
218	typedef T1 first_type;
219	typedef T2 second_type;
220
221	first_type& first() { return static_cast<base1>(this*)->get(); }
222
223	first_type const& first() const
224	{
225	return static_cast<base1 const>(this*)->get();
226	}
227
228	second_type& second() { return static_cast<base2>(this*)->get(); }
229
230	second_type const& second() const
231	{
232	return static_cast<base2 const>(this*)->get();
233	}
234
235	template <typename First, typename Second>
236	compressed(First const& x1, Second const& x2) : base1(x1), base2(x2)
237	{
238	}
239
240	compressed(compressed const& x) : base1(x.first()), base2(x.second()) {}
241
242	compressed(compressed& x, move_tag m)
243	: base1(x.first(), m), base2(x.second(), m)
244	{
245	}
246
247	void assign(compressed const& x)
248	{
249	first() = x.first();
250	second() = x.second();
251	}
252
253	void move_assign(compressed& x)
254	{
255	first() = boost::move(x.first());
256	second() = boost::move(x.second());
257	}
258
259	void swap(compressed& x)
260	{
261	boost::swap(first(), x.first());
262	boost::swap(second(), x.second());
263	}
264
265	private:
266	// Prevent assignment just to make use of assign or
267	// move_assign explicit.
268	compressed& operator=(compressed const&);
269	};
270
271	//////////////////////////////////////////////////////////////////////////
272	// pair_traits
273	//
274	// Used to get the types from a pair without instantiating it.
275
276	template <typename Pair> struct pair_traits
277	{
278	typedef typename Pair::first_type first_type;
279	typedef typename Pair::second_type second_type;
280	};
281
282	template <typename T1, typename T2> struct pair_traits<std::pair<T1, T2> >
283	{
284	typedef T1 first_type;
285	typedef T2 second_type;
286	};
287
288	#if defined(BOOST_MSVC)
289	#pragma warning(push)
290	#pragma warning(disable : 4512) // assignment operator could not be generated.
291	#pragma warning(disable : 4345) // behavior change: an object of POD type
292	// constructed with an initializer of the form ()
293	// will be default-initialized.
294	#endif
295
296	//////////////////////////////////////////////////////////////////////////
297	// Bits and pieces for implementing traits
298
299	template <typename T>
300	typename boost::add_lvalue_reference<T>::type make();
301	struct choice9
302	{
303	typedef char (&type)[`9`];
304	};
305	struct choice8 : choice9
306	{
307	typedef char (&type)[`8`];
308	};
309	struct choice7 : choice8
310	{
311	typedef char (&type)[`7`];
312	};
313	struct choice6 : choice7
314	{
315	typedef char (&type)[`6`];
316	};
317	struct choice5 : choice6
318	{
319	typedef char (&type)[`5`];
320	};
321	struct choice4 : choice5
322	{
323	typedef char (&type)[`4`];
324	};
325	struct choice3 : choice4
326	{
327	typedef char (&type)[`3`];
328	};
329	struct choice2 : choice3
330	{
331	typedef char (&type)[`2`];
332	};
333	struct choice1 : choice2
334	{
335	typedef char (&type)[`1`];
336	};
337	choice1 choose();
338
339	typedef choice1::type yes_type;
340	typedef choice2::type no_type;
341
342	struct private_type
343	{
344	private_type const& operator,(int) const;
345	};
346
347	template <typename T> no_type is_private_type(T const&);
348	yes_type is_private_type(private_type const&);
349
350	struct convert_from_anything
351	{
352	template <typename T> convert_from_anything(T const&);
353	};
354	}
355	}
356	}
357
358	////////////////////////////////////////////////////////////////////////////
359	// emplace_args
360	//
361	// Either forwarding variadic arguments, or storing the arguments in
362	// emplace_args##n
363
364	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
365
366	#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename... Args
367	#define BOOST_UNORDERED_EMPLACE_ARGS BOOST_FWD_REF(Args)... args
368	#define BOOST_UNORDERED_EMPLACE_FORWARD boost::forward<Args>(args)...
369
370	#else
371
372	#define BOOST_UNORDERED_EMPLACE_TEMPLATE typename Args
373	#define BOOST_UNORDERED_EMPLACE_ARGS Args const& args
374	#define BOOST_UNORDERED_EMPLACE_FORWARD args
375
376	#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
377
378	#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
379	typedef BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(Arg, n); \
380	BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
381
382	#else
383
384	#define BOOST_UNORDERED_EARGS_MEMBER(z, n, _) \
385	typedef typename boost::add_lvalue_reference<BOOST_PP_CAT(A, n)>::type \
386	BOOST_PP_CAT(Arg, n); \
387	BOOST_PP_CAT(Arg, n) BOOST_PP_CAT(a, n);
388
389	#endif
390
391	#define BOOST_UNORDERED_FWD_PARAM(z, n, a) \
392	BOOST_FWD_REF(BOOST_PP_CAT(A, n)) BOOST_PP_CAT(a, n)
393
394	#define BOOST_UNORDERED_CALL_FORWARD(z, i, a) \
395	boost::forward<BOOST_PP_CAT(A, i)>(BOOST_PP_CAT(a, i))
396
397	#define BOOST_UNORDERED_EARGS_INIT(z, n, _) \
398	BOOST_PP_CAT(a, n)(BOOST_PP_CAT(b, n))
399
400	#define BOOST_UNORDERED_EARGS(z, n, _) \
401	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
402	struct BOOST_PP_CAT(emplace_args, n) \
403	{ \
404	BOOST_PP_REPEAT_##z(n, BOOST_UNORDERED_EARGS_MEMBER, _) BOOST_PP_CAT( \
405	emplace_args, n)(BOOST_PP_ENUM_BINARY_PARAMS_Z(z, n, Arg, b)) \
406	: BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_EARGS_INIT, _) \
407	{ \
408	} \
409	}; \
410	\
411	template <BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
412	inline BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> \
413	create_emplace_args(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_FWD_PARAM, b)) \
414	{ \
415	BOOST_PP_CAT(emplace_args, n)<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> e( \
416	BOOST_PP_ENUM_PARAMS_Z(z, n, b)); \
417	return e; \
418	}
419
420	namespace boost {
421	namespace unordered {
422	namespace detail {
423	template <typename A0> struct emplace_args1
424	{
425	BOOST_UNORDERED_EARGS_MEMBER(`1`, `0`, _)
426
427	explicit emplace_args1(Arg0 b0) : a0(b0) {}
428	};
429
430	template <typename A0>
431	inline emplace_args1<A0> create_emplace_args(BOOST_FWD_REF(A0) b0)
432	{
433	emplace_args1<A0> e(b0);
434	return e;
435	}
436
437	template <typename A0, typename A1> struct emplace_args2
438	{
439	BOOST_UNORDERED_EARGS_MEMBER(`1`, `0`, _)
440	BOOST_UNORDERED_EARGS_MEMBER(`1`, `1`, _)
441
442	emplace_args2(Arg0 b0, Arg1 b1) : a0(b0), a1(b1) {}
443	};
444
445	template <typename A0, typename A1>
446	inline emplace_args2<A0, A1> create_emplace_args(
447	BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1)
448	{
449	emplace_args2<A0, A1> e(b0, b1);
450	return e;
451	}
452
453	template <typename A0, typename A1, typename A2> struct emplace_args3
454	{
455	BOOST_UNORDERED_EARGS_MEMBER(`1`, `0`, _)
456	BOOST_UNORDERED_EARGS_MEMBER(`1`, `1`, _)
457	BOOST_UNORDERED_EARGS_MEMBER(`1`, `2`, _)
458
459	emplace_args3(Arg0 b0, Arg1 b1, Arg2 b2) : a0(b0), a1(b1), a2(b2) {}
460	};
461
462	template <typename A0, typename A1, typename A2>
463	inline emplace_args3<A0, A1, A2> create_emplace_args(
464	BOOST_FWD_REF(A0) b0, BOOST_FWD_REF(A1) b1, BOOST_FWD_REF(A2) b2)
465	{
466	emplace_args3<A0, A1, A2> e(b0, b1, b2);
467	return e;
468	}
469
470	BOOST_UNORDERED_EARGS(`1`, `4`, _)
471	BOOST_UNORDERED_EARGS(`1`, `5`, _)
472	BOOST_UNORDERED_EARGS(`1`, `6`, _)
473	BOOST_UNORDERED_EARGS(`1`, `7`, _)
474	BOOST_UNORDERED_EARGS(`1`, `8`, _)
475	BOOST_UNORDERED_EARGS(`1`, `9`, _)
476	BOOST_PP_REPEAT_FROM_TO(`10`, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
477	BOOST_UNORDERED_EARGS, _)
478	}
479	}
480	}
481
482	#undef BOOST_UNORDERED_DEFINE_EMPLACE_ARGS
483	#undef BOOST_UNORDERED_EARGS_MEMBER
484	#undef BOOST_UNORDERED_EARGS_INIT
485
486	#endif
487
488	////////////////////////////////////////////////////////////////////////////////
489	//
490	// Some utilities for implementing allocator_traits, but useful elsewhere so
491	// they're always defined.
492
493	namespace boost {
494	namespace unordered {
495	namespace detail {
496
497	////////////////////////////////////////////////////////////////////////////
498	// Integral_constrant, true_type, false_type
499	//
500	// Uses the standard versions if available.
501
502	#if !defined(BOOST_NO_CXX11_HDR_TYPE_TRAITS)
503
504	using std::integral_constant;
505	using std::true_type;
506	using std::false_type;
507
508	#else
509
510	template <typename T, T Value> struct integral_constant
511	{
512	enum
513	{
514	value = Value
515	};
516	};
517
518	typedef boost::unordered::detail::integral_constant<bool, true> true_type;
519	typedef boost::unordered::detail::integral_constant<bool, false>
520	false_type;
521
522	#endif
523
524	////////////////////////////////////////////////////////////////////////////
525	// Explicitly call a destructor
526
527	#if defined(BOOST_MSVC)
528	#pragma warning(push)
529	#pragma warning(disable : 4100) // unreferenced formal parameter
530	#endif
531
532	namespace func {
533	template <class T> inline void destroy(T* x) { x->~T(); }
534	}
535
536	#if defined(BOOST_MSVC)
537	#pragma warning(pop)
538	#endif
539
540	//////////////////////////////////////////////////////////////////////////
541	// value_base
542	//
543	// Space used to store values.
544
545	template <typename ValueType> struct value_base
546	{
547	typedef ValueType value_type;
548
549	typename boost::aligned_storage<sizeof(value_type),
550	boost::alignment_of<value_type>::value>::type data_;
551
552	value_base() : data_() {}
553
554	void* address() { return this; }
555
556	value_type& value() { return (ValueType)this; }
557
558	value_type const& value() const { return (ValueType const)this**; }
559
560	value_type* value_ptr() { return (ValueType)this*; }
561
562	value_type const* value_ptr() const { return (ValueType const)this*; }
563
564	private:
565	value_base& operator=(value_base const&);
566	};
567
568	//////////////////////////////////////////////////////////////////////////
569	// optional
570	// TODO: Use std::optional when available.
571
572	template <typename T> class optional
573	{
574	BOOST_MOVABLE_BUT_NOT_COPYABLE(optional)
575
576	boost::unordered::detail::value_base<T> value_;
577	bool has_value_;
578
579	void destroy()
580	{
581	if (has_value_) {
582	boost::unordered::detail::func::destroy(value_.value_ptr());
583	has_value_ = false;
584	}
585	}
586
587	void move(optional<T>& x)
588	{
589	BOOST_ASSERT(!has_value_ && x.has_value_);
590	new (value_.value_ptr()) T(boost::move(x.value_.value()));
591	boost::unordered::detail::func::destroy(x.value_.value_ptr());
592	has_value_ = true;
593	x.has_value_ = false;
594	}
595
596	public:
597	optional() BOOST_NOEXCEPT : has_value_(false) {}
598
599	optional(BOOST_RV_REF(optional<T>) x) : has_value_(false)
600	{
601	if (x.has_value_) {
602	move(x);
603	}
604	}
605
606	explicit optional(T const& x) : has_value_(true)
607	{
608	new (value_.value_ptr()) T(x);
609	}
610
611	optional& operator=(BOOST_RV_REF(optional<T>) x)
612	{
613	destroy();
614	if (x.has_value_) {
615	move(x);
616	}
617	return *this;
618	}
619
620	~optional() { destroy(); }
621
622	bool has_value() const { return has_value_; }
623	T& operator() { return* value_.value(); }
624	T const& operator() const* { return value_.value(); }
625	T* operator->() { return value_.value_ptr(); }
626	T const* operator->() const { return value_.value_ptr(); }
627
628	bool operator==(optional<T> const& x) const
629	{
630	return has_value_ ? x.has_value_ && value_.value() == x.value_.value()
631	: !x.has_value_;
632	}
633
634	bool operator!=(optional<T> const& x) const { return !((*this) == x); }
635
636	void swap(optional<T>& x)
637	{
638	if (has_value_ != x.has_value_) {
639	if (has_value_) {
640	x.move(*this);
641	} else {
642	move(x);
643	}
644	} else if (has_value_) {
645	boost::swap(value_.value(), x.value_.value());
646	}
647	}
648
649	friend void swap(optional<T>& x, optional<T>& y) { x.swap(y); }
650	};
651	}
652	}
653	}
654
655	////////////////////////////////////////////////////////////////////////////////
656	//
657	// Allocator traits
658	//
659
660	namespace boost {
661	namespace unordered {
662	namespace detail {
663
664	template <typename Alloc>
665	struct allocator_traits : boost::allocator_traits<Alloc>
666	{
667	};
668
669	template <typename Alloc, typename T>
670	struct rebind_wrap : boost::allocator_rebind<Alloc, T>
671	{
672	};
673	}
674	}
675	}
676
677	////////////////////////////////////////////////////////////////////////////
678	// Functions used to construct nodes. Emulates variadic construction,
679	// piecewise construction etc.
680
681	////////////////////////////////////////////////////////////////////////////
682	// construct_value
683	//
684	// Only use allocator_traits::construct, allocator_traits::destroy when full
685	// C++11 support is available.
686
687	#if BOOST_UNORDERED_CXX11_CONSTRUCTION
688
689	#elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
690
691	namespace boost {
692	namespace unordered {
693	namespace detail {
694	namespace func {
695	template <typename T, typename... Args>
696	inline void construct_value(T* address, BOOST_FWD_REF(Args)... args)
697	{
698	new ((void*)address) T(boost::forward<Args>(args)...);
699	}
700	}
701	}
702	}
703	}
704
705	#else
706
707	namespace boost {
708	namespace unordered {
709	namespace detail {
710	namespace func {
711	template <typename T> inline void construct_value(T* address)
712	{
713	new ((void*)address) T();
714	}
715
716	template <typename T, typename A0>
717	inline void construct_value(T* address, BOOST_FWD_REF(A0) a0)
718	{
719	new ((void*)address) T(boost::forward<A0>(a0));
720	}
721	}
722	}
723	}
724	}
725
726	#endif
727
728	////////////////////////////////////////////////////////////////////////////
729	// Construct from tuple
730	//
731	// Used to emulate piecewise construction.
732
733	#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
734	template <typename Alloc, typename T, \
735	BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
736	void construct_from_tuple(Alloc&, T* ptr, \
737	namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
738	{ \
739	new ((void*)ptr) \
740	T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
741	}
742
743	#define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
744
745	// construct_from_tuple for boost::tuple
746	// The workaround for old Sun compilers comes later in the file.
747
748	#if !BOOST_UNORDERED_SUN_WORKAROUNDS1
749
750	namespace boost {
751	namespace unordered {
752	namespace detail {
753	namespace func {
754	template <typename Alloc, typename T>
755	void construct_from_tuple(Alloc&, T* ptr, boost::tuple<>)
756	{
757	new ((void*)ptr) T();
758	}
759
760	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `1`, boost)
761	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `2`, boost)
762	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `3`, boost)
763	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `4`, boost)
764	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `5`, boost)
765	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `6`, boost)
766	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `7`, boost)
767	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `8`, boost)
768	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `9`, boost)
769	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `10`, boost)
770	}
771	}
772	}
773	}
774
775	#endif
776
777	// construct_from_tuple for std::tuple
778
779	#if !BOOST_UNORDERED_CXX11_CONSTRUCTION && BOOST_UNORDERED_TUPLE_ARGS
780
781	namespace boost {
782	namespace unordered {
783	namespace detail {
784	namespace func {
785	template <typename Alloc, typename T>
786	void construct_from_tuple(Alloc&, T* ptr, std::tuple<>)
787	{
788	new ((void*)ptr) T();
789	}
790
791	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `1`, std)
792	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `2`, std)
793	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `3`, std)
794	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `4`, std)
795	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `5`, std)
796
797	#if BOOST_UNORDERED_TUPLE_ARGS >= 6
798	BOOST_PP_REPEAT_FROM_TO(`6`, BOOST_PP_INC(BOOST_UNORDERED_TUPLE_ARGS),
799	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE, std)
800	#endif
801	}
802	}
803	}
804	}
805
806	#endif
807
808	#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
809	#undef BOOST_UNORDERED_GET_TUPLE_ARG
810
811	// construct_from_tuple for boost::tuple on old versions of sunpro.
812	//
813	// Old versions of Sun C++ had problems with template overloads of
814	// boost::tuple, so to fix it I added a distinct type for each length to
815	// the overloads. That means there's no possible ambiguity between the
816	// different overloads, so that the compiler doesn't get confused
817
818	#if BOOST_UNORDERED_SUN_WORKAROUNDS1
819
820	#define BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(z, n, namespace_) \
821	template <typename Alloc, typename T, \
822	BOOST_PP_ENUM_PARAMS_Z(z, n, typename A)> \
823	void construct_from_tuple_impl(boost::unordered::detail::func::length<n>, \
824	Alloc&, T* ptr, \
825	namespace_::tuple<BOOST_PP_ENUM_PARAMS_Z(z, n, A)> const& x) \
826	{ \
827	new ((void*)ptr) \
828	T(BOOST_PP_ENUM_##z(n, BOOST_UNORDERED_GET_TUPLE_ARG, namespace_)); \
829	}
830
831	#define BOOST_UNORDERED_GET_TUPLE_ARG(z, n, namespace_) namespace_::get<n>(x)
832
833	namespace boost {
834	namespace unordered {
835	namespace detail {
836	namespace func {
837	template <int N> struct length
838	{
839	};
840
841	template <typename Alloc, typename T>
842	void construct_from_tuple_impl(
843	boost::unordered::detail::func::length<`0`>, Alloc&, T* ptr,
844	boost::tuple<>)
845	{
846	new ((void*)ptr) T();
847	}
848
849	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `1`, boost)
850	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `2`, boost)
851	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `3`, boost)
852	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `4`, boost)
853	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `5`, boost)
854	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `6`, boost)
855	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `7`, boost)
856	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `8`, boost)
857	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `9`, boost)
858	BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE(`1`, `10`, boost)
859
860	template <typename Alloc, typename T, typename Tuple>
861	void construct_from_tuple(Alloc& alloc, T* ptr, Tuple const& x)
862	{
863	construct_from_tuple_impl(boost::unordered::detail::func::length<
864	boost::tuples::length<Tuple>::value>(),
865	alloc, ptr, x);
866	}
867	}
868	}
869	}
870	}
871
872	#undef BOOST_UNORDERED_CONSTRUCT_FROM_TUPLE
873	#undef BOOST_UNORDERED_GET_TUPLE_ARG
874
875	#endif
876
877	namespace boost {
878	namespace unordered {
879	namespace detail {
880	namespace func {
881	////////////////////////////////////////////////////////////////////////
882	// Trait to check for piecewise construction.
883
884	template <typename A0> struct use_piecewise
885	{
886	static choice1::type test(
887	choice1, boost::unordered::piecewise_construct_t);
888
889	static choice2::type test(choice2, ...);
890
891	enum
892	{
893	value = sizeof(choice1::type) ==
894	sizeof(test(choose(), boost::unordered::detail::make<A0>()))
895	};
896	};
897
898	#if BOOST_UNORDERED_CXX11_CONSTRUCTION
899
900	////////////////////////////////////////////////////////////////////////
901	// Construct from variadic parameters
902
903	template <typename Alloc, typename T, typename... Args>
904	inline void construct_from_args(
905	Alloc& alloc, T* address, BOOST_FWD_REF(Args)... args)
906	{
907	boost::allocator_construct(
908	alloc, address, boost::forward<Args>(args)...);
909	}
910
911	// For backwards compatibility, implement a special case for
912	// piecewise_construct with boost::tuple
913
914	template <typename A0> struct detect_boost_tuple
915	{
916	template <typename T0, typename T1, typename T2, typename T3,
917	typename T4, typename T5, typename T6, typename T7, typename T8,
918	typename T9>
919	static choice1::type test(choice1,
920	boost::tuple<T0, T1, T2, T3, T4, T5, T6, T7, T8, T9> const&);
921
922	static choice2::type test(choice2, ...);
923
924	enum
925	{
926	value = sizeof(choice1::type) ==
927	sizeof(test(choose(), boost::unordered::detail::make<A0>()))
928	};
929	};
930
931	// Special case for piecewise_construct
932
933	template <class... Args, std::size_t... Is, class... TupleArgs>
934	std::tuple<typename std::add_lvalue_reference<Args>::type...>
935	to_std_tuple_impl(boost::mp11::mp_list<Args...>,
936	boost::tuple<TupleArgs...>& tuple, boost::mp11::index_sequence<Is...>)
937	{
938	(void) tuple;
939	return std::tuple<typename std::add_lvalue_reference<Args>::type...>(
940	boost::get<Is>(tuple)...);
941	}
942
943	template <class T>
944	using add_lvalue_reference_t =
945	typename std::add_lvalue_reference<T>::type;
946
947	template <class... Args>
948	boost::mp11::mp_transform<add_lvalue_reference_t,
949	boost::mp11::mp_remove<std::tuple<Args...>,
950	boost::tuples::null_type> >
951	to_std_tuple(boost::tuple<Args...>& tuple)
952	{
953	using list = boost::mp11::mp_remove<boost::mp11::mp_list<Args...>,
954	boost::tuples::null_type>;
955	using list_size = boost::mp11::mp_size<list>;
956	using index_seq = boost::mp11::make_index_sequence<list_size::value>;
957
958	return to_std_tuple_impl(list{}, tuple, index_seq{});
959	}
960
961	template <typename Alloc, typename A, typename B, typename A0,
962	typename A1, typename A2>
963	inline typename boost::enable_if_c<use_piecewise<A0>::value &&
964	detect_boost_tuple<A1>::value &&
965	detect_boost_tuple<A2>::value,
966	void>::type
967	construct_from_args(Alloc& alloc, std::pair<A, B>* address,
968	BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
969	{
970	boost::allocator_construct(alloc, address, std::piecewise_construct,
971	to_std_tuple(a1), to_std_tuple(a2));
972	}
973
974	#elif !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
975
976	////////////////////////////////////////////////////////////////////////
977	// Construct from variadic parameters
978
979	template <typename Alloc, typename T, typename... Args>
980	inline void construct_from_args(
981	Alloc&, T* address, BOOST_FWD_REF(Args)... args)
982	{
983	new ((void*)address) T(boost::forward<Args>(args)...);
984	}
985
986	// Special case for piecewise_construct
987
988	template <typename Alloc, typename A, typename B, typename A0,
989	typename A1, typename A2>
990	inline typename enable_if<use_piecewise<A0>, void>::type
991	construct_from_args(Alloc& alloc, std::pair<A, B>* address,
992	BOOST_FWD_REF(A0), BOOST_FWD_REF(A1) a1, BOOST_FWD_REF(A2) a2)
993	{
994	boost::unordered::detail::func::construct_from_tuple(
995	alloc, boost::addressof(address->first), boost::forward<A1>(a1));
996	BOOST_TRY
997	{
998	boost::unordered::detail::func::construct_from_tuple(
999	alloc, boost::addressof(address->second), boost::forward<A2>(a2));
1000	}
1001	BOOST_CATCH(...)
1002	{
1003	boost::unordered::detail::func::destroy(
1004	boost::addressof(address->first));
1005	BOOST_RETHROW
1006	}
1007	BOOST_CATCH_END
1008	}
1009
1010	#else // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1011
1012	////////////////////////////////////////////////////////////////////////
1013	// Construct from emplace_args
1014
1015	// Explicitly write out first three overloads for the sake of sane
1016	// error messages.
1017
1018	template <typename Alloc, typename T, typename A0>
1019	inline void construct_from_args(
1020	Alloc&, T* address, emplace_args1<A0> const& args)
1021	{
1022	new ((void*)address) T(boost::forward<A0>(args.a0));
1023	}
1024
1025	template <typename Alloc, typename T, typename A0, typename A1>
1026	inline void construct_from_args(
1027	Alloc&, T* address, emplace_args2<A0, A1> const& args)
1028	{
1029	new ((void*)address)
1030	T(boost::forward<A0>(args.a0), boost::forward<A1>(args.a1));
1031	}
1032
1033	template <typename Alloc, typename T, typename A0, typename A1,
1034	typename A2>
1035	inline void construct_from_args(
1036	Alloc&, T* address, emplace_args3<A0, A1, A2> const& args)
1037	{
1038	new ((void*)address) T(boost::forward<A0>(args.a0),
1039	boost::forward<A1>(args.a1), boost::forward<A2>(args.a2));
1040	}
1041
1042	// Use a macro for the rest.
1043
1044	#define BOOST_UNORDERED_CONSTRUCT_IMPL(z, num_params, _) \
1045	template <typename Alloc, typename T, \
1046	BOOST_PP_ENUM_PARAMS_Z(z, num_params, typename A)> \
1047	inline void construct_from_args(Alloc&, T* address, \
1048	boost::unordered::detail::BOOST_PP_CAT(emplace_args, num_params) < \
1049	BOOST_PP_ENUM_PARAMS_Z(z, num_params, A) > const& args) \
1050	{ \
1051	new ((void*)address) \
1052	T(BOOST_PP_ENUM_##z(num_params, BOOST_UNORDERED_CALL_FORWARD, args.a)); \
1053	}
1054
1055	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `4`, _)
1056	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `5`, _)
1057	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `6`, _)
1058	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `7`, _)
1059	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `8`, _)
1060	BOOST_UNORDERED_CONSTRUCT_IMPL(`1`, `9`, _)
1061	BOOST_PP_REPEAT_FROM_TO(`10`, BOOST_PP_INC(BOOST_UNORDERED_EMPLACE_LIMIT),
1062	BOOST_UNORDERED_CONSTRUCT_IMPL, _)
1063
1064	#undef BOOST_UNORDERED_CONSTRUCT_IMPL
1065
1066	// Construct with piecewise_construct
1067
1068	template <typename Alloc, typename A, typename B, typename A0,
1069	typename A1, typename A2>
1070	inline typename enable_if<use_piecewise<A0>, void>::type
1071	construct_from_args(Alloc& alloc, std::pair<A, B>* address,
1072	boost::unordered::detail::emplace_args3<A0, A1, A2> const& args)
1073	{
1074	boost::unordered::detail::func::construct_from_tuple(
1075	alloc, boost::addressof(address->first), args.a1);
1076	BOOST_TRY
1077	{
1078	boost::unordered::detail::func::construct_from_tuple(
1079	alloc, boost::addressof(address->second), args.a2);
1080	}
1081	BOOST_CATCH(...)
1082	{
1083	boost::unordered::detail::func::destroy(
1084	boost::addressof(address->first));
1085	BOOST_RETHROW
1086	}
1087	BOOST_CATCH_END
1088	}
1089
1090	#endif // BOOST_NO_CXX11_VARIADIC_TEMPLATES
1091	}
1092	}
1093	}
1094	}
1095
1096	namespace boost {
1097	namespace unordered {
1098	namespace detail {
1099
1100	///////////////////////////////////////////////////////////////////
1101	//
1102	// Node construction
1103
1104	template <typename NodeAlloc> struct node_constructor
1105	{
1106	typedef NodeAlloc node_allocator;
1107	typedef boost::unordered::detail::allocator_traits<NodeAlloc>
1108	node_allocator_traits;
1109	typedef typename node_allocator_traits::value_type node;
1110	typedef typename node_allocator_traits::pointer node_pointer;
1111	typedef typename node::value_type value_type;
1112
1113	node_allocator& alloc_;
1114	node_pointer node_;
1115
1116	node_constructor(node_allocator& n) : alloc_(n), node_() {}
1117
1118	~node_constructor();
1119
1120	void create_node();
1121
1122	// no throw
1123	node_pointer release()
1124	{
1125	BOOST_ASSERT(node_);
1126	node_pointer p = node_;
1127	node_ = node_pointer();
1128	return p;
1129	}
1130
1131	private:
1132	node_constructor(node_constructor const&);
1133	node_constructor& operator=(node_constructor const&);
1134	};
1135
1136	template <typename Alloc> node_constructor<Alloc>::~node_constructor()
1137	{
1138	if (node_) {
1139	boost::unordered::detail::func::destroy(boost::to_address(node_));
1140	node_allocator_traits::deallocate(alloc_, node_, `1`);
1141	}
1142	}
1143
1144	template <typename Alloc> void node_constructor<Alloc>::create_node()
1145	{
1146	BOOST_ASSERT(!node_);
1147	node_ = node_allocator_traits::allocate(alloc_, `1`);
1148	new ((void*)boost::to_address(node_)) node();
1149	}
1150
1151	template <typename NodeAlloc> struct node_tmp
1152	{
1153	typedef typename boost::allocator_value_type<NodeAlloc>::type node;
1154	typedef typename boost::allocator_pointer<NodeAlloc>::type node_pointer;
1155	typedef typename node::value_type value_type;
1156	typedef typename boost::allocator_rebind<NodeAlloc, value_type>::type
1157	value_allocator;
1158
1159	NodeAlloc& alloc_;
1160	node_pointer node_;
1161
1162	explicit node_tmp(node_pointer n, NodeAlloc& a) : alloc_(a), node_(n) {}
1163
1164	~node_tmp();
1165
1166	// no throw
1167	node_pointer release()
1168	{
1169	node_pointer p = node_;
1170	node_ = node_pointer();
1171	return p;
1172	}
1173	};
1174
1175	template <typename Alloc> node_tmp<Alloc>::~node_tmp()
1176	{
1177	if (node_) {
1178	value_allocator val_alloc(alloc_);
1179	boost::allocator_destroy(val_alloc, node_->value_ptr());
1180	boost::allocator_deallocate(alloc_, node_, `1`);
1181	}
1182	}
1183	}
1184	}
1185	}
1186
1187	namespace boost {
1188	namespace unordered {
1189	namespace detail {
1190	namespace func {
1191
1192	// Some nicer construct_node functions, might try to
1193	// improve implementation later.
1194
1195	template <typename Alloc, BOOST_UNORDERED_EMPLACE_TEMPLATE>
1196	inline typename boost::allocator_pointer<Alloc>::type
1197	construct_node_from_args(Alloc& alloc, BOOST_UNORDERED_EMPLACE_ARGS)
1198	{
1199	typedef typename boost::allocator_value_type<Alloc>::type node;
1200	typedef typename node::value_type value_type;
1201	typedef typename boost::allocator_rebind<Alloc, value_type>::type
1202	value_allocator;
1203
1204	value_allocator val_alloc(alloc);
1205
1206	node_constructor<Alloc> a(alloc);
1207	a.create_node();
1208	construct_from_args(
1209	val_alloc, a.node_->value_ptr(), BOOST_UNORDERED_EMPLACE_FORWARD);
1210	return a.release();
1211	}
1212
1213	template <typename Alloc, typename U>
1214	inline typename boost::allocator_pointer<Alloc>::type construct_node(
1215	Alloc& alloc, BOOST_FWD_REF(U) x)
1216	{
1217	node_constructor<Alloc> a(alloc);
1218	a.create_node();
1219
1220	typedef typename boost::allocator_value_type<Alloc>::type node;
1221	typedef typename node::value_type value_type;
1222	typedef typename boost::allocator_rebind<Alloc, value_type>::type
1223	value_allocator;
1224
1225	value_allocator val_alloc(alloc);
1226
1227	boost::allocator_construct(
1228	val_alloc, a.node_->value_ptr(), boost::forward<U>(x));
1229	return a.release();
1230	}
1231
1232	#if BOOST_UNORDERED_CXX11_CONSTRUCTION
1233
1234	template <typename Alloc, typename Key>
1235	inline typename boost::allocator_pointer<Alloc>::type
1236	construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
1237	{
1238	node_constructor<Alloc> a(alloc);
1239	a.create_node();
1240
1241	typedef typename boost::allocator_value_type<Alloc>::type node;
1242	typedef typename node::value_type value_type;
1243	typedef typename boost::allocator_rebind<Alloc, value_type>::type
1244	value_allocator;
1245
1246	value_allocator val_alloc(alloc);
1247
1248	boost::allocator_construct(
1249	val_alloc, a.node_->value_ptr(), std::piecewise_construct,
1250	std::forward_as_tuple(boost::forward<Key>(k)),
1251	std::forward_as_tuple());
1252	return a.release();
1253	}
1254
1255	template <typename Alloc, typename Key, typename Mapped>
1256	inline typename boost::allocator_pointer<Alloc>::type
1257	construct_node_pair(
1258	Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
1259	{
1260	node_constructor<Alloc> a(alloc);
1261	a.create_node();
1262
1263	typedef typename boost::allocator_value_type<Alloc>::type node;
1264	typedef typename node::value_type value_type;
1265	typedef typename boost::allocator_rebind<Alloc, value_type>::type
1266	value_allocator;
1267
1268	value_allocator val_alloc(alloc);
1269
1270	boost::allocator_construct(val_alloc, a.node_->value_ptr(),
1271	std::piecewise_construct,
1272	std::forward_as_tuple(boost::forward<Key>(k)),
1273	std::forward_as_tuple(boost::forward<Mapped>(m)));
1274	return a.release();
1275	}
1276
1277	template <typename Alloc, typename Key, typename... Args>
1278	inline typename boost::allocator_pointer<Alloc>::type
1279	construct_node_pair_from_args(
1280	Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Args)... args)
1281	{
1282	node_constructor<Alloc> a(alloc);
1283	a.create_node();
1284
1285	typedef typename boost::allocator_value_type<Alloc>::type node;
1286	typedef typename node::value_type value_type;
1287	typedef typename boost::allocator_rebind<Alloc, value_type>::type
1288	value_allocator;
1289
1290	value_allocator val_alloc(alloc);
1291
1292	#if !(BOOST_COMP_CLANG && BOOST_COMP_CLANG < BOOST_VERSION_NUMBER(3, 8, 0) && \
1293	defined(BOOST_LIBSTDCXX11))
1294	boost::allocator_construct(val_alloc, a.node_->value_ptr(),
1295	std::piecewise_construct,
1296	std::forward_as_tuple(boost::forward<Key>(k)),
1297	std::forward_as_tuple(boost::forward<Args>(args)...));
1298	#else
1299	// It doesn't seem to be possible to construct a tuple with 3 variadic
1300	// rvalue reference members when using older versions of clang with
1301	// libstdc++, so just use std::make_tuple instead of
1302	// std::forward_as_tuple.
1303	boost::allocator_construct(val_alloc, a.node_->value_ptr(),
1304	std::piecewise_construct,
1305	std::forward_as_tuple(boost::forward<Key>(k)),
1306	std::make_tuple(boost::forward<Args>(args)...));
1307	#endif
1308	return a.release();
1309	}
1310
1311	#else
1312
1313	template <typename Alloc, typename Key>
1314	inline
1315	typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1316	construct_node_pair(Alloc& alloc, BOOST_FWD_REF(Key) k)
1317	{
1318	node_constructor<Alloc> a(alloc);
1319	a.create_node();
1320	boost::unordered::detail::func::construct_value(
1321	boost::addressof(a.node_->value_ptr()->first),
1322	boost::forward<Key>(k));
1323	BOOST_TRY
1324	{
1325	boost::unordered::detail::func::construct_value(
1326	boost::addressof(a.node_->value_ptr()->second));
1327	}
1328	BOOST_CATCH(...)
1329	{
1330	boost::unordered::detail::func::destroy(
1331	boost::addressof(a.node_->value_ptr()->first));
1332	BOOST_RETHROW
1333	}
1334	BOOST_CATCH_END
1335	return a.release();
1336	}
1337
1338	template <typename Alloc, typename Key, typename Mapped>
1339	inline
1340	typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1341	construct_node_pair(
1342	Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_FWD_REF(Mapped) m)
1343	{
1344	node_constructor<Alloc> a(alloc);
1345	a.create_node();
1346	boost::unordered::detail::func::construct_value(
1347	boost::addressof(a.node_->value_ptr()->first),
1348	boost::forward<Key>(k));
1349	BOOST_TRY
1350	{
1351	boost::unordered::detail::func::construct_value(
1352	boost::addressof(a.node_->value_ptr()->second),
1353	boost::forward<Mapped>(m));
1354	}
1355	BOOST_CATCH(...)
1356	{
1357	boost::unordered::detail::func::destroy(
1358	boost::addressof(a.node_->value_ptr()->first));
1359	BOOST_RETHROW
1360	}
1361	BOOST_CATCH_END
1362	return a.release();
1363	}
1364
1365	template <typename Alloc, typename Key,
1366	BOOST_UNORDERED_EMPLACE_TEMPLATE>
1367	inline
1368	typename boost::unordered::detail::allocator_traits<Alloc>::pointer
1369	construct_node_pair_from_args(
1370	Alloc& alloc, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
1371	{
1372	node_constructor<Alloc> a(alloc);
1373	a.create_node();
1374	boost::unordered::detail::func::construct_value(
1375	boost::addressof(a.node_->value_ptr()->first),
1376	boost::forward<Key>(k));
1377	BOOST_TRY
1378	{
1379	boost::unordered::detail::func::construct_from_args(alloc,
1380	boost::addressof(a.node_->value_ptr()->second),
1381	BOOST_UNORDERED_EMPLACE_FORWARD);
1382	}
1383	BOOST_CATCH(...)
1384	{
1385	boost::unordered::detail::func::destroy(
1386	boost::addressof(a.node_->value_ptr()->first));
1387	BOOST_RETHROW
1388	}
1389	BOOST_CATCH_END
1390	return a.release();
1391	}
1392
1393	#endif
1394
1395	template <typename T, typename Alloc, typename Key>
1396	inline typename boost::allocator_pointer<Alloc>::type
1397	construct_node_from_key(T*, Alloc& alloc, BOOST_FWD_REF(Key) k)
1398	{
1399	return construct_node(alloc, boost::forward<Key>(k));
1400	}
1401
1402	template <typename T, typename V, typename Alloc, typename Key>
1403	inline typename boost::allocator_pointer<Alloc>::type
1404	construct_node_from_key(
1405	std::pair<T const, V>*, Alloc& alloc, BOOST_FWD_REF(Key) k)
1406	{
1407	return construct_node_pair(alloc, boost::forward<Key>(k));
1408	}
1409	} // namespace func
1410	}
1411	}
1412	}
1413
1414	#if defined(BOOST_MSVC)
1415	#pragma warning(pop)
1416	#endif
1417
1418	namespace boost {
1419	namespace unordered {
1420	namespace detail {
1421	//////////////////////////////////////////////////////////////////////////
1422	// Functions
1423	//
1424	// This double buffers the storage for the hash function and key equality
1425	// predicate in order to have exception safe copy/swap. To do so,
1426	// use 'construct_spare' to construct in the spare space, and then when
1427	// ready to use 'switch_functions' to switch to the new functions.
1428	// If an exception is thrown between these two calls, use
1429	// 'cleanup_spare_functions' to destroy the unused constructed functions.
1430
1431	#if defined(_GLIBCXX_HAVE_BUILTIN_LAUNDER)
1432	// gcc-12 warns when accessing the `current_functions` of our `functions`
1433	// class below with `-Wmaybe-unitialized`. By laundering the pointer, we
1434	// silence the warning and assure the compiler that a valid object exists
1435	// in that region of storage. This warning is also generated in C++03
1436	// which does not have `std::launder`. The compiler builtin is always
1437	// available, regardless of the C++ standard used when compiling.
1438	template <class T> T* launder(T* p) BOOST_NOEXCEPT
1439	{
1440	return __builtin_launder(p);
1441	}
1442	#else
1443	template <class T> T* launder(T* p) BOOST_NOEXCEPT { return p; }
1444	#endif
1445
1446	template <class H, class P> class functions
1447	{
1448	public:
1449	static const bool nothrow_move_assignable =
1450	boost::is_nothrow_move_assignable<H>::value &&
1451	boost::is_nothrow_move_assignable<P>::value;
1452	static const bool nothrow_move_constructible =
1453	boost::is_nothrow_move_constructible<H>::value &&
1454	boost::is_nothrow_move_constructible<P>::value;
1455	static const bool nothrow_swappable =
1456	boost::is_nothrow_swappable<H>::value &&
1457	boost::is_nothrow_swappable<P>::value;
1458
1459	private:
1460	functions& operator=(functions const&);
1461
1462	typedef compressed<H, P> function_pair;
1463
1464	typedef typename boost::aligned_storage<sizeof(function_pair),
1465	boost::alignment_of<function_pair>::value>::type aligned_function;
1466
1467	unsigned char current_; // 0/1 - Currently active functions
1468	// +2 - Both constructed
1469	aligned_function funcs_[`2`];
1470
1471	public:
1472	functions(H const& hf, P const& eq) : current_(`0`)
1473	{
1474	construct_functions(current_, hf, eq);
1475	}
1476
1477	functions(functions const& bf) : current_(`0`)
1478	{
1479	construct_functions(current_, bf.current_functions());
1480	}
1481
1482	functions(functions& bf, boost::unordered::detail::move_tag)
1483	: current_(`0`)
1484	{
1485	construct_functions(current_, bf.current_functions(),
1486	boost::unordered::detail::integral_constant<bool,
1487	nothrow_move_constructible>());
1488	}
1489
1490	~functions()
1491	{
1492	BOOST_ASSERT(!(current_ & `2`));
1493	destroy_functions(which: current_);
1494	}
1495
1496	H const& hash_function() const { return current_functions().first(); }
1497
1498	P const& key_eq() const { return current_functions().second(); }
1499
1500	function_pair const& current_functions() const
1501	{
1502	return *::boost::unordered::detail::launder(
1503	static_cast<function_pair const*>(
1504	static_cast<void const*>(funcs_[current_ & `1`].address())));
1505	}
1506
1507	function_pair& current_functions()
1508	{
1509	return *::boost::unordered::detail::launder(
1510	static_cast<function_pair*>(
1511	static_cast<void*>(funcs_[current_ & `1`].address())));
1512	}
1513
1514	void construct_spare_functions(function_pair const& f)
1515	{
1516	BOOST_ASSERT(!(current_ & `2`));
1517	construct_functions(current_ ^ `1`, f);
1518	current_ \|= `2`;
1519	}
1520
1521	void cleanup_spare_functions()
1522	{
1523	if (current_ & `2`) {
1524	current_ = static_cast<unsigned char>(current_ & `1`);
1525	destroy_functions(which: current_ ^ `1`);
1526	}
1527	}
1528
1529	void switch_functions()
1530	{
1531	BOOST_ASSERT(current_ & `2`);
1532	destroy_functions(which: static_cast<unsigned char>(current_ & `1`));
1533	current_ ^= `3`;
1534	}
1535
1536	private:
1537	void construct_functions(unsigned char which, H const& hf, P const& eq)
1538	{
1539	BOOST_ASSERT(!(which & `2`));
1540	new ((void*)&funcs_[which]) function_pair(hf, eq);
1541	}
1542
1543	void construct_functions(unsigned char which, function_pair const& f,
1544	boost::unordered::detail::false_type =
1545	boost::unordered::detail::false_type())
1546	{
1547	BOOST_ASSERT(!(which & `2`));
1548	new ((void*)&funcs_[which]) function_pair(f);
1549	}
1550
1551	void construct_functions(unsigned char which, function_pair& f,
1552	boost::unordered::detail::true_type)
1553	{
1554	BOOST_ASSERT(!(which & `2`));
1555	new ((void*)&funcs_[which])
1556	function_pair(f, boost::unordered::detail::move_tag ());
1557	}
1558
1559	void destroy_functions(unsigned char which)
1560	{
1561	BOOST_ASSERT(!(which & `2`));
1562	boost::unordered::detail::func::destroy(
1563	(function_pair*)(&funcs_[which]));
1564	}
1565	};
1566
1567	////////////////////////////////////////////////////////////////////////////
1568	// rvalue parameters when type can't be a BOOST_RV_REF(T) parameter
1569	// e.g. for int
1570
1571	#if !defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
1572	#define BOOST_UNORDERED_RV_REF(T) BOOST_RV_REF(T)
1573	#else
1574	struct please_ignore_this_overload
1575	{
1576	typedef please_ignore_this_overload type;
1577	};
1578
1579	template <typename T> struct rv_ref_impl
1580	{
1581	typedef BOOST_RV_REF(T) type;
1582	};
1583
1584	template <typename T>
1585	struct rv_ref : boost::conditional<boost::is_class<T>::value,
1586	boost::unordered::detail::rv_ref_impl<T>,
1587	please_ignore_this_overload>::type
1588	{
1589	};
1590
1591	#define BOOST_UNORDERED_RV_REF(T) \
1592	typename boost::unordered::detail::rv_ref<T>::type
1593	#endif
1594
1595	#if defined(BOOST_MSVC)
1596	#pragma warning(push)
1597	#pragma warning(disable : 4127) // conditional expression is constant
1598	#endif
1599
1600	//////////////////////////////////////////////////////////////////////////
1601	// convert double to std::size_t
1602
1603	inline std::size_t double_to_size(double f)
1604	{
1605	return f >= static_cast<double>(
1606	(std::numeric_limits<std::size_t>::max)())
1607	? (std::numeric_limits<std::size_t>::max)()
1608	: static_cast<std::size_t>(f);
1609	}
1610
1611	//////////////////////////////////////////////////////////////////////////
1612	// iterator definitions
1613
1614	namespace iterator_detail {
1615	template <class Node, class Bucket> class c_iterator;
1616
1617	template <class Node, class Bucket> class iterator
1618	{
1619	public:
1620	typedef typename Node::value_type value_type;
1621	typedef value_type element_type;
1622	typedef value_type* pointer;
1623	typedef value_type& reference;
1624	typedef std::ptrdiff_t difference_type;
1625	typedef std::forward_iterator_tag iterator_category;
1626
1627	iterator() : p(), itb(){}
1628
1629	reference operator() const* BOOST_NOEXCEPT { return dereference(); }
1630	pointer operator->() const BOOST_NOEXCEPT
1631	{
1632	pointer x = boost::addressof(p->value());
1633	return x;
1634	}
1635
1636	iterator& operator++() BOOST_NOEXCEPT
1637	{
1638	increment();
1639	return *this;
1640	}
1641
1642	iterator operator++(int) BOOST_NOEXCEPT
1643	{
1644	iterator old = *this;
1645	increment();
1646	return old;
1647	}
1648
1649	bool operator==(iterator const& other) const BOOST_NOEXCEPT
1650	{
1651	return equal(other);
1652	}
1653
1654	bool operator!=(iterator const& other) const BOOST_NOEXCEPT
1655	{
1656	return !equal(other);
1657	}
1658
1659	bool operator==(
1660	boost::unordered::detail::iterator_detail::c_iterator<Node,
1661	Bucket> const& other) const BOOST_NOEXCEPT
1662	{
1663	return equal(other);
1664	}
1665
1666	bool operator!=(
1667	boost::unordered::detail::iterator_detail::c_iterator<Node,
1668	Bucket> const& other) const BOOST_NOEXCEPT
1669	{
1670	return !equal(other);
1671	}
1672
1673	private:
1674	typedef typename Node::node_pointer node_pointer;
1675	typedef grouped_bucket_iterator<Bucket> bucket_iterator;
1676
1677	node_pointer p;
1678	bucket_iterator itb;
1679
1680	template <class Types> friend struct boost::unordered::detail::table;
1681	template <class N, class B> friend class c_iterator;
1682
1683	iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_) {}
1684
1685	value_type& dereference() const BOOST_NOEXCEPT { return p->value(); }
1686
1687	bool equal(const iterator& x) const BOOST_NOEXCEPT
1688	{
1689	return (p == x.p);
1690	}
1691
1692	bool equal(
1693	const boost::unordered::detail::iterator_detail::c_iterator<Node,
1694	Bucket>& x) const BOOST_NOEXCEPT
1695	{
1696	return (p == x.p);
1697	}
1698
1699	void increment() BOOST_NOEXCEPT
1700	{
1701	p = p->next;
1702	if (!p) {
1703	p = (++itb)->next;
1704	}
1705	}
1706	};
1707
1708	template <class Node, class Bucket> class c_iterator
1709	{
1710	public:
1711	typedef typename Node::value_type value_type;
1712	typedef value_type const element_type;
1713	typedef value_type const* pointer;
1714	typedef value_type const& reference;
1715	typedef std::ptrdiff_t difference_type;
1716	typedef std::forward_iterator_tag iterator_category;
1717
1718	c_iterator() : p(), itb(){}
1719	c_iterator(iterator<Node, Bucket> it) : p(it.p), itb(it.itb) {}
1720
1721	reference operator() const* BOOST_NOEXCEPT { return dereference(); }
1722	pointer operator->() const BOOST_NOEXCEPT
1723	{
1724	pointer x = boost::addressof(p->value());
1725	return x;
1726	}
1727
1728	c_iterator& operator++() BOOST_NOEXCEPT
1729	{
1730	increment();
1731	return *this;
1732	}
1733
1734	c_iterator operator++(int) BOOST_NOEXCEPT
1735	{
1736	c_iterator old = *this;
1737	increment();
1738	return old;
1739	}
1740
1741	bool operator==(c_iterator const& other) const BOOST_NOEXCEPT
1742	{
1743	return equal(x: other);
1744	}
1745
1746	bool operator!=(c_iterator const& other) const BOOST_NOEXCEPT
1747	{
1748	return !equal(x: other);
1749	}
1750
1751	bool operator==(
1752	boost::unordered::detail::iterator_detail::iterator<Node,
1753	Bucket> const& other) const BOOST_NOEXCEPT
1754	{
1755	return equal(x: other);
1756	}
1757
1758	bool operator!=(
1759	boost::unordered::detail::iterator_detail::iterator<Node,
1760	Bucket> const& other) const BOOST_NOEXCEPT
1761	{
1762	return !equal(x: other);
1763	}
1764
1765	private:
1766	typedef typename Node::node_pointer node_pointer;
1767	typedef grouped_bucket_iterator<Bucket> bucket_iterator;
1768
1769	node_pointer p;
1770	bucket_iterator itb;
1771
1772	template <class Types> friend struct boost::unordered::detail::table;
1773	template <class, class> friend class iterator;
1774
1775	c_iterator(node_pointer p_, bucket_iterator itb_) : p(p_), itb(itb_)
1776	{
1777	}
1778
1779	value_type const& dereference() const BOOST_NOEXCEPT
1780	{
1781	return p->value();
1782	}
1783
1784	bool equal(const c_iterator& x) const BOOST_NOEXCEPT
1785	{
1786	return (p == x.p);
1787	}
1788
1789	void increment() BOOST_NOEXCEPT
1790	{
1791	p = p->next;
1792	if (!p) {
1793	p = (++itb)->next;
1794	}
1795	}
1796	};
1797	} // namespace iterator_detail
1798
1799	//////////////////////////////////////////////////////////////////////////
1800	// table structure used by the containers
1801	template <typename Types>
1802	struct table : boost::unordered::detail::functions<typename Types::hasher,
1803	typename Types::key_equal>
1804	{
1805	private:
1806	table(table const&);
1807	table& operator=(table const&);
1808
1809	public:
1810	typedef typename Types::hasher hasher;
1811	typedef typename Types::key_equal key_equal;
1812	typedef typename Types::const_key_type const_key_type;
1813	typedef typename Types::extractor extractor;
1814	typedef typename Types::value_type value_type;
1815	typedef typename Types::table table_impl;
1816
1817	typedef boost::unordered::detail::functions<typename Types::hasher,
1818	typename Types::key_equal>
1819	functions;
1820
1821	typedef typename Types::value_allocator value_allocator;
1822	typedef typename boost::allocator_void_pointer<value_allocator>::type void_pointer;
1823	typedef node<value_type, void_pointer> node_type;
1824
1825	typedef boost::unordered::detail::grouped_bucket_array<
1826	bucket<node_type, void_pointer>, value_allocator, prime_fmod_size<> >
1827	bucket_array_type;
1828
1829	typedef typename bucket_array_type::node_allocator_type
1830	node_allocator_type;
1831	typedef typename boost::allocator_pointer<node_allocator_type>::type node_pointer;
1832
1833	typedef boost::unordered::detail::node_constructor<node_allocator_type>
1834	node_constructor;
1835	typedef boost::unordered::detail::node_tmp<node_allocator_type> node_tmp;
1836
1837	typedef typename bucket_array_type::bucket_type bucket_type;
1838
1839	typedef typename bucket_array_type::iterator bucket_iterator;
1840
1841	typedef typename bucket_array_type::local_iterator l_iterator;
1842	typedef typename bucket_array_type::const_local_iterator cl_iterator;
1843
1844	typedef std::size_t size_type;
1845
1846	typedef iterator_detail::iterator<node_type, bucket_type> iterator;
1847	typedef iterator_detail::c_iterator<node_type, bucket_type> c_iterator;
1848
1849	typedef std::pair<iterator, bool> emplace_return;
1850
1851	////////////////////////////////////////////////////////////////////////
1852	// Members
1853
1854	std::size_t size_;
1855	float mlf_;
1856	std::size_t max_load_;
1857	bucket_array_type buckets_;
1858
1859	public:
1860	////////////////////////////////////////////////////////////////////////
1861	// Data access
1862
1863	size_type bucket_count() const { return buckets_.bucket_count(); }
1864
1865	template <class Key>
1866	iterator next_group(Key const& k, c_iterator n) const
1867	{
1868	c_iterator last = this->end();
1869	while (n != last && this->key_eq()(k, extractor::extract(*n))) {
1870	++n;
1871	}
1872	return iterator(n.p, n.itb);
1873	}
1874
1875	template <class Key> std::size_t group_count(Key const& k) const
1876	{
1877	if (size_ == `0`) {
1878	return `0`;
1879	}
1880	std::size_t c = `0`;
1881	std::size_t const key_hash = this->hash(k);
1882	bucket_iterator itb =
1883	buckets_.at(buckets_.position(key_hash));
1884
1885	bool found = false;
1886
1887	for (node_pointer pos = itb->next; pos; pos = pos->next) {
1888	if (this->key_eq()(k, this->get_key(pos))) {
1889	++c;
1890	found = true;
1891	} else if (found) {
1892	break;
1893	}
1894	}
1895	return c;
1896	}
1897
1898	node_allocator_type const& node_alloc() const
1899	{
1900	return buckets_.get_node_allocator();
1901	}
1902
1903	node_allocator_type& node_alloc()
1904	{
1905	return buckets_.get_node_allocator();
1906	}
1907
1908	std::size_t max_bucket_count() const
1909	{
1910	typedef typename bucket_array_type::size_policy size_policy;
1911	return size_policy::size(size_policy::size_index(
1912	boost::allocator_max_size(this->node_alloc())));
1913	}
1914
1915	iterator begin() const
1916	{
1917	if (size_ == `0`) {
1918	return end();
1919	}
1920
1921	bucket_iterator itb = buckets_.begin();
1922	return iterator(itb->next, itb);
1923	}
1924
1925	iterator end() const
1926	{
1927	return iterator();
1928	}
1929
1930	l_iterator begin(std::size_t bucket_index) const
1931	{
1932	return buckets_.begin(bucket_index);
1933	}
1934
1935	std::size_t hash_to_bucket(std::size_t hash_value) const
1936	{
1937	return buckets_.position(hash_value);
1938	}
1939
1940	std::size_t bucket_size(std::size_t index) const
1941	{
1942	std::size_t count = `0`;
1943	if (size_ > `0`) {
1944	bucket_iterator itb = buckets_.at(index);
1945	node_pointer n = itb->next;
1946	while (n) {
1947	++count;
1948	n = n->next;
1949	}
1950	}
1951	return count;
1952	}
1953
1954	////////////////////////////////////////////////////////////////////////
1955	// Load methods
1956
1957	void recalculate_max_load()
1958	{
1959	// From 6.3.1/13:
1960	// Only resize when size >= mlf_ count*
1961	std::size_t const bc = buckets_.bucket_count();
1962
1963	// it's important we do the `bc == 0` check here because the `mlf_`
1964	// can be specified to be infinity. The operation `n INF` is `INF`*
1965	// for all `n > 0` but NaN for `n == 0`.
1966	//
1967	max_load_ =
1968	bc == `0` ? `0`
1969	: boost::unordered::detail::double_to_size(
1970	f: static_cast<double>(mlf_) * static_cast<double>(bc));
1971	}
1972
1973	void max_load_factor(float z)
1974	{
1975	BOOST_ASSERT(z > `0`);
1976	mlf_ = (std::max)(a: z, b: minimum_max_load_factor);
1977	recalculate_max_load();
1978	}
1979
1980	////////////////////////////////////////////////////////////////////////
1981	// Constructors
1982
1983	table()
1984	: functions(hasher(), key_equal()), size_(`0`), mlf_(`1.0f`),
1985	max_load_(`0`)
1986	{
1987	}
1988
1989	table(std::size_t num_buckets, hasher const& hf, key_equal const& eq,
1990	node_allocator_type const& a)
1991	: functions(hf, eq), size_(`0`), mlf_(`1.0f`), max_load_(`0`),
1992	buckets_(num_buckets, a)
1993	{
1994	recalculate_max_load();
1995	}
1996
1997	table(table const& x, node_allocator_type const& a)
1998	: functions(x), size_(`0`), mlf_(x.mlf_), max_load_(`0`),
1999	buckets_(x.size_, a)
2000	{
2001	recalculate_max_load();
2002	}
2003
2004	table(table& x, boost::unordered::detail::move_tag m)
2005	: functions(x, m), size_(x.size_), mlf_(x.mlf_),
2006	max_load_(x.max_load_), buckets_(boost::move(x.buckets_))
2007	{
2008	x.size_ = `0`;
2009	x.max_load_ = `0`;
2010	}
2011
2012	table(table& x, node_allocator_type const& a,
2013	boost::unordered::detail::move_tag m)
2014	: functions(x, m), size_(`0`), mlf_(x.mlf_), max_load_(`0`),
2015	buckets_(x.bucket_count(), a)
2016	{
2017	recalculate_max_load();
2018	}
2019
2020	////////////////////////////////////////////////////////////////////////
2021	// Swap and Move
2022
2023	void swap_allocators(table& other, false_type)
2024	{
2025	boost::unordered::detail::func::ignore_unused_variable_warning(other);
2026
2027	// According to 23.2.1.8, if propagate_on_container_swap is
2028	// false the behaviour is undefined unless the allocators
2029	// are equal.
2030	BOOST_ASSERT(node_alloc() == other.node_alloc());
2031	}
2032
2033	// Not nothrow swappable
2034	void swap(table& x, false_type)
2035	{
2036	if (this == &x) {
2037	return;
2038	}
2039
2040	this->construct_spare_functions(x.current_functions());
2041	BOOST_TRY { x.construct_spare_functions(this->current_functions()); }
2042	BOOST_CATCH(...)
2043	{
2044	this->cleanup_spare_functions();
2045	BOOST_RETHROW
2046	}
2047	BOOST_CATCH_END
2048	this->switch_functions();
2049	x.switch_functions();
2050
2051	buckets_.swap(x.buckets_);
2052	boost::swap(size_, x.size_);
2053	std::swap(mlf_, x.mlf_);
2054	std::swap(max_load_, x.max_load_);
2055	}
2056
2057	// Nothrow swappable
2058	void swap(table& x, true_type)
2059	{
2060	buckets_.swap(x.buckets_);
2061	boost::swap(size_, x.size_);
2062	std::swap(mlf_, x.mlf_);
2063	std::swap(max_load_, x.max_load_);
2064	this->current_functions().swap(x.current_functions());
2065	}
2066
2067	// Only swaps the allocators if propagate_on_container_swap.
2068	// If not propagate_on_container_swap and allocators aren't
2069	// equal, behaviour is undefined.
2070	void swap(table& x)
2071	{
2072	BOOST_ASSERT(boost::allocator_propagate_on_container_swap<
2073	node_allocator_type>::type::value \|\|
2074	node_alloc() == x.node_alloc());
2075	swap(x, boost::unordered::detail::integral_constant<bool,
2076	functions::nothrow_swappable>());
2077	}
2078
2079	// Only call with nodes allocated with the currect allocator, or
2080	// one that is equal to it. (Can't assert because other's
2081	// allocators might have already been moved).
2082	void move_buckets_from(table& other)
2083	{
2084	buckets_ = boost::move(other.buckets_);
2085
2086	size_ = other.size_;
2087	max_load_ = other.max_load_;
2088
2089	other.size_ = `0`;
2090	other.max_load_ = `0`;
2091	}
2092
2093	// For use in the constructor when allocators might be different.
2094	void move_construct_buckets(table& src)
2095	{
2096	if (this->node_alloc() == src.node_alloc()) {
2097	move_buckets_from(other&: src);
2098	return;
2099	}
2100
2101	if (src.size_ == `0`) {
2102	return;
2103	}
2104
2105	BOOST_ASSERT(
2106	buckets_.bucket_count() == src.buckets_.bucket_count());
2107
2108	this->reserve(src.size_);
2109	for (iterator pos = src.begin(); pos != src.end(); ++pos) {
2110	node_tmp b(detail::func::construct_node(
2111	this->node_alloc(), boost::move(pos.p->value())),
2112	this->node_alloc());
2113
2114	const_key_type& k = this->get_key(b.node_);
2115	std::size_t key_hash = this->hash(k);
2116
2117	bucket_iterator itb =
2118	buckets_.at(buckets_.position(key_hash));
2119	buckets_.insert_node(itb, b.release());
2120	++size_;
2121	}
2122	}
2123
2124	////////////////////////////////////////////////////////////////////////
2125	// Delete/destruct
2126
2127	~table() { delete_buckets(); }
2128
2129	void delete_node(node_pointer p)
2130	{
2131	node_allocator_type alloc = this->node_alloc();
2132
2133	value_allocator val_alloc(alloc);
2134	boost::allocator_destroy(val_alloc, p->value_ptr());
2135	boost::allocator_deallocate(alloc, p, `1`);
2136	}
2137
2138	void delete_buckets()
2139	{
2140	iterator pos = begin(), last = this->end();
2141	for (; pos != last;) {
2142	node_pointer p = pos.p;
2143	bucket_iterator itb = pos.itb;
2144	++pos;
2145	buckets_.extract_node(itb, p);
2146	delete_node(p);
2147	--size_;
2148	}
2149
2150	buckets_.clear();
2151	}
2152
2153	////////////////////////////////////////////////////////////////////////
2154	// Clear
2155
2156	void clear_impl();
2157
2158	////////////////////////////////////////////////////////////////////////
2159	// Assignment
2160
2161	template <typename UniqueType>
2162	void assign(table const& x, UniqueType is_unique)
2163	{
2164	typedef typename boost::allocator_propagate_on_container_copy_assignment<node_allocator_type>::type pocca;
2165
2166	if (this != &x) {
2167	assign(x, is_unique,
2168	boost::unordered::detail::integral_constant<bool,
2169	pocca::value>());
2170	}
2171	}
2172
2173	template <typename UniqueType>
2174	void assign(table const &x, UniqueType is_unique, false_type)
2175	{
2176	// Strong exception safety.
2177	this->construct_spare_functions(x.current_functions());
2178	BOOST_TRY
2179	{
2180	mlf_ = x.mlf_;
2181	recalculate_max_load();
2182
2183	this->reserve_for_insert(x.size_);
2184	this->clear_impl();
2185	}
2186	BOOST_CATCH(...)
2187	{
2188	this->cleanup_spare_functions();
2189	BOOST_RETHROW
2190	}
2191	BOOST_CATCH_END
2192	this->switch_functions();
2193	copy_buckets(x, is_unique);
2194	}
2195
2196	template <typename UniqueType>
2197	void assign(table const &x, UniqueType is_unique, true_type)
2198	{
2199	if (node_alloc() == x.node_alloc())
2200	{
2201	buckets_.reset_allocator(x.node_alloc());
2202	assign(x, is_unique, false_type());
2203	}
2204	else
2205	{
2206	bucket_array_type new_buckets(x.size_, x.node_alloc());
2207	this->construct_spare_functions(x.current_functions());
2208	this->switch_functions();
2209
2210	// Delete everything with current allocators before assigning
2211	// the new ones.
2212	delete_buckets();
2213	buckets_.reset_allocator(x.node_alloc());
2214	buckets_ = boost::move(new_buckets);
2215
2216	// Copy over other data, all no throw.
2217	mlf_ = x.mlf_;
2218	reserve(x.size_);
2219
2220	// Finally copy the elements.
2221	if (x.size_)
2222	{
2223	copy_buckets(x, is_unique);
2224	}
2225	}
2226	}
2227
2228	template <typename UniqueType>
2229	void move_assign(table& x, UniqueType is_unique)
2230	{
2231	if (this != &x) {
2232	move_assign(x, is_unique,
2233	boost::unordered::detail::integral_constant<bool,
2234	boost::allocator_propagate_on_container_move_assignment<
2235	node_allocator_type>::type::value>());
2236	}
2237	}
2238
2239	// Propagate allocator
2240	template <typename UniqueType>
2241	void move_assign(table& x, UniqueType, true_type)
2242	{
2243	if (!functions::nothrow_move_assignable) {
2244	this->construct_spare_functions(x.current_functions());
2245	this->switch_functions();
2246	} else {
2247	this->current_functions().move_assign(x.current_functions());
2248	}
2249	delete_buckets();
2250
2251	buckets_.reset_allocator(x.buckets_.get_node_allocator());
2252	mlf_ = x.mlf_;
2253	move_buckets_from(other&: x);
2254	}
2255
2256	// Don't propagate allocator
2257	template <typename UniqueType>
2258	void move_assign(table& x, UniqueType is_unique, false_type)
2259	{
2260	if (node_alloc() == x.node_alloc()) {
2261	move_assign_equal_alloc(x);
2262	} else {
2263	move_assign_realloc(x, is_unique);
2264	}
2265	}
2266
2267	void move_assign_equal_alloc(table& x)
2268	{
2269	if (!functions::nothrow_move_assignable) {
2270	this->construct_spare_functions(x.current_functions());
2271	this->switch_functions();
2272	} else {
2273	this->current_functions().move_assign(x.current_functions());
2274	}
2275	delete_buckets();
2276	mlf_ = x.mlf_;
2277	move_buckets_from(other&: x);
2278	}
2279
2280	template <typename UniqueType>
2281	void move_assign_realloc(table& x, UniqueType is_unique)
2282	{
2283	this->construct_spare_functions(x.current_functions());
2284	BOOST_TRY
2285	{
2286	mlf_ = x.mlf_;
2287	recalculate_max_load();
2288	if (x.size_ > `0`) {
2289	this->reserve_for_insert(x.size_);
2290	}
2291	this->clear_impl();
2292	}
2293	BOOST_CATCH(...)
2294	{
2295	this->cleanup_spare_functions();
2296	BOOST_RETHROW
2297	}
2298	BOOST_CATCH_END
2299	this->switch_functions();
2300	move_assign_buckets(x, is_unique);
2301	}
2302
2303	// Accessors
2304
2305	const_key_type& get_key(node_pointer n) const
2306	{
2307	return extractor::extract(n->value());
2308	}
2309
2310	template <class Key>
2311	std::size_t hash(Key const& k) const
2312	{
2313	return this->hash_function()(k);
2314	}
2315
2316	// Find Node
2317
2318	template <class Key>
2319	node_pointer find_node_impl(
2320	Key const& x, bucket_iterator itb) const
2321	{
2322	node_pointer p = node_pointer();
2323	if (itb != buckets_.end()) {
2324	key_equal const& pred = this->key_eq();
2325	p = itb->next;
2326	for (; p; p = p->next) {
2327	if (pred(x, extractor::extract(p->value()))) {
2328	break;
2329	}
2330	}
2331	}
2332	return p;
2333	}
2334
2335	template <class Key> node_pointer find_node(Key const& k) const
2336	{
2337	std::size_t const key_hash = this->hash(k);
2338	return find_node_impl(
2339	k, buckets_.at(buckets_.position(key_hash)));
2340	}
2341
2342	node_pointer find_node(
2343	const_key_type& k, bucket_iterator itb) const
2344	{
2345	return find_node_impl(k, itb);
2346	}
2347
2348	template <class Key> iterator find(Key const& k) const
2349	{
2350	return this->transparent_find(
2351	k, this->hash_function(), this->key_eq());
2352	}
2353
2354	template <class Key, class Hash, class Pred>
2355	inline iterator transparent_find(
2356	Key const& k, Hash const& h, Pred const& pred) const
2357	{
2358	if (size_ > `0`) {
2359	std::size_t const key_hash = h(k);
2360	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
2361	for (node_pointer p = itb->next; p; p = p->next) {
2362	if (BOOST_LIKELY(pred(k, extractor::extract(p->value())))) {
2363	return iterator(p, itb);
2364	}
2365	}
2366	}
2367
2368	return this->end();
2369	}
2370
2371	template <class Key>
2372	node_pointer* find_prev(Key const& key, bucket_iterator itb)
2373	{
2374	if (size_ > `0`) {
2375	key_equal pred = this->key_eq();
2376	for (node_pointer* pp = boost::addressof(itb->next); *pp;
2377	pp = boost::addressof((*pp)->next)) {
2378	if (pred(key, extractor::extract((*pp)->value()))) {
2379	return pp;
2380	}
2381	}
2382	}
2383	typedef node_pointer* node_pointer_pointer;
2384	return node_pointer_pointer();
2385	}
2386
2387	// Extract and erase
2388
2389	template <class Key> node_pointer extract_by_key_impl(Key const& k)
2390	{
2391	iterator it = this->find(k);
2392	if (it == this->end()) {
2393	return node_pointer();
2394	}
2395
2396	buckets_.extract_node(it.itb, it.p);
2397	--size_;
2398
2399	return it.p;
2400	}
2401
2402	// Reserve and rehash
2403	void transfer_node(
2404	node_pointer p, bucket_type&, bucket_array_type& new_buckets)
2405	{
2406	const_key_type& key = extractor::extract(p->value());
2407	std::size_t const h = this->hash(key);
2408	bucket_iterator itnewb = new_buckets.at(new_buckets.position(h));
2409	new_buckets.insert_node(itnewb, p);
2410	}
2411
2412	static std::size_t min_buckets(std::size_t num_elements, float mlf)
2413	{
2414	std::size_t num_buckets = static_cast<std::size_t>(
2415	std::ceil(x: static_cast<float>(num_elements) / mlf));
2416
2417	if (num_buckets == `0` && num_elements > `0`) { // mlf == inf
2418	num_buckets = `1`;
2419	}
2420	return num_buckets;
2421	}
2422
2423	void rehash(std::size_t);
2424	void reserve(std::size_t);
2425	void reserve_for_insert(std::size_t);
2426	void rehash_impl(std::size_t);
2427
2428	////////////////////////////////////////////////////////////////////////
2429	// Unique keys
2430
2431	// equals
2432
2433	bool equals_unique(table const& other) const
2434	{
2435	if (this->size_ != other.size_)
2436	return false;
2437
2438	c_iterator pos = this->begin();
2439	c_iterator last = this->end();
2440
2441	while (pos != last) {
2442	node_pointer p = pos.p;
2443	node_pointer p2 = other.find_node(this->get_key(p));
2444	if (!p2 \|\| !(p->value() == p2->value())) {
2445	return false;
2446	}
2447	++pos;
2448	}
2449
2450	return true;
2451	}
2452
2453	// Emplace/Insert
2454
2455	template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
2456	iterator emplace_hint_unique(
2457	c_iterator hint, const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
2458	{
2459	if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
2460	return iterator(hint.p, hint.itb);
2461	} else {
2462	return emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
2463	}
2464	}
2465
2466	template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
2467	emplace_return emplace_unique(
2468	const_key_type& k, BOOST_UNORDERED_EMPLACE_ARGS)
2469	{
2470	std::size_t key_hash = this->hash(k);
2471	bucket_iterator itb =
2472	buckets_.at(buckets_.position(key_hash));
2473	node_pointer pos = this->find_node_impl(k, itb);
2474
2475	if (pos) {
2476	return emplace_return(iterator(pos, itb), false);
2477	} else {
2478	node_tmp b(boost::unordered::detail::func::construct_node_from_args(
2479	this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
2480	this->node_alloc());
2481
2482	if (size_ + `1` > max_load_) {
2483	reserve(size_ + `1`);
2484	itb = buckets_.at(buckets_.position(key_hash));
2485	}
2486
2487	node_pointer p = b.release();
2488	buckets_.insert_node(itb, p);
2489	++size_;
2490
2491	return emplace_return(iterator(p, itb), true);
2492	}
2493	}
2494
2495	template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
2496	iterator emplace_hint_unique(
2497	c_iterator hint, no_key, BOOST_UNORDERED_EMPLACE_ARGS)
2498	{
2499	node_tmp b(boost::unordered::detail::func::construct_node_from_args(
2500	this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
2501	this->node_alloc());
2502
2503	const_key_type& k = this->get_key(b.node_);
2504	if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
2505	return iterator(hint.p, hint.itb);
2506	}
2507
2508	std::size_t const key_hash = this->hash(k);
2509	bucket_iterator itb =
2510	buckets_.at(buckets_.position(key_hash));
2511
2512	node_pointer p = this->find_node_impl(k, itb);
2513	if (p) {
2514	return iterator(p, itb);
2515	}
2516
2517	if (size_ + `1` > max_load_) {
2518	this->reserve(size_ + `1`);
2519	itb = buckets_.at(buckets_.position(key_hash));
2520	}
2521
2522	p = b.release();
2523	buckets_.insert_node(itb, p);
2524	++size_;
2525	return iterator(p, itb);
2526	}
2527
2528	template <BOOST_UNORDERED_EMPLACE_TEMPLATE>
2529	emplace_return emplace_unique(no_key, BOOST_UNORDERED_EMPLACE_ARGS)
2530	{
2531	node_tmp b(boost::unordered::detail::func::construct_node_from_args(
2532	this->node_alloc(), BOOST_UNORDERED_EMPLACE_FORWARD),
2533	this->node_alloc());
2534
2535	const_key_type& k = this->get_key(b.node_);
2536	std::size_t key_hash = this->hash(k);
2537
2538	bucket_iterator itb =
2539	buckets_.at(buckets_.position(key_hash));
2540	node_pointer pos = this->find_node_impl(k, itb);
2541
2542	if (pos) {
2543	return emplace_return(iterator(pos, itb), false);
2544	} else {
2545	if (size_ + `1` > max_load_) {
2546	reserve(size_ + `1`);
2547	itb = buckets_.at(buckets_.position(key_hash));
2548	}
2549
2550	node_pointer p = b.release();
2551	buckets_.insert_node(itb, p);
2552	++size_;
2553
2554	return emplace_return(iterator(p, itb), true);
2555	}
2556	}
2557
2558	template <typename Key>
2559	emplace_return try_emplace_unique(BOOST_FWD_REF(Key) k)
2560	{
2561	std::size_t key_hash = this->hash(k);
2562	bucket_iterator itb =
2563	buckets_.at(buckets_.position(key_hash));
2564
2565	node_pointer pos = this->find_node_impl(k, itb);
2566
2567	if (pos) {
2568	return emplace_return(iterator(pos, itb), false);
2569	} else {
2570	node_allocator_type alloc = node_alloc();
2571
2572	value_type* dispatch = BOOST_NULLPTR;
2573
2574	node_tmp tmp(detail::func::construct_node_from_key(
2575	dispatch, alloc, boost::forward<Key>(k)),
2576	alloc);
2577
2578	if (size_ + `1` > max_load_) {
2579	reserve(size_ + `1`);
2580	itb = buckets_.at(buckets_.position(key_hash));
2581	}
2582
2583	node_pointer p = tmp.release();
2584	buckets_.insert_node(itb, p);
2585
2586	++size_;
2587	return emplace_return(iterator(p, itb), true);
2588	}
2589	}
2590
2591	template <typename Key>
2592	iterator try_emplace_hint_unique(c_iterator hint, BOOST_FWD_REF(Key) k)
2593	{
2594	if (hint.p && this->key_eq()(extractor::extract(*hint), k)) {
2595	return iterator(hint.p, hint.itb);
2596	} else {
2597	return try_emplace_unique(k).first;
2598	}
2599	}
2600
2601	template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
2602	emplace_return try_emplace_unique(
2603	BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
2604	{
2605	std::size_t key_hash = this->hash(k);
2606	bucket_iterator itb =
2607	buckets_.at(buckets_.position(key_hash));
2608
2609	node_pointer pos = this->find_node_impl(k, itb);
2610
2611	if (pos) {
2612	return emplace_return(iterator(pos, itb), false);
2613	}
2614
2615	node_tmp b(
2616	boost::unordered::detail::func::construct_node_pair_from_args(
2617	this->node_alloc(), k, BOOST_UNORDERED_EMPLACE_FORWARD),
2618	this->node_alloc());
2619
2620	if (size_ + `1` > max_load_) {
2621	reserve(size_ + `1`);
2622	itb = buckets_.at(buckets_.position(key_hash));
2623	}
2624
2625	pos = b.release();
2626
2627	buckets_.insert_node(itb, pos);
2628	++size_;
2629	return emplace_return(iterator(pos, itb), true);
2630	}
2631
2632	template <typename Key, BOOST_UNORDERED_EMPLACE_TEMPLATE>
2633	iterator try_emplace_hint_unique(
2634	c_iterator hint, BOOST_FWD_REF(Key) k, BOOST_UNORDERED_EMPLACE_ARGS)
2635	{
2636	if (hint.p && this->key_eq()(hint->first, k)) {
2637	return iterator(hint.p, hint.itb);
2638	} else {
2639	return try_emplace_unique(k, BOOST_UNORDERED_EMPLACE_FORWARD).first;
2640	}
2641	}
2642
2643	template <typename Key, typename M>
2644	emplace_return insert_or_assign_unique(
2645	BOOST_FWD_REF(Key) k, BOOST_FWD_REF(M) obj)
2646	{
2647	std::size_t key_hash = this->hash(k);
2648	bucket_iterator itb =
2649	buckets_.at(buckets_.position(key_hash));
2650
2651	node_pointer p = this->find_node_impl(k, itb);
2652	if (p) {
2653	p->value().second = boost::forward<M>(obj);
2654	return emplace_return(iterator(p, itb), false);
2655	}
2656
2657	node_tmp b(boost::unordered::detail::func::construct_node_pair(
2658	this->node_alloc(), boost::forward<Key>(k),
2659	boost::forward<M>(obj)),
2660	node_alloc());
2661
2662	if (size_ + `1` > max_load_) {
2663	reserve(size_ + `1`);
2664	itb = buckets_.at(buckets_.position(key_hash));
2665	}
2666
2667	p = b.release();
2668
2669	buckets_.insert_node(itb, p);
2670	++size_;
2671	return emplace_return(iterator(p, itb), true);
2672	}
2673
2674	template <typename NodeType, typename InsertReturnType>
2675	void move_insert_node_type_unique(
2676	NodeType& np, InsertReturnType& result)
2677	{
2678	if (!np) {
2679	result.position = this->end();
2680	result.inserted = false;
2681	return;
2682	}
2683
2684	const_key_type& k = this->get_key(np.ptr_);
2685	std::size_t const key_hash = this->hash(k);
2686	bucket_iterator itb =
2687	buckets_.at(buckets_.position(key_hash));
2688	node_pointer p = this->find_node_impl(k, itb);
2689
2690	if (p) {
2691	iterator pos(p, itb);
2692	result.node = boost::move(np);
2693	result.position = pos;
2694	result.inserted = false;
2695	return;
2696	}
2697
2698	this->reserve_for_insert(size_ + `1`);
2699
2700	p = np.ptr_;
2701	itb = buckets_.at(buckets_.position(key_hash));
2702
2703	buckets_.insert_node(itb, p);
2704	np.ptr_ = node_pointer();
2705	++size_;
2706
2707	result.position = iterator(p, itb);
2708	result.inserted = true;
2709	}
2710
2711	template <typename NodeType>
2712	iterator move_insert_node_type_with_hint_unique(
2713	c_iterator hint, NodeType& np)
2714	{
2715	if (!np) {
2716	return this->end();
2717	}
2718
2719	const_key_type& k = this->get_key(np.ptr_);
2720	if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
2721	return iterator(hint.p, hint.itb);
2722	}
2723
2724	std::size_t const key_hash = this->hash(k);
2725	bucket_iterator itb =
2726	buckets_.at(buckets_.position(key_hash));
2727	node_pointer p = this->find_node_impl(k, itb);
2728	if (p) {
2729	return iterator(p, itb);
2730	}
2731
2732	p = np.ptr_;
2733
2734	if (size_ + `1` > max_load_) {
2735	this->reserve(size_ + `1`);
2736	itb = buckets_.at(buckets_.position(key_hash));
2737	}
2738
2739	buckets_.insert_node(itb, p);
2740	++size_;
2741	np.ptr_ = node_pointer();
2742	return iterator(p, itb);
2743	}
2744
2745	template <typename Types2>
2746	void merge_unique(boost::unordered::detail::table<Types2>& other)
2747	{
2748	typedef boost::unordered::detail::table<Types2> other_table;
2749	BOOST_STATIC_ASSERT((boost::is_same<node_type,
2750	typename other_table::node_type>::value));
2751	BOOST_ASSERT(this->node_alloc() == other.node_alloc());
2752
2753	if (other.size_ == `0`) {
2754	return;
2755	}
2756
2757	this->reserve_for_insert(size_ + other.size_);
2758
2759	iterator last = other.end();
2760	for (iterator pos = other.begin(); pos != last;) {
2761	const_key_type& key = other.get_key(pos.p);
2762	std::size_t const key_hash = this->hash(key);
2763
2764	bucket_iterator itb =
2765	buckets_.at(buckets_.position(key_hash));
2766
2767	if (this->find_node_impl(key, itb)) {
2768	++pos;
2769	continue;
2770	}
2771
2772	iterator old = pos;
2773	++pos;
2774
2775	node_pointer p = other.extract_by_iterator_unique(old);
2776	buckets_.insert_node(itb, p);
2777	++size_;
2778	}
2779	}
2780
2781	////////////////////////////////////////////////////////////////////////
2782	// Insert range methods
2783	//
2784	// if hash function throws, or inserting > 1 element, basic exception
2785	// safety strong otherwise
2786
2787	template <class InputIt>
2788	void insert_range_unique(no_key, InputIt i, InputIt j)
2789	{
2790	hasher const& hf = this->hash_function();
2791	node_allocator_type alloc = this->node_alloc();
2792
2793	for (; i != j; ++i) {
2794	node_tmp tmp(detail::func::construct_node(alloc, *i), alloc);
2795
2796	value_type const& value = tmp.node_->value();
2797	const_key_type& key = extractor::extract(value);
2798	std::size_t const h = hf(key);
2799
2800	bucket_iterator itb = buckets_.at(buckets_.position(h));
2801	node_pointer it = find_node_impl(key, itb);
2802	if (it) {
2803	continue;
2804	}
2805
2806	if (size_ + `1` > max_load_) {
2807	reserve(size_ + `1`);
2808	itb = buckets_.at(buckets_.position(h));
2809	}
2810
2811	node_pointer nptr = tmp.release();
2812	buckets_.insert_node(itb, nptr);
2813	++size_;
2814	}
2815	}
2816
2817	////////////////////////////////////////////////////////////////////////
2818	// Extract
2819
2820	inline node_pointer extract_by_iterator_unique(c_iterator i)
2821	{
2822	node_pointer p = i.p;
2823	bucket_iterator itb = i.itb;
2824
2825	buckets_.extract_node(itb, p);
2826	--size_;
2827
2828	return p;
2829	}
2830
2831	////////////////////////////////////////////////////////////////////////
2832	// Erase
2833	//
2834
2835	template <class Key> std::size_t erase_key_unique_impl(Key const& k)
2836	{
2837	bucket_iterator itb = buckets_.at(buckets_.position(this->hash(k)));
2838	node_pointer* pp = this->find_prev(k, itb);
2839	if (!pp) {
2840	return `0`;
2841	}
2842
2843	node_pointer p = *pp;
2844	buckets_.extract_node_after(itb, pp);
2845	this->delete_node(p);
2846	--size_;
2847	return `1`;
2848	}
2849
2850	iterator erase_node(c_iterator pos) {
2851	c_iterator next = pos;
2852	++next;
2853
2854	bucket_iterator itb = pos.itb;
2855	node_pointer* pp = boost::addressof(itb->next);
2856	while (*pp != pos.p) {
2857	pp = boost::addressof((*pp)->next);
2858	}
2859
2860	buckets_.extract_node_after(itb, pp);
2861	this->delete_node(pos.p);
2862	--size_;
2863
2864	return iterator(next.p, next.itb);
2865	}
2866
2867	iterator erase_nodes_range(c_iterator first, c_iterator last)
2868	{
2869	if (first == last) {
2870	return iterator(last.p, last.itb);
2871	}
2872
2873	// though `first` stores of a copy of a pointer to a node, we wish to
2874	// mutate the pointers stored internally by the singly-linked list in
2875	// each bucket group so we have to retrieve it manually by iterating
2876	//
2877	bucket_iterator itb = first.itb;
2878	node_pointer* pp = boost::addressof(itb->next);
2879	while (*pp != first.p) {
2880	pp = boost::addressof((*pp)->next);
2881	}
2882
2883	while (*pp != last.p) {
2884	node_pointer p = *pp;
2885	pp = (pp)->next;
2886
2887	this->delete_node(p);
2888	--size_;
2889
2890
2891	bool const at_end = !(*pp);
2892	bool const is_empty_bucket = !itb->next;
2893
2894	if (at_end) {
2895	if (is_empty_bucket) {
2896	buckets_.unlink_bucket(itb++);
2897	} else {
2898	++itb;
2899	}
2900	pp = boost::addressof(itb->next);
2901	}
2902	}
2903
2904	return iterator(last.p, last.itb);
2905	}
2906
2907	////////////////////////////////////////////////////////////////////////
2908	// fill_buckets_unique
2909
2910	void copy_buckets(table const& src, true_type)
2911	{
2912	BOOST_ASSERT(size_ == `0`);
2913
2914	this->reserve_for_insert(src.size_);
2915
2916	for (iterator pos = src.begin(); pos != src.end(); ++pos) {
2917	value_type const& value = *pos;
2918	const_key_type& key = extractor::extract(value);
2919	std::size_t const key_hash = this->hash(key);
2920
2921	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
2922
2923	node_allocator_type alloc = this->node_alloc();
2924	node_tmp tmp(detail::func::construct_node(alloc, value), alloc);
2925
2926	buckets_.insert_node(itb, tmp.release());
2927	++size_;
2928	}
2929	}
2930
2931	void move_assign_buckets(table& src, true_type)
2932	{
2933	BOOST_ASSERT(size_ == `0`);
2934	BOOST_ASSERT(max_load_ >= src.size_);
2935
2936	iterator last = src.end();
2937	node_allocator_type alloc = this->node_alloc();
2938
2939	for (iterator pos = src.begin(); pos != last; ++pos) {
2940	value_type value = boost::move(*pos);
2941	const_key_type& key = extractor::extract(value);
2942	std::size_t const key_hash = this->hash(key);
2943
2944	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
2945
2946	node_tmp tmp(
2947	detail::func::construct_node(alloc, boost::move(value)), alloc);
2948
2949	buckets_.insert_node(itb, tmp.release());
2950	++size_;
2951	}
2952	}
2953
2954	////////////////////////////////////////////////////////////////////////
2955	// Equivalent keys
2956
2957	// Equality
2958
2959	bool equals_equiv(table const& other) const
2960	{
2961	if (this->size_ != other.size_)
2962	return false;
2963
2964	iterator last = this->end();
2965	for (iterator n1 = this->begin(); n1 != last;) {
2966	const_key_type& k = extractor::extract(*n1);
2967	iterator n2 = other.find(k);
2968	if (n2 == other.end()) {
2969	return false;
2970	}
2971
2972	iterator end1 = this->next_group(k, n1);
2973	iterator end2 = other.next_group(k, n2);
2974
2975	if (!group_equals_equiv(n1, end1, n2, end2)) {
2976	return false;
2977	}
2978
2979	n1 = end1;
2980	}
2981
2982	return true;
2983	}
2984
2985	static bool group_equals_equiv(iterator n1, iterator end1,
2986	iterator n2, iterator end2)
2987	{
2988	for (;;) {
2989	if (n1 != n2)
2990	break;
2991
2992	++n1;
2993	++n2;
2994
2995	if (n1 == end1)
2996	return n2 == end2;
2997
2998	if (n2 == end2)
2999	return false;
3000	}
3001
3002	for (iterator n1a = n1, n2a = n2;;) {
3003	++n1a;
3004	++n2a;
3005
3006	if (n1a == end1) {
3007	if (n2a == end2)
3008	break;
3009	else
3010	return false;
3011	}
3012
3013	if (n2a == end2)
3014	return false;
3015	}
3016
3017	iterator start = n1;
3018	for (; n1 != end1; ++n1) {
3019	value_type const& v = *n1;
3020	if (!find_equiv(n: start, last: n1, v)) {
3021	std::size_t matches = count_equal_equiv(n: n2, last: end2, v);
3022	if (!matches)
3023	return false;
3024
3025	iterator t = n1;
3026	if (matches != `1` + count_equal_equiv(n: ++t, last: end1, v))
3027	return false;
3028	}
3029	}
3030
3031	return true;
3032	}
3033
3034	static bool find_equiv(
3035	iterator n, iterator last, value_type const& v)
3036	{
3037	for (; n != last; ++n)
3038	if (*n == v)
3039	return true;
3040	return false;
3041	}
3042
3043	static std::size_t count_equal_equiv(
3044	iterator n, iterator last, value_type const& v)
3045	{
3046	std::size_t count = `0`;
3047	for (; n != last; ++n)
3048	if (*n == v)
3049	++count;
3050	return count;
3051	}
3052
3053	// Emplace/Insert
3054
3055	iterator emplace_equiv(node_pointer n)
3056	{
3057	node_tmp a(n, this->node_alloc());
3058	const_key_type& k = this->get_key(a.node_);
3059	std::size_t key_hash = this->hash(k);
3060	bucket_iterator itb =
3061	buckets_.at(buckets_.position(key_hash));
3062	node_pointer hint = this->find_node_impl(k, itb);
3063
3064	if (size_ + `1` > max_load_) {
3065	this->reserve(size_ + `1`);
3066	itb = buckets_.at(buckets_.position(key_hash));
3067	}
3068	node_pointer p = a.release();
3069	buckets_.insert_node_hint(itb, p, hint);
3070	++size_;
3071	return iterator(p, itb);
3072	}
3073
3074	iterator emplace_hint_equiv(c_iterator hint, node_pointer n)
3075	{
3076	node_tmp a(n, this->node_alloc());
3077	const_key_type& k = this->get_key(a.node_);
3078	bucket_iterator itb = hint.itb;
3079	node_pointer p = hint.p;
3080
3081	std::size_t key_hash = `0u`;
3082
3083	bool const needs_rehash = (size_ + `1` > max_load_);
3084	bool const usable_hint = (p && this->key_eq()(k, this->get_key(p)));
3085
3086	if (!usable_hint) {
3087	key_hash = this->hash(k);
3088	itb = buckets_.at(buckets_.position(key_hash));
3089	p = this->find_node_impl(k, itb);
3090	} else if (usable_hint && needs_rehash) {
3091	key_hash = this->hash(k);
3092	}
3093
3094	if (needs_rehash) {
3095	this->reserve(size_ + `1`);
3096	itb = buckets_.at(buckets_.position(key_hash));
3097	}
3098
3099	a.release();
3100	buckets_.insert_node_hint(itb, n, p);
3101	++size_;
3102	return iterator(n, itb);
3103	}
3104
3105	void emplace_no_rehash_equiv(node_pointer n)
3106	{
3107	BOOST_ASSERT(size_ + `1` <= max_load_);
3108	node_tmp a(n, this->node_alloc());
3109	const_key_type& k = this->get_key(a.node_);
3110	std::size_t key_hash = this->hash(k);
3111	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
3112	node_pointer hint = this->find_node_impl(k, itb);
3113	node_pointer p = a.release();
3114	buckets_.insert_node_hint(itb, p, hint);
3115	++size_;
3116	}
3117
3118	template <typename NodeType>
3119	iterator move_insert_node_type_equiv(NodeType& np)
3120	{
3121	iterator result;
3122
3123	if (np) {
3124	this->reserve_for_insert(size_ + `1`);
3125
3126	const_key_type& k = this->get_key(np.ptr_);
3127	std::size_t key_hash = this->hash(k);
3128
3129	bucket_iterator itb =
3130	buckets_.at(buckets_.position(key_hash));
3131
3132	node_pointer hint = this->find_node_impl(k, itb);
3133	buckets_.insert_node_hint(itb, np.ptr_, hint);
3134	++size_;
3135
3136	result = iterator(np.ptr_, itb);
3137	np.ptr_ = node_pointer();
3138	}
3139
3140	return result;
3141	}
3142
3143	template <typename NodeType>
3144	iterator move_insert_node_type_with_hint_equiv(
3145	c_iterator hint, NodeType& np)
3146	{
3147	iterator result;
3148	if (np) {
3149	bucket_iterator itb = hint.itb;
3150	node_pointer pos = hint.p;
3151	const_key_type& k = this->get_key(np.ptr_);
3152	std::size_t key_hash = this->hash(k);
3153	if (size_ + `1` > max_load_) {
3154	this->reserve(size_ + `1`);
3155	itb = buckets_.at(buckets_.position(key_hash));
3156	}
3157
3158	if (hint.p && this->key_eq()(k, this->get_key(hint.p))) {
3159	} else {
3160	itb = buckets_.at(buckets_.position(key_hash));
3161	pos = this->find_node_impl(k, itb);
3162	}
3163	buckets_.insert_node_hint(itb, np.ptr_, pos);
3164	++size_;
3165	result = iterator(np.ptr_, itb);
3166
3167	np.ptr_ = node_pointer();
3168	}
3169
3170	return result;
3171	}
3172
3173	////////////////////////////////////////////////////////////////////////
3174	// Insert range methods
3175
3176	// if hash function throws, or inserting > 1 element, basic exception
3177	// safety. Strong otherwise
3178	template <class I>
3179	typename boost::unordered::detail::enable_if_forward<I, void>::type
3180	insert_range_equiv(I i, I j)
3181	{
3182	if (i == j)
3183	return;
3184
3185	std::size_t distance = static_cast<std::size_t>(std::distance(i, j));
3186	if (distance == `1`) {
3187	emplace_equiv(n: boost::unordered::detail::func::construct_node(
3188	this->node_alloc(), *i));
3189	} else {
3190	// Only require basic exception safety here
3191	this->reserve_for_insert(size_ + distance);
3192
3193	for (; i != j; ++i) {
3194	emplace_no_rehash_equiv(
3195	n: boost::unordered::detail::func::construct_node(
3196	this->node_alloc(), *i));
3197	}
3198	}
3199	}
3200
3201	template <class I>
3202	typename boost::unordered::detail::disable_if_forward<I, void>::type
3203	insert_range_equiv(I i, I j)
3204	{
3205	for (; i != j; ++i) {
3206	emplace_equiv(n: boost::unordered::detail::func::construct_node(
3207	this->node_alloc(), *i));
3208	}
3209	}
3210
3211	////////////////////////////////////////////////////////////////////////
3212	// Extract
3213
3214	inline node_pointer extract_by_iterator_equiv(c_iterator n)
3215	{
3216	node_pointer p = n.p;
3217	bucket_iterator itb = n.itb;
3218	buckets_.extract_node(itb, p);
3219	--size_;
3220	return p;
3221	}
3222
3223	////////////////////////////////////////////////////////////////////////
3224	// Erase
3225	//
3226	// no throw
3227
3228	template <class Key> std::size_t erase_key_equiv_impl(Key const& k)
3229	{
3230	std::size_t deleted_count = `0`;
3231
3232	bucket_iterator itb = buckets_.at(buckets_.position(this->hash(k)));
3233	node_pointer* pp = this->find_prev(k, itb);
3234	if (pp) {
3235	while (pp && this->key_eq()(this->get_key(pp), k)) {
3236	node_pointer p = *pp;
3237	pp = (pp)->next;
3238
3239	this->delete_node(p);
3240	--size_;
3241	++deleted_count;
3242	}
3243
3244	if (!itb->next) {
3245	buckets_.unlink_bucket(itb);
3246	}
3247	}
3248	return deleted_count;
3249	}
3250
3251	std::size_t erase_key_equiv(const_key_type& k)
3252	{
3253	return this->erase_key_equiv_impl(k);
3254	}
3255
3256	////////////////////////////////////////////////////////////////////////
3257	// fill_buckets
3258
3259	void copy_buckets(table const& src, false_type)
3260	{
3261	BOOST_ASSERT(size_ == `0`);
3262
3263	this->reserve_for_insert(src.size_);
3264
3265	iterator last = src.end();
3266	for (iterator pos = src.begin(); pos != last; ++pos) {
3267	value_type const& value = *pos;
3268	const_key_type& key = extractor::extract(value);
3269	std::size_t const key_hash = this->hash(key);
3270
3271	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
3272	node_allocator_type alloc = this->node_alloc();
3273	node_tmp tmp(detail::func::construct_node(alloc, value), alloc);
3274	node_pointer hint = this->find_node_impl(key, itb);
3275	buckets_.insert_node_hint(itb, tmp.release(), hint);
3276	++size_;
3277	}
3278	}
3279
3280	void move_assign_buckets(table& src, false_type)
3281	{
3282	BOOST_ASSERT(size_ == `0`);
3283	BOOST_ASSERT(max_load_ >= src.size_);
3284
3285	iterator last = src.end();
3286	node_allocator_type alloc = this->node_alloc();
3287
3288	for (iterator pos = src.begin(); pos != last; ++pos) {
3289	value_type value = boost::move(*pos);
3290	const_key_type& key = extractor::extract(value);
3291	std::size_t const key_hash = this->hash(key);
3292
3293	bucket_iterator itb = buckets_.at(buckets_.position(key_hash));
3294
3295	node_pointer hint = this->find_node_impl(key, itb);
3296	node_tmp tmp(
3297	detail::func::construct_node(alloc, boost::move(value)), alloc);
3298
3299	buckets_.insert_node_hint(itb, tmp.release(), hint);
3300	++size_;
3301	}
3302	}
3303	};
3304
3305	//////////////////////////////////////////////////////////////////////////
3306	// Clear
3307
3308	template <typename Types> inline void table<Types>::clear_impl()
3309	{
3310	bucket_iterator itb = buckets_.begin(), last = buckets_.end();
3311	for (; itb != last;) {
3312	bucket_iterator next_itb = itb;
3313	++next_itb;
3314	node_pointer* pp = boost::addressof(itb->next);
3315	while (*pp) {
3316	node_pointer p = *pp;
3317	buckets_.extract_node_after(itb, pp);
3318	this->delete_node(p);
3319	--size_;
3320	}
3321	itb = next_itb;
3322	}
3323	}
3324
3325	//////////////////////////////////////////////////////////////////////////
3326	// Reserve & Rehash
3327
3328	// if hash function throws, basic exception safety
3329	// strong otherwise.
3330	template <typename Types>
3331	inline void table<Types>::rehash(std::size_t num_buckets)
3332	{
3333	num_buckets = buckets_.bucket_count_for(
3334	(std::max)(a: min_buckets(num_elements: size_, mlf: mlf_), b: num_buckets));
3335
3336	if (num_buckets != this->bucket_count()) {
3337	this->rehash_impl(num_buckets);
3338	}
3339	}
3340
3341	template <class Types>
3342	inline void table<Types>::reserve(std::size_t num_elements)
3343	{
3344	std::size_t num_buckets = min_buckets(num_elements, mlf: mlf_);
3345	this->rehash(num_buckets);
3346	}
3347
3348	template <class Types>
3349	inline void table<Types>::reserve_for_insert(std::size_t num_elements)
3350	{
3351	if (num_elements > max_load_) {
3352	std::size_t const num_buckets = static_cast<std::size_t>(
3353	`1.0f` + std::ceil(x: static_cast<float>(num_elements) / mlf_));
3354
3355	this->rehash_impl(num_buckets);
3356	}
3357	}
3358
3359	template <class Types>
3360	inline void table<Types>::rehash_impl(std::size_t num_buckets)
3361	{
3362	bucket_array_type new_buckets(
3363	num_buckets, buckets_.get_node_allocator());
3364
3365	BOOST_TRY
3366	{
3367	boost::unordered::detail::span<bucket_type> bspan = buckets_.raw();
3368
3369	bucket_type* pos = bspan.data;
3370	std::size_t size = bspan.size;
3371	bucket_type* last = pos + size;
3372
3373	for (; pos != last; ++pos) {
3374	bucket_type& b = *pos;
3375	for (node_pointer p = b.next; p;) {
3376	node_pointer next_p = p->next;
3377	transfer_node(p, b, new_buckets);
3378	p = next_p;
3379	b.next = p;
3380	}
3381	}
3382	}
3383	BOOST_CATCH(...)
3384	{
3385	for (bucket_iterator pos = new_buckets.begin();
3386	pos != new_buckets.end(); ++pos) {
3387	bucket_type& b = *pos;
3388	for (node_pointer p = b.next; p;) {
3389	node_pointer next_p = p->next;
3390	delete_node(p);
3391	--size_;
3392	p = next_p;
3393	}
3394	}
3395	buckets_.unlink_empty_buckets();
3396	BOOST_RETHROW
3397	}
3398	BOOST_CATCH_END
3399
3400	buckets_ = boost::move(new_buckets);
3401	recalculate_max_load();
3402	}
3403
3404	#if defined(BOOST_MSVC)
3405	#pragma warning(pop)
3406	#endif
3407
3408	////////////////////////////////////////////////////////////////////////
3409	// key extractors
3410	//
3411	// no throw
3412	//
3413	// 'extract_key' is called with the emplace parameters to return a
3414	// key if available or 'no_key' is one isn't and will need to be
3415	// constructed. This could be done by overloading the emplace
3416	// implementation
3417	// for the different cases, but that's a bit tricky on compilers without
3418	// variadic templates.
3419
3420	template <typename Key, typename T> struct is_key
3421	{
3422	template <typename T2> static choice1::type test(T2 const&);
3423	static choice2::type test(Key const&);
3424
3425	enum
3426	{
3427	value = sizeof(test(boost::unordered::detail::make<T>())) ==
3428	sizeof(choice2::type)
3429	};
3430
3431	typedef
3432	typename boost::conditional<value, Key const&, no_key>::type type;
3433	};
3434
3435	template <class ValueType> struct set_extractor
3436	{
3437	typedef ValueType value_type;
3438	typedef ValueType key_type;
3439
3440	static key_type const& extract(value_type const& v) { return v; }
3441
3442	static key_type const& extract(BOOST_UNORDERED_RV_REF(value_type) v)
3443	{
3444	return v;
3445	}
3446
3447	static no_key extract() { return no_key (); }
3448
3449	template <class Arg> static no_key extract(Arg const&)
3450	{
3451	return no_key ();
3452	}
3453
3454	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
3455	template <class Arg1, class Arg2, class... Args>
3456	static no_key extract(Arg1 const&, Arg2 const&, Args const&...)
3457	{
3458	return no_key ();
3459	}
3460	#else
3461	template <class Arg1, class Arg2>
3462	static no_key extract(Arg1 const&, Arg2 const&)
3463	{
3464	return no_key();
3465	}
3466	#endif
3467	};
3468
3469	template <class ValueType> struct map_extractor
3470	{
3471	typedef ValueType value_type;
3472	typedef typename boost::remove_const<typename boost::unordered::detail::
3473	pair_traits<ValueType>::first_type>::type key_type;
3474
3475	static key_type const& extract(value_type const& v) { return v.first; }
3476
3477	template <class Second>
3478	static key_type const& extract(std::pair<key_type, Second> const& v)
3479	{
3480	return v.first;
3481	}
3482
3483	template <class Second>
3484	static key_type const& extract(
3485	std::pair<key_type const, Second> const& v)
3486	{
3487	return v.first;
3488	}
3489
3490	#if defined(BOOST_NO_CXX11_RVALUE_REFERENCES)
3491	template <class Second>
3492	static key_type const& extract(
3493	boost::rv<std::pair<key_type, Second> > const& v)
3494	{
3495	return v.first;
3496	}
3497
3498	template <class Second>
3499	static key_type const& extract(
3500	boost::rv<std::pair<key_type const, Second> > const& v)
3501	{
3502	return v.first;
3503	}
3504	#endif
3505
3506	template <class Arg1>
3507	static key_type const& extract(key_type const& k, Arg1 const&)
3508	{
3509	return k;
3510	}
3511
3512	static no_key extract() { return no_key (); }
3513
3514	template <class Arg> static no_key extract(Arg const&)
3515	{
3516	return no_key ();
3517	}
3518
3519	template <class Arg1, class Arg2>
3520	static no_key extract(Arg1 const&, Arg2 const&)
3521	{
3522	return no_key ();
3523	}
3524
3525	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
3526	template <class Arg1, class Arg2, class Arg3, class... Args>
3527	static no_key extract(
3528	Arg1 const&, Arg2 const&, Arg3 const&, Args const&...)
3529	{
3530	return no_key ();
3531	}
3532	#endif
3533
3534	#if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
3535
3536	#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
3537	template <typename T2> \
3538	static no_key extract(boost::unordered::piecewise_construct_t, \
3539	namespace_ tuple<> const&, T2 const&) \
3540	{ \
3541	return no_key (); \
3542	} \
3543	\
3544	template <typename T, typename T2> \
3545	static typename is_key<key_type, T>::type extract( \
3546	boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k, \
3547	T2 const&) \
3548	{ \
3549	return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
3550	}
3551
3552	#else
3553
3554	#define BOOST_UNORDERED_KEY_FROM_TUPLE(namespace_) \
3555	static no_key extract( \
3556	boost::unordered::piecewise_construct_t, namespace_ tuple<> const&) \
3557	{ \
3558	return no_key(); \
3559	} \
3560	\
3561	template <typename T> \
3562	static typename is_key<key_type, T>::type extract( \
3563	boost::unordered::piecewise_construct_t, namespace_ tuple<T> const& k) \
3564	{ \
3565	return typename is_key<key_type, T>::type(namespace_ get<0>(k)); \
3566	}
3567
3568	#endif
3569
3570	BOOST_UNORDERED_KEY_FROM_TUPLE(boost::)
3571
3572	#if BOOST_UNORDERED_TUPLE_ARGS
3573	BOOST_UNORDERED_KEY_FROM_TUPLE(std::)
3574	#endif
3575
3576	#undef BOOST_UNORDERED_KEY_FROM_TUPLE
3577	};
3578
3579	template <class Container, class Predicate>
3580	typename Container::size_type erase_if(Container& c, Predicate& pred)
3581	{
3582	typedef typename Container::size_type size_type;
3583	typedef typename Container::iterator iterator;
3584
3585	size_type const size = c.size();
3586
3587	for (iterator pos = c.begin(), last = c.end(); pos != last;) {
3588	if (pred(*pos)) {
3589	pos = c.erase(pos);
3590	} else {
3591	++pos;
3592	}
3593	}
3594
3595	return (size - c.size());
3596	}
3597	}
3598	}
3599	}
3600
3601	#undef BOOST_UNORDERED_EMPLACE_TEMPLATE
3602	#undef BOOST_UNORDERED_EMPLACE_ARGS
3603	#undef BOOST_UNORDERED_EMPLACE_FORWARD
3604
3605	#endif
3606

Browse the source code of include/boost/unordered/detail/implementation.hpp