From: Tomasz Kamiński <[email protected]> Constructor and assigment are not implemented, as they depends on above. --- This is a forge pull request published on the gcc-patches mailing list mailing list as requested by tkaminsk via Sourceware Forge <[email protected]>. Forge discussion: https://forge.sourceware.org/gcc/gcc/pulls/224
Get it locally using: ``` git fetch forge-upstream "+refs/versioned_pull/224/*:refs/versioned_pull/224/*" git switch -c "pr-224-v1" "refs/versioned_pull/224/1/head" ``` Or, download the patch at: https://forge.sourceware.org/gcc/gcc/pulls/224.diff Created on: 2026-08-25 09:57:22+00:00 Latest update: 2026-08-25 10:18:25+00:00 Changes: 4 changed files, 1438 additions, 0 deletions Head revision: tkaminsk/gcc ref tk/hive commit 6a9eeea6b3648750c3507c399319a1182ca1ded2 Base revision: gcc/gcc ref trunk commit 70ebcf89f8534fe410163415f18c527b7b694b0b r17-3477-g70ebcf89f8534f Merge base: 70ebcf89f8534fe410163415f18c527b7b694b0b Requested Reviewers: Changed files: - A: hive.cpp - A: libstdc++-v3/include/bits/hive.h - M: libstdc++-v3/include/Makefile.am - M: libstdc++-v3/include/Makefile.in hive.cpp | 143 ++++ libstdc++-v3/include/Makefile.am | 1 + libstdc++-v3/include/Makefile.in | 1 + libstdc++-v3/include/bits/hive.h | 1293 ++++++++++++++++++++++++++++++ 4 files changed, 1438 insertions(+) create mode 100644 hive.cpp create mode 100644 libstdc++-v3/include/bits/hive.h diff --git a/hive.cpp b/hive.cpp new file mode 100644 index 0000000000000..0616051e1e1d7 --- /dev/null +++ b/hive.cpp @@ -0,0 +1,143 @@ +#include <iostream> +#include <bits/hive.h> +#include <ranges> +#include <vector> + +static_assert(std::forward_iterator<std::hive<int>::iterator>); +static_assert(std::ranges::range<std::hive<int>&>); + +void iterate(const std::hive<long long>& h) +{ + std::cout << "-- Forward: " << std::endl; + for (auto it = h.begin(), e = h.end(); it != e; ++it) + std::cout << *it << std::endl; + std::cout << "-- Backward: " << std::endl; + for (auto it = h.end(), b = h.begin(); it != b;) + std::cout << *--it << std::endl; +} + +void insert(std::hive<long long>& h) +{ + for (int i = 10; i < 100; i+= 10) + for (int j = 9; j > 0; j -= 2) + { + std::cout << "Emplace " << (i+j) << std::endl; + h.emplace(i + j); + } +} + +int main() +{ + std::hive<long long> h; + insert(h); + iterate(h); + + int r = 0; + while (!h.empty()) + { + std::cout << "---- Erase round: " << ++r << std::endl; + for (auto it = h.begin(), e = h.end(); it != e;) + { + std::cout << "Erase: " << *it << std::endl; + it = h.erase(it); + if (it == e) + break; + std::cout << "Keep: " << *it++ << std::endl; + } + std::cout << "- After erase " << std::endl; + for (auto it = h.begin(), e = h.end(); it != e; ++it) + std::cout << *it << std::endl; + } + + r = 0; + insert(h); + iterate(h); + + int n = 20; + while (!h.empty()) + { + std::cout << "---- Erase decreasing bulk round: " << ++r << std::endl; + for (auto it = h.begin(), e = h.end(); it != e;) + { + std::cout << "Erase: " << *it << " + " << n << std::endl; + auto next = it; + std::ranges::advance(next, n, e); + it = h.erase(it, next); + std::cout << "Size after: " << h.size() << std::endl; + if (it == e) + break; + + std::cout << "Keep: " << *it << " + " << n << std::endl; + std::ranges::advance(it, n, e); + } + std::cout << "- After erase " << std::endl; + for (auto it = h.begin(), e = h.end(); it != e; ++it) + std::cout << *it << std::endl; + + if (n >= 2) n /= 2; + } + + r = 0; + insert(h); + iterate(h); + + n = 1; + while (!h.empty()) + { + std::cout << "---- Erase increasing bulk round: " << ++r << std::endl; + for (auto it = h.begin(), e = h.end(); it != e;) + { + std::cout << "Erase: " << *it << " + " << n << std::endl; + auto next = it; + std::ranges::advance(next, n, e); + it = h.erase(it, next); + std::cout << "Size after: " << h.size() << std::endl; + if (it == e) + break; + std::cout << "Keep: " << *it << " + " << n << std::endl; + std::ranges::advance(it, n, e); + } + std::cout << "- After erase " << std::endl; + for (auto it = h.begin(), e = h.end(); it != e; ++it) + std::cout << *it << std::endl; + + n *= 2; + } + + std::vector<long long> v; + for (int i = 10; i < 50; i+= 10) + for (int j = 9; j > 0; j -= 1) + v.push_back(i + j); + + auto tv = [s = std::span(v)](size_t from, size_t count) + { + size_t offset = from % 10; + size_t start = (from / 10 - 1) * 10; + return std::views::transform(s.subspan(offset, count), [start](auto v) { return v + start; }); + }; + + std::cout << "---- Range insert" << std::endl; + h.insert_range(v); + h.insert_range(tv(50, 20)); + h.insert_range(tv(70, 5) | std::views::as_input); + h.insert_range(tv(75, 15) | std::views::as_input); + iterate(h); + + auto it = h.begin(), nt = it; + std::ranges::advance(nt, 60); + it = h.erase(it, nt); + std::ranges::advance(it, 7); + std::ranges::advance(nt = it, 6); + it = h.erase(it, nt); + + std::cout << "---- Assinging v" << std::endl; + h.assign_range(v); + iterate(h); + + h.assign_range(std::vector<int>{}); + h.assign_range(tv(60, 15)); + + std::cout << "---- Assinging v as input" << std::endl; + h.assign_range(v | std::views::as_input); + iterate(h); +} diff --git a/libstdc++-v3/include/Makefile.am b/libstdc++-v3/include/Makefile.am index 3c30aa21d6b55..9c9385cd6f682 100644 --- a/libstdc++-v3/include/Makefile.am +++ b/libstdc++-v3/include/Makefile.am @@ -231,6 +231,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 d081481293fff..afc3d5bb6b3bf 100644 --- a/libstdc++-v3/include/Makefile.in +++ b/libstdc++-v3/include/Makefile.in @@ -587,6 +587,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 0000000000000..a96aa113559a8 --- /dev/null +++ b/libstdc++-v3/include/bits/hive.h @@ -0,0 +1,1293 @@ +// 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 + +#include <bits/stl_iterator_base_funcs.h> +#include <bits/stdexcept_throw.h> +#include <initializer_list> +#include <compare> +#include <bit> +#include <bits/align.h> +#include <bits/ranges_base.h> // ranges::distance +#include <bits/ranges_algobase.h> // ranges::copy +#include <bits/ranges_util.h> // ranges::subrange + +#include <debug/assertions.h> + +namespace std _GLIBCXX_VISIBILITY(default) +{ +_GLIBCXX_BEGIN_NAMESPACE_VERSION +_GLIBCXX_BEGIN_NAMESPACE_CONTAINER + +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 _Allocator = allocator<_Tp>> + class hive; + +namespace __hive +{ + struct _IgnorePtr + { + constexpr + _IgnorePtr(nullptr_t) + { } + + template<typename _Tp> + constexpr + _IgnorePtr(const volatile _Tp*) + { } + }; + + template<size_t _Bytes> + struct _Counter + { + static consteval auto + _S_select_size() + { +#ifdef __UINT64_TYPE__ + if constexpr (_Bytes == 8) + return static_cast<__UINT64_TYPE__>(0); + else +#endif +#ifdef __UINT32_TYPE__ + if constexpr (_Bytes == 4) + return static_cast<__UINT32_TYPE__>(0); + else +#endif +#ifdef __UINT16_TYPE__ + if constexpr (_Bytes == 2) + return static_cast<__UINT16_TYPE__>(0); + else +#endif + if constexpr (_Bytes == 1) + return static_cast<unsigned char>(0); + else + static_assert("Unsupported bytes count"); + } + + using _SizeT = decltype(_S_select_size()); + + static consteval size_t + max_size() + { + if constexpr (_Bytes >= 8) + return (size_t(1) << 48) - 1; + else if constexpr (_Bytes >= 4) + return (size_t(1) << 24) - 1; + else if constexpr (_Bytes >= 2) + return (size_t(1) << 12) - 1; + else + return 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) + { + _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) + { + 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) + { + 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) + { + *__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) + { + 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 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_next; + _SizeT _M_prev; + }; + + union _Slot + { + _Tp _M_val; + _Free_node _M_free; + }; + + struct _Reservation + { + _SizeT _M_pos; + _SizeT _M_capacity; + _SizeT _M_next; + }; + + using _Alloc_ptr = __ptr_rebind<_Ptr, _Slot>; + using _Mem_ptr = std::conditional_t< + // Block is stored at the first byte of allocated memory chunk, + // so their pointer value are the same. + is_pointer_v<_Ptr> && (alignof(void*) <= alignof(_Slot)), + _IgnorePtr, _Alloc_ptr>; + + static constexpr size_t + _S_slot_count(size_t __bytes) + { return (__bytes + sizeof(_Slot) - 1) / sizeof(_Slot); } + + static constexpr size_t + _S_extra_slots(size_t __capacity) + { + 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; + + _Block(_Alloc_ptr __mem, _SizeT __capacity) + : _M_mem(__mem), _M_capacity(__capacity) + { _M_clear_slots(); } + + _Block* _M_prev = nullptr; + _Block* _M_next = nullptr; + _Block* _M_next_free = nullptr; + + [[no_unique_address]] _Mem_ptr _M_mem = nullptr; + _SizeT _M_capacity = 0; + _SizeT _M_free_head = -1; + + [[__gnu__::__always_inline__]] + bool + _M_sentinel() const noexcept + { return _M_capacity == 0; } + + [[__gnu__::__always_inline__]] + bool + _M_full() const noexcept + { return _M_free_head == npos; } + + [[__gnu__::__always_inline__]] + bool + _M_empty() const noexcept + { + // TODO: Could also compare _M_skipfield(0) with _M_capacity. + return (_M_free_head == 0) && (_M_slot(0)->_M_free._M_next == npos); + } + + [[__gnu__::__always_inline__]] + _Alloc_ptr + _M_memory() const noexcept + { + if constexpr (is_pointer_v<_Ptr> && (alignof(void*) <= alignof(_Slot))) + return reinterpret_cast<_Slot*>(const_cast<_Block*>(this)); + else + return _M_mem; + } + + [[__gnu__::__always_inline__]] + unsigned char* + _M_skipfield(size_t __pos) const noexcept + { + return reinterpret_cast<unsigned char*>(const_cast<_Block*>(this)) + + sizeof(_Block) + __pos; + } + + [[__gnu__::__always_inline__]] + bool + _M_occupied(size_t __pos) const noexcept + { return *_M_skipfield(__pos) == 0xff; } + + [[__gnu__::__always_inline__]] + size_t + _M_first_occupied() const noexcept + { + if (_M_sentinel() || _M_occupied(0)) + return 0; + return _CounterT::_S_load_fwd(_M_skipfield(0)); + } + + [[__gnu__::__always_inline__]] + _Slot* + _M_slot(size_t __pos) const noexcept + { return std::to_address(_M_memory()) + _S_extra_slots(_M_capacity) + __pos; } + + [[__gnu__::__always_inline__]] + _Tp* + _M_elem(size_t __pos) const noexcept + { return std::addressof(_M_slot(__pos)->_M_val); } + + [[__gnu__::__always_inline__]] + _Free_node& + _M_free_node(size_t __pos) const noexcept + { return _M_slot(__pos)->_M_free; } + + // Returns the information about the first range of empty slotents, preserving + // values stored inside the slot. + [[__gnu__::__always_inline__]] + _Reservation + _M_reserve_slots() + { + return {_M_free_head, + _CounterT::_S_load_fwd(_M_skipfield(_M_free_head)), + _M_free_node(_M_free_head)._M_next}; + } + + // 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) + { + std::fill_n(_M_skipfield(__res._M_pos), __n, 0xff); + if (__n < __res._M_capacity) + { + // Node is partially used, trim it size, and adjust node. + _M_free_head += __n; + _M_free_node(_M_free_head) = {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_free_node(_M_free_head)._M_prev = npos; + return false; + } + else + { + // Node and block is fully used. + _M_free_head = npos; + return true; + } + } + + // Marks are slots as empty, creating single free node + // for range [0, _M_capacity) + void + _M_clear_slots() + { + std::fill_n(_M_skipfield(0), _M_capacity, 0); + _CounterT::_S_store(_M_skipfield(0), _M_capacity); + _M_free_node(0) = { npos, npos }; + _M_free_head = 0; + } + + // 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 + size_t + _M_release_slots(size_t& __pos, size_t __n) + { + size_t __pfree = 0, __nfree = 0; + if ((__pos > 0) && !_M_occupied(__pos - 1)) + __pfree = _CounterT::_S_load_bwd(_M_skipfield(__pos - 1)); + if ((__pos + __n < _M_capacity) && !_M_occupied(__pos + __n)) + __nfree = _CounterT::_S_load_fwd(_M_skipfield(__pos + __n)); + + if (__pfree + __nfree + __n == _M_capacity) + { + // All slots in blocks become empty, simply clear the block. + _M_clear_slots(); + __pos = _M_capacity; + return true; + } + + auto __link_next = [this](size_t __pos, size_t __next) + { + if (__pos != npos) + _M_free_node(__pos)._M_next = __next; + else + _M_free_head = __next; + }; + + auto __link_prev = [this](size_t __pos, size_t __prev) + { + if (__pos != npos) + _M_free_node(__pos)._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_free_node(__pos + __n); + __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); + _Free_node& __node = _M_free_node(__pos); + __node = _M_free_node(__pos + __n); + + // 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_free_node(__pos) = {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; + } + + [[__gnu__::__always_inline__]] + void + _M_set_next(_Block* __node) + { + _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 single linked list (_M_next_free), + // starting at _M_free_head() (which is _M_sent._M_next_free). + template<typename _Tp, typename _Allocator> + struct _Block_list + { + static consteval size_t + _S_counter_bytes() + { + size_t __max = sizeof(_Tp) / 2; +#ifdef __UINT64_TYPE__ + if (__max >= 8) + return 8; + else +#endif +#ifdef __UINT32_TYPE__ + if (__max >= 4) + return 4; + else +#endif +#ifdef __UINT16_TYPE__ + if (__max >= 2) + return 2; + else +#endif + return 1; + } + + using _CounterT = _Counter<_S_counter_bytes()>; + using _SizeT = typename _CounterT::_SizeT; + using _BlockT = _Block<_Tp, _CounterT, typename allocator_traits<_Allocator>::pointer>; + using _SlotT = typename _BlockT::_Slot; + + using _SAlloc = typename allocator_traits<_Allocator>::template rebind_alloc<_SlotT>; + using _SAllocTraits = typename allocator_traits<_Allocator>::template rebind_traits<_SlotT>; + + static consteval hive_limits + _S_hard_limits() + { + return {1, 10}; + + 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(1, __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(1, __max); + } + } + + static consteval hive_limits + _S_default_limits() + { + 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; + hive_limits _M_limits = _S_default_limits(); + size_t _M_capacity = 0; + size_t _M_last_capacity = _S_default_limits().min; + [[no_unique_address]] _Allocator _M_alloc; + + ~_Block_list() + { + _SAlloc __salloc(_M_alloc); + + _BlockT* __block = _M_first; + while (__block) + { + _BlockT* __cur = __block; + auto __ptr = __cur->_M_memory(); + auto __count = __cur->_M_capacity; + __block = __block->_M_next; + + // Skip sentinel node + if (__cur->_M_sentinel()) + continue; + + // Custom pointer may have non-trivial destructor, call it before releasing + // memory. + __cur->~_BlockT(); + __count += _BlockT::_S_extra_slots(__count); + _SAllocTraits::deallocate(__salloc, __ptr, __count); + } + } + + [[__gnu__::__always_inline__]] + _BlockT* + _M_free_head() const noexcept + { return _M_sent._M_next_free; } + + [[__gnu__::__always_inline__]] + void + _M_pop_free() + { _M_sent._M_next_free = _M_sent._M_next_free->_M_next_free; } + + [[__gnu__::__always_inline__]] + void + _M_append_free(_BlockT* __block) + { + __block->_M_next_free = _M_sent._M_next_free; + _M_sent._M_next_free = __block; + } + + void + _M_expose(_BlockT* __first, _BlockT* __last) + { + __first->_M_prev->_M_set_next(__last->_M_next); + + _M_link_prev(_M_sent, __first); + __last->_M_set_next(&_M_sent); + } + + [[__gnu__::__always_inline__]] + void + _M_expose(_BlockT* __block) + { _M_expose(__block, __block); } + + void + _M_hide(_BlockT* __first, _BlockT* __last) + { + _M_link_prev(*__first, __last->_M_next); + _M_append_reserved(__first, __last); + } + + [[__gnu__::__always_inline__]] + void + _M_hide(_BlockT* __block) + { _M_hide(__block, __block); } + + _BlockT* + _M_reserve_block(size_t __capacity) + { + _SAlloc __salloc(_M_alloc); + + _BlockT* __block = _M_allocate_block(__salloc, __capacity); + _M_append_reserved(__block, __block); + _M_append_free(__block); + _M_capacity += __capacity; + return __block; + } + + _BlockT* + _M_reserve_block() + { + _M_last_capacity *= 2; + if (_M_last_capacity > _M_limits.max) + _M_last_capacity = _M_limits.max; + return _M_reserve_block(_M_last_capacity); + } + + private: + static _BlockT* + _M_allocate_block(_SAlloc& __alloc, size_t __capacity) + { + const size_t __count = __capacity + _BlockT::_S_extra_slots(__capacity); + auto __mem = _SAllocTraits::allocate(__alloc, __count); + + void* __ptr = std::to_address(__mem); + size_t __space = __count * sizeof(_SlotT); + if constexpr (alignof(_BlockT) > sizeof(_SlotT)) + __ptr = std::align(alignof(_BlockT), sizeof(_BlockT), __ptr, __space); + + return ::new(__ptr) _BlockT(__mem, __capacity); + } + + [[__gnu__::__always_inline__]] + void + _M_link_prev(_BlockT& __of, _BlockT* __to) + { + 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; + + _M_pos -= _CounterT::_S_load_bwd(_M_block->_M_skipfield(_M_pos)); + if (_M_pos) + 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 _GLIBCXX_STD_C::hive; + }; +} // namespace __hive + +template<typename _Tp, typename _Allocator> + class hive + { + using _BlockListT = __hive::_Block_list<_Tp, _Allocator>; + using _BlockT = typename _BlockListT::_BlockT; + using _CounterT = typename _BlockListT::_CounterT; + using _AllocT = allocator_traits<_Allocator>; + + public: + using size_type = size_t; + using difference_type = ptrdiff_t; + using iterator = __hive::_Iterator<_Tp, _BlockT>; + using const_iterator = __hive::_Iterator<const _Tp, _BlockT>; + + hive() = default; + + ~hive() + { + if (empty()) + return; + + _BlockT* __block = _M_blocks._M_first; + while (__block != &_M_blocks._M_sent) + { + _M_clear(__block); + __block = __block->_M_next; + } + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + void + assign_range(_Rg&& __rg) + { + if (empty()) + return 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, __pos), end()); + else + erase(const_iterator(__block->_M_next), 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 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 from + size_t __last = _M_assign_in_block(__block, __it, __end); + return __erase_from(__block, __last); + } + else + { + // Fully assign block, we do not need to check end + _M_assign_in_block(__block, __it, unreachable_sentinel); + __assigned += __block->_M_capacity; + } + + // Insert remaining elements + insert_range(ranges::subrange(std::move(__it), __end, + __size - __assigned)); + } + else + { + // Fillout existing active blocks + for (_BlockT* __block = _M_blocks._M_first; + !__block->_M_sentinel(); __block = __block->_M_next) + { + size_t __last = _M_assign_in_block(__block, __it, __end); + if (__it == __end) + return __erase_from(__block, __last); + } + + // Insert remaining elements + insert_range(ranges::subrange(std::move(__it), __end)); + } + } + + iterator + begin() + { return iterator(_M_blocks._M_first); } + + iterator + end() + { 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); } + + 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; } + + constexpr hive_limits + block_capacity_limits() const noexcept + { return _M_blocks._M_limits; } + + void + reserve(size_type __n) + { + if (__n <= capacity()) + return; + + const hive_limits __limits = _M_blocks._M_limits; + 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_capacity = __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 / 2); + _M_blocks._M_reserve_block(__n - __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); + } + + template<typename... _Args> + iterator + emplace(_Args&&... __args) + { + _BlockT* __block; + if (_M_size == capacity()) + __block = _M_blocks._M_reserve_block(); + else + __block = _M_blocks._M_free_head(); + + _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); + } + + template<__detail::__container_compatible_range<_Tp> _Rg> + void + insert_range(_Rg&& __rg) + { + auto __it = std::ranges::begin(__rg); + auto __end = std::ranges::end(__rg); + if (__it == __end) [[unlikely]] + return; + + if constexpr (ranges::sized_range<_Rg>) + { + const auto __new_size = _M_size + size_t(ranges::size(__rg)); + reserve(__new_size); + + _BlockT* __block = _M_blocks._M_free_head(); + // Fillout initial blocks, we do not need to check against end + while (_M_size + __block->_M_capacity <= __new_size) + { + _M_insert_in_block(__block, __it, unreachable_sentinel); + __block = _M_blocks._M_free_head(); + if (!__block) + return; + } + + // Handle block that is partially filled + while (__it != __end) + _M_insert_in_slot(__block, __it, __end); + } + else + { + // Fill out empty spaces in existing blocks. + while (_BlockT* __block = _M_blocks._M_free_head()) + if (_M_insert_in_block(__block, __it, __end)) + return; + + // Allocate new blocks for remaining elements + while (true) + { + _BlockT* __block = _M_blocks._M_reserve_block(); + if (_M_insert_in_block(__block, __it, __end)) + return; + } + } + } + + 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_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 a 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 nodes 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 fully cleared, remove elements, and move to next block + 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); + } + + private: + 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(_Allocator& __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 + _M_commit() + { + if (_M_block->_M_commit_slots(_M_res, _M_count)) + _M_self._M_blocks._M_pop_free(); + // Expose block that was previously reserved + if (_M_res._M_capacity == _M_block->_M_capacity) + _M_self._M_blocks._M_expose(_M_block); + + _M_self._M_size += _M_count; + _M_count = 0; + } + + ~_InsertGuard() + { + if (_M_count) + _M_commit(); + } + }; + + // Returns position of element after last inserted element, or _M_capacity otherwise. + template<typename _Iterator, typename _Sentinel> + size_t + _M_insert_in_slot(_BlockT* __block, _Iterator& __first, _Sentinel __last) + { + _InsertGuard __guard(*this, __block); + while ((__first != __last) && !__guard._M_filled()) + { + __guard.construct(_M_blocks._M_alloc, *__first); + ++__first; + } + return __guard._M_res._M_pos + __guard._M_res._M_capacity; + } + + template<typename _Iterator, typename _Sentinel> + bool + _M_insert_in_block(_BlockT* __block, _Iterator& __first, _Sentinel __last) + { + while (!__block->_M_full()) + { + _M_insert_in_slot(__block, __first, __last); + if (__first == __last) + return true; + } + return false; + } + + // Returns position of element after last assigned/inserted element, or _M_capacity otherwise. + template<typename _Iterator, typename _Sentinel> + size_t + _M_assign_in_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 + __pos = _M_insert_in_slot(__block, __first, __last); + } + return __pos; + } + + void + _M_erase_range(_BlockT* __block, size_t __first, size_t __to) + { + if (__block->_M_full()) + _M_blocks._M_append_free(__block); + + auto __release = [&] (size_t __count) { + __block->_M_release_slots(__first, __count); + _M_size -= __count; + return __first; + }; + + size_t __pos = __first; + _AllocT::destroy(_M_blocks._M_alloc, __block->_M_elem(__pos++)); + + while (__pos != __to) + if (__block->_M_occupied(__pos)) + _AllocT::destroy(_M_blocks._M_alloc, __block->_M_elem(__pos++)); + else + __pos = __release(__pos - __first); + + if (size_t __count = __pos - __first) + __release(__count); + } + + void + _M_clear(_BlockT* __block) + { + size_t __pos = 0, __first = 0; + while (__pos != __block->_M_capacity) + if (__block->_M_occupied(__pos)) + _AllocT::destroy(_M_blocks._M_alloc, __block->_M_elem(__pos++)); + else + { + _M_size -= __pos - __first; + __first = __pos + _CounterT::_S_load_fwd(__block->_M_skipfield(__pos)); + __pos = __first; + } + + _M_size -= __pos - __first; + } + + void + _M_clear(_BlockT* __from, _BlockT* __to) + { + while (__from != __to) + { + if (__from->_M_full()) + _M_blocks._M_append_free(__from); + + _M_clear(__from); + __from->_M_clear_slots(); + __from = __from->_M_next; + } + } + + _BlockListT _M_blocks; + size_type _M_size = 0; + }; + +#if __cplusplus >= 201703L +// namespace __detail::__variant +// { +// template<typename> struct _Never_valueless_alt; // see <variant> + + // Provide the strong exception-safety guarantee when emplacing a + // vector into a variant, but only if move assignment cannot throw. +// template<typename _Tp, typename _Alloc> +// struct _Never_valueless_alt<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> +// : std::is_nothrow_move_assignable<_GLIBCXX_STD_C::vector<_Tp, _Alloc>> +// { }; +// } // namespace __detail::__variant +#endif // C++17 + +_GLIBCXX_END_NAMESPACE_CONTAINER +_GLIBCXX_END_NAMESPACE_VERSION +} // namespace std + +#endif /* _BITS_HIVE_H */ -- 2.54.0
