Index/libs / hub / include / boost / container / hub.hpp
Prev Index Next

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

99.0% Lines (676/683) 91.3% Functions (1192/1306)
libs/hub/include/boost/container/hub.hpp
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 30574994 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 30574994 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 10413115 inline int unchecked_countr_one(std::uint64_t x)
150 {
151 10413115 return unchecked_countr_zero(~x);
152 }
153
154 626934 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 626934 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 21616095 static pointer pointer_to(block_base& x) noexcept
183 {
184 21616095 return pointer_traits<pointer>::pointer_to(x);
185 }
186
187 3427 static const_pointer pointer_to(const block_base& x) noexcept
188 {
189 3427 return pointer_traits<const_pointer>::pointer_to(x);
190 }
191
192 BOOST_FORCEINLINE void link_available_before(pointer p) noexcept
193 {
194 155686 next_available = p;
195 155686 prev_available = p->prev_available;
196 156492 next_available->prev_available = pointer_to(*this);
197 156492 prev_available->next_available = pointer_to(*this);
198 156300 }
199
200 BOOST_FORCEINLINE void link_available_after(pointer p) noexcept
201 {
202 117687 prev_available = p;
203 117687 next_available = p->next_available;
204 117807 next_available->prev_available = pointer_to(*this);
205 117807 prev_available->next_available = pointer_to(*this);
206 117777 }
207
208 BOOST_FORCEINLINE void unlink_available() noexcept
209 {
210 174337 prev_available->next_available = next_available;
211 174483 next_available->prev_available = prev_available;
212 174337 }
213
214 BOOST_FORCEINLINE void link_before(pointer p) noexcept
215 {
216 155662 next = p;
217 155662 prev = p->prev;
218 156398 next->prev = pointer_to(*this);
219 156412 prev->next = pointer_to(*this);
220 156234 }
221
222 BOOST_FORCEINLINE void unlink() noexcept
223 {
224 99074 prev->next = next;
225 99164 next->prev = prev;
226 99074 }
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 41019428 ValuePointer data() noexcept { return data_; }
241 ValuePointer data_;
242 };
243
244 template<typename ValuePointer>
245 17940 void swap_payload(block<ValuePointer>& x, block<ValuePointer>& y) noexcept
246 {
247 17940 std::swap(x.mask, y.mask);
248 17940 std::swap(x.data_, y.data_);
249 17940 }
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 15624323 static_cast_block_pointer(block_base_pointer pbb) noexcept
270 {
271 15621282 return pointer_traits<block_pointer>::pointer_to(
272 15624323 static_cast<block&>(*pbb));
273 }
274
275 347 block_list()
276 59 {
277 347 reset();
278 347 mask = 1; /* sentinel */
279 347 data_ = nullptr;
280 347 }
281
282 29 block_list(block_list&& x) noexcept: block_list{}
283 {
284 34 if(x.next_available != x.header()) {
285 29 prev_available = x.prev_available;
286 29 next_available = x.next_available;
287 34 next_available->prev_available = header();
288 39 prev_available->next_available = header();
289 }
290 34 if(x.prev != x.header()) {
291 29 prev = x.prev;
292 29 next = x.next;
293 34 next->prev = header();
294 39 prev->next = header();
295 }
296 29 x.reset();
297 29 }
298
299 53 block_list& operator=(block_list&& x) noexcept
300 {
301 53 reset();
302 63 if(x.next_available != x.header()) {
303 45 prev_available = x.prev_available;
304 45 next_available = x.next_available;
305 53 next_available->prev_available = header();
306 61 prev_available->next_available = header();
307 }
308 63 if(x.prev != x.header()) {
309 45 prev = x.prev;
310 45 next = x.next;
311 53 next->prev = header();
312 61 prev->next = header();
313 }
314 53 x.reset();
315 53 return *this;
316 }
317
318 823 void reset() noexcept
319 {
320 823 prev_available = header();
321 823 next_available = header();
322 823 prev = header();
323 823 next = header();
324 823 }
325
326 10789623 block_base_pointer header() noexcept
327 {
328 10789623 return pointer_to(static_cast<block_base&>(*this));
329 }
330
331 3427 const_block_base_pointer header() const noexcept
332 {
333 3427 return pointer_to(static_cast<const block_base&>(*this));
334 }
335
336 BOOST_FORCEINLINE void link_at_back(block_pointer pb) noexcept
337 {
338 155648 pb->link_before(header());
339 156220 }
340
341 BOOST_FORCEINLINE void link_before(
342 block_pointer pbx, block_pointer pby) noexcept
343 {
344 14 pbx->link_before(pby);
345 14 }
346
347 BOOST_FORCEINLINE static void unlink(block_pointer pb) noexcept
348 {
349 59496 pb->unlink();
350 99358 }
351
352 BOOST_FORCEINLINE void link_available_at_back(block_pointer pb) noexcept
353 {
354 155686 pb->link_available_before(header());
355 156300 }
356
357 BOOST_FORCEINLINE void link_available_at_front(block_pointer pb) noexcept
358 {
359 117687 pb->link_available_after(header());
360 117777 }
361
362 BOOST_FORCEINLINE void unlink_available(block_pointer pb) noexcept
363 {
364 174337 pb->unlink_available();
365 174799 }
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 24417 iterator(const iterator&) = default;
389
390 template<
391 typename Value2Pointer,
392 typename = enable_if_consts_to_element_type_t<Value2Pointer>
393 >
394 3480 iterator(const iterator<Value2Pointer>& x) noexcept: pbb{x.pbb}, n{x.n} {}
395
396 2802 iterator& operator=(const iterator& x) = default;
397
398 template<
399 typename Value2Pointer,
400 typename = enable_if_consts_to_element_type_t<Value2Pointer>
401 >
402 3078 iterator& operator=(const iterator<Value2Pointer>& x) noexcept
403 {
404 3078 pbb = x.pbb;
405 3078 n = x.n;
406 3078 return *this;
407 }
408
409 9841711 pointer operator->() const noexcept
410 {
411 9930031 return static_cast<block&>(*pbb).data() + n;
412 }
413
414 9841637 reference operator*() const noexcept
415 {
416 9885779 return *operator->();
417 }
418
419 BOOST_FORCEINLINE iterator& operator++() noexcept
420 {
421 4955404 auto mask = pbb->mask & (full << 1 << n);
422 5323087 if(BOOST_UNLIKELY(mask == 0)) {
423 122688 pbb = pbb->next;
424 136496 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->next, block);
425 133057 mask = pbb->mask;
426 }
427 5333499 n = hub_detail::unchecked_countr_zero(mask);
428 5333499 return *this;
429 }
430
431 BOOST_FORCEINLINE iterator operator++(int) noexcept
432 {
433 9768 iterator tmp(*this);
434 this->operator++();
435 9768 return tmp;
436 }
437
438 BOOST_FORCEINLINE iterator& operator--() noexcept
439 {
440 9025 auto mask = pbb->mask & (full >> 1 >> (N - 1 - n));
441 35074 if(BOOST_UNLIKELY(mask == 0)) {
442 810 pbb = pbb->prev;
443 2430 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb->prev, block);
444 2025 mask = pbb->mask;
445 }
446 36100 n = N - 1 - hub_detail::unchecked_countl_zero(mask);
447 36100 return *this;
448 }
449
450 BOOST_FORCEINLINE iterator operator--(int) noexcept
451 {
452 1368 iterator tmp(*this);
453 this->operator--();
454 1368 return tmp;
455 }
456
457 5258155 friend bool operator==(const iterator& x, const iterator& y) noexcept
458 {
459 5348159 return x.pbb == y.pbb && x.n == y.n;
460 }
461
462 5172678 friend bool operator!=(const iterator& x, const iterator& y) noexcept
463 {
464 5172678 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 9965327 iterator(const_block_base_pointer pbb_, int n_) noexcept:
484 9965327 pbb{const_cast_block_base_pointer(pbb_)}, n{n_} {}
485
486 523 iterator(const_block_base_pointer pbb_) noexcept:
487 523 pbb{const_cast_block_base_pointer(pbb_)},
488 642 n{hub_detail::unchecked_countr_zero(pbb->mask)}
489 523 {}
490
491 static block_base_pointer
492 9965850 const_cast_block_base_pointer(const_block_base_pointer pbb_) noexcept
493 {
494 9965850 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 998663 sort_iterator(T** pp_, std::size_t index_): pp{pp_}, index{index_} {}
511
512 131446458 pointer operator->() const noexcept
513 {
514 131446458 return pp[index / N] + (index % N);
515 }
516
517 131446458 reference operator*() const noexcept
518 {
519 131446458 return *operator->();
520 }
521
522 24379312 sort_iterator& operator++() noexcept
523 {
524 24379312 ++index;
525 24379312 return *this;
526 }
527
528 sort_iterator operator++(int) noexcept
529 {
530 sort_iterator tmp(*this);
531 ++index;
532 return tmp;
533 }
534
535 29888125 sort_iterator& operator--() noexcept
536 {
537 29888125 --index;
538 29888125 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 748998 operator-(const sort_iterator& x, const sort_iterator& y) noexcept
550 {
551 748998 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 748998 operator+(const sort_iterator& x, difference_type n) noexcept
562 {
563 748998 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 249649 operator-(const sort_iterator& x, difference_type n) noexcept
580 {
581 249649 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 8 operator==(const sort_iterator& x, const sort_iterator& y) noexcept
591 {
592 8 return x.index == y.index;
593 }
594
595 friend bool
596 2400528 operator!=(const sort_iterator& x, const sort_iterator& y) noexcept
597 {
598 2400528 return x.index != y.index;
599 }
600
601 friend bool
602 8543092 operator<(const sort_iterator& x, const sort_iterator& y) noexcept
603 {
604 8543092 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 29 buffer(std::size_t n, Allocator al_): al{al_}
633 {
634 29 data = static_cast<T*>(::operator new[](n * sizeof(T), std::nothrow));
635 29 if(data) capacity = n;
636 29 }
637
638 29 ~buffer()
639 {
640 29 if(data) {
641 29 for(; begin_ != end_; ++begin_) allocator_destroy(al, begin());
642 29 ::operator delete[](data);
643 }
644 29 }
645
646 4824835 T* begin() const noexcept { return data + begin_; }
647 2412432 T* end() const noexcept { return data + end_; }
648
649 template<typename... Args>
650 2412403 void emplace_back(Args&&... args)
651 {
652 2412403 BOOST_ASSERT(data && end_ != capacity);
653 2412403 allocator_construct(al, end(), std::forward<Args>(args)...);
654 2412403 ++end_;
655 2412403 }
656
657 2412403 void erase_front() noexcept
658 {
659 2412403 BOOST_ASSERT(data && begin_ != end_);
660 2412403 allocator_destroy(al, begin());
661 2412403 ++begin_;
662 2412403 }
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 16 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 2 void if_constexpr(std::true_type, F f, G = G{}) { f(); }
815
816 template<typename F, typename G>
817 19 void if_constexpr(std::false_type, F, G g) { g(); }
818
819 template<typename T>
820 2 void copy_assign_if(std::true_type, T& x, const T& y) { x = y; }
821
822 template<typename T>
823 6 void copy_assign_if(std::false_type, T&, const T&) {}
824
825 template<typename T>
826 6 void move_assign_if(std::true_type, T& x, T& y) { x = std::move(y); }
827
828 template<typename T>
829 3 void move_assign_if(std::false_type, T&, T&) {}
830
831 template<typename T>
832 2 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 95 hub() noexcept(noexcept(Allocator())): hub{Allocator()} {}
883
884 318 explicit hub(const Allocator& al_) noexcept:
885 318 allocator_base{empty_init, al_} {}
886
887 20 explicit hub(size_type n, const Allocator& al_ = Allocator()): hub{al_}
888 {
889 20 range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
890 allocator_construct(al(), p);
891 });
892 20 }
893
894 21 hub(size_type n, const T& x, const Allocator& al_ = Allocator()): hub{al_}
895 {
896 21 insert(n, x);
897 21 }
898
899 template<
900 typename InputIterator,
901 typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
902 >
903 156 hub(
904 InputIterator first, InputIterator last,
905 156 const Allocator& al_ = Allocator()): hub{al_}
906 {
907 156 insert(first, last);
908 156 }
909
910 #if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
911 template<hub_detail::container_compatible_range<T> R>
912 10 hub(from_range_t, R&& rg, const Allocator& al_ = Allocator()): hub{al_}
913 {
914 10 insert_range(std::forward<R>(rg));
915 10 }
916 #endif
917
918 24 hub(const hub& x):
919 48 hub{x, allocator_select_on_container_copy_construction(x.al())} {}
920
921 28 hub(const hub& x, const hub_detail::type_identity_t<Allocator>& al_):
922 28 hub(x.begin(), x.end(), al_) {}
923
924 6 hub(hub&& x) noexcept:
925 10 hub{std::move(x), Allocator(std::move(x.al())), std::true_type{}} {}
926
927 8 hub(hub&& x, const hub_detail::type_identity_t<Allocator>& al_):
928 8 hub{std::move(x), al_, allocator_is_always_equal_t<Allocator>{}} {}
929
930 10 hub(std::initializer_list<T> il, const Allocator& al_ = Allocator()):
931 10 hub{il.begin(), il.end(), al_} {}
932
933 326 ~hub() { reset(); }
934
935 8 hub& operator=(const hub& x)
936 {
937 using pocca =
938 allocator_propagate_on_container_copy_assignment_t<Allocator>;
939
940 8 if(this != &x) {
941 10 if(al() != x.al() && pocca::value) {
942 1 reset();
943 1 hub_detail::copy_assign_if(pocca{}, al(), x.al());
944 1 insert(x.begin(), x.end());
945 }
946 else{
947 7 hub_detail::copy_assign_if(pocca{}, al(), x.al());
948 7 assign(x.begin(), x.end());
949 }
950 }
951 8 return *this;
952 }
953
954 10 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 10 if(this != &x) {
960 10 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 10 return *this;
969 }
970
971 4 hub& operator=(std::initializer_list<T> il)
972 {
973 4 assign(il);
974 4 return *this;
975 }
976
977 template<
978 typename InputIterator,
979 typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
980 >
981 19 void assign(InputIterator first, InputIterator last)
982 {
983 19 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 19 }
988
989 #if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
990 template<hub_detail::container_compatible_range<T> R>
991 4 void assign_range(R&& rg)
992 {
993 4 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 4 }
998 #endif
999
1000 20 void assign(size_type n, const T& x)
1001 {
1002 20 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 20 }
1007
1008 8 void assign(std::initializer_list<T> il) { assign(il.begin(), il.end()); }
1009
1010 64 allocator_type get_allocator() const noexcept { return al(); }
1011
1012 2560 iterator begin() noexcept { return ++end(); }
1013 2656 const_iterator begin() const noexcept { return ++end(); }
1014 19443 iterator end() noexcept { return {blist.header(), 0}; }
1015 3427 const_iterator end() const noexcept { return {blist.header(), 0}; }
1016 8 reverse_iterator rbegin() noexcept { return reverse_iterator{end()}; }
1017 12 const_reverse_iterator rbegin() const noexcept
1018 12 { return const_reverse_iterator{end()}; }
1019 8 reverse_iterator rend() noexcept { return reverse_iterator{begin()}; }
1020 12 const_reverse_iterator rend() const noexcept
1021 12 { return const_reverse_iterator{begin()}; }
1022 1074 const_iterator cbegin() const noexcept { return begin(); }
1023 1201 const_iterator cend() const noexcept { return end(); }
1024 4 const_reverse_iterator crbegin() const noexcept { return rbegin(); }
1025 4 const_reverse_iterator crend() const noexcept { return rend(); }
1026
1027 48 bool empty() const noexcept { return size_ == 0; }
1028 1322 size_type size() const noexcept { return size_; }
1029
1030 32 size_type max_size() const noexcept
1031 {
1032 std::size_t
1033 32 bs = (std::size_t)allocator_max_size(al()) * sizeof(block),
1034 50 vs = (std::size_t)allocator_max_size(Allocator(al())) * sizeof(T);
1035 return
1036 32 (size_type)((std::min)(bs, vs) / (sizeof(block) + sizeof(T) * N) * N);
1037 }
1038
1039 418 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 20 void reserve(size_type n)
1047 {
1048 20 if(n > max_size()) {
1049 8 BOOST_THROW_EXCEPTION(
1050 std::length_error("Requested capacity greater than max_size()"));
1051 }
1052 188 while(capacity() < n) (void)create_new_available_block();
1053 16 }
1054
1055 8 void shrink_to_fit()
1056 {
1057 8 compact();
1058 8 trim_capacity();
1059 8 }
1060
1061 14 void trim_capacity() noexcept { trim_capacity(0); }
1062
1063 20 void trim_capacity(size_type n) noexcept
1064 {
1065 /* Linear on # available blocks, std::hive is linear on # _reserved_
1066 * blocks.
1067 */
1068 26 for(auto pbb = blist.header()->next_available;
1069 231 capacity() > n && pbb != blist.header(); ) {
1070 178 auto pb = static_cast_block_pointer(pbb);
1071 178 pbb = pbb-> next_available;
1072 178 if(pb->mask == 0) {
1073 174 blist.unlink_available(pb);
1074 146 delete_block(pb);
1075 146 --num_blocks;
1076 }
1077 }
1078 20 }
1079
1080 template<typename... Args>
1081 BOOST_FORCEINLINE iterator emplace(Args&&... args)
1082 {
1083 int n;
1084 9934242 auto pb = retrieve_available_block(n);
1085 19870120 allocator_construct(
1086 9934651 al(), boost::to_address(pb->data() + n), std::forward<Args>(args)...);
1087 9933424 auto mask_plus_one = (pb->mask |= pb->mask + 1) + 1;
1088 9934651 if(BOOST_UNLIKELY(mask_plus_one <= 2)) {
1089 /* pb->mask == 0 (impossible), 1 or full */
1090 310477 if(mask_plus_one == 0) blist.unlink_available(pb);
1091 155268 else /* pb->mask == 1 */ blist.link_at_back(pb);
1092 }
1093 9933424 ++size_;
1094 9934651 return {pb, n};
1095 }
1096
1097 template<typename... Args>
1098 BOOST_FORCEINLINE iterator emplace_hint(const_iterator, Args&&... args)
1099 {
1100 14 return emplace(std::forward<Args>(args)...);
1101 }
1102
1103 1604 BOOST_FORCEINLINE iterator insert(const T& x) { return emplace(x); }
1104 BOOST_FORCEINLINE iterator insert(const_iterator, const T& x)
1105 4 { return emplace(x); }
1106 19866036 BOOST_FORCEINLINE iterator insert(T&& x) { return emplace(std::move(x)); }
1107 BOOST_FORCEINLINE iterator insert(const_iterator, T&& x)
1108 8 { return emplace(std::move(x)); }
1109
1110 4 void insert(std::initializer_list<T> il) { insert(il.begin(), il.end()); }
1111
1112 #if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1113 template<hub_detail::container_compatible_range<T> R>
1114 18 void insert_range(R&& rg)
1115 {
1116 18 range_insert_impl(
1117 std::ranges::begin(rg), std::ranges::end(rg),
1118 [this] (T* p, auto it) { allocator_construct(al(), p, *it); });
1119 18 }
1120 #endif
1121
1122 template<
1123 typename InputIterator,
1124 typename = hub_detail::enable_if_is_input_iterator_t<InputIterator>
1125 >
1126 191 void insert(InputIterator first, InputIterator last)
1127 {
1128 191 range_insert_impl(first, last, [this] (T* p, InputIterator it) {
1129 allocator_construct(al(), p, *it);
1130 });
1131 191 }
1132
1133 21 void insert(size_type n, const T& x)
1134 {
1135 21 range_insert_impl(size_type(0), n, [&, this] (T* p, size_type) {
1136 10 allocator_construct(al(), p, x);
1137 });
1138 21 }
1139
1140 BOOST_FORCEINLINE iterator erase(const_iterator pos)
1141 {
1142 1414 auto pbb = pos.pbb;
1143 3022 auto n = pos.n;
1144 ++pos;
1145 536 erase_impl(pbb, n);
1146 3558 return {pos.pbb, pos.n};
1147 }
1148
1149 BOOST_FORCEINLINE void erase_void(const_iterator pos)
1150 {
1151 erase_impl(pos.pbb, pos.n);
1152 }
1153
1154 1233 iterator erase(const_iterator first, const_iterator last)
1155 {
1156 3245 for(auto pbb = first.pbb; first != last; ) {
1157 2157 first = erase(first);
1158 2157 if(first.pbb != pbb) break;
1159 }
1160 1233 auto pbb = first.pbb;
1161 1440 if(pbb != last.pbb){
1162 do {
1163 29 auto pb = static_cast_block_pointer(pbb);
1164 29 pbb = pb->next;
1165 29 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1166 29 size_ -= destroy_all_in_nonempty_block(pb);
1167 5 blist.unlink(pb);
1168 32 if(BOOST_UNLIKELY(pb->mask == full)) blist.link_available_at_front(pb);
1169 29 pb->mask = 0;
1170 34 } while(pbb != last.pbb);
1171 11 first = {pbb};
1172 }
1173 1243 while(first != last) first = erase(first);
1174 1440 return {last.pbb, last.n};
1175 }
1176
1177 21 void swap(hub& x)
1178 noexcept(
1179 allocator_propagate_on_container_swap_t<Allocator>::value ||
1180 allocator_is_always_equal_t<Allocator>::value)
1181 {
1182 using pocs = allocator_propagate_on_container_swap_t<Allocator>;
1183
1184 21 hub_detail::if_constexpr(pocs{}, [&, this]{
1185 hub_detail::swap_if(pocs{}, al(), x.al());
1186 },
1187 [&, this]{ /* else */
1188 BOOST_ASSERT(al() == x.al());
1189 (void)this;
1190 });
1191 21 std::swap(blist, x.blist);
1192 21 std::swap(num_blocks, x.num_blocks);
1193 21 std::swap(size_, x.size_);
1194 21 }
1195
1196 8 void clear() noexcept { erase(begin(), end()); }
1197
1198 12 void splice(hub& x)
1199 {
1200 12 BOOST_ASSERT(this != &x);
1201 20 BOOST_ASSERT(al() == x.al());
1202 90 for(auto pbb = x.blist.header()->next; pbb != x.blist.header(); ) {
1203 60 auto pb = static_cast_block_pointer(pbb);
1204 60 pbb = pbb->next;
1205 60 if(pb->mask != full) {
1206 18 x.blist.unlink_available(pb);
1207 21 blist.link_available_at_front(pb);
1208 }
1209 12 x.blist.unlink(pb);
1210 60 blist.link_at_back(pb);
1211 60 --x.num_blocks;
1212 60 ++num_blocks;
1213 60 auto s = core::popcount(pb->mask);
1214 60 x.size_ -= s;
1215 60 size_ += s;
1216 }
1217 12 }
1218
1219 6 void splice(hub&& x) { splice(x); }
1220
1221 template<typename BinaryPredicate = std::equal_to<T>>
1222 6 size_type unique(BinaryPredicate pred = BinaryPredicate())
1223 {
1224 6 auto s = size_;
1225 1206 for(auto first = cbegin(), last = cend(); first != last; ) {
1226 1200 auto next = std::next(first);
1227 1200 first = erase(
1228 next,
1229 std::find_if_not(next, last, [&] (const T& x) {
1230 return pred(x, *first);
1231 }));
1232 }
1233 6 return (size_type)(s - size_);
1234 }
1235
1236 template<typename Compare = std::less<T>>
1237 47 void sort(Compare comp = Compare())
1238 {
1239 /* transfer_sort is usually the fastest, but it consumes the most
1240 * auxiliary memory when sizeof(T) > sizeof(sort_proxy), so we restrict
1241 * its usage to the case sizeof(T) <= sizeof(sort_proxy).
1242 * compact_sort uses the least amount of auxiliary memory (by far), and
1243 * it's also faster than proxy_sort when the auxiliary memory of the latter
1244 * exceeds some threshold seemingly related to the size of the L2 cache;
1245 * we conventionally set the threshold to 2MB for lack of a more precise
1246 * estimation mechanism.
1247 * TODO: In 32-bit mode, the threshold policy is not so clear-cut and the
1248 * cost of moving elements around seems to play a role.
1249 */
1250 BOOST_IF_CONSTEXPR(sizeof(T) <= sizeof(sort_proxy)) {
1251 29 if(transfer_sort(comp)) return;
1252 }
1253 else{
1254 static constexpr std::size_t memory_threshold = 2 * 1024 * 1024;
1255 18 if((std::size_t)size_ * sizeof(sort_proxy) <= memory_threshold) {
1256 10 if(proxy_sort(comp)) return;
1257 }
1258 }
1259 8 compact_sort(comp);
1260 }
1261
1262 1600 iterator get_iterator(const_pointer p) noexcept /* noexcept? */
1263 {
1264 std::less<const T*> less;
1265 4992 for(auto pbb = blist.next; pbb != blist.header(); pbb = pbb-> next) {
1266 3328 auto pb = static_cast_block_pointer(pbb);
1267 6464 if(!less(boost::to_address(p), boost::to_address(pb->data())) &&
1268 4800 less(boost::to_address(p), boost::to_address(pb->data() + N))) {
1269 2000 return {pb, (int)(p - pb->data())};
1270 }
1271 }
1272 ✗ return end(); /* shouldn't assert? */
1273 }
1274
1275 800 const_iterator get_iterator(const_pointer p) const noexcept /* noexcept? */
1276 {
1277 800 return const_cast<hub*>(this)->get_iterator(p);
1278 }
1279
1280 template<typename F>
1281 410 void visit(iterator first, iterator last, F f)
1282 {
1283 410 visit_while(first, last, [&] (value_type& x) {
1284 f(x);
1285 return true;
1286 });
1287 410 }
1288
1289 template<typename F>
1290 344 void visit(const_iterator first, const_iterator last, F f) const
1291 {
1292 344 visit_while(first, last, [&] (const value_type& x) {
1293 f(x);
1294 return true;
1295 });
1296 344 }
1297
1298 template<typename F>
1299 2138 iterator visit_while(iterator first, iterator last, F f)
1300 {
1301 56860 for(auto pbb = first.pbb; first != last; ) {
1302 56152 if(!f(*first)) return first;
1303 ++first;
1304 69082 if(first.pbb != pbb) break;
1305 }
1306 2110 if(first.pbb != last.pbb) {
1307 2132 first = visit_while_impl(first.pbb, last.pbb, f);
1308 1784 if(first.pbb != last.pbb) return first;
1309 }
1310 12818 for(; first != last; ++first) if(!f(*first)) return first;
1311 770 return first;
1312 }
1313
1314 template<typename F>
1315 1036 const_iterator visit_while(
1316 const_iterator first, const_iterator last, F f) const
1317 {
1318 1295 auto it =const_cast<hub*>(this)->visit_while(
1319 1295 iterator{first.pbb, first.n}, iterator{last.pbb, last.n},
1320 [&] (const value_type& x) { return f(x); });
1321 1036 return {it.pbb, it.n};
1322 }
1323
1324 template<typename F>
1325 70 void visit_all(F f)
1326 {
1327 70 visit(begin(), end(), std::ref(f));
1328 70 }
1329
1330 template<typename F>
1331 4 void visit_all(F f) const
1332 {
1333 4 visit(begin(), end(), std::ref(f));
1334 4 }
1335
1336 template<typename F>
1337 4 iterator visit_all_while(F f)
1338 {
1339 4 return visit_while(begin(), end(), std::ref(f));
1340 }
1341
1342 template<typename F>
1343 4 const_iterator visit_all_while(F f) const
1344 {
1345 4 return visit_while(begin(), end(), std::ref(f));
1346 }
1347
1348 private:
1349 template<typename U, typename A, typename P>
1350 friend typename hub<U, A>::size_type erase_if(hub<U, A>&, P);
1351
1352 using block_typedefs = hub_detail::block_typedefs<Allocator>;
1353 using block_base = typename block_typedefs::block_base;
1354 using block_base_pointer = typename block_typedefs::block_base_pointer;
1355 using const_block_base_pointer =
1356 typename block_typedefs::const_block_base_pointer;
1357 using block = typename block_typedefs::block;
1358 using block_pointer = typename block_typedefs::block_pointer;
1359 using block_allocator = typename block_typedefs::block_allocator;
1360 using block_list = typename block_typedefs::block_list;
1361 using allocator_base = empty_value<block_allocator, 0>;
1362 using mask_type = typename block_base::mask_type;
1363
1364 static constexpr int N = block_base::N;
1365 static constexpr mask_type full = block_base::full;
1366
1367 20550957 block_allocator& al() noexcept { return allocator_base::get(); }
1368 166 const block_allocator& al() const noexcept { return allocator_base::get(); }
1369
1370 struct reset_on_exit
1371 {
1372 5 ~reset_on_exit() { x.reset(); }
1373
1374 hub& x;
1375 };
1376
1377 8 hub(
1378 hub&& x, const Allocator& al_, std::true_type /* equal allocs */) noexcept:
1379 8 allocator_base{empty_init, al_}, blist{std::move(x.blist)},
1380 8 num_blocks{x.num_blocks}, size_{x.size_}
1381 {
1382 8 x.num_blocks = 0;
1383 8 x.size_ = 0;
1384 8 }
1385
1386 6 hub(
1387 hub&& x, const Allocator& al_, std::false_type /* maybe unequal allocs */):
1388 6 hub{al_}
1389 {
1390 6 if(al() == x.al()) {
1391 2 blist = std::move(x.blist);
1392 2 num_blocks = x.num_blocks;
1393 2 size_ = x.size_;
1394 2 x.num_blocks = 0;
1395 2 x.size_ = 0;
1396 }
1397 else {
1398 4 reset_on_exit on_exit{x}; (void)on_exit;
1399 4 range_insert_impl(x.begin(), x.end(), [this] (T* p, iterator it) {
1400 allocator_construct(al(), p, std::move(*it));
1401 });
1402 4 }
1403 6 }
1404
1405 9 void move_assign(hub& x, std::true_type /* transfer structure */)
1406 {
1407 using pocma =
1408 allocator_propagate_on_container_move_assignment_t<Allocator>;
1409
1410 9 reset();
1411 9 hub_detail::move_assign_if(pocma{}, al(), x.al());
1412 9 blist = std::move(x.blist);
1413 9 num_blocks = x.num_blocks;
1414 9 size_ = x.size_;
1415 9 x.num_blocks = 0;
1416 9 x.size_ = 0;
1417 9 }
1418
1419 3 void move_assign(hub& x, std::false_type /* maybe move data */)
1420 {
1421 3 if(al() == x.al()) {
1422 2 move_assign(x, std::true_type{});
1423 }
1424 else {
1425 1 reset_on_exit on_exit{x}; (void)on_exit;
1426 1 range_assign_impl(
1427 x.begin(), x.end(),
1428 400 [this] (T* p, iterator it)
1429 200 { allocator_construct(al(), p, std::move(*it)); },
1430 400 [] (T* p, iterator it)
1431 200 { *p = std::move(*it); });
1432 1 }
1433 3 }
1434
1435 static block_pointer
1436 15624323 static_cast_block_pointer(block_base_pointer pbb) noexcept
1437 {
1438 15624323 return block_list::static_cast_block_pointer(pbb);
1439 }
1440
1441 156300 block_pointer create_new_available_block()
1442 {
1443 156300 auto pb = allocator_allocate(al(), 1);
1444 156300 pb->mask = 0;
1445 BOOST_TRY {
1446 156300 allocator_rebind_t<Allocator, value_type> val(al());
1447 156492 pb->data_ = allocator_allocate(val, N);
1448 }
1449 ✗ BOOST_CATCH(...) {
1450 ✗ allocator_deallocate(al(), pb, 1);
1451 ✗ BOOST_RETHROW;
1452 }
1453 BOOST_CATCH_END
1454 156300 blist.link_available_at_back(pb);
1455 156300 ++num_blocks;
1456 156300 return pb;
1457 }
1458
1459 156300 void delete_block(block_pointer pb) noexcept
1460 {
1461 156300 allocator_rebind_t<Allocator, value_type> val(al());
1462 156300 allocator_deallocate(val, pb->data(), N);
1463 156300 allocator_deallocate(al(), pb, 1);
1464 156300 }
1465
1466 BOOST_FORCEINLINE block_pointer retrieve_available_block(int& n)
1467 {
1468 9936138 if(BOOST_LIKELY(blist.next_available != blist.header())){
1469 9779852 auto pb = static_cast_block_pointer(blist.next_available);
1470 9779442 n = hub_detail::unchecked_countr_one(pb->mask);
1471 9779032 return pb;
1472 }
1473 else {
1474 156128 n = 0;
1475 156128 return create_new_available_block();
1476 }
1477 }
1478
1479 59422 size_type destroy_all_in_nonempty_block(block_pointer pb) noexcept
1480 {
1481 59422 BOOST_ASSERT(pb->mask != 0);
1482 59494 return destroy_all_in_nonempty_block(pb, std::integral_constant<bool,
1483 std::is_trivially_destructible<T>::value &&
1484 ( hub_detail::is_std_allocator<block_allocator>::value ||
1485 hub_detail::is_std_pmr_polymorphic_allocator<block_allocator>::value ||
1486 59422 !hub_detail::allocator_has_destroy<block_allocator, T*>::value )>{});
1487 }
1488
1489 59180 size_type destroy_all_in_nonempty_block(
1490 block_pointer pb, std::true_type /* trivial destruction */) noexcept
1491 {
1492 59180 return (size_type)core::popcount(pb->mask);
1493 }
1494
1495 242 size_type destroy_all_in_nonempty_block(
1496 block_pointer pb, std::false_type /* use allocator_destroy */) noexcept
1497 {
1498 242 size_type s = 0;
1499 242 auto mask = pb->mask;
1500 do {
1501 5181 auto n = hub_detail::unchecked_countr_zero(mask);
1502 5181 allocator_destroy(al(), boost::to_address(pb->data() + n));
1503 5181 ++s;
1504 5181 mask &= mask - 1;
1505 5181 } while(mask);
1506 242 return s;
1507 }
1508
1509 56876 size_type destroy_all_in_full_block(block_pointer pb) noexcept
1510 {
1511 56876 BOOST_ASSERT(pb->mask == full);
1512 3696940 for(int n = 0; n < N; ++n) {
1513 3651328 allocator_destroy(al(), boost::to_address(pb->data() + n));
1514 }
1515 56876 return (size_type)N;
1516 }
1517
1518 341 void reset() noexcept
1519 {
1520 99807 for(auto pbb = blist.next_available; pbb != blist.header(); ) {
1521 99278 auto pb = static_cast_block_pointer(pbb);
1522 99278 pbb = pb->next_available;
1523 BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1524 40079 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1525 }
1526 99278 if(pb->mask != 0) {
1527 59393 destroy_all_in_nonempty_block(pb);
1528 67 blist.unlink(pb);
1529 }
1530 99278 delete_block(pb);
1531 }
1532 /* full blocks remaining */
1533 57417 for(auto pbb = blist.next; pbb != blist.header(); ) {
1534 56876 BOOST_ASSERT(pbb->mask == full);
1535 56876 auto pb = static_cast_block_pointer(pbb);
1536 56876 pbb = pb->next;
1537 BOOST_IF_CONSTEXPR(!std::is_trivially_destructible<T>::value) {
1538 37587 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1539 }
1540 56876 destroy_all_in_full_block(pb);
1541 56876 delete_block(pb);
1542 }
1543 341 blist.reset();
1544 341 num_blocks = 0;
1545 341 size_ = 0;
1546 341 }
1547
1548 BOOST_FORCEINLINE void erase_impl(block_base_pointer pbb, int n) noexcept
1549 {
1550 5119854 auto pb = static_cast_block_pointer(pbb);
1551 5121128 allocator_destroy(al(), boost::to_address(pb->data() + n));
1552 5119878 if(BOOST_UNLIKELY(pb->mask == full)) blist.link_available_at_front(pb);
1553 5117943 pb->mask &= ~((mask_type)(1) << n);
1554 5119860 if(BOOST_UNLIKELY(pb->mask == 0)) blist.unlink(pb);
1555 5119854 --size_;
1556 5119854 }
1557
1558 template<typename Incrementable, typename Sentinel, typename Construct>
1559 287 void range_insert_impl(
1560 Incrementable first, Sentinel last, Construct construct)
1561 {
1562 923 while(first != last) {
1563 int n;
1564 760 auto pb = retrieve_available_block(n);
1565 for(; ; ) {
1566 58548 construct(boost::to_address(pb->data() + n), first++);
1567 43758 ++size_;
1568 43915 if(BOOST_UNLIKELY(pb->mask == 0)) blist.link_at_back(pb);
1569 51153 pb->mask |= pb->mask +1;
1570 43758 if(pb->mask == full){
1571 636 blist.unlink_available(pb);
1572 636 break;
1573 }
1574 43122 else if(first == last) return;
1575 42839 n = hub_detail::unchecked_countr_one(pb->mask);
1576 }
1577 }
1578 }
1579
1580 template<
1581 typename Incrementable, typename Sentinel,
1582 typename Construct, typename Insert
1583 >
1584 44 void range_assign_impl(
1585 Incrementable first, Sentinel last, Construct construct, Insert insert)
1586 {
1587 44 auto pbb = blist.next;
1588 44 int n = -1;
1589 44 if(first != last) {
1590 /* consume active blocks */
1591 92 for(; pbb != blist.header(); pbb = pbb->next) {
1592 40 auto pb = static_cast_block_pointer(pbb);
1593 40 n = 0;
1594 2173 for(mask_type bit = 1; bit; bit <<= 1, ++n) {
1595 2140 if(pb->mask & bit) { /* full slot */
1596 2120 insert(boost::to_address(pb->data() + n), first++);
1597 }
1598 else { /* empty slot */
1599 662 construct(boost::to_address(pb->data() + n), first++);
1600 460 ++size_;
1601 460 pb->mask |= bit;
1602 463 if(pb->mask == full) blist.unlink_available(pb);
1603 }
1604 2140 if(first == last) goto exit;
1605 }
1606 }
1607 40 exit: ;
1608 }
1609 44 if(first != last) {
1610 /* all active blocks consumed, keep inserting */
1611 33 range_insert_impl(first, last, construct);
1612 }
1613 else{
1614 /* erase remaining original elements */
1615 20 auto it = (n == -1)? const_iterator{pbb}: ++const_iterator{pbb, n};
1616 11 erase(it, cend());
1617 }
1618 44 }
1619
1620 template<typename Compare>
1621 29 bool transfer_sort(Compare comp)
1622 {
1623 /* transfer to a buffer, sort and transfer back */
1624 53 hub_detail::buffer<T,Allocator> buf(size_, al());
1625 29 if(!buf.data) return false;
1626
1627 39 visit_all([&] (value_type& x) { buf.emplace_back(std::move(x)); });
1628 29 std::sort(buf.begin(), buf.end(), comp);
1629 29 visit_all([&] (value_type& x) {
1630 10 x = std::move(*buf.begin());
1631 10 buf.erase_front();
1632 });
1633 29 return true;
1634 29 }
1635
1636 struct sort_proxy
1637 {
1638 T* p;
1639 size_type n;
1640 };
1641
1642 template<typename Compare>
1643 10 bool proxy_sort(Compare comp)
1644 {
1645 /* sort an array of (pointer, index) pairs and relocate according to it */
1646 10 if(size_ > 1) {
1647 8 hub_detail::nodtor_unique_ptr<sort_proxy[]> p
1648 {static_cast<sort_proxy*>(
1649 8 ::operator new[](size_ * sizeof(sort_proxy), std::nothrow))};
1650 8 if(!p) return false;
1651
1652 8 size_type i = 0;
1653 8 visit_all([&] (value_type& x) {
1654 p[i] = {std::addressof(x), i};
1655 ++i;
1656 });
1657
1658 8 std::sort(
1659 8 p.get(), p.get() + size_,
1660 [&] (const sort_proxy& x, const sort_proxy& y) {
1661 return comp(const_cast<const T&>(*x.p), const_cast<const T&>(*y.p));
1662 });
1663
1664 8 i = 0;
1665 7888 for(; i < size_; ++i) {
1666 7880 if(p[i].n != i) {
1667 53 T x = std::move(*(p[i].p));
1668 53 auto j = i;
1669 do {
1670 7819 auto k = p[j].n;
1671 7819 *(p[j].p) = std::move(*p[k].p);
1672 7819 p[j].n = j;
1673 7819 j = k;
1674 7819 } while(p[j].n != i);
1675 53 *(p[j].p) = std::move(x);
1676 53 p[j].n = j;
1677 53 }
1678 }
1679 8 }
1680 10 return true;
1681 }
1682
1683 template<typename Compare>
1684 8 void compact_sort(Compare comp)
1685 {
1686 /* compact elements and build an array of pointers to data chunks of N */
1687 using sort_iterator = hub_detail::sort_iterator<T, N>;
1688
1689 8 if(size_ > 1) {
1690 8 std::size_t n = (std::size_t)((size_ + N - 1) / N);
1691 8 hub_detail::nodtor_unique_ptr<T*[]> p
1692 8 {static_cast<T**>(::operator new[](n * sizeof(T*)))};
1693 8 std::size_t i = 0;
1694 8 compact([&] (block_pointer pb) {
1695 ✗ p[i++] = boost::to_address(pb->data());
1696 });
1697 8 BOOST_ASSERT(i == n);
1698
1699 8 std::sort(
1700 sort_iterator{p.get(), 0}, sort_iterator{p.get(), size_}, comp);
1701 8 }
1702 8 }
1703
1704 36 void compact() { compact([] (block_pointer) {}); }
1705
1706 template<typename Track>
1707 16 void compact(Track track)
1708 {
1709 29075 for(auto pbbx = blist.next; pbbx != blist.header(); ) {
1710 29070 auto pbx = static_cast_block_pointer(pbbx);
1711 29070 auto pbby = pbbx->next;
1712 29070 if(pbx->mask != full) {
1713 do{
1714 57734 if(pbby->mask == full) {
1715 do {
1716 8470 track(static_cast_block_pointer(pbby));
1717 8470 pbby = pbby->next;
1718 8470 } while(pbby->mask == full);
1719 ✗ blist.unlink(pbx);
1720 14 blist.link_before(pbx, static_cast_block_pointer(pbby));
1721 }
1722 57735 if(pbby == blist.header()) {
1723 16 compact(pbx);
1724 16 track(pbx);
1725 16 return;
1726 }
1727 else{
1728 57718 auto pby = static_cast_block_pointer(pbby);
1729 57718 compact(pbx,pby);
1730 57718 if(pby->mask == 0) {
1731 39838 pbby = pby->next;
1732 ✗ blist.unlink(pby);
1733 }
1734 }
1735 57718 }while(pbx->mask != full);
1736 18774 blist.unlink_available(pbx);
1737 }
1738 29054 track(pbx);
1739 29051 pbbx = pbby;
1740 }
1741 }
1742
1743 57718 void compact(block_pointer pbx, block_pointer pby)
1744 {
1745 57718 auto cx = core::popcount(pbx->mask),
1746 57718 cy = core::popcount(pby->mask);
1747 57718 if(cx < cy) {
1748 17940 std::swap(cx, cy);
1749 17940 swap_payload(*pbx, *pby);
1750 }
1751 57718 auto c = (std::min)(N - cx, cy);
1752 648532 while(c--) {
1753 590814 auto n = hub_detail::unchecked_countr_one(pbx->mask);
1754 590814 auto m = N - 1 - hub_detail::unchecked_countl_zero(pby->mask);
1755 590814 allocator_construct(
1756 590814 al(), boost::to_address(pbx->data() + n), std::move(pby->data()[m]));
1757 590814 allocator_destroy(al(), boost::to_address(pby->data() + m));
1758 590814 pbx->mask |= pbx->mask + 1;
1759 590814 pby->mask &= ~((mask_type)(1) << m);
1760 }
1761 57718 }
1762
1763 16 void compact(block_pointer pb)
1764 {
1765 4 for(; ; ) {
1766 20 auto n = hub_detail::unchecked_countr_one(pb->mask);
1767 20 auto m = N - 1 - hub_detail::unchecked_countl_zero(pb->mask);
1768 20 if(n > m) return;
1769 4 allocator_construct(
1770 4 al(), boost::to_address(pb->data() + n), std::move(pb->data()[m]));
1771 4 allocator_destroy(al(), boost::to_address(pb->data() + m));
1772 4 pb->mask |= pb->mask + 1;
1773 4 pb->mask &= ~((mask_type)(1) << m);
1774 }
1775 }
1776
1777 template<typename F>
1778 1436 iterator visit_while_impl(
1779 block_base_pointer pbb, block_base_pointer last_pbb, F&& f)
1780 {
1781 1436 BOOST_ASSERT(pbb != last_pbb);
1782 1436 auto pb = static_cast_block_pointer(pbb);
1783 1436 auto mask = pb->mask;
1784 1436 auto n = hub_detail::unchecked_countr_zero(mask);
1785 1436 auto pd = pb->data();
1786 do {
1787 157098 pbb = pb->next;
1788 157098 auto next_mask = pbb->mask;
1789 157098 auto next_n = hub_detail::unchecked_countr_zero(next_mask);
1790 157506 auto next_pd = static_cast_block_pointer(pbb)->data();
1791 157506 BOOST_CONTAINER_HUB_PREFETCH(next_pd + next_n);
1792 157098 BOOST_CONTAINER_HUB_PREFETCH(pbb->next);
1793 for(; ; ) {
1794 4902006 if(!f(pd[n])) return {pb, n};
1795 4885302 mask &= mask - 1;
1796 4885302 if(!mask) break;
1797 4729132 n = hub_detail::unchecked_countr_zero(mask);
1798 }
1799 156170 pb = static_cast_block_pointer(pbb);
1800 156170 mask = next_mask;
1801 156170 n = next_n;
1802 155994 pd = next_pd;
1803 156170 } while(pb != last_pbb);
1804 508 return {last_pbb};
1805 }
1806
1807 block_list blist;
1808 size_type num_blocks = 0;
1809 size_type size_ = 0;
1810 };
1811
1812 #if !defined(BOOST_NO_CXX17_DEDUCTION_GUIDES)
1813 template<
1814 typename InputIterator,
1815 typename Allocator = std::allocator<
1816 typename std::iterator_traits<InputIterator>::value_type>
1817 >
1818 hub(InputIterator, InputIterator, Allocator = Allocator())
1819 -> hub<
1820 typename std::iterator_traits<InputIterator>::value_type, Allocator>;
1821
1822 #if !defined(BOOST_CONTAINER_HUB_NO_RANGES)
1823 template<
1824 std::ranges::input_range R,
1825 typename Allocator = std::allocator<std::ranges::range_value_t<R>>
1826 >
1827 hub(from_range_t, R&&, Allocator = Allocator())
1828 -> hub<std::ranges::range_value_t<R>, Allocator>;
1829 #endif
1830 #endif
1831
1832 template<typename T, typename Allocator>
1833 8 void swap(hub<T, Allocator>& x, hub<T, Allocator>& y)
1834 noexcept(noexcept(x.swap(y)))
1835 {
1836 8 x.swap(y);
1837 8 }
1838
1839 template<typename T, typename Allocator, typename Predicate>
1840 typename hub<T, Allocator>::size_type
1841 54 erase_if(hub<T, Allocator>& x, Predicate pred)
1842 {
1843 using hub_container = hub<T, Allocator>;
1844 using size_type = typename hub_container::size_type;
1845 using block = typename hub_container::block;
1846
1847 54 auto s = x.size_;
1848 155332 for(auto pbb = x.blist.next; pbb != x.blist.header(); ) {
1849 155262 auto pb = x.static_cast_block_pointer(pbb);
1850 155262 pbb = pb->next;
1851 155262 BOOST_CONTAINER_HUB_PREFETCH_BLOCK(pbb, block);
1852 155262 auto mask = pb->mask;
1853 do {
1854 9935010 auto n = hub_detail::unchecked_countr_zero(mask);
1855 9935510 if(pred(pb->data()[n])) x.erase_impl(pb, n);
1856 9935010 mask &= mask - 1;
1857 9935010 } while(mask);
1858 }
1859 54 return (size_type)(s - x.size_);
1860 }
1861
1862 template<typename T, typename Allocator, typename U = T>
1863 typename hub<T, Allocator>::size_type
1864 8 erase(hub<T, Allocator>& x, const U& value)
1865 {
1866 808 return erase_if(x, [&](const T& v) -> bool { return v == value; });
1867 }
1868
1869 } /* namespace container */
1870
1871 } /* namespace boost */
1872
1873 #if defined(BOOST_MSVC)
1874 #pragma warning(pop) /* C4714 */
1875 #endif
1876
1877 #endif
1878