Share type-erased SwissTable policy functions across tables with trivially relocatable slots.

For example, a map from int64 to int64 and a map from a 64-bit enum to a pointer now share a single policy function table and growth transfer function.

Lookup and insertion paths are unchanged.

PiperOrigin-RevId: 1014272242
diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 6aa12ae..2eaa721 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -2034,7 +2034,7 @@
 
 constexpr size_t kProbedElementIndexSentinel = ~size_t{};
 
-// Implementation detail of transfer_unprobed_elements_to_next_capacity_fn.
+// Implementation detail of TransferUnprobedElementsToNextCapacity.
 // Tries to find the new index for an element with `hash` for growth to the next
 // capacity.
 // Returns kProbedElementIndexSentinel if element was probed in the table before
@@ -2199,6 +2199,10 @@
   };
 };
 
+// Transfers the contents of `count` slots from src_slot to dst_slot.
+using TransferNFn = void (*)(void* set, void* dst_slot, void* src_slot,
+                             size_t count);
+
 // PolicyFunctions bundles together some information for a particular
 // raw_hash_set<T, ...> instantiation. This information is passed to
 // type-erased functions that want to do small amounts of type-specific
@@ -2214,7 +2218,7 @@
 
   // Transfers the contents of `count` slots from src_slot to dst_slot.
   // We use ability to transfer several slots in single group table growth.
-  void (*transfer_n)(void* set, void* dst_slot, void* src_slot, size_t count);
+  TransferNFn transfer_n;
 
   const AllocPolicy* alloc_policy;
 
@@ -2238,6 +2242,25 @@
   const void* hash_fn(const CommonFields& common) const {
     return reinterpret_cast<const char*>(&common) + hasher_offset;
   }
+
+  // Returns the `PolicyFunctions` instance for tables with trivially
+  // relocatable slots. All function pointers are independent of the
+  // `raw_hash_set` type, so the instance is shared across all `raw_hash_set`
+  // instantiations with the same slot size, hasher offset, type erased slot
+  // hash function and `AllocPolicy` (which is itself shared for the default
+  // allocator).
+  template <uint32_t kSlotSize, uint32_t kHasherOffset, HashSlotFn kHashSlot,
+            const AllocPolicy* kAllocPolicy>
+  static constexpr const PolicyFunctions& GetRelocatableRef() {
+    return P<kSlotSize, kHasherOffset, kHashSlot, kAllocPolicy>::kP;
+  }
+
+ private:
+  // Short name is used to minimize the mangled name length of static variables
+  // and reduce linker input size.
+  template <uint32_t kSlotSize, uint32_t kHasherOffset, HashSlotFn kHashSlot,
+            const AllocPolicy* kAllocPolicy>
+  struct P;
 };
 
 using DestroySlotFn = void (*)(void* set, void* slot);
@@ -2478,6 +2501,99 @@
   memcpy(dst, src, SizeOfSlot * count);
 }
 
+// Implementation of
+// `PolicyFunctions::transfer_unprobed_elements_to_next_capacity`.
+// `Traits` describes the slot layout and operations:
+//   static constexpr size_t kSlotSize;
+//   // Returns the hash of the slot.
+//   static size_t HashSlot(CommonFields& common, void* slot, size_t seed);
+//   // Transfers `src_slot` into `dst_slot`.
+//   static void TransferSlot(CommonFields& common, void* dst_slot,
+//                            void* src_slot);
+// See `RelocatableSlotTransferTraits` (shared across tables with trivially
+// relocatable slots) and `raw_hash_set::TransferTraits`.
+template <class Traits>
+void TransferUnprobedElementsToNextCapacity(
+    CommonFields& __restrict common, const ctrl_t* old_ctrl,
+    void* probed_storage, void* __restrict old_slots, size_t old_capacity,
+    void (*encode_probed_element)(void* probed_storage, size_t hash,
+                                  size_t source_offset)) {
+  constexpr size_t kSlotSize = Traits::kSlotSize;
+  ABSL_ASSUME(old_capacity + 1 >= Group::kWidth);
+  ABSL_ASSUME((old_capacity + 1) % Group::kWidth == 0);
+  const size_t new_capacity = NextCapacity(old_capacity);
+  ABSL_ASSUME(new_capacity > kMaxSmallCapacity);
+  ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity);
+
+  const size_t seed = common.seed().seed();
+  ctrl_t* new_ctrl = common.control();
+  char* new_slots = static_cast<char*>(common.slot_array(new_capacity));
+  char* old_slots_ptr = static_cast<char*>(old_slots);
+
+  for (size_t group_index = 0; group_index < old_capacity;
+       group_index += Group::kWidth) {
+    GroupFullEmptyOrDeleted old_g(old_ctrl + group_index);
+    std::memset(new_ctrl + group_index, static_cast<int8_t>(ctrl_t::kEmpty),
+                Group::kWidth);
+    std::memset(new_ctrl + group_index + old_capacity + 1,
+                static_cast<int8_t>(ctrl_t::kEmpty), Group::kWidth);
+    // TODO(b/382423690): try to type erase everything outside of the loop.
+    // We will share a lot of code in expense of one function call per group.
+    for (auto in_fixed_group_index : old_g.MaskFull()) {
+      size_t old_index = group_index + in_fixed_group_index;
+      char* old_slot = old_slots_ptr + old_index * kSlotSize;
+      // TODO(b/382423690): try to avoid entire hash calculation since we need
+      // only one new bit of h1.
+      size_t hash = Traits::HashSlot(common, old_slot, seed);
+      size_t new_index = TryFindNewIndexWithoutProbing(
+          hash, old_index, old_capacity, new_capacity);
+      // Note that encode_probed_element is allowed to use old_ctrl buffer
+      // till and included the old_index.
+      if (ABSL_PREDICT_FALSE(new_index == kProbedElementIndexSentinel)) {
+        encode_probed_element(probed_storage, hash, old_index);
+        continue;
+      }
+      ABSL_SWISSTABLE_ASSERT((new_index & old_capacity) <= old_index);
+      ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[new_index]));
+      new_ctrl[new_index] = static_cast<ctrl_t>(H2(hash));
+      char* new_slot = new_slots + new_index * kSlotSize;
+      SanitizerUnpoisonMemoryRegion(new_slot, kSlotSize);
+      Traits::TransferSlot(common, new_slot, old_slot);
+      SanitizerPoisonMemoryRegion(old_slot, kSlotSize);
+    }
+  }
+}
+
+// `Traits` for `TransferUnprobedElementsToNextCapacity` for trivially
+// relocatable slots. Slots are transferred with memcpy and hashed with the type
+// erased `kHashSlot`, so the same instantiation is shared by all tables with
+// the same slot size, hasher offset and type erased slot hash function.
+template <size_t kSize, uint32_t kHasherOffset, HashSlotFn kHashSlot>
+struct RelocatableSlotTransferTraits {
+  static constexpr size_t kSlotSize = kSize;
+  static size_t HashSlot(CommonFields& common, void* slot, size_t seed) {
+    return kHashSlot(reinterpret_cast<const char*>(&common) + kHasherOffset,
+                     slot, seed);
+  }
+  static void TransferSlot(CommonFields&, void* dst_slot, void* src_slot) {
+    std::memcpy(dst_slot, src_slot, kSlotSize);
+  }
+};
+
+template <uint32_t kSlotSize, uint32_t kHasherOffset, HashSlotFn kHashSlot,
+          const AllocPolicy* kAllocPolicy>
+struct PolicyFunctions::P {
+  static constexpr PolicyFunctions kP = {
+      kSlotSize,
+      kHasherOffset,
+      kHashSlot,
+      &TransferNRelocatable<kSlotSize>,
+      kAllocPolicy,
+      &TransferUnprobedElementsToNextCapacity<
+          RelocatableSlotTransferTraits<kSlotSize, kHasherOffset, kHashSlot>>,
+  };
+};
+
 // Given the hash of a value not currently in the table and the first group with
 // an empty slot in the probe sequence, finds a viable slot to insert it at.
 //
@@ -4402,59 +4518,6 @@
                : &raw_hash_set::destroy_slot_fn_impl;
   }
 
-  // TODO(b/382423690): Try to type erase entire function or at least type erase
-  // by GetKey + Hash for memcpyable types.
-  // TODO(b/382423690): Try to type erase for big slots: sizeof(slot_type) > 16.
-  static void transfer_unprobed_elements_to_next_capacity_fn(
-      CommonFields& __restrict common, const ctrl_t* old_ctrl,
-      void* probed_storage, void* __restrict old_slots, size_t old_capacity,
-      void (*encode_probed_element)(void* probed_storage, size_t hash,
-                                    size_t source_offset)) {
-    ABSL_ASSUME(old_capacity + 1 >= Group::kWidth);
-    ABSL_ASSUME((old_capacity + 1) % Group::kWidth == 0);
-    const size_t new_capacity = NextCapacity(old_capacity);
-    ABSL_ASSUME(new_capacity > kMaxSmallCapacity);
-    ABSL_SWISSTABLE_ASSERT(common.capacity() == new_capacity);
-
-    auto* set = reinterpret_cast<raw_hash_set*>(&common);
-    slot_type* old_slots_ptr = to_slot(old_slots);
-    ctrl_t* new_ctrl = common.control();
-    slot_type* new_slots = set->slot_array(new_capacity);
-
-    for (size_t group_index = 0; group_index < old_capacity;
-         group_index += Group::kWidth) {
-      GroupFullEmptyOrDeleted old_g(old_ctrl + group_index);
-      std::memset(new_ctrl + group_index, static_cast<int8_t>(ctrl_t::kEmpty),
-                  Group::kWidth);
-      std::memset(new_ctrl + group_index + old_capacity + 1,
-                  static_cast<int8_t>(ctrl_t::kEmpty), Group::kWidth);
-      // TODO(b/382423690): try to type erase everything outside of the loop.
-      // We will share a lot of code in expense of one function call per group.
-      for (auto in_fixed_group_index : old_g.MaskFull()) {
-        size_t old_index = group_index + in_fixed_group_index;
-        slot_type* old_slot = old_slots_ptr + old_index;
-        // TODO(b/382423690): try to avoid entire hash calculation since we need
-        // only one new bit of h1.
-        size_t hash = set->hash_of(old_slot);
-        size_t new_index = TryFindNewIndexWithoutProbing(
-            hash, old_index, old_capacity, new_capacity);
-        // Note that encode_probed_element is allowed to use old_ctrl buffer
-        // till and included the old_index.
-        if (ABSL_PREDICT_FALSE(new_index == kProbedElementIndexSentinel)) {
-          encode_probed_element(probed_storage, hash, old_index);
-          continue;
-        }
-        ABSL_SWISSTABLE_ASSERT((new_index & old_capacity) <= old_index);
-        ABSL_SWISSTABLE_ASSERT(IsEmpty(new_ctrl[new_index]));
-        new_ctrl[new_index] = static_cast<ctrl_t>(H2(hash));
-        auto* new_slot = new_slots + new_index;
-        SanitizerUnpoisonMemoryRegion(new_slot, sizeof(slot_type));
-        set->transfer(new_slot, old_slot);
-        SanitizerPoisonMemoryRegion(old_slot, sizeof(slot_type));
-      }
-    }
-  }
-
   static constexpr DeallocBackingArrayFn get_dealloc_backing_array_fn() {
     return &DeallocateBackingArray<BackingArrayAlignment(alignof(slot_type)),
                                    CharAlloc>;
@@ -4475,6 +4538,11 @@
     }
   }
 
+  static constexpr bool kHasSharedAllocPolicy =
+      BackingArrayAlignment(alignof(slot_type)) ==
+          kStandardBackingArrayAlignment &&
+      kIsDefaultAlloc;
+
   static constexpr const AllocPolicy& GetAllocPolicy() {
     static_assert(sizeof(slot_type) <= (std::numeric_limits<uint32_t>::max)(),
                   "Slot size is too large. Use std::unique_ptr for value type "
@@ -4488,9 +4556,7 @@
                   size_t{(std::numeric_limits<uint16_t>::max)()});
     static_assert(AllocOffset() <=
                   size_t{(std::numeric_limits<uint32_t>::max)()});
-    if constexpr (BackingArrayAlignment(alignof(slot_type)) ==
-                      kStandardBackingArrayAlignment &&
-                  kIsDefaultAlloc) {
+    if constexpr (kHasSharedAllocPolicy) {
       return AllocPolicy::GetNormalRef<
           static_cast<uint32_t>(sizeof(slot_type)),
           static_cast<uint16_t>(alignof(slot_type)),
@@ -4501,19 +4567,51 @@
     }
   }
 
+  // `Traits` for `TransferUnprobedElementsToNextCapacity` for slots that are
+  // not trivially relocatable.
+  struct TransferTraits {
+    static constexpr size_t kSlotSize = sizeof(slot_type);
+    static size_t HashSlot(CommonFields& common, void* slot, size_t) {
+      return reinterpret_cast<raw_hash_set&>(common).hash_of(to_slot(slot));
+    }
+    static void TransferSlot(CommonFields& common, void* dst_slot,
+                             void* src_slot) {
+      reinterpret_cast<raw_hash_set&>(common).transfer(to_slot(dst_slot),
+                                                       to_slot(src_slot));
+    }
+  };
+
   static const PolicyFunctions& GetPolicyFunctions() {
     static_assert(HasherOffset() <=
                   size_t{(std::numeric_limits<uint32_t>::max)()});
-    static constexpr PolicyFunctions value = {
-        static_cast<uint32_t>(sizeof(slot_type)),
-        static_cast<uint32_t>(HasherOffset()),
-        get_hash_slot_fn(),
-        PolicyTraits::transfer_uses_memcpy()
-            ? TransferNRelocatable<sizeof(slot_type)>
-            : &raw_hash_set::transfer_n_slots_fn,
-        &GetAllocPolicy(),
-        &raw_hash_set::transfer_unprobed_elements_to_next_capacity_fn};
-    return value;
+    if constexpr (PolicyTraits::transfer_uses_memcpy() &&
+                  kHasSharedAllocPolicy) {
+      // All function pointers and `AllocPolicy` are independent of the
+      // `raw_hash_set` type, so the instance is shared with other tables with
+      // the same slot size, hasher offset, slot hash function and
+      // `AllocPolicy`.
+      return PolicyFunctions::GetRelocatableRef<
+          static_cast<uint32_t>(sizeof(slot_type)),
+          static_cast<uint32_t>(HasherOffset()), get_hash_slot_fn(),
+          &GetAllocPolicy()>();
+    } else {
+      using Traits = std::conditional_t<
+          PolicyTraits::transfer_uses_memcpy(),
+          RelocatableSlotTransferTraits<
+              sizeof(slot_type), static_cast<uint32_t>(HasherOffset()),
+              get_hash_slot_fn()>,
+          TransferTraits>;
+      static constexpr PolicyFunctions value = {
+          static_cast<uint32_t>(sizeof(slot_type)),
+          static_cast<uint32_t>(HasherOffset()),
+          get_hash_slot_fn(),
+          PolicyTraits::transfer_uses_memcpy()
+              ? &TransferNRelocatable<sizeof(slot_type)>
+              : &raw_hash_set::transfer_n_slots_fn,
+          &GetAllocPolicy(),
+          &TransferUnprobedElementsToNextCapacity<Traits>};
+      return value;
+    }
   }
 
   // `common_` must be the first member: type erased functions cast
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 0db6824..cf288e7 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -91,6 +91,10 @@
   static size_t CountTombstones(const C& c) {
     return c.common().TombstonesCount();
   }
+  template <typename C>
+  static const PolicyFunctions& GetPolicyFunctions() {
+    return C::GetPolicyFunctions();
+  }
 };
 
 namespace {
@@ -5591,6 +5595,69 @@
   }
 }
 
+enum class EnumPtr : uintptr_t {};
+enum class Enum64 : int64_t {};
+
+template <class Table>
+const PolicyFunctions* GetPolicyFunctionsPtr() {
+  return &RawHashSetTestOnlyAccess::GetPolicyFunctions<Table>();
+}
+
+TEST(Table, PolicyFunctionsAreSharedForRelocatableSlots) {
+  // Tables with the same slot layout and type erased slot hash function share
+  // a single `PolicyFunctions` instance. Use pointer-sized integers so that
+  // `alignof(slot_type) <= alignof(size_t)` and `sizeof(EnumPtr) ==
+  // sizeof(const void*)` on both 32-bit and 64-bit platforms.
+  const PolicyFunctions* intptr_pair_policy =
+      GetPolicyFunctionsPtr<absl::flat_hash_map<intptr_t, intptr_t>>();
+  EXPECT_EQ(intptr_pair_policy,
+            (GetPolicyFunctionsPtr<absl::flat_hash_map<uintptr_t, EnumPtr>>()));
+  EXPECT_EQ(
+      intptr_pair_policy,
+      (GetPolicyFunctionsPtr<absl::flat_hash_map<EnumPtr, const void*>>()));
+
+  // Different slot size.
+  EXPECT_NE(intptr_pair_policy,
+            (GetPolicyFunctionsPtr<absl::flat_hash_map<int8_t, int8_t>>()));
+  // Same slot size, but different slot hash function.
+  EXPECT_NE(intptr_pair_policy,
+            GetPolicyFunctionsPtr<absl::flat_hash_set<absl::string_view>>());
+  // Custom allocators have a distinct `AllocPolicy`, so `PolicyFunctions` is
+  // not shared, but the transfer function is still shared.
+  using CustomAllocTable = absl::flat_hash_map<
+      intptr_t, intptr_t, absl::Hash<intptr_t>, std::equal_to<intptr_t>,
+      CountingAllocator<std::pair<const intptr_t, intptr_t>>>;
+  EXPECT_NE(intptr_pair_policy, GetPolicyFunctionsPtr<CustomAllocTable>());
+  EXPECT_EQ(intptr_pair_policy->transfer_unprobed_elements_to_next_capacity,
+            GetPolicyFunctionsPtr<CustomAllocTable>()
+                ->transfer_unprobed_elements_to_next_capacity);
+}
+
+TEST(Table, GrowthWithSharedPolicyFunctions) {
+  // Exercise the shared transfer function across the growth paths from SOO up
+  // to a few resizes, including probed elements, for a few layouts.
+  constexpr int kCount = 25;
+  const auto test = [](auto table) {
+    using T = decltype(table);
+    using V = typename T::key_type;
+    for (int i = 0; i < kCount; ++i) {
+      table.insert(static_cast<V>(i));
+      ASSERT_EQ(table.size(), static_cast<size_t>(i + 1));
+    }
+    for (int i = 0; i < kCount; ++i) {
+      ASSERT_TRUE(table.contains(static_cast<V>(i))) << i;
+    }
+    ASSERT_FALSE(table.contains(static_cast<V>(kCount)));
+  };
+  test(absl::flat_hash_set<int8_t>());
+  test(absl::flat_hash_set<int16_t>());
+  test(absl::flat_hash_set<int32_t>());
+  test(absl::flat_hash_set<int64_t>());
+  test(absl::flat_hash_set<Enum64>());
+  // Non-canonical hasher that forces probing on every growth.
+  test(absl::flat_hash_set<int32_t, ZeroHash>());
+}
+
 }  // namespace
 }  // namespace container_internal
 ABSL_NAMESPACE_END