Author: Christopher Di Bella Date: 2025-09-12T06:33:10-07:00 New Revision: e8f61801c6237e56b3d69190af7a7acfdcede1e8
URL: https://github.com/llvm/llvm-project/commit/e8f61801c6237e56b3d69190af7a7acfdcede1e8 DIFF: https://github.com/llvm/llvm-project/commit/e8f61801c6237e56b3d69190af7a7acfdcede1e8.diff LOG: [libcxx] adds size-based `__split_buffer` representation to unstable ABI (#139632) **tl;dr** We can significantly improve the runtime performance of `std::vector` by changing its representation from three pointers to one pointer and two integers. This document explains the details of this change, along with the justifications for making it. See the [RFC] for more information. `vector` depends on `__split_buffer` for inserting elements. Changing `__split_buffer` to match `vector`'s representation simplifies the model, as it eliminates the need to convert between two different representations of a contiguous buffer in the same configuration of libc++. [RFC]: https://discourse.llvm.org/t/adding-a-size-based-vector-to-libc-s-unstable-abi/86306 --------- Co-authored-by: Jorge Gorbe Moya <jgo...@google.com> Added: Modified: libcxx/include/__split_buffer libcxx/include/__vector/vector.h libcxx/include/deque libcxx/test/libcxx/type_traits/is_replaceable.compile.pass.cpp libcxx/test/libcxx/type_traits/is_trivially_relocatable.compile.pass.cpp lldb/examples/synthetic/libcxx.py Removed: ################################################################################ diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer index 21e58f4abc6b3..15368a3bc8955 100644 --- a/libcxx/include/__split_buffer +++ b/libcxx/include/__split_buffer @@ -13,10 +13,12 @@ #include <__algorithm/max.h> #include <__algorithm/move.h> #include <__algorithm/move_backward.h> +#include <__assert> #include <__config> #include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/move_iterator.h> +#include <__memory/addressof.h> #include <__memory/allocate_at_least.h> #include <__memory/allocator.h> #include <__memory/allocator_traits.h> @@ -45,25 +47,434 @@ _LIBCPP_PUSH_MACROS _LIBCPP_BEGIN_NAMESPACE_STD -// __split_buffer allocates a contiguous chunk of memory and stores objects in the range [__begin_, __end_). -// It has uninitialized memory in the ranges [__first_, __begin_) and [__end_, __cap_). That allows -// it to grow both in the front and back without having to move the data. +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +class __split_buffer; + +template <class _SplitBuffer, class _Tp, class _Allocator> +class __split_buffer_pointer_layout { +protected: + using value_type = _Tp; + using allocator_type = _Allocator; + using __alloc_rr _LIBCPP_NODEBUG = __libcpp_remove_reference_t<allocator_type>; + using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<__alloc_rr>; + using reference = value_type&; + using const_reference = const value_type&; + using size_type = typename __alloc_traits::size_type; + using diff erence_type = typename __alloc_traits:: diff erence_type; + using pointer = typename __alloc_traits::pointer; + using const_pointer = typename __alloc_traits::const_pointer; + using iterator = pointer; + using const_iterator = const_pointer; + using __sentinel_type _LIBCPP_NODEBUG = pointer; -template <class _Tp, class _Allocator = allocator<_Tp> > -struct __split_buffer { public: - using value_type = _Tp; - using allocator_type = _Allocator; - using __alloc_rr _LIBCPP_NODEBUG = __libcpp_remove_reference_t<allocator_type>; - using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<__alloc_rr>; - using reference = value_type&; - using const_reference = const value_type&; - using size_type = typename __alloc_traits::size_type; - using diff erence_type = typename __alloc_traits:: diff erence_type; - using pointer = typename __alloc_traits::pointer; - using const_pointer = typename __alloc_traits::const_pointer; - using iterator = pointer; - using const_iterator = const_pointer; + // Can't be defaulted due to _LIBCPP_COMPRESSED_PAIR not being an aggregate in C++03 and C++11. + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_pointer_layout() : __back_cap_(nullptr) {} + + _LIBCPP_CONSTEXPR_SINCE_CXX20 + _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_pointer_layout(const allocator_type& __alloc) + : __back_cap_(nullptr), __alloc_(__alloc) {} + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT { + return __front_cap_; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __end_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __end_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { + return static_cast<size_type>(__end_ - __begin_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __begin_ == __end_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { + return static_cast<size_type>(__back_cap_ - __front_cap_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT { + return __alloc_; + } + + // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction, + // not explicit types. + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT { + return __end_; + } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT { + return __back_cap_; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT { + __front_cap_ = __new_first; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT { + __begin_ = __new_begin; + __end_ = __new_end; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT { + __begin_ = __new_begin; + __end_ = __begin_ + __new_size; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT { + _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_"); + __end_ = __new_end; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT { + __end_ = __begin_ + __new_size; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT { + __back_cap_ = __front_cap_ + __new_capacity; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT { + __back_cap_ = __new_capacity; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT { + return static_cast<size_type>(__begin_ - __front_cap_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT { + return static_cast<size_type>(__back_cap_ - __end_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return *(__end_ - 1); } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT { return *(__end_ - 1); } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator( + __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>, + value_type, + __alloc_rr&>& __other) _NOEXCEPT { + std::swap(__front_cap_, __other.__front_cap_); + std::swap(__begin_, __other.__begin_); + std::swap(__back_cap_, __other.__back_cap_); + std::swap(__end_, __other.__end_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_pointer_layout& __other) _NOEXCEPT { + std::swap(__front_cap_, __other.__front_cap_); + std::swap(__begin_, __other.__begin_); + std::swap(__back_cap_, __other.__back_cap_); + std::swap(__end_, __other.__end_); + std::__swap_allocator(__alloc_, __other.__alloc_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT { + __front_cap_ = nullptr; + __begin_ = nullptr; + __end_ = nullptr; + __back_cap_ = nullptr; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __copy_without_alloc(__split_buffer_pointer_layout const& __other) + _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) { + __front_cap_ = __other.__front_cap_; + __begin_ = __other.__begin_; + __end_ = __other.__end_; + __back_cap_ = __other.__back_cap_; + } + +private: + pointer __front_cap_ = nullptr; + pointer __begin_ = nullptr; + pointer __end_ = nullptr; + _LIBCPP_COMPRESSED_PAIR(pointer, __back_cap_, allocator_type, __alloc_); + + template <class, class, class> + friend class __split_buffer_pointer_layout; +}; + +template <class _SplitBuffer, class _Tp, class _Allocator> +class __split_buffer_size_layout { +protected: + using value_type = _Tp; + using allocator_type = _Allocator; + using __alloc_rr _LIBCPP_NODEBUG = __libcpp_remove_reference_t<allocator_type>; + using __alloc_traits _LIBCPP_NODEBUG = allocator_traits<__alloc_rr>; + using reference = value_type&; + using const_reference = const value_type&; + using size_type = typename __alloc_traits::size_type; + using diff erence_type = typename __alloc_traits:: diff erence_type; + using pointer = typename __alloc_traits::pointer; + using const_pointer = typename __alloc_traits::const_pointer; + using iterator = pointer; + using const_iterator = const_pointer; + using __sentinel_type _LIBCPP_NODEBUG = size_type; + +public: + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer_size_layout() = default; + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer_size_layout(const allocator_type& __alloc) + : __alloc_(__alloc) {} + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer __front_cap() _NOEXCEPT { return __front_cap_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer __front_cap() const _NOEXCEPT { + return __front_cap_; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer begin() _NOEXCEPT { return __begin_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_pointer begin() const _NOEXCEPT { return __begin_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() _NOEXCEPT { return __begin_ + __size_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI pointer end() const _NOEXCEPT { return __begin_ + __size_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const _NOEXCEPT { return __size_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const _NOEXCEPT { return __size_ == 0; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const _NOEXCEPT { return __cap_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type& __get_allocator() _NOEXCEPT { return __alloc_; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI allocator_type const& __get_allocator() const _NOEXCEPT { + return __alloc_; + } + + // Returns the sentinel object directly. Should be used in conjunction with automatic type deduction, + // not explicit types. + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_sentinel() const _NOEXCEPT { + return __size_; + } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __sentinel_type __raw_capacity() const _NOEXCEPT { + return __cap_; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_data(pointer __new_first) _NOEXCEPT { + __front_cap_ = __new_first; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __set_valid_range(pointer __new_begin, pointer __new_end) _NOEXCEPT { + // Size-based __split_buffers track their size directly: we need to explicitly update the size + // when the front is adjusted. + __size_ -= __new_begin - __begin_; + __begin_ = __new_begin; + __set_sentinel(__new_end); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __set_valid_range(pointer __new_begin, size_type __new_size) _NOEXCEPT { + // Size-based __split_buffers track their size directly: we need to explicitly update the size + // when the front is adjusted. + __size_ -= __new_begin - __begin_; + __begin_ = __new_begin; + __set_sentinel(__new_size); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(pointer __new_end) _NOEXCEPT { + _LIBCPP_ASSERT_INTERNAL(__front_cap_ <= __new_end, "__new_end cannot precede __front_cap_"); + __size_ += __new_end - end(); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_sentinel(size_type __new_size) _NOEXCEPT { + __size_ = __new_size; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(size_type __new_capacity) _NOEXCEPT { + __cap_ = __new_capacity; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __set_capacity(pointer __new_capacity) _NOEXCEPT { + __cap_ = __new_capacity - __begin_; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const _NOEXCEPT { + return static_cast<size_type>(__begin_ - __front_cap_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const _NOEXCEPT { + // `__cap_ - __end_` tells us the total number of spares when in size-mode. We need to remove + // the __front_spare from the count. + return __cap_ - __size_ - __front_spare(); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() _NOEXCEPT { return __begin_[__size_ - 1]; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const _NOEXCEPT { + return __begin_[__size_ - 1]; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_without_allocator( + __split_buffer_pointer_layout<__split_buffer<value_type, __alloc_rr&, __split_buffer_pointer_layout>, + value_type, + __alloc_rr&>& __other) _NOEXCEPT { + std::swap(__front_cap_, __other.__front_cap_); + std::swap(__begin_, __other.__begin_); + std::swap(__cap_, __other.__cap_); + std::swap(__size_, __other.__size_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer_size_layout& __other) _NOEXCEPT { + std::swap(__front_cap_, __other.__front_cap_); + std::swap(__begin_, __other.__begin_); + std::swap(__cap_, __other.__cap_); + std::swap(__size_, __other.__size_); + std::__swap_allocator(__alloc_, __other.__alloc_); + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __reset() _NOEXCEPT { + __front_cap_ = nullptr; + __begin_ = nullptr; + __size_ = 0; + __cap_ = 0; + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __copy_without_alloc(__split_buffer_size_layout const& __other) + _NOEXCEPT_(is_nothrow_copy_assignable<pointer>::value) { + __front_cap_ = __other.__front_cap_; + __begin_ = __other.__begin_; + __cap_ = __other.__cap_; + __size_ = __other.__size_; + } + +private: + pointer __front_cap_ = nullptr; + pointer __begin_ = nullptr; + size_type __size_ = 0; + size_type __cap_ = 0; + _LIBCPP_NO_UNIQUE_ADDRESS allocator_type __alloc_; + + template <class, class, class> + friend class __split_buffer_size_layout; +}; + +// `__split_buffer` is a contiguous array data structure. It may hold spare capacity at both ends of +// the sequence. This allows for a `__split_buffer` to grow from both the front and the back without +// relocating its contents until it runs out of room. This characteristic sets it apart from +// `std::vector`, which only holds spare capacity at its end. As such, `__split_buffer` is useful +// for implementing both `std::vector` and `std::deque`. +// +// The sequence is stored as a contiguous chunk of memory delimited by the following "pointers" (`o` denotes +// uninitialized memory and `x` denotes a valid object): +// +// |oooooooooooooooooooxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxoooooooooooooooooooooooo| +// ^ ^ ^ ^ +// __front_cap_ __begin_ __end_ __back_cap_ +// +// The range [__front_cap_, __begin_) contains uninitialized memory. It is referred to as the "front spare capacity". +// The range [__begin_, __end_) contains valid objects. It is referred to as the "valid range". +// The range [__end_, __back_cap_) contains uninitialized memory. It is referred to as the "back spare capacity". +// +// The layout of `__split_buffer` is determined by the `_Layout` template template parameter. This +// `_Layout` allows the above pointers to be stored as diff erent representations, such as integer +// offsets. A layout class template must provide the following interface: +// +// template<class _Tp, class _Allocator, class _Layout> +// class __layout { +// protected: +// using value_type = _Tp; +// using allocator_type = _Allocator; +// using __alloc_rr = __libcpp_remove_reference_t<allocator_type>; +// using __alloc_traits = allocator_traits<__alloc_rr>; +// using reference = value_type&; +// using const_reference = const value_type&; +// using size_type = typename __alloc_traits::size_type; +// using diff erence_type = typename __alloc_traits:: diff erence_type; +// using pointer = typename __alloc_traits::pointer; +// using const_pointer = typename __alloc_traits::const_pointer; +// using iterator = pointer; +// using const_iterator = const_pointer; +// using __sentinel_type = /* type that represents the layout's sentinel */; +// +// public: +// __layout() = default; +// explicit __layout(const allocator_type&); +// +// pointer __front_cap(); +// const_pointer __front_cap() const; +// +// pointer begin(); +// const_pointer begin() const; +// +// pointer end(); +// pointer end() const; +// +// size_type size() const; +// bool empty() const; +// size_type capacity() const; +// +// allocator_type& __get_allocator(); +// allocator_type const& __get_allocator() const; +// +// __sentinel_type __raw_sentinel() const; +// __sentinel_type __raw_capacity() const; +// +// void __set_data(pointer); +// void __set_valid_range(pointer __begin, pointer __end); +// void __set_valid_range(pointer __begin, size_type __size); +// void __set_sentinel(pointer __end); +// void __set_sentinel(size_type __size); +// +// void __set_capacity(size_type __capacity); +// void __set_capacity(pointer __capacity); +// +// size_type __front_spare() const; +// size_type __back_spare() const; +// +// reference back(); +// const_reference back() const; +// +// template<class _OtherLayout> +// void __swap_without_allocator(_OtherLayout&); +// void swap(__layout&); +// +// void __reset(); +// void __copy_without_alloc(__layout const&); +// }; +// +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +class __split_buffer : _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator> { + using __base_type _LIBCPP_NODEBUG = _Layout<__split_buffer<_Tp, _Allocator, _Layout>, _Tp, _Allocator>; + +public: + using __base_type::__back_spare; + using __base_type::__copy_without_alloc; + using __base_type::__front_cap; + using __base_type::__front_spare; + using __base_type::__get_allocator; + using __base_type::__raw_capacity; + using __base_type::__raw_sentinel; + using __base_type::__reset; + using __base_type::__set_capacity; + using __base_type::__set_data; + using __base_type::__set_sentinel; + using __base_type::__set_valid_range; + + using typename __base_type::__alloc_rr; + using typename __base_type::__alloc_traits; + using typename __base_type::allocator_type; + using typename __base_type::const_iterator; + using typename __base_type::const_pointer; + using typename __base_type::const_reference; + using typename __base_type:: diff erence_type; + using typename __base_type::iterator; + using typename __base_type::pointer; + using typename __base_type::reference; + using typename __base_type::size_type; + using typename __base_type::value_type; // A __split_buffer contains the following members which may be trivially relocatable: // - pointer: may be trivially relocatable, so it's checked @@ -78,23 +489,15 @@ public: __split_buffer, void>; - pointer __first_; - pointer __begin_; - pointer __end_; - _LIBCPP_COMPRESSED_PAIR(pointer, __cap_, allocator_type, __alloc_); - __split_buffer(const __split_buffer&) = delete; __split_buffer& operator=(const __split_buffer&) = delete; - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer() - _NOEXCEPT_(is_nothrow_default_constructible<allocator_type>::value) - : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr) {} + _LIBCPP_HIDE_FROM_ABI __split_buffer() = default; - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a) - : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr), __alloc_(__a) {} + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(__alloc_rr& __a) : __base_type(__a) {} _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI explicit __split_buffer(const __alloc_rr& __a) - : __first_(nullptr), __begin_(nullptr), __end_(nullptr), __cap_(nullptr), __alloc_(__a) {} + : __base_type(__a) {} _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI __split_buffer(size_type __cap, size_type __start, __alloc_rr& __a); @@ -111,36 +514,16 @@ public: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~__split_buffer(); - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator begin() _NOEXCEPT { return __begin_; } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator begin() const _NOEXCEPT { return __begin_; } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator end() _NOEXCEPT { return __end_; } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_iterator end() const _NOEXCEPT { return __end_; } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(__begin_); } + using __base_type::back; + using __base_type::begin; + using __base_type::capacity; + using __base_type::empty; + using __base_type::end; + using __base_type::size; - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type size() const { - return static_cast<size_type>(__end_ - __begin_); - } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool empty() const { return __end_ == __begin_; } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type capacity() const { - return static_cast<size_type>(__cap_ - __first_); - } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __front_spare() const { - return static_cast<size_type>(__begin_ - __first_); - } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI size_type __back_spare() const { - return static_cast<size_type>(__cap_ - __end_); - } - - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *__begin_; } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *__begin_; } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference back() { return *(__end_ - 1); } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference back() const { return *(__end_ - 1); } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void clear() _NOEXCEPT { __destruct_at_end(begin()); } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI reference front() { return *begin(); } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI const_reference front() const { return *begin(); } _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void shrink_to_fit() _NOEXCEPT; @@ -149,8 +532,8 @@ public: template <class... _Args> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void emplace_back(_Args&&... __args); - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(__begin_ + 1); } - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(__end_ - 1); } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_front() { __destruct_at_begin(begin() + 1); } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back() { __destruct_at_end(end() - 1); } _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n); _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x); @@ -184,242 +567,240 @@ public: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void swap(__split_buffer& __x) _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>); - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const; + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI bool __invariants() const { + if (__front_cap() == nullptr) { + if (begin() != nullptr) + return false; + + if (!empty()) + return false; + + if (capacity() != 0) + return false; + + return true; + } else { + if (begin() < __front_cap()) + return false; + + if (capacity() < size()) + return false; + + if (end() < begin()) + return false; + + return true; + } + } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void + __swap_without_allocator(__split_buffer<value_type, __alloc_rr&, _Layout>& __other) _NOEXCEPT { + __base_type::__swap_without_allocator(__other); + } private: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer& __c, true_type) _NOEXCEPT_(is_nothrow_move_assignable<allocator_type>::value) { - __alloc_ = std::move(__c.__alloc_); + __get_allocator() = std::move(__c.__get_allocator()); } _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __move_assign_alloc(__split_buffer&, false_type) _NOEXCEPT {} struct _ConstructTransaction { _LIBCPP_CONSTEXPR_SINCE_CXX20 - _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(pointer* __p, size_type __n) _NOEXCEPT - : __pos_(*__p), - __end_(*__p + __n), - __dest_(__p) {} + _LIBCPP_HIDE_FROM_ABI explicit _ConstructTransaction(__split_buffer* __parent, pointer __p, size_type __n) _NOEXCEPT + : __pos_(__p), + __end_(__p + __n), + __parent_(__parent) {} - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { *__dest_ = __pos_; } + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI ~_ConstructTransaction() { __parent_->__set_sentinel(__pos_); } pointer __pos_; const pointer __end_; private: - pointer* __dest_; + __split_buffer* __parent_; }; -}; -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 bool __split_buffer<_Tp, _Allocator>::__invariants() const { - if (__first_ == nullptr) { - if (__begin_ != nullptr) - return false; - if (__end_ != nullptr) - return false; - if (__cap_ != nullptr) - return false; - } else { - if (__begin_ < __first_) - return false; - if (__end_ < __begin_) - return false; - if (__cap_ < __end_) - return false; - } - return true; -} + template <class _T2, class _A2, template <class, class, class> class _L2> + friend class __split_buffer; +}; -// Default constructs __n objects starting at __end_ +// Default constructs __n objects starting at `end()` // throws if construction throws // Precondition: __n > 0 // Precondition: size() + __n <= capacity() // Postcondition: size() == size() + __n -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n) { - _ConstructTransaction __tx(std::addressof(this->__end_), __n); +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n) { + _ConstructTransaction __tx(this, end(), __n); for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { - __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_)); + __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_)); } } -// Copy constructs __n objects starting at __end_ from __x +// Copy constructs __n objects starting at `end()` from __x // throws if construction throws // Precondition: __n > 0 // Precondition: size() + __n <= capacity() // Postcondition: size() == old size() + __n // Postcondition: [i] == __x for all i in [size() - __n, __n) -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__split_buffer<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) { - _ConstructTransaction __tx(std::addressof(this->__end_), __n); +__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(size_type __n, const_reference __x) { + _ConstructTransaction __tx(this, end(), __n); for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_) { - __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_), __x); + __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), __x); } } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> template <class _Iterator, class _Sentinel> _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) { - __alloc_rr& __a = __alloc_; +__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) { + __alloc_rr& __a = __get_allocator(); for (; __first != __last; ++__first) { - if (__end_ == __cap_) { - size_type __old_cap = __cap_ - __first_; + if (__back_spare() == 0) { + size_type __old_cap = capacity(); size_type __new_cap = std::max<size_type>(2 * __old_cap, 8); __split_buffer __buf(__new_cap, 0, __a); - for (pointer __p = __begin_; __p != __end_; ++__p, (void)++__buf.__end_) - __alloc_traits::construct(__buf.__alloc_, std::__to_address(__buf.__end_), std::move(*__p)); + pointer __buf_end = __buf.end(); + pointer __end = end(); + for (pointer __p = begin(); __p != __end; ++__p) { + __alloc_traits::construct(__buf.__get_allocator(), std::__to_address(__buf_end), std::move(*__p)); + __buf.__set_sentinel(++__buf_end); + } swap(__buf); } - __alloc_traits::construct(__a, std::__to_address(this->__end_), *__first); - ++this->__end_; + + __alloc_traits::construct(__a, std::__to_address(end()), *__first); + __set_sentinel(size() + 1); } } -template <class _Tp, class _Allocator> + +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> template <class _ForwardIterator, __enable_if_t<__has_forward_iterator_category<_ForwardIterator>::value, int> > _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) { +__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) { __construct_at_end_with_size(__first, std::distance(__first, __last)); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> template <class _ForwardIterator> _LIBCPP_CONSTEXPR_SINCE_CXX20 void -__split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) { - _ConstructTransaction __tx(std::addressof(this->__end_), __n); +__split_buffer<_Tp, _Allocator, _Layout>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) { + _ConstructTransaction __tx(this, end(), __n); for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void)++__first) { - __alloc_traits::construct(__alloc_, std::__to_address(__tx.__pos_), *__first); + __alloc_traits::construct(__get_allocator(), std::__to_address(__tx.__pos_), *__first); } } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void -__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, false_type) { - while (__begin_ != __new_begin) - __alloc_traits::destroy(__alloc_, std::__to_address(__begin_++)); +__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, false_type) { + pointer __begin = begin(); + // Updating begin at every iteration is unnecessary because destruction can't throw. + while (__begin != __new_begin) + __alloc_traits::destroy(__get_allocator(), std::__to_address(__begin++)); + __set_valid_range(__begin, end()); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 inline void -__split_buffer<_Tp, _Allocator>::__destruct_at_begin(pointer __new_begin, true_type) { - __begin_ = __new_begin; -} - -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void -__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT { - while (__new_last != __end_) - __alloc_traits::destroy(__alloc_, std::__to_address(--__end_)); +__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_begin(pointer __new_begin, true_type) { + __set_valid_range(__new_begin, end()); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void -__split_buffer<_Tp, _Allocator>::__destruct_at_end(pointer __new_last, true_type) _NOEXCEPT { - __end_ = __new_last; +__split_buffer<_Tp, _Allocator, _Layout>::__destruct_at_end(pointer __new_last, false_type) _NOEXCEPT { + pointer __end = end(); + // Updating begin at every iteration is unnecessary because destruction can't throw. + while (__new_last != __end) + __alloc_traits::destroy(__get_allocator(), std::__to_address(--__end)); + __set_sentinel(__end); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 -__split_buffer<_Tp, _Allocator>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) - : __cap_(nullptr), __alloc_(__a) { - if (__cap == 0) { - __first_ = nullptr; - } else { - auto __allocation = std::__allocate_at_least(__alloc_, __cap); - __first_ = __allocation.ptr; - __cap = __allocation.count; +__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(size_type __cap, size_type __start, __alloc_rr& __a) + : __base_type(__a) { + _LIBCPP_ASSERT_INTERNAL(__cap >= __start, "can't have a start point outside the capacity"); + if (__cap > 0) { + auto __allocation = std::__allocate_at_least(__get_allocator(), __cap); + __set_data(__allocation.ptr); + __cap = __allocation.count; } - __begin_ = __end_ = __first_ + __start; - __cap_ = __first_ + __cap; + + pointer __begin = __front_cap() + __start; + __set_valid_range(__begin, __begin); + __set_capacity(__cap); } -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>::~__split_buffer() { +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::~__split_buffer() { clear(); - if (__first_) - __alloc_traits::deallocate(__alloc_, __first_, capacity()); + if (__front_cap()) + __alloc_traits::deallocate(__get_allocator(), __front_cap(), capacity()); } -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c) +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c) _NOEXCEPT_(is_nothrow_move_constructible<allocator_type>::value) - : __first_(std::move(__c.__first_)), - __begin_(std::move(__c.__begin_)), - __end_(std::move(__c.__end_)), - __cap_(std::move(__c.__cap_)), - __alloc_(std::move(__c.__alloc_)) { - __c.__first_ = nullptr; - __c.__begin_ = nullptr; - __c.__end_ = nullptr; - __c.__cap_ = nullptr; + : __base_type(std::move(__c)) { + __c.__reset(); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 -__split_buffer<_Tp, _Allocator>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) - : __cap_(nullptr), __alloc_(__a) { - if (__a == __c.__alloc_) { - __first_ = __c.__first_; - __begin_ = __c.__begin_; - __end_ = __c.__end_; - __cap_ = __c.__cap_; - __c.__first_ = nullptr; - __c.__begin_ = nullptr; - __c.__end_ = nullptr; - __c.__cap_ = nullptr; +__split_buffer<_Tp, _Allocator, _Layout>::__split_buffer(__split_buffer&& __c, const __alloc_rr& __a) + : __base_type(__a) { + if (__a == __c.__get_allocator()) { + __set_data(__c.__front_cap()); + __set_valid_range(__c.begin(), __c.end()); + __set_capacity(__c.capacity()); + __c.__reset(); } else { - auto __allocation = std::__allocate_at_least(__alloc_, __c.size()); - __first_ = __allocation.ptr; - __begin_ = __end_ = __first_; - __cap_ = __first_ + __allocation.count; + auto __allocation = std::__allocate_at_least(__get_allocator(), __c.size()); + __set_data(__allocation.ptr); + __set_valid_range(__front_cap(), __front_cap()); + __set_capacity(__allocation.count); typedef move_iterator<iterator> _Ip; __construct_at_end(_Ip(__c.begin()), _Ip(__c.end())); } } -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator>& -__split_buffer<_Tp, _Allocator>::operator=(__split_buffer&& __c) +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 __split_buffer<_Tp, _Allocator, _Layout>& +__split_buffer<_Tp, _Allocator, _Layout>::operator=(__split_buffer&& __c) _NOEXCEPT_((__alloc_traits::propagate_on_container_move_assignment::value && is_nothrow_move_assignable<allocator_type>::value) || !__alloc_traits::propagate_on_container_move_assignment::value) { clear(); shrink_to_fit(); - __first_ = __c.__first_; - __begin_ = __c.__begin_; - __end_ = __c.__end_; - __cap_ = __c.__cap_; + __copy_without_alloc(__c); __move_assign_alloc(__c, integral_constant<bool, __alloc_traits::propagate_on_container_move_assignment::value>()); - __c.__first_ = __c.__begin_ = __c.__end_ = __c.__cap_ = nullptr; + __c.__reset(); return *this; } -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::swap(__split_buffer& __x) +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::swap(__split_buffer& __x) _NOEXCEPT_(!__alloc_traits::propagate_on_container_swap::value || __is_nothrow_swappable_v<__alloc_rr>) { - std::swap(__first_, __x.__first_); - std::swap(__begin_, __x.__begin_); - std::swap(__end_, __x.__end_); - std::swap(__cap_, __x.__cap_); - std::__swap_allocator(__alloc_, __x.__alloc_); + __base_type::swap(__x); } -template <class _Tp, class _Allocator> -_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::shrink_to_fit() _NOEXCEPT { +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> +_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::shrink_to_fit() _NOEXCEPT { if (capacity() > size()) { #if _LIBCPP_HAS_EXCEPTIONS try { #endif // _LIBCPP_HAS_EXCEPTIONS - __split_buffer<value_type, __alloc_rr&> __t(size(), 0, __alloc_); + __split_buffer<value_type, __alloc_rr&, _Layout> __t(size(), 0, __get_allocator()); if (__t.capacity() < capacity()) { - __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_)); - __t.__end_ = __t.__begin_ + (__end_ - __begin_); - std::swap(__first_, __t.__first_); - std::swap(__begin_, __t.__begin_); - std::swap(__end_, __t.__end_); - std::swap(__cap_, __t.__cap_); + __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(end())); + __t.__set_sentinel(size()); + __swap_without_allocator(__t); } #if _LIBCPP_HAS_EXCEPTIONS } catch (...) { @@ -428,55 +809,56 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::shrink_to_fi } } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> template <class... _Args> -_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::emplace_front(_Args&&... __args) { - if (__begin_ == __first_) { - if (__end_ < __cap_) { - diff erence_type __d = __cap_ - __end_; +_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_front(_Args&&... __args) { + if (__front_spare() == 0) { + pointer __end = end(); + if (__back_spare() > 0) { + // The elements are pressed up against the front of the buffer: we need to move them back a + // little bit to make `emplace_front` have amortised O(1) complexity. + diff erence_type __d = __back_spare(); __d = (__d + 1) / 2; - __begin_ = std::move_backward(__begin_, __end_, __end_ + __d); - __end_ += __d; + auto __new_end = __end + __d; + __set_valid_range(std::move_backward(begin(), __end, __new_end), __new_end); } else { - size_type __c = std::max<size_type>(2 * static_cast<size_type>(__cap_ - __first_), 1); - __split_buffer<value_type, __alloc_rr&> __t(__c, (__c + 3) / 4, __alloc_); - __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_)); - std::swap(__first_, __t.__first_); - std::swap(__begin_, __t.__begin_); - std::swap(__end_, __t.__end_); - std::swap(__cap_, __t.__cap_); + size_type __c = std::max<size_type>(2 * capacity(), 1); + __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, (__c + 3) / 4, __get_allocator()); + __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end)); + __base_type::__swap_without_allocator(__t); } } - __alloc_traits::construct(__alloc_, std::__to_address(__begin_ - 1), std::forward<_Args>(__args)...); - --__begin_; + + __alloc_traits::construct(__get_allocator(), std::__to_address(begin() - 1), std::forward<_Args>(__args)...); + __set_valid_range(begin() - 1, size() + 1); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> template <class... _Args> -_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator>::emplace_back(_Args&&... __args) { - if (__end_ == __cap_) { - if (__begin_ > __first_) { - diff erence_type __d = __begin_ - __first_; +_LIBCPP_CONSTEXPR_SINCE_CXX20 void __split_buffer<_Tp, _Allocator, _Layout>::emplace_back(_Args&&... __args) { + pointer __end = end(); + if (__back_spare() == 0) { + if (__front_spare() > 0) { + diff erence_type __d = __front_spare(); __d = (__d + 1) / 2; - __end_ = std::move(__begin_, __end_, __begin_ - __d); - __begin_ -= __d; + __end = std::move(begin(), __end, begin() - __d); + __set_valid_range(begin() - __d, __end); } else { - size_type __c = std::max<size_type>(2 * static_cast<size_type>(__cap_ - __first_), 1); - __split_buffer<value_type, __alloc_rr&> __t(__c, __c / 4, __alloc_); - __t.__construct_at_end(move_iterator<pointer>(__begin_), move_iterator<pointer>(__end_)); - std::swap(__first_, __t.__first_); - std::swap(__begin_, __t.__begin_); - std::swap(__end_, __t.__end_); - std::swap(__cap_, __t.__cap_); + size_type __c = std::max<size_type>(2 * capacity(), 1); + __split_buffer<value_type, __alloc_rr&, _Layout> __t(__c, __c / 4, __get_allocator()); + __t.__construct_at_end(move_iterator<pointer>(begin()), move_iterator<pointer>(__end)); + __base_type::__swap_without_allocator(__t); } } - __alloc_traits::construct(__alloc_, std::__to_address(__end_), std::forward<_Args>(__args)...); - ++__end_; + + __alloc_traits::construct(__get_allocator(), std::__to_address(__end), std::forward<_Args>(__args)...); + __set_sentinel(++__end); } -template <class _Tp, class _Allocator> +template <class _Tp, class _Allocator, template <class, class, class> class _Layout> _LIBCPP_CONSTEXPR_SINCE_CXX20 inline _LIBCPP_HIDE_FROM_ABI void -swap(__split_buffer<_Tp, _Allocator>& __x, __split_buffer<_Tp, _Allocator>& __y) _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { +swap(__split_buffer<_Tp, _Allocator, _Layout>& __x, __split_buffer<_Tp, _Allocator, _Layout>& __y) + _NOEXCEPT_(_NOEXCEPT_(__x.swap(__y))) { __x.swap(__y); } diff --git a/libcxx/include/__vector/vector.h b/libcxx/include/__vector/vector.h index 5a3c13189d52f..27e681aeef22a 100644 --- a/libcxx/include/__vector/vector.h +++ b/libcxx/include/__vector/vector.h @@ -86,6 +86,9 @@ _LIBCPP_BEGIN_NAMESPACE_STD template <class _Tp, class _Allocator /* = allocator<_Tp> */> class vector { + template <class _Up, class _Alloc> + using __split_buffer _LIBCPP_NODEBUG = std::__split_buffer<_Up, _Alloc, __split_buffer_pointer_layout>; + public: // // Types @@ -820,6 +823,24 @@ class vector { __add_alignment_assumption(_Ptr __p) _NOEXCEPT { return __p; } + + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __swap_layouts(__split_buffer<_Tp, allocator_type&>& __sb) { + auto __vector_begin = __begin_; + auto __vector_sentinel = __end_; + auto __vector_cap = __cap_; + + auto __sb_begin = __sb.begin(); + auto __sb_sentinel = __sb.__raw_sentinel(); + auto __sb_cap = __sb.__raw_capacity(); + + // TODO: replace with __set_valid_range and __set_capacity when vector supports it. + __begin_ = __sb_begin; + __end_ = __sb_sentinel; + __cap_ = __sb_cap; + + __sb.__set_valid_range(__vector_begin, __vector_sentinel); + __sb.__set_capacity(__vector_cap); + } }; #if _LIBCPP_STD_VER >= 17 @@ -850,15 +871,14 @@ template <class _Tp, class _Allocator> _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v) { __annotate_delete(); - auto __new_begin = __v.__begin_ - (__end_ - __begin_); + auto __new_begin = __v.begin() - size(); std::__uninitialized_allocator_relocate( this->__alloc_, std::__to_address(__begin_), std::__to_address(__end_), std::__to_address(__new_begin)); - __v.__begin_ = __new_begin; + __v.__set_valid_range(__new_begin, __v.end()); __end_ = __begin_; // All the objects have been destroyed by relocating them. - std::swap(this->__begin_, __v.__begin_); - std::swap(this->__end_, __v.__end_); - std::swap(this->__cap_, __v.__cap_); - __v.__first_ = __v.__begin_; + + __swap_layouts(__v); + __v.__set_data(__v.begin()); __annotate_new(size()); } @@ -870,25 +890,23 @@ template <class _Tp, class _Allocator> _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer vector<_Tp, _Allocator>::__swap_out_circular_buffer(__split_buffer<value_type, allocator_type&>& __v, pointer __p) { __annotate_delete(); - pointer __ret = __v.__begin_; + pointer __ret = __v.begin(); // Relocate [__p, __end_) first to avoid having a hole in [__begin_, __end_) // in case something in [__begin_, __p) throws. std::__uninitialized_allocator_relocate( - this->__alloc_, std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.__end_)); - __v.__end_ += (__end_ - __p); + this->__alloc_, std::__to_address(__p), std::__to_address(__end_), std::__to_address(__v.end())); + auto __relocated_so_far = __end_ - __p; + __v.__set_sentinel(__v.end() + __relocated_so_far); __end_ = __p; // The objects in [__p, __end_) have been destroyed by relocating them. - auto __new_begin = __v.__begin_ - (__p - __begin_); + auto __new_begin = __v.begin() - (__p - __begin_); std::__uninitialized_allocator_relocate( this->__alloc_, std::__to_address(__begin_), std::__to_address(__p), std::__to_address(__new_begin)); - __v.__begin_ = __new_begin; - __end_ = __begin_; // All the objects have been destroyed by relocating them. - - std::swap(this->__begin_, __v.__begin_); - std::swap(this->__end_, __v.__end_); - std::swap(this->__cap_, __v.__cap_); - __v.__first_ = __v.__begin_; + __v.__set_valid_range(__new_begin, __v.end()); + __end_ = __begin_; // All the objects have been destroyed by relocating them. + __swap_layouts(__v); + __v.__set_data(__v.begin()); __annotate_new(size()); return __ret; } @@ -1136,8 +1154,9 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::pointer vector<_Tp, _Allocator>::__emplace_back_slow_path(_Args&&... __args) { __split_buffer<value_type, allocator_type&> __v(__recommend(size() + 1), size(), this->__alloc_); // __v.emplace_back(std::forward<_Args>(__args)...); - __alloc_traits::construct(this->__alloc_, std::__to_address(__v.__end_), std::forward<_Args>(__args)...); - __v.__end_++; + pointer __end = __v.end(); + __alloc_traits::construct(this->__alloc_, std::__to_address(__end), std::forward<_Args>(__args)...); + __v.__set_sentinel(++__end); __swap_out_circular_buffer(__v); return this->__end_; } @@ -1332,14 +1351,14 @@ vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _Inpu __split_buffer<value_type, allocator_type&> __merged( __recommend(size() + __v.size()), __off, __alloc_); // has `__off` positions available at the front std::__uninitialized_allocator_relocate( - __alloc_, std::__to_address(__old_last), std::__to_address(this->__end_), std::__to_address(__merged.__end_)); + __alloc_, std::__to_address(__old_last), std::__to_address(this->__end_), std::__to_address(__merged.end())); __guard.__complete(); // Release the guard once objects in [__old_last_, __end_) have been successfully relocated. - __merged.__end_ += this->__end_ - __old_last; + __merged.__set_sentinel(__merged.end() + (this->__end_ - __old_last)); this->__end_ = __old_last; std::__uninitialized_allocator_relocate( - __alloc_, std::__to_address(__v.__begin_), std::__to_address(__v.__end_), std::__to_address(__merged.__end_)); - __merged.__end_ += __v.size(); - __v.__end_ = __v.__begin_; + __alloc_, std::__to_address(__v.begin()), std::__to_address(__v.end()), std::__to_address(__merged.end())); + __merged.__set_sentinel(__merged.size() + __v.size()); + __v.__set_sentinel(__v.begin()); __p = __swap_out_circular_buffer(__merged, __p); } return __make_iter(__p); diff --git a/libcxx/include/deque b/libcxx/include/deque index 395a1076fd3c4..98d1dbbddb7e8 100644 --- a/libcxx/include/deque +++ b/libcxx/include/deque @@ -487,6 +487,9 @@ const _DiffType __deque_iterator<_ValueType, _Pointer, _Reference, _MapPointer, template <class _Tp, class _Allocator /*= allocator<_Tp>*/> class deque { + template <class _Up, class _Alloc> + using __split_buffer _LIBCPP_NODEBUG = std::__split_buffer<_Up, _Alloc, __split_buffer_pointer_layout>; + public: // types: @@ -1238,8 +1241,8 @@ private: clear(); shrink_to_fit(); } - __alloc() = __c.__alloc(); - __map_.__alloc_ = __c.__map_.__alloc_; + __alloc() = __c.__alloc(); + __map_.__get_allocator() = __c.__map_.__get_allocator(); } _LIBCPP_HIDE_FROM_ABI void __copy_assign_alloc(const deque&, false_type) {} @@ -1318,7 +1321,7 @@ deque<_Tp, _Allocator>::deque(const deque& __c) : __map_(__pointer_allocator(__alloc_traits::select_on_container_copy_construction(__c.__alloc()))), __start_(0), __size_(0), - __alloc_(__map_.__alloc_) { + __alloc_(__map_.__get_allocator()) { __annotate_new(0); __append(__c.begin(), __c.end()); } @@ -2071,7 +2074,7 @@ void deque<_Tp, _Allocator>::__add_front_capacity() { // Else need to allocate 1 buffer, *and* we need to reallocate __map_. else { __split_buffer<pointer, __pointer_allocator&> __buf( - std::max<size_type>(2 * __map_.capacity(), 1), 0, __map_.__alloc_); + std::max<size_type>(2 * __map_.capacity(), 1), 0, __map_.__get_allocator()); typedef __allocator_destructor<_Allocator> _Dp; unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size)); @@ -2080,10 +2083,7 @@ void deque<_Tp, _Allocator>::__add_front_capacity() { for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i) __buf.emplace_back(*__i); - std::swap(__map_.__first_, __buf.__first_); - std::swap(__map_.__begin_, __buf.__begin_); - std::swap(__map_.__end_, __buf.__end_); - std::swap(__map_.__cap_, __buf.__cap_); + __map_.__swap_without_allocator(__buf); __start_ = __map_.size() == 1 ? __block_size / 2 : __start_ + __block_size; } __annotate_whole_block(0, __asan_poison); @@ -2134,7 +2134,7 @@ void deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) { else { size_type __ds = (__nb + __back_capacity) * __block_size - __map_.empty(); __split_buffer<pointer, __pointer_allocator&> __buf( - std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), 0, __map_.__alloc_); + std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), 0, __map_.__get_allocator()); # if _LIBCPP_HAS_EXCEPTIONS try { # endif // _LIBCPP_HAS_EXCEPTIONS @@ -2157,10 +2157,7 @@ void deque<_Tp, _Allocator>::__add_front_capacity(size_type __n) { } for (__map_pointer __i = __map_.begin(); __i != __map_.end(); ++__i) __buf.emplace_back(*__i); - std::swap(__map_.__first_, __buf.__first_); - std::swap(__map_.__begin_, __buf.__begin_); - std::swap(__map_.__end_, __buf.__end_); - std::swap(__map_.__cap_, __buf.__cap_); + __map_.__swap_without_allocator(__buf); __start_ += __ds; } } @@ -2194,7 +2191,7 @@ void deque<_Tp, _Allocator>::__add_back_capacity() { // Else need to allocate 1 buffer, *and* we need to reallocate __map_. else { __split_buffer<pointer, __pointer_allocator&> __buf( - std::max<size_type>(2 * __map_.capacity(), 1), __map_.size(), __map_.__alloc_); + std::max<size_type>(2 * __map_.capacity(), 1), __map_.size(), __map_.__get_allocator()); typedef __allocator_destructor<_Allocator> _Dp; unique_ptr<pointer, _Dp> __hold(__alloc_traits::allocate(__a, __block_size), _Dp(__a, __block_size)); @@ -2203,10 +2200,7 @@ void deque<_Tp, _Allocator>::__add_back_capacity() { for (__map_pointer __i = __map_.end(); __i != __map_.begin();) __buf.emplace_front(*--__i); - std::swap(__map_.__first_, __buf.__first_); - std::swap(__map_.__begin_, __buf.__begin_); - std::swap(__map_.__end_, __buf.__end_); - std::swap(__map_.__cap_, __buf.__cap_); + __map_.__swap_without_allocator(__buf); __annotate_whole_block(__map_.size() - 1, __asan_poison); } } @@ -2259,7 +2253,7 @@ void deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) { __split_buffer<pointer, __pointer_allocator&> __buf( std::max<size_type>(2 * __map_.capacity(), __nb + __map_.size()), __map_.size() - __front_capacity, - __map_.__alloc_); + __map_.__get_allocator()); # if _LIBCPP_HAS_EXCEPTIONS try { # endif // _LIBCPP_HAS_EXCEPTIONS @@ -2282,10 +2276,7 @@ void deque<_Tp, _Allocator>::__add_back_capacity(size_type __n) { } for (__map_pointer __i = __map_.end(); __i != __map_.begin();) __buf.emplace_front(*--__i); - std::swap(__map_.__first_, __buf.__first_); - std::swap(__map_.__begin_, __buf.__begin_); - std::swap(__map_.__end_, __buf.__end_); - std::swap(__map_.__cap_, __buf.__cap_); + __map_.__swap_without_allocator(__buf); __start_ -= __ds; } } diff --git a/libcxx/test/libcxx/type_traits/is_replaceable.compile.pass.cpp b/libcxx/test/libcxx/type_traits/is_replaceable.compile.pass.cpp index 546240a6c3286..c04e9443c8e67 100644 --- a/libcxx/test/libcxx/type_traits/is_replaceable.compile.pass.cpp +++ b/libcxx/test/libcxx/type_traits/is_replaceable.compile.pass.cpp @@ -133,16 +133,58 @@ static_assert(!std::__is_replaceable<CustomMoveAssignment>::value, ""); // ---------------------- // __split_buffer -static_assert(std::__is_replaceable<std::__split_buffer<int> >::value, ""); -static_assert(std::__is_replaceable<std::__split_buffer<NotTriviallyCopyable> >::value, ""); -static_assert(!std::__is_replaceable<std::__split_buffer<int, NonPropagatingStatefulCopyAssignAlloc<int> > >::value, - ""); -static_assert(!std::__is_replaceable<std::__split_buffer<int, NonPropagatingStatefulMoveAssignAlloc<int> > >::value, - ""); -static_assert(std::__is_replaceable<std::__split_buffer<int, NonPropagatingStatelessCopyAssignAlloc<int> > >::value, +static_assert( + std::__is_replaceable<std::__split_buffer<int, std::allocator<int>, std::__split_buffer_pointer_layout> >::value, + ""); +static_assert(std::__is_replaceable<std::__split_buffer<NotTriviallyCopyable, + std::allocator<NotTriviallyCopyable>, + std::__split_buffer_pointer_layout> >::value, ""); -static_assert(std::__is_replaceable<std::__split_buffer<int, NonPropagatingStatelessMoveAssignAlloc<int> > >::value, +static_assert( + !std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatefulCopyAssignAlloc<int>, std::__split_buffer_pointer_layout > >:: + value, + ""); +static_assert( + !std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatefulMoveAssignAlloc<int>, std::__split_buffer_pointer_layout > >:: + value, + ""); +static_assert( + std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatelessCopyAssignAlloc<int>, std::__split_buffer_pointer_layout > >:: + value, + ""); +static_assert( + std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatelessMoveAssignAlloc<int>, std::__split_buffer_pointer_layout > >:: + value, + ""); + +static_assert( + std::__is_replaceable<std::__split_buffer<int, std::allocator<int>, std::__split_buffer_size_layout> >::value, ""); +static_assert(std::__is_replaceable<std::__split_buffer<NotTriviallyCopyable, + std::allocator<NotTriviallyCopyable>, + std::__split_buffer_size_layout> >::value, ""); +static_assert( + !std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatefulCopyAssignAlloc<int>, std::__split_buffer_size_layout > >::value, + ""); +static_assert( + !std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatefulMoveAssignAlloc<int>, std::__split_buffer_size_layout > >::value, + ""); +static_assert( + std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatelessCopyAssignAlloc<int>, std::__split_buffer_size_layout > >:: + value, + ""); +static_assert( + std::__is_replaceable< + std::__split_buffer<int, NonPropagatingStatelessMoveAssignAlloc<int>, std::__split_buffer_size_layout > >:: + value, + ""); // standard library types // ---------------------- diff --git a/libcxx/test/libcxx/type_traits/is_trivially_relocatable.compile.pass.cpp b/libcxx/test/libcxx/type_traits/is_trivially_relocatable.compile.pass.cpp index c462672616f77..10889eb50870d 100644 --- a/libcxx/test/libcxx/type_traits/is_trivially_relocatable.compile.pass.cpp +++ b/libcxx/test/libcxx/type_traits/is_trivially_relocatable.compile.pass.cpp @@ -68,9 +68,27 @@ static_assert(!std::__libcpp_is_trivially_relocatable<NonTrivialDestructor>::val // ---------------------- // __split_buffer -static_assert(std::__libcpp_is_trivially_relocatable<std::__split_buffer<int> >::value, ""); -static_assert(std::__libcpp_is_trivially_relocatable<std::__split_buffer<NotTriviallyCopyable> >::value, ""); -static_assert(!std::__libcpp_is_trivially_relocatable<std::__split_buffer<int, test_allocator<int> > >::value, ""); +static_assert(std::__libcpp_is_trivially_relocatable< + std::__split_buffer<int, std::allocator<int>, std::__split_buffer_pointer_layout> >::value, + ""); +static_assert(std::__libcpp_is_trivially_relocatable<std::__split_buffer<NotTriviallyCopyable, + std::allocator<NotTriviallyCopyable>, + std::__split_buffer_pointer_layout> >::value, + ""); +static_assert(!std::__libcpp_is_trivially_relocatable< + std::__split_buffer<int, test_allocator<int>, std::__split_buffer_pointer_layout > >::value, + ""); + +static_assert(std::__libcpp_is_trivially_relocatable< + std::__split_buffer<int, std::allocator<int>, std::__split_buffer_size_layout> >::value, + ""); +static_assert(std::__libcpp_is_trivially_relocatable<std::__split_buffer<NotTriviallyCopyable, + std::allocator<NotTriviallyCopyable>, + std::__split_buffer_size_layout> >::value, + ""); +static_assert(!std::__libcpp_is_trivially_relocatable< + std::__split_buffer<int, test_allocator<int>, std::__split_buffer_size_layout > >::value, + ""); // standard library types // ---------------------- diff --git a/lldb/examples/synthetic/libcxx.py b/lldb/examples/synthetic/libcxx.py index 5abeb3061f4f5..549255e280c1d 100644 --- a/lldb/examples/synthetic/libcxx.py +++ b/lldb/examples/synthetic/libcxx.py @@ -1,3 +1,6 @@ +from enum import Enum +from sys import stderr +import sys import lldb import lldb.formatters.Logger @@ -74,6 +77,59 @@ def stdstring_SummaryProvider(valobj, dict): return '"' + strval + '"' +def get_buffer_end(buffer, begin): + """ + Returns a pointer to where the next element would be pushed. + + For libc++'s stable ABI and unstable < LLVM 22, returns `__end_`. + For libc++'s unstable ABI, returns `__begin_ + __size_`. + """ + map_end = buffer.GetChildMemberWithName("__end_") + if map_end.IsValid(): + return map_end.GetValueAsUnsigned(0) + map_size = buffer.GetChildMemberWithName("__size_").GetValueAsUnsigned(0) + return begin + map_size + + +def get_buffer_endcap(parent, buffer, begin, has_compressed_pair_layout, is_size_based): + """ + Returns a pointer to the end of the buffer. + + For libc++'s stable ABI and unstable < LLVM 22, returns: + * `__end_cap_`, if `__compressed_pair` is being used + * `__cap_`, otherwise + For libc++'s unstable ABI, returns `__begin_ + __cap_`. + """ + if has_compressed_pair_layout: + map_endcap = parent._get_value_of_compressed_pair( + buffer.GetChildMemberWithName("__end_cap_") + ) + elif buffer.GetType().GetNumberOfDirectBaseClasses() == 1: + # LLVM 22's __split_buffer is derived from a base class that describes its layout. When the + # compressed pair ABI is required, we also use an anonymous struct. Per [#158131], LLDB + # is unable to access members of an anonymous struct to a base class, through the derived + # class. This means that in order to access the compressed pair's pointer, we need to first + # get to its base class. + # + # [#158131]: https://github.com/llvm/llvm-project/issues/158131 + buffer = buffer.GetChildAtIndex(0) + if is_size_based: + map_endcap = buffer.GetChildMemberWithName("__cap_") + else: + map_endcap = buffer.GetChildMemberWithName("__back_cap_") + map_endcap = map_endcap.GetValueAsUnsigned(0) + else: + map_endcap = buffer.GetChildMemberWithName("__cap_") + if not map_endcap.IsValid(): + map_endcap = buffer.GetChildMemberWithName("__end_cap_") + map_endcap = map_endcap.GetValueAsUnsigned(0) + + if is_size_based: + return begin + map_endcap + + return map_endcap + + class stdvector_SynthProvider: def __init__(self, valobj, dict): logger = lldb.formatters.Logger.Logger() @@ -755,23 +811,21 @@ def update(self): if self.block_size < 0: logger.write("block_size < 0") return - map_ = self.valobj.GetChildMemberWithName("__map_") start = self.valobj.GetChildMemberWithName("__start_").GetValueAsUnsigned(0) + + map_ = self.valobj.GetChildMemberWithName("__map_") + is_size_based = map_.GetChildMemberWithName("__size_").IsValid() first = map_.GetChildMemberWithName("__first_") + # LLVM 22 renames __map_.__begin_ to __map_.__front_cap_ + if not first: + first = map_.GetChildMemberWithName("__front_cap_") map_first = first.GetValueAsUnsigned(0) self.map_begin = map_.GetChildMemberWithName("__begin_") map_begin = self.map_begin.GetValueAsUnsigned(0) - map_end = map_.GetChildMemberWithName("__end_").GetValueAsUnsigned(0) - - if has_compressed_pair_layout: - map_endcap = self._get_value_of_compressed_pair( - map_.GetChildMemberWithName("__end_cap_") - ) - else: - map_endcap = map_.GetChildMemberWithName("__cap_") - if not map_endcap.IsValid(): - map_endcap = map_.GetChildMemberWithName("__end_cap_") - map_endcap = map_endcap.GetValueAsUnsigned(0) + map_end = get_buffer_end(map_, map_begin) + map_endcap = get_buffer_endcap( + self, map_, map_begin, has_compressed_pair_layout, is_size_based + ) # check consistency if not map_first <= map_begin <= map_end <= map_endcap: _______________________________________________ lldb-commits mailing list lldb-commits@lists.llvm.org https://lists.llvm.org/cgi-bin/mailman/listinfo/lldb-commits
