libs/hub/include/boost/container/hub.hpp

99.0% Lines (676/683) 91.3% List of functions (1192/1306)

[ ] prev/next file n p prev/next uncovered line

hub.hpp

f(x) Functions (1306)

Function Calls Lines Blocks

Line	Hits	Source Code
1		/* Hub container.
2		*
3		* Copyright 2025-2026 Joaquin M Lopez Munoz.
4		* Distributed under the Boost Software License, Version 1.0.
5		* (See accompanying file LICENSE_1_0.txt or copy at
6		* http://www.boost.org/LICENSE_1_0.txt)
7		*/
8
9		#ifndef BOOST_CONTAINER_HUB_HPP
10		#define BOOST_CONTAINER_HUB_HPP
11
12		#include <algorithm>
13		#include <boost/assert.hpp>
14		#include <boost/config.hpp>
15		#include <boost/config/workaround.hpp>
16		#include <boost/core/allocator_access.hpp>
17		#include <boost/core/bit.hpp>
18		#include <boost/core/empty_value.hpp>
19		#include <boost/core/no_exceptions_support.hpp>
20		#include <boost/core/pointer_traits.hpp>
21		#include <boost/throw_exception.hpp>
22		#include <cstddef>
23		#include <cstdint>
24		#include <functional>
25		#include <initializer_list>
26		#include <iterator>
27		#include <memory>
28		#include <new>
29		#include <stdexcept>
30		#include <type_traits>
31		#include <utility>
32
33		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
34		#include <memory_resource>
35		#endif
36
37		#if defined(BOOST_NO_CXX20_HDR_CONCEPTS) \|\| defined(BOOST_NO_CXX20_HDR_RANGES)
38		#define BOOST_CONTAINER_HUB_NO_RANGES
39		#elif BOOST_WORKAROUND(BOOST_CLANG_VERSION, < 170100) && \
40		defined(BOOST_LIBSTDCXX_VERSION)
41		/* https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109647
42		* https://github.com/llvm/llvm-project/issues/49620
43		*/
44		#define BOOST_CONTAINER_HUB_NO_RANGES
45		#endif
46
47		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
48		#include <concepts>
49		#include <ranges>
50		#endif
51
52		#if !defined(BOOST_CONTAINER_HUB_DISABLE_SSE2)
53		#if defined(BOOST_CONTAINER_HUB_ENABLE_SSE2)\|\| \
54		defined(__SSE2__) \|\| \
55		defined(_M_X64) \|\| (defined(_M_IX86_FP) && _M_IX86_FP >= 2)
56		#define BOOST_CONTAINER_HUB_SSE2
57		#endif
58		#endif
59
60		#if defined(BOOST_CONTAINER_HUB_SSE2)
61		#include <emmintrin.h>
62		#endif
63
64		#ifdef __has_builtin
65		#define BOOST_CONTAINER_HUB_HAS_BUILTIN(x) __has_builtin(x)
66		#else
67		#define BOOST_CONTAINER_HUB_HAS_BUILTIN(x) 0
68		#endif
69
70		#if !defined(NDEBUG)
71		#define BOOST_CONTAINER_HUB_ASSUME(cond) BOOST_ASSERT(cond)
72		#elif BOOST_CONTAINER_HUB_HAS_BUILTIN(__builtin_assume)
73		#define BOOST_CONTAINER_HUB_ASSUME(cond) __builtin_assume(cond)
74		#elif defined(__GNUC__) \|\| \
75		BOOST_CONTAINER_HUB_HAS_BUILTIN(__builtin_unreachable)
76		#define BOOST_CONTAINER_HUB_ASSUME(cond) \
77		do{ \
78		if(!(cond)) __builtin_unreachable(); \
79		} while(0)
80		#elif defined(_MSC_VER)
81		#define BOOST_CONTAINER_HUB_ASSUME(cond) __assume(cond)
82		#else
83		#define BOOST_CONTAINER_HUB_ASSUME(cond) \
84		do{ \
85		static_cast<void>(false && (cond)); \
86		} while(0)
87		#endif
88
89		/* We use BOOST_CONTAINER_HUB_PREFETCH[_BLOCK] macros rather than proper
90		* functions because of https://gcc.gnu.org/bugzilla/show_bug.cgi?id=109985
91		*/
92
93		#if defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
94		#define BOOST_CONTAINER_HUB_PREFETCH(p) \
95		__builtin_prefetch((const char*)boost::to_address(p))
96		#elif defined(BOOST_CONTAINER_HUB_SSE2)
97		#define BOOST_CONTAINER_HUB_PREFETCH(p) \
98		_mm_prefetch((const char*)boost::to_address(p), _MM_HINT_T0)
99		#else
100		#define BOOST_CONTAINER_HUB_PREFETCH(p) ((void)(p))
101		#endif
102
103		#define BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, Block) \
104		do{ \
105		auto p0 = &static_cast<Block&>(*(pbb)); \
106		BOOST_CONTAINER_HUB_PREFETCH(p0->data()); \
107		} while(0)
108
109		#if defined(BOOST_MSVC)
110		#pragma warning(push)
111		#pragma warning(disable:4714) /* marked as __forceinline not inlined */
112		#endif
113
114		namespace boost {
115
116		namespace container {
117
118		template<typename T, typename Allocator = std::allocator<T>>
119		class hub;
120
121		template<typename T, typename Allocator, typename Predicate>
122		typename hub<T, Allocator>::size_type erase_if(hub<T, Allocator>&, Predicate);
123
124		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
125		namespace pmr {
126
127		template<typename T>
128		using hub = boost::container::hub<T, std::pmr::polymorphic_allocator<T>>;
129
130		}
131		#endif
132
133		namespace hub_detail {
134
135	30574994x	inline int unchecked_countr_zero(std::uint64_t x)
136		{
137		#if defined(BOOST_MSVC) && (defined(_M_X64) \|\| defined(_M_ARM64))
138		unsigned long r;
139		_BitScanForward64(&r, x);
140		return (int)r;
141		#elif defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
142	30574994x	return (int)__builtin_ctzll(x);
143		#else
144		BOOST_CONTAINER_HUB_ASSUME(x != 0);
145		return (int)core::countr_zero(x);
146		#endif
147		}
148
149	10413115x	inline int unchecked_countr_one(std::uint64_t x)
150		{
151	10413115x	return unchecked_countr_zero(~x);
152		}
153
154	626934x	inline int unchecked_countl_zero(std::uint64_t x)
155		{
156		#if defined(BOOST_MSVC) && (defined(_M_X64) \|\| defined(_M_ARM64))
157		unsigned long r;
158		_BitScanReverse64(&r, x);
159		return (int)(63 - r);
160		#elif defined(BOOST_GCC) \|\| defined(BOOST_CLANG)
161	626934x	return (int)__builtin_clzll(x);
162		#else
163		BOOST_CONTAINER_HUB_ASSUME(x != 0);
164		return (int)core::countl_zero(x);
165		#endif
166		}
167
168		template<typename Pointer, typename T>
169		using pointer_rebind_t =
170		typename pointer_traits<Pointer>::template rebind<T>;
171
172		template<typename VoidPointer>
173		struct block_base
174		{
175		using pointer = pointer_rebind_t<VoidPointer, block_base>;
176		using const_pointer = pointer_rebind_t<VoidPointer, const block_base>;
177		using mask_type = std::uint64_t;
178
179		static constexpr int N = 64;
180		static constexpr mask_type full = (mask_type)(-1);
181
182	21616095x	static pointer pointer_to(block_base& x) noexcept
183		{
184	21616095x	return pointer_traits<pointer>::pointer_to(x);
185		}
186
187	3427x	static const_pointer pointer_to(const block_base& x) noexcept
188		{
189	3427x	return pointer_traits<const_pointer>::pointer_to(x);
190		}
191
192		BOOST_FORCEINLINE void link_available_before(pointer p) noexcept
193		{
194	155686x	next_available = p;
195	155686x	prev_available = p->prev_available;
196	156492x	next_available->prev_available = pointer_to(*this);
197	156492x	prev_available->next_available = pointer_to(*this);
198	156300x	}
199
200		BOOST_FORCEINLINE void link_available_after(pointer p) noexcept
201		{
202	117687x	prev_available = p;
203	117687x	next_available = p->next_available;
204	117807x	next_available->prev_available = pointer_to(*this);
205	117807x	prev_available->next_available = pointer_to(*this);
206	117777x	}
207
208		BOOST_FORCEINLINE void unlink_available() noexcept
209		{
210	174337x	prev_available->next_available = next_available;
211	174483x	next_available->prev_available = prev_available;
212	174337x	}
213
214		BOOST_FORCEINLINE void link_before(pointer p) noexcept
215		{
216	155662x	next = p;
217	155662x	prev = p->prev;
218	156398x	next->prev = pointer_to(*this);
219	156412x	prev->next = pointer_to(*this);
220	156234x	}
221
222		BOOST_FORCEINLINE void unlink() noexcept
223		{
224	99074x	prev->next = next;
225	99164x	next->prev = prev;
226	99074x	}
227
228		pointer prev_available,
229		next_available,
230		prev,
231		next;
232		mask_type mask;
233		};
234
235		template<typename ValuePointer>
236		struct block: block_base<pointer_rebind_t<ValuePointer, void>>
237		{
238		using super = block_base<pointer_rebind_t<ValuePointer, void>>;
239
240	41019428x	ValuePointer data() noexcept { return data_; }
241		ValuePointer data_;
242		};
243
244		template<typename ValuePointer>
245	17940x	void swap_payload(block<ValuePointer>& x, block<ValuePointer>& y) noexcept
246		{
247	17940x	std::swap(x.mask, y.mask);
248	17940x	std::swap(x.data_, y.data_);
249	17940x	}
250
251		template<typename ValuePointer>
252		struct block_list: block<ValuePointer>
253		{
254		using block = hub_detail::block<ValuePointer>;
255		using block_base = typename block::super;
256		using block_base_pointer = typename block_base::pointer;
257		using const_block_base_pointer = typename block_base::const_pointer;
258		using block_pointer = pointer_rebind_t<ValuePointer, block>;
259		using block_base::full;
260		using block_base::pointer_to;
261		using block_base::prev_available;
262		using block_base::next_available;
263		using block_base::prev;
264		using block_base::next;
265		using block_base::mask;
266		using block::data_;
267
268		static block_pointer
269	15624323x	static_cast_block_pointer(block_base_pointer pbb) noexcept
270		{
271	15621282x	return pointer_traits<block_pointer>::pointer_to(
272	15624323x	static_cast<block&>(*pbb));
273		}
274
275	347x	block_list()
276	59x	{
277	347x	reset();
278	347x	mask = 1; /* sentinel */
279	347x	data_ = nullptr;
280	347x	}
281
282	29x	block_list(block_list&& x) noexcept: block_list{}
283		{
284	34x	if(x.next_available != x.header()) {
285	29x	prev_available = x.prev_available;
286	29x	next_available = x.next_available;
287	34x	next_available->prev_available = header();
288	39x	prev_available->next_available = header();
289		}
290	34x	if(x.prev != x.header()) {
291	29x	prev = x.prev;
292	29x	next = x.next;
293	34x	next->prev = header();
294	39x	prev->next = header();
295		}
296	29x	x.reset();
297	29x	}
298
299	53x	block_list& operator=(block_list&& x) noexcept
300		{
301	53x	reset();
302	63x	if(x.next_available != x.header()) {
303	45x	prev_available = x.prev_available;
304	45x	next_available = x.next_available;
305	53x	next_available->prev_available = header();
306	61x	prev_available->next_available = header();
307		}
308	63x	if(x.prev != x.header()) {
309	45x	prev = x.prev;
310	45x	next = x.next;
311	53x	next->prev = header();
312	61x	prev->next = header();
313		}
314	53x	x.reset();
315	53x	return *this;
316		}
317
318	823x	void reset() noexcept
319		{
320	823x	prev_available = header();
321	823x	next_available = header();
322	823x	prev = header();
323	823x	next = header();
324	823x	}
325
326	10789623x	block_base_pointer header() noexcept
327		{
328	10789623x	return pointer_to(static_cast<block_base&>(*this));
329		}
330
331	3427x	const_block_base_pointer header() const noexcept
332		{
333	3427x	return pointer_to(static_cast<const block_base&>(*this));
334		}
335
336		BOOST_FORCEINLINE void link_at_back(block_pointer pb) noexcept
337		{
338	155648x	pb->link_before(header());
339	156220x	}
340
341		BOOST_FORCEINLINE void link_before(
342		block_pointer pbx, block_pointer pby) noexcept
343		{
344	14x	pbx->link_before(pby);
345	14x	}
346
347		BOOST_FORCEINLINE static void unlink(block_pointer pb) noexcept
348		{
349	59496x	pb->unlink();
350	99358x	}
351
352		BOOST_FORCEINLINE void link_available_at_back(block_pointer pb) noexcept
353		{
354	155686x	pb->link_available_before(header());
355	156300x	}
356
357		BOOST_FORCEINLINE void link_available_at_front(block_pointer pb) noexcept
358		{
359	117687x	pb->link_available_after(header());
360	117777x	}
361
362		BOOST_FORCEINLINE void unlink_available(block_pointer pb) noexcept
363		{
364	174337x	pb->unlink_available();
365	174799x	}
366		};
367
368		template<typename ValuePointer>
369		class iterator
370		{
371		using element_type = typename pointer_traits<ValuePointer>::element_type;
372		template<typename Value2Pointer>
373		using enable_if_consts_to_element_type_t =typename std::enable_if<
374		std::is_same<
375		const typename pointer_traits<Value2Pointer>::element_type,
376		element_type>::value
377		>::type;
378
379		public:
380		using value_type = typename std::remove_const<element_type>::type;
381		using difference_type =
382		typename pointer_traits<ValuePointer>::difference_type;
383		using pointer = ValuePointer;
384		using reference = element_type&;
385		using iterator_category = std::bidirectional_iterator_tag;
386
387		iterator() = default;
388	24417x	iterator(const iterator&) = default;
389
390		template<
391		typename Value2Pointer,
392		typename = enable_if_consts_to_element_type_t<Value2Pointer>
393		>
394	3480x	iterator(const iterator<Value2Pointer>& x) noexcept: pbb{x.pbb}, n{x.n} {}
395
396	2802x	iterator& operator=(const iterator& x) = default;
397
398		template<
399		typename Value2Pointer,
400		typename = enable_if_consts_to_element_type_t<Value2Pointer>
401		>
402	3078x	iterator& operator=(const iterator<Value2Pointer>& x) noexcept
403		{
404	3078x	pbb = x.pbb;
405	3078x	n = x.n;
406	3078x	return *this;
407		}
408
409	9841711x	pointer operator->() const noexcept
410		{
411	9930031x	return static_cast<block&>(*pbb).data() + n;
412		}
413
414	9841637x	reference operator*() const noexcept
415		{
416	9885779x	return *operator->();
417		}
418
419		BOOST_FORCEINLINE iterator& operator++() noexcept
420		{
421	4955404x	auto mask = pbb->mask & (full << 1 << n);
422	5323087x	if(BOOST_UNLIKELY(mask == 0)) {
423	122688x	pbb = pbb->next;
424	136496x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->next, block);
425	133057x	mask = pbb->mask;
426		}
427	5333499x	n = hub_detail::unchecked_countr_zero(mask);
428	5333499x	return *this;
429		}
430
431		BOOST_FORCEINLINE iterator operator++(int) noexcept
432		{
433	9768x	iterator tmp(*this);
434		this->operator++();
435	9768x	return tmp;
436		}
437
438		BOOST_FORCEINLINE iterator& operator--() noexcept
439		{
440	9025x	auto mask = pbb->mask & (full >> 1 >> (N - 1 - n));
441	35074x	if(BOOST_UNLIKELY(mask == 0)) {
442	810x	pbb = pbb->prev;
443	2430x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->prev, block);
444	2025x	mask = pbb->mask;
445		}
446	36100x	n = N - 1 - hub_detail::unchecked_countl_zero(mask);
447	36100x	return *this;
448		}
449
450		BOOST_FORCEINLINE iterator operator--(int) noexcept
451		{
452	1368x	iterator tmp(*this);
453		this->operator--();
454	1368x	return tmp;
455		}
456
457	5258155x	friend bool operator==(const iterator& x, const iterator& y) noexcept
458		{
459	5348159x	return x.pbb == y.pbb && x.n == y.n;
460		}
461
462	5172678x	friend bool operator!=(const iterator& x, const iterator& y) noexcept
463		{
464	5172678x	return !(x == y);
465		}
466
467		private:
468		template<typename> friend class iterator;
469		template<typename, typename> friend class container::hub;
470
471		template<typename T>
472		using pointer_rebind_t = hub_detail::pointer_rebind_t<ValuePointer, T>;
473		using block_base = hub_detail::block_base<pointer_rebind_t<void>>;
474		using block_base_pointer = pointer_rebind_t<block_base>;
475		using const_block_base_pointer = pointer_rebind_t<const block_base>;
476		using nonconst_pointer = pointer_rebind_t<value_type>; /* used by Natvis */
477		using block = hub_detail::block<nonconst_pointer>;
478		using mask_type = typename block_base::mask_type;
479
480		static constexpr int N = block_base::N;
481		static constexpr mask_type full = block_base::full;
482
483	9965327x	iterator(const_block_base_pointer pbb_, int n_) noexcept:
484	9965327x	pbb{const_cast_block_base_pointer(pbb_)}, n{n_} {}
485
486	523x	iterator(const_block_base_pointer pbb_) noexcept:
487	523x	pbb{const_cast_block_base_pointer(pbb_)},
488	642x	n{hub_detail::unchecked_countr_zero(pbb->mask)}
489	523x	{}
490
491		static block_base_pointer
492	9965850x	const_cast_block_base_pointer(const_block_base_pointer pbb_) noexcept
493		{
494	9965850x	return block_base::pointer_to(const_cast<block_base&>(*pbb_));
495		}
496
497		block_base_pointer pbb = nullptr;
498		int n = 0;
499		};
500
501		template<typename T, std::size_t N>
502		struct sort_iterator
503		{
504		using value_type = T;
505		using difference_type = std::ptrdiff_t;
506		using pointer = T*;
507		using reference = T&;
508		using iterator_category = std::random_access_iterator_tag;
509
510	998663x	sort_iterator(T** pp_, std::size_t index_): pp{pp_}, index{index_} {}
511
512	131446458x	pointer operator->() const noexcept
513		{
514	131446458x	return pp[index / N] + (index % N);
515		}
516
517	131446458x	reference operator*() const noexcept
518		{
519	131446458x	return *operator->();
520		}
521
522	24379312x	sort_iterator& operator++() noexcept
523		{
524	24379312x	++index;
525	24379312x	return *this;
526		}
527
528		sort_iterator operator++(int) noexcept
529		{
530		sort_iterator tmp(*this);
531		++index;
532		return tmp;
533		}
534
535	29888125x	sort_iterator& operator--() noexcept
536		{
537	29888125x	--index;
538	29888125x	return *this;
539		}
540
541		sort_iterator operator--(int) noexcept
542		{
543		sort_iterator tmp(*this);
544		--index;
545		return tmp;
546		}
547
548		friend difference_type
549	748998x	operator-(const sort_iterator& x, const sort_iterator& y) noexcept
550		{
551	748998x	return (difference_type)(x.index - y.index);
552		}
553
554		sort_iterator& operator+=(difference_type n) noexcept
555		{
556		index += n;
557		return *this;
558		}
559
560		friend sort_iterator
561	748998x	operator+(const sort_iterator& x, difference_type n) noexcept
562		{
563	748998x	return {x.pp, x.index + n};
564		}
565
566		friend sort_iterator
567		operator+(difference_type n, const sort_iterator& x) noexcept
568		{
569		return {x.pp, n + x.index};
570		}
571
572		sort_iterator& operator-=(difference_type n) noexcept
573		{
574		index -= n;
575		return *this;
576		}
577
578		friend sort_iterator
579	249649x	operator-(const sort_iterator& x, difference_type n) noexcept
580		{
581	249649x	return {x.pp, x.index - n};
582		}
583
584		reference operator[](difference_type n) const noexcept
585		{
586		return operator(this + n);
587		}
588
589		friend bool
590	8x	operator==(const sort_iterator& x, const sort_iterator& y) noexcept
591		{
592	8x	return x.index == y.index;
593		}
594
595		friend bool
596	2400528x	operator!=(const sort_iterator& x, const sort_iterator& y) noexcept
597		{
598	2400528x	return x.index != y.index;
599		}
600
601		friend bool
602	8543092x	operator<(const sort_iterator& x, const sort_iterator& y) noexcept
603		{
604	8543092x	return x.index < y.index;
605		}
606
607		friend bool
608		operator>(const sort_iterator& x, const sort_iterator& y) noexcept
609		{
610		return x.index > y.index;
611		}
612
613		friend bool
614		operator<=(const sort_iterator& x, const sort_iterator& y) noexcept
615		{
616		return x.index <= y.index;
617		}
618
619		friend bool
620		operator>=(const sort_iterator& x, const sort_iterator& y) noexcept
621		{
622		return x.index >= y.index;
623		}
624
625		T** pp;
626		std::size_t index;
627		};
628
629		template<typename T, typename Allocator>
630		struct buffer
631		{
632	29x	buffer(std::size_t n, Allocator al_): al{al_}
633		{
634	29x	data = static_cast<T>(::operator new[](n sizeof(T), std::nothrow));
635	29x	if(data) capacity = n;
636	29x	}
637
638	29x	~buffer()
639		{
640	29x	if(data) {
641	29x	for(; begin_ != end_; ++begin_) allocator_destroy(al, begin());
642	29x	::operator delete[](data);
643		}
644	29x	}
645
646	4824835x	T* begin() const noexcept { return data + begin_; }
647	2412432x	T* end() const noexcept { return data + end_; }
648
649		template<typename... Args>
650	2412403x	void emplace_back(Args&&... args)
651		{
652	2412403x	BOOST_ASSERT(data && end_ != capacity);
653	2412403x	allocator_construct(al, end(), std::forward<Args>(args)...);
654	2412403x	++end_;
655	2412403x	}
656
657	2412403x	void erase_front() noexcept
658		{
659	2412403x	BOOST_ASSERT(data && begin_ != end_);
660	2412403x	allocator_destroy(al, begin());
661	2412403x	++begin_;
662	2412403x	}
663
664		Allocator al;
665		std::size_t begin_ = 0, end_ = 0;
666		std::size_t capacity = 0;
667		T* data = nullptr;
668		};
669
670		template<typename T>
671		struct nodtor_deleter
672		{
673		using pointer = T*;
674		void operator()(pointer p) noexcept { ::operator delete(p); }
675		};
676
677		template<typename T>
678		struct nodtor_deleter<T[]>
679		{
680		using pointer = T*;
681	16x	void operator()(pointer p) noexcept { ::operator delete[](p); }
682		};
683
684		template<typename T>
685		using nodtor_unique_ptr = std::unique_ptr<T, nodtor_deleter<T>>;
686
687		template<typename T>
688		struct type_identity { using type = T; };
689
690		template<typename T>
691		using type_identity_t = typename type_identity<T>::type;
692
693		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
694		template<class R, class T>
695		concept container_compatible_range =
696		std::ranges::input_range<R> &&
697		std::convertible_to<std::ranges::range_reference_t<R>, T>;
698
699		/* Use own from_range_t only if std::from_range_t does not exist.
700		* Technique explained at
701		https://bannalia.blogspot.com/2016/09/compile-time-checking-existence-of.html
702		*/
703
704		struct from_range_t{ explicit from_range_t() = default; };
705		struct from_range_t_hook{};
706
707		} /* namespace hub_detail */
708		} /* namespace container */
709		} /* namespace boost */
710
711		namespace std {
712
713		template<> struct hash< ::boost::container::hub_detail::from_range_t_hook>
714		{
715		using from_range_t_type = decltype([] {
716		using namespace ::boost::container::hub_detail;
717		return from_range_t{};
718		}());
719
720		/* make standard happy */
721		std::size_t operator()(
722		const ::boost::container::hub_detail::from_range_t_hook&) const;
723		};
724
725		}
726
727		namespace boost {
728		namespace container {
729
730		/* TODO: this may collide with other same-named entities in different
731		* parts of Boost.Container.
732		*/
733		using from_range_t =
734		typename std::hash<hub_detail::from_range_t_hook>::from_range_t_type;
735		inline constexpr from_range_t from_range {};
736
737		namespace hub_detail {
738		#endif
739
740		template<typename InputIterator>
741		using enable_if_is_input_iterator_t =
742		typename std::enable_if<
743		std::is_convertible<
744		typename std::iterator_traits<InputIterator>::iterator_category,
745		std::input_iterator_tag
746		>::value
747		>::type;
748
749		/* std::pmr::polymorphic_allocator::destroy may be marked as deprecated.
750		* C&P from boost/core/allocator_access.hpp.
751		*/
752		#if defined(_LIBCPP_SUPPRESS_DEPRECATED_PUSH)
753		_LIBCPP_SUPPRESS_DEPRECATED_PUSH
754		#endif
755		#if defined(_STL_DISABLE_DEPRECATED_WARNING)
756		_STL_DISABLE_DEPRECATED_WARNING
757		#endif
758		#if defined(__clang__) && defined(__has_warning)
759		# if __has_warning("-Wdeprecated-declarations")
760		# pragma clang diagnostic push
761		# pragma clang diagnostic ignored "-Wdeprecated-declarations"
762		# endif
763		#elif defined(_MSC_VER)
764		# pragma warning(push)
765		# pragma warning(disable: 4996)
766		#elif defined(BOOST_GCC) && BOOST_GCC >= 40600
767		# pragma GCC diagnostic push
768		# pragma GCC diagnostic ignored "-Wdeprecated-declarations"
769		#endif
770
771		template<typename Allocator, typename Ptr, typename = void>
772		struct allocator_has_destroy: std::false_type {};
773
774		template<typename Allocator, typename Ptr>
775		struct allocator_has_destroy<
776		Allocator, Ptr,
777		decltype((void)std::declval<Allocator&>().destroy(std::declval<Ptr>()))
778		>: std::true_type {};
779
780		#if defined(__clang__) && defined(__has_warning)
781		# if __has_warning("-Wdeprecated-declarations")
782		# pragma clang diagnostic pop
783		# endif
784		#elif defined(_MSC_VER)
785		# pragma warning(pop)
786		#elif defined(BOOST_GCC) && BOOST_GCC >= 40600
787		# pragma GCC diagnostic pop
788		#endif
789		#if defined(_STL_RESTORE_DEPRECATED_WARNING)
790		_STL_RESTORE_DEPRECATED_WARNING
791		#endif
792		#if defined(_LIBCPP_SUPPRESS_DEPRECATED_POP)
793		_LIBCPP_SUPPRESS_DEPRECATED_POP
794		#endif
795
796		template<typename Allocator>
797		struct is_std_allocator: std::false_type {};
798
799		template<typename T>
800		struct is_std_allocator<std::allocator<T>>: std::true_type {};
801
802		template<typename Allocator>
803		struct is_std_pmr_polymorphic_allocator: std::false_type {};
804
805		#ifndef BOOST_NO_CXX17_HDR_MEMORY_RESOURCE
806		template<typename T>
807		struct is_std_pmr_polymorphic_allocator<std::pmr::polymorphic_allocator<T>>:
808		std::true_type {};
809		#endif
810
811		struct if_constexpr_void_else{ void operator()() const {} };
812
813		template<typename F, typename G = if_constexpr_void_else>
814	2x	void if_constexpr(std::true_type, F f, G = G{}) { f(); }
815
816		template<typename F, typename G>
817	19x	void if_constexpr(std::false_type, F, G g) { g(); }
818
819		template<typename T>
820	2x	void copy_assign_if(std::true_type, T& x, const T& y) { x = y; }
821
822		template<typename T>
823	6x	void copy_assign_if(std::false_type, T&, const T&) {}
824
825		template<typename T>
826	6x	void move_assign_if(std::true_type, T& x, T& y) { x = std::move(y); }
827
828		template<typename T>
829	3x	void move_assign_if(std::false_type, T&, T&) {}
830
831		template<typename T>
832	2x	void swap_if(std::true_type, T& x, T& y) { using std::swap; swap(x, y); }
833
834		template<typename T>
835		void swap_if(std::false_type, T&, T&) {}
836
837		template<typename Allocator>
838		struct block_typedefs
839		{
840		using pointer = allocator_pointer_t<Allocator>;
841		template<typename Q>
842		using pointer_rebind_t = hub_detail::pointer_rebind_t<pointer, Q>;
843
844		using block_base = hub_detail::block_base<pointer_rebind_t<void>>;
845		using block_base_pointer = pointer_rebind_t<block_base>;
846		using const_block_base_pointer = pointer_rebind_t<const block_base>;
847		using block = hub_detail::block<pointer>;
848		using block_pointer = pointer_rebind_t<block>;
849		using block_allocator = allocator_rebind_t<Allocator,block>;
850		using block_list = hub_detail::block_list<pointer>;
851		};
852
853		} /* namespace container::hub_detail */
854
855		template<typename T, typename Allocator>
856		class hub: empty_value<
857		typename hub_detail::block_typedefs<Allocator>::block_allocator, 0>
858		{
859		static_assert(
860		!std::is_const<T>::value && !std::is_volatile<T>::value &&
861		!std::is_function<T>::value && !std::is_reference<T>::value &&
862		!std::is_void<T>::value,
863		"T must be a cv-unqualified object type");
864		static_assert(
865		std::is_same<T, allocator_value_type_t<Allocator>>::value,
866		"Allocator's value_type must be the same type as T");
867
868		public:
869		using value_type = T;
870		using allocator_type = Allocator;
871		using pointer = allocator_pointer_t<Allocator>;
872		using const_pointer = allocator_const_pointer_t<Allocator>;
873		using reference = T&;
874		using const_reference = const T&;
875		using size_type = allocator_size_type_t<Allocator>;
876		using difference_type = allocator_difference_type_t<Allocator>;
877		using iterator = hub_detail::iterator<pointer>;
878		using const_iterator = hub_detail::iterator<const_pointer>;
879		using reverse_iterator = std::reverse_iterator<iterator>;
880		using const_reverse_iterator = std::reverse_iterator<const_iterator>;
881
882	95x	hub() noexcept(noexcept(Allocator())): hub{Allocator()} {}
883
884	318x	explicit hub(const Allocator& al_) noexcept:
885	318x	allocator_base{empty_init, al_} {}
886
887	20x	explicit hub(size_type n, const Allocator& al_ = Allocator()): hub{al_}
888		{
889	20x	range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
890		allocator_construct(al(), p);
891		});
892	20x	}
893
894	21x	hub(size_type n, const T& x, const Allocator& al_ = Allocator()): hub{al_}
895		{
896	21x	insert(n, x);
897	21x	}
898
899		template<
900		typename InputIterator,
901		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
902		>
903	156x	hub(
904		InputIterator first, InputIterator last,
905	156x	const Allocator& al_ = Allocator()): hub{al_}
906		{
907	156x	insert(first, last);
908	156x	}
909
910		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
911		template<hub_detail::container_compatible_range<T> R>
912	10x	hub(from_range_t, R&& rg, const Allocator& al_ = Allocator()): hub{al_}
913		{
914	10x	insert_range(std::forward<R>(rg));
915	10x	}
916		#endif
917
918	24x	hub(const hub& x):
919	48x	hub{x, allocator_select_on_container_copy_construction(x.al())} {}
920
921	28x	hub(const hub& x, const hub_detail::type_identity_t<Allocator>& al_):
922	28x	hub(x.begin(), x.end(), al_) {}
923
924	6x	hub(hub&& x) noexcept:
925	10x	hub{std::move(x), Allocator(std::move(x.al())), std::true_type{}} {}
926
927	8x	hub(hub&& x, const hub_detail::type_identity_t<Allocator>& al_):
928	8x	hub{std::move(x), al_, allocator_is_always_equal_t<Allocator>{}} {}
929
930	10x	hub(std::initializer_list<T> il, const Allocator& al_ = Allocator()):
931	10x	hub{il.begin(), il.end(), al_} {}
932
933	326x	~hub() { reset(); }
934
935	8x	hub& operator=(const hub& x)
936		{
937		using pocca =
938		allocator_propagate_on_container_copy_assignment_t<Allocator>;
939
940	8x	if(this != &x) {
941	10x	if(al() != x.al() && pocca::value) {
942	1x	reset();
943	1x	hub_detail::copy_assign_if(pocca{}, al(), x.al());
944	1x	insert(x.begin(), x.end());
945		}
946		else{
947	7x	hub_detail::copy_assign_if(pocca{}, al(), x.al());
948	7x	assign(x.begin(), x.end());
949		}
950		}
951	8x	return *this;
952		}
953
954	10x	hub& operator=(hub&& x)
955		noexcept(
956		allocator_propagate_on_container_move_assignment_t<Allocator>::value \|\|
957		allocator_is_always_equal_t<Allocator>::value)
958		{
959	10x	if(this != &x) {
960	10x	move_assign(
961		x,
962		std::integral_constant<
963		bool,
964		allocator_propagate_on_container_move_assignment_t<Allocator>::
965		value \|\|
966		allocator_is_always_equal_t<Allocator>::value>{});
967		}
968	10x	return *this;
969		}
970
971	4x	hub& operator=(std::initializer_list<T> il)
972		{
973	4x	assign(il);
974	4x	return *this;
975		}
976
977		template<
978		typename InputIterator,
979		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
980		>
981	19x	void assign(InputIterator first, InputIterator last)
982		{
983	19x	range_assign_impl(
984		first, last,
985		[this] (T* p, InputIterator it) { allocator_construct(al(), p, *it); },
986		[] (T* p, InputIterator it) { p = it; });
987	19x	}
988
989		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
990		template<hub_detail::container_compatible_range<T> R>
991	4x	void assign_range(R&& rg)
992		{
993	4x	range_assign_impl(
994		std::ranges::begin(rg), std::ranges::end(rg),
995		[this] (T* p, auto it) { allocator_construct(al(), p, *it); },
996		[] (T* p, auto it) { p = it; });
997	4x	}
998		#endif
999
1000	20x	void assign(size_type n, const T& x)
1001		{
1002	20x	range_assign_impl(
1003		size_type(0), n,
1004		[&, this] (T* p, size_type) { allocator_construct(al(), p, x); },
1005		[&] (T* p, size_type) { *p = x; });
1006	20x	}
1007
1008	8x	void assign(std::initializer_list<T> il) { assign(il.begin(), il.end()); }
1009
1010	64x	allocator_type get_allocator() const noexcept { return al(); }
1011
1012	2560x	iterator begin() noexcept { return ++end(); }
1013	2656x	const_iterator begin() const noexcept { return ++end(); }
1014	19443x	iterator end() noexcept { return {blist.header(), 0}; }
1015	3427x	const_iterator end() const noexcept { return {blist.header(), 0}; }
1016	8x	reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
1017	12x	const_reverse_iterator rbegin() const noexcept
1018	12x	{ return const_reverse_iterator{end()}; }
1019	8x	reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
1020	12x	const_reverse_iterator rend() const noexcept
1021	12x	{ return const_reverse_iterator{begin()}; }
1022	1074x	const_iterator cbegin() const noexcept { return begin(); }
1023	1201x	const_iterator cend() const noexcept { return end(); }
1024	4x	const_reverse_iterator crbegin() const noexcept { return rbegin(); }
1025	4x	const_reverse_iterator crend() const noexcept { return rend(); }
1026
1027	48x	bool empty() const noexcept { return size_ == 0; }
1028	1322x	size_type size() const noexcept { return size_; }
1029
1030	32x	size_type max_size() const noexcept
1031		{
1032		std::size_t
1033	32x	bs = (std::size_t)allocator_max_size(al()) * sizeof(block),
1034	50x	vs = (std::size_t)allocator_max_size(Allocator(al())) * sizeof(T);
1035		return
1036	32x	(size_type)((std::min)(bs, vs) / (sizeof(block) + sizeof(T) * N) * N);
1037		}
1038
1039	442x	size_type capacity() const noexcept { return num_blocks * N; }
1040
1041		size_type memory() const noexcept // TODO: remove
1042		{
1043		return num_blocks * (sizeof(block) + sizeof(T) * N);
1044		}
1045
1046	20x	void reserve(size_type n)
1047		{
1048	20x	if(n > max_size()) {
1049	8x	BOOST_THROW_EXCEPTION(
1050		std::length_error("Requested capacity greater than max_size()"));
1051		}
1052	188x	while(capacity() < n) (void)create_new_available_block();
1053	16x	}
1054
1055	8x	void shrink_to_fit()
1056		{
1057	8x	compact();
1058	8x	trim_capacity();
1059	8x	}
1060
1061	14x	void trim_capacity() noexcept { trim_capacity(0); }
1062
1063	20x	void trim_capacity(size_type n) noexcept
1064		{
1065		/* Linear on # available blocks, std::hive is linear on # _reserved_
1066		* blocks.
1067		*/
1068	20x	if(capacity() <= n) return;
1069	26x	for(auto pbb = blist.header()->next_available;
1070	231x	capacity() - n >= N && pbb != blist.header(); ) {
1071	178x	auto pb = static_cast_block_pointer(pbb);
1072	178x	pbb = pbb-> next_available;
1073	178x	if(pb->mask == 0) {
1074	174x	blist.unlink_available(pb);
1075	146x	delete_block(pb);
1076	146x	--num_blocks;
1077		}
1078		}
1079		}
1080
1081		template<typename... Args>
1082		BOOST_FORCEINLINE iterator emplace(Args&&... args)
1083		{
1084		int n;
1085	9934242x	auto pb = retrieve_available_block(n);
1086	19870120x	allocator_construct(
1087	9934651x	al(), boost::to_address(pb->data() + n), std::forward<Args>(args)...);
1088	9933424x	auto mask_plus_one = (pb->mask \|= pb->mask + 1) + 1;
1089	9934651x	if(BOOST_UNLIKELY(mask_plus_one <= 2)) {
1090		/* pb->mask == 0 (impossible), 1 or full */
1091	310477x	if(mask_plus_one == 0) blist.unlink_available(pb);
1092	155268x	else /* pb->mask == 1 */ blist.link_at_back(pb);
1093		}
1094	9933424x	++size_;
1095	9934651x	return {pb, n};
1096		}
1097
1098		template<typename... Args>
1099		BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
1100		{
1101	14x	return emplace(std::forward<Args>(args)...);
1102		}
1103
1104	1604x	BOOST_FORCEINLINE iterator insert(const T& x) { return emplace(x); }
1105		BOOST_FORCEINLINE iterator insert(const_iterator, const T& x)
1106	4x	{ return emplace(x); }
1107	19866036x	BOOST_FORCEINLINE iterator insert(T&& x) { return emplace(std::move(x)); }
1108		BOOST_FORCEINLINE iterator insert(const_iterator, T&& x)
1109	8x	{ return emplace(std::move(x)); }
1110
1111	4x	void insert(std::initializer_list<T> il) { insert(il.begin(), il.end()); }
1112
1113		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1114		template<hub_detail::container_compatible_range<T> R>
1115	18x	void insert_range(R&& rg)
1116		{
1117	18x	range_insert_impl(
1118		std::ranges::begin(rg), std::ranges::end(rg),
1119		[this] (T* p, auto it) { allocator_construct(al(), p, *it); });
1120	18x	}
1121		#endif
1122
1123		template<
1124		typename InputIterator,
1125		typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
1126		>
1127	191x	void insert(InputIterator first, InputIterator last)
1128		{
1129	191x	range_insert_impl(first, last, [this] (T* p, InputIterator it) {
1130		allocator_construct(al(), p, *it);
1131		});
1132	191x	}
1133
1134	21x	void insert(size_type n, const T& x)
1135		{
1136	21x	range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
1137	10x	allocator_construct(al(), p, x);
1138		});
1139	21x	}
1140
1141		BOOST_FORCEINLINE iterator erase(const_iterator pos)
1142		{
1143	1414x	auto pbb = pos.pbb;
1144	3022x	auto n = pos.n;
1145		++pos;
1146	536x	erase_impl(pbb, n);
1147	3558x	return {pos.pbb, pos.n};
1148		}
1149
1150		BOOST_FORCEINLINE void erase_void(const_iterator pos)
1151		{
1152		erase_impl(pos.pbb, pos.n);
1153		}
1154
1155	1233x	iterator erase(const_iterator first, const_iterator last)
1156		{
1157	3245x	for(auto pbb = first.pbb; first != last; ) {
1158	2157x	first = erase(first);
1159	2157x	if(first.pbb != pbb) break;
1160		}
1161	1233x	auto pbb = first.pbb;
1162	1440x	if(pbb != last.pbb){
1163		do {
1164	29x	auto pb = static_cast_block_pointer(pbb);
1165	29x	pbb = pb->next;
1166	29x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1167	29x	size_ -= destroy_all_in_nonempty_block(pb);
1168	5x	blist.unlink(pb);
1169	32x	if(BOOST_UNLIKELY(pb->mask == full)) blist.link_available_at_front(pb);
1170	29x	pb->mask = 0;
1171	34x	} while(pbb != last.pbb);
1172	11x	first = {pbb};
1173		}
1174	1243x	while(first != last) first = erase(first);
1175	1440x	return {last.pbb, last.n};
1176		}
1177
1178	21x	void swap(hub& x)
1179		noexcept(
1180		allocator_propagate_on_container_swap_t<Allocator>::value \|\|
1181		allocator_is_always_equal_t<Allocator>::value)
1182		{
1183		using pocs = allocator_propagate_on_container_swap_t<Allocator>;
1184
1185	21x	hub_detail::if_constexpr(pocs{}, [&, this]{
1186		hub_detail::swap_if(pocs{}, al(), x.al());
1187		},
1188		[&, this]{ /* else */
1189		BOOST_ASSERT(al() == x.al());
1190		(void)this;
1191		});
1192	21x	std::swap(blist, x.blist);
1193	21x	std::swap(num_blocks, x.num_blocks);
1194	21x	std::swap(size_, x.size_);
1195	21x	}
1196
1197	8x	void clear() noexcept { erase(begin(), end()); }
1198
1199	12x	void splice(hub& x)
1200		{
1201	12x	BOOST_ASSERT(this != &x);
1202	20x	BOOST_ASSERT(al() == x.al());
1203	90x	for(auto pbb = x.blist.header()->next; pbb != x.blist.header(); ) {
1204	60x	auto pb = static_cast_block_pointer(pbb);
1205	60x	pbb = pbb->next;
1206	60x	if(pb->mask != full) {
1207	18x	x.blist.unlink_available(pb);
1208	21x	blist.link_available_at_front(pb);
1209		}
1210	12x	x.blist.unlink(pb);
1211	60x	blist.link_at_back(pb);
1212	60x	--x.num_blocks;
1213	60x	++num_blocks;
1214	60x	auto s = core::popcount(pb->mask);
1215	60x	x.size_ -= s;
1216	60x	size_ += s;
1217		}
1218	12x	}
1219
1220	6x	void splice(hub&& x) { splice(x); }
1221
1222		template<typename BinaryPredicate = std::equal_to<T>>
1223	6x	size_type unique(BinaryPredicate pred = BinaryPredicate())
1224		{
1225	6x	auto s = size_;
1226	1206x	for(auto first = cbegin(), last = cend(); first != last; ) {
1227	1200x	auto next = std::next(first);
1228	1200x	first = erase(
1229		next,
1230		std::find_if_not(next, last, [&] (const T& x) {
1231		return pred(x, *first);
1232		}));
1233		}
1234	6x	return (size_type)(s - size_);
1235		}
1236
1237		template<typename Compare = std::less<T>>
1238	47x	void sort(Compare comp = Compare())
1239		{
1240		/* transfer_sort is usually the fastest, but it consumes the most
1241		* auxiliary memory when sizeof(T) > sizeof(sort_proxy), so we restrict
1242		* its usage to the case sizeof(T) <= sizeof(sort_proxy).
1243		* compact_sort uses the least amount of auxiliary memory (by far), and
1244		* it's also faster than proxy_sort when the auxiliary memory of the latter
1245		* exceeds some threshold seemingly related to the size of the L2 cache;
1246		* we conventionally set the threshold to 2MB for lack of a more precise
1247		* estimation mechanism.
1248		* TODO: In 32-bit mode, the threshold policy is not so clear-cut and the
1249		* cost of moving elements around seems to play a role.
1250		*/
1251		BOOST_IF_CONSTEXPR(sizeof(T) <= sizeof(sort_proxy)) {
1252	29x	if(transfer_sort(comp)) return;
1253		}
1254		else{
1255		static constexpr std::size_t memory_threshold = 2 * 1024 * 1024;
1256	18x	if((std::size_t)size_ * sizeof(sort_proxy) <= memory_threshold) {
1257	10x	if(proxy_sort(comp)) return;
1258		}
1259		}
1260	8x	compact_sort(comp);
1261		}
1262
1263	1600x	iterator get_iterator(const_pointer p) noexcept /* noexcept? */
1264		{
1265		std::less<const T*> less;
1266	4992x	for(auto pbb = blist.next; pbb != blist.header(); pbb = pbb-> next) {
1267	3328x	auto pb = static_cast_block_pointer(pbb);
1268	6464x	if(!less(boost::to_address(p), boost::to_address(pb->data())) &&
1269	4800x	less(boost::to_address(p), boost::to_address(pb->data() + N))) {
1270	2000x	return {pb, (int)(p - pb->data())};
1271		}
1272		}
1273	✗	return end(); /* shouldn't assert? */
1274		}
1275
1276	800x	const_iterator get_iterator(const_pointer p) const noexcept /* noexcept? */
1277		{
1278	800x	return const_cast<hub*>(this)->get_iterator(p);
1279		}
1280
1281		template<typename F>
1282	410x	void visit(iterator first, iterator last, F f)
1283		{
1284	410x	visit_while(first, last, [&] (value_type& x) {
1285		f(x);
1286		return true;
1287		});
1288	410x	}
1289
1290		template<typename F>
1291	344x	void visit(const_iterator first, const_iterator last, F f) const
1292		{
1293	344x	visit_while(first, last, [&] (const value_type& x) {
1294		f(x);
1295		return true;
1296		});
1297	344x	}
1298
1299		template<typename F>
1300	2138x	iterator visit_while(iterator first, iterator last, F f)
1301		{
1302	56860x	for(auto pbb = first.pbb; first != last; ) {
1303	56152x	if(!f(*first)) return first;
1304		++first;
1305	69082x	if(first.pbb != pbb) break;
1306		}
1307	2110x	if(first.pbb != last.pbb) {
1308	2132x	first = visit_while_impl(first.pbb, last.pbb, f);
1309	1784x	if(first.pbb != last.pbb) return first;
1310		}
1311	12818x	for(; first != last; ++first) if(!f(*first)) return first;
1312	770x	return first;
1313		}
1314
1315		template<typename F>
1316	1036x	const_iterator visit_while(
1317		const_iterator first, const_iterator last, F f) const
1318		{
1319	1295x	auto it =const_cast<hub*>(this)->visit_while(
1320	1295x	iterator{first.pbb, first.n}, iterator{last.pbb, last.n},
1321		[&] (const value_type& x) { return f(x); });
1322	1036x	return {it.pbb, it.n};
1323		}
1324
1325		template<typename F>
1326	70x	void visit_all(F f)
1327		{
1328	70x	visit(begin(), end(), std::ref(f));
1329	70x	}
1330
1331		template<typename F>
1332	4x	void visit_all(F f) const
1333		{
1334	4x	visit(begin(), end(), std::ref(f));
1335	4x	}
1336
1337		template<typename F>
1338	4x	iterator visit_all_while(F f)
1339		{
1340	4x	return visit_while(begin(), end(), std::ref(f));
1341		}
1342
1343		template<typename F>
1344	4x	const_iterator visit_all_while(F f) const
1345		{
1346	4x	return visit_while(begin(), end(), std::ref(f));
1347		}
1348
1349		private:
1350		template<typename U, typename A, typename P>
1351		friend typename hub<U, A>::size_type erase_if(hub<U, A>&, P);
1352
1353		using block_typedefs = hub_detail::block_typedefs<Allocator>;
1354		using block_base = typename block_typedefs::block_base;
1355		using block_base_pointer = typename block_typedefs::block_base_pointer;
1356		using const_block_base_pointer =
1357		typename block_typedefs::const_block_base_pointer;
1358		using block = typename block_typedefs::block;
1359		using block_pointer = typename block_typedefs::block_pointer;
1360		using block_allocator = typename block_typedefs::block_allocator;
1361		using block_list = typename block_typedefs::block_list;
1362		using allocator_base = empty_value<block_allocator, 0>;
1363		using mask_type = typename block_base::mask_type;
1364
1365		static constexpr int N = block_base::N;
1366		static constexpr mask_type full = block_base::full;
1367
1368	20550957x	block_allocator& al() noexcept { return allocator_base::get(); }
1369	166x	const block_allocator& al() const noexcept { return allocator_base::get(); }
1370
1371		struct reset_on_exit
1372		{
1373	5x	~reset_on_exit() { x.reset(); }
1374
1375		hub& x;
1376		};
1377
1378	8x	hub(
1379		hub&& x, const Allocator& al_, std::true_type /* equal allocs */) noexcept:
1380	8x	allocator_base{empty_init, al_}, blist{std::move(x.blist)},
1381	8x	num_blocks{x.num_blocks}, size_{x.size_}
1382		{
1383	8x	x.num_blocks = 0;
1384	8x	x.size_ = 0;
1385	8x	}
1386
1387	6x	hub(
1388		hub&& x, const Allocator& al_, std::false_type /* maybe unequal allocs */):
1389	6x	hub{al_}
1390		{
1391	6x	if(al() == x.al()) {
1392	2x	blist = std::move(x.blist);
1393	2x	num_blocks = x.num_blocks;
1394	2x	size_ = x.size_;
1395	2x	x.num_blocks = 0;
1396	2x	x.size_ = 0;
1397		}
1398		else {
1399	4x	reset_on_exit on_exit{x}; (void)on_exit;
1400	4x	range_insert_impl(x.begin(), x.end(), [this] (T* p, iterator it) {
1401		allocator_construct(al(), p, std::move(*it));
1402		});
1403	4x	}
1404	6x	}
1405
1406	9x	void move_assign(hub& x, std::true_type /* transfer structure */)
1407		{
1408		using pocma =
1409		allocator_propagate_on_container_move_assignment_t<Allocator>;
1410
1411	9x	reset();
1412	9x	hub_detail::move_assign_if(pocma{}, al(), x.al());
1413	9x	blist = std::move(x.blist);
1414	9x	num_blocks = x.num_blocks;
1415	9x	size_ = x.size_;
1416	9x	x.num_blocks = 0;
1417	9x	x.size_ = 0;
1418	9x	}
1419
1420	3x	void move_assign(hub& x, std::false_type /* maybe move data */)
1421		{
1422	3x	if(al() == x.al()) {
1423	2x	move_assign(x, std::true_type{});
1424		}
1425		else {
1426	1x	reset_on_exit on_exit{x}; (void)on_exit;
1427	1x	range_assign_impl(
1428		x.begin(), x.end(),
1429	400x	[this] (T* p, iterator it)
1430	200x	{ allocator_construct(al(), p, std::move(*it)); },
1431	400x	[] (T* p, iterator it)
1432	200x	{ p = std::move(it); });
1433	1x	}
1434	3x	}
1435
1436		static block_pointer
1437	15624323x	static_cast_block_pointer(block_base_pointer pbb) noexcept
1438		{
1439	15624323x	return block_list::static_cast_block_pointer(pbb);
1440		}
1441
1442	156300x	block_pointer create_new_available_block()
1443		{
1444	156300x	auto pb = allocator_allocate(al(), 1);
1445	156300x	pb->mask = 0;
1446		BOOST_TRY {
1447	156300x	allocator_rebind_t<Allocator, value_type> val(al());
1448	156492x	pb->data_ = allocator_allocate(val, N);
1449		}
1450	✗	BOOST_CATCH(...) {
1451	✗	allocator_deallocate(al(), pb, 1);
1452	✗	BOOST_RETHROW;
1453		}
1454		BOOST_CATCH_END
1455	156300x	blist.link_available_at_back(pb);
1456	156300x	++num_blocks;
1457	156300x	return pb;
1458		}
1459
1460	156300x	void delete_block(block_pointer pb) noexcept
1461		{
1462	156300x	allocator_rebind_t<Allocator, value_type> val(al());
1463	156300x	allocator_deallocate(val, pb->data(), N);
1464	156300x	allocator_deallocate(al(), pb, 1);
1465	156300x	}
1466
1467		BOOST_FORCEINLINE block_pointer retrieve_available_block(int& n)
1468		{
1469	9936138x	if(BOOST_LIKELY(blist.next_available != blist.header())){
1470	9779852x	auto pb = static_cast_block_pointer(blist.next_available);
1471	9779442x	n = hub_detail::unchecked_countr_one(pb->mask);
1472	9779032x	return pb;
1473		}
1474		else {
1475	156128x	n = 0;
1476	156128x	return create_new_available_block();
1477		}
1478		}
1479
1480	59422x	size_type destroy_all_in_nonempty_block(block_pointer pb) noexcept
1481		{
1482	59422x	BOOST_ASSERT(pb->mask != 0);
1483	59494x	return destroy_all_in_nonempty_block(pb, std::integral_constant<bool,
1484		std::is_trivially_destructible<T>::value &&
1485		( hub_detail::is_std_allocator<block_allocator>::value \|\|
1486		hub_detail::is_std_pmr_polymorphic_allocator<block_allocator>::value \|\|
1487	59422x	!hub_detail::allocator_has_destroy<block_allocator, T*>::value )>{});
1488		}
1489
1490	59180x	size_type destroy_all_in_nonempty_block(
1491		block_pointer pb, std::true_type /* trivial destruction */) noexcept
1492		{
1493	59180x	return (size_type)core::popcount(pb->mask);
1494		}
1495
1496	242x	size_type destroy_all_in_nonempty_block(
1497		block_pointer pb, std::false_type /* use allocator_destroy */) noexcept
1498		{
1499	242x	size_type s = 0;
1500	242x	auto mask = pb->mask;
1501		do {
1502	5181x	auto n = hub_detail::unchecked_countr_zero(mask);
1503	5181x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1504	5181x	++s;
1505	5181x	mask &= mask - 1;
1506	5181x	} while(mask);
1507	242x	return s;
1508		}
1509
1510	56876x	size_type destroy_all_in_full_block(block_pointer pb) noexcept
1511		{
1512	56876x	BOOST_ASSERT(pb->mask == full);
1513	3696940x	for(int n = 0; n < N; ++n) {
1514	3651328x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1515		}
1516	56876x	return (size_type)N;
1517		}
1518
1519	341x	void reset() noexcept
1520		{
1521	99807x	for(auto pbb = blist.next_available; pbb != blist.header(); ) {
1522	99278x	auto pb = static_cast_block_pointer(pbb);
1523	99278x	pbb = pb->next_available;
1524		BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1525	40079x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1526		}
1527	99278x	if(pb->mask != 0) {
1528	59393x	destroy_all_in_nonempty_block(pb);
1529	67x	blist.unlink(pb);
1530		}
1531	99278x	delete_block(pb);
1532		}
1533		/* full blocks remaining */
1534	57417x	for(auto pbb = blist.next; pbb != blist.header(); ) {
1535	56876x	BOOST_ASSERT(pbb->mask == full);
1536	56876x	auto pb = static_cast_block_pointer(pbb);
1537	56876x	pbb = pb->next;
1538		BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1539	37587x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1540		}
1541	56876x	destroy_all_in_full_block(pb);
1542	56876x	delete_block(pb);
1543		}
1544	341x	blist.reset();
1545	341x	num_blocks = 0;
1546	341x	size_ = 0;
1547	341x	}
1548
1549		BOOST_FORCEINLINE void erase_impl(block_base_pointer pbb, int n) noexcept
1550		{
1551	5119854x	auto pb = static_cast_block_pointer(pbb);
1552	5121128x	allocator_destroy(al(), boost::to_address(pb->data() + n));
1553	5119878x	if(BOOST_UNLIKELY(pb->mask == full)) blist.link_available_at_front(pb);
1554	5117943x	pb->mask &= ~((mask_type)(1) << n);
1555	5119860x	if(BOOST_UNLIKELY(pb->mask == 0)) blist.unlink(pb);
1556	5119854x	--size_;
1557	5119854x	}
1558
1559		template<typename Incrementable, typename Sentinel, typename Construct>
1560	287x	void range_insert_impl(
1561		Incrementable first, Sentinel last, Construct construct)
1562		{
1563	923x	while(first != last) {
1564		int n;
1565	760x	auto pb = retrieve_available_block(n);
1566		for(; ; ) {
1567	58548x	construct(boost::to_address(pb->data() + n), first++);
1568	43758x	++size_;
1569	43915x	if(BOOST_UNLIKELY(pb->mask == 0)) blist.link_at_back(pb);
1570	51153x	pb->mask \|= pb->mask +1;
1571	43758x	if(pb->mask == full){
1572	636x	blist.unlink_available(pb);
1573	636x	break;
1574		}
1575	43122x	else if(first == last) return;
1576	42839x	n = hub_detail::unchecked_countr_one(pb->mask);
1577		}
1578		}
1579		}
1580
1581		template<
1582		typename Incrementable, typename Sentinel,
1583		typename Construct, typename Insert
1584		>
1585	44x	void range_assign_impl(
1586		Incrementable first, Sentinel last, Construct construct, Insert insert)
1587		{
1588	44x	auto pbb = blist.next;
1589	44x	int n = -1;
1590	44x	if(first != last) {
1591		/* consume active blocks */
1592	92x	for(; pbb != blist.header(); pbb = pbb->next) {
1593	40x	auto pb = static_cast_block_pointer(pbb);
1594	40x	n = 0;
1595	2173x	for(mask_type bit = 1; bit; bit <<= 1, ++n) {
1596	2140x	if(pb->mask & bit) { /* full slot */
1597	2120x	insert(boost::to_address(pb->data() + n), first++);
1598		}
1599		else { /* empty slot */
1600	662x	construct(boost::to_address(pb->data() + n), first++);
1601	460x	++size_;
1602	460x	pb->mask \|= bit;
1603	463x	if(pb->mask == full) blist.unlink_available(pb);
1604		}
1605	2140x	if(first == last) goto exit;
1606		}
1607		}
1608	40x	exit: ;
1609		}
1610	44x	if(first != last) {
1611		/* all active blocks consumed, keep inserting */
1612	33x	range_insert_impl(first, last, construct);
1613		}
1614		else{
1615		/* erase remaining original elements */
1616	20x	auto it = (n == -1)? const_iterator{pbb}: ++const_iterator{pbb, n};
1617	11x	erase(it, cend());
1618		}
1619	44x	}
1620
1621		template<typename Compare>
1622	29x	bool transfer_sort(Compare comp)
1623		{
1624		/* transfer to a buffer, sort and transfer back */
1625	53x	hub_detail::buffer<T,Allocator> buf(size_, al());
1626	29x	if(!buf.data) return false;
1627
1628	39x	visit_all([&] (value_type& x) { buf.emplace_back(std::move(x)); });
1629	29x	std::sort(buf.begin(), buf.end(), comp);
1630	29x	visit_all([&] (value_type& x) {
1631	10x	x = std::move(*buf.begin());
1632	10x	buf.erase_front();
1633		});
1634	29x	return true;
1635	29x	}
1636
1637		struct sort_proxy
1638		{
1639		T* p;
1640		size_type n;
1641		};
1642
1643		template<typename Compare>
1644	10x	bool proxy_sort(Compare comp)
1645		{
1646		/* sort an array of (pointer, index) pairs and relocate according to it */
1647	10x	if(size_ > 1) {
1648	8x	hub_detail::nodtor_unique_ptr<sort_proxy[]> p
1649		{static_cast<sort_proxy*>(
1650	8x	::operator new[](size_ * sizeof(sort_proxy), std::nothrow))};
1651	8x	if(!p) return false;
1652
1653	8x	size_type i = 0;
1654	8x	visit_all([&] (value_type& x) {
1655		p[i] = {std::addressof(x), i};
1656		++i;
1657		});
1658
1659	8x	std::sort(
1660	8x	p.get(), p.get() + size_,
1661		[&] (const sort_proxy& x, const sort_proxy& y) {
1662		return comp(const_cast<const T&>(x.p), const_cast<const T&>(y.p));
1663		});
1664
1665	8x	i = 0;
1666	7888x	for(; i < size_; ++i) {
1667	7880x	if(p[i].n != i) {
1668	53x	T x = std::move(*(p[i].p));
1669	53x	auto j = i;
1670		do {
1671	7819x	auto k = p[j].n;
1672	7819x	(p[j].p) = std::move(p[k].p);
1673	7819x	p[j].n = j;
1674	7819x	j = k;
1675	7819x	} while(p[j].n != i);
1676	53x	*(p[j].p) = std::move(x);
1677	53x	p[j].n = j;
1678	53x	}
1679		}
1680	8x	}
1681	10x	return true;
1682		}
1683
1684		template<typename Compare>
1685	8x	void compact_sort(Compare comp)
1686		{
1687		/* compact elements and build an array of pointers to data chunks of N */
1688		using sort_iterator = hub_detail::sort_iterator<T, N>;
1689
1690	8x	if(size_ > 1) {
1691	8x	std::size_t n = (std::size_t)((size_ + N - 1) / N);
1692	8x	hub_detail::nodtor_unique_ptr<T*[]> p
1693	8x	{static_cast<T*>(::operator new[](n sizeof(T*)))};
1694	8x	std::size_t i = 0;
1695	8x	compact([&] (block_pointer pb) {
1696	✗	p[i++] = boost::to_address(pb->data());
1697		});
1698	8x	BOOST_ASSERT(i == n);
1699
1700	8x	std::sort(
1701		sort_iterator{p.get(), 0}, sort_iterator{p.get(), size_}, comp);
1702	8x	}
1703	8x	}
1704
1705	36x	void compact() { compact([] (block_pointer) {}); }
1706
1707		template<typename Track>
1708	16x	void compact(Track track)
1709		{
1710	29075x	for(auto pbbx = blist.next; pbbx != blist.header(); ) {
1711	29070x	auto pbx = static_cast_block_pointer(pbbx);
1712	29070x	auto pbby = pbbx->next;
1713	29070x	if(pbx->mask != full) {
1714		do{
1715	57734x	if(pbby->mask == full) {
1716		do {
1717	8470x	track(static_cast_block_pointer(pbby));
1718	8470x	pbby = pbby->next;
1719	8470x	} while(pbby->mask == full);
1720	✗	blist.unlink(pbx);
1721	14x	blist.link_before(pbx, static_cast_block_pointer(pbby));
1722		}
1723	57735x	if(pbby == blist.header()) {
1724	16x	compact(pbx);
1725	16x	track(pbx);
1726	16x	return;
1727		}
1728		else{
1729	57718x	auto pby = static_cast_block_pointer(pbby);
1730	57718x	compact(pbx,pby);
1731	57718x	if(pby->mask == 0) {
1732	39838x	pbby = pby->next;
1733	✗	blist.unlink(pby);
1734		}
1735		}
1736	57718x	}while(pbx->mask != full);
1737	18774x	blist.unlink_available(pbx);
1738		}
1739	29054x	track(pbx);
1740	29051x	pbbx = pbby;
1741		}
1742		}
1743
1744	57718x	void compact(block_pointer pbx, block_pointer pby)
1745		{
1746	57718x	auto cx = core::popcount(pbx->mask),
1747	57718x	cy = core::popcount(pby->mask);
1748	57718x	if(cx < cy) {
1749	17940x	std::swap(cx, cy);
1750	17940x	swap_payload(pbx, pby);
1751		}
1752	57718x	auto c = (std::min)(N - cx, cy);
1753	648532x	while(c--) {
1754	590814x	auto n = hub_detail::unchecked_countr_one(pbx->mask);
1755	590814x	auto m = N - 1 - hub_detail::unchecked_countl_zero(pby->mask);
1756	590814x	allocator_construct(
1757	590814x	al(), boost::to_address(pbx->data() + n), std::move(pby->data()[m]));
1758	590814x	allocator_destroy(al(), boost::to_address(pby->data() + m));
1759	590814x	pbx->mask \|= pbx->mask + 1;
1760	590814x	pby->mask &= ~((mask_type)(1) << m);
1761		}
1762	57718x	}
1763
1764	16x	void compact(block_pointer pb)
1765		{
1766	4x	for(; ; ) {
1767	20x	auto n = hub_detail::unchecked_countr_one(pb->mask);
1768	20x	auto m = N - 1 - hub_detail::unchecked_countl_zero(pb->mask);
1769	20x	if(n > m) return;
1770	4x	allocator_construct(
1771	4x	al(), boost::to_address(pb->data() + n), std::move(pb->data()[m]));
1772	4x	allocator_destroy(al(), boost::to_address(pb->data() + m));
1773	4x	pb->mask \|= pb->mask + 1;
1774	4x	pb->mask &= ~((mask_type)(1) << m);
1775		}
1776		}
1777
1778		template<typename F>
1779	1436x	iterator visit_while_impl(
1780		block_base_pointer pbb, block_base_pointer last_pbb, F&& f)
1781		{
1782	1436x	BOOST_ASSERT(pbb != last_pbb);
1783	1436x	auto pb = static_cast_block_pointer(pbb);
1784	1436x	auto mask = pb->mask;
1785	1436x	auto n = hub_detail::unchecked_countr_zero(mask);
1786	1436x	auto pd = pb->data();
1787		do {
1788	157098x	pbb = pb->next;
1789	157098x	auto next_mask = pbb->mask;
1790	157098x	auto next_n = hub_detail::unchecked_countr_zero(next_mask);
1791	157506x	auto next_pd = static_cast_block_pointer(pbb)->data();
1792	157506x	BOOST_CONTAINER_HUB_PREFETCH(next_pd + next_n);
1793	157098x	BOOST_CONTAINER_HUB_PREFETCH(pbb->next);
1794		for(; ; ) {
1795	4902006x	if(!f(pd[n])) return {pb, n};
1796	4885302x	mask &= mask - 1;
1797	4885302x	if(!mask) break;
1798	4729132x	n = hub_detail::unchecked_countr_zero(mask);
1799		}
1800	156170x	pb = static_cast_block_pointer(pbb);
1801	156170x	mask = next_mask;
1802	156170x	n = next_n;
1803	155994x	pd = next_pd;
1804	156170x	} while(pb != last_pbb);
1805	508x	return {last_pbb};
1806		}
1807
1808		block_list blist;
1809		size_type num_blocks = 0;
1810		size_type size_ = 0;
1811		};
1812
1813		#if !defined(BOOST_NO_CXX17_DEDUCTION_GUIDES)
1814		template<
1815		typename InputIterator,
1816		typename Allocator = std::allocator<
1817		typename std::iterator_traits<InputIterator>::value_type>
1818		>
1819		hub(InputIterator, InputIterator, Allocator = Allocator())
1820		-> hub<
1821		typename std::iterator_traits<InputIterator>::value_type, Allocator>;
1822
1823		#if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1824		template<
1825		std::ranges::input_range R,
1826		typename Allocator = std::allocator<std::ranges::range_value_t<R>>
1827		>
1828		hub(from_range_t, R&&, Allocator = Allocator())
1829		-> hub<std::ranges::range_value_t<R>, Allocator>;
1830		#endif
1831		#endif
1832
1833		template<typename T, typename Allocator>
1834	8x	void swap(hub<T, Allocator>& x, hub<T, Allocator>& y)
1835		noexcept(noexcept(x.swap(y)))
1836		{
1837	8x	x.swap(y);
1838	8x	}
1839
1840		template<typename T, typename Allocator, typename Predicate>
1841		typename hub<T, Allocator>::size_type
1842	54x	erase_if(hub<T, Allocator>& x, Predicate pred)
1843		{
1844		using hub_container = hub<T, Allocator>;
1845		using size_type = typename hub_container::size_type;
1846		using block = typename hub_container::block;
1847
1848	54x	auto s = x.size_;
1849	155332x	for(auto pbb = x.blist.next; pbb != x.blist.header(); ) {
1850	155262x	auto pb = x.static_cast_block_pointer(pbb);
1851	155262x	pbb = pb->next;
1852	155262x	BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1853	155262x	auto mask = pb->mask;
1854		do {
1855	9935010x	auto n = hub_detail::unchecked_countr_zero(mask);
1856	9935510x	if(pred(pb->data()[n])) x.erase_impl(pb, n);
1857	9935010x	mask &= mask - 1;
1858	9935010x	} while(mask);
1859		}
1860	54x	return (size_type)(s - x.size_);
1861		}
1862
1863		template<typename T, typename Allocator, typename U = T>
1864		typename hub<T, Allocator>::size_type
1865	8x	erase(hub<T, Allocator>& x, const U& value)
1866		{
1867	808x	return erase_if(x, [&](const T& v) -> bool { return v == value; });
1868		}
1869
1870		} /* namespace container */
1871
1872		} /* namespace boost */
1873
1874		#if defined(BOOST_MSVC)
1875		#pragma warning(pop) /* C4714 */
1876		#endif
1877
1878		#endif
1879