[llvm-branch-commits] [libcxx] [libc++] Add ABI flag to make __tree nodes more compact (PR #147681)

[Nikolas Klauser via llvm-branch-commits]

https://github.com/philnik777 created 
https://github.com/llvm/llvm-project/pull/147681

None

>From bd3919aed4aa6cae451541d2ad29f914e2785dc0 Mon Sep 17 00:00:00 2001
From: Nikolas Klauser <nikolasklau...@berlin.de>
Date: Tue, 10 Jun 2025 05:56:20 +0200
Subject: [PATCH] [libc++] Add ABI flag to make __tree nodes more compact

---
 libcxx/include/__configuration/abi.h |  3 ++
 libcxx/include/__tree                | 47 ++++++++++++++++++++++++++--
 2 files changed, 48 insertions(+), 2 deletions(-)

diff --git a/libcxx/include/__configuration/abi.h 
b/libcxx/include/__configuration/abi.h
index cc4b930b3cf4a..b9ef56e76f988 100644
--- a/libcxx/include/__configuration/abi.h
+++ b/libcxx/include/__configuration/abi.h
@@ -116,6 +116,7 @@
 // This setting disables the addition of such artificial padding, leading to a 
more optimal
 // representation for several types.
 #  define _LIBCPP_ABI_NO_COMPRESSED_PAIR_PADDING
+#  define _LIBCPP_ABI_TREE_POINTER_INT_PAIR
 #elif _LIBCPP_ABI_VERSION == 1
 #  if !(defined(_LIBCPP_OBJECT_FORMAT_COFF) || 
defined(_LIBCPP_OBJECT_FORMAT_XCOFF))
 // Enable compiling copies of now inline methods into the dylib to support
@@ -135,6 +136,8 @@
 #  endif
 #endif
 
+#define _LIBCPP_ABI_TREE_POINTER_INT_PAIR
+
 // We had some bugs where we use [[no_unique_address]] together with 
construct_at,
 // which causes UB as the call on construct_at could write to overlapping 
subobjects
 //
diff --git a/libcxx/include/__tree b/libcxx/include/__tree
index 82ffcc13e1f91..e994b5f8c3a51 100644
--- a/libcxx/include/__tree
+++ b/libcxx/include/__tree
@@ -40,6 +40,7 @@
 #include <__utility/forward.h>
 #include <__utility/move.h>
 #include <__utility/pair.h>
+#include <__utility/pointer_int_pair.h>
 #include <__utility/swap.h>
 #include <limits>
 
@@ -61,7 +62,7 @@ class __tree_const_iterator;
 
 template <class _Pointer>
 class __tree_end_node;
-template <class _VoidPtr>
+template <class _VoidPtr, class = void>
 class __tree_node_base;
 template <class _Tp, class _VoidPtr>
 class __tree_node;
@@ -626,7 +627,7 @@ public:
   _LIBCPP_HIDE_FROM_ABI __tree_end_node() _NOEXCEPT : __left_() {}
 };
 
-template <class _VoidPtr>
+template <class _VoidPtr, class>
 class _LIBCPP_STANDALONE_DEBUG __tree_node_base : public 
__tree_node_base_types<_VoidPtr>::__end_node_type {
   typedef __tree_node_base_types<_VoidPtr> _NodeBaseTypes;
 
@@ -654,6 +655,48 @@ public:
   __tree_node_base& operator=(__tree_node_base const&) = delete;
 };
 
+#ifdef _LIBCPP_ABI_TREE_POINTER_INT_PAIR
+template <class _VoidPtr>
+class __tree_node_base<
+    _VoidPtr,
+    __enable_if_t<is_pointer<typename 
__tree_node_base_types<_VoidPtr>::__node_base_pointer>::value> >
+    : public __tree_node_base_types<_VoidPtr>::__end_node_type {
+  using _NodeBaseTypes = __tree_node_base_types<_VoidPtr>;
+
+public:
+  using pointer          = typename _NodeBaseTypes::__node_base_pointer;
+  using __parent_pointer = typename _NodeBaseTypes::__parent_pointer;
+
+  pointer __right_;
+
+private:
+  using __pair_t = __pointer_int_pair<__parent_pointer, bool, 
__integer_width(1)>;
+
+  __pair_t __parent_and_color_;
+
+public:
+  _LIBCPP_HIDE_FROM_ABI pointer __parent_unsafe() const {
+    return static_cast<pointer>(__parent_and_color_.__get_ptr());
+  }
+
+  _LIBCPP_HIDE_FROM_ABI void __set_parent(pointer __ptr) { 
__set_parent(static_cast<__parent_pointer>(__ptr)); }
+
+  _LIBCPP_HIDE_FROM_ABI void __set_parent(__parent_pointer __ptr) {
+    __parent_and_color_ = __pair_t(__ptr, __parent_and_color_.__get_value());
+  }
+
+  _LIBCPP_HIDE_FROM_ABI __parent_pointer __get_parent() const { return 
__parent_and_color_.__get_ptr(); }
+  _LIBCPP_HIDE_FROM_ABI __tree_color __get_color() const {
+    return static_cast<__tree_color>(__parent_and_color_.__get_value());
+  }
+  _LIBCPP_HIDE_FROM_ABI void __set_color(__tree_color __color) {
+    __parent_and_color_ = __pair_t(__parent_and_color_.__get_ptr(), __color == 
__tree_color::__black);
+  }
+};
+#endif // _LIBCPP_ABI_TREE_POINTER_INT_PAIR
+
+static_assert(sizeof(__tree_node_base<void*>) == 24);
+
 template <class _Tp, class _VoidPtr>
 class _LIBCPP_STANDALONE_DEBUG __tree_node : public __tree_node_base<_VoidPtr> 
{
 public:

_______________________________________________
llvm-branch-commits mailing list
llvm-branch-commits@lists.llvm.org
https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-branch-commits