[libc++] Add __pointer_int_pair

[philnik]

Summary

This is an implementation detail for move_only_function

[philnik]

Generate output

[philnik]

Try to fix CI

[philnik]

Try to fix CI

[philnik]

Next try

[philnik]

Next try

[ldionne]

libcxx/include/__math_h/log2i.h

9 ↗

(On Diff #483936)

Why is this not just under __math?

23 ↗

(On Diff #483936)

We might as well add a comment explaining what the function does (compute the base-2 log of an integral type)?

27 ↗

(On Diff #483936)

Here and elsewhere?

libcxx/include/__utility/pointer_int_pair.h

63–65

I really feel like the parameters should be the other way around here, because this is really a pair, and we always specify both types in a pair. I suggest we do this:

enum class __bitfield_width : size_t { };

template <class _Pointer, class _IntType, __bitfield_width __int_bit_count>
struct __pointer_int_pair;

This way, we can do this, which is more obvious than what we have right now IMO:

__pointer_int_pair<Overaligned*, size_t, __bitfield_width(2)>

In particular, I don't see why we have a default size_t type for the integral type. I don't think it makes sense, since this tries to be a general pointer-and-integral-type pair.

66

I think this can be defined as a typedef inside the class?

80–85

_LIBCPP_HIDE_FROM_ABI

87

Please add a test that uses the implicit syntax here to lock in this behavior. I think it's useful to have this be non-explicit so you can do something like return {ptr, int} when you know that the return type is a __pointer_int_pair, but I think it should be locked with a test.

103–104

I would hold off creating this until you need it (which may be in the very next patch, but then we can see it in context and decide whether it pulls its weight).

110–111

I would just inline it like this. I missed the __pointer prefix when I first read it and I thought this was a bug -- I think it's a bit confusing and doesn't save a lot of typing.

116–118

Those could be constexpr, not that it wins us very much.

libcxx/test/libcxx/utilities/pointer_int_pair/constructor_assert.pass.cpp

2

Let's name this assert.constructor.pass.cpp -- I've been trying to do this consistently.

libcxx/test/libcxx/utilities/pointer_int_pair/pointer_int_pair.pass.cpp

14–17

You could use ADDITIONAL_COMPILE_FLAGS: -Wno-private-header instead.

21

Please test that you can constinit a pointer-int-pair.

23

Please test with an overaligned type and with more than 2 bits for the integer.

25

Please test with a non-std::size_t type, like bool and a few others.

[Mordante]

Mainly curious, can you give an indication how much space this would save?

libcxx/include/__math_h/log2i.h

9 ↗

(On Diff #483936)

Actually I think this file should be removed. Instead we should make __bit_log2 in <bit> available in all language versions.

[tschuett]

LLVM ships the same type: PointerIntPair.

[ldionne]

In D140278#4008229, @tschuett wrote:

LLVM ships the same type: PointerIntPair.

This is heavily inspired from it, but we're still tweaking the API as we think makes the most sense. Since this is a private type, we can always end up changing the API if we find the we like something closer to the original one better.

[ldionne]

libcxx/include/__utility/pointer_int_pair.h

2

Note for when we come back to this review: do we need to care about endianness? This was raised by @huixie90 during the live review of D142063.

libcxx/include/CMakeLists.txt

set(files
   __iterator/readable_traits.h
   __iterator/reverse_access.h
   __iterator/reverse_iterator.h
   __iterator/size.h
   __iterator/sortable.h
   __iterator/unreachable_sentinel.h
   __iterator/wrap_iter.h
   __locale
+  __math/log2i.h
   __mbstate_t.h
   __memory/addressof.h
   __memory/align.h
   __memory/allocate_at_least.h
   __memory/allocation_guard.h
   __memory/allocator.h
   __memory/allocator_arg_t.h
   __memory/allocator_destructor.h
set(files
   __utility/exchange.h
   __utility/forward.h
   __utility/forward_like.h
   __utility/in_place.h
   __utility/integer_sequence.h
   __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
   __utility/swap.h
   __utility/to_underlying.h
   __utility/transaction.h
   __utility/unreachable.h
   __variant/monostate.h

libcxx/include/__algorithm/sort.h

 #include <__algorithm/unwrap_iter.h>
 #include <__bits>
 #include <__config>
 #include <__debug>
 #include <__debug_utils/randomize_range.h>
 #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>
 #include <climits>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
if (__i - __first < __last - __i) {
       __first = ++__i;
     } else {
       std::__introsort<_AlgPolicy, _Compare>(__i + difference_type(1), __last, __comp, __depth);
       __last = __i;
     }
   }
 }
 
-template <typename _Number>
-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<unsigned>(__n));
-  if (sizeof(__n) <= sizeof(unsigned long))
-    return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n));
-  if (sizeof(__n) <= sizeof(unsigned long long))
-    return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n));
-
-  _Number __log2 = 0;
-  while (__n > 1) {
-    __log2++;
-    __n >>= 1;
-  }
-  return __log2;
-}
-
 template <class _WrappedComp, class _RandomAccessIterator>
 _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;
   using _Compare = typename _Unwrap::_Comp;
   _Compare __comp = _Unwrap::__get_comp(__wrapped_comp);
   std::__introsort<_AlgPolicy, _Compare>(__first, __last, __comp, __depth_limit);
 }
 

libcxx/include/__math/log2i.h

+//===----------------------------------------------------------------------===//
+//
+// 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 <climits>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+template <typename _Number>
+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<unsigned>(__n));
+  if (sizeof(__n) <= sizeof(unsigned long))
+    return sizeof(unsigned long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long>(__n));
+  if (sizeof(__n) <= sizeof(unsigned long long))
+    return sizeof(unsigned long long) * CHAR_BIT - 1 - __libcpp_clz(static_cast<unsigned long long>(__n));
+
+  _Number __log2 = 0;
+  while (__n > 1) {
+    __log2++;
+    __n >>= 1;
+  }
+  return __log2;
+}
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP___MATH_LOG2I_H

libcxx/include/__utility/pointer_int_pair.h

+//===----------------------------------------------------------------------===//
+//
+// 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 <cstddef>
+#include <cstdint>
+
+#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 <class>
+struct _PointerLikeTraits;
+
+template <class _Tp>
+  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<uintptr_t>(__ptr); }
+  static _LIBCPP_HIDE_FROM_ABI _Tp* __to_pointer(uintptr_t __ptr) { return reinterpret_cast<_Tp*>(__ptr); }
+};
+
+template <class _Tp>
+  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<uintptr_t>(__ptr); }
+  static _LIBCPP_HIDE_FROM_ABI _Tp* __to_pointer(uintptr_t __ptr) { return reinterpret_cast<_Tp*>(__ptr); }
+};
+
+template <class _Pointer,
+          size_t __int_bit_count,
+          class _IntType       = size_t,
+          class _PointerTraits = _PointerLikeTraits<_Pointer>>
+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<uintptr_t>(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 <class>
+  friend struct _PointerLikeTraits;
+};
+
+template <class _Pointer>
+using __pointer_bool_pair = __pointer_int_pair<_Pointer, 1, bool>;
+
+template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
+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 <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
+struct tuple_size<__pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>>
+    : integral_constant<size_t, 2> {};
+
+template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
+struct tuple_element<0, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> {
+  using type = _Pointer;
+};
+
+template <class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
+struct tuple_element<1, __pointer_int_pair<_Pointer, __int_bit_count, _IntType, _PointerTraits>> {
+  using type = _IntType;
+};
+
+template <size_t __i, class _Pointer, size_t __int_bit_count, class _IntType, class _PointerTraits>
+_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

libcxx/test/libcxx/utilities/pointer_int_pair/constructor_assert.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <cassert>
+
+#include "check_assertion.h"
+
+struct [[gnu::packed]] Packed {
+  char c;
+  int i;
+};
+
+int main(int, char**) {
+  TEST_LIBCPP_ASSERT_FAILURE((std::__pointer_int_pair<int*, 1>{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<int*, 1>{&p.i, 0}), "Pointer alignment is too low!");
+  TEST_DIAGNOSTIC_POP
+
+  return 0;
+}

libcxx/test/libcxx/utilities/pointer_int_pair/pointer_int_pair.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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 <cassert>
+
+int main(int, char**) {
+  {
+    std::__pointer_int_pair<int*, 1> pair = {};
+    assert(pair.__get_value() == 0);
+    assert(pair.__get_ptr() == nullptr);
+  }
+  {
+    std::__pointer_int_pair<int*, 1> pair(nullptr, 1);
+    assert(pair.__get_value() == 1);
+    assert(pair.__get_ptr() == nullptr);
+  }
+  {
+    int i;
+    std::__pointer_int_pair<int*, 1> pair(&i, 0);
+    assert(pair.__get_value() == 0);
+    assert(pair.__get_ptr() == &i);
+  }
+  {
+    int i;
+    std::__pointer_int_pair<int*, 2> pair(&i, 2);
+    assert(pair.__get_value() == 2);
+    assert(pair.__get_ptr() == &i);
+  }
+  {
+    short i;
+    std::__pointer_int_pair<short*, 1> pair(&i, 1);
+    assert(pair.__get_value() == 1);
+    assert(pair.__get_ptr() == &i);
+  }
+  {
+    int i;
+    std::__pointer_int_pair<std::__pointer_int_pair<int*, 1>, 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<int*, 2> pair{&i, 3};
+    auto [ptr, value] = pair;
+    assert(ptr == &i);
+    assert(value == 3);
+  }
+
+  return 0;
+}

libcxx/test/libcxx/utilities/pointer_int_pair/static_asserts.verify.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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<char*, 2> ptr1; // expected-note {{here}}
+// expected-error-re@*:* {{{{static_assert|static assertion}} failed {{.*}}_IntType has to be an integral type}}
+std::__pointer_int_pair<int*, 2, int*> 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<int*, 2, signed> ptr3; // expected-note {{here}}