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