Implement small object optimization in swisstable - disabled for now.

Details:
- We use the space for control/slots pointers as the inline buffer.
- We use a max inline capacity of 1 to make the implementation much simpler and to avoid having to randomize the iteration order for inline tables.
- For iteration of inline tables, we introduce the kSooControl buffer which just has 1 full control byte followed by 1 sentinel control byte so that incrementing yields an end() iterator. We don't access kSooControl during lookups - only iteration.
PiperOrigin-RevId: 613253492
Change-Id: Id98ff11842f8bef27ac7ed88138dc03b46ce4fa6

1 files changed, 50 insertions, 41 deletions

diff --git a/absl/container/flat_hash_set_test.cc b/absl/container/flat_hash_set_test.cc
index 9ce9267e..b425bc50 100644
--- a/absl/container/flat_hash_set_test.cc
+++ b/absl/container/flat_hash_set_test.cc
@@ -181,15 +181,13 @@ TEST(FlatHashSet, EraseIf) {
   }
 }
 
-class PoisonInline {
+class PoisonSoo {
   int64_t data_;
 
  public:
-  explicit PoisonInline(int64_t d) : data_(d) {
-    SanitizerPoisonObject(&data_);
-  }
-  PoisonInline(const PoisonInline& that) : PoisonInline(*that) {}
-  ~PoisonInline() { SanitizerUnpoisonObject(&data_); }
+  explicit PoisonSoo(int64_t d) : data_(d) { SanitizerPoisonObject(&data_); }
+  PoisonSoo(const PoisonSoo& that) : PoisonSoo(*that) {}
+  ~PoisonSoo() { SanitizerUnpoisonObject(&data_); }
 
   int64_t operator*() const {
     SanitizerUnpoisonObject(&data_);
@@ -198,45 +196,56 @@ class PoisonInline {
     return ret;
   }
   template <typename H>
-  friend H AbslHashValue(H h, const PoisonInline& pi) {
+  friend H AbslHashValue(H h, const PoisonSoo& pi) {
     return H::combine(std::move(h), *pi);
   }
-  bool operator==(const PoisonInline& rhs) const { return **this == *rhs; }
+  bool operator==(const PoisonSoo& rhs) const { return **this == *rhs; }
 };
 
-// Tests that we don't touch the poison_ member of PoisonInline.
-TEST(FlatHashSet, PoisonInline) {
-  PoisonInline a(0), b(1);
-  {  // basic usage
-    flat_hash_set<PoisonInline> set;
-    set.insert(a);
-    EXPECT_THAT(set, UnorderedElementsAre(a));
-    set.insert(b);
-    EXPECT_THAT(set, UnorderedElementsAre(a, b));
-    set.erase(a);
-    EXPECT_THAT(set, UnorderedElementsAre(b));
-    set.rehash(0);  // shrink to inline
-    EXPECT_THAT(set, UnorderedElementsAre(b));
-  }
-  {  // test move constructor from inline to inline
-    flat_hash_set<PoisonInline> set;
-    set.insert(a);
-    flat_hash_set<PoisonInline> set2(std::move(set));
-    EXPECT_THAT(set2, UnorderedElementsAre(a));
-  }
-  {  // test move assignment from inline to inline
-    flat_hash_set<PoisonInline> set, set2;
-    set.insert(a);
-    set2 = std::move(set);
-    EXPECT_THAT(set2, UnorderedElementsAre(a));
-  }
-  {  // test alloc move constructor from inline to inline
-    flat_hash_set<PoisonInline> set;
-    set.insert(a);
-    flat_hash_set<PoisonInline> set2(std::move(set),
-                                     std::allocator<PoisonInline>());
-    EXPECT_THAT(set2, UnorderedElementsAre(a));
-  }
+TEST(FlatHashSet, PoisonSooBasic) {
+  PoisonSoo a(0), b(1);
+  flat_hash_set<PoisonSoo> set;
+  set.insert(a);
+  EXPECT_THAT(set, UnorderedElementsAre(a));
+  set.insert(b);
+  EXPECT_THAT(set, UnorderedElementsAre(a, b));
+  set.erase(a);
+  EXPECT_THAT(set, UnorderedElementsAre(b));
+  set.rehash(0);  // Shrink to SOO.
+  EXPECT_THAT(set, UnorderedElementsAre(b));
+}
+
+TEST(FlatHashSet, PoisonSooMoveConstructSooToSoo) {
+  PoisonSoo a(0);
+  flat_hash_set<PoisonSoo> set;
+  set.insert(a);
+  flat_hash_set<PoisonSoo> set2(std::move(set));
+  EXPECT_THAT(set2, UnorderedElementsAre(a));
+}
+
+TEST(FlatHashSet, PoisonSooAllocMoveConstructSooToSoo) {
+  PoisonSoo a(0);
+  flat_hash_set<PoisonSoo> set;
+  set.insert(a);
+  flat_hash_set<PoisonSoo> set2(std::move(set), std::allocator<PoisonSoo>());
+  EXPECT_THAT(set2, UnorderedElementsAre(a));
+}
+
+TEST(FlatHashSet, PoisonSooMoveAssignFullSooToEmptySoo) {
+  PoisonSoo a(0);
+  flat_hash_set<PoisonSoo> set, set2;
+  set.insert(a);
+  set2 = std::move(set);
+  EXPECT_THAT(set2, UnorderedElementsAre(a));
+}
+
+TEST(FlatHashSet, PoisonSooMoveAssignFullSooToFullSoo) {
+  PoisonSoo a(0), b(1);
+  flat_hash_set<PoisonSoo> set, set2;
+  set.insert(a);
+  set2.insert(b);
+  set2 = std::move(set);
+  EXPECT_THAT(set2, UnorderedElementsAre(a));
 }
 
 TEST(FlatHashSet, FlatHashSetPolicyDestroyReturnsTrue) {