Export of internal Abseil changes

--
d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c by Gennadiy Rozental <rogeeff@google.com>:

Introduce ABSL specific macros for detecting the usage of sanitizers.

PiperOrigin-RevId: 321687443

--
a41342cc04b1088087dda12d7272aa3835f8e36a by Evan Brown <ezb@google.com>:

Get rid of recursion in clear_and_delete().

PiperOrigin-RevId: 321583786

--
99c6d300b17f186c28867b08cc79f1e55077e88a by Evan Brown <ezb@google.com>:

Code simplification: consolidate methods to erase values/nodes.

Motivation: this will make floating storage work simpler.

- Delete erase_same_node/erase_from_leaf_node/remove_value/remove_values_ignore_children.
- Move node deletion methods inside btree_node.
- Delete three-argument move() and use transfer_n() instead.
- Note: there's still one usage of move (in btree::erase(iterator)) that could use transfer, but I think doing so would add more complexity than it's worth.

PiperOrigin-RevId: 321407673

--
c3efed6c1763190c6b3bccbede9b2989ab21b258 by Evan Brown <ezb@google.com>:

Support heterogeneous insert_or_assign, try_emplace, operator[] for btree_map.

Also do a bit of cleanup:
- Add _impl methods for insert_or_assign/try_emplace.
- Rename some hint iterator params from `position` to `hint`.

PiperOrigin-RevId: 321399557
GitOrigin-RevId: d2b7a83bafb90d35b2b7d8eb4177e9d712e8d62c
Change-Id: Ie2d0c7c3ed197c2b53d475248941392cbad20e59

6 files changed, 312 insertions, 294 deletions

diff --git a/absl/base/config.h b/absl/base/config.h
index f54466de..b1e095d3 100644
--- a/absl/base/config.h
+++ b/absl/base/config.h
@@ -154,6 +154,12 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' ||
 #define ABSL_INTERNAL_HAS_KEYWORD(x) 0
 #endif
 
+#ifdef __has_feature
+#define ABSL_HAVE_FEATURE(f) __has_feature(f)
+#else
+#define ABSL_HAVE_FEATURE(f) 0
+#endif
+
 // ABSL_HAVE_TLS is defined to 1 when __thread should be supported.
 // We assume __thread is supported on Linux when compiled with Clang or compiled
 // against libstdc++ with _GLIBCXX_HAVE_TLS defined.
@@ -226,11 +232,9 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' ||
 // * Xcode 9.3 started disallowing `thread_local` for 32-bit iOS simulator
 //   targeting iOS 9.x.
 // * Xcode 10 moves the deployment target check for iOS < 9.0 to link time
-//   making __has_feature unreliable there.
+//   making ABSL_HAVE_FEATURE unreliable there.
 //
-// Otherwise, `__has_feature` is only supported by Clang so it has be inside
-// `defined(__APPLE__)` check.
-#if __has_feature(cxx_thread_local) && \
+#if ABSL_HAVE_FEATURE(cxx_thread_local) && \
     !(TARGET_OS_IPHONE && __IPHONE_OS_VERSION_MIN_REQUIRED < __IPHONE_9_0)
 #define ABSL_HAVE_THREAD_LOCAL 1
 #endif
@@ -312,15 +316,15 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' ||
 
 #if __clang_major__ > 3 || (__clang_major__ == 3 && __clang_minor__ >= 6)
 // Clang >= 3.6
-#if __has_feature(cxx_exceptions)
+#if ABSL_HAVE_FEATURE(cxx_exceptions)
 #define ABSL_HAVE_EXCEPTIONS 1
-#endif  // __has_feature(cxx_exceptions)
+#endif  // ABSL_HAVE_FEATURE(cxx_exceptions)
 #else
 // Clang < 3.6
 // http://releases.llvm.org/3.6.0/tools/clang/docs/ReleaseNotes.html#the-exceptions-macro
-#if defined(__EXCEPTIONS) && __has_feature(cxx_exceptions)
+#if defined(__EXCEPTIONS) && ABSL_HAVE_FEATURE(cxx_exceptions)
 #define ABSL_HAVE_EXCEPTIONS 1
-#endif  // defined(__EXCEPTIONS) && __has_feature(cxx_exceptions)
+#endif  // defined(__EXCEPTIONS) && ABSL_HAVE_FEATURE(cxx_exceptions)
 #endif  // __clang_major__ > 3 || (__clang_major__ == 3 && __clang_minor__ >= 6)
 
 // Handle remaining special cases and default to exceptions being supported.
@@ -661,4 +665,50 @@ static_assert(ABSL_INTERNAL_INLINE_NAMESPACE_STR[0] != 'h' ||
 #define ABSL_DLL
 #endif  // defined(_MSC_VER)
 
+// ABSL_HAVE_MEMORY_SANITIZER
+//
+// MemorySanitizer (MSan) is a detector of uninitialized reads. It consists of
+// a compiler instrumentation module and a run-time library.
+#ifdef ABSL_HAVE_MEMORY_SANITIZER
+#error "ABSL_HAVE_MEMORY_SANITIZER cannot be directly set."
+#elif defined(MEMORY_SANITIZER)
+// The MEMORY_SANITIZER macro is deprecated but we will continue to honor it
+// for now.
+#define ABSL_HAVE_MEMORY_SANITIZER 1
+#elif defined(__SANITIZE_MEMORY__)
+#define ABSL_HAVE_MEMORY_SANITIZER 1
+#elif !defined(__native_client__) && ABSL_HAVE_FEATURE(memory_sanitizer)
+#define ABSL_HAVE_MEMORY_SANITIZER 1
+#endif
+
+// ABSL_HAVE_THREAD_SANITIZER
+//
+// ThreadSanitizer (TSan) is a fast data race detector.
+#ifdef ABSL_HAVE_THREAD_SANITIZER
+#error "ABSL_HAVE_THREAD_SANITIZER cannot be directly set."
+#elif defined(THREAD_SANITIZER)
+// The THREAD_SANITIZER macro is deprecated but we will continue to honor it
+// for now.
+#define ABSL_HAVE_THREAD_SANITIZER 1
+#elif defined(__SANITIZE_THREAD__)
+#define ABSL_HAVE_THREAD_SANITIZER 1
+#elif ABSL_HAVE_FEATURE(thread_sanitizer)
+#define ABSL_HAVE_THREAD_SANITIZER 1
+#endif
+
+// ABSL_HAVE_ADDRESS_SANITIZER
+//
+// AddressSanitizer (ASan) is a fast memory error detector.
+#ifdef ABSL_HAVE_ADDRESS_SANITIZER
+#error "ABSL_HAVE_ADDRESS_SANITIZER cannot be directly set."
+#elif defined(ADDRESS_SANITIZER)
+// The ADDRESS_SANITIZER macro is deprecated but we will continue to honor it
+// for now.
+#define ABSL_HAVE_ADDRESS_SANITIZER 1
+#elif defined(__SANITIZE_ADDRESS__)
+#define ABSL_HAVE_ADDRESS_SANITIZER 1
+#elif ABSL_HAVE_FEATURE(address_sanitizer)
+#define ABSL_HAVE_ADDRESS_SANITIZER 1
+#endif
+
 #endif  // ABSL_BASE_CONFIG_H_
diff --git a/absl/base/dynamic_annotations.h b/absl/base/dynamic_annotations.h
index 1444dc48..5ea697b7 100644
--- a/absl/base/dynamic_annotations.h
+++ b/absl/base/dynamic_annotations.h
@@ -53,19 +53,9 @@
 #include "absl/base/internal/dynamic_annotations.h"  // IWYU pragma: export
 
 // -------------------------------------------------------------------------
-// Decide which features are enabled
+// Decide which features are enabled.
 
-#ifndef DYNAMIC_ANNOTATIONS_ENABLED
-#define DYNAMIC_ANNOTATIONS_ENABLED 0
-#endif
-
-#if defined(__clang__) && !defined(SWIG)
-#define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 1
-#else
-#define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 0
-#endif
-
-#if DYNAMIC_ANNOTATIONS_ENABLED != 0
+#ifdef ABSL_HAVE_THREAD_SANITIZER
 
 #define ABSL_INTERNAL_RACE_ANNOTATIONS_ENABLED 1
 #define ABSL_INTERNAL_READS_ANNOTATIONS_ENABLED 1
@@ -85,24 +75,21 @@
 // will issue a warning, if these attributes are compiled. Only include them
 // when compiling using Clang.
 
-// ANNOTALYSIS_ENABLED == 1 when IGNORE_READ_ATTRIBUTE_ENABLED == 1
-#define ABSL_INTERNAL_ANNOTALYSIS_ENABLED \
-  ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED
-// Read/write annotations are enabled in Annotalysis mode; disabled otherwise.
-#define ABSL_INTERNAL_READS_WRITES_ANNOTATIONS_ENABLED \
-  ABSL_INTERNAL_ANNOTALYSIS_ENABLED
-#endif
-
-// Memory annotations are also made available to LLVM's Memory Sanitizer
-#if defined(MEMORY_SANITIZER) && defined(__has_feature) && \
-    !defined(__native_client__)
-#if __has_feature(memory_sanitizer)
-#define ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED 1
+#if defined(__clang__)
+#define ABSL_INTERNAL_ANNOTALYSIS_ENABLED 1
+#if !defined(SWIG)
+#define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 1
+#else
+#define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 0
 #endif
+#else
+#define ABSL_INTERNAL_ANNOTALYSIS_ENABLED 0
+#define ABSL_INTERNAL_IGNORE_READS_ATTRIBUTE_ENABLED 0
 #endif
 
-#ifndef ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED
-#define ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED 0
+// Read/write annotations are enabled in Annotalysis mode; disabled otherwise.
+#define ABSL_INTERNAL_READS_WRITES_ANNOTATIONS_ENABLED \
+  ABSL_INTERNAL_ANNOTALYSIS_ENABLED
 #endif
 
 #ifdef __cplusplus
@@ -243,7 +230,7 @@ ABSL_INTERNAL_END_EXTERN_C
 // -------------------------------------------------------------------------
 // Define memory annotations.
 
-#if ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED == 1
+#ifdef ABSL_HAVE_MEMORY_SANITIZER
 
 #include <sanitizer/msan_interface.h>
 
@@ -253,9 +240,10 @@ ABSL_INTERNAL_END_EXTERN_C
 #define ABSL_ANNOTATE_MEMORY_IS_UNINITIALIZED(address, size) \
   __msan_allocated_memory(address, size)
 
-#else  // ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED == 0
+#else  // !defined(ABSL_HAVE_MEMORY_SANITIZER)
 
-#if DYNAMIC_ANNOTATIONS_ENABLED == 1
+// TODO(rogeeff): remove this branch
+#ifdef ABSL_HAVE_THREAD_SANITIZER
 #define ABSL_ANNOTATE_MEMORY_IS_INITIALIZED(address, size) \
   do {                                                     \
     (void)(address);                                       \
@@ -273,7 +261,7 @@ ABSL_INTERNAL_END_EXTERN_C
 
 #endif
 
-#endif  // ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED
+#endif  // ABSL_HAVE_MEMORY_SANITIZER
 
 // -------------------------------------------------------------------------
 // Define IGNORE_READS_BEGIN/_END attributes.
@@ -468,7 +456,7 @@ ABSL_INTERNAL_END_EXTERN_C
 // -------------------------------------------------------------------------
 // Address sanitizer annotations
 
-#ifdef ADDRESS_SANITIZER
+#ifdef ABSL_HAVE_ADDRESS_SANITIZER
 // Describe the current state of a contiguous container such as e.g.
 // std::vector or std::string. For more details see
 // sanitizer/common_interface_defs.h, which is provided by the compiler.
@@ -483,16 +471,15 @@ ABSL_INTERNAL_END_EXTERN_C
 
 #else
 
-#define ABSL_ANNOTATE_CONTIGUOUS_CONTAINER(beg, end, old_mid, new_mid)
+#define ABSL_ANNOTATE_CONTIGUOUS_CONTAINER(beg, end, old_mid, new_mid)  // empty
 #define ABSL_ADDRESS_SANITIZER_REDZONE(name) static_assert(true, "")
 
-#endif  // ADDRESS_SANITIZER
+#endif  // ABSL_HAVE_ADDRESS_SANITIZER
 
 // -------------------------------------------------------------------------
 // Undefine the macros intended only for this file.
 
 #undef ABSL_INTERNAL_RACE_ANNOTATIONS_ENABLED
-#undef ABSL_INTERNAL_MEMORY_ANNOTATIONS_ENABLED
 #undef ABSL_INTERNAL_READS_ANNOTATIONS_ENABLED
 #undef ABSL_INTERNAL_WRITES_ANNOTATIONS_ENABLED
 #undef ABSL_INTERNAL_ANNOTALYSIS_ENABLED
diff --git a/absl/container/btree_test.cc b/absl/container/btree_test.cc
index c5808074..67ee7521 100644
--- a/absl/container/btree_test.cc
+++ b/absl/container/btree_test.cc
@@ -2509,6 +2509,39 @@ TEST(Btree,
   EXPECT_THAT(m2,
               ElementsAre(Pair(IsEmpty(), 1), Pair(ElementsAre(IsNull()), 2)));
 }
+
+TEST(Btree, HeterogeneousTryEmplace) {
+  absl::btree_map<std::string, int> m;
+  std::string s = "key";
+  absl::string_view sv = s;
+  m.try_emplace(sv, 1);
+  EXPECT_EQ(m[s], 1);
+
+  m.try_emplace(m.end(), sv, 2);
+  EXPECT_EQ(m[s], 1);
+}
+
+TEST(Btree, HeterogeneousOperatorMapped) {
+  absl::btree_map<std::string, int> m;
+  std::string s = "key";
+  absl::string_view sv = s;
+  m[sv] = 1;
+  EXPECT_EQ(m[s], 1);
+
+  m[sv] = 2;
+  EXPECT_EQ(m[s], 2);
+}
+
+TEST(Btree, HeterogeneousInsertOrAssign) {
+  absl::btree_map<std::string, int> m;
+  std::string s = "key";
+  absl::string_view sv = s;
+  m.insert_or_assign(sv, 1);
+  EXPECT_EQ(m[s], 1);
+
+  m.insert_or_assign(m.end(), sv, 2);
+  EXPECT_EQ(m[s], 2);
+}
 #endif
 
 }  // namespace
diff --git a/absl/container/internal/btree.h b/absl/container/internal/btree.h
index 996afa61..188631d1 100644
--- a/absl/container/internal/btree.h
+++ b/absl/container/internal/btree.h
@@ -255,10 +255,6 @@ struct common_params {
   static void move(Alloc *alloc, slot_type *src, slot_type *dest) {
     slot_policy::move(alloc, src, dest);
   }
-  static void move(Alloc *alloc, slot_type *first, slot_type *last,
-                   slot_type *result) {
-    slot_policy::move(alloc, first, last, result);
-  }
 };
 
 // A parameters structure for holding the type parameters for a btree_map.
@@ -336,13 +332,6 @@ struct set_slot_policy {
   static void move(Alloc * /*alloc*/, slot_type *src, slot_type *dest) {
     *dest = std::move(*src);
   }
-
-  template <typename Alloc>
-  static void move(Alloc *alloc, slot_type *first, slot_type *last,
-                   slot_type *result) {
-    for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
-      move(alloc, src, dest);
-  }
 };
 
 // A parameters structure for holding the type parameters for a btree_set.
@@ -759,14 +748,10 @@ class btree_node {
   template <typename... Args>
   void emplace_value(size_type i, allocator_type *alloc, Args &&... args);
 
-  // Removes the value at position i, shifting all existing values and children
-  // at positions > i to the left by 1.
-  void remove_value(int i, allocator_type *alloc);
-
-  // Removes the values at positions [i, i + to_erase), shifting all values
-  // after that range to the left by to_erase. Does not change children at all.
-  void remove_values_ignore_children(int i, int to_erase,
-                                     allocator_type *alloc);
+  // Removes the values at positions [i, i + to_erase), shifting all existing
+  // values and children after that range to the left by to_erase. Clears all
+  // children between [i, i + to_erase).
+  void remove_values(field_type i, field_type to_erase, allocator_type *alloc);
 
   // Rebalances a node with its right sibling.
   void rebalance_right_to_left(int to_move, btree_node *right,
@@ -778,7 +763,7 @@ class btree_node {
   void split(int insert_position, btree_node *dest, allocator_type *alloc);
 
   // Merges a node with its right sibling, moving all of the values and the
-  // delimiting key in the parent node onto itself.
+  // delimiting key in the parent node onto itself, and deleting the src node.
   void merge(btree_node *src, allocator_type *alloc);
 
   // Node allocation/deletion routines.
@@ -799,12 +784,15 @@ class btree_node {
     absl::container_internal::SanitizerPoisonMemoryRegion(
         &mutable_child(start()), (kNodeValues + 1) * sizeof(btree_node *));
   }
-  void destroy(allocator_type *alloc) {
-    for (int i = start(); i < finish(); ++i) {
-      value_destroy(i, alloc);
-    }
+
+  static void deallocate(const size_type size, btree_node *node,
+                         allocator_type *alloc) {
+    absl::container_internal::Deallocate<Alignment()>(alloc, node, size);
   }
 
+  // Deletes a node and all of its children.
+  static void clear_and_delete(btree_node *node, allocator_type *alloc);
+
  public:
   // Exposed only for tests.
   static bool testonly_uses_linear_node_search() {
@@ -813,14 +801,21 @@ class btree_node {
 
  private:
   template <typename... Args>
-  void value_init(const size_type i, allocator_type *alloc, Args &&... args) {
+  void value_init(const field_type i, allocator_type *alloc, Args &&... args) {
     absl::container_internal::SanitizerUnpoisonObject(slot(i));
     params_type::construct(alloc, slot(i), std::forward<Args>(args)...);
   }
-  void value_destroy(const size_type i, allocator_type *alloc) {
+  void value_destroy(const field_type i, allocator_type *alloc) {
     params_type::destroy(alloc, slot(i));
     absl::container_internal::SanitizerPoisonObject(slot(i));
   }
+  void value_destroy_n(const field_type i, const field_type n,
+                       allocator_type *alloc) {
+    for (slot_type *s = slot(i), *end = slot(i + n); s != end; ++s) {
+      params_type::destroy(alloc, s);
+      absl::container_internal::SanitizerPoisonObject(s);
+    }
+  }
 
   // Transfers value from slot `src_i` in `src_node` to slot `dest_i` in `this`.
   void transfer(const size_type dest_i, const size_type src_i,
@@ -1423,25 +1418,8 @@ class btree {
   }
 
   // Deletion helper routines.
-  void erase_same_node(iterator begin, iterator end);
-  iterator erase_from_leaf_node(iterator begin, size_type to_erase);
   iterator rebalance_after_delete(iterator iter);
 
-  // Deallocates a node of a certain size in bytes using the allocator.
-  void deallocate(const size_type size, node_type *node) {
-    absl::container_internal::Deallocate<node_type::Alignment()>(
-        mutable_allocator(), node, size);
-  }
-
-  void delete_internal_node(node_type *node) {
-    node->destroy(mutable_allocator());
-    deallocate(node_type::InternalSize(), node);
-  }
-  void delete_leaf_node(node_type *node) {
-    node->destroy(mutable_allocator());
-    deallocate(node_type::LeafSize(node->max_count()), node);
-  }
-
   // Rebalances or splits the node iter points to.
   void rebalance_or_split(iterator *iter);
 
@@ -1510,9 +1488,6 @@ class btree {
   template <typename K>
   iterator internal_find(const K &key) const;
 
-  // Deletes a node and all of its children.
-  void internal_clear(node_type *node);
-
   // Verifies the tree structure of node.
   int internal_verify(const node_type *node, const key_type *lo,
                       const key_type *hi) const;
@@ -1580,26 +1555,27 @@ inline void btree_node<P>::emplace_value(const size_type i,
 }
 
 template <typename P>
-inline void btree_node<P>::remove_value(const int i, allocator_type *alloc) {
-  if (!leaf() && finish() > i + 1) {
-    assert(child(i + 1)->count() == 0);
-    for (size_type j = i + 1; j < finish(); ++j) {
-      set_child(j, child(j + 1));
-    }
-    clear_child(finish());
-  }
-
-  remove_values_ignore_children(i, /*to_erase=*/1, alloc);
-}
+inline void btree_node<P>::remove_values(const field_type i,
+                                         const field_type to_erase,
+                                         allocator_type *alloc) {
+  // Transfer values after the removed range into their new places.
+  value_destroy_n(i, to_erase, alloc);
+  const field_type orig_finish = finish();
+  const field_type src_i = i + to_erase;
+  transfer_n(orig_finish - src_i, i, src_i, this, alloc);
 
-template <typename P>
-inline void btree_node<P>::remove_values_ignore_children(
-    const int i, const int to_erase, allocator_type *alloc) {
-  params_type::move(alloc, slot(i + to_erase), finish_slot(), slot(i));
-  for (int j = finish() - to_erase; j < finish(); ++j) {
-    value_destroy(j, alloc);
+  if (!leaf()) {
+    // Delete all children between begin and end.
+    for (field_type j = 0; j < to_erase; ++j) {
+      clear_and_delete(child(i + j + 1), alloc);
+    }
+    // Rotate children after end into new positions.
+    for (field_type j = i + to_erase + 1; j <= orig_finish; ++j) {
+      set_child(j - to_erase, child(j));
+      clear_child(j);
+    }
   }
-  set_finish(finish() - to_erase);
+  set_finish(orig_finish - to_erase);
 }
 
 template <typename P>
@@ -1751,8 +1727,51 @@ void btree_node<P>::merge(btree_node *src, allocator_type *alloc) {
   set_finish(start() + 1 + count() + src->count());
   src->set_finish(src->start());
 
-  // Remove the value on the parent node.
-  parent()->remove_value(position(), alloc);
+  // Remove the value on the parent node and delete the src node.
+  parent()->remove_values(position(), /*to_erase=*/1, alloc);
+}
+
+template <typename P>
+void btree_node<P>::clear_and_delete(btree_node *node, allocator_type *alloc) {
+  if (node->leaf()) {
+    node->value_destroy_n(node->start(), node->count(), alloc);
+    deallocate(LeafSize(node->max_count()), node, alloc);
+    return;
+  }
+  if (node->count() == 0) {
+    deallocate(InternalSize(), node, alloc);
+    return;
+  }
+
+  // The parent of the root of the subtree we are deleting.
+  btree_node *delete_root_parent = node->parent();
+
+  // Navigate to the leftmost leaf under node, and then delete upwards.
+  while (!node->leaf()) node = node->start_child();
+  field_type pos = node->position();
+  btree_node *parent = node->parent();
+  do {
+    // In each iteration of this loop, we delete one leaf node and go right.
+    for (; pos <= parent->finish(); ++pos) {
+      node = parent->child(pos);
+      if (!node->leaf()) {
+        // Navigate to the leftmost leaf under node.
+        while (!node->leaf()) node = node->start_child();
+        pos = node->position();
+        parent = node->parent();
+      }
+      node->value_destroy_n(node->start(), node->count(), alloc);
+      deallocate(LeafSize(node->max_count()), node, alloc);
+    }
+    // If we've deleted all children of parent, then delete parent and go up.
+    for (; parent != delete_root_parent && pos > parent->finish(); ++pos) {
+      node = parent;
+      pos = node->position();
+      parent = node->parent();
+      node->value_destroy_n(node->start(), node->count(), alloc);
+      deallocate(InternalSize(), node, alloc);
+    }
+  } while (parent != delete_root_parent);
 }
 
 ////
@@ -2034,7 +2053,7 @@ auto btree<P>::erase(iterator iter) -> iterator {
   bool internal_delete = false;
   if (!iter.node->leaf()) {
     // Deletion of a value on an internal node. First, move the largest value
-    // from our left child here, then delete that position (in remove_value()
+    // from our left child here, then delete that position (in remove_values()
     // below). We can get to the largest value from our left child by
     // decrementing iter.
     iterator internal_iter(iter);
@@ -2046,7 +2065,7 @@ auto btree<P>::erase(iterator iter) -> iterator {
   }
 
   // Delete the key from the leaf.
-  iter.node->remove_value(iter.position, mutable_allocator());
+  iter.node->remove_values(iter.position, /*to_erase=*/1, mutable_allocator());
   --size_;
 
   // We want to return the next value after the one we just erased. If we
@@ -2121,7 +2140,9 @@ auto btree<P>::erase_range(iterator begin, iterator end)
   }
 
   if (begin.node == end.node) {
-    erase_same_node(begin, end);
+    assert(end.position > begin.position);
+    begin.node->remove_values(begin.position, end.position - begin.position,
+                              mutable_allocator());
     size_ -= count;
     return {count, rebalance_after_delete(begin)};
   }
@@ -2131,8 +2152,11 @@ auto btree<P>::erase_range(iterator begin, iterator end)
     if (begin.node->leaf()) {
       const size_type remaining_to_erase = size_ - target_size;
       const size_type remaining_in_node = begin.node->finish() - begin.position;
-      begin = erase_from_leaf_node(
-          begin, (std::min)(remaining_to_erase, remaining_in_node));
+      const size_type to_erase =
+          (std::min)(remaining_to_erase, remaining_in_node);
+      begin.node->remove_values(begin.position, to_erase, mutable_allocator());
+      size_ -= to_erase;
+      begin = rebalance_after_delete(begin);
     } else {
       begin = erase(begin);
     }
@@ -2141,51 +2165,6 @@ auto btree<P>::erase_range(iterator begin, iterator end)
 }
 
 template <typename P>
-void btree<P>::erase_same_node(iterator begin, iterator end) {
-  assert(begin.node == end.node);
-  assert(end.position > begin.position);
-
-  node_type *node = begin.node;
-  size_type to_erase = end.position - begin.position;
-  if (!node->leaf()) {
-    // Delete all children between begin and end.
-    for (size_type i = 0; i < to_erase; ++i) {
-      internal_clear(node->child(begin.position + i + 1));
-    }
-    // Rotate children after end into new positions.
-    for (size_type i = begin.position + to_erase + 1; i <= node->finish();
-         ++i) {
-      node->set_child(i - to_erase, node->child(i));
-      node->clear_child(i);
-    }
-  }
-  node->remove_values_ignore_children(begin.position, to_erase,
-                                      mutable_allocator());
-
-  // Do not need to update rightmost_, because
-  // * either end == this->end(), and therefore node == rightmost_, and still
-  //   exists
-  // * or end != this->end(), and therefore rightmost_ hasn't been erased, since
-  //   it wasn't covered in [begin, end)
-}
-
-template <typename P>
-auto btree<P>::erase_from_leaf_node(iterator begin, size_type to_erase)
-    -> iterator {
-  node_type *node = begin.node;
-  assert(node->leaf());
-  assert(node->finish() > begin.position);
-  assert(begin.position + to_erase <= node->finish());
-
-  node->remove_values_ignore_children(begin.position, to_erase,
-                                      mutable_allocator());
-
-  size_ -= to_erase;
-
-  return rebalance_after_delete(begin);
-}
-
-template <typename P>
 template <typename K>
 auto btree<P>::erase_unique(const K &key) -> size_type {
   const iterator iter = internal_find(key);
@@ -2213,7 +2192,7 @@ auto btree<P>::erase_multi(const K &key) -> size_type {
 template <typename P>
 void btree<P>::clear() {
   if (!empty()) {
-    internal_clear(root());
+    node_type::clear_and_delete(root(), mutable_allocator());
   }
   mutable_root() = EmptyNode();
   rightmost_ = EmptyNode();
@@ -2354,12 +2333,7 @@ void btree<P>::rebalance_or_split(iterator *iter) {
 template <typename P>
 void btree<P>::merge_nodes(node_type *left, node_type *right) {
   left->merge(right, mutable_allocator());
-  if (right->leaf()) {
-    if (rightmost_ == right) rightmost_ = left;
-    delete_leaf_node(right);
-  } else {
-    delete_internal_node(right);
-  }
+  if (rightmost_ == right) rightmost_ = left;
 }
 
 template <typename P>
@@ -2416,20 +2390,20 @@ bool btree<P>::try_merge_or_rebalance(iterator *iter) {
 
 template <typename P>
 void btree<P>::try_shrink() {
-  if (root()->count() > 0) {
+  node_type *orig_root = root();
+  if (orig_root->count() > 0) {
     return;
   }
   // Deleted the last item on the root node, shrink the height of the tree.
-  if (root()->leaf()) {
+  if (orig_root->leaf()) {
     assert(size() == 0);
-    delete_leaf_node(root());
     mutable_root() = rightmost_ = EmptyNode();
   } else {
-    node_type *child = root()->start_child();
+    node_type *child = orig_root->start_child();
     child->make_root();
-    delete_internal_node(root());
     mutable_root() = child;
   }
+  node_type::clear_and_delete(orig_root, mutable_allocator());
 }
 
 template <typename P>
@@ -2474,7 +2448,7 @@ inline auto btree<P>::internal_emplace(iterator iter, Args &&... args)
                            old_root->start(), old_root, alloc);
       new_root->set_finish(old_root->finish());
       old_root->set_finish(old_root->start());
-      delete_leaf_node(old_root);
+      node_type::clear_and_delete(old_root, alloc);
       mutable_root() = rightmost_ = new_root;
     } else {
       rebalance_or_split(&iter);
@@ -2578,18 +2552,6 @@ auto btree<P>::internal_find(const K &key) const -> iterator {
 }
 
 template <typename P>
-void btree<P>::internal_clear(node_type *node) {
-  if (!node->leaf()) {
-    for (int i = node->start(); i <= node->finish(); ++i) {
-      internal_clear(node->child(i));
-    }
-    delete_internal_node(node);
-  } else {
-    delete_leaf_node(node);
-  }
-}
-
-template <typename P>
 int btree<P>::internal_verify(const node_type *node, const key_type *lo,
                               const key_type *hi) const {
   assert(node->count() > 0);
diff --git a/absl/container/internal/btree_container.h b/absl/container/internal/btree_container.h
index d0fc6451..3b2e8a9e 100644
--- a/absl/container/internal/btree_container.h
+++ b/absl/container/internal/btree_container.h
@@ -268,23 +268,21 @@ class btree_set_container : public btree_container<Tree> {
     init_type v(std::forward<Args>(args)...);
     return this->tree_.insert_unique(params_type::key(v), std::move(v));
   }
-  iterator insert(const_iterator position, const value_type &v) {
+  iterator insert(const_iterator hint, const value_type &v) {
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v), v)
+        .insert_hint_unique(iterator(hint), params_type::key(v), v)
         .first;
   }
-  iterator insert(const_iterator position, value_type &&v) {
+  iterator insert(const_iterator hint, value_type &&v) {
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v),
-                            std::move(v))
+        .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
         .first;
   }
   template <typename... Args>
-  iterator emplace_hint(const_iterator position, Args &&... args) {
+  iterator emplace_hint(const_iterator hint, Args &&... args) {
     init_type v(std::forward<Args>(args)...);
     return this->tree_
-        .insert_hint_unique(iterator(position), params_type::key(v),
-                            std::move(v))
+        .insert_hint_unique(iterator(hint), params_type::key(v), std::move(v))
         .first;
   }
   template <typename InputIterator>
@@ -392,111 +390,72 @@ class btree_map_container : public btree_set_container<Tree> {
   // Insertion routines.
   // Note: the nullptr template arguments and extra `const M&` overloads allow
   // for supporting bitfield arguments.
-  // Note: when we call `std::forward<M>(obj)` twice, it's safe because
-  // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
-  // `ret.second` is false.
-  template <class M>
-  std::pair<iterator, bool> insert_or_assign(const key_type &k, const M &obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_unique(k, k, obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret;
+  template <typename K = key_type, class M>
+  std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k,
+                                             const M &obj) {
+    return insert_or_assign_impl(k, obj);
   }
-  template <class M, key_type * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(key_type &&k, const M &obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, std::move(k), obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret;
+  template <typename K = key_type, class M, K * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, const M &obj) {
+    return insert_or_assign_impl(std::forward<K>(k), obj);
   }
-  template <class M, M * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(const key_type &k, M &&obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, k, std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret;
+  template <typename K = key_type, class M, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(const key_arg<K> &k, M &&obj) {
+    return insert_or_assign_impl(k, std::forward<M>(obj));
   }
-  template <class M, key_type * = nullptr, M * = nullptr>
-  std::pair<iterator, bool> insert_or_assign(key_type &&k, M &&obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_unique(k, std::move(k), std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret;
+  template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+  std::pair<iterator, bool> insert_or_assign(key_arg<K> &&k, M &&obj) {
+    return insert_or_assign_impl(std::forward<K>(k), std::forward<M>(obj));
   }
-  template <class M>
-  iterator insert_or_assign(const_iterator position, const key_type &k,
+  template <typename K = key_type, class M>
+  iterator insert_or_assign(const_iterator hint, const key_arg<K> &k,
                             const M &obj) {
-    const std::pair<iterator, bool> ret =
-        this->tree_.insert_hint_unique(iterator(position), k, k, obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret.first;
+    return insert_or_assign_hint_impl(hint, k, obj);
   }
-  template <class M, key_type * = nullptr>
-  iterator insert_or_assign(const_iterator position, key_type &&k,
-                            const M &obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, std::move(k), obj);
-    if (!ret.second) ret.first->second = obj;
-    return ret.first;
+  template <typename K = key_type, class M, K * = nullptr>
+  iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, const M &obj) {
+    return insert_or_assign_hint_impl(hint, std::forward<K>(k), obj);
   }
-  template <class M, M * = nullptr>
-  iterator insert_or_assign(const_iterator position, const key_type &k,
-                            M &&obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, k, std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret.first;
+  template <typename K = key_type, class M, M * = nullptr>
+  iterator insert_or_assign(const_iterator hint, const key_arg<K> &k, M &&obj) {
+    return insert_or_assign_hint_impl(hint, k, std::forward<M>(obj));
   }
-  template <class M, key_type * = nullptr, M * = nullptr>
-  iterator insert_or_assign(const_iterator position, key_type &&k, M &&obj) {
-    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
-        iterator(position), k, std::move(k), std::forward<M>(obj));
-    if (!ret.second) ret.first->second = std::forward<M>(obj);
-    return ret.first;
+  template <typename K = key_type, class M, K * = nullptr, M * = nullptr>
+  iterator insert_or_assign(const_iterator hint, key_arg<K> &&k, M &&obj) {
+    return insert_or_assign_hint_impl(hint, std::forward<K>(k),
+                                      std::forward<M>(obj));
   }
-  template <typename... Args>
-  std::pair<iterator, bool> try_emplace(const key_type &k, Args &&... args) {
-    return this->tree_.insert_unique(
-        k, std::piecewise_construct, std::forward_as_tuple(k),
-        std::forward_as_tuple(std::forward<Args>(args)...));
+
+  template <typename K = key_type, typename... Args,
+            typename absl::enable_if_t<
+                !std::is_convertible<K, const_iterator>::value, int> = 0>
+  std::pair<iterator, bool> try_emplace(const key_arg<K> &k, Args &&... args) {
+    return try_emplace_impl(k, std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  std::pair<iterator, bool> try_emplace(key_type &&k, Args &&... args) {
-    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
-    // and then using `k` unsequenced. This is safe because the move is into a
-    // forwarding reference and insert_unique guarantees that `key` is never
-    // referenced after consuming `args`.
-    const key_type &key_ref = k;
-    return this->tree_.insert_unique(
-        key_ref, std::piecewise_construct, std::forward_as_tuple(std::move(k)),
-        std::forward_as_tuple(std::forward<Args>(args)...));
+  template <typename K = key_type, typename... Args,
+            typename absl::enable_if_t<
+                !std::is_convertible<K, const_iterator>::value, int> = 0>
+  std::pair<iterator, bool> try_emplace(key_arg<K> &&k, Args &&... args) {
+    return try_emplace_impl(std::forward<K>(k), std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  iterator try_emplace(const_iterator hint, const key_type &k,
+  template <typename K = key_type, typename... Args>
+  iterator try_emplace(const_iterator hint, const key_arg<K> &k,
                        Args &&... args) {
-    return this->tree_
-        .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
-                            std::forward_as_tuple(k),
-                            std::forward_as_tuple(std::forward<Args>(args)...))
-        .first;
+    return try_emplace_hint_impl(hint, k, std::forward<Args>(args)...);
   }
-  template <typename... Args>
-  iterator try_emplace(const_iterator hint, key_type &&k, Args &&... args) {
-    // Note: `key_ref` exists to avoid a ClangTidy warning about moving from `k`
-    // and then using `k` unsequenced. This is safe because the move is into a
-    // forwarding reference and insert_hint_unique guarantees that `key` is
-    // never referenced after consuming `args`.
-    const key_type &key_ref = k;
-    return this->tree_
-        .insert_hint_unique(iterator(hint), key_ref, std::piecewise_construct,
-                            std::forward_as_tuple(std::move(k)),
-                            std::forward_as_tuple(std::forward<Args>(args)...))
-        .first;
+  template <typename K = key_type, typename... Args>
+  iterator try_emplace(const_iterator hint, key_arg<K> &&k, Args &&... args) {
+    return try_emplace_hint_impl(hint, std::forward<K>(k),
+                                 std::forward<Args>(args)...);
   }
-  mapped_type &operator[](const key_type &k) {
+
+  template <typename K = key_type>
+  mapped_type &operator[](const key_arg<K> &k) {
     return try_emplace(k).first->second;
   }
-  mapped_type &operator[](key_type &&k) {
-    return try_emplace(std::move(k)).first->second;
+  template <typename K = key_type>
+  mapped_type &operator[](key_arg<K> &&k) {
+    return try_emplace(std::forward<K>(k)).first->second;
   }
 
   template <typename K = key_type>
@@ -513,6 +472,40 @@ class btree_map_container : public btree_set_container<Tree> {
       base_internal::ThrowStdOutOfRange("absl::btree_map::at");
     return it->second;
   }
+
+ private:
+  // Note: when we call `std::forward<M>(obj)` twice, it's safe because
+  // insert_unique/insert_hint_unique are guaranteed to not consume `obj` when
+  // `ret.second` is false.
+  template <class K, class M>
+  std::pair<iterator, bool> insert_or_assign_impl(K &&k, M &&obj) {
+    const std::pair<iterator, bool> ret =
+        this->tree_.insert_unique(k, std::forward<K>(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret;
+  }
+  template <class K, class M>
+  iterator insert_or_assign_hint_impl(const_iterator hint, K &&k, M &&obj) {
+    const std::pair<iterator, bool> ret = this->tree_.insert_hint_unique(
+        iterator(hint), k, std::forward<K>(k), std::forward<M>(obj));
+    if (!ret.second) ret.first->second = std::forward<M>(obj);
+    return ret.first;
+  }
+
+  template <class K, class... Args>
+  std::pair<iterator, bool> try_emplace_impl(K &&k, Args &&... args) {
+    return this->tree_.insert_unique(
+        k, std::piecewise_construct, std::forward_as_tuple(std::forward<K>(k)),
+        std::forward_as_tuple(std::forward<Args>(args)...));
+  }
+  template <class K, class... Args>
+  iterator try_emplace_hint_impl(const_iterator hint, K &&k, Args &&... args) {
+    return this->tree_
+        .insert_hint_unique(iterator(hint), k, std::piecewise_construct,
+                            std::forward_as_tuple(std::forward<K>(k)),
+                            std::forward_as_tuple(std::forward<Args>(args)...))
+        .first;
+  }
 };
 
 // A common base class for btree_multiset and btree_multimap.
@@ -566,11 +559,11 @@ class btree_multiset_container : public btree_container<Tree> {
   iterator insert(value_type &&v) {
     return this->tree_.insert_multi(std::move(v));
   }
-  iterator insert(const_iterator position, const value_type &v) {
-    return this->tree_.insert_hint_multi(iterator(position), v);
+  iterator insert(const_iterator hint, const value_type &v) {
+    return this->tree_.insert_hint_multi(iterator(hint), v);
   }
-  iterator insert(const_iterator position, value_type &&v) {
-    return this->tree_.insert_hint_multi(iterator(position), std::move(v));
+  iterator insert(const_iterator hint, value_type &&v) {
+    return this->tree_.insert_hint_multi(iterator(hint), std::move(v));
   }
   template <typename InputIterator>
   void insert(InputIterator b, InputIterator e) {
@@ -584,9 +577,9 @@ class btree_multiset_container : public btree_container<Tree> {
     return this->tree_.insert_multi(init_type(std::forward<Args>(args)...));
   }
   template <typename... Args>
-  iterator emplace_hint(const_iterator position, Args &&... args) {
+  iterator emplace_hint(const_iterator hint, Args &&... args) {
     return this->tree_.insert_hint_multi(
-        iterator(position), init_type(std::forward<Args>(args)...));
+        iterator(hint), init_type(std::forward<Args>(args)...));
   }
   iterator insert(node_type &&node) {
     if (!node) return this->end();
diff --git a/absl/container/internal/container_memory.h b/absl/container/internal/container_memory.h
index 536ea398..92a61cc0 100644
--- a/absl/container/internal/container_memory.h
+++ b/absl/container/internal/container_memory.h
@@ -429,13 +429,6 @@ struct map_slot_policy {
                                                    std::move(src->value));
     }
   }
-
-  template <class Allocator>
-  static void move(Allocator* alloc, slot_type* first, slot_type* last,
-                   slot_type* result) {
-    for (slot_type *src = first, *dest = result; src != last; ++src, ++dest)
-      move(alloc, src, dest);
-  }
 };
 
 }  // namespace container_internal