[RFC] libstdc++: Implement P0447R28 std::hive
Tomasz Kaminski
tkaminsk@redhat.com
Thu Oct 1 14:33:54 GMT 2026
On Wed, Sep 30, 2026 at 4:52 PM Tomasz Kamiński <tkaminsk@redhat.com> wrote:
> This patch implements std::hive for C++26 as specified in P0447R28,
> except the sort member function.
>
> The tracking of the occupied and empty slot inside of single block, is done
> by the combination of low complexity skipfield (_BlockT::_M_skipfield), and
> double linked list of the free nodes stored inside first empty slot
> (_M_free).
> As each slot need to store position of the previous/next entry, we
> determine
> the _SizeT for the _BlockT, based on the size of the element _Tp. Limiting
> to
> half of sizeof(_Tp) or 1. As the skipfied is always byte sized (to reduce
> overhead for each element elements), larger block sized are encoded into
> multiple sequential bytes (see __hive::_Counter).
> We should explore the bitset stacking [1][2] as the alternative for both of
> above, as this would allow us to store elements of _Tp directly (instead of
> union with free node), and enable direct use of memcopy to insert or
> override elements.
> Additionally currently blocks does not store the number of occupied/free
> elements (only capacity), which prevents us from having no-op delete for
> trivially destructible types, and make insertion less optimal.
>
> The block metadata, skipfields and elements are sharing single allocation,
> where the block and skipfields are placed in storage provided by initial
> elements (_BlockT::_S_extra_slots). The pointer to initial allocation is
> stored in the block (_M_mem) and offset on each access (_M_elem). This
> allow
> the pointer to be eliminated completely if _BlockT is guaranteed to share
> same
> address, however requires extra computation on each access.
> We should measure effector storing pointer to start of elements and offset
> for the start of allocation instead (unsigned char member).
> Note that the above approach is not constexpr-compatible, as it requires
> reinterpret_cast and placement new on storage of object from different
> type.
> However, we could use a start offset with value zero to indicate separate
> allocation for blocks, elements and skipfield. This would required adding
> a separate skipfield pointer. Treating this as separate mode (and not
> constexpr path), will still work we support non-transient allocations,
> as runtime would be able to recognized and handle it accordingly.
>
This make iteration 30-40% faster, so clear win. Changed the implementation
on forget to use that:
https://forge.sourceware.org/gcc/gcc/pulls/224/commits/1a73c796eb6742e5aec02d9203f4588ae6eaf678
.
>
> The implementation currently keeps all reserved blocks (extra capacity)
> by default, until they removal is explicitly requested (shrink_to_fit,
> trim_capacity) or required to meet invariants (change of allocator or
> limits: reshape, move assignment). The reference implementation reduces
> the number of reserved blocks, and keeps only last two. This is again
> something to investigate.
>
> When the user specifies invalid limits (outside of hard limits), the
> standard makes operation erroneous with implementation-defined behavior.
> This patch asserts on that, and then:
> * use default limits, if limits does not for a range max < min,
> * otherwise clamp the limits to the hard limits
>
> Finally, the hive implements unconditional erase for range of iterator,
> in terms of erase with always true predicate (_M_block_erase_if) with
> always true functor. For that purpose we define _Always functor in the
> predefined_ops.h, as such utility is generally useful.
>
> [1]
> https://discourse.llvm.org/t/std-new-information-for-implementors/89125
> [2] https://plflib.org/matt_bentley_-_bitset_stacking.pdf
>
> libstdc++-v3/ChangeLog:
>
> * include/Makefile.am: Add std/hive and bits/hive.h headers.
> * include/Makefile.in: Regenerate.
> * include/bits/predefined_ops.h (__gnucxx::__ops::_Always):
> Define.
> * include/bits/version.def (hive): Define with value zero
> and no-std mode.
> * include/bits/version.h: Regenerate.
> * include/bits/hive.h: New file.
> * include/std/hive: New file.
> * testsuite/23_containers/hive/access.cc: New test.
> * testsuite/23_containers/hive/assign.cc: New test.
> * testsuite/23_containers/hive/capacity.cc: New test.
> * testsuite/23_containers/hive/copy_alloc.cc: New test.
> * testsuite/23_containers/hive/ctor.cc: New test.
> * testsuite/23_containers/hive/erasure.cc: New test.
> * testsuite/23_containers/hive/insert.cc: New test.
> * testsuite/23_containers/hive/move_alloc.cc: New test.
> * testsuite/23_containers/hive/splice.cc: New test.
> * testsuite/23_containers/hive/throws.cc: New test.
> ---
> The corresponding pull request can be also found on forge:
> https://forge.sourceware.org/gcc/gcc/pulls/224
>
> Some open question, to answer:
> * should I merge bits/hive.h into std/hive, or create
> separate bits/hive.tcc
> * is __gnucxx::__ops::_Always OK to add in all standard
> modes
>
> This is send as RFC, but I do not see issue in merging it to
> master in the current form (without exposing FTM).
>
> libstdc++-v3/include/Makefile.am | 2 +
> libstdc++-v3/include/Makefile.in | 2 +
> libstdc++-v3/include/bits/hive.h | 2238 +++++++++++++++++
> libstdc++-v3/include/bits/predefined_ops.h | 11 +
> libstdc++-v3/include/bits/version.def | 9 +
> libstdc++-v3/include/bits/version.h | 9 +
> libstdc++-v3/include/std/hive | 55 +
> .../testsuite/23_containers/hive/access.cc | 67 +
> .../testsuite/23_containers/hive/assign.cc | 158 ++
> .../testsuite/23_containers/hive/capacity.cc | 383 +++
> .../23_containers/hive/copy_alloc.cc | 335 +++
> .../testsuite/23_containers/hive/ctor.cc | 238 ++
> .../testsuite/23_containers/hive/erasure.cc | 291 +++
> .../testsuite/23_containers/hive/insert.cc | 93 +
> .../23_containers/hive/move_alloc.cc | 444 ++++
> .../testsuite/23_containers/hive/ranges.cc | 86 +
> .../testsuite/23_containers/hive/splice.cc | 200 ++
> .../testsuite/23_containers/hive/throws.cc | 352 +++
> 18 files changed, 4973 insertions(+)
> create mode 100644 libstdc++-v3/include/bits/hive.h
> create mode 100644 libstdc++-v3/include/std/hive
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/access.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/assign.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/insert.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/splice.cc
> create mode 100644 libstdc++-v3/testsuite/23_containers/hive/throws.cc
>
> diff --git a/libstdc++-v3/include/Makefile.am
> b/libstdc++-v3/include/Makefile.am
> index 3c30aa21d6b..60b795b0379 100644
> --- a/libstdc++-v3/include/Makefile.am
> +++ b/libstdc++-v3/include/Makefile.am
> @@ -79,6 +79,7 @@ std_headers = \
> ${std_srcdir}/forward_list \
> ${std_srcdir}/fstream \
> ${std_srcdir}/future \
> + ${std_srcdir}/hive \
> ${std_srcdir}/inplace_vector \
> ${std_srcdir}/iomanip \
> ${std_srcdir}/ios \
> @@ -231,6 +232,7 @@ bits_headers = \
> ${bits_srcdir}/gslice_array.h \
> ${bits_srcdir}/hashtable.h \
> ${bits_srcdir}/hashtable_policy.h \
> + ${bits_srcdir}/hive.h \
> ${bits_srcdir}/indirect.h \
> ${bits_srcdir}/indirect_array.h \
> ${bits_srcdir}/ios_base.h \
> diff --git a/libstdc++-v3/include/Makefile.in
> b/libstdc++-v3/include/Makefile.in
> index d081481293f..5d09c2b826f 100644
> --- a/libstdc++-v3/include/Makefile.in
> +++ b/libstdc++-v3/include/Makefile.in
> @@ -438,6 +438,7 @@ std_freestanding = \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/forward_list \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/fstream \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/future \
> +@GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/hive \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/inplace_vector \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/iomanip \
> @GLIBCXX_HOSTED_TRUE@ ${std_srcdir}/ios \
> @@ -587,6 +588,7 @@ bits_freestanding = \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/gslice_array.h \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/hashtable.h \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/hashtable_policy.h \
> +@GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/hive.h \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/indirect.h \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/indirect_array.h \
> @GLIBCXX_HOSTED_TRUE@ ${bits_srcdir}/ios_base.h \
> diff --git a/libstdc++-v3/include/bits/hive.h
> b/libstdc++-v3/include/bits/hive.h
> new file mode 100644
> index 00000000000..d3a951dbe23
> --- /dev/null
> +++ b/libstdc++-v3/include/bits/hive.h
> @@ -0,0 +1,2238 @@
> +// Hive implementation -*- C++ -*-
> +
> +// Copyright (C) 2026 Free Software Foundation, Inc.
> +//
> +// This file is part of the GNU ISO C++ Library. This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +// GNU General Public License for more details.
> +
> +// Under Section 7 of GPL version 3, you are granted additional
> +// permissions described in the GCC Runtime Library Exception, version
> +// 3.1, as published by the Free Software Foundation.
> +
> +// You should have received a copy of the GNU General Public License and
> +// a copy of the GCC Runtime Library Exception along with this program;
> +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @file bits/hive.h
> + * This is an internal header file, included by other library headers.
> + * Do not attempt to use it directly. @headername{hive}
> + */
> +
> +#ifndef _BITS_HIVE_H
> +#define _BITS_HIVE_H 1
> +
> +#ifdef __glibcxx_hive // C++ >= 26
> +
> +#include <bits/align.h>
> +#include <bits/stl_iterator_base_funcs.h>
> +#include <bits/stdexcept_throw.h>
> +#include <bits/ranges_util.h> // ranges::subrange, _Repeat_iterator
> +#include <compare>
> +#include <bit>
> +#include <initializer_list>
> +#include <span>
> +
> +#include <debug/assertions.h>
> +
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> +
> +struct hive_limits
> +{
> + constexpr
> + hive_limits(size_t __min, size_t __max) noexcept
> + : min(__min), max(__max)
> + { }
> +
> + size_t min;
> + size_t max;
> +};
> +
> +template<typename _Tp, typename _Alloc = allocator<_Tp>>
> + class hive;
> +
> +template<typename _Tp, typename _Alloc, typename _Predicate>
> + typename hive<_Tp, _Alloc>::size_type
> + erase_if(hive<_Tp, _Alloc>& __cont, _Predicate __pred);
> +
> +namespace __hive
> +{
> + struct _IgnorePtr
> + {
> + constexpr
> + _IgnorePtr(nullptr_t)
> + { }
> +
> + template<typename _Tp>
> + constexpr
> + _IgnorePtr(const volatile _Tp*)
> + { }
> + };
> +
> + template<size_t _Bytes>
> + struct _Counter
> + {
> + static consteval auto
> + _S_select_size()
> + {
> + if constexpr (_Bytes == sizeof(size_t))
> + return static_cast<size_t>(0);
> +#ifdef __UINT64_TYPE__
> + else if constexpr (_Bytes == 8)
> + return static_cast<__UINT64_TYPE__>(0);
> +#endif
> +#ifdef __UINT32_TYPE__
> + else if constexpr (_Bytes == 4)
> + return static_cast<__UINT32_TYPE__>(0);
> +#endif
> +#ifdef __UINT16_TYPE__
> + else if constexpr (_Bytes == 2)
> + return static_cast<__UINT16_TYPE__>(0);
> +#endif
> + else if constexpr (_Bytes == 1)
> + return static_cast<unsigned char>(0);
> + else
> + static_assert("Unsupported bytes count");
> + }
> +
> + using _SizeT = decltype(_S_select_size());
> +
> + static consteval _SizeT
> + max_size()
> + {
> + if constexpr (_Bytes >= 8)
> + return (_SizeT(1) << 48) - 1;
> + else if constexpr (_Bytes >= 4)
> + return (_SizeT(1) << 24) - 1;
> + else if constexpr (_Bytes >= 2)
> + return (_SizeT(1) << 12) - 1;
> + else
> + return _SizeT(255);
> + }
> +
> + static constexpr unsigned char _S_contb = 0x40;
> + static constexpr unsigned char _S_vmask = _S_contb - 1;
> +
> + static _SizeT
> + _S_load_high(const unsigned char* __ptr) noexcept
> + {
> + _SizeT __res(*__ptr & _S_vmask);
> + if constexpr (_Bytes >= 2)
> + __res |= (_SizeT(__ptr[1] & _S_vmask) << 6);
> + if constexpr (_Bytes >= 4)
> + {
> + __res |= (_SizeT(__ptr[2] & _S_vmask) << 12);
> + __res |= (_SizeT(__ptr[3] & _S_vmask) << 18);
> + }
> + if constexpr (_Bytes >= 8)
> + {
> + __res |= (_SizeT(__ptr[4] & _S_vmask) << 24);
> + __res |= (_SizeT(__ptr[5] & _S_vmask) << 30);
> + __res |= (_SizeT(__ptr[6] & _S_vmask) << 36);
> + __res |= (_SizeT(__ptr[7] & _S_vmask) << 42);
> + }
> + return __res;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + static _SizeT
> + _S_load_fwd(const unsigned char* __ptr) noexcept
> + {
> + if constexpr (_Bytes == 1)
> + return _SizeT(*__ptr);
> + else if (!(*__ptr & _S_contb))
> + return _SizeT(*__ptr & _S_vmask);
> + else
> + return _S_load_high(__ptr);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + static _SizeT
> + _S_load_bwd(const unsigned char* __ptr) noexcept
> + {
> + if constexpr (_Bytes == 1)
> + return _SizeT(*__ptr);
> + else if (!(*__ptr & _S_contb))
> + return _SizeT(*__ptr & _S_vmask);
> + else
> + return _S_load_high(__ptr + 1 - _Bytes);
> + }
> +
> + static void
> + _S_store_high(unsigned char* __ptr, _SizeT __val) noexcept
> + {
> + *__ptr = (_S_contb | (__val & 0x3f));
> + if constexpr (_Bytes >= 2)
> + __ptr[1] = (_S_contb | ((__val >> 6) & _S_vmask));
> + if constexpr (_Bytes >= 4)
> + {
> + __ptr[2] = (_S_contb | ((__val >> 12) & _S_vmask));
> + __ptr[3] = (_S_contb | ((__val >> 18) & _S_vmask));
> + }
> + if constexpr (_Bytes >= 8)
> + {
> + __ptr[4] = (_S_contb | ((__val >> 24) & _S_vmask));
> + __ptr[5] = (_S_contb | ((__val >> 30) & _S_vmask));
> + __ptr[6] = (_S_contb | ((__val >> 36) & _S_vmask));
> + __ptr[7] = (_S_contb | ((__val >> 42) & _S_vmask));
> + }
> + }
> +
> + [[__gnu__::__always_inline__]]
> + static void
> + _S_store(unsigned char* __ptr, _SizeT __val) noexcept
> + {
> + if constexpr (_Bytes == 1)
> + __ptr[0] = __ptr[__val-1] = __val;
> + else if (__val <= _S_vmask)
> + __ptr[0] = __ptr[__val-1] = __val;
> + else
> + {
> + _S_store_high(__ptr, __val);
> + _S_store_high(__ptr + __val - _Bytes, __val);
> + }
> + }
> + };
> +
> + // Represents an metada about the memory block. Each memory
> + // block consits of:
> + // * block metadata (_Block object)
> + // * skipfields (_M_capacity bytes)
> + // * slots (_M_capacity _Slot)
> + // Are of them are placed in single memory chunk of _M_capacity
> + // + _S_extra_slots(_M_capacity) elements, as follows
> + //
> + // | <- _S_extra_slots(_M_capacity) -->
> |
> + // | <- __for_align_ --> | <-- __for_block -> | <-- _for_skipfields -->
> | <-- _M_capacity --> |
> + // [ align ][ _Block ][ skipfields ]
> [ slots ]
> + //
> + // The address of the chunk (if needed) is stored inside block can be
> + // retrived by _M_memory(). The member is optimized out if it can be
> + // restored from block address (there is not algigment).
> + //
> + // Each of the slot either contains element (_M_val) or is empty,
> + // occupied elemnts has their corresponding skipfield by set to
> + // 0xff.
> + //
> + // Continous ranges of the empty slot, form a double linked list,
> + // that are indicated by positions of previous and next node
> + // (npos is used to indicate first/last node). The head of the
> + // list is _M_free_head member. The size of the range is encoded
> + // in the edge bytes of skipfields, allow O(1) skipping.
> + //
> + // The _Blocks are member of intriusive list represented by
> + // _Block_list and _M_next, _M_prev, _M_next_free, _M_prev_free
> + // members facilitate that.
> + template<typename _Tp, typename _Counter, typename _Ptr>
> + struct _Block
> + {
> + using _CounterT = _Counter;
> + using _SizeT = typename _CounterT::_SizeT;
> + static constexpr _SizeT npos = ~_SizeT(0);
> +
> + struct _Free_node
> + {
> + _SizeT _M_prev;
> + _SizeT _M_next;
> + };
> +
> + union _Slot
> + {
> + _Tp _M_val;
> + _Free_node _M_free;
> + };
> +
> + struct _Reservation
> + {
> + _SizeT _M_pos;
> + _SizeT _M_capacity;
> + _SizeT _M_next;
> + };
> +
> + using _Alloc_ptr = __ptr_rebind<_Ptr, _Slot>;
> + using _Mem_ptr = std::conditional_t<
> + // Block is stored at the first byte of allocated memory chunk,
> + // so their pointer value are the same.
> + is_pointer_v<_Ptr> && (alignof(void*) <= alignof(_Slot)),
> + _IgnorePtr, _Alloc_ptr>;
> +
> + static constexpr size_t
> + _S_slot_count(size_t __bytes) noexcept
> + { return (__bytes + sizeof(_Slot) - 1) / sizeof(_Slot); }
> +
> + static constexpr size_t
> + _S_extra_slots(size_t __capacity) noexcept
> + {
> + constexpr size_t __align_req = (alignof(_Block) > alignof(_Slot))
> + ? alignof(_Block) - alignof(_Slot)
> : 0;
> + constexpr size_t __for_align = _S_slot_count(__align_req);
> + constexpr size_t __for_block = _S_slot_count(sizeof(_Block));
> + constexpr size_t __block_pad = __for_align * sizeof(_Slot) -
> __align_req
> + + __for_block * sizeof(_Slot) -
> sizeof(_Block);
> +
> + size_t __for_skipfields
> + = (__capacity > __block_pad) ? _S_slot_count(__capacity -
> __block_pad) : 0;
> + return __for_align + __for_block + __for_skipfields;
> + }
> +
> + _Block() = default;
> +
> + explicit
> + _Block(_Alloc_ptr __mem, _SizeT __capacity) noexcept
> + : _M_mem(__mem), _M_capacity(__capacity)
> + { _M_clear_slots(); }
> +
> + _Block* _M_next = nullptr;
> + _Block* _M_prev = nullptr;
> + _Block* _M_next_free = nullptr;
> + _Block* _M_prev_free = nullptr;
> +
> + [[no_unique_address]] _Mem_ptr _M_mem = nullptr;
> + _SizeT _M_capacity = 0;
> + _SizeT _M_free_head = npos;
> +
> + [[__gnu__::__always_inline__]]
> + bool
> + _M_sentinel() const noexcept
> + { return _M_capacity == 0; }
> +
> + [[__gnu__::__always_inline__]]
> + bool
> + _M_full() const noexcept
> + { return _M_free_head == npos; }
> +
> + [[__gnu__::__always_inline__]]
> + bool
> + _M_empty() const noexcept
> + {
> + return (_M_free_head == 0) && (_M_free_count(0) == _M_capacity);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + _Alloc_ptr
> + _M_memory() const noexcept
> + {
> + if constexpr (is_pointer_v<_Ptr> && (alignof(void*) <=
> alignof(_Slot)))
> + return reinterpret_cast<_Slot*>(const_cast<_Block*>(this));
> + else
> + return _M_mem;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + unsigned char*
> + _M_skipfield(size_t __pos) const noexcept
> + {
> + return reinterpret_cast<unsigned char*>(const_cast<_Block*>(this))
> + + sizeof(_Block) + __pos;
> + }
> +
> + // Number of empty slot in free node starting at __pos.
> + [[__gnu__::__always_inline__]]
> + _SizeT
> + _M_free_count(size_t __pos) const noexcept
> + { return _CounterT::_S_load_fwd(_M_skipfield(__pos)); }
> +
> + [[__gnu__::__always_inline__]]
> + bool
> + _M_occupied(size_t __pos) const noexcept
> + {
> + auto val = *_M_skipfield(__pos);
> + return val == 0xff;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + _SizeT
> + _M_first_occupied() const noexcept
> + {
> + if (_M_sentinel() || _M_occupied(0))
> + return 0;
> + return _M_free_count(0);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + _Slot*
> + _M_slot(size_t __pos) const noexcept
> + { return std::to_address(_M_memory()) + _S_extra_slots(_M_capacity)
> + __pos; }
> +
> + [[__gnu__::__always_inline__]]
> + _Tp*
> + _M_elem(size_t __pos) const noexcept
> + { return std::addressof(_M_slot(__pos)->_M_val); }
> +
> + // If slot is contained within block, returns it position,
> + // and npos otherwise.
> + _SizeT
> + _M_contains(const _Slot* __ptr)
> + {
> + constexpr std::less<const _Slot*> __ptrlt;
> + if (!__ptrlt(__ptr, _M_slot(0)) && !__ptrlt(_M_slot(_M_capacity -
> 1), __ptr))
> + return __ptr - _M_slot(0);
> + return npos;
> + }
> +
> + // Returns the information about the first range of empty slots,
> + // with sufficient information to rebuild it.
> + [[__gnu__::__always_inline__]]
> + _Reservation
> + _M_reserve_slots() const noexcept
> + {
> + return {_M_free_head,
> + _M_free_count(_M_free_head),
> + _M_slot(_M_free_head)->_M_free._M_next};
> + }
> +
> + // Push the free node at position __pos to front on the list,
> + // guaranteeing next insertion will happen at that point
> + void
> + _M_move_free_head(size_t __pos) noexcept
> + {
> + if (_M_free_head == __pos)
> + return;
> +
> + _Free_node& __node = _M_slot(__pos)->_M_free;
> + // Unlik the node from it's current position
> + _M_slot(__node._M_prev)->_M_free._M_next = __node._M_next;
> + if (__node._M_next != npos)
> + _M_slot(__node._M_next)->_M_free._M_prev = __node._M_prev;
> +
> + // Move it to the front of the free list
> + __node = {npos, _M_free_head};
> + _M_free_head = __pos;
> + }
> +
> + // Marks slots in range [__res._M_pos, __res._M_pos + __n),
> adjusting the free list.
> + // Returns true if the block is filled.
> + bool
> + _M_commit_slots(_Reservation __res, size_t __n) noexcept
> + {
> + std::fill_n(_M_skipfield(__res._M_pos), __n, 0xff);
> + if (__n < __res._M_capacity)
> + {
> + // Node is partially used, trim it size, and adjust node.
> + _M_free_head += __n;
> + _M_slot(_M_free_head)->_M_free = {npos, __res._M_next};
> + _CounterT::_S_store(_M_skipfield(_M_free_head),
> __res._M_capacity - __n);
> + return false;
> + }
> + else if (__res._M_next != npos)
> + {
> + // Node is fully used, next free node becomes first node.
> + _M_free_head = __res._M_next;
> + _M_slot(_M_free_head)->_M_free._M_prev = npos;
> + return false;
> + }
> + else
> + {
> + // Node and block is fully used.
> + _M_free_head = npos;
> + return true;
> + }
> + }
> +
> + // Marks slot in range [__pos, __pos + __n) as empty, and record
> them
> + // in free list. Updates __pos to next occupied slot and returns
> true
> + // if block is empty
> + bool
> + _M_release_slots(size_t& __pos, size_t __n) noexcept
> + {
> + size_t __pfree = 0, __nfree = 0;
> + if ((__pos > 0) && !_M_occupied(__pos - 1))
> + __pfree = _CounterT::_S_load_bwd(_M_skipfield(__pos - 1));
> + if ((__pos + __n < _M_capacity) && !_M_occupied(__pos + __n))
> + __nfree = _CounterT::_S_load_fwd(_M_skipfield(__pos + __n));
> +
> + if (__pfree + __nfree + __n == _M_capacity)
> + {
> + // All slots in blocks become empty, simply clear the block.
> + _M_clear_slots();
> + __pos = _M_capacity;
> + return true;
> + }
> +
> + auto __link_next = [this](size_t __pos, size_t __next)
> + {
> + if (__pos != npos)
> + _M_slot(__pos)->_M_free._M_next = __next;
> + else
> + _M_free_head = __next;
> + };
> +
> + auto __link_prev = [this](size_t __pos, size_t __prev)
> + {
> + if (__pos != npos)
> + _M_slot(__pos)->_M_free._M_prev = __prev;
> + };
> +
> + if (__pfree && __nfree)
> + {
> + // Two free blocks are merged, expand the preceeding one to
> cover all slots.
> + _CounterT::_S_store(_M_skipfield(__pos - __pfree), __pfree +
> __nfree + __n);
> +
> + // And then remove the succseeding node from the free list.
> + const _Free_node __next = _M_slot(__pos + __n)->_M_free;
> + __link_next(__next._M_prev, __next._M_next);
> + __link_prev(__next._M_next, __next._M_prev);
> + }
> + else if (__pfree)
> + // Expand the preceeding slot, already on free list
> + _CounterT::_S_store(_M_skipfield(__pos - __pfree), __pfree +
> __n);
> + else if (__nfree)
> + {
> + // Expand the succseeding slot, adjusting it start position.
> + _CounterT::_S_store(_M_skipfield(__pos), __nfree + __n);
> + _M_slot(__pos)->_M_free = _M_slot(__pos + __n)->_M_free;
> + const _Free_node __node = _M_slot(__pos)->_M_free;
> +
> + // Adjust start position in previous and sucsseding node.
> + __link_next(__node._M_prev, __pos);
> + __link_prev(__node._M_next, __pos);
> + }
> + else
> + {
> + // New [__pos, __pos + __n) is inside occupied slots range,
> + // created a new slot and corresponding free list node.
> + _CounterT::_S_store(_M_skipfield(__pos), __n);
> + _M_slot(__pos)->_M_free = {npos, _M_free_head};
> +
> + // Add new node at begining of free list.
> + __link_prev(_M_free_head, __pos);
> + _M_free_head = __pos;
> + }
> +
> + __pos += __n + __nfree;
> + return false;
> + }
> +
> + // Marks are slots as empty, creating single free node
> + // for range [0, _M_capacity)
> + void
> + _M_clear_slots() noexcept
> + {
> + std::fill_n(_M_skipfield(0), _M_capacity, 0);
> + _CounterT::_S_store(_M_skipfield(0), _M_capacity);
> + _M_slot(0)->_M_free = { npos, npos };
> + _M_free_head = 0;
> + }
> +
> + // Destroys all elements in occupied slot in the node, using
> provided
> + // allocator. Returns the number of destroyed elements.
> + template<typename _TpAlloc>
> + size_t
> + _M_clear_elems(_TpAlloc& __alloc)
> + {
> + size_t __removed = 0;
> + size_t __pos = 0, __first = 0;
> + while (__pos != _M_capacity)
> + if (_M_occupied(__pos))
> + std::allocator_traits<_TpAlloc>::destroy(__alloc,
> _M_elem(__pos++));
> + else
> + {
> + __removed += __pos - __first;
> + __pos += _M_free_count(__pos);
> + __first = __pos;
> + }
> + __removed += __pos - __first;
> + return __removed;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_set_next(_Block* __node) noexcept
> + {
> + _M_next = __node;
> + if (__node)
> + __node->_M_prev = this;
> + }
> + };
> +
> +
> + // Class representing an double linked list of blocks. Manages the block
> + // itself, but not contained elements.
> + //
> + // The blocks are split into two kinds:
> + // * active [_M_first, _M_sent): contains at least one element, visited
> + // by iteration
> + // * reserved (_M_sent, null): no element contained, provded extra
> capacity.
> + // The blocks are moved between list by hiding (active -> reserved) or
> + // exposing (reserved->active).
> + //
> + // Futhermore, the reserved blocks and the subset of active list, that
> contains
> + // at least one free slot, are forming double linked list
> (_M_prev_free, _M_next_free),
> + // pointed out is _M_sent._M_next_free (head), and _M_prev_free (tail),
> but _M_sent
> + // is not part of the list.
> + template<typename _Tp, typename _Alloc>
> + struct _Block_list
> + {
> + static consteval size_t
> + _S_counter_bytes()
> + {
> + constexpr size_t __max = sizeof(_Tp) / 2;
> + if constexpr (__max >= sizeof(size_t))
> + return sizeof(size_t);
> +#ifdef __UINT64_TYPE__
> + else if (__max >= 8)
> + return 8;
> +#endif
> +#ifdef __UINT32_TYPE__
> + else if (__max >= 4)
> + return 4;
> +#endif
> +#ifdef __UINT16_TYPE__
> + else if (__max >= 2)
> + return 2;
> +#endif
> + else
> + return 1;
> + }
> +
> + using _CounterT = _Counter<_S_counter_bytes()>;
> + using _SizeT = typename _CounterT::_SizeT;
> + using _BlockT = _Block<_Tp, _CounterT, typename
> allocator_traits<_Alloc>::pointer>;
> + using _SlotT = typename _BlockT::_Slot;
> +
> + using _SAlloc = typename allocator_traits<_Alloc>::template
> rebind_alloc<_SlotT>;
> + using _SAllocTraits = typename allocator_traits<_Alloc>::template
> rebind_traits<_SlotT>;
> +
> + static consteval hive_limits
> + _S_hard_limits()
> + {
> + size_t __alloc_max;
> + if constexpr (requires { _SAlloc::max_size(); })
> + __alloc_max = _SAlloc::max_size();
> + else
> + __alloc_max = numeric_limits<typename
> _SAllocTraits::size_type>::max()
> + / sizeof(_SlotT);
> +
> + constexpr size_t __counter_max = _CounterT::max_size();
> + if (__alloc_max >= __counter_max +
> _BlockT::_S_extra_slots(__counter_max))
> + return hive_limits(2, __counter_max);
> + else
> + {
> + size_t __max = __alloc_max;
> + if constexpr (alignof(_BlockT) > alignof(_SlotT))
> + __max -= _BlockT::_S_slot_count(alignof(_BlockT) -
> alignof(_SlotT));
> + __max -= _BlockT::_S_slot_count(sizeof(_BlockT));
> +
> + __max = (__max * sizeof(_SlotT)) / (sizeof(_SlotT) + 1);
> + return hive_limits(2, __max);
> + }
> + }
> +
> + static consteval hive_limits
> + _S_default_limits()
> + {
> + // TODO consider if we should do something better
> + auto __hard = _S_hard_limits();
> + if (__hard.max < 16)
> + return __hard;
> + else if (__hard.max < 255)
> + return hive_limits(16, __hard.max);
> + else if (__hard.max < 512)
> + return hive_limits(16, 255);
> + else
> + return hive_limits(16, 512);
> + }
> +
> + _BlockT _M_sent = _BlockT();
> + _BlockT* _M_first = &_M_sent;
> + size_t _M_capacity = 0;
> + [[no_unique_address]] _Alloc _M_alloc;
> + _SizeT _M_min_cap;
> + _SizeT _M_max_cap;
> + _SizeT _M_last_cap;
> +
> + constexpr explicit
> + _Block_list(hive_limits __limits, const _Alloc& __alloc)
> + : _M_alloc(__alloc), _M_min_cap(__limits.min),
> _M_max_cap(__limits.max),
> + _M_last_cap(_M_min_cap)
> + { }
> +
> + ~_Block_list()
> + { _M_drop_blocks(); }
> +
> + void
> + _M_swap_blocks(_Block_list& __other) noexcept
> + {
> + auto __fixup = [](_Block_list& __list)
> + {
> + if (_BlockT* __next = __list._M_sent._M_next)
> + __next->_M_prev = &__list._M_sent;
> + __list._M_link_prev(__list._M_sent, &__list._M_sent);
> + };
> +
> + std::swap(_M_first, __other._M_first);
> + std::swap(_M_sent._M_prev, __other._M_sent._M_prev);
> + std::swap(_M_sent._M_next, __other._M_sent._M_next);
> + std::swap(_M_sent._M_next_free, __other._M_sent._M_next_free);
> + std::swap(_M_sent._M_prev_free, __other._M_sent._M_prev_free);
> + std::swap(_M_capacity, __other._M_capacity);
> + __fixup(__other);
> + __fixup(*this);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + _BlockT*
> + _M_next_free() const noexcept
> + {
> + if (_M_sent._M_next_free)
> + return _M_sent._M_next_free;
> + else
> + return _M_sent._M_next;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_unlink_free(_BlockT* __block) noexcept
> + {
> + _BlockT* __prev = __block->_M_prev_free ? __block->_M_prev_free :
> &_M_sent;
> + _BlockT* __next = __block->_M_next_free ? __block->_M_next_free :
> &_M_sent;
> + __prev->_M_next_free = __block->_M_next_free;
> + __next->_M_prev_free = __block->_M_prev_free;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_append_free(_BlockT* __block) noexcept
> + {
> + __block->_M_next_free = _M_sent._M_next_free;
> + __block->_M_prev_free = nullptr;
> + if (!_M_sent._M_next_free)
> + _M_sent._M_next_free = _M_sent._M_prev_free = __block;
> + else
> + {
> + _M_sent._M_next_free->_M_prev_free = __block;
> + _M_sent._M_next_free = __block;
> + }
> + }
> +
> + // Unlinks to block from the active block list, does update free
> list.
> + [[__gnu__::__always_inline__]]
> + void
> + _M_detach_active(_BlockT* __first, _BlockT* __last)
> + { _M_link_prev(*__first, __last->_M_next); }
> +
> + // Appends blocks to the active blocks list, does not update free
> list.
> + [[__gnu__::__always_inline__]]
> + void
> + _M_append_active(_BlockT* __first, _BlockT* __last)
> + {
> + _M_link_prev(_M_sent, __first);
> + __last->_M_set_next(&_M_sent);
> + }
> +
> + // Move blocks from reserved to active.
> + void
> + _M_expose(_BlockT* __first, _BlockT* __last) noexcept
> + {
> + __first->_M_prev->_M_set_next(__last->_M_next);
> + _M_append_active(__first, __last);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_expose(_BlockT* __block) noexcept
> + { _M_expose(__block, __block); }
> +
> + // Move blocks from active to reserved
> + // pre: [__first, __last) are not on the free list
> + void
> + _M_hide(_BlockT* __first, _BlockT* __last) noexcept
> + {
> + _M_detach_active(__first, __last);
> + _M_append_reserved(__first, __last);
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_hide(_BlockT* __block) noexcept
> + { _M_hide(__block, __block); }
> +
> + _BlockT*
> + _M_reserve_block(size_t __capacity)
> + {
> + _SAlloc __salloc(_M_alloc);
> +
> + _BlockT* __block = _S_allocate_block(__salloc, __capacity);
> + _M_append_reserved(__block, __block);
> + _M_capacity += __capacity;
> + return __block;
> + }
> +
> + _BlockT*
> + _M_reserve_block()
> + {
> + _BlockT* __block = _M_reserve_block(_M_last_cap);
> + if (_M_last_cap < _M_max_cap / 2)
> + _M_last_cap *= 2;
> + else
> + _M_last_cap = _M_max_cap;
> + return __block;
> + }
> +
> + // Dallocate all reserved blocks.
> + void
> + _M_trim_capacity()
> + {
> + _SAlloc __salloc(_M_alloc);
> + _M_capacity -= _S_deallocate_blocks(__salloc, _M_sent._M_next,
> nullptr);
> + _M_sent._M_next = nullptr;
> + }
> +
> + // Deallocate reserved blocks with total capacity no greater
> + // than __remove.
> + void
> + _M_reduce_capacity(size_t __remove)
> + {
> + _SAlloc __salloc(_M_alloc);
> + _BlockT* __prev = &_M_sent;
> + while (__remove >= _M_min_cap)
> + {
> + _BlockT* __last = __prev->_M_next;
> + while(__last && __last->_M_capacity > __remove)
> + __last = __last->_M_next;
> +
> + if (!__last)
> + break;
> +
> + __prev = __last->_M_prev;
> + while (__last && __last->_M_capacity <= __remove)
> + {
> + __remove -= __last->_M_capacity;
> + __last = __last->_M_next;
> + }
> +
> + _M_capacity -= _S_deallocate_blocks(__salloc, __prev->_M_next,
> __last);
> + __prev->_M_set_next(__last);
> + }
> + }
> +
> + // Deallocate reserved blocks for which predicate is true
> + template<typename _Pred>
> + void
> + _M_trim_reserved_if(_Pred __pred)
> + {
> + _SAlloc __salloc(_M_alloc);
> + _BlockT* __prev = &_M_sent;
> + while (true)
> + {
> + _BlockT* __last = __prev->_M_next;
> + while(__last && !__pred(__last))
> + __last = __last->_M_next;
> +
> + if (!__last)
> + break;
> +
> + __prev = __last->_M_prev;
> + while (__last && __pred(__last))
> + __last = __last->_M_next;
> +
> + _M_capacity -= _S_deallocate_blocks(__salloc, __prev->_M_next,
> __last);
> + __prev->_M_set_next(__last);
> + }
> + }
> +
> + // Move active blocks from the __src to the current block list,
> they total
> + // capacity is assumed to be cap.
> + void
> + _M_splice_active(_Block_list& __src, size_t __cap)
> + {
> + _BlockT* __first = __src._M_first;
> + _BlockT* __last = __src._M_sent._M_prev;
> +
> + __src._M_detach_active(__first, __last);
> + __src._M_capacity -= __cap;
> + _M_append_active(__first, __last);
> + _M_capacity += __cap;
> +
> + if (!__src._M_sent._M_next_free)
> + return;
> +
> + // Concate free lists
> + _BlockT* __last_free = _M_sent._M_next_free
> + ? _M_sent._M_prev_free
> + : &_M_sent;
> + __last_free->_M_next_free = __src._M_sent._M_next_free;
> + __src._M_sent._M_next_free->_M_prev_free = _M_sent._M_prev_free;
> + _M_sent._M_prev_free = __src._M_sent._M_prev_free;
> + __src._M_sent._M_next_free = nullptr;
> + __src._M_sent._M_prev_free = nullptr;
> + }
> +
> + // Deallocates all blocks (reserved and used), asumes elements are
> cleared
> + void
> + _M_drop_blocks()
> + {
> + _SAlloc __salloc(_M_alloc);
> + _S_deallocate_blocks(__salloc, _M_first, &_M_sent);
> + _S_deallocate_blocks(__salloc, _M_sent._M_next, nullptr);
> +
> + _M_sent._M_prev_free = _M_sent._M_next_free = nullptr;
> + _M_sent._M_prev = _M_sent._M_next = nullptr;
> + _M_first = &_M_sent;
> +
> + _M_capacity = 0;
> + _M_last_cap = _M_min_cap;
> + }
> +
> + private:
> + static _BlockT*
> + _S_allocate_block(_SAlloc& __alloc, size_t __capacity)
> + {
> + const size_t __count = __capacity +
> _BlockT::_S_extra_slots(__capacity);
> + auto __mem = _SAllocTraits::allocate(__alloc, __count);
> +
> + void* __ptr = std::to_address(__mem);
> + size_t __space = __count * sizeof(_SlotT);
> + if constexpr (alignof(_BlockT) > sizeof(_SlotT))
> + __ptr = std::align(alignof(_BlockT), sizeof(_BlockT), __ptr,
> __space);
> +
> + return ::new(__ptr) _BlockT(__mem, __capacity);
> + }
> +
> + static size_t
> + _S_deallocate_blocks(_SAlloc& __alloc, _BlockT* __from, _BlockT*
> __to)
> + {
> + size_t __capacity = 0;
> + while (__from != __to)
> + {
> + _BlockT* __cur = __from;
> + auto __ptr = __cur->_M_memory();
> + auto __count = __cur->_M_capacity +
> _BlockT::_S_extra_slots(__cur->_M_capacity);
> + __capacity += __cur->_M_capacity;
> + __from = __from->_M_next;
> +
> + // Custom pointer may have non-trivial destructor,
> + // call it before releasing memory.
> + __cur->~_BlockT();
> + _SAllocTraits::deallocate(__alloc, __ptr, __count);
> + }
> + return __capacity;
> + }
> +
> + [[__gnu__::__always_inline__]]
> + void
> + _M_link_prev(_BlockT& __of, _BlockT* __to) noexcept
> + {
> + if (_BlockT* __prev = __of._M_prev)
> + __prev->_M_set_next(__to);
> + else
> + {
> + // __of is first block, set __to as first
> + _M_first = __to;
> + __to->_M_prev = nullptr;
> + }
> + }
> +
> + void
> + _M_append_reserved(_BlockT* __first, _BlockT* __last)
> + {
> + __last->_M_set_next(_M_sent._M_next);
> + _M_sent._M_set_next(__first);
> + }
> + };
> +
> + template<typename _Tp, typename _BlockT>
> + struct _Iterator
> + {
> + using _CounterT = typename _BlockT::_CounterT;
> +
> + public:
> + using iterator_category = bidirectional_iterator_tag;
> + using value_type = _Tp;
> + using pointer = _Tp*;
> + using reference = _Tp&;
> + using size_type = size_t;
> + using difference_type = ptrdiff_t;
> +
> + _Iterator() = default;
> +
> + template<typename _Up>
> + requires is_const_v<_Tp> && is_same_v<_Tp, const _Up>
> + _Iterator(_Iterator<_Up, _BlockT> __other)
> + : _M_block(__other._M_block), _M_pos(__other._M_pos)
> + { }
> +
> + reference
> + operator*() const noexcept
> + { return _M_block->_M_slot(_M_pos)->_M_val; }
> +
> + pointer
> + operator->() const noexcept
> + { return _M_block->_M_elem(_M_pos); }
> +
> + _Iterator&
> + operator++()
> + {
> + ++_M_pos;
> + if (_M_pos != _M_block->_M_capacity)
> + {
> + if (_M_block->_M_occupied(_M_pos))
> + return *this;
> +
> + _M_pos +=
> _CounterT::_S_load_fwd(_M_block->_M_skipfield(_M_pos));
> + if (_M_pos != _M_block->_M_capacity)
> + return *this;
> + }
> +
> + _M_block = _M_block->_M_next;
> + _M_pos = _M_block->_M_first_occupied();
> + return *this;
> + }
> +
> + _Iterator
> + operator++(int)
> + {
> + _Iterator __res = *this;
> + ++*this;
> + return __res;
> + }
> +
> + _Iterator&
> + operator--()
> + {
> + if (_M_pos)
> + {
> + --_M_pos;
> + if (_M_block->_M_occupied(_M_pos))
> + return *this;
> +
> + if (_M_pos)
> + {
> + size_t __gap =
> _CounterT::_S_load_bwd(_M_block->_M_skipfield(_M_pos));
> + if (_M_pos >= __gap)
> + {
> + _M_pos -= __gap;
> + return *this;
> + }
> + }
> + }
> +
> + _M_block = _M_block->_M_prev;
> + __glibcxx_assert(_M_block);
> + _M_pos = _M_block->_M_capacity - 1;
> + if (_M_block->_M_occupied(_M_pos))
> + return *this;
> +
> + _M_pos -= _CounterT::_S_load_bwd(_M_block->_M_skipfield(_M_pos));
> + return *this;
> + }
> +
> + _Iterator
> + operator--(int)
> + {
> + _Iterator __res = *this;
> + --*this;
> + return __res;
> + }
> +
> + friend bool operator==(_Iterator, _Iterator) = default;
> +
> + private:
> + explicit
> + _Iterator(const _BlockT* __block)
> + : _M_block(__block), _M_pos(__block->_M_first_occupied())
> + { }
> +
> + explicit
> + _Iterator(const _BlockT* __block, size_t __pos)
> + : _M_block(__block), _M_pos(__pos)
> + { }
> +
> + const _BlockT* _M_block = nullptr;
> + size_t _M_pos = 0;
> +
> + friend struct _Iterator<const _Tp, _BlockT>;
> + template<typename, typename>
> + friend class std::hive;
> + };
> +} // namespace __hive
> +
> +template<typename _Tp, typename _Alloc>
> + class hive
> + {
> + using _BlockListT = __hive::_Block_list<_Tp, _Alloc>;
> + using _BlockT = typename _BlockListT::_BlockT;
> + using _SlotT = typename _BlockListT::_SlotT;
> + using _CounterT = typename _BlockListT::_CounterT;
> + using _AllocT = allocator_traits<_Alloc>;
> +
> + public:
> + using value_type = _Tp;
> + using allocator_type = _Alloc;
> + using pointer = typename _AllocT::pointer;
> + using const_pointer = typename _AllocT::const_pointer;
> + using reference = value_type&;
> + using const_reference = const value_type&;
> + using size_type = size_t;
> + using difference_type = ptrdiff_t;
> + using iterator = __hive::_Iterator<_Tp, _BlockT>;
> + using const_iterator = __hive::_Iterator<const _Tp, _BlockT>;
> + using reverse_iterator = std::reverse_iterator<iterator>;
> + using const_reverse_iterator = std::reverse_iterator<const_iterator>;
> +
> + constexpr
> + hive() noexcept(noexcept(_Alloc()))
> + : _M_blocks(block_capacity_default_limits(), _Alloc())
> + { }
> +
> + constexpr explicit
> + hive(const _Alloc& __alloc) noexcept
> + : _M_blocks(block_capacity_default_limits(), __alloc)
> + { }
> +
> + constexpr explicit
> + hive(hive_limits __limits)
> + : _M_blocks(__limits, _Alloc())
> + { }
> +
> + constexpr
> + hive(hive_limits __limits, const _Alloc& __alloc)
> + : _M_blocks(__limits, __alloc)
> + { }
> +
> + explicit
> + hive(size_type __count, const _Alloc& __alloc = _Alloc())
> + : hive(__alloc)
> + { _M_insert_n(__count, _ValueInitTag()); }
> +
> + hive(size_type __count, hive_limits __limits,
> + const _Alloc& __alloc = _Alloc())
> + : hive(_S_clamp_limits(__limits), __alloc)
> + { _M_insert_n(__count, _ValueInitTag()); }
> +
> + hive(size_type __count, const _Tp& __value,
> + const _Alloc& __alloc = _Alloc())
> + : hive(__alloc)
> + { _M_insert_n(__count, __value); }
> +
> + hive(size_type __count, const _Tp& __value,
> + hive_limits __limits, const _Alloc& __alloc = _Alloc())
> + : hive(_S_clamp_limits(__limits), __alloc)
> + { _M_insert_n(__count, __value); }
> +
> + hive(initializer_list<_Tp> __il, const _Alloc& __alloc = _Alloc())
> + : hive(__alloc)
> + { insert(__il); }
> +
> + hive(initializer_list<_Tp> __il, hive_limits __limits,
> + const _Alloc& __alloc = _Alloc())
> + : hive(_S_clamp_limits(__limits), __alloc)
> + { insert(__il); }
> +
> + template<__has_input_iter_cat _InputIterator>
> + hive(_InputIterator __first, _InputIterator __last,
> + const _Alloc& __alloc = _Alloc())
> + : hive(__alloc)
> + { insert(__first, __last); }
> +
> + template<__has_input_iter_cat _InputIterator>
> + hive(_InputIterator __first, _InputIterator __last,
> + hive_limits __limits, const _Alloc& __alloc = _Alloc())
> + : hive(_S_clamp_limits(__limits), __alloc)
> + { insert(__first, __last); }
> +
> + template<__detail::__container_compatible_range<_Tp> _Rg>
> + hive(from_range_t, _Rg&& __rg, const _Alloc& __alloc = _Alloc())
> + : hive(__alloc)
> + { insert_range(__rg); }
> +
> + template<__detail::__container_compatible_range<_Tp> _Rg>
> + hive(from_range_t, _Rg&& __rg, hive_limits __limits,
> + const _Alloc& __alloc = _Alloc())
> + : hive(_S_clamp_limits(__limits), __alloc)
> + { insert_range(__rg); }
> +
> + hive(const hive& __other)
> + : hive(
> + __other.block_capacity_limits(),
> +
> _AllocT::select_on_container_copy_construction(__other.get_allocator()))
> + { _M_insert_range(__other); }
> +
> + hive(const hive& __other, const type_identity_t<_Alloc>& __alloc)
> + : hive(__other.block_capacity_limits(), __alloc)
> + { _M_insert_range(__other); }
> +
> + hive(hive&& __other) noexcept
> + : hive(__other.block_capacity_limits(), __other.get_allocator())
> + {
> + _M_blocks._M_swap_blocks(__other._M_blocks);
> + _M_size = __other._M_size;
> + __other._M_size = 0;
> + }
> +
> + hive(hive&& __other, const type_identity_t<_Alloc>& __alloc)
> + noexcept(_AllocT::is_always_equal::value)
> + : hive(__other.block_capacity_limits(), __alloc)
> + {
> + if constexpr (!_AllocT::is_always_equal::value)
> + if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> + {
> + insert(std::make_move_iterator(__other.begin()),
> + std::make_move_iterator(__other.end()));
> + __other.clear();
> + return;
> + }
> +
> + _M_blocks._M_swap_blocks(__other._M_blocks);
> + _M_size = __other._M_size;
> + __other._M_size = 0;
> + }
> +
> + hive& operator=(const hive& __other)
> + {
> + if (this == std::addressof(__other))
> + return *this;
> +
> + if constexpr
> (_AllocT::propagate_on_container_copy_assignment::value)
> + {
> + if constexpr (!_AllocT::is_always_equal::value)
> + if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> + _M_clear_and_trim();
> + _M_blocks._M_alloc = __other._M_blocks._M_alloc;
> + }
> +
> + _M_assign_range(__other);
> + return *this;
> + }
> +
> + hive& operator=(hive&& __other)
> +
> noexcept(allocator_traits<_Alloc>::propagate_on_container_move_assignment::value
> + || allocator_traits<_Alloc>::is_always_equal::value)
> + {
> + if constexpr
> (!_AllocT::propagate_on_container_move_assignment::value
> + && !_AllocT::is_always_equal::value)
> + if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> + {
> + assign(std::make_move_iterator(__other.begin()),
> + std::make_move_iterator(__other.end()));
> + __other.clear();
> + return *this;
> + }
> +
> + if constexpr
> (_AllocT::propagate_on_container_move_assignment::value)
> + {
> + if constexpr (!_AllocT::is_always_equal::value)
> + if (_M_blocks._M_alloc != __other._M_blocks._M_alloc)
> + _M_clear_and_trim();
> + _M_blocks._M_alloc = __other._M_blocks._M_alloc;
> + }
> +
> + // Capacity limits are swapped, so the blocks we transfered are
> within them.
> + _M_swap(__other);
> + __other.clear();
> + return *this;
> + }
> +
> + hive& operator=(initializer_list<_Tp> __il)
> + {
> + assign_range(__il);
> + return *this;
> + }
> +
> + void
> + swap(hive& __other)
> + noexcept(allocator_traits<_Alloc>::propagate_on_container_swap::value
> + || allocator_traits<_Alloc>::is_always_equal::value)
> + {
> + if constexpr (_AllocT::propagate_on_container_swap::value)
> + std::swap(_M_blocks._M_alloc, __other._M_blocks._M_alloc);
> + else if constexpr (!_AllocT::is_always_equal::value)
> + __glibcxx_assert(_M_blocks._M_alloc == __other._M_blocks._M_alloc);
> + _M_swap(__other);
> + }
> +
> + ~hive()
> + { _M_clear_and_trim(); }
> +
> + template<__detail::__container_compatible_range<_Tp> _Rg>
> + void
> + assign_range(_Rg&& __rg)
> + {
> + if constexpr (ranges::contiguous_range<_Rg> &&
> ranges::sized_range<_Rg>)
> + {
> + span<remove_reference_t<ranges::range_reference_t<_Rg>>>
> + __span(__rg);
> + _M_assign_range(__span);
> + }
> + else
> + _M_assign_range(__rg);
> + }
> +
> + template<__has_input_iter_cat _InputIterator>
> + void assign(_InputIterator __first, _InputIterator __last)
> + {
> + if constexpr (contiguous_iterator<_InputIterator>)
> + {
> + span<remove_reference_t<iter_reference_t<_InputIterator>>>
> + __span(__first, __last);
> + _M_assign_range(__span);
> + }
> + else
> + {
> + ranges::subrange<_InputIterator> __range(__first, __last);
> + _M_assign_range(__range);
> + }
> + }
> +
> + void
> + assign(initializer_list<_Tp> __il)
> + {
> + span<const _Tp> __span(__il);
> + _M_assign_range(__span);
> + }
> +
> + void
> + assign(size_type __count, const _Tp& __val)
> + {
> + assign(std::__make_repeat_iterator(__val, size_type(0)),
> + std::__make_repeat_iterator(__val, __count));
> + }
> +
> + allocator_type
> + get_allocator() const noexcept
> + { return _M_blocks._M_alloc; }
> +
> + iterator
> + begin() noexcept
> + { return iterator(_M_blocks._M_first); }
> +
> + iterator
> + end() noexcept
> + { return iterator(&_M_blocks._M_sent, 0); }
> +
> + const_iterator
> + begin() const noexcept
> + { return const_iterator(_M_blocks._M_first); }
> +
> + const_iterator
> + end() const noexcept
> + { return const_iterator(&_M_blocks._M_sent, 0); }
> +
> + reverse_iterator
> + rbegin() noexcept
> + { return reverse_iterator(end()); }
> +
> + reverse_iterator
> + rend() noexcept
> + { return reverse_iterator(begin()); }
> +
> + const_reverse_iterator
> + rbegin() const noexcept
> + { return const_reverse_iterator(end()); }
> +
> + const_reverse_iterator
> + rend() const noexcept
> + { return const_reverse_iterator(begin()); }
> +
> + const_iterator
> + cbegin() const noexcept
> + { return begin(); }
> +
> + const_iterator
> + cend() const noexcept
> + { return end(); }
> +
> + const_reverse_iterator
> + crbegin() const noexcept
> + { return rbegin(); }
> +
> + const_reverse_iterator
> + crend() const noexcept
> + { return rend(); }
> +
> + bool
> + empty() const noexcept
> + { return _M_size == 0; }
> +
> + size_type
> + size() const noexcept
> + { return _M_size; }
> +
> + size_type
> + capacity() const noexcept
> + { return _M_blocks._M_capacity; }
> +
> + void
> + reserve(size_type __n)
> + { _M_reserve(__n, block_capacity_limits()); }
> +
> + void
> + trim_capacity()
> + { _M_blocks._M_trim_capacity(); }
> +
> + void
> + trim_capacity(size_type __keep)
> + {
> + if (__keep >= capacity())
> + return;
> + else if (__keep <= size())
> + _M_blocks._M_trim_capacity();
> + else
> + _M_blocks._M_reduce_capacity(capacity() - __keep);
> + }
> +
> + // shrink to fit
> + void
> + shrink_to_fit()
> + {
> + trim_capacity();
> + // No or single partially free block, we size matches capacity
> + if (size() == capacity())
> + return;
> +
> + _RelocateGuard __guard(*this);
> + // Visit blocks in reserve as they normally go from largest to
> smallest.
> + _BlockT* __block = _M_blocks._M_sent._M_prev;
> + _BlockT* __lowest_kept = nullptr;
> + while (__block)
> + {
> + _BlockT* __prev = __block->_M_prev;
> + if (_M_blocks._M_capacity - __block->_M_capacity >= _M_size)
> + __guard._M_move_active(__block);
> + else if (!__lowest_kept || __lowest_kept->_M_capacity >
> __block->_M_capacity)
> + __lowest_kept = __block;
> + __block = __prev;
> + }
> +
> + // Extra capacity is over minium block size, replace minimum block.
> + if (_M_blocks._M_capacity - _M_size >= _M_blocks._M_min_cap)
> + {
> + __guard._M_move_active(__lowest_kept);
> + reserve(_M_size);
> + }
> +
> + __guard._M_transfer();
> + }
> +
> + void
> + reshape(hive_limits __limits)
> + {
> + __limits = _S_clamp_limits(__limits);
> + auto __outside_limits = [&__limits](const _BlockT* __block)
> + {
> + size_t __cap = __block->_M_capacity;
> + return __cap < __limits.min || __cap > __limits.max;
> + };
> +
> + _M_blocks._M_trim_reserved_if(__outside_limits);
> +
> + _RelocateGuard __guard(*this);
> + _BlockT* __block = _M_blocks._M_first;
> + while (!__block->_M_sentinel())
> + {
> + _BlockT* __next = __block->_M_next;
> + if (__outside_limits(__block))
> + __guard._M_move_active(__block);
> + __block = __next;
> + }
> +
> + // Expand limits, so both new and old blocks are within
> + // them, as in case of exception both of them may remain.
> + if (__limits.min < _M_blocks._M_min_cap)
> + _M_blocks._M_min_cap = __limits.min;
> + if (__limits.max > _M_blocks._M_max_cap)
> + _M_blocks._M_max_cap = __limits.max;
> +
> + _M_reserve(_M_size, __limits);
> + __guard._M_transfer();
> + _M_blocks._M_min_cap = __limits.min;
> + _M_blocks._M_max_cap = __limits.max;
> + }
> +
> +
> + constexpr hive_limits
> + block_capacity_limits() const noexcept
> + { return hive_limits(_M_blocks._M_min_cap, _M_blocks._M_max_cap); }
> +
> + static constexpr hive_limits
> + block_capacity_default_limits() noexcept
> + { return _BlockListT::_S_default_limits(); }
> +
> + static constexpr hive_limits
> + block_capacity_hard_limits() noexcept
> + { return _BlockListT::_S_hard_limits(); }
> +
> + static constexpr
> + bool is_within_hard_limits(hive_limits __limits) noexcept
> + {
> + hive_limits __hard = block_capacity_hard_limits();
> + return __hard.min <= __limits.min
> + && __limits.min <= __limits.max
> + && __limits.max <= __hard.max;
> + }
> +
> + template<typename... _Args>
> + iterator
> + emplace(_Args&&... __args)
> + {
> + _BlockT* __block;
> + if (_M_size == capacity())
> + __block = _M_blocks._M_reserve_block();
> + else
> + __block = _M_blocks._M_next_free();
> +
> + _InsertGuard __guard(*this, __block);
> + __guard.construct(_M_blocks._M_alloc,
> std::forward<_Args>(__args)...);
> + __guard._M_commit();
> + return iterator(__block, __guard._M_res._M_pos);
> + }
> +
> + iterator
> + insert(const _Tp& __val)
> + { return emplace(__val); }
> +
> + iterator
> + insert(_Tp&& __val)
> + { return emplace(std::move(__val)); }
> +
> + template<typename... _Args>
> + iterator
> + emplace_hint(const_iterator, _Args&&... __args)
> + { return emplace(std::forward<_Args>(__args)...); }
> +
> + iterator
> + insert(const_iterator, const _Tp& __val)
> + { return emplace(__val); }
> +
> + iterator
> + insert(const_iterator, _Tp&& __val)
> + { return emplace(std::move(__val)); }
> +
> + template<__detail::__container_compatible_range<_Tp> _Rg>
> + void
> + insert_range(_Rg&& __rg)
> + {
> + if constexpr (ranges::contiguous_range<_Rg> &&
> ranges::sized_range<_Rg>)
> + {
> + span<remove_reference_t<ranges::range_reference_t<_Rg>>>
> + __span(__rg);
> + _M_insert_range(__span);
> + }
> + else
> + _M_insert_range(__rg);
> + }
> +
> + template<__has_input_iter_cat _InputIterator>
> + void insert(_InputIterator __first, _InputIterator __last)
> + {
> + if constexpr (contiguous_iterator<_InputIterator>)
> + {
> + span<remove_reference_t<iter_reference_t<_InputIterator>>>
> + __span(__first, __last);
> + _M_insert_range(__span);
> + }
> + else
> + {
> + ranges::subrange<_InputIterator> __range(__first, __last);
> + _M_insert_range(__range);
> + }
> + }
> +
> + void
> + insert(initializer_list<_Tp> __il)
> + {
> + span<const _Tp> __span(__il);
> + _M_insert_range(__span);
> + }
> +
> + void
> + insert(size_type __count, const _Tp& __val)
> + { _M_insert_n(__count, __val); }
> +
> + iterator
> + erase(const_iterator __it)
> + {
> + _BlockT* __block = const_cast<_BlockT*>(__it._M_block);
> + _BlockT* __next_block = __block->_M_next;
> + size_t __pos = __it._M_pos;
> +
> + if (__block->_M_full())
> + _M_blocks._M_append_free(__block);
> +
> + _AllocT::destroy(_M_blocks._M_alloc, __block->_M_elem(__pos));
> + _M_size -= 1;
> +
> + if (__block->_M_release_slots(__pos, 1))
> + {
> + _M_blocks._M_unlink_free(__block);
> + _M_blocks._M_hide(__block);
> + }
> +
> + if (__pos != __block->_M_capacity)
> + return iterator(__block, __pos);
> + else
> + return iterator(__next_block);
> + }
> +
> + iterator
> + erase(const_iterator __first, const_iterator __last)
> + {
> + _BlockT* __fblock = const_cast<_BlockT*>(__first._M_block);
> + _BlockT* __lblock = const_cast<_BlockT*>(__last._M_block);
> + if (__fblock == __lblock)
> + {
> + // Erase of range in single block, clear elements if any.
> + if (__first._M_pos != __last._M_pos)
> + _M_erase_range(__fblock, __first._M_pos, __last._M_pos);
> + return iterator(__last._M_block, __last._M_pos);
> + }
> +
> + // Remove any elements designated in last block
> + if (auto __lfirst = __lblock->_M_first_occupied(); __last._M_pos !=
> __lfirst)
> + _M_erase_range(__lblock, __lfirst, __last._M_pos);
> +
> + // If __first block is not set to be fully cleared, remove
> designated elements
> + if (__first._M_pos != __fblock->_M_first_occupied())
> + {
> + _M_erase_range(__fblock, __first._M_pos, __fblock->_M_capacity);
> + __fblock = __fblock->_M_next;
> + if (__fblock == __lblock)
> + return iterator(__last._M_block, __last._M_pos);
> + }
> +
> + // Clear elements in fully erased block, and move to reserved list.
> + _M_clear(__fblock, __lblock);
> + _M_blocks._M_hide(__fblock, __lblock->_M_prev);
> + return iterator(__last._M_block, __last._M_pos);
> + }
> +
> + void
> + clear()
> + {
> + if (empty())
> + return;
> +
> + _M_clear(_M_blocks._M_first, &_M_blocks._M_sent);
> + _M_blocks._M_hide(_M_blocks._M_first, _M_blocks._M_sent._M_prev);
> + }
> +
> + void
> + splice(hive& __other)
> + {
> + __glibcxx_assert(get_allocator() == __other.get_allocator());
> + if (this == std::addressof(__other)) [[unlikely]]
> + {
> + __glibcxx_assert(this == std::addressof(__other));
> + return;
> + }
> +
> + if (__other.empty())
> + return;
> +
> + _BlockListT& __src = __other._M_blocks;
> + size_t __moved_cap = 0;
> + for (const _BlockT* __block = __other._M_blocks._M_first;
> + !__block->_M_sentinel(); __block = __block->_M_next)
> + {
> + const auto __cap = __block->_M_capacity;
> + if (__cap < _M_blocks._M_min_cap || __cap >
> _M_blocks._M_max_cap)
> + std::__throw_length_error("hive::splice");
> + __moved_cap += __cap;
> + }
> +
> + _M_blocks._M_splice_active(__other._M_blocks, __moved_cap);
> + _M_size += __other._M_size;
> + __other._M_size = 0;
> + }
> +
> + void
> + splice(hive&& __other)
> + { splice(__other); }
> +
> + template<class _Predicate = equal_to<_Tp>>
> + size_type
> + unique(_Predicate __bin_pred = _Predicate())
> + {
> + _Tp* __last = nullptr;
> + auto __pred = [&__last, &__bin_pred](_Tp& __e)
> + {
> + if (__last) [[likely]]
> + if (__bin_pred(*__last, __e))
> + return true;
> +
> + __last = std::addressof(__e);
> + return false;
> + };
> + return _M_erase_if(__pred);
> + }
> +
> + // TODO: sort
> +
> + iterator
> + get_iterator(const_pointer __ptr) noexcept
> + {
> + auto __eptr = reinterpret_cast<const
> _SlotT*>(std::to_address(__ptr));
> + return _M_get_iterator(__eptr);
> + }
> +
> + const_iterator
> + get_iterator(const_pointer __ptr) const noexcept
> + {
> + auto __eptr = reinterpret_cast<const
> _SlotT*>(std::to_address(__ptr));
> + return _M_get_iterator(__eptr);
> + }
> +
> + private:
> + // Used to value initialize elements
> + struct _ValueInitTag
> + { };
> +
> + // Handles insertion of the elements to the single free node in the
> block.
> + // In case of exceptions commits already constructed elements.
> + struct _InsertGuard
> + {
> + hive& _M_self;
> + _BlockT* _M_block;
> + typename _BlockT::_Reservation _M_res;
> + size_t _M_count = 0;
> +
> + _InsertGuard(hive& __self, _BlockT* __block)
> + : _M_self(__self)
> + , _M_block(__block)
> + , _M_res(_M_block->_M_reserve_slots())
> + { }
> +
> + [[__gnu__::__always_inline__]]
> + bool
> + _M_filled() const noexcept
> + { return _M_count == _M_res._M_capacity; }
> +
> + template<typename... _Args>
> + void
> + construct(_Alloc& __alloc, _Args&&... __args)
> + {
> + auto* __space = _M_block->_M_elem(_M_res._M_pos + _M_count);
> + _AllocT::construct(__alloc, __space,
> std::forward<_Args>(__args)...);
> + ++_M_count;
> + }
> +
> + void
> + construct(_Alloc& __alloc, _ValueInitTag)
> + { construct(__alloc); }
> +
> + void
> + _M_commit()
> + {
> + if (_M_count == 0) [[unlikely]]
> + // Restore free slot node, that maybe overriden by
> + // cosntruction attempt, block status does not change.
> + _M_block->_M_commit_slots(_M_res, 0);
> + else if (_M_res._M_capacity == _M_block->_M_capacity)
> + {
> + // Insertion into reserved block expose it to iteration,
> + // and link to partially free list if not filled.
> + _M_self._M_blocks._M_expose(_M_block);
> + if (!_M_block->_M_commit_slots(_M_res, _M_count))
> + _M_self._M_blocks._M_append_free(_M_block);
> + }
> + else if (_M_block->_M_commit_slots(_M_res, _M_count))
> + // Unlink active block that was filled out.
> + _M_self._M_blocks._M_unlink_free(_M_block);
> +
> + _M_self._M_size += _M_count;
> + _M_block = nullptr;
> + }
> +
> + ~_InsertGuard()
> + {
> + if (_M_block)
> + _M_commit();
> + }
> + };
> +
> + // Handles relocation of elements between blocks inside the same hive
> structure.
> + // The blocks from which elements needs to be removed, are attached
> to the _M_aside
> + // member, then transfered block by block by _M_transfer function
> (they emptied block
> + // are linked as reverved in _M_blocks), and deallocated in guard
> destructuctor.
> + //
> + // In case if exception is throw during transfer, the destructor
> splices the blocks
> + // back to the _M_self, and if the __first transfered back block have
> moved-from
> + // elements remove them. For that reason, the elements inside the
> blocks are always
> + // included in hvie size (and substracted when removed).
> + struct _RelocateGuard
> + {
> + hive& _M_self;
> + _BlockListT _M_aside;
> + move_iterator<const_iterator> _M_last;
> +
> + _RelocateGuard(hive& __self)
> + : _M_self(__self)
> + , _M_aside(__self.block_capacity_limits(), __self.get_allocator())
> + , _M_last(const_iterator(&_M_aside._M_sent, 0))
> + { }
> +
> + ~_RelocateGuard()
> + {
> + _M_aside._M_trim_capacity();
> + if (_M_last.base() == const_iterator(&_M_aside._M_sent, 0))
> + return;
> +
> + _BlockT* __last = _M_aside._M_first;
> + _M_self._M_blocks._M_splice_active(_M_aside, _M_aside._M_capacity);
> + // If exception was thrown during transfer from block, the starting
> + // elements of the block until _M_last will be in moved from state,
> + // erase them.
> + _M_self.erase(const_iterator(__last), _M_last.base());
> + }
> +
> + void
> + _M_move_active(_BlockT* __block)
> + {
> + _M_self._M_blocks._M_detach_active(__block, __block);
> + _M_self._M_blocks._M_capacity -= __block->_M_capacity;
> + _M_aside._M_append_active(__block, __block);
> + _M_aside._M_capacity += __block->_M_capacity;
> +
> + if (__block->_M_full())
> + return;
> +
> + _M_self._M_blocks._M_unlink_free(__block);
> + _M_aside._M_append_free(__block);
> + }
> +
> + void
> + _M_transfer()
> + {
> + _BlockT* __srcblock = _M_aside._M_first;
> + _M_last = make_move_iterator(const_iterator(__srcblock));
> + while (!__srcblock->_M_sentinel())
> + {
> + _BlockT* __nextblock = __srcblock->_M_next;
> + auto __nextit =
> make_move_iterator(const_iterator(__nextblock));
> +
> + while (_BlockT* __dstblock = _M_self._M_blocks._M_next_free())
> + if (_M_self._M_fill_block(__dstblock, _M_last, __nextit))
> + break;
> +
> + if (!__srcblock->_M_full())
> + _M_aside._M_unlink_free(__srcblock);
> + _M_self._M_size -=
> __srcblock->_M_clear_elems(_M_self._M_blocks._M_alloc);
> + _M_aside._M_hide(__srcblock);
> +
> + __srcblock = __nextblock;
> + _M_last = __nextit;
> + }
> + }
> + };
> +
> + // Checks the user provided limits, agains defined limits. The
> behavior of
> + // erronous case (limits are not withing hard limits) is to:
> + // * use default limits if limits does not form a range
> + // * clamp provided value to the hard limits.
> + static constexpr hive_limits
> + _S_clamp_limits(hive_limits __limits)
> + {
> + __glibcxx_assert(is_within_hard_limits(__limits));
> + if (__limits.min > __limits.max) [[unlikely]]
> + return block_capacity_default_limits();
> +
> + static constexpr auto __hard = block_capacity_hard_limits();
> + if (__limits.max <= __hard.min) [[unlikely]]
> + return hive_limits(__hard.min, __hard.min);
> + if (__limits.min >= __hard.max) [[unlikely]]
> + return hive_limits(__hard.max, __hard.max);
> +
> + if (__limits.min < __hard.min) [[unlikely]]
> + __limits.min = __hard.min;
> + if (__limits.max > __hard.max) [[unlikely]]
> + __limits.max = __hard.max;
> + return __limits;
> + }
> +
> + iterator
> + _M_get_iterator(const _SlotT* __ptr) const
> + {
> + std::less<const _SlotT*> __ptrlt;
> + for (_BlockT* __block = _M_blocks._M_first;
> + !__block->_M_sentinel(); __block = __block->_M_next)
> + if (auto __pos = __block->_M_contains(__ptr); __pos !=
> _BlockT::npos)
> + if (__block->_M_occupied(__pos))
> + return iterator(__block, __pos);
> + else
> + break;
> +
> + // Standard says that the behavior is undefined in case when __ptr
> does
> + // not point to container. We return end() iterator for cases that
> can
> + // be detected.
> + __glibcxx_assert(false && "pointer does not point to element in
> container");
> + return iterator(&_M_blocks._M_sent, 0);
> + }
> +
> + void
> + _M_swap(hive& __other) noexcept
> + {
> + std::swap(_M_blocks._M_min_cap, __other._M_blocks._M_min_cap);
> + std::swap(_M_blocks._M_max_cap, __other._M_blocks._M_max_cap);
> + std::swap(_M_blocks._M_last_cap, __other._M_blocks._M_last_cap);
> +
> + _M_blocks._M_swap_blocks(__other._M_blocks);
> + std::swap(_M_size, __other._M_size);
> + }
> +
> + void
> + _M_reserve(size_type __n, hive_limits __limits)
> + {
> + if (__n <= capacity())
> + return;
> +
> + // Rerved blocks are added to the front of the list, so we append
> larger
> + // first, so they will be used from smallest to largest.
> + for (__n -= capacity(); __n / 2 >= __limits.max; __n -=
> __limits.max)
> + _M_blocks._M_reserve_block(__limits.max);
> +
> + if (__n >= __limits.max)
> + {
> + _M_blocks._M_last_cap = __limits.max;
> +
> + // If last block would be smaller than minum limit, try to
> + // split last two blocks equally, to avoid going over capacity
> + if ((__n > __limits.max)
> + && (__n < __limits.max + __limits.min)
> + && (__n >= 2 * __limits.min))
> + {
> + _M_blocks._M_reserve_block(__n - __n / 2);
> + _M_blocks._M_reserve_block(__n / 2);
> + return;
> + }
> +
> + _M_blocks._M_reserve_block(__limits.max);
> + __n -= __limits.max;
> + }
> +
> + if (__n >= __limits.min)
> + _M_blocks._M_reserve_block(__n);
> + else if (__n > 0)
> + _M_blocks._M_reserve_block(__limits.min);
> + }
> +
> +
> + // Returns position of element after last inserted element, or
> _M_capacity otherwise.
> + template<typename _Iterator, typename _Sentinel>
> + size_t
> + _M_fill_free_head(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> + {
> + _InsertGuard __guard(*this, __block);
> + while ((__first != __last) && !__guard._M_filled())
> + {
> + __guard.construct(_M_blocks._M_alloc, *__first);
> + ++__first;
> + }
> + __guard._M_commit();
> + return __guard._M_res._M_pos + __guard._M_res._M_capacity;
> + }
> +
> + // Returns true if the whole range was inserted.
> + template<typename _Iterator, typename _Sentinel>
> + bool
> + _M_fill_block(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> + {
> + while (!__block->_M_full())
> + {
> + _M_fill_free_head(__block, __first, __last);
> + if (__first == __last)
> + return true;
> + }
> + return false;
> + }
> +
> + template<typename _Rg>
> + void
> + _M_insert_range(_Rg& __rg)
> + {
> + auto __it = std::ranges::begin(__rg);
> + auto __end = std::ranges::end(__rg);
> + if (__it == __end) [[unlikely]]
> + return;
> +
> + if constexpr (ranges::sized_range<_Rg>)
> + {
> + const auto __new_size = _M_size + size_t(ranges::size(__rg));
> + reserve(__new_size);
> +
> + // Fillout initial blocks, we do not need to check against end
> + // TODO: should we store freee space in block, for better
> condition
> + for (_BlockT* __block = _M_blocks._M_next_free();
> + _M_size + __block->_M_capacity < __new_size;
> + __block = _M_blocks._M_next_free())
> + _M_fill_block(__block, __it, unreachable_sentinel);
> +
> + // For the black that we are not sure will be filled fully,
> + // check against end
> + while (_BlockT* __block = _M_blocks._M_next_free())
> + if (_M_fill_block(__block, __it, __end))
> + return;
> + }
> + else
> + {
> + // Fill out empty spaces in existing blocks.
> + while (_BlockT* __block = _M_blocks._M_next_free())
> + if (_M_fill_block(__block, __it, __end))
> + return;
> +
> + // Allocate new blocks for remaining elements
> + while (true)
> + {
> + _BlockT* __block = _M_blocks._M_reserve_block();
> + if (_M_fill_block(__block, __it, __end))
> + return;
> + }
> + }
> + }
> +
> + template<typename _Up>
> + void
> + _M_insert_n(size_type __count, const _Up& __val)
> + {
> + insert(std::__make_repeat_iterator(__val, size_type(0)),
> + std::__make_repeat_iterator(__val, __count));
> + }
> +
> + // Returns position of element after last assigned/inserted element,
> or _M_capacity otherwise.
> + template<typename _Iterator, typename _Sentinel>
> + size_t
> + _M_assign_block(_BlockT* __block, _Iterator& __first, _Sentinel
> __last)
> + {
> + size_t __pos = 0;
> + while ((__pos != __block->_M_capacity) && (__first != __last))
> + if (__block->_M_occupied(__pos))
> + {
> + *__block->_M_elem(__pos++) = *__first;
> + ++__first;
> + }
> + else
> + {
> + // Preserve order of elements, by inserting at that position.
> + __block->_M_move_free_head(__pos);
> + __pos = _M_fill_free_head(__block, __first, __last);
> + }
> + return __pos;
> + }
> +
> + template<__detail::__container_compatible_range<_Tp> _Rg>
> + void
> + _M_assign_range(_Rg& __rg)
> + {
> + if (empty())
> + return _M_insert_range(__rg);
> +
> + auto __it = std::ranges::begin(__rg);
> + auto __end = std::ranges::end(__rg);
> + if (__it == __end)
> + return clear();
> +
> + auto __erase_from = [&](_BlockT* __block, size_t __pos)
> + {
> + if (__pos == __block->_M_capacity)
> + erase(const_iterator(__block->_M_next), end());
> + else if (__block->_M_occupied(__pos))
> + erase(const_iterator(__block, __pos), end());
> + else
> + {
> + // Move to first occupied slot or end of block
> + __pos += __block->_M_free_count(__pos);
> + if (__pos == __block->_M_capacity)
> + erase(const_iterator(__block->_M_next), end());
> + else
> + erase(const_iterator(__block, __pos), end());
> + }
> + };
> +
> + if constexpr (ranges::sized_range<_Rg>)
> + {
> + const auto __size = size_t(ranges::size(__rg));
> + reserve(__size);
> +
> + size_t __assigned = 0;
> + // Assing/inserter elements to existing active blocks
> + for (_BlockT* __block = _M_blocks._M_first;
> + !__block->_M_sentinel(); __block = __block->_M_next)
> + if (__assigned == __size)
> + {
> + erase(const_iterator(__block), end());
> + return;
> + }
> + else if (__assigned + __block->_M_capacity > __size)
> + {
> + // Block is partially filled, insert until end,
> + // and then erase rest of the container elements.
> + size_t __last = _M_assign_block(__block, __it, __end);
> + __erase_from(__block, __last);
> + return;
> + }
> + else
> + {
> + // Fully assign block, we do not need to check end
> + _M_assign_block(__block, __it, unreachable_sentinel);
> + __assigned += __block->_M_capacity;
> + }
> +
> + // Insert remaining elements
> + insert_range(ranges::subrange(std::move(__it), __end,
> + __size - __assigned));
> + }
> + else
> + {
> + // Assing/inserter elements to existing active blocks
> + for (_BlockT* __block = _M_blocks._M_first;
> + !__block->_M_sentinel(); __block = __block->_M_next)
> + {
> + size_t __last = _M_assign_block(__block, __it, __end);
> + if (__it == __end)
> + return __erase_from(__block, __last);
> + }
> +
> + // Insert remaining elements
> + insert_range(ranges::subrange(std::move(__it), __end));
> + }
> + }
> +
> + // Erase elements from the block from which predicate is true.
> + template<typename _Pred>
> + void
> + _M_block_erase_if(_BlockT* __block, _Pred __pred,
> + size_t __from, size_t __to)
> + {
> + static constexpr bool __always
> + = is_same_v<_Pred, __gnu_cxx::__ops::_Always>;
> +
> + // We know that blcok have at least one element, so
> + // add it to free list now.
> + if constexpr (__always)
> + if (__block->_M_full())
> + _M_blocks._M_append_free(__block);
> +
> + auto __release = [&] (size_t __count)
> + {
> + if constexpr (!__always)
> + if (__block->_M_full())
> + _M_blocks._M_append_free(__block);
> +
> + __block->_M_release_slots(__from, __count);
> + _M_size -= __count;
> + return __from;
> + };
> +
> + size_t __pos = __from;
> + while (__pos != __to)
> + {
> + if (!__block->_M_occupied(__pos))
> + {
> + if (__always || __pos >= __from)
> + __pos = __release(__pos - __from);
> + else
> + __from = (__pos += __block->_M_free_count(__pos));
> + continue;
> + }
> +
> + if (__pred(*__block->_M_elem(__pos)))
> + _AllocT::destroy(_M_blocks._M_alloc,
> __block->_M_elem(__pos));
> + else if constexpr (!__always)
> + {
> + if (__pos > __from)
> + __release(__pos - __from);
> + __from = __pos + 1;
> + }
> + ++__pos;
> + }
> +
> + if (size_t __count = __pos - __from)
> + __release(__count);
> + }
> +
> + void
> + _M_erase_range(_BlockT* __block, size_t __from, size_t __to)
> + {
> + __gnu_cxx::__ops::_Always __always;
> + _M_block_erase_if(__block, __always, __from, __to);
> + }
> +
> + template<typename _Pred>
> + size_t
> + _M_erase_if(_Pred __pred)
> + {
> + size_t __old_size = _M_size;
> +
> + _BlockT* __block = _M_blocks._M_first;
> + while (!__block->_M_sentinel())
> + {
> + _M_block_erase_if(__block, __pred,
> __block->_M_first_occupied(),
> + __block->_M_capacity);
> +
> + _BlockT* __next = __block->_M_next;
> + if (__block->_M_empty())
> + {
> + _M_blocks._M_unlink_free(__block);
> + _M_blocks._M_hide(__block);
> + }
> + __block = __next;
> + }
> +
> + return __old_size - _M_size;
> + }
> +
> + // Destroy all elements from actvive blocks in given range
> + void
> + _M_clear(_BlockT* __from, _BlockT* __to)
> + {
> + for (; __from != __to; __from = __from->_M_next)
> + {
> + if (!__from->_M_full())
> + _M_blocks._M_unlink_free(__from);
> +
> + _M_size -= __from->_M_clear_elems(_M_blocks._M_alloc);
> + __from->_M_clear_slots();
> + }
> + }
> +
> + // Destroy all elments in the active block and deallocate all
> + // of them.
> + void
> + _M_clear_and_trim()
> + {
> + for (_BlockT* __block = _M_blocks._M_first;
> + __block != &_M_blocks._M_sent;
> + __block = __block->_M_next)
> + __block->_M_clear_elems(_M_blocks._M_alloc);
> +
> + _M_blocks._M_drop_blocks();
> + _M_size = 0;
> + }
> +
> + _BlockListT _M_blocks;
> + size_type _M_size = 0;
> +
> + template<typename _Up, typename _OAlloc, typename _Predicate>
> + friend typename hive<_Up, _OAlloc>::size_type
> + erase_if(hive<_Up, _OAlloc>& __cont, _Predicate __pred);
> + };
> +
> + template<class _Tp, class _Alloc>
> + void swap(hive<_Tp, _Alloc>& __lhs, hive<_Tp, _Alloc>& __rhs)
> + noexcept(noexcept(__lhs.swap(__rhs)))
> + { __lhs.swap(__rhs); }
> +
> + template<typename _Tp, typename _Alloc, typename _Predicate>
> + typename hive<_Tp, _Alloc>::size_type
> + erase_if(hive<_Tp, _Alloc>& __hive, _Predicate __pred)
> + { return __hive._M_erase_if(std::move(__pred)); }
> +
> + template<typename _Tp, typename _Alloc, typename _Up = _Tp>
> + typename hive<_Tp, _Alloc>::size_type
> + erase(hive<_Tp, _Alloc>& __hive, const _Up& __value)
> + { return std::erase_if(__hive,
> __gnu_cxx::__ops::__equal_to(__value)); }
> +
> +_GLIBCXX_END_NAMESPACE_VERSION
> +} // namespace std
> +
> +#endif /* __glibcxx_hive */
> +#endif /* _BITS_HIVE_H */
> diff --git a/libstdc++-v3/include/bits/predefined_ops.h
> b/libstdc++-v3/include/bits/predefined_ops.h
> index 83ce29b9231..c6ffa06c3fb 100644
> --- a/libstdc++-v3/include/bits/predefined_ops.h
> +++ b/libstdc++-v3/include/bits/predefined_ops.h
> @@ -203,6 +203,17 @@ namespace __ops
> __equal_to(const _Value& __val)
> { return _Comp_with_val_2nd<equal_to, _Value>(equal_to(), __val); }
>
> + struct _Always
> + {
> +#pragma GCC diagnostic push
> +#pragma GCC diagnostic ignored "-Wc++23-extensions" // static operator()
> + template<typename _Tp>
> + static _GLIBCXX_CONSTEXPR bool
> + operator()(const _Tp&) _GLIBCXX_NOEXCEPT
> + { return true; }
> +#pragma GCC diagnostic pop
> + };
> +
> } // namespace __ops
> } // namespace __gnu_cxx
>
> diff --git a/libstdc++-v3/include/bits/version.def
> b/libstdc++-v3/include/bits/version.def
> index 9c523581c65..95214fc8546 100644
> --- a/libstdc++-v3/include/bits/version.def
> +++ b/libstdc++-v3/include/bits/version.def
> @@ -2518,6 +2518,15 @@ ftms = {
> };
> };
>
> +ftms = {
> + name = hive;
> + values = {
> + v = 1; // set to 202502 when implemented
> + cxxmin = 26;
> + no_stdname = true;
> + };
> +};
> +
> ftms = {
> name = within_lifetime;
> // 202306 P2641R4 Checking if a union alternative is active
> diff --git a/libstdc++-v3/include/bits/version.h
> b/libstdc++-v3/include/bits/version.h
> index e0003054af6..340c892f978 100644
> --- a/libstdc++-v3/include/bits/version.h
> +++ b/libstdc++-v3/include/bits/version.h
> @@ -2774,6 +2774,15 @@
> #endif /* !defined(__cpp_lib_valarray) */
> #undef __glibcxx_want_valarray
>
> +#if !defined(__cpp_lib_hive)
> +# if (__cplusplus > 202302L)
> +# define __glibcxx_hive 1L
> +# if defined(__glibcxx_want_all) || defined(__glibcxx_want_hive)
> +# endif
> +# endif
> +#endif /* !defined(__cpp_lib_hive) */
> +#undef __glibcxx_want_hive
> +
> #if !defined(__cpp_lib_within_lifetime)
> # if (__cplusplus > 202302L) &&
> (__has_builtin(__builtin_is_within_lifetime))
> # define __glibcxx_within_lifetime 202603L
> diff --git a/libstdc++-v3/include/std/hive b/libstdc++-v3/include/std/hive
> new file mode 100644
> index 00000000000..a4a532cd025
> --- /dev/null
> +++ b/libstdc++-v3/include/std/hive
> @@ -0,0 +1,55 @@
> +// <vector> -*- C++ -*-
> +
> +// Copyright (C) 2026 Free Software Foundation, Inc.
> +//
> +// This file is part of the GNU ISO C++ Library. This library is free
> +// software; you can redistribute it and/or modify it under the
> +// terms of the GNU General Public License as published by the
> +// Free Software Foundation; either version 3, or (at your option)
> +// any later version.
> +
> +// This library is distributed in the hope that it will be useful,
> +// but WITHOUT ANY WARRANTY; without even the implied warranty of
> +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
> +// GNU General Public License for more details.
> +
> +// Under Section 7 of GPL version 3, you are granted additional
> +// permissions described in the GCC Runtime Library Exception, version
> +// 3.1, as published by the Free Software Foundation.
> +
> +// You should have received a copy of the GNU General Public License and
> +// a copy of the GCC Runtime Library Exception along with this program;
> +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
> +// <http://www.gnu.org/licenses/>.
> +
> +/** @file include/hive
> + * This is a Standard C++ Library header.
> + */
> +
> +#ifndef _GLIBCXX_HIVE
> +#define _GLIBCXX_HIVE 1
> +
> +#ifdef _GLIBCXX_SYSHDR
> +#pragma GCC system_header
> +#endif
> +
> +#define __glibcxx_want_hive
> +#include <bits/version.h>
> +
> +#ifdef __glibcxx_hive // C++ >= 26
> +
> +#include <bits/hive.h>
> +#include <bits/memory_resource.h>
> +
> +namespace std _GLIBCXX_VISIBILITY(default)
> +{
> +_GLIBCXX_BEGIN_NAMESPACE_VERSION
> + namespace pmr {
> + template<typename _Tp>
> + using hive = std::hive<_Tp, polymorphic_allocator<_Tp>>;
> + } // namespace pmr
> +_GLIBCXX_END_NAMESPACE_VERSION
> +} // namespace std
> +#endif // C++17
> +
> +#endif /* _GLIBCXX_HIVE */
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/access.cc
> b/libstdc++-v3/testsuite/23_containers/hive/access.cc
> new file mode 100644
> index 00000000000..d4aefaa5772
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/access.cc
> @@ -0,0 +1,67 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <array>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +void
> +test_access(std::hive_limits hl)
> +{
> + std::size_t n = 100;
> + auto iota = std::views::indices(n);
> + std::hive<int> h(std::from_range, iota, hl);
> + const std::hive<int>& ch = h;
> +
> + VERIFY( std::ranges::equal(
> + h.begin(), h.end(),
> + std::ranges::begin(iota), std::ranges::end(iota)) );
> + VERIFY( std::ranges::equal(
> + h.cbegin(), h.cend(),
> + std::ranges::begin(iota), std::ranges::end(iota)) );
> + VERIFY( std::ranges::equal(
> + ch.begin(), ch.end(),
> + std::ranges::begin(iota), std::ranges::end(iota)) );
> +
> + VERIFY( std::ranges::equal(
> + h.rbegin(), h.rend(),
> + std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> + VERIFY( std::ranges::equal(
> + h.crbegin(), h.crend(),
> + std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> + VERIFY( std::ranges::equal(
> + ch.rbegin(), ch.rend(),
> + std::ranges::rbegin(iota), std::ranges::rend(iota)) );
> +
> +
> + for (size_t i = 0; i < n; i += 13)
> + {
> + auto it = std::next(h.begin(), i);
> + auto ptr = &*it;
> + VERIFY( *it == i );
> + auto cit = std::next(ch.begin(), i);
> + VERIFY( it == cit );
> + VERIFY( &*cit == ptr );
> +
> + auto rit = std::prev(h.end(), n - i);
> + VERIFY( &*rit == ptr );
> + auto crit = std::prev(ch.end(), n - i);
> + VERIFY( &*crit == ptr );
> +
> + auto pit = h.get_iterator(ptr);
> + VERIFY( pit == it );
> + VERIFY( &*pit == ptr );
> + auto cpit = ch.get_iterator(ptr);
> + VERIFY( cpit == it );
> + VERIFY( &*cpit == ptr );
> + }
> +}
> +
> +int main()
> +{
> + test_access(std::hive<int>::block_capacity_default_limits());
> + test_access(std::hive_limits(10, 50));
> + test_access(std::hive_limits(2, 7));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> b/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> new file mode 100644
> index 00000000000..258c0dd1f7f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/assign.cc
> @@ -0,0 +1,158 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <testsuite_hooks.h>
> +
> +struct Tracker
> +{
> + static inline size_t copy = 0;
> + static inline size_t assign = 0;
> + static inline size_t create = 0;
> + static inline size_t destroy = 0;
> +
> + static void resetCounters()
> + { create = copy = assign = destroy = 0; }
> +
> + Tracker()
> + : Tracker(0)
> + {}
> +
> + Tracker(int p)
> + : x(p)
> + { ++create; }
> +
> + ~Tracker()
> + { ++destroy; }
> +
> + Tracker(const Tracker& other)
> + : x(other.x)
> + { ++copy; }
> +
> + Tracker& operator=(const Tracker& other)
> + { ++assign; this->x = other.x; return *this; }
> +
> + int x;
> +
> + friend constexpr bool
> + operator==(const Tracker&, const Tracker&) = default;
> +
> + friend constexpr bool
> + operator==(const Tracker& nm, int y)
> + { return nm.x == y; }
> +};
> +
> +template<typename Op>
> +void test_limits(Op&& op, std::hive_limits hl)
> +{
> + std::hive<Tracker> h(hl);
> + Tracker::resetCounters();
> + op(h);
> + VERIFY( Tracker::copy == 10 );
> + VERIFY( Tracker::assign == 0 );
> + VERIFY( Tracker::destroy == 0 );
> +
> + h.insert(10, Tracker(20));
> + Tracker::resetCounters();
> + op(h);
> + VERIFY( Tracker::copy == 0 );
> + VERIFY( Tracker::assign == 10 );
> + VERIFY( Tracker::destroy == 10 );
> +
> + h.erase(std::next(h.begin(), 3), h.end());
> + Tracker::resetCounters();
> + op(h);
> + VERIFY( Tracker::copy == 7 );
> + VERIFY( Tracker::assign == 3 );
> + VERIFY( Tracker::destroy == 0 );
> +
> + h.erase(h.begin(), std::next(h.begin(), 6));
> + Tracker::resetCounters();
> + op(h);
> + VERIFY( Tracker::copy == 6 );
> + VERIFY( Tracker::assign == 4 );
> + VERIFY( Tracker::destroy == 0 );
> +
> + auto it = h.begin();
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + Tracker::resetCounters();
> +
> + op(h);
> + VERIFY( Tracker::copy == 4 );
> + VERIFY( Tracker::assign == 6 );
> + VERIFY( Tracker::destroy == 0 );
> +
> + h.insert(7, Tracker(10));
> + it = h.begin();
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + it = h.erase(++it);
> + Tracker::resetCounters();
> +
> + op(h);
> + // Block need to have at least 2 elements, so all remain active
> + VERIFY( Tracker::copy == 5 );
> + VERIFY( Tracker::assign == 5 );
> + VERIFY( Tracker::destroy == 4 );
> +
> + h.insert(11, Tracker(10));
> + it = h.begin();
> + it = h.erase(std::next(it, 2), std::next(it, 7));
> + it = h.erase(std::next(it, 2), std::next(it, 7));
> + it = h.erase(std::next(it, 2), std::next(it, 7));
> + Tracker::resetCounters();
> +
> + op(h);
> + // Whole blocks may be cleared, so check total operations
> + VERIFY( Tracker::copy + Tracker::assign == 10 );
> + VERIFY( Tracker::assign + Tracker::destroy == 6 );
> +}
> +
> +template<typename Op>
> +void test_assign(Op&& op)
> +{
> + test_limits(op, std::hive<Tracker>::block_capacity_default_limits());
> + test_limits(op, std::hive_limits(20, 50));
> + test_limits(op, std::hive_limits(5, 10));
> + test_limits(op, std::hive_limits(10, 10));
> + test_limits(op, std::hive_limits(2, 4));
> +}
> +
> +int main()
> +{
> + std::initializer_list<Tracker> il{11, 12, 13, 14, 15, 26, 27, 28, 29,
> 30};
> + const std::hive<Tracker> src(il);
> +
> + test_assign([il, &src](std::hive<Tracker>& dst) {
> + dst = src;
> + VERIFY( std::ranges::equal(dst, il) );
> + VERIFY( std::ranges::equal(src, il) );
> + });
> + test_assign([il, &src](std::hive<Tracker>& dst) {
> + dst = il;
> + VERIFY( std::ranges::equal(dst, il) );
> + VERIFY( std::ranges::equal(src, il) );
> + });
> + test_assign([il](std::hive<Tracker>& dst) {
> + dst.assign_range(il);
> + VERIFY( std::ranges::equal(dst, il) );
> + });
> + test_assign([il](std::hive<Tracker>& dst) {
> + dst.assign(il.begin(), il.end());
> + VERIFY( std::ranges::equal(dst, il) );
> + });
> + test_assign([il](std::hive<Tracker>& dst) {
> + dst.assign(il);
> + VERIFY( std::ranges::equal(dst, il) );
> + });
> +
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> b/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> new file mode 100644
> index 00000000000..03947577035
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/capacity.cc
> @@ -0,0 +1,383 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <array>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +struct BlockCounter
> +{
> + size_t count = 0;
> + size_t min = size_t(-1);
> + size_t max = 0;
> +
> + void resetBounds()
> + {
> + min = size_t(-1);
> + max = 0;
> + }
> +};
> +
> +template<typename T, typename SizeType = size_t, size_t Max =
> SizeType(-1)>
> +struct TrackingAlloc
> +{
> + using value_type = T;
> + using size_type = SizeType;
> +
> + template<typename U>
> + struct rebind
> + { using other = TrackingAlloc<U, SizeType, Max>; };
> +
> + constexpr
> + TrackingAlloc(BlockCounter& param)
> + : counter(¶m)
> + { }
> +
> + template<typename U, typename OSizeType, OSizeType OMax>
> + constexpr
> + TrackingAlloc(const TrackingAlloc<U, OSizeType, OMax>& other)
> + : counter(other.counter)
> + { }
> +
> + static constexpr
> + size_type max_size() noexcept
> + requires (Max != size_type(-1))
> + { return size_type(Max); }
> +
> + T* allocate(size_t n)
> + {
> + if (n < counter->min)
> + counter->min = n;
> + if (n > counter->max)
> + counter->max = n;
> + ++counter->count;
> + return std::allocator<T>{}.allocate(n);
> + }
> +
> + void deallocate(T* ptr, size_t n)
> + {
> + --counter->count;
> + std::allocator<T>{}.deallocate(ptr, n);
> + }
> +
> +private:
> + BlockCounter* counter;
> +
> + template<typename, typename, size_t>
> + friend class TrackingAlloc;
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Tp, typename Alloc>
> +constexpr size_t
> +adjusted_count(size_t n)
> +{
> + // This peeks into implementation to provide actual counter,
> + // as block is allocated inside memnory region,
> + return n + std::__hive::_Block_list<Tp,
> Alloc>::_BlockT::_S_extra_slots(n);
> +}
> +
> +template<typename Tp, typename Alloc>
> +constexpr size_t
> +adjusted_count(const std::hive<Tp, Alloc>&, size_t n)
> +{ return adjusted_count<Tp, Alloc>(n); }
> +
> +template<typename SizeType = size_t, size_t Max = SizeType(-1)>
> +constexpr bool
> +max_size_respected()
> +{
> + using T = std::array<size_t, 4>;
> + using Alloc = TrackingAlloc<T, SizeType, Max>;
> +
> + BlockCounter bc;
> + std::hive_limits hl = std::hive<T, Alloc>::block_capacity_hard_limits();
> + return adjusted_count<T, Alloc>(hl.max)
> + <= std::allocator_traits<Alloc>::max_size(Alloc(bc));
> +}
> +
> +static_assert( max_size_respected<unsigned char>() );
> +static_assert( max_size_respected<unsigned char, 12>() );
> +static_assert( max_size_respected<unsigned short>() );
> +static_assert( max_size_respected<unsigned short, 1024>() );
> +static_assert( max_size_respected<unsigned int>() );
> +static_assert( max_size_respected<unsigned int, 66'000>() );
> +
> +void
> +test_over()
> +{
> + BlockCounter bc;
> + std::hive<int, TrackingAlloc<int>> h(140, 10, std::hive_limits(30, 40),
> bc);
> + VERIFY( h.capacity() == 140 );
> + VERIFY( bc.count == 4 );
> + VERIFY( bc.min >= adjusted_count(h, 30) );
> + VERIFY( bc.max <= adjusted_count(h, 40) );
> +
> + h.reserve(160);
> + VERIFY( h.capacity() == 170 );
> + VERIFY( bc.count == 5 );
> + VERIFY( bc.min >= adjusted_count(h, 30) );
> + VERIFY( bc.max <= adjusted_count(h, 40) );
> +
> + // Elements are not removed
> + h.trim_capacity(110);
> + VERIFY( h.capacity() == 140 );
> + VERIFY( bc.count == 4 );
> +
> + h.trim_capacity();
> + VERIFY( h.capacity() == 140 );
> + VERIFY( bc.count == 4 );
> +
> + h.clear();
> + h.trim_capacity(120);
> + VERIFY( h.capacity() == 140 );
> + VERIFY( bc.count == 4 );
> +
> + h.trim_capacity(80);
> + VERIFY( h.capacity() == 80 );
> + VERIFY( bc.count == 2 );
> +
> + h.trim_capacity();
> + VERIFY( h.capacity() == 0 );
> + VERIFY( bc.count == 0 );
> +
> + // Allocates blocks of size 40 and 30
> + h.reserve(50);
> + VERIFY( h.capacity() == 70 );
> + VERIFY( bc.count == 2 );
> +}
> +
> +void
> +test_exact()
> +{
> + BlockCounter bc;
> + std::hive<int, TrackingAlloc<int>> h(std::hive_limits(2, 10), bc);
> +
> + h.reserve(10);
> + VERIFY( h.capacity() == 10 );
> + VERIFY( bc.count == 1 );
> + VERIFY( bc.min == adjusted_count(h, 10) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.reserve(14);
> + VERIFY( h.capacity() == 14 );
> + VERIFY( bc.count == 2 );
> + VERIFY( bc.min == adjusted_count(h, 4) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.reserve(16);
> + VERIFY( h.capacity() == 16 );
> + VERIFY( bc.count == 3 );
> + VERIFY( bc.min == adjusted_count(h, 2) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.reserve(20);
> + VERIFY( h.capacity() == 20 );
> + VERIFY( bc.count == 4 );
> + VERIFY( bc.min == adjusted_count(h, 2) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.reserve(30);
> + VERIFY( h.capacity() == 30 );
> + VERIFY( bc.count == 5 );
> + VERIFY( bc.min == adjusted_count(h, 2) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + // h has now blocks 10,4,2,4,10, remove 10 and 2
> + h.trim_capacity(18);
> + VERIFY( h.capacity() == 18 );
> + VERIFY( bc.count == 3 );
> +
> + h.trim_capacity(10);
> + VERIFY( h.capacity() == 10 );
> + VERIFY( bc.count == 1 );
> +}
> +
> +void
> +test_shrink_to_fit()
> +{
> + BlockCounter bc;
> + std::hive<int, TrackingAlloc<int>> h(std::hive_limits(10, 50), bc);
> + h.insert_range(std::views::iota(0, 10));
> + h.insert_range(std::views::iota(10, 20));
> + h.insert_range(std::views::iota(20, 120));
> + h.erase(std::next(h.begin(), 100), h.end());
> + VERIFY( h.size() == 100 );
> + VERIFY( h.capacity() == 120 );
> + VERIFY( bc.count == 4 );
> + VERIFY( bc.min == adjusted_count(h, 10) );
> + VERIFY( bc.max == adjusted_count(h, 50) );
> +
> + bc.resetBounds();
> + // Replace two initial moved to last block
> + h.shrink_to_fit();
> + VERIFY( h.size() == 100 );
> + VERIFY( h.capacity() == 100 );
> + VERIFY( bc.count == 2 );
> + VERIFY( bc.max == 0 ); // no allocations
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100)) );
> +
> + // Add block of size 40
> + h.reserve(140);
> + VERIFY( h.capacity() == 140 );
> + VERIFY( bc.count == 3 );
> + std::erase_if(h, [](int x) { return x >= 70; });
> + bc.resetBounds();
> +
> + // Replace block of size 50 with one of size 20,
> + // and remove reserved blocks
> + h.shrink_to_fit();
> + VERIFY( h.size() == 70 );
> + VERIFY( h.capacity() == 70 );
> + VERIFY( bc.count == 2 );
> + VERIFY( bc.min == adjusted_count(h, 20) );
> + VERIFY( bc.max == adjusted_count(h, 20) );
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 70)) );
> +
> + std::erase_if(h, [](int x) { return x < 15; });
> + bc.resetBounds();
> +
> + // We have [50, 20) blocks, so 20 is reduced to 10
> + // This guaranteed that capacity() - size() is always smaller than
> + // minimum block size
> + h.shrink_to_fit();
> + VERIFY( h.size() == 55 );
> + VERIFY( h.capacity() == 60 );
> + VERIFY( bc.count == 2 );
> + VERIFY( bc.min == adjusted_count(h, 10) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(15, 70)) );
> +
> + // We iterator blocks in reverse order, as they are usually placed
> + // in increasing order.
> + h.reserve(70);
> + h.reserve(100);
> + h.insert_range(std::views::iota(0, 15));
> + h.insert_range(std::views::iota(70, 100));
> + VERIFY( h.capacity() == 100 );
> + VERIFY( bc.count == 4 ); // 50, 10, 10, 30
> + std::erase_if(h, [](int x) { return x % 2; });
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100) |
> std::views::stride(2)) );
> + bc.resetBounds();
> +
> + // This remove 10,10,30 blocks from the last
> + h.shrink_to_fit();
> + VERIFY( h.size() == 50 );
> + VERIFY( h.capacity() == 50 );
> + VERIFY( bc.count == 1 ); // 10, 10, 30
> + VERIFY( bc.max == 0 ); // no allocations
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 100) |
> std::views::stride(2)) );
> +}
> +
> +void
> +test_reshape()
> +{
> + BlockCounter bc;
> + std::hive<int, TrackingAlloc<int>> h(std::hive_limits(2, 50), bc);
> +
> + h.insert_range(std::views::iota(0, 5));
> + VERIFY( h.capacity() == 5 );
> + VERIFY( bc.count == 1 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 5) );
> +
> + h.insert_range(std::views::iota(5, 10));
> + VERIFY( h.capacity() == 10 );
> + VERIFY( bc.count == 2 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 5) );
> +
> + h.insert_range(std::views::iota(10, 20));
> + VERIFY( h.capacity() == 20 );
> + VERIFY( bc.count == 3 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.insert_range(std::views::iota(20, 30));
> + VERIFY( h.capacity() == 30 );
> + VERIFY( bc.count == 4 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 10) );
> +
> + h.insert_range(std::views::iota(30, 50));
> + VERIFY( h.capacity() == 50 );
> + VERIFY( bc.count == 5 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 20) );
> +
> + h.insert_range(std::views::iota(50, 100));
> + VERIFY( h.capacity() == 100 );
> + VERIFY( bc.count == 6 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 50) );
> +
> + h.insert_range(std::views::iota(100, 200));
> + VERIFY( h.capacity() == 200 );
> + VERIFY( bc.count == 8 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 50) );
> +
> + h.reserve(280);
> + VERIFY( h.capacity() == 280 );
> + VERIFY( bc.count == 10 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 50) );
> +
> + // h now has blocks of capacity 5,5,10,10,20,50,50,50,50,30
> + VERIFY( std::ranges::equal(h, std::views::iota(0, 200)) );
> +
> + h.reshape({5, 100});
> + VERIFY( limits_eq(h, {5, 100}) );
> + VERIFY( h.capacity() == 280 );
> + VERIFY( bc.count == 10 );
> + VERIFY( bc.min == adjusted_count(h, 5) );
> + VERIFY( bc.max == adjusted_count(h, 50) );
> + VERIFY( std::ranges::equal(h, std::views::iota(0, 200)) );
> +
> + bc.resetBounds();
> + // Removes reserved block of size 50, and replaces 3x50
> + // blocks with 5x30, using one reserved
> + h.reshape({5, 30});
> + VERIFY( limits_eq(h, {5, 30}) );
> + VERIFY( h.capacity() == 200 );
> + VERIFY( bc.count == 10 );
> + VERIFY( bc.min == adjusted_count(h, 30) );
> + VERIFY( bc.max == adjusted_count(h, 30) );
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +
> + // Replaces intial 5,5,10,10 blocks with one 30 block
> + h.reshape(std::hive_limits(20, 30));
> + VERIFY( limits_eq(h, {20, 30}) );
> + VERIFY( h.capacity() == 200 );
> + VERIFY( bc.count == 7 );
> + VERIFY( bc.min == adjusted_count(h, 30) );
> + VERIFY( bc.max == adjusted_count(h, 30) );
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +
> + // Reallocate everything with 80 size blocks
> + bc.resetBounds();
> + h.reshape(std::hive_limits(80, 80));
> + VERIFY( limits_eq(h, {80, 80}) );
> + VERIFY( h.capacity() == 240 );
> + VERIFY( bc.count == 3 );
> + VERIFY( bc.min == adjusted_count(h, 80) );
> + VERIFY( bc.max == adjusted_count(h, 80) );
> + VERIFY( std::ranges::is_permutation(h, std::views::iota(0, 200)) );
> +}
> +
> +int main()
> +{
> + test_over();
> + test_exact();
> + test_shrink_to_fit();
> + test_reshape();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> b/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> new file mode 100644
> index 00000000000..e0ac6aa555f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/copy_alloc.cc
> @@ -0,0 +1,335 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <memory>
> +#include <scoped_allocator>
> +#include <utility>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +using __gnu_test::propagating_allocator;
> +using __gnu_test::tracker_allocator;
> +using Counter = __gnu_test::tracker_allocator_counter;
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +int
> +elem_alloc_personality(const Hive& hive)
> +{
> + int front = hive.begin()->get_allocator().get_personality();
> + int back = std::prev(hive.end())->get_allocator().get_personality();
> + VERIFY( front == back );
> + return front;
> +}
> +
> +template<bool Propagate>
> +void
> +test_ctor()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits sl(10, 20);
> + const Hive src({Vector{1, 2, 3}, Vector{4, 5, 6}},
> + sl, ScopedAlloc{11, 22});
> +
> + Counter::reset();
> + Hive s1(src);
> + VERIFY( std::ranges::equal(s1, src) );
> + VERIFY( limits_eq(s1, sl) );
> + if (Propagate)
> + {
> + VERIFY( s1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s1) == 22 );
> + }
> + else
> + {
> + VERIFY( s1.get_allocator().get_personality() == 0 );
> + VERIFY( elem_alloc_personality(s1) == 0 );
> + }
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Counter::reset();
> + Hive d1(src, ScopedAlloc{33, 44});
> + VERIFY( std::ranges::equal(d1, src) );
> + VERIFY( limits_eq(d1, sl) );
> + VERIFY( d1.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d1) == 44 );
> + VERIFY( Counter::get_allocation_count() >= sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_assign()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits dl(30, 50);
> + const Vector vc{11, 12, 13};
> + const Hive src({Vector{1, 2, 3}, Vector{4, 5, 6}},
> + std::hive_limits(10, 20), ScopedAlloc{11, 22});
> +
> + Hive s0(dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s0 = src;
> + VERIFY( std::ranges::equal(s0, src) );
> + VERIFY( limits_eq(s0, dl) );
> + VERIFY( s0.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s0) == 22 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s1(1, vc, dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s1 = src;
> + VERIFY( std::ranges::equal(s1, src) );
> + VERIFY( limits_eq(s1, dl) );
> + VERIFY( s1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s1) == 22 );
> + VERIFY( Counter::get_allocation_count() >= 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 1 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s2(2, vc, dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s2 = src;
> + VERIFY( std::ranges::equal(s2, src) );
> + VERIFY( limits_eq(s2, dl) );
> + VERIFY( s2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s2) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s3 = src;
> + VERIFY( std::ranges::equal(s2, src) );
> + VERIFY( limits_eq(s3, dl) );
> + VERIFY( s3.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s3) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 1 );
> +
> + Hive d0(dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d0 = src;
> + VERIFY( std::ranges::equal(d0, src) );
> + VERIFY( limits_eq(d0, dl) );
> + if (Propagate)
> + {
> + VERIFY( d0.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d0) == 22 );
> + }
> + else
> + {
> + VERIFY( d0.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d0) == 44 );
> + }
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive d1(1, vc, dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d1 = src;
> + VERIFY( std::ranges::equal(d1, src) );
> + VERIFY( limits_eq(d1, dl) );
> + if (Propagate)
> + {
> + VERIFY( d1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d1) == 22 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() >= sizeof(Vector) );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 1 );
> + }
> + else
> + {
> + VERIFY( d1.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d1) == 44 );
> + VERIFY( Counter::get_allocation_count() >= 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 1 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> + }
> +
> + Hive d2(2, vc, dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d2 = src;
> + VERIFY( std::ranges::equal(d2, src) );
> + VERIFY( limits_eq(d2, dl) );
> + if (Propagate)
> + {
> + VERIFY( d2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d2) == 22 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> + }
> + else
> + {
> + VERIFY( d2.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d2) == 44 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> + }
> +
> + Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d3 = src;
> + VERIFY( std::ranges::equal(d3, src) );
> + VERIFY( limits_eq(d3, dl) );
> + if (Propagate)
> + {
> + VERIFY( d3.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d3) == 22 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() >= 3 * sizeof(Vector) );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> + }
> + else
> + {
> + VERIFY( d3.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d3) == 44 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 1 );
> + }
> +}
> +
> +template<bool Propagate>
> +void
> +test_empty()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits dl(30, 50);
> + const Vector vc{11, 12, 13};
> + const Hive empty(std::hive_limits(10, 20), ScopedAlloc{11, 22});
> +
> + Hive s0(dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s0 = empty;
> + VERIFY( s0.empty() );
> + VERIFY( limits_eq(s0, dl) );
> + VERIFY( s0.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> + Counter::reset();
> +
> + s3 = empty;
> + VERIFY( s3.empty() );
> + VERIFY( limits_eq(s3, dl) );
> + VERIFY( s3.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> +
> + Hive d0(dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d0 = empty;
> + VERIFY( d0.empty() );
> + VERIFY( limits_eq(d0, dl) );
> + if (Propagate)
> + VERIFY( d0.get_allocator().get_personality() == 11 );
> + else
> + VERIFY( d0.get_allocator().get_personality() == 33 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d3 = empty;
> + VERIFY( d3.empty() );
> + VERIFY( limits_eq(d3, dl) );
> + if (Propagate)
> + {
> + VERIFY( d3.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> + }
> + else
> + {
> + VERIFY( d3.get_allocator().get_personality() == 33 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + }
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_all()
> +{
> + test_ctor<Propagate>();
> + test_assign<Propagate>();
> + test_empty<Propagate>();
> +}
> +
> +int main()
> +{
> + test_all<true>();
> + test_all<false>();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> b/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> new file mode 100644
> index 00000000000..1f53db5837e
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/ctor.cc
> @@ -0,0 +1,238 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <memory>
> +#include <scoped_allocator>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +struct NonMovable
> +{
> + NonMovable() = default;
> + NonMovable(int p) : x(p) { }
> +
> + NonMovable(NonMovable&&) = delete;
> +
> + int x;
> +
> + friend constexpr bool
> + operator==(const NonMovable& nm, int y)
> + { return nm.x == y; }
> +};
> +
> +struct MoveOnly
> +{
> + MoveOnly() = default;
> + MoveOnly(int p) : x(p) { }
> +
> + MoveOnly(MoveOnly&&) = default;
> + MoveOnly& operator=(MoveOnly&&) = default;
> +
> + int x;
> +
> + friend constexpr bool
> + operator==(const MoveOnly& nm, int y)
> + { return nm.x == y; }
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_default(const Hive& hive)
> +{ return limits_eq(hive, Hive::block_capacity_default_limits()); }
> +
> +template<typename T, typename Check, typename... Args>
> +void
> +verify_alloc(Check&& check, const Args&... args)
> +{
> + using __gnu_test::default_init_allocator;
> + using Hive = std::hive<int, default_init_allocator<int>>;
> + default_init_allocator<T> a{};
> + a.state = 5;
> +
> + auto h1 = Hive(args...);
> + VERIFY( h1.get_allocator().state == 0 );
> + VERIFY( limits_default(h1) );
> + VERIFY( check(h1, args...) );
> +
> + auto h2 = Hive(args..., a);
> + VERIFY( h2.get_allocator().state == 5 );
> + VERIFY( limits_default(h1) );
> + VERIFY( check(h2, args...) );
> +
> + std::hive_limits hl(5, 50);
> + auto h3 = Hive(args..., hl);
> + VERIFY( h3.get_allocator().state == 0 );
> + VERIFY( limits_eq(h3, hl) );
> + VERIFY( check(h3, args...) );
> +
> + auto h4 = Hive(args..., hl, a);
> + VERIFY( h4.get_allocator().state == 5 );
> + VERIFY( limits_eq(h4, hl) );
> + VERIFY( check(h4, args...) );
> +}
> +
> +void
> +test_empty()
> +{
> + std::hive<int> h;
> + VERIFY( h.empty() );
> + verify_alloc<int>([](const auto& hive) {
> + return hive.empty();
> + });
> +}
> +
> +constinit std::hive<int> gh1;
> +constinit std::hive<int> gh2(std::hive_limits(5, 50));
> +
> +void
> +test_copy()
> +{
> + std::hive_limits hl(5, 50);
> + std::initializer_list<int> il{1, 2, 3, 4, 5};
> +
> + const std::hive<int> s1(il);
> + const std::hive<int> s2(il, hl);
> +
> + std::hive<int> h1(s1);
> + VERIFY( std::ranges::equal(h1, il) );
> + VERIFY( limits_default(h1) );
> +
> + std::hive<int> h2(s2);
> + VERIFY( std::ranges::equal(h2, il) );
> + VERIFY( limits_eq(h2, hl) );
> +
> + using __gnu_test::default_init_allocator;
> + using Hive = std::hive<int, default_init_allocator<int>>;
> + default_init_allocator<int> a{};
> + a.state = 5;
> +
> + const Hive sd1(il);
> + const Hive sd2(il, hl);
> +
> + auto d1 = Hive(sd1);
> + VERIFY( d1.get_allocator().state == 0 );
> + VERIFY( limits_default(d1) );
> + VERIFY( std::ranges::equal(d1, il) );
> +
> + auto d2 = Hive(sd1, a);
> + VERIFY( d2.get_allocator().state == 5 );
> + VERIFY( limits_default(d1) );
> + VERIFY( std::ranges::equal(d2, il) );
> +
> + auto d3 = Hive(sd2);
> + VERIFY( d3.get_allocator().state == 0 );
> + VERIFY( limits_eq(d3, hl) );
> + VERIFY( std::ranges::equal(d3, il) );
> +
> + auto d4 = Hive(sd2, a);
> + VERIFY( d4.get_allocator().state == 5 );
> + VERIFY( limits_eq(d4, hl) );
> + VERIFY( std::ranges::equal(d4, il) );
> +}
> +
> +void
> +test_move()
> +{
> + std::hive_limits hl(5, 50);
> + std::initializer_list<int> il{1, 2, 3, 4, 5};
> +
> + std::hive<MoveOnly> s1(std::from_range, il);
> + std::hive<MoveOnly> s2(std::from_range, il, hl);
> +
> + std::hive<MoveOnly> h1(std::move(s1));
> + VERIFY( std::ranges::equal(h1, il, std::equal_to{}) );
> + VERIFY( limits_default(h1) );
> +
> + std::hive<MoveOnly> h2(std::move(s2));
> + VERIFY( std::ranges::equal(h2, il, std::equal_to{}) );
> + VERIFY( limits_eq(h2, hl) );
> +
> + using __gnu_test::default_init_allocator;
> + using Hive = std::hive<MoveOnly, default_init_allocator<MoveOnly>>;
> + default_init_allocator<MoveOnly> a{};
> + a.state = 5;
> +
> + Hive sd1a(std::from_range, il);
> + Hive sd1b(std::from_range, il);
> + Hive sd2a(std::from_range, il, hl);
> + Hive sd2b(std::from_range, il, hl);
> +
> + auto d1 = Hive(std::move(sd1a));
> + VERIFY( d1.get_allocator().state == 0 );
> + VERIFY( limits_default(d1) );
> + VERIFY( std::ranges::equal(d1, il, std::equal_to{}) );
> +
> + auto d2 = Hive(std::move(sd1b), a);
> + VERIFY( d2.get_allocator().state == 5 );
> + VERIFY( limits_default(d1) );
> + VERIFY( std::ranges::equal(d2, il, std::equal_to{}) );
> +
> + auto d3 = Hive(std::move(sd2a));
> + VERIFY( d3.get_allocator().state == 0 );
> + VERIFY( limits_eq(d3, hl) );
> + VERIFY( std::ranges::equal(d3, il, std::equal_to{}) );
> +
> + auto d4 = Hive(std::move(sd2b), a);
> + VERIFY( d4.get_allocator().state == 5 );
> + VERIFY( limits_eq(d4, hl) );
> + VERIFY( std::ranges::equal(d4, il, std::equal_to{}) );
> +}
> +
> +void
> +test_n()
> +{
> + auto check = [](const auto& hive, size_t n, auto... vs)
> + {
> + int v = (0, ..., vs);
> + return hive.size() == n
> + && std::ranges::all_of(hive, [v](const auto& e) { return e == v; });
> + };
> +
> + std::hive<NonMovable> h1(10);
> + VERIFY( check(h1, 10) );
> + verify_alloc<NonMovable>(check, 15);
> +
> + std::hive<int> h2(20, 7);
> + VERIFY( check(h2, 20, 7) );
> + verify_alloc<int>(check, 20, 13);
> +}
> +
> +void
> +test_range()
> +{
> + std::initializer_list<int> il{1, 2, 3, 4, 5, 6, 7, 8};
> + auto check = [il](const auto& hive, const auto&... args)
> + { return std::ranges::equal(hive, il); };
> +
> + std::hive<int> h1(il);
> + VERIFY( check(h1) );
> + verify_alloc<int>(check, il);
> +
> + std::hive<int> h2(il.begin(), il.end());
> + VERIFY( check(h2) );
> + verify_alloc<int>(check, il.begin(), il.end());
> +
> + std::hive<int> h3(std::from_range, il);
> + VERIFY( check(h3) );
> + verify_alloc<int>(check, std::from_range, il);
> +}
> +
> +int main()
> +{
> + test_empty();
> + test_copy();
> + test_move();
> + test_n();
> + test_range();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> b/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> new file mode 100644
> index 00000000000..f410592bc5a
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/erasure.cc
> @@ -0,0 +1,291 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <testsuite_hooks.h>
> +
> +struct Tracker
> +{
> + static inline size_t copy = 0;
> + static inline size_t assign = 0;
> + static inline size_t create = 0;
> + static inline size_t destroy = 0;
> +
> + static void resetCounters()
> + { create = copy = assign = destroy = 0; }
> +
> + Tracker()
> + : Tracker(0)
> + {}
> +
> + Tracker(int p)
> + : x(p)
> + { ++create; }
> +
> + ~Tracker()
> + { ++destroy; }
> +
> + Tracker(const Tracker& other)
> + : x(other.x)
> + { ++copy; }
> +
> + Tracker& operator=(const Tracker& other)
> + { ++assign; this->x = other.x; return *this; }
> +
> + int x;
> +
> + friend constexpr bool
> + operator==(const Tracker&, const Tracker&) = default;
> +
> + friend constexpr bool
> + operator==(const Tracker& nm, int y)
> + { return nm.x == y; }
> +};
> +
> +bool eq(const std::hive<Tracker>& h, std::initializer_list<int> il)
> +{
> + if (!std::ranges::equal(h, il, std::equal_to{}, &Tracker::x))
> + return false;
> + return std::ranges::equal(std::rbegin(h), std::rend(h),
> + std::rbegin(il), std::rend(il),
> + std::equal_to{}, &Tracker::x);
> +}
> +
> +void
> +test_erase(std::hive_limits hl)
> +{
> + std::initializer_list<Tracker> il
> + {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
> +
> + std::hive<Tracker> h(il, hl);
> + size_t cap = h.capacity();
> + Tracker::resetCounters();
> +
> + h.clear();
> + VERIFY( h.empty() );
> + VERIFY( Tracker::destroy == 16 );
> +
> + h = il;
> + Tracker::resetCounters();
> + auto it = h.erase(h.begin(), h.end());
> + VERIFY( it == h.end() );
> + VERIFY( h.empty() );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 16 );
> +
> + h = il;
> + Tracker::resetCounters();
> + it = h.erase(std::next(h.begin(), 5), std::next(h.begin(), 10));
> + VERIFY( eq(h, {1,2,3,4,5,11,12,13,14,15,16}) );
> + VERIFY( it->x == 11 );
> + VERIFY( Tracker::destroy == 5 );
> +
> + it = h.erase(h.begin(), std::next(h.begin(), 5));
> + VERIFY( eq(h, {11,12,13,14,15,16}) );
> + VERIFY( it->x == 11 );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 10 );
> +
> + it = h.erase(h.begin(), std::next(h.begin(), 5));
> + VERIFY( eq(h, {16}) );
> + VERIFY( it->x == 16 );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 15 );
> +
> + it = h.erase(h.begin());
> + VERIFY( it == h.end() );
> + VERIFY( h.empty() );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 16 );
> +
> + h = il;
> + Tracker::resetCounters();
> + for (auto it = h.begin(); it != h.end();)
> + it = h.erase(++it);
> + VERIFY( eq(h, {1,3,5,7,9,11,13,15}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 8 );
> +
> + auto erase_step = [&](size_t step)
> + {
> + for (auto it = h.begin(); it != h.end(); std::ranges::advance(it,
> step, h.end()))
> + {
> + auto n = it;
> + std::ranges::advance(n, step, h.end());
> + it = h.erase(it, n);
> + }
> + };
> +
> + erase_step(2);
> + VERIFY( eq(h, {5,7,13,15}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 12 );
> +
> + erase_step(2);
> + VERIFY( eq(h, {13,15}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 14 );
> +
> + erase_step(2);
> + VERIFY( h.empty() );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 16 );
> +
> + h = il;
> + Tracker::resetCounters();
> +
> + it = h.erase(h.begin());
> + VERIFY( it->x == 2 );
> + VERIFY( eq(h, {2,3,4,5,6,7,8,9,10,11,12,13,14,15,16}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 1 );
> +
> + erase_step(2);
> + VERIFY( eq(h, {4,5,8,9,12,13,16}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 9 );
> +
> + erase_step(3);
> + VERIFY( eq(h, {9,12,13}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 13 );
> +
> + erase_step(1);
> + VERIFY( eq(h, {12}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 15 );
> +
> + h.clear();
> + h.trim_capacity();
> + VERIFY( h.empty() );
> + VERIFY( h.capacity() == 0 );
> + VERIFY( Tracker::destroy == 16 );
> +
> + std::hive<Tracker> h2(500, -1, hl);
> + std::ranges::copy(std::views::iota(1, 5), h2.begin());
> + std::ranges::copy(std::views::iota(5, 10), std::prev(h2.end(), 5));
> + cap = h2.capacity();
> + Tracker::resetCounters();
> +
> + it = h2.erase(std::next(h2.begin(), 4), std::prev(h2.end(), 5));
> + VERIFY( it->x == 5 );
> + VERIFY( eq(h2, {1,2,3,4,5,6,7,8,9}) );
> + VERIFY( h2.capacity() == cap );
> + VERIFY( Tracker::destroy == 491 );
> +}
> +
> +void
> +test_unique(std::hive_limits hl)
> +{
> + std::initializer_list<Tracker> il
> + {1,1,2,2,2,3,4,5,5,7,7,8,8,8,8,8,10,12,11,11,15,15};
> +
> + std::hive<Tracker> h(il, hl);
> + const size_t cap = h.capacity();
> + Tracker::resetCounters();
> +
> + auto rem = h.unique();
> + VERIFY( rem == 11 );
> + VERIFY( eq(h, {1,2,3,4,5,7,8,10,12,11,15}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 11 );
> +
> + rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> + { return (lhs.x % 2) == (rhs.x %2); });
> + VERIFY( rem == 4 );
> + VERIFY( eq(h, {1,2,3,4,5,8,11}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 15 );
> +
> + rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> + { return std::abs(lhs.x - rhs.x) <= 2; });
> + VERIFY( rem == 3 );
> + VERIFY( eq(h, {1,4,8,11}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 18 );
> +
> + rem = h.unique([](const Tracker& lhs, const Tracker& rhs)
> + { return true; });
> + VERIFY( rem == 3 );
> + VERIFY( eq(h, {1}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 21 );
> +}
> +
> +void
> +test_erase_if(std::hive_limits hl)
> +{
> + std::initializer_list<Tracker> il
> + {0, 1, 2, 3, 11, 12, 13, 14, 4, 15,
> + 5, 5, 5, 6, 17, 17, 7, 18, 8, 9, 19, 10, 20};
> +
> + std::hive<Tracker> h(il, hl);
> + size_t cap = h.capacity();
> + Tracker::resetCounters();
> +
> + auto rem = std::erase_if(h, [](const Tracker& t) { return t.x > 10; });
> + VERIFY( rem == 10 );
> + VERIFY( eq(h, {0,1,2,3,4,5,5,5,6,7,8,9,10}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 10 );
> +
> + rem = std::erase(h, 5);
> + VERIFY( rem == 3 );
> + VERIFY( eq(h, {0,1,2,3,4,6,7,8,9,10}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 13 );
> +
> + rem = std::erase_if(h, [](const Tracker& t) { return t.x % 2; });
> + VERIFY( rem == 4 );
> + VERIFY( eq(h, {0,2,4,6,8,10}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 17 );
> +
> + rem = std::erase(h, 0);
> + VERIFY( rem == 1 );
> + VERIFY( eq(h, {2,4,6,8,10}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 18 );
> +
> + rem = std::erase(h, 10);
> + VERIFY( rem == 1 );
> + VERIFY( eq(h, {2,4,6,8}) );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 19 );
> +
> + rem = std::erase_if(h, [](const Tracker& t) { return true; });
> + VERIFY( rem == 4 );
> + VERIFY( h.empty() );
> + VERIFY( h.capacity() == cap );
> + VERIFY( Tracker::destroy == 23 );
> +
> + std::hive<Tracker> h2(500, -1, hl);
> + std::ranges::copy(std::views::iota(1, 10),
> + (h2 | std::views::stride(50)).begin());
> + cap = h2.capacity();
> + Tracker::resetCounters();
> +
> + rem = std::erase_if(h2, [](const Tracker& t) { return t.x < 0; });
> + VERIFY( rem == 491 );
> + VERIFY( eq(h2, {1,2,3,4,5,6,7,8,9}) );
> + VERIFY( h2.capacity() == cap );
> + VERIFY( Tracker::destroy == 491 );
> +}
> +
> +void test_limits(std::hive_limits hl)
> +{
> + test_erase(hl);
> + test_unique(hl);
> + test_erase_if(hl);
> +}
> +
> +int main()
> +{
> + test_limits(std::hive<Tracker>::block_capacity_default_limits());
> + test_limits(std::hive_limits(20, 50));
> + test_limits(std::hive_limits(5, 10));
> + test_limits(std::hive_limits(10, 10));
> + test_limits(std::hive_limits(2, 4));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> b/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> new file mode 100644
> index 00000000000..112131ff26c
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/insert.cc
> @@ -0,0 +1,93 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <flat_set>
> +#include <testsuite_hooks.h>
> +
> +void test_inserts(std::hive<int>& hive)
> +{
> + std::flat_set<int> expected(std::from_range, hive);
> +
> + auto it = hive.emplace(1);
> + VERIFY( *it == 1 );
> + expected.insert(1);
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + std::vector<int> v{11, 12, 13, 14, 15};
> + hive.insert(v.begin(), v.end());
> + expected.insert(v.begin(), v.end());
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + v = {16, 17, 18};
> + hive.insert_range(v);
> + expected.insert(v.begin(), v.end());
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + it = hive.insert(2);
> + VERIFY( *it == 2 );
> + expected.insert(2);
> +
> + it = hive.insert(hive.end(), 3);
> + VERIFY( *it == 3 );
> + expected.insert(3);
> +
> + it = hive.emplace_hint(hive.end(), 4);
> + VERIFY( *it == 4 );
> + expected.insert(4);
> +
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + hive.insert(10, 20);
> + expected.insert(20);
> + VERIFY( std::ranges::count(hive, 20) == 10 );
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + std::initializer_list<int> il{11, 12, 13, 14};
> + hive.insert(il);
> + expected.insert(il.begin(), il.end());
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +}
> +
> +void test_limits(std::hive_limits hl =
> std::hive<int>::block_capacity_default_limits())
> +{
> + std::hive<int> h0(hl);
> + test_inserts(h0);
> +
> + std::hive<int> h1(hl);
> + h1.reserve(4);
> + h1.reserve(3);
> + test_inserts(h1);
> +
> + std::hive<int> h2({-1, -2, -3, -4, -5}, hl);
> + test_inserts(h2);
> +
> + std::hive<int> h3(100, -1, hl);
> + for (auto it = h3.begin(); it != h3.end(); )
> + it = h3.erase(++it);
> + test_inserts(h3);
> +
> + std::hive<int> h4(80, -2, hl);
> + for (auto it = h4.begin(); it != h4.end(); std::advance(it, 10))
> + it = h4.erase(it, std::next(it, 10));
> + test_inserts(h4);
> +
> + std::hive<int> h5(50, -3, hl);
> + h5.erase(std::next(h5.begin(), 42), std::next(h5.begin(), 48));
> + h5.erase(std::next(h5.begin(), 33), std::next(h5.begin(), 35));
> + h5.erase(std::next(h5.begin(), 36), std::next(h5.begin(), 38));
> + h5.erase(std::next(h5.begin(), 24), std::next(h5.begin(), 28));
> + h5.erase(std::next(h5.begin(), 12), std::next(h5.begin(), 19));
> + h5.erase(std::next(h5.begin()), std::next(h5.begin(), 5));
> + test_inserts(h5);
> +}
> +
> +int main()
> +{
> + test_limits();
> + test_limits(std::hive_limits(20, 50));
> + test_limits(std::hive_limits(5, 10));
> + test_limits(std::hive_limits(10, 10));
> + test_limits(std::hive_limits(2, 4));
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> b/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> new file mode 100644
> index 00000000000..8bea84df2a2
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/move_alloc.cc
> @@ -0,0 +1,444 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <memory>
> +#include <optional>
> +#include <scoped_allocator>
> +#include <utility>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +#include <testsuite_allocator.h>
> +
> +using __gnu_test::propagating_allocator;
> +using __gnu_test::tracker_allocator;
> +using Counter = __gnu_test::tracker_allocator_counter;
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +template<typename Hive>
> +int
> +elem_alloc_personality(const Hive& hive)
> +{
> + int front = hive.begin()->get_allocator().get_personality();
> + int back = std::prev(hive.end())->get_allocator().get_personality();
> + VERIFY( front == back );
> + return front;
> +}
> +
> +template<bool Propagate>
> +void
> +test_ctor()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits sl(10, 20);
> + const std::initializer_list<Vector> il = {Vector{1, 2, 3}, Vector{4, 5,
> 6}};
> + std::optional<Hive> opt;
> + auto make = [&] -> Hive&&
> + {
> + opt.emplace(il, sl, ScopedAlloc{11, 22});
> + Counter::reset();
> + return std::move(*opt);
> + };
> +
> + Hive s1(make());
> + VERIFY( std::ranges::equal(s1, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s1, sl) );
> + VERIFY( s1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s1) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive d1(make(), ScopedAlloc{33, 44});
> + VERIFY( std::ranges::equal(d1, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(d1, sl) );
> + VERIFY( d1.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d1) == 44 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_assign()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits sl(10, 20);
> + const std::hive_limits dl(30, 50);
> + const Vector vc{11, 12, 13};
> + const std::initializer_list<Vector> il = {Vector{1, 2, 3}, Vector{4, 5,
> 6}};
> + std::optional<Hive> opt;
> + auto make = [&] -> Hive&&
> + {
> + opt.emplace(il, sl, ScopedAlloc{11, 22});
> + Counter::reset();
> + return std::move(*opt);
> + };
> +
> + Hive s0(dl, ScopedAlloc{11, 22});
> +
> + s0 = make();
> + VERIFY( std::ranges::equal(s0, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s0, sl) );
> + VERIFY( s0.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s0) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s1(1, vc, dl, ScopedAlloc{11, 22});
> +
> + s1 = make();
> + VERIFY( std::ranges::equal(s1, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s1, sl) );
> + VERIFY( s1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s1) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 1 );
> +
> + Hive s2(2, vc, dl, ScopedAlloc{11, 22});
> +
> + s2 = make();
> + VERIFY( std::ranges::equal(s2, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s2, sl) );
> + VERIFY( s2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s2) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> +
> + Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +
> + s3 = make();
> + VERIFY( std::ranges::equal(s2, il) );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s3, sl) );
> + VERIFY( s3.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(s3) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> +
> + Hive d0(dl, ScopedAlloc{33, 44});
> +
> + d0 = make();
> + VERIFY( std::ranges::equal(d0, il) );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( d0.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d0) == 22 );
> + VERIFY( limits_eq(d0, sl) );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> + }
> + else
> + {
> + VERIFY( limits_eq(d0, dl) );
> + VERIFY( d0.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d0) == 44 );
> + VERIFY( Counter::get_allocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_construct_count() == 2 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> + }
> +
> + Hive d1(1, vc, dl, ScopedAlloc{33, 44});
> +
> + d1 = make();
> + VERIFY( std::ranges::equal(d1, il) );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( limits_eq(d1, sl) );
> + VERIFY( d1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d1) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() >= sizeof(Vector) );
> + VERIFY( Counter::get_destruct_count() == 1 );
> + }
> + else
> + {
> + VERIFY( limits_eq(d1, dl) );
> + VERIFY( d1.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d1) == 44 );
> + VERIFY( Counter::get_allocation_count() >= 0 );
> + VERIFY( Counter::get_construct_count() == 1 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> + }
> +
> + Hive d2(2, vc, dl, ScopedAlloc{33, 44});
> +
> + d2 = make();
> + VERIFY( std::ranges::equal(d2, il) );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( d2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d2) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> + VERIFY( Counter::get_destruct_count() == 2 );
> + }
> + else
> + {
> + VERIFY( limits_eq(d2, dl) );
> + VERIFY( d2.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d2) == 44 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 2 );
> + }
> +
> + Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + d3 = make();
> + VERIFY( std::ranges::equal(d3, il) );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( limits_eq(d3, sl) );
> + VERIFY( d3.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(d3) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() >= 3 * sizeof(Vector) );
> + VERIFY( Counter::get_destruct_count() == 3 );
> + }
> + else
> + {
> + VERIFY( limits_eq(d3, dl) );
> + VERIFY( d3.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(d3) == 44 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> + }
> +}
> +
> +template<bool Propagate>
> +void
> +test_empty()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::hive_limits sl(10, 20);
> + const std::hive_limits dl(30, 50);
> + const Vector vc{11, 12, 13};
> + std::optional<Hive> opt;
> + auto make = [&] -> Hive&&
> + {
> + opt.emplace(sl, ScopedAlloc{11, 22});
> + Counter::reset();
> + return std::move(*opt);
> + };
> +
> + Hive s0(dl, ScopedAlloc{11, 22});
> +
> + s0 = make();
> + VERIFY( s0.empty() );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s0, sl) );
> + VERIFY( s0.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive s3(3, vc, dl, ScopedAlloc{11, 22});
> +
> + s3 = make();
> + VERIFY( s3.empty() );
> + VERIFY( opt->empty() );
> + VERIFY( limits_eq(s3, sl) );
> + VERIFY( s3.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> +
> + Hive d0(dl, ScopedAlloc{33, 44});
> +
> + d0 = make();
> + VERIFY( d0.empty() );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( limits_eq(d0, sl) );
> + VERIFY( d0.get_allocator().get_personality() == 11 );
> + }
> + else
> + {
> + VERIFY( limits_eq(d0, dl) );
> + VERIFY( d0.get_allocator().get_personality() == 33 );
> + }
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + Hive d3(3, vc, dl, ScopedAlloc{33, 44});
> +
> + d3 = make();
> + VERIFY( d3.empty() );
> + VERIFY( opt->empty() );
> + if (Propagate)
> + {
> + VERIFY( limits_eq(d3, sl) );
> + VERIFY( d3.get_allocator().get_personality() == 11 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() >= 2 * sizeof(Vector) );
> + }
> + else
> + {
> + VERIFY( limits_eq(d3, dl) );
> + VERIFY( d3.get_allocator().get_personality() == 33 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + }
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 3 );
> +}
> +
> +template<bool Propagate>
> +void
> +test_swap()
> +{
> + using PropAlloc = propagating_allocator<int, Propagate>;
> + using Vector = std::vector<int, PropAlloc>;
> + using ScopedAlloc = std::scoped_allocator_adaptor<
> + propagating_allocator<Vector, Propagate, tracker_allocator<Vector>>,
> + PropAlloc>;
> + using Hive = std::hive<Vector, ScopedAlloc>;
> +
> + const std::initializer_list<Vector> il1 = {Vector{1, 2, 3}, Vector{4,
> 5, 6}};
> + const std::initializer_list<Vector> il2 = {Vector{11, 12, 13}};
> + const std::hive_limits hl1(10, 20);
> + const std::hive_limits hl2(30, 50);
> +
> + Hive h1(il1, hl1, ScopedAlloc{11, 22});
> + Hive h2(il2, hl2, ScopedAlloc{11, 22});
> + Hive h3(il2, hl2, ScopedAlloc{33, 44});
> + Counter::reset();
> +
> + h1.swap(h2);
> + VERIFY( std::ranges::equal(h1, il2) );
> + VERIFY( std::ranges::equal(h2, il1) );
> + VERIFY( limits_eq(h1, hl2) );
> + VERIFY( limits_eq(h2, hl1) );
> + VERIFY( h1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h1) == 22 );
> + VERIFY( h2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h2) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + std::swap(h1, h2);
> + VERIFY( std::ranges::equal(h1, il1) );
> + VERIFY( std::ranges::equal(h2, il2) );
> + VERIFY( limits_eq(h1, hl1) );
> + VERIFY( limits_eq(h2, hl2) );
> + VERIFY( h1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h1) == 22 );
> + VERIFY( h2.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h2) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + if constexpr (Propagate)
> + {
> + h1.swap(h3);
> + VERIFY( std::ranges::equal(h1, il2) );
> + VERIFY( std::ranges::equal(h3, il1) );
> + VERIFY( limits_eq(h1, hl2) );
> + VERIFY( limits_eq(h3, hl1) );
> + VERIFY( h1.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(h1) == 44 );
> + VERIFY( h3.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h3) == 22 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> +
> + std::swap(h1, h3);
> + VERIFY( std::ranges::equal(h1, il1) );
> + VERIFY( std::ranges::equal(h3, il2) );
> + VERIFY( limits_eq(h1, hl1) );
> + VERIFY( limits_eq(h3, hl2) );
> + VERIFY( h1.get_allocator().get_personality() == 11 );
> + VERIFY( elem_alloc_personality(h1) == 22 );
> + VERIFY( h3.get_allocator().get_personality() == 33 );
> + VERIFY( elem_alloc_personality(h3) == 44 );
> + VERIFY( Counter::get_allocation_count() == 0 );
> + VERIFY( Counter::get_deallocation_count() == 0 );
> + VERIFY( Counter::get_construct_count() == 0 );
> + VERIFY( Counter::get_destruct_count() == 0 );
> + }
> +}
> +
> +template<bool Propagate>
> +void
> +test_all()
> +{
> + test_ctor<Propagate>();
> + test_assign<Propagate>();
> + test_empty<Propagate>();
> + test_swap<Propagate>();
> +}
> +
> +int main()
> +{
> + test_all<true>();
> + test_all<false>();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> b/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> new file mode 100644
> index 00000000000..41b6316425b
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
> @@ -0,0 +1,86 @@
> +// { dg-do run { target c++26 } }
> +// { dg-timeout-factor 2 }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <span>
> +#include <testsuite_hooks.h>
> +#include <testsuite_iterators.h>
> +
> +template<typename V, typename Range>
> +void
> +do_test(std::hive_limits hl =
> std::hive<V>::block_capacity_default_limits())
> +{
> + // The range's value_type.
> + using T = std::ranges::range_value_t<Range>;
> + T a[]{1,2,3,4,5,6,7,8,9,10};
> +
> + auto eq = [](const std::hive<V>& l, std::span<T> r) {
> + return std::ranges::equal(l, r, std::equal_to<>{});
> + };
> +
> + std::hive<V> h(std::from_range, Range(a, a+4), hl);
> + VERIFY( eq(h, {a, 4}) );
> +
> + h.insert_range(Range(a+4, a+9));
> + VERIFY( eq(h, {a, 9}) );
> +
> + h.assign_range(Range(a, a+10));
> + VERIFY( eq(h, {a, 10}) );
> +
> + if constexpr (std::ranges::forward_range<Range>)
> + {
> + Range r(a, a+10);
> + auto it = r.begin();
> + std::hive<V> h2(it, std::next(it, 3), hl);
> + VERIFY( eq(h2, {a, 3}) );
> +
> + h2.insert(std::next(it, 3), std::next(it, 10));
> + VERIFY( eq(h2, {a, 10}) );
> +
> + h2.assign(it, std::next(it, 6));
> + VERIFY( eq(h2, {a, 6}) );
> + }
> +}
> +
> +template<typename Range>
> +void
> +do_test_l()
> +{
> + do_test<int, Range>();
> + do_test<int, Range>(std::hive_limits(2, 3));
> + do_test<int, Range>(std::hive_limits(4, 8));
> +}
> +
> +int main()
> +{
> + using namespace __gnu_test;
> +
> + do_test_l<test_forward_range<int>>();
> + do_test_l<test_forward_sized_range<int>>();
> + do_test_l<test_sized_range_sized_sent<int, forward_iterator_wrapper>>();
> +
> + do_test_l<test_input_range<int>>();
> + do_test_l<test_input_sized_range<int>>();
> + do_test_l<test_sized_range_sized_sent<int, input_iterator_wrapper>>();
> +
> + do_test_l<test_range<int, input_iterator_wrapper_nocopy>>();
> + do_test_l<test_sized_range<int, input_iterator_wrapper_nocopy>>();
> + do_test_l<test_sized_range_sized_sent<int,
> input_iterator_wrapper_nocopy>>();
> +
> + do_test_l<test_forward_range<short>>();
> + do_test_l<test_input_range<short>>();
> +
> + // Not lvalue-convertible to int
> + struct C {
> + constexpr C(int v) : val(v) { }
> + constexpr operator int() && { return val; }
> + constexpr bool operator==(int b) const { return b == val; }
> + int val;
> + };
> + using rvalue_input_range = test_range<C, input_iterator_wrapper_rval>;
> + do_test<int, rvalue_input_range>();
> +
> + return true;
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> b/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> new file mode 100644
> index 00000000000..43e4a79f5f4
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/splice.cc
> @@ -0,0 +1,200 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <flat_set>
> +#include <testsuite_hooks.h>
> +
> +template<typename T>
> +void
> +check_inserts(std::hive<T>& hive)
> +{
> + std::flat_set<int> expected(std::from_range, hive);
> +
> + auto it = hive.emplace(1);
> + VERIFY( *it == 1 );
> + expected.insert(1);
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + std::vector<int> v{11, 12, 13, 14, 15};
> + hive.insert(v.begin(), v.end());
> + expected.insert(v.begin(), v.end());
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + v = {16, 17, 18};
> + hive.insert_range(v);
> + expected.insert(v.begin(), v.end());
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +
> + it = hive.insert(2);
> + VERIFY( *it == 2 );
> + expected.insert(2);
> +
> + it = hive.insert(hive.end(), 3);
> + VERIFY( *it == 3 );
> + expected.insert(3);
> +
> + it = hive.emplace_hint(hive.end(), 4);
> + VERIFY( *it == 4 );
> + expected.insert(4);
> + VERIFY( std::flat_set<int>(std::from_range, hive) == expected );
> +}
> +
> +template<typename Cont>
> +std::ranges::subrange<typename Cont::iterator>
> +woend(Cont& cont)
> +{ return {cont.begin(), std::prev(cont.end())}; }
> +
> +template<typename T>
> +void
> +splice(std::hive<T>& dst, std::hive<T>& src, size_t reserved)
> +{
> + using subhive = std::ranges::subrange<typename std::hive<T>::iterator>;
> +
> + std::vector<int> din(std::from_range, dst);
> + subhive dsr(dst.begin(), std::prev(dst.end()));
> + size_t dcap = dst.capacity();
> +
> + std::vector<int> sin(std::from_range, src);
> + subhive ssr(src.begin(), std::prev(src.end()));
> + size_t scap = src.capacity();
> +
> + dst.splice(src);
> + VERIFY( src.empty() );
> + VERIFY( src.capacity() == reserved );
> +
> + VERIFY( dst.size() == din.size() + sin.size() );
> + VERIFY( dst.capacity() == dcap + scap - reserved );
> + VERIFY( std::ranges::equal(dst, std::views::concat(din, sin)) );
> +
> + // Verify iterator stabilty
> + auto sstart = std::next(dst.begin(), din.size());
> + auto last = std::prev(sstart);
> + VERIFY( std::ranges::equal(dsr, woend(din)) );
> + VERIFY( dsr.begin() == dst.begin() );
> + VERIFY( dsr.end() == std::prev(sstart) );
> + VERIFY( std::ranges::equal(ssr, woend(sin)) );
> + VERIFY( ssr.begin() == sstart );
> + VERIFY( ssr.end() == std::prev(dst.end()) );
> +
> + // Validate free list by inserting elements
> + check_inserts(dst);
> + check_inserts(src);
> +}
> +
> +template<typename T>
> +void
> +swap(std::hive<T>& dst, std::hive<T>& src, size_t)
> +{
> + using subhive = std::ranges::subrange<typename std::hive<T>::iterator>;
> +
> + std::vector<int> din(std::from_range, dst);
> + auto dsr = woend(dst);
> + size_t dcap = dst.capacity();
> +
> + std::vector<int> sin(std::from_range, src);
> + auto ssr = woend(src);
> + size_t scap = src.capacity();
> +
> + dst.swap(src);
> + VERIFY( src.size() == din.size() );
> + VERIFY( src.capacity() == dcap );
> + VERIFY( std::ranges::equal(src, din) );
> +
> + VERIFY( dst.size() == sin.size() );
> + VERIFY( dst.capacity() == scap );
> + VERIFY( std::ranges::equal(dst, sin) );
> +
> + // Verify iterator stabilty
> + VERIFY( std::ranges::equal(dsr, woend(din)) );
> + VERIFY( dsr.begin() == src.begin() );
> + VERIFY( dsr.end() == std::prev(src.end()) );
> + VERIFY( std::ranges::equal(ssr, woend(sin)) );
> + VERIFY( ssr.begin() == dst.begin() );
> + VERIFY( ssr.end() == std::prev(dst.end()) );
> +
> + dsr.front() = 33;
> + ssr.front() = 44;
> + VERIFY( *dst.begin() == 44 );
> + VERIFY( *src.begin() == 33 );
> +
> + // Validate free list by inserting elements
> + check_inserts(dst);
> + check_inserts(src);
> +}
> +
> +template<typename T>
> +using op_t = void(*)(std::hive<T>&, std::hive<T>&, size_t);
> +
> +void
> +test_limits(op_t<int> op, std::hive_limits hl)
> +{
> + std::hive<int> d1(std::from_range, std::views::iota(0, 10), hl);
> + std::hive<int> s1(std::from_range, std::views::iota(10, 20), hl);
> + op(d1, s1, 0);
> +
> + std::hive<int> d2(std::from_range, std::views::iota(0, 10), hl);
> + std::hive<int> s2(std::from_range, std::views::iota(10, 20), hl);
> + size_t c2 = s2.capacity();
> + d2.reserve(d2.capacity() + 50);
> + s2.reserve(s2.capacity() + 30);
> + op(d2, s2, s2.capacity() - c2);
> +
> + auto erase_even = [](auto& hive)
> + {
> + for (auto it = hive.begin(); it != hive.end(); ++it)
> + it = hive.erase(it);
> + };
> +
> + std::hive<int> d3(std::from_range, std::views::iota(0, 50), hl);
> + std::hive<int> s3(std::from_range, std::views::iota(100, 150), hl);
> + erase_even(s3);
> + op(d3, s3, 0);
> +
> + std::hive<int> d4(std::from_range, std::views::iota(0, 50), hl);
> + std::hive<int> s4(std::from_range, std::views::iota(100, 150), hl);
> + erase_even(d4);
> + erase_even(s4);
> + op(d4, s4, 0);
> +
> + std::hive<int> d5(std::from_range, std::views::iota(0, 50), hl);
> + std::hive<int> s5(std::from_range, std::views::iota(100, 150), hl);
> + erase_even(d5);
> + op(d5, s5, 0);
> +}
> +
> +void
> +test_op(op_t<int> op)
> +{
> + test_limits(op, std::hive<int>::block_capacity_default_limits());
> + test_limits(op, std::hive_limits(20, 50));
> + test_limits(op, std::hive_limits(5, 10));
> + test_limits(op, std::hive_limits(10, 10));
> + test_limits(op, std::hive_limits(2, 4));
> +}
> +
> +void
> +test_limits_mismatch()
> +{
> + std::hive<int> dst(std::from_range, std::views::iota(0, 50),
> std::hive_limits(10, 20));
> + std::hive<int> src(std::from_range, std::views::iota(100, 150),
> std::hive_limits(20, 50));
> + try
> + {
> + dst.splice(src);
> + VERIFY(false);
> + }
> + catch (const std::length_error&)
> + { }
> +
> + VERIFY( std::ranges::equal(dst, std::views::iota(0, 50)) );
> + VERIFY( std::ranges::equal(src, std::views::iota(100, 150)) );
> +}
> +
> +int main()
> +{
> + test_op(splice);
> + test_op(swap);
> + test_limits_mismatch();
> +}
> diff --git a/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> b/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> new file mode 100644
> index 00000000000..f6be21b10e4
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/23_containers/hive/throws.cc
> @@ -0,0 +1,352 @@
> +// { dg-do run { target c++26 } }
> +
> +#include <hive>
> +
> +#include <algorithm>
> +#include <ranges>
> +#include <vector>
> +#include <testsuite_hooks.h>
> +
> +struct Thrower
> +{
> + struct Exception {};
> +
> + static inline size_t copy = 0;
> + static inline size_t assign = 0;
> + static inline size_t create = 0;
> + static inline size_t destroy = 0;
> + static inline size_t throwAfter = -1;
> +
> + static void resetCounters()
> + {
> + create = copy = assign = destroy = 0;
> + throwAfter = -1;
> + }
> +
> + Thrower()
> + : Thrower(0)
> + {}
> +
> + Thrower(int p)
> + : x(p)
> + { ++create; }
> +
> + ~Thrower()
> + { ++destroy; }
> +
> + Thrower(const Thrower& other)
> + : x(other.x)
> + {
> + if (copy + assign >= throwAfter)
> + throw Exception();
> + ++copy;
> + }
> +
> + Thrower& operator=(const Thrower& other)
> + {
> + if (copy + assign >= throwAfter)
> + throw Exception();
> +
> + ++assign;
> + this->x = other.x;
> + return *this;
> + }
> +
> + int x;
> +
> + friend constexpr bool
> + operator==(const Thrower&, const Thrower&) = default;
> +
> + friend constexpr bool
> + operator==(const Thrower& nm, int y)
> + { return nm.x == y; }
> +};
> +
> +constexpr bool
> +limits_eq(std::hive_limits lhs, std::hive_limits rhs)
> +{ return lhs.min == rhs.min && lhs.max == rhs.max; }
> +
> +template<typename Hive>
> +constexpr bool
> +limits_eq(const Hive& hive, std::hive_limits rhs)
> +{ return limits_eq(hive.block_capacity_limits(), rhs); }
> +
> +void
> +test_inserts(std::hive<Thrower>& hive)
> +{
> + const std::vector<int> source(std::from_range, hive |
> std::views::transform(&Thrower::x));
> + auto is_subset = [&source](std::span<const int> s, const
> std::hive<Thrower>& h)
> + {
> + auto sit = s.begin(), send = s.end();
> + auto hit = h.begin(), hend = h.end();
> + for (auto hit = h.begin(), hend = h.end();
> + sit != send && hit != hend;
> + ++hit)
> + if (hit->x == *sit)
> + ++sit;
> + return sit == send;
> + };
> +
> + std::vector<Thrower> v{1,2,3,4,5,6,7,8,9,10};
> +
> + Thrower::resetCounters();
> + Thrower::throwAfter = 0;
> + try {
> + hive.emplace(v.front());
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( hive.size() == source.size() );
> + VERIFY( is_subset(source, hive) );
> + VERIFY( Thrower::copy == 0 );
> + VERIFY( Thrower::assign == 0 );
> +
> + try {
> + hive.insert_range(v);
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( hive.size() == source.size() );
> + VERIFY( is_subset(source, hive) );
> + VERIFY( Thrower::copy == 0 );
> + VERIFY( Thrower::assign == 0 );
> +
> + try {
> + hive.assign_range(v);
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( hive.size() == source.size() );
> + VERIFY( is_subset(source, hive) );
> + VERIFY( Thrower::copy == 0 );
> + VERIFY( Thrower::assign == 0 );
> +
> + Thrower::resetCounters();
> + Thrower::throwAfter = 3;
> + try {
> + hive.insert_range(v);
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( hive.size() == source.size() + 3 );
> + VERIFY( is_subset(source, hive) );
> + VERIFY( Thrower::copy == 3 );
> + VERIFY( Thrower::assign == 0 );
> +
> + Thrower::resetCounters();
> + Thrower::throwAfter = 7;
> + try {
> + hive.assign_range(v);
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( hive.size() >= source.size() + 0 );
> + VERIFY( hive.size() <= source.size() + 7 );
> + VERIFY( is_subset(source | std::views::drop(7), hive) );
> + VERIFY( Thrower::copy + Thrower::assign == 7 );
> +
> + Thrower::resetCounters();
> +}
> +
> +void
> +test_inserts()
> +{
> + const auto hl = std::hive<Thrower>::block_capacity_default_limits();
> + std::hive<Thrower> h0(hl);
> + test_inserts(h0);
> +
> + std::hive<Thrower> h1(hl);
> + h1.reserve(4);
> + h1.reserve(3);
> + test_inserts(h1);
> +
> + std::hive<Thrower> h2({-1, -2, -3, -4, -5}, hl);
> + test_inserts(h2);
> +
> + std::hive<Thrower> h3(100, -1, hl);
> + for (auto it = h3.begin(); it != h3.end(); )
> + it = h3.erase(++it);
> + test_inserts(h3);
> +
> + std::hive<Thrower> h4(80, -2, hl);
> + for (auto it = h4.begin(); it != h4.end(); std::advance(it, 10))
> + it = h4.erase(it, std::next(it, 10));
> + test_inserts(h4);
> +
> + std::hive<Thrower> h5(50, -3, hl);
> + h5.erase(std::next(h5.begin(), 42), std::next(h5.begin(), 48));
> + h5.erase(std::next(h5.begin(), 33), std::next(h5.begin(), 35));
> + h5.erase(std::next(h5.begin(), 36), std::next(h5.begin(), 38));
> + h5.erase(std::next(h5.begin(), 24), std::next(h5.begin(), 28));
> + h5.erase(std::next(h5.begin(), 12), std::next(h5.begin(), 19));
> + h5.erase(std::next(h5.begin()), std::next(h5.begin(), 5));
> + test_inserts(h5);
> +}
> +
> +void
> +test_shrink_to_fit()
> +{
> + std::initializer_list<Thrower> il
> + { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 };
> + std::initializer_list<Thrower> ex
> + { 0, 2, 4, 6, 8, 10, 12, 14 };
> + std::hive<Thrower> h1(il, std::hive_limits(2, 5));
> + std::erase_if(h1, [](const Thrower& t) { return t.x % 2; });
> + VERIFY( std::ranges::equal(h1, ex) );
> +
> + Thrower::resetCounters();
> + Thrower::throwAfter = 0;
> + try {
> + h1.shrink_to_fit();
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( h1.size() == 8 );
> + // 3x5 active block, and 1x3 reserved
> + VERIFY( h1.capacity() == 18 );
> + VERIFY( std::ranges::is_permutation(h1, ex) );
> + VERIFY( Thrower::copy == 0 );
> + VERIFY( Thrower::destroy == 0 );
> +
> + Thrower::throwAfter = 3;
> + try {
> + h1.shrink_to_fit();
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( h1.size() == 8 );
> + // 2x5 and 1x3 active block
> + VERIFY( h1.capacity() == 13 );
> + VERIFY( std::ranges::is_permutation(h1, ex) );
> + VERIFY( Thrower::copy == 3 );
> + VERIFY( Thrower::destroy == 3 );
> +
> + Thrower::throwAfter = 5;
> + h1.shrink_to_fit();
> + // 1x5, 1x3 active block
> + VERIFY( h1.capacity() == 8 );
> + VERIFY( std::ranges::is_permutation(h1, ex) );
> + VERIFY( Thrower::copy == 5 );
> + VERIFY( Thrower::destroy == 5 );
> +
> + Thrower::resetCounters();
> +}
> +
> +void
> +test_reshape()
> +{
> + std::initializer_list<Thrower> il
> + { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 };
> + const std::hive_limits hl(4, 4);
> + std::hive<Thrower> h1(il, hl);
> +
> + Thrower::resetCounters();
> + Thrower::throwAfter = 0;
> + try {
> + h1.reshape({5, 5});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 3x4 active block, 3x5 reserved
> + VERIFY( h1.capacity() == 27 );
> + VERIFY( std::ranges::equal(h1, il) );
> + VERIFY( Thrower::copy == 0 );
> + VERIFY( Thrower::destroy == 0 );
> +
> + // Throw after first active block of size 4
> + Thrower::throwAfter = 4;
> + try {
> + h1.reshape({5, 5});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 2x4+1x5 active block, 2x5 reserved
> + VERIFY( h1.capacity() == 23 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 4 );
> + VERIFY( Thrower::destroy == 4 );
> +
> + // Throw in middle of active block of size 4
> + Thrower::throwAfter = 10;
> + try {
> + h1.reshape({5, 5});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 1x4+2x5 active block, 1x5 reserved
> + VERIFY( h1.capacity() == 19 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 10 );
> + VERIFY( Thrower::destroy == 10 );
> +
> + // Going back to blocks of size 4, throw in mid of first block
> + Thrower::resetCounters();
> + Thrower::throwAfter = 4;
> + try {
> + h1.reshape({4, 4});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 2x4+2x5 active block, 1x4 reserved
> + VERIFY( h1.capacity() == 22 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 4 );
> + VERIFY( Thrower::destroy == 4 );
> +
> + // Finish that first block of size 5
> + Thrower::throwAfter = 5;
> + try {
> + h1.reshape({4, 4});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 2x4+1x5 active block, 1x4 reserved
> + VERIFY( h1.capacity() == 17 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 5 );
> + VERIFY( Thrower::destroy == 5 );
> +
> + Thrower::throwAfter = 8;
> + try {
> + h1.reshape({4, 4});
> + VERIFY( false );
> + } catch (const Thrower::Exception&) {
> + }
> + VERIFY( limits_eq(h1, {4, 5}) );
> + VERIFY( h1.size() == 12 );
> + // 2x4+1x5 active block, 1x4 reserved
> + VERIFY( h1.capacity() == 17 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 8 );
> + VERIFY( Thrower::destroy == 8 );
> +
> + // Move remaining 2 elements
> + Thrower::throwAfter = 10;
> + h1.reshape({4, 4});
> + VERIFY( limits_eq(h1, {4, 4}) );
> + VERIFY( h1.size() == 12 );
> + // 3x4 active blocks
> + VERIFY( h1.capacity() == 12 );
> + VERIFY( std::ranges::is_permutation(h1, il) );
> + VERIFY( Thrower::copy == 10 );
> + VERIFY( Thrower::destroy == 10 );
> +
> + Thrower::resetCounters();
> +}
> +
> +int main()
> +{
> + test_inserts();
> + test_shrink_to_fit();
> + test_reshape();
> +}
> --
> 2.55.0
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://gcc.gnu.org/pipermail/gcc-patches/attachments/20261001/2cb0668b/attachment-0001.htm>
More information about the Gcc-patches
mailing list