Share the btree empty node across btrees with compatible node headers.

The empty node only depends on the node header layout (field_type and alignment), so move it out of btree into a namespace-scope BtreeEmptyNode<FieldType, Alignment> template and round the alignment up to 16. All btrees with the same field_type and node alignment of at most 16 now share a single empty node.

PiperOrigin-RevId: 1018604643
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 55ff457..d0cf89e 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -569,9 +569,9 @@
   //   // internal nodes.
   //   btree_node *children[kNodeSlots + 1];
   //
-  // This class is only constructed by EmptyNodeType. Normally, pointers to the
-  // layout above are allocated, cast to btree_node*, and de-allocated within
-  // the btree implementation.
+  // This class is never constructed. Pointers to the layout above are
+  // allocated, cast to btree_node*, and de-allocated within the btree
+  // implementation. Empty btrees point to a shared BtreeEmptyNode instead.
   ~btree_node() = default;
   btree_node(btree_node const &) = delete;
   btree_node &operator=(btree_node const &) = delete;
@@ -1337,33 +1337,50 @@
   int position_;
 };
 
+// We use a static empty node for the root/leftmost/rightmost of empty btrees
+// in order to avoid branching in begin()/end(). The empty node only depends on
+// the node's field_type and alignment (not on the full Params), so it is
+// defined outside of btree in order to be shared between all btrees with
+// compatible node headers.
+template <typename FieldType, size_t Alignment>
+struct alignas(Alignment) BtreeEmptyNode {
+  // Mirrors the header of btree_node's layout (see the comment in btree_node).
+  void *parent;
+#ifdef ABSL_BTREE_ENABLE_GENERATIONS
+  uint32_t generation = 0;
+#endif
+  FieldType position = 0;
+  FieldType start = 0;
+  FieldType finish = 0;
+  // max_count must be != kInternalNodeMaxCount (so that this node is regarded
+  // as a leaf node). max_count() is never called when the tree is empty.
+  FieldType max_count = 1;
+
+  constexpr BtreeEmptyNode() : parent(this) {}
+};
+
+template <typename FieldType, size_t Alignment>
+BtreeEmptyNode<FieldType, Alignment> *GetBtreeEmptyNode() {
+  static constexpr BtreeEmptyNode<FieldType, Alignment> empty_node;
+  return const_cast<BtreeEmptyNode<FieldType, Alignment> *>(&empty_node);
+}
+
 template <typename Params>
 class btree {
   using node_type = btree_node<Params>;
   using is_key_compare_to = typename Params::is_key_compare_to;
   using field_type = typename node_type::field_type;
 
-  // We use a static empty node for the root/leftmost/rightmost of empty btrees
-  // in order to avoid branching in begin()/end().
-  struct EmptyNodeType : node_type {
-    using field_type = typename node_type::field_type;
-    node_type *parent;
-#ifdef ABSL_BTREE_ENABLE_GENERATIONS
-    uint32_t generation = 0;
-#endif
-    field_type position = 0;
-    field_type start = 0;
-    field_type finish = 0;
-    // max_count must be != kInternalNodeMaxCount (so that this node is regarded
-    // as a leaf node). max_count() is never called when the tree is empty.
-    field_type max_count = node_type::kInternalNodeMaxCount + 1;
-
-    constexpr EmptyNodeType() : parent(this) {}
-  };
+  // Round the alignment of the empty node up to 16 so that btrees with
+  // different (small) node alignments share the same node.
+  static constexpr size_t kEmptyNodeAlignment =
+      (std::max)(size_t{16}, size_t{node_type::Alignment()});
 
   static node_type *EmptyNode() {
-    alignas(node_type::Alignment()) static constexpr EmptyNodeType empty_node;
-    return const_cast<EmptyNodeType *>(&empty_node);
+    static_assert(node_type::kInternalNodeMaxCount != 1,
+                  "The empty node must be regarded as a leaf node.");
+    return reinterpret_cast<node_type *>(
+        GetBtreeEmptyNode<field_type, kEmptyNodeAlignment>());
   }
 
   enum : uint32_t {