diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -394,6 +394,7 @@ __iterator/unreachable_sentinel.h __iterator/wrap_iter.h __locale + __math/log2i.h __mbstate_t.h __memory/addressof.h __memory/align.h @@ -691,6 +692,7 @@ __utility/move.h __utility/pair.h __utility/piecewise_construct.h + __utility/pointer_int_pair.h __utility/priority_tag.h __utility/rel_ops.h __utility/small_buffer.h diff --git a/libcxx/include/__algorithm/sort.h b/libcxx/include/__algorithm/sort.h --- a/libcxx/include/__algorithm/sort.h +++ b/libcxx/include/__algorithm/sort.h @@ -22,6 +22,7 @@ #include <__functional/operations.h> #include <__functional/ranges_operations.h> #include <__iterator/iterator_traits.h> +#include <__math/log2i.h> #include <__memory/destruct_n.h> #include <__memory/unique_ptr.h> #include <__utility/move.h> @@ -604,29 +605,10 @@ } } -template -inline _LIBCPP_HIDE_FROM_ABI _Number __log2i(_Number __n) { - if (__n == 0) - return 0; - if (sizeof(__n) <= sizeof(unsigned)) - return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); - if (sizeof(__n) <= sizeof(unsigned long)) - return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); - if (sizeof(__n) <= sizeof(unsigned long long)) - return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); - - _Number __log2 = 0; - while (__n > 1) { - __log2++; - __n >>= 1; - } - return __log2; -} - template _LIBCPP_HIDDEN void __sort(_RandomAccessIterator __first, _RandomAccessIterator __last, _WrappedComp __wrapped_comp) { typedef typename iterator_traits<_RandomAccessIterator>::difference_type difference_type; - difference_type __depth_limit = 2 * __log2i(__last - __first); + difference_type __depth_limit = 2 * std::__log2i(__last - __first); using _Unwrap = _UnwrapAlgPolicy<_WrappedComp>; using _AlgPolicy = typename _Unwrap::_AlgPolicy; diff --git a/libcxx/include/__math/log2i.h b/libcxx/include/__math/log2i.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__math/log2i.h @@ -0,0 +1,43 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___MATH_LOG2I_H +#define _LIBCPP___MATH_LOG2I_H + +#include <__bits> +#include <__config> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX14 _Number __log2i(_Number __n) { + if (__n == 0) + return 0; + if (sizeof(__n) <= sizeof(unsigned)) + return sizeof(unsigned) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); + if (sizeof(__n) <= sizeof(unsigned long)) + return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); + if (sizeof(__n) <= sizeof(unsigned long long)) + return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast(__n)); + + _Number __log2 = 0; + while (__n > 1) { + __log2++; + __n >>= 1; + } + return __log2; +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___MATH_LOG2I_H diff --git a/libcxx/include/__utility/pointer_int_pair.h b/libcxx/include/__utility/pointer_int_pair.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__utility/pointer_int_pair.h @@ -0,0 +1,153 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___UTILITY_POINTER_INT_PAIR_H +#define _LIBCPP___UTILITY_POINTER_INT_PAIR_H + +#include <__assert> +#include <__concepts/derived_from.h> +#include <__config> +#include <__math/log2i.h> +#include <__tuple/tuple_element.h> +#include <__tuple/tuple_size.h> +#include <__type_traits/is_pointer.h> +#include <__type_traits/is_unsigned.h> +#include <__type_traits/is_void.h> +#include <__type_traits/remove_pointer.h> +#include <__utility/swap.h> +#include +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +#if _LIBCPP_STD_VER >= 23 + +// A __pointer_int_pair is a pair of a pointer and an integral type. The lower bits of the pointer that are free +// due to the alignment requirement of the pointee are used to store the integral type. +// +// This imposes a constraint on the number of bits available for the integral type -- the integral type can use +// at most log2(alignof(T)) bits. This technique allows storing the integral type without additional storage +// beyond that of the pointer itself, at the cost of some bit twiddling. + +_LIBCPP_BEGIN_NAMESPACE_STD + +template +struct _PointerLikeTraits; + +template + requires(!is_void_v<_Tp>) +struct _PointerLikeTraits<_Tp*> { + static constexpr size_t __low_bits_available = std::__log2i(alignof(_Tp)); + + static _LIBCPP_HIDE_FROM_ABI uintptr_t __to_uintptr(_Tp* __ptr) { return reinterpret_cast(__ptr); } + static _LIBCPP_HIDE_FROM_ABI _Tp* __to_pointer(uintptr_t __ptr) { return reinterpret_cast<_Tp*>(__ptr); } +}; + +template + requires is_void_v<_Tp> +struct _PointerLikeTraits<_Tp*> { + static constexpr size_t __low_bits_available = 0; + + static _LIBCPP_HIDE_FROM_ABI uintptr_t __to_uintptr(_Tp* __ptr) { return reinterpret_cast(__ptr); } + static _LIBCPP_HIDE_FROM_ABI _Tp* __to_pointer(uintptr_t __ptr) { return reinterpret_cast<_Tp*>(__ptr); } +}; + +template > +class __pointer_int_pair { + static_assert(__int_bit_count <= _PointerTraits::__low_bits_available, + "Not enough bits available for requested bit count"); + static_assert(is_integral_v<_IntType>, "_IntType has to be an integral type"); + static_assert(is_unsigned_v<_IntType>, "__pointer_int_pair doesn't work for signed types"); + + static constexpr size_t __extra_bits = _PointerTraits::__low_bits_available - __int_bit_count; + static constexpr uintptr_t __int_mask = static_cast(1 << _PointerTraits::__low_bits_available) - 1; + static constexpr uintptr_t __ptr_mask = ~__int_mask; + + uintptr_t __value_ = 0; + +public: + __pointer_int_pair() = default; + __pointer_int_pair(const __pointer_int_pair&) = default; + __pointer_int_pair(__pointer_int_pair&&) = default; + __pointer_int_pair& operator=(const __pointer_int_pair&) = default; + __pointer_int_pair& operator=(__pointer_int_pair&&) = default; + ~__pointer_int_pair() = default; + + _LIBCPP_HIDE_FROM_ABI __pointer_int_pair(_Pointer __ptr_value, _IntType __int_value) + : __value_(_PointerTraits::__to_uintptr(__ptr_value) | (__int_value << __extra_bits)) { + _LIBCPP_ASSERT((__int_value & (__int_mask >> __extra_bits)) == __int_value, "integer is too large!"); + _LIBCPP_ASSERT( + (_PointerTraits::__to_uintptr(__ptr_value) & __ptr_mask) == _PointerTraits::__to_uintptr(__ptr_value), + "Pointer alignment is too low!"); + } + + constexpr _LIBCPP_HIDE_FROM_ABI _IntType __get_value() const { return (__value_ & __int_mask) >> __extra_bits; } + + _LIBCPP_HIDE_FROM_ABI _Pointer __get_ptr() const { return _PointerTraits::__to_pointer(__value_ & __ptr_mask); } + + template + friend struct _PointerLikeTraits; +}; + +template +using __pointer_bool_pair = __pointer_int_pair<_Pointer, 1, bool>; + +template +struct _PointerLikeTraits<__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> { +private: + using _PointerIntPair = __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>; + static constexpr size_t __pointer_low_bits_available = _PointerLikeTraits<_Pointer>::__low_bits_available; + static_assert(__pointer_low_bits_available >= __int_bit_count); + +public: + static constexpr size_t __low_bits_available = __pointer_low_bits_available - __int_bit_count; + + static _LIBCPP_HIDE_FROM_ABI uintptr_t __to_uintptr(_PointerIntPair __ptr) { return __ptr.__value_; } + + static _LIBCPP_HIDE_FROM_ABI _PointerIntPair __to_pointer(uintptr_t __ptr) { + _PointerIntPair __tmp{}; + __tmp.__value_ = __ptr; + return __tmp; + } +}; + +// Make __pointer_int_pair tuple-like + +template +struct tuple_size<__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> + : integral_constant {}; + +template +struct tuple_element<0, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> { + using type = _Pointer; +}; + +template +struct tuple_element<1, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> { + using type = _IntType; +}; + +template +_LIBCPP_HIDE_FROM_ABI auto get(__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits> __pair) { + if constexpr (__i == 0) { + return __pair.__get_ptr(); + } else { + return __pair.__get_value(); + } +} + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP_STD_VER >= 23 + +#endif // _LIBCPP___UTILITY_POINTER_INT_PAIR_H diff --git a/libcxx/test/libcxx/utilities/pointer_int_pair/constructor_assert.pass.cpp b/libcxx/test/libcxx/utilities/pointer_int_pair/constructor_assert.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/utilities/pointer_int_pair/constructor_assert.pass.cpp @@ -0,0 +1,40 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// REQUIRES: has-unix-headers +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 +// XFAIL: use_system_cxx_lib && target={{.+}}-apple-macosx{{10.9|10.10|10.11|10.12|10.13|10.14|10.15|11.0|12.0}} +// ADDITIONAL_COMPILE_FLAGS: -D_LIBCPP_ENABLE_ASSERTIONS=1 + +#include "test_macros.h" + +TEST_DIAGNOSTIC_PUSH +TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header") +#include <__utility/pointer_int_pair.h> +TEST_DIAGNOSTIC_POP + +#include + +#include "check_assertion.h" + +struct [[gnu::packed]] Packed { + char c; + int i; +}; + +int main(int, char**) { + TEST_LIBCPP_ASSERT_FAILURE((std::__pointer_int_pair{nullptr, 2}), "integer is too large!"); + + TEST_DIAGNOSTIC_PUSH + TEST_CLANG_DIAGNOSTIC_IGNORED("-Waddress-of-packed-member") // That's what we're trying to test + Packed p; + TEST_LIBCPP_ASSERT_FAILURE((std::__pointer_int_pair{&p.i, 0}), "Pointer alignment is too low!"); + TEST_DIAGNOSTIC_POP + + return 0; +} diff --git a/libcxx/test/libcxx/utilities/pointer_int_pair/pointer_int_pair.pass.cpp b/libcxx/test/libcxx/utilities/pointer_int_pair/pointer_int_pair.pass.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/utilities/pointer_int_pair/pointer_int_pair.pass.cpp @@ -0,0 +1,65 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20 + +#include "test_macros.h" + +TEST_DIAGNOSTIC_PUSH +TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header") +#include <__utility/pointer_int_pair.h> +TEST_DIAGNOSTIC_POP + +#include + +int main(int, char**) { + { + std::__pointer_int_pair pair = {}; + assert(pair.__get_value() == 0); + assert(pair.__get_ptr() == nullptr); + } + { + std::__pointer_int_pair pair(nullptr, 1); + assert(pair.__get_value() == 1); + assert(pair.__get_ptr() == nullptr); + } + { + int i; + std::__pointer_int_pair pair(&i, 0); + assert(pair.__get_value() == 0); + assert(pair.__get_ptr() == &i); + } + { + int i; + std::__pointer_int_pair pair(&i, 2); + assert(pair.__get_value() == 2); + assert(pair.__get_ptr() == &i); + } + { + short i; + std::__pointer_int_pair pair(&i, 1); + assert(pair.__get_value() == 1); + assert(pair.__get_ptr() == &i); + } + { + int i; + std::__pointer_int_pair, 1> pair({&i, 1}, 0); + assert(pair.__get_value() == 0); + assert(pair.__get_ptr().__get_ptr() == &i); + assert(pair.__get_ptr().__get_value() == 1); + } + { + int i; + std::__pointer_int_pair pair{&i, 3}; + auto [ptr, value] = pair; + assert(ptr == &i); + assert(value == 3); + } + + return 0; +} diff --git a/libcxx/test/libcxx/utilities/pointer_int_pair/static_asserts.verify.cpp b/libcxx/test/libcxx/utilities/pointer_int_pair/static_asserts.verify.cpp new file mode 100644 --- /dev/null +++ b/libcxx/test/libcxx/utilities/pointer_int_pair/static_asserts.verify.cpp @@ -0,0 +1,21 @@ +//===----------------------------------------------------------------------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "test_macros.h" + +TEST_DIAGNOSTIC_PUSH +TEST_CLANG_DIAGNOSTIC_IGNORED("-Wprivate-header") +#include <__utility/pointer_int_pair.h> +TEST_DIAGNOSTIC_POP + +// expected-error-re@*:* {{{{static_assert|static assertion}} failed {{.*}}Not enough bits available for requested bit count}} +std::__pointer_int_pair ptr1; // expected-note {{here}} +// expected-error-re@*:* {{{{static_assert|static assertion}} failed {{.*}}_IntType has to be an integral type}} +std::__pointer_int_pair ptr2; // expected-note {{here}} +// expected-error-re@*:* {{{{static_assert|static assertion}} failed {{.*}}__pointer_int_pair doesn't work for signed types}} +std::__pointer_int_pair ptr3; // expected-note {{here}}