From 9f1dcc70d64232e77964de9b90e209e23e0110db Mon Sep 17 00:00:00 2001
From: Evan Brown <ezb@google.com>
Date: Thu, 20 Jul 2023 09:56:18 -0700
Subject: Add a special case for erase(begin(), end()) to reset the control
 bytes. The motivation is to avoid potentially expanding the table
 unnecessarily later.

Note: I prefer doing this as a special case in erase(iterator, iterator) rather than special casing erase(iterator) for size==1 because IIUC that changes the time complexity of erase(iterator) from O(1) to O(N) and in pathological cases, it could change loops from O(N) to O(N^2).
PiperOrigin-RevId: 549661855
Change-Id: I8603324260f51a98809db32f840ff09f25cf2481
---
 absl/container/internal/raw_hash_set.h       | 14 ++++++++++----
 absl/container/internal/raw_hash_set_test.cc |  8 ++++++++
 2 files changed, 18 insertions(+), 4 deletions(-)

(limited to 'absl')

diff --git a/absl/container/internal/raw_hash_set.h b/absl/container/internal/raw_hash_set.h
index 1b9f4d89..f0e107be 100644
--- a/absl/container/internal/raw_hash_set.h
+++ b/absl/container/internal/raw_hash_set.h
@@ -1910,8 +1910,7 @@ class raw_hash_set {
       // Already guaranteed to be empty; so nothing to do.
     } else {
       destroy_slots();
-      ClearBackingArray(common(), GetPolicyFunctions(),
-                        /*reuse=*/cap < 128);
+      ClearBackingArray(common(), GetPolicyFunctions(), /*reuse=*/cap < 128);
     }
     common().set_reserved_growth(0);
   }
@@ -2165,6 +2164,14 @@ class raw_hash_set {
 
   iterator erase(const_iterator first,
                  const_iterator last) ABSL_ATTRIBUTE_LIFETIME_BOUND {
+    // We check for empty first because ClearBackingArray requires that
+    // capacity() > 0 as a precondition.
+    if (empty()) return end();
+    if (first == begin() && last == end()) {
+      destroy_slots();
+      ClearBackingArray(common(), GetPolicyFunctions(), /*reuse=*/true);
+      return end();
+    }
     while (first != last) {
       erase(first++);
     }
@@ -2224,8 +2231,7 @@ class raw_hash_set {
   void rehash(size_t n) {
     if (n == 0 && capacity() == 0) return;
     if (n == 0 && size() == 0) {
-      ClearBackingArray(common(), GetPolicyFunctions(),
-                        /*reuse=*/false);
+      ClearBackingArray(common(), GetPolicyFunctions(), /*reuse=*/false);
       return;
     }
 
diff --git a/absl/container/internal/raw_hash_set_test.cc b/absl/container/internal/raw_hash_set_test.cc
index 6cbf6dea..66621cf0 100644
--- a/absl/container/internal/raw_hash_set_test.cc
+++ b/absl/container/internal/raw_hash_set_test.cc
@@ -1093,6 +1093,14 @@ TEST(Table, EraseMaintainsValidIterator) {
   EXPECT_EQ(num_erase_calls, kNumElements);
 }
 
+TEST(Table, EraseBeginEnd) {
+  IntTable t;
+  for (int i = 0; i < 10; ++i) t.insert(i);
+  EXPECT_EQ(t.size(), 10);
+  t.erase(t.begin(), t.end());
+  EXPECT_EQ(t.size(), 0);
+}
+
 // Collect N bad keys by following algorithm:
 // 1. Create an empty table and reserve it to 2 * N.
 // 2. Insert N random elements.
-- 
cgit v1.2.3