[RFC v2] libstdc++: Implement P0447R28 std::hive
Tomasz Kamiński
tkaminsk@redhat.com
Tue Oct 6 11:40:19 GMT 2026
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 _Blocks stores the number of free elements (_M_elements), which
allows _M_clear_elems to skip calls of destructor for allocators that do not
override destroy. And also for more optimial implementation of insertion of
sized range - for blocks that are completly filled we avoid checking iterator
against end.
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 first slot used for
storing elements (_M_slots) and it offset from start of allocation (_M_offset)
are stored in block. This leads to significantly (30%-40%) faster iterations
time, comparing to storing pointer to allocation and computing offset on
the fly.
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.
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.
---
v2
- stores the first element to pointer and it offset from allocation
inside block, as this leads to significantly faster iteration times
- maintains numbe of free slots inisde block, simpliyfing clear
operations
libstdc++-v3/include/Makefile.am | 2 +
libstdc++-v3/include/Makefile.in | 2 +
libstdc++-v3/include/bits/hive.h | 2232 +++++++++++++++++
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 | 84 +
.../testsuite/23_containers/hive/splice.cc | 200 ++
.../testsuite/23_containers/hive/throws.cc | 352 +++
18 files changed, 4965 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..b1478d94371
--- /dev/null
+++ b/libstdc++-v3/include/bits/hive.h
@@ -0,0 +1,2232 @@
+// 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
+{
+ 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>;
+
+ 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 __offset, _SizeT __capacity) noexcept
+ : _M_slots(__mem + __offset), _M_offset(__offset),
+ _M_capacity(__capacity), _M_free(_M_capacity)
+ { _M_clear_slots(); }
+
+ _Block* _M_next = nullptr;
+ _Block* _M_prev = nullptr;
+ _Block* _M_next_free = nullptr;
+ _Block* _M_prev_free = nullptr;
+
+ _Alloc_ptr _M_slots = nullptr;
+ _SizeT _M_capacity = 0;
+ _SizeT _M_offset = 0;
+ _SizeT _M_free = 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 == 0; }
+
+ [[__gnu__::__always_inline__]]
+ bool
+ _M_empty() const noexcept
+ { return _M_free == _M_capacity; }
+
+ [[__gnu__::__always_inline__]]
+ _Alloc_ptr
+ _M_memory() const noexcept
+ { return _M_slots - _M_offset; }
+
+ [[__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_slots) + __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);
+ _M_free -= __n;
+ 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));
+
+ _M_free += __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)
+ {
+ using _TpAllocT = std::allocator_traits<_TpAlloc>;
+ size_t __removed = _M_capacity - _M_free;
+ _M_free = _M_capacity;
+
+ // If type is trivially destructible and allocator does not provide destroy
+ // (allocator_traits cannot be specialized), then skip calling detructor.
+ if constexpr (is_trivially_destructible_v<_Tp>)
+ if constexpr (requires (typename _TpAllocT::pointer __p) { __alloc.destroy(__p); })
+ return __removed;
+
+ size_t __pos = 0, __first = 0;
+ while (__pos != _M_capacity)
+ if (_M_occupied(__pos))
+ _TpAllocT::destroy(__alloc, _M_elem(__pos++));
+ else
+ {
+ __pos += _M_free_count(__pos);
+ __first = __pos;
+ }
+
+ 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 __extra = _BlockT::_S_extra_slots(__capacity);
+ const size_t __count = __capacity + __extra;
+ 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, __extra, __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 + __cur->_M_offset;
+ __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();
+ 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));
+
+ const size_t __elems = __srcblock->_M_capacity - __srcblock->_M_free;
+ _M_self._M_insert_preallocated(__elems, _M_last, __nextit);
+
+ 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
+ {
+ 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 _Iterator, typename _Sentinel>
+ void
+ _M_insert_preallocated(size_t __count, _Iterator& __first, _Sentinel __last)
+ {
+ // Fillout initial blocks, we do not need to check against end
+ _BlockT* __block = _M_blocks._M_next_free();
+ while (__block->_M_free < __count)
+ {
+ __count -= __block->_M_free;
+ _M_fill_block(__block, __first, unreachable_sentinel);
+ __block = _M_blocks._M_next_free();
+ }
+
+ // For the last if it is not filled fully, check against end.
+ if (__block->_M_free == __count)
+ _M_fill_block(__block, __first, unreachable_sentinel);
+ else
+ _M_fill_block(__block, __first, __last);
+ }
+
+ 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_t(ranges::size(__rg));
+ reserve(_M_size + __new);
+ _M_insert_preallocated(__new, __it, __end);
+ }
+ 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
+ _M_insert_preallocated(__size - _M_size, __it, __end);
+ }
+ 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..1f77bfca283
--- /dev/null
+++ b/libstdc++-v3/testsuite/23_containers/hive/ranges.cc
@@ -0,0 +1,84 @@
+// { 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>();
+}
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
More information about the Libstdc++
mailing list